Synchronization using counting semaphores
Vivek Sarkar · 1988
This paper studies the optimization problem of enforcing a dependence graph with the minimum number of synchronization operations. For a dependence graph with N vertices, it is shown that binary semaphores may require Ο(N2) operations, compared to Ο(N) operations for counting semaphores. Though the optimization problem of using the minimum number of counting semaphore operations is shown to be NP-complete, we present an approximation algorithm that is observed to be very close to optimal (within 0.5%) on small, randomly generated dependence graphs. A surprising property of the problem is that the inclusion (rather than removal) of transitive edges can actually help reduce the number of synchronization operations.