Runtime analysis of atomicity for multithreaded programs

Atomicity is a correctness condition for concurrent systems. Informally, atomicity is the property that every concurrent execution of a set of transactions is equivalent to some serial execution of the same transactions. In multithreaded programs, executions of procedures (or methods) can be regarded as transactions. Correctness in the presence of concurrency typically requires atomicity of these transactions. Tools that automatically detect atomicity violations can uncover subtle errors that are hard to find with traditional debugging and testing techniques. This paper describes two algorithms for runtime detection of atomicity violations and compares their cost and effectiveness. The reduction-based algorithm checks atomicity based on commutativity properties of events in a trace; the block-based algorithm efficiently represents the relevant information about a trace as a set of blocks (i.e., pairs of events plus associated synchronizations) and checks atomicity by comparing each block with other blocks. To improve the efficiency and accuracy of both algorithms, we incorporate a multilockset algorithm for checking data races, dynamic escape analysis, and happen-before analysis. Experiments show that both algorithms are effective in finding atomicity violations. The block-based algorithm is more accurate but more expensive than the reduction-based algorithm.

1 Introduction

Mltithreading has become a common programming technique. Not only operating systems but also many applications are multithreaded. However, developing multithreaded programs is difficult. Concurrency introduces the possibility of errors that do not exist in sequential programs. Furthermore, multithreaded programs may behave differently from one run to another because threads are scheduled indeterminately. For most systems, the number of possible schedules is enormous and testing the system's behavior for each possible schedule is infeasible. Specialized techniques are needed to ensure that multithreaded programs do not have concurrency-related errors.