Tech Report CS-93-29

Detecting Race Conditions in Parallel Programs That Use One Semaphore

Hsueh-I Lu, Philip N. Klein, and Robert H.B. Netzer

Revised January 1996


We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that use many semaphores. For the case of a single semaphore, we give an algorithm that takes $O(n^{1.5} p)$ time, where $p$ is the number of processors and $n$ is the total number of semaphore operations executed. Our algorithm constructs a representation from which one can determine in constant time whether a race exists between two given events.

(complete text in pdf or gzipped postscript)