Enabling semantics to improve detection of data races and misuses of lock‐free data structures. (23rd April 2017)

• Record Type: Journal Article
• Authors: Dolz, Manuel F.; Del Rio Astorga, David; Fernández, Javier; Torquati, Massimo; García, José Daniel; García‐Carballeira, Félix; Danelutto, Marco
• Other Names: Lengauer Christian guestEditor.; Bougé Luc guestEditor.; Trystram Denis guestEditor.; Balaji Pavan guestEditor.; Leung Kai‐Cheung guestEditor.
• Is Part Of: Concurrency and computation. Volume 29:Number 15(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-04-23
• Subjects: data race detectors -- parallel programming -- semantics -- wait‐/lock‐free data structures; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4114
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: The rapid progress of multi/many‐core architectures has caused data‐intensive parallel applications not yet fully optimized to deliver the best performance. In the advent of concurrent programming, frameworks offering structured patterns have alleviated developers' burden adapting such applications to multithreaded architectures. While some of these patterns are implemented using synchronization primitives, others avoid them by means of lock‐free data mechanisms. However, lock‐free programming is not straightforward, ensuring an appropriate use of their interfaces can be challenging, since different memory models plus instruction reordering at compiler/processor levels can interfere in the occurrence of data races. The benefits of race detectors are formidable in this sense; however, they may emit false positives if are unaware of the underlying lock‐free structure semantics. To mitigate this issue, this paper extends ThreadSanitizer, a race detection tool, with the semantics of 2 lock‐free data structures: the single‐producer/single‐consumer and the multiple‐producer/multiple‐consumer queues. With it, we are able to drop false positives and detect potential semantic violations. The experimental evaluation, using different queue implementations on a set of μ benchmarks and real applications, demonstrates that it is possible to reduce, on average, 60% the number of data race warnings and detect wrong uses of these structures.