Imperial College London
Portrait Picture

ProfessorAlastairDonaldson

Faculty of Engineering, Department of Computing

Professor of Programming Languages
 
 
 
//

Contact

 

+44 (0)20 7594 8266alastair.donaldson Website

 
 
//

Location

 

422Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Thomson:2016:10.1145/2858651,
author = {Thomson, P and Donaldson, AF and Betts, A},
doi = {10.1145/2858651},
journal = {ACM Transactions on Parallel Computing},
title = {Concurrency testing using controlled schedulers: an empirical study},
url = {http://dx.doi.org/10.1145/2858651},
volume = {2},
year = {2016}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - We present an independent empirical study on concurrency testing using controlled schedulers. We have gathered 49 buggy concurrent software benchmarks, drawn from public code bases, which we call SCTBench. We applied a modified version of an existing concurrency testing tool to SCTBench, testing five controlled scheduling techniques: depth-first search, preemption bounding, delay bounding, a controlled random scheduler, and probabilistic concurrency testing (PCT). We attempt to answer several research questions: Which technique performs the best, in terms of bug finding ability? How effective are the two main schedule bounding techniques—preemption bounding and delay bounding—at finding bugs? What challenges are associated with applying concurrency testing techniques to existing code? Can we classify certain benchmarks as trivial or nontrivial? Overall, we found that PCT (with parameter d = 3) was the most effective technique in terms of bug finding; it found all bugs found by the other techniques, plus an additional three, and it missed only one bug. Surprisingly, we found that the naive controlled random scheduler, which randomly chooses one thread to execute at each scheduling point, performs well, finding more bugs than preemption bounding and just two fewer bugs than delay bounding. Our findings confirm that delay bounding is superior to preemption bounding and that schedule bounding is superior to an unbounded depth-first search. The majority of bugs in SCTBench can be exposed using a small schedule bound (1--2), supporting previous claims, although one benchmark requires five preemptions. We found that the need to remove nondeterminism and control all synchronization (as is required for systematic concurrency testing) can be nontrivial. There were eight distinct programs that could not easily be included in out study, such as those that perform network and interprocess communication. We report various properties about the benchmarks tested, such a
AU  - Thomson,P
AU  - Donaldson,AF
AU  - Betts,A
DO  - 10.1145/2858651
PY  - 2016///
SN  - 2329-4949
TI  - Concurrency testing using controlled schedulers: an empirical study
T2  - ACM Transactions on Parallel Computing
UR  - http://dx.doi.org/10.1145/2858651
UR  - http://hdl.handle.net/10044/1/32224
VL  - 2
ER  -
Download