Mutual Exclusion

N-Thread Bakery (Tickets)

Bakery (Lamport; Hehner-Shyamasundar variant) is the classic N-thread software mutex: each thread picks a ticket > all currently-held tickets and waits its turn. FCFS, all 5 rules of the mutex game satisfied.

Why tickets?

Because with N threads there’s no simple bounded-boolean scheme that gives FCFS and rules 1–5 simultaneously. A ticket (monotonic counter per thread) turns “who goes next?” into “who has the smallest ticket?” — a pure order question. Position breaks ties deterministically.

Shape

_Task Bakery {                          // Lamport; Hehner-Shyamasundar variant
    int * ticket, N, priority;          // priority == this task's index
    void main() {
        for ( int i = 0; i < 1000; i += 1 ) {
            // step 1 — select a ticket one larger than any seen
            ticket[priority] = 0;        // signal "selecting" (highest priority)
            int max = 0;
            for ( int j = 0; j < N; j += 1 ) {
                int v = ticket[j];       // copy (may change)
                if ( v != INT_MAX && max < v ) max = v;
            }
            max += 1;
            ticket[priority] = max;
 
            // step 2 — wait until my ticket is the smallest
            for ( int j = 0; j < N; j += 1 ) {
                while ( ticket[j] < max ||
                        ( ticket[j] == max && j < priority ) ) {}
            }
            CriticalSection();
            ticket[priority] = INT_MAX;  // exit protocol — "no ticket"
        }
    }
};

Ticket value meanings

• INT_MAX ⇒ don’t want in.
• 0 ⇒ currently selecting a ticket (treated as highest priority, so no one overtakes me mid-selection).
• Otherwise ⇒ the ticket value.
• Ties broken by thread position (priority index).

Properties

• FCFS — no starvation.
• Uses N * M bits where M is the ticket size (e.g., 32 bits).
• Lamport’s variant is RW-safe; Hehner-Shyamasundar is RW-unsafe because the ticket[priority] = max write can flicker to INT_MAX, letting other tasks proceed.
• Ticket values cannot increase indefinitely — probabilistically correct in practice, reset to INT_MAX when no task is contending.

Related

• Mutual Exclusion Game
• Tournament Algorithm
• Fetch-and-Increment (hardware-assisted ticket lock)
• Dekker’s Algorithm