Synchronization using counting semaphores

Abstract

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 O(N2) operations, compared to O(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. We characterize a class of dependence graphs for which the approximation algorithm is optimal. This class includes forests of fan-in trees, fan-out trees and series-parallel graphs. The number of synchronization operations needed for binary and counting semaphores are compared for randomly generated dependence graphs, using an implementation of the approximation algorithm in LISP/VM. The experimental results show that the use of counting semaphores significantly reduces the total number of synchronization operations, compared to binary semaphores.