Lamports bakery algorithm - TarisMajor/5143-OpSystems GitHub Wiki

Lamport’s Bakery Algorithm

Lamport’s Bakery Algorithm is a mutual exclusion algorithm designed by Leslie Lamport in 1974. It is based on the idea of a "ticket" system, similar to how customers take tickets at a bakery to wait for service. The algorithm is designed to solve the problem of mutual exclusion in a system where many processes are trying to access a shared resource.

Description:

Each process, before entering the critical section, picks a number from a shared queue, which acts like a ticket. The number is chosen such that each process takes the next number in line. The processes are then allowed to enter the critical section in order of their ticket numbers, ensuring fairness and avoiding starvation. The algorithm is highly fair and ensures that no process is skipped or left out, preventing race conditions in a distributed or multi-threaded system.

Key Points:

Fairness: The process with the smallest ticket number enters the critical section first. Avoids starvation: Every process eventually gets a chance to enter. Works in environments with multiple processes.

Source: Lamport, L. (1974). "The Bakery Algorithm". ACM Transactions on Programming Languages and Systems.