A Decision Procedure for Detecting Atomicity Violations for Communicating Processes with Locks
File(s)
Date
2009Author
Kidd, Nicholas
Lammich, Peter
Touili, Tayssir
Reps, Thomas
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
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
(a la synchronized methods in Java). The technique detects violations
expressed as indexed phase automata (PAs)|a class of non-deterministic nite 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.
Permanent Link
http://digital.library.wisc.edu/1793/60662Citation
TR1649