A Fast Mutual Exclusion Algorithm
A new solution to the mutual exclusion problem is presented that, in the absence of contention, requires only seven memory accesses. It assumes atomic reads and atomic writes to shared registers. Capsule Review To build a useful computing system from a collection of processors that communicate by sharing memory, but lack any atomic operation more complex than a memory read or write, it is necessary to implement mutual exclusion using only these operations. Solutions to this problem have been known for twenty years, but they are linear in the number of processors. Lamport presents a new algorithm which takes constant time (five writes and two reads) in the absence of contention, which is the normal case. To achieve this performance it sacrifices fairness, which is probably unimportant in practical applications. The paper gives an informal argument that the algorithm's performance in the absence of contention is optimal, and a fairly formal proof of safety and freedom from deadlock, u...