Bakery Algorithm

1. Introduction to Bakery Algorithm

  • The Bakery Algorithm is a software-based solution to the critical section problem for n processes, designed by Leslie Lamport.

  • It ensures that multiple processes can safely access a shared resource (critical section) without interference, similar to taking a number at a bakery.

2. Core Idea

  • Each process, before entering its critical section, receives a number (ticket).

  • The process with the smallest number gets to enter the critical section first.

  • If two processes get the same number, the process with the smaller process ID (PID) enters first.

3. Data Structures Used

  • n: The total number of processes.

  • choosing[n]: A boolean array where choosing[i] is true if process i is currently picking a number.

  • number[n]: An integer array where number[i] stores the number (ticket) chosen by process i. Initially, all number[i] are 00.

4. Algorithm Steps (for process i)
4.1. Entry Section (Choosing a Number)

  1. Process i indicates it's choosing a number:
    choosing[i] = true

  2. Process i selects a number by finding the maximum number currently held by any process and adding 11:
    number[i] = max(number[0], ..., number[n-1]) + 1

  3. Process i finishes choosing its number:
    choosing[i] = false

4.2. Entry Section (Waiting for Turn)

  1. Process i iterates through all other processes j (from 00 to n-1, excluding i).

  2. For each process j:

    • Wait if process j is still choosing a number:
      while (choosing[j] is true) { /* busy-wait */ }

    • Wait if process j has a valid number and its turn is before process i's turn:while (number[j] != 0 && (number[j], j) < (number[i], i)) { /* busy-wait */ } (The comparison (number[j], j) < (number[i], i) means:

      • If number[j] < number[i], then process j's turn is first.

      • If number[j] == number[i], then the process with the smaller process ID (j < i) has priority.)

4.3. Critical Section

  • Once all waiting conditions are met, process i enters its critical section.

4.4. Exit Section

  • After finishing the critical section, process i resets its number, indicating it no longer needs the critical section:
    number[i] = 0

5. Properties Ensured

  • Mutual Exclusion: Only one process can be in the critical section at any given time.

  • Progress: If no process is in its critical section and some processes want to enter, then only those processes whose numbers are valid can participate in the decision of which process will enter its critical section next.

  • Bounded Waiting: A bound exists on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before the request is granted.

6. Disadvantages

  • Busy Waiting: Processes consume CPU cycles while actively waiting in a loop for their turn, which can be inefficient.

  • Implementation Complexity: The algorithm, especially the lexicographical comparison, can be tricky to implement correctly.

  • Memory Consistency Issues: Might not work correctly on systems with weak memory models where memory operations are not guaranteed to be ordered as expected without specific hardware instructions (memory barriers).