UCSC-CRL-93-29: A CLASS OF SYNCHRONIZATION OPERATIONS THAT PERMIT EFFICIENT RACE DETECTION

08/01/1993 09:00 AM
Computer Science
We present an efficient algorithm for ``precisely\'\' determining the possible alternate orderings of events from a program trace for a class of synchronization operations. The class includes, post and wait without clear, a restricted form of semaphores, and message passing where the sender names the receiver. The ordering information is precise in that a race detection system could be built using the ordering information such that if the program does not contain any data races for a given input, no races will be reported, and if the the program does contain data races, at least one of those races will be reported.

UCSC-CRL-93-29