Bakery Algorithm

operating-systems concurrency

Definition

Bakery Algorithm

The Bakery algorithm, developed by Leslie Lamport, solves the mutual exclusion problem for $n$ processes. Each process takes a numbered ticket upon entering; the process with the smallest ticket enters the critical section first.

Algorithm

The algorithm maintains two shared arrays:

Array	Type	Meaning
choosing[0..n-1]	boolean	choosing[i] is true while process $i$ reads the maximum ticket number
number[0..n-1]	integer	number[i] is the ticket held by process $i$ (0 means no ticket)

Void process(int i)
    while (true) {
        choosing[i] = true;
        number[i] = 1 + max(number[0], ..., number[n-1]);
        choosing[i] = false;
        
        for (int j = 0; j < n; j++) {
            while (choosing[j]) { /* wait */ }

            while (number[j] != 0 &&
                   (number[j], j) < (number[i], i)) {
                /* wait */
            }
        }
        
        /* --- Critical Section --- */
        
        number[i] = 0;
        
        /* --- Remainder Section --- */
    }

Lexicographic Ordering

Tickets are compared as pairs $(number,process\_id)$. If two processes obtain the same ticket number, the process with the smaller ID precedes the other. This ensures a total order among waiting processes.

Correctness

Mutual Exclusion

No two processes execute the critical section simultaneously.

Proof

Suppose processes $i$ and $j$ (with $i<j$) both enter the critical section. Both must have passed the inner while loop for each other. For $i$ to pass $j$‘s test, either number[j] == 0 or $(number[j],j)>(number[i],i)$. For $j$ to pass $i$‘s test, either number[i] == 0 or $(number[i],i)>(number[j],j)$. Since both hold non-zero tickets in the critical section, we have both $(number[j],j)>(number[i],i)$ and $(number[i],i)>(number[j],j)$, a contradiction.

Progress

If some process wishes to enter the critical section and no process is currently in it, some process will enter within finite time.

Proof

Among processes waiting with non-zero tickets, let $k$ be the process with the smallest $(number,id)$ pair. For any other waiting process $m$, we have $(number[m],m)>(number[k],k)$. Thus $k$ will not block on any process. Process $k$ proceeds to the critical section.

Bounded Waiting

A process waiting to enter the critical section will enter within $n-1$ turns.

Proof

When process $i$ takes its ticket, any process $j$ that later takes a ticket receives $number[j]>number[i]$ (or equal with $j>i$, giving $i$ priority). Process $i$ waits only for processes already holding tickets. At most $n-1$ such processes exist, and each enters the critical section exactly once before $i$.