Algorithms to implement semaphores in distributed environment

Synchronization of concurrent processes has been an important issue in operating system design. Processes need to synchronize with one another or co-ordinate access to shared resources to maintain the correctness of the system. Semaphores provide a simple, yet powerful mechanism for synchronization among concurrent processes.;Implementation and properties of semaphores, while well understood in shared memory systems, have not received sufficient attention in distributed systems. The lack of shared memory makes implementation of semaphores difficult in a distributed system. Several algorithms based on message passing exist which provide mutually exclusive access to a critical section in a distributed system. These algorithms indirectly implement a binary semaphore. There is still a need for a general purpose synchronization mechanism in distributed systems. Providing such mechanisms through the use of a centralized controller is undesirable for several reasons.;Lately, there has been wide-spread interest in implementing the shared memory programming paradigm on distributed systems. Such systems, called Distributed Shared Memory (DSM), are the implementation of the shared memory programming paradigm on a distributed memory (or multicomputer) system. The DSM programming model is appealing because it combines the performance advantage of distributed memory systems and the ease of programming of shared memory systems.;In this dissertation, a taxonomy of the synchronization mechanisms for several Distributed Shared Memory systems is presented. The representative systems are classified according to whether they are hardware or software based, whether the mechanism is integrated into the system or not and whether implementation of the synchronization mechanism is centralized or distributed. The dissertation then presents three decentralized algorithms to implement semaphores in a distributed system.;In the first decentralized scheme to support semaphores in a distributed system, the semaphores (and associated information structures) are grouped into pages called semaphore-pages. These pages are replicated in the system. Algorithms to cache the semaphores as well as to update the information structures of the pages are presented. The second approach implements a semaphore as a token in the system and provides algorithms to acquire the token to perform operations on it. This approach splits a distributed system into a hierarchy of processors, and replicates the semaphore among the processor clusters to exploit the locality of reference and thus increases the efficiency of access. The third approach is a consensus-based approach where a semaphore is replicated over the nodes in the system. A node wishing to perform an operation on a semaphore must request and acquire a consensus from the other nodes in the system. Splitting the processors into clusters as in the previous approach introduces interesting challenges. Algorithms are presented for both the unclustered and clustered consensus-based approaches. All three algorithms are proven to be free of deadlock and starvation.;Extensive performance studies of these algorithms based on simulation is presented. Comparisons of these approaches with each other, as well as with centralized and other distributed techniques are discussed.