The Bakery-Algorithm
The Bakery-Algorithm is a classic Synchronization algorithm developed by Leslie-Lamport to solve the Mutual-Exclusion problem in Concurrent-Computing. It ensures that multiple Processes do not access a Critical-Section at the same time, even in the absence of hardware-level Atomic-Operations such as compare-and-swap.
How the Algorithm Works
The algorithm is inspired by the ticketing systems used in retail environments like bakeries. When a Thread wants to enter the Critical-Section, it must first take a ticket number. This number is assigned as one greater than the maximum of all currently existing ticket numbers. The thread then waits until its number is the smallest among all threads currently competing for access. If two threads receive the same number, the Process-ID is used as a tie-breaker, ensuring a First-In-First-Out property and preventing Starvation.
Context and Theoretical Significance
Leslie-Lamport first described this method in his 1974 paper titled