Bakery Algorithm for Mutual Exclusion

Introduction

The Bakery Algorithm extends mutual-exclusion reasoning from two processes to many processes. Peterson’s Algorithm works for two processes, but the Bakery Algorithm gives a conceptual solution for n competing processes.

Its central idea is similar to taking a ticket in a queue. A process chooses a ticket, waits behind earlier tickets, enters the critical section, and clears its ticket after leaving.

Core Idea

The Bakery Algorithm creates an order among processes that want to enter the critical section. The process with the smallest active ticket gets priority.

If two processes get the same ticket number, the smaller process ID wins. So priority is decided using the pair (ticket number, process ID).

This ticket-based order gives the algorithm its fairness intuition.

Shared Variables

The Bakery Algorithm uses two shared arrays: choosing[] and number[].

A new ticket is usually chosen as 1 + max(number[]), based on the ticket values visible to that process.

The choosing[] array prevents other processes from judging a process while it is still picking its ticket. The number[] array stores the chosen ticket values.

Priority Pair

The priority pair is written as (number[i], i). This pair decides which process should go first.

• Smaller ticket wins: (2, 4) has priority over (3, 1) because ticket 2 is smaller than ticket 3.

• Smaller ID breaks ties: (2, 1) has priority over (2, 3) because both tickets are equal, but process ID 1 is smaller.

• Zero means not waiting: If number[i] = 0, process i is not competing for the critical section.

This pair creates a clear ordering among active processes.

Algorithm Flow

For process i, the flow is:

• Start choosing: Set choosing[i] = true.

• Pick ticket: Set number[i] = 1 + max(number[]).

• Finish choosing: Set choosing[i] = false.

• Check every other process: For each process j, wait if j is still choosing.

• Compare priority: Wait if j has a nonzero ticket and (number[j], j) has higher priority.

• Enter critical section: Enter when no earlier active process exists.

• Clear ticket: Set number[i] = 0 after leaving.

Why Mutual Exclusion Holds

Mutual exclusion means two processes must not be inside the critical section at the same time.

In the Bakery Algorithm, every interested process has a nonzero ticket. All interested processes are compared using (number, process ID), so one active process has the smallest priority pair.

Only the process with the smallest pair can pass the waiting checks first. Any process with a larger pair must wait. Because ties are broken by process ID, two processes cannot both be first at the same time.

Progress and Bounded Waiting

Progress means that if processes are waiting and the critical section is free, entry should not be postponed forever. The process with the smallest active ticket can move forward.

Bounded waiting means a process should not be skipped endlessly. Once a process has a ticket, newer or larger tickets must wait behind it according to the ordering rule.

Assumptions and Limitations

The Bakery Algorithm is mainly studied as a teaching-model software solution. Its reasoning depends on predictable shared-variable behavior.

Important assumptions include:

• Distinct process IDs: IDs must be unique so ties can be broken.

• Consistent comparison rule: All processes compare (ticket, ID) pairs the same way.

• Shared reads and writes: The model assumes shared-variable operations behave as expected.

• Memory ordering: The reasoning assumes memory operations appear in the needed order.

• Busy waiting: Processes may spin while waiting for their turn.

In modern systems, production synchronization usually uses hardware atomics, mutexes, semaphores, monitors, or runtime lock libraries instead of directly implementing the Bakery Algorithm.

Bakery vs Peterson Algorithm

The Bakery Algorithm is more general than Peterson’s Algorithm, but also more complex.

Summary

The Bakery Algorithm is a classic mutual exclusion algorithm for n processes. It uses choosing[] to protect ticket creation and number[] to store each process’s active ticket.

The process with the smallest (ticket, process ID) pair gets priority. This ordering supports mutual exclusion, progress, and bounded waiting in the teaching model, while modern systems usually rely on stronger synchronization primitives.