In this paper, the authors describe a way of solving (i.e., implementing) mutual exclusion problems that can be represented as undirected graphs. As the authors point out, their approach to mutual exclusion problems is not an attempt to improve on published distributed solutions, which do not rely on shared variables for synchronization. Not all concurrent programming environments, however, support the remote procedure calls and message-passing protocols required to eliminate shared variables. The technique described is intended to lead to the correct and efficient solution of a range of mutual exclusion problems using binary semaphores.
Discussion centers on the range of mutual exclusion problems that can be solved using this graphical approach; due consideration is given to deadlock, starvation, and efficiency. All the solutions employ either weak or blocked- queue binary semaphores. The final example uses these primitives to simulate a monitor.
The presentation is clear, and the proofs are very informal. Hence, this paper is accessible to all students, academics, and professionals with an interest in concurrent programming.