Implementing the Bakery Algorithm

1. The Bakery Analogy: Taking a Number

The intuition behind the algorithm is wonderfully simple and comes from a common real-world scenario: a bakery or a bank where customers take a numbered token upon entry. The customer with the lowest number gets served next. In our case, "processes" are the customers, and "being served" means entering the critical section.

A process wanting to enter the critical section will:

1. Take a number: This number will be higher than anyone else's current number.
2. Wait its turn: It waits until its number is the lowest among all processes waiting to enter.

Let's watch a video that introduces this concept and walks through a simplified version of the algorithm.

This simplified version seems to work, but it relies on a critical assumption: that the process of picking a number (max(...) + 1) is atomic. In a concurrent system, this is not a safe assumption. What if two processes read the maximum value at the same time, before either has a chance to update it?

2. Refining the Algorithm: Handling Concurrent Access

The real challenge, and the genius of the algorithm, lies in handling the race conditions that occur when the process of choosing a number is not atomic. Let's break down the problems and their solutions.

Problem 1: Two Processes Get the Same Number

If two processes, say Pi and Pj, read the same max value concurrently, they will both calculate the exact same token number. If they then try to enter the critical section, which one goes first? If both see that their number is the "lowest," they might both enter, violating mutual exclusion.

The Solution: A Tie-Breaker
The algorithm resolves this by using the process ID (e.g., i and j) as a tie-breaker. If two processes have the same token number, the process with the lower process ID gets priority. This is a form of lexicographical comparison on the pair (number, process_id).

(a, b) < (c, d) is true if a < c, or if a == c and b < d.

So, (number[i], i) < (number[j], j) means process i has a smaller number, OR the numbers are the same and i has a smaller process ID.

Problem 2: Reading Stale Numbers

Even with the tie-breaker, there's a more subtle race condition. Imagine this sequence:

1. Pi starts choosing a number but is preempted after it has read all the current numbers but before it calculates its own new number.
2. Pj runs, quickly chooses its number (which is still low), and enters the critical section.
3. Pi resumes, calculates its number based on the stale values it read earlier, and also gets a low number.
4. Pi might then incorrectly decide it can also enter the critical section, violating mutual exclusion.

The Solution: The choosing Array
To prevent this, the algorithm introduces a shared boolean array, choosing.

• choosing[i] = true; indicates that process i is currently in the middle of picking its token number.
• Before any process Pj checks Pi's token number, it must first wait until choosing[i] is false. This ensures that Pj only compares its number against a stable, fully-chosen number from Pi.

Let's see how these refinements come together in the complete algorithm.

3. The Complete Bakery Algorithm

You've now seen all the pieces and why they exist. Let's put it all together by looking at the formal pseudocode.

The entry section can be summarized as:

1. choosing[i] = true; — Announce that I'm picking a number.
2. number[i] = max(...) + 1; — Pick the next available number.
3. choosing[i] = false; — I'm done picking.
4. Loop through all other processes j:
   a. while (choosing[j]); — Wait for Pj to finish picking its number.
   b. while ((number[j] != 0) && (number[j], j) < (number[i], i)); — Wait if Pj is interested (number[j] != 0) and has a better priority (lower number, or same number with a lower ID).

This structure guarantees all three properties: Mutual Exclusion, Progress, and Bounded Waiting.

4. Application: Analyzing a GATE Problem

GATE questions love to test your understanding of synchronization algorithms by presenting a slightly incorrect version and asking you to identify the consequences. Let's tackle a question from GATE 2016.

The critical difference is the condition t[j] <= t[i]. The correct algorithm uses a strict less-than comparison for the numbers and a process ID tie-breaker: (t[j], j) < (t[i], i). This modified version uses less-than-or-equal-to and has no tie-breaker.

What happens if two processes, Pi and Pj, happen to get the same token number, so t[i] == t[j]?

• Pi will execute while (t[j] != 0 && t[j] <= t[i]). This is true, so Pi waits.
• Pj will execute while (t[i] != 0 && t[i] <= t[j]). This is also true, so Pj waits.

Both processes are waiting for the other to finish, but neither can proceed. This is a classic deadlock.

Now, let's analyze the properties based on this flaw:

• Mutual Exclusion: This is still satisfied. For two processes Pi and Pj to be in the critical section simultaneously, Pi must have passed its check on Pj (meaning t[j] > t[i]) and Pj must have passed its check on Pi (meaning t[i] > t[j]). This is a contradiction. So, at most one process can enter. Option (A) is TRUE.
• Progress: Not satisfied. As we saw, if two processes get the same token number, they can deadlock. This means interested processes are unable to decide who enters next, violating the progress condition.
• Bounded Waiting: Not satisfied. A deadlock means a process waits forever, which is the definition of unbounded waiting.
• Cannot cause a deadlock: False. We just demonstrated a deadlock scenario.

This exercise demonstrates a vital skill for your exam: don't just memorize algorithms, understand the purpose of each line of code so you can predict the consequences of changing it.

Conclusion

In this lesson, we scaled up our approach to the critical section problem from two processes to n processes using the Bakery Algorithm. We saw how a simple analogy of taking a number is refined with a process ID tie-breaker and a choosing flag to handle the complexities of concurrent execution.

Key Takeaways:

• The Bakery Algorithm provides a solution to the critical section problem for n processes.
• It uses a shared number array for token values and a shared choosing array to prevent race conditions during token selection.
• Mutual exclusion is ensured by a lexicographical comparison of (number, process_id) pairs, which acts as a tie-breaker.
• The algorithm guarantees Mutual Exclusion, Progress, and Bounded Waiting.
• Like Peterson's solution, it is a software-only solution that relies on busy-waiting.

While theoretically sound, the busy-waiting nature of software solutions like Peterson's and Bakery makes them inefficient. In our next lesson, we will begin exploring more practical and efficient solutions that leverage special hardware instructions. We'll start by looking at atomic operations like Test-and-Set and how they form the basis for higher-level synchronization tools like mutex locks.