ABSTRACT
Mutual exclusion is a fundamental problem in concurrent programming and has been extensively studied under different contexts. Imagine that N users (N> 1) want to print data on a shared printer infinitely often. Since at most one user can print at any time, there should be a protocol for the serialization of the printer access, and for the fair sharing of that printer. As another example, consider a network of processes, where each process has a copy of a shared file F. To be consistent, all copies of F must be identical, regardless of how individual processes perform their read or write operations. Simultaneous updates of the local copies will violate the consistency of F. A simple way to achieve this is to give each process exclusive write access to its local copy of F during write operations, and propagate all updates to the various local copies of F with the other processes, before any other process starts accessing its local copy. This shows the importance of studying the mutual exclusion problem. The problem can be generalized to the exclusive access of any shared resource on a network of processes. In multiprocessor cache coherence, at most one process has the right to update a shared variable. A well-known implementation of mutual exclusion is found in the CSMA/CD protocol used to resolve bus contention in ethernets.
