This paper details the design of a scalable algorithm for the mutual exclusion problem. Starting by inserting a redundant assignment into Peterson's agoorithm for two processes, we derive another algorithm that uses only local spins, i.e., a process busy-waits only on locally accessible shared variables. The new two-process algorithm is then adapted to serve as a building block of the complete tournament-like algorithm; the adaptation si such that the entire algorithm still uses only local spins, which is crucial for scalability. We consider the simplicity of the algorithm and its derivation to be the main contributions of this paper.
展开▼
