Computer Science – Data Structures and Algorithms
Scientific paper
2002-08-03
Algorithmica, 35(4):321-345, 2003
Computer Science
Data Structures and Algorithms
24 pages, 12 figures, preliminary versions appeared in WADS 93 and ESA 96
Scientific paper
10.1007/s00453-002-1004-3
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.
Klein Philip N.
Lu Hsueh-I
Netzer Rob H. B.
No associations
LandOfFree
Detecting Race Conditions in Parallel Programs that Use Semaphores does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Detecting Race Conditions in Parallel Programs that Use Semaphores, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting Race Conditions in Parallel Programs that Use Semaphores will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-725394