Peterson’s Solution to the Critical Section Problem

In computer science, process synchronization plays a key role in ensuring that multiple processes running in a system do not interfere with each other when accessing shared resources. This issue often arises in the Critical Section Problem, where two or more processes need exclusive access to a shared variable, file, or database.

One of the simplest and most famous software-based solutions for this problem is Peterson’s Solution. It is widely taught in Operating System courses because it explains the concepts of mutual exclusion, progress, and bounded waiting in a clear and logical way.

Understanding the Critical Section Problem

When multiple processes are running simultaneously, there may be certain code segments called critical sections, where a process reads or writes shared resources.

The main goals of solving the Critical Section Problem are:

1. Mutual Exclusion – Only one process should be inside the critical section at any time.
2. Progress – If no process is in the critical section, one of the waiting processes should be allowed to enter without unnecessary delay.
3. Bounded Waiting – Each process gets a fair chance, so no process waits forever to enter.

Peterson’s Solution

Peterson’s Solution is a software-based algorithm designed for two processes (P0 and P1) to share a single-use resource without conflicts.

It uses two shared variables:

1. flag[2] – An array where flag[i] is true if process Pi wants to enter the critical section.
2. turn – Indicates whose turn it is to enter the critical section.

Key Idea:

• Each process sets its flag to true when it wants to enter.
• It then gives priority to the other process by setting the turn variable.
• The process waits until either the other process is not interested or it is its own turn.

Real-world Example to understand Peterson’s solution

Imagine you and your roommate share one bathroom in your apartment.
You both sometimes need it at the same time. If you rush in without coordination, you might clash at the door (the race condition).

Peterson’s solution is like you both following a polite rule system:

1. Turn variable → You both agree that whoever’s turn it is will get priority to use the bathroom. If it’s your turn but you don’t need it, you pass it to your roommate.
2. Flag variables → Each of you has a sign on your bedroom door saying:
   • true → “I need the bathroom”
   • false → “I don’t need it right now”
3. The agreement:
   • Before heading to the bathroom, you put your flag to true and say “It’s your turn” to the other person.
   • Then you wait outside unless it’s your turn or the other person’s flag is false (meaning they don’t need it).
4. Once you’re done, you set your flag to false so the other person can go.

Why it works:

• Mutual exclusion → Only one person in the bathroom at a time.
• Progress → If one person isn’t using it, the other doesn’t wait unnecessarily.
• Bounded waiting → No one can hog the bathroom forever; the turn alternates.

Peterson’s Algorithm (Code)

Let’s write the algorithm for two processes: P0 and P1.

For Process P0

flag[0] = true;           // P0 wants to enter critical section
turn = 1;                 // Give turn to P1
while (flag[1] == true && turn == 1) {
    // Wait until P1 finishes or gives up
}

// Critical Section
// Code accessing shared resources goes here

flag[0] = false;          // P0 leaves the critical section

For Process P1

flag[1] = true;           // P1 wants to enter critical section
turn = 0;                 // Give turn to P0
while (flag[0] == true && turn == 0) {
    // Wait until P0 finishes or gives up
}

// Critical Section
// Code accessing shared resources goes here

flag[1] = false;          // P1 leaves the critical section

Step-by-Step Explanation

Let’s break it down for better understanding:

1. Expressing the intention
   • When process Pi wants to enter, it sets flag[i] = true.
   • This is like raising a hand to say, “I want to use the resource.”
2. Giving the other process a chance
   • The process sets turn to the other process’s index.
   • Example: If P0 wants to enter, it sets turn = 1.
3. Waiting loop (while condition)
   • The process waits as long as the other process also wants to enter (flag[j] == true) and it is the other process’s turn.
   • This prevents both processes from entering at the same time.
4. Entering the Critical Section
   • Once the while condition is false, the process enters the critical section safely.
5. Leaving the Critical Section
   • The process sets its flag to false, indicating it no longer needs the resource.

Why Peterson’s Solution Works

Peterson’s Solution satisfies all three requirements of the Critical Section Problem:

• Mutual Exclusion: Both processes cannot enter the critical section at the same time.
• Progress: If only one process wants to enter, it will get access without delay.
• Bounded Waiting: No process waits indefinitely; the turn variable ensures fairness.

Advantages of Peterson’s Solution

• Simple to understand and implement for two processes.
• Requires no special hardware or machine instructions.
• Proves the concept of mutual exclusion clearly.

Limitations of Peterson’s Solution

• Works only for two processes.
• Relies on the assumption of sequential consistency of memory operations (not always guaranteed in modern multi-core processors without extra memory barriers).
• Not practical for real systems but excellent for teaching and conceptual understanding.

Conclusion

Peterson’s Solution is a classic method for solving the Critical Section Problem for two processes. While it’s not used in modern production systems due to hardware and architectural changes, it remains one of the best educational examples to understand process synchronization.

By using two simple shared variables (flag[] and turn), this algorithm ensures mutual exclusion, progress, and bounded waiting, the three golden rules of synchronization.