  We address the problem of detecting race conditions in programs that use
semaphores for synchronization. Netzer and Miller showed that it is NP-complete
to detect race conditions in programs that use many semaphores. We show in this
paper that it remains NP-complete even if only two semaphores are used in the
parallel programs.
  For the tractable case, i.e., using only one semaphore, we give two
algorithms for detecting race conditions from the trace of executing a parallel
program on p processors, where n semaphore operations are executed. The first
algorithm determines in O(n) time whether a race condition exists between any
two given operations. The second algorithm runs in O(np log n) time and outputs
a compact representation from which one can determine in O(1) time whether a
race condition exists between any two given operations. The second algorithm is
near-optimal in that the running time is only O(log n) times the time required
simply to write down the output.
