In the Peterson Algorithm for mutual exclusion an implicit assumption is that the operations with the shared global variables happen atomically.

To me, this is not a superficial assumption , cause it's another mutual exclusion issue . In which way we make the operations with the shared global variables happen atomically ?


1 Answer 1


The Peterson Algorithm uses only memory read and memory write operations, which are atomic in almost every computer ever built. (All the bits in a word are read or written on the same cycle, and the memory bus of the computer is built in such a way that only one of the processors has access on any specific cycle.)

That said, the atomicity of the write operations is not necessary. Leslie Lamport is quite clear about this in his commentary on his web page about his classic "Bakery Algorithm" for mutual exclusion (http://lamport.azurewebsites.net/pubs/pubs.html#bakery):

Several books have included emasculated versions of the algorithm in which reading and writing are atomic operations, and called those versions "the bakery algorithm". I find that deplorable. There's nothing wrong with publishing a simplified version, as long as it's called a simplified version.

What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion. Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location. So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion. Such an algorithm cannot really be said to solve the mutual exclusion problem. Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion. Brinch Hansen said exactly this in a 1972 paper. Many people apparently still believe it.

(emphasis added)

For more details about this aspect of the problem see Lamport's 1991 paper, "The Mutual Exclusion Problem Has Been Solved," http://lamport.azurewebsites.net/pubs/pubs.html#lamport-mutual-solved.

  • $\begingroup$ Where can i find a detailed explanations of memory read and memory write operations ? $\endgroup$
    – Qwerto
    Apr 30, 2018 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.