The problem of multiprocessor mutual-exclusion was first proposed in 1962 by T. Dekker, but no correct solution for more than two processes was published until 1965, when Edsger Dijkstra wrote his one-page article [2] giving a working but complicated solution to the problem. His solution guaranteed mutual exclusion, freedom from deadlock, and freedom from livelock, but allowed the possiblity of one process being forever stuck in the entry section while other processes are allowed into the critical section. This paper was quickly followed by Donald Knuth's equally complicated solution [4], which did guarantee freedom from starvation.
Both of the above algorithms had the fault that if a single processor were to halt ( i.e., crash) at any point in the entry section, the whole system might block indefinitely. Also, both solutions assumed atomic reads and writes to memory; that is, they assumed that all reads and writes to single memory locations will be non-overlapping, presumably arbitrated by hardware. This assumption is often not valid, and we must deal with the possiblity that a read may overlap a write, thus returning invalid or partial results, or that several writes may overlap, thus writing invalid or partial data.
Eight years after Knuth's article, Leslie Lamport published a solution [5] which is not only simpler that the first two, but which both allows any processor to halt anywhere in the entry section and allows a read to return any arbitrary value if it overlaps a write. Lamport's algorithm also had the new property that processes were served in a first-come first-served order, which Dijkstra's and Knuth's algorithms did not guarantee.
Knuth's algorithm was basically analoguous to a bakery, where customers take a number when they walk in the door and wait for their number to be called. In the algorithm, each process that wanted to enter the critical section would select a number that was one greater than the maximum number chosen by the other processes, and the process with the lowest number would be allowed in.
In 1981, seven years after Knuth's article, Gary Peterson published his now-famous algorithm [11] for two processes, and also gave an algorithm for more than two processes. The two-process algorithm was so simple that he felt that a proof of correctness was not necessary, and it is worth reproducing here:
/* Entry section for P1 */ /* Entry section for P2 */ Q1 := True; Q2 := True; TURN := 1; TURN := 2; wait while Q2 and TURN := 1; wait while Q1 and TURN := 2; /* Exit section for P1 */ /* Exit section for P2 */ Q1 := False; Q2 := False;
Both in this algorithm and in all of the previous ones, the processes busy-wait until they are allowed to enter the critical section. One might wonder why these algorithms busy-wait instead of simply context-switching to another ready process. At the beginning of this paper, we made the assumption that critical sections were usually very small; this would imply that any process busy-waiting on a lock would likely wait for a fairly short period of time. The overhead of context-switching is usually large enough that busy-waiting is more efficient. For critical sections that are longer, such as those with disk access, the above algorithms can be used as low-level building blocks for higher-level semaphores.