Learning from Mistakes --- A Comprehensive Study on Real World Concurrency Bug Characteristics. In the proceedings of the 13th International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS'08), March 2008

The reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is dif#2;cult. Addressing this challenge requires advances in multiple directions, including concurrency bug detection, concurrent program testing, concurrent programming model design, etc. Designing effective techniques in all these directions will signi#2;cantly bene#2;t from a deep understanding of real world concurrency bug characteristics. This paper provides the #2;rst (to the best of our knowledge) comprehensive real world concurrency bug characteristic study. Specifically, we have carefully examined concurrency bug patterns, manifestation, and #2;x strategies of 105 randomly selected real world concurrency bugs from 4 representative server and client opensource applications (MySQL, Apache, Mozilla and OpenOf#2;ce). Our study reveals several interesting #2;ndings and provides useful guidance for concurrency bug detection, testing, and concurrent programming language design. Some of our #2;ndings are as follows: (1) Around one third of the examined non-deadlock concurrency bugs are caused by violation to programmers' order intentions, which may not be easily expressed via synchronization primitives like locks and transactional 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 indicates that testing concurrent programs can target at exploring possible 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 #2;xed by simply adding or changing locks, and many of the #2;xes were not correct at the #2;rst try, indicating the dif#2;culty of reasoning concurrent execution by programmers.