A Decision Procedure for Detecting Atomicity Violations
for Communicating Processes with Locks
Nicholas Kidd, Peter Lammich, Tayssir Touili, and Thomas Reps
We present a new decision procedure for detecting property violations in
pushdown models for concurrent programs that use lock-based synchronization,
where each thread's lock operations are properly nested à la synchronized
methods in Java). The technique detects violations expressed as
indexed phase automata (PAs)—a class of non-deterministic
finite automata in which the only loops are self-loops.
Our interest in PAs stems from their ability to capture atomic-set
serializability violations. (Atomic-set serializability is a relaxation of
atomicity to only a user-specified set of memory locations.) We implemented
the decision procedure and applied it to detecting atomic-set-serializability
violations in models of concurrent Java programs. Compared with a prior method
based on a semi-decision procedure, not only was the decision procedure 7.5X
faster overall, but the semi-decision procedure timed out on about 68% of the
queries versus 4% for the decision procedure.
(Click here to access the paper:
PDF;
(c) Springer-Verlag.)