Bakery Algorithm

The most common mutual exclusion algorithms or techniques use Mutexes or Semaphores [ shared between processes ] to give exclusive access of a shared resource. However, these do not work in case of Crash Faults. If a process that is holding a lock crashes, the contending process halts [ for how long? it is not-deterministic ]

The Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem for the general case of N process. Like all shared-memory synchronization algorithms, the bakery algorithm requires that one process be able to read a word of memory while another process is writing it.  (Each memory location is written by only one process, so concurrent writing never occurs.)  Unlike any previous algorithm, and almost all subsequent algorithms, the bakery algorithm works regardless of what value is obtained by a read that overlaps a write.

Link – Leslie Lamport

The Bakery Algorithm solves two problems, the first being the Crash Fault issue discussed above. The second being that the memory model does NOT need to be Sequentially Consistent.

Peterson’s algorithm and Lamport’s bakery algorithm work correctly. They are considered “software solutions” because the only dependency they have on the hardware is that simple load and store instructions are atomic. However, they have drawbacks. These algorithms are rather complex and difficult to understand. Besides, they do wasteful “busy waiting.”

– Lecture Notes

Semaphore is a better generalization of the Mutual-Exclusion problem.

Safe, Regular and Atomic Registers

Safe Registers is a weak form of memory i.e. if a Read overlaps a Write [ to put it another way, if a read is concurrent with a write ], the Read CAN return ANY value in that the register or memory location can possibly hold i.e. if the Safe Register is 32 bits, it can return any value between all 0’s and all 1’s.

Regular Registers are a bit stronger form of memory i.e. if a Read overlaps a Write, the Read can return an older pre-existing value or the new value set by the Write. This needs some special implementation to achieve. So for instance, the original value in the Register is 5 and the Write will change it to 10, the Read can either return 5 or 10. So unlike the Safe Register, we have really narrowed the scope of error into something that actually is real. Regular Registers will return the previous state or the new state of memory and NOT an Invalid state like the Safe Registers.

Atomic Registers are the strongest form of memory i.e. a Read CANNOT overlap with a Write. Therefore Reads will ALWAYS give a valid state when they’re executed.

The Bakery Algorithm can work even with the weakest form of memory i.e. Safe Registers.

You can convert a Safe Register into a Regular Register by making the register hold ONLY 2 values i.e. true or false. In this case, since only 2 States are possible, you either Get the new state or the old.