Testing concurrent programs on relaxed memory models
Authors:
Open Access
- 17 July 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 122-132
Abstract
High-performance concurrent libraries, such as lock-free data structures and custom synchronization primitives, are notoriously difficult to write correctly. Such code is often implemented without locks, instead using plain loads and stores and low-level operations like atomic compare-and-swaps and explicit memory fences. Such code must run correctly despite the relaxed memory model of the underlying compiler, virtual machine, and/or hardware. These memory models may reorder the reads and writes issued by a thread, greatly complicating parallel reasoning. We propose Relaxer, a combination of predictive dynamic analysis and software testing, to help programmers write correct, highly-concurrent programs. Our technique works in two phases. First, Relaxer examines a sequentially-consistent run of a program under test and dynamically detects potential data races. These races are used to predict possible violations of sequential consistency under alternate executions on a relaxed memory model. In the second phase, Relaxer re-executes the program with a biased random scheduler and with a conservative simulation of a relaxed memory model in order to create with high probability a predicted sequential consistency violation. These executions can be used to test whether or not a program works as expected when the underlying memory model is not sequentially consistent. We have implemented Relaxer for C and have evaluated it on several synchronization algorithms, concurrent data structures, and parallel applications. Relaxer generates many executions of these benchmarks with violations of sequential consistency, highlighting a number of bugs under relaxed memory models.Keywords
Funding Information
- Microsoft (24263)
- Division of Computer and Network Systems (CNS-0720906CCF-1018729CCF-1018730)
- University of California (DIG07-10227)
- Division of Computing and Communication Foundations (CNS-0720906CCF-1018729CCF-1018730)
- Intel Corporation (24894)
This publication has 22 references indexed in Scilit:
- x86-TSOCommunications of the ACM, 2010
- Generating Litmus Tests for Contrasting Memory Consistency Models2010
- Effective Program Verification for Relaxed Memory Models2008
- Race directed random testing of concurrent programs2008
- Memory model sensitive bytecode verificationFormal Methods in System Design, 2007
- Iterative context bounding for systematic testing of multithreaded programs2007
- QB or Not QB: An Efficient Execution Verification Tool for Memory Orderings2004
- Testing Concurrent Java Programs using Randomized SchedulingElectronic Notes in Theoretical Computer Science, 2002
- An executable specification, analyzer and verifier for RMO (relaxed memory order)1995
- A new solution of Dijkstra's concurrent programming problemCommunications of the ACM, 1974