Peterson's Solution for Critical Sections

1. The Components of Peterson's Solution

Peterson's solution cleverly combines two ideas we've seen before: a "turn" variable to grant priority and a "flag" array to indicate interest. It operates on two shared data items:

• int turn;: An integer variable that indicates which process has the turn to enter the critical section. If turn == i, it is process Pi's turn.
• boolean flag[2];: A boolean array where flag[i] = true signifies that process Pi is ready to enter its critical section.

Let's look at the structure of the algorithm for a process Pi (the other process, Pj, would have j = 1 - i).

The logic in the entry section can be described as follows:

1. flag[i] = true;: The process Pi declares its interest in entering the critical section.
2. turn = j;: The process then graciously gives the turn to the other process, Pj. This is a key step. Pi is essentially saying, "I want to enter, but if you want to enter too, you can go first."
3. while (flag[j] && turn == j);: Pi now waits, but only if two conditions are met: the other process (Pj) is also interested (flag[j] == true), AND it is Pj's turn (turn == j). Pi can only enter its critical section if Pj is not interested or if it is Pi's turn.

This flowchart provides a good visual summary of the algorithm's logic for a single process.

2. Verifying the Three Requirements

Now for the most critical part, especially for your GATE preparation: proving that this algorithm correctly solves the critical section problem. We must demonstrate that it satisfies Mutual Exclusion, Progress, and Bounded Waiting.

For this, we'll turn to a video that walks through the proofs in a step-by-step manner, which is excellent for building a rigorous understanding.

Let's summarize the key arguments:

• Mutual Exclusion: The turn variable is the tie-breaker. If both processes set their flag to true at roughly the same time, they will both also try to set the turn variable. Since turn is a single shared variable, only one write operation will "win". If Pi sets turn = j and then Pj sets turn = i, the final value of turn will be i.

  • When Pj checks its while condition (flag[i] && turn == i), it will find it true and will wait.
  • When Pi checks its while condition (flag[j] && turn == j), it will find turn == j is false (since turn is now i). Pi will therefore break the loop and enter the critical section. Mutual exclusion is preserved.

• Progress: If process Pj is not interested in the critical section, its flag[j] will be false. When Pi reaches its while loop, the condition flag[j] && turn == j will immediately be false, regardless of the value of turn. Thus, Pi can enter its critical section without delay. An uninterested process does not impede progress.

3. The Bounded Waiting Guarantee

Proving bounded waiting is often the most nuanced part of analyzing Peterson's solution, but it's where the algorithm's elegance truly shines. The key is to understand how a process that is waiting is guaranteed to eventually get its turn.

Here's the essence of the bounded waiting argument:

• A process Pi can only be stuck in its while loop if flag[j] is true and turn is j.
• If Pi is waiting, it means Pj is either in its critical section or is about to enter it.
• When Pj exits its critical section, it sets flag[j] to false. This would allow Pi to enter.
• What if Pj immediately tries to re-enter its critical section? To do so, Pj must execute flag[j] = true; and, crucially, turn = i;.
• By setting turn = i, Pj has now given the turn to Pi. If Pi is still waiting, its while condition (flag[j] && turn == j) will become false because turn is no longer j. Pi is now guaranteed to enter.
• Therefore, a process Pi needs to wait for at most one entry by process Pj before it can enter its own critical section. This satisfies the bounded waiting condition.

4. Application to GATE Problems

Your goal is to apply this knowledge in the exam. GATE questions on Peterson's solution often test your understanding of the entry condition or the properties it guarantees.

First, a quick question to check your understanding of its properties.

The question highlights an important property: Peterson's solution is a busy-waiting solution. The process continuously checks the while loop condition, consuming CPU cycles without doing productive work. This is a primary disadvantage.

Now, let's see a direct application of the algorithm itself in a previous year's GATE question.

As the video shows, the question is a straightforward test of whether you know the algorithm's structure. The correct predicate P for the while loop is flag[j] && turn == j, which ensures mutual exclusion by making a process wait if the other process is interested and it's the other process's turn.

Conclusion

In this lesson, we dissected Peterson's solution, our first functional software-based approach to the critical section problem. We not only learned its structure but also rigorously proved that it meets the three essential criteria for a valid synchronization mechanism.

Key Takeaways:

• Peterson's solution solves the critical section problem for two processes.
• It uses a shared boolean flag array to indicate interest and a shared integer turn variable to resolve conflicts and ensure fairness.
• It guarantees Mutual Exclusion, Progress, and Bounded Waiting.
• Its main drawback is that it relies on busy-waiting, which is inefficient as it consumes CPU cycles while a process is waiting.

While Peterson's solution is a powerful theoretical tool, its limitation to only two processes is a significant practical constraint. In our next lesson, we will address this by studying the Bakery algorithm, which extends the principles of an orderly waiting system to handle the critical section problem for n processes.