Bakery Algorithm

operating-systems concurrency

Definition

Bakery Algorithm

The Bakery algorithm is a synchronisation algorithm developed by Leslie Lamport to solve the mutual exclusion problem for $n$ processes. It is based on the intuition of a bakery where customers take a numbered ticket upon entering and are served in increasing order of their numbers.

Mechanism

The algorithm uses two global arrays:

• choosing[0..n-1]: A boolean array where choosing[i] is true if process $i$ is currently taking a number.
• number[0..n-1]: An integer array storing the ticket number for each process.

Logical Steps

1. Ticket Acquisition: A process sets its choosing flag to true, finds the maximum current ticket number, and assigns itself max + 1.
2. Waiting: The process then iterates through all other processes $j$ and waits until:
   • Process $j$ is not currently choosing a number.
   • Process $j$ either has no ticket (number[j] == 0) or has a ticket with a higher priority than process $i$.
3. Tie-breaking: If two processes receive the same ticket number, the process with the lower ID ($i<j$) is given priority.

// Process Pi
loop
    choosing[i] := true;
    number[i] := 1 + max(number[0], ..., number[n-1]);
    choosing[i] := false;
    
    for j := 0 to n-1 do
    begin
        while choosing[j] do nothing; // Wait if process j is taking a ticket
        while number[j] ≠ 0 and (number[j], j) < (number[i], i) do nothing;
    end;
    
    // --- Critical Section ---
    
    number[i] := 0; // Release ticket
    
    // --- Remainder Section ---
end loop;

Properties

• Mutual Exclusion: Guaranteed through the ticket comparison.
• Progress: Guaranteed because the process with the smallest $(number,ID)$ pair can always proceed.
• Bounded Waiting: Guaranteed because new processes will always receive a higher ticket number than those already in line.