Run-time analysis for atomicity

Writing and debugging concurrent (shared-variable) programs is notoriously difficult. This motivated the development of numerous static analysis and run-time analysis techniques designed to (help) ensure that concurrent programs satisfy common correctness requirements for concurrent programs, such as absence of race conditions and absence of deadlocks. This paper focuses on another common correctness requirement for concurrent programs, namely, atomicity, which requires that any set of concurrent invocations of designated procedures is equivalent to performing those invocations serially in some order. Run-time analysis algorithms for detecting violations of atomicity are presented. The algorithms vary in cost and precision.