Learning from mistakes

Top Cited Papers
Publisher Website
Google Scholar
Abstract
The reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is difcult. Addressing this challenge requires advances in multiple directions, including concurrency bug detection, concurrent pro- gram testing, concurrent programming model design, etc. Design- ing effective techniques in all these directions will signicantly benet from a deep understanding of real world concurrency bug characteristics. This paper provides the rst (to the best of our knowledge) com- prehensive real world concurrency bug characteristic study. Specif- ically, we have carefully examined concurrency bug patterns, man- ifestation, and x strategies of 105 randomly selected real world concurrency bugs from 4 representative server and client open- source applications (MySQL, Apache, Mozilla and OpenOfce). Our study reveals several interesting ndings and provides use- ful guidance for concurrency bug detection, testing, and concurrent programming language design. Some of our ndings are as follows: (1) Around one third of the examined non-deadlock concurrency bugs are caused by vio- lation to programmers' order intentions, which may not be easily expressed via synchronization primitives like locks and transac- tional memories; (2) Around 34% of the examined non-deadlock concurrency bugs involve multiple variables, which are not well addressed by existing bug detection tools; (3) About 92% of the examined concurrency bugs can be reliably triggered by enforcing certain orders among no more than 4 memory accesses. This indi- cates that testing concurrent programs can target at exploring possi- ble orders among every small groups of memory accesses, instead of among all memory accesses; (4) About 73% of the examined non-deadlock concurrency bugs were not x ed by simply adding or changing locks, and many of the x es were not correct at the rst try, indicating the difculty of reasoning concurrent execution by programmers.

This publication has 34 references indexed in Scilit: