Peterson Solution | Critical-Section Problem

Peterson's Solution

Peterson's solution was developed to address the critical section problem, particularly when involving only two processes. This solution is designed to ensure mutual exclusion, bounded waiting, and the progress of these processes.

Let's assume two processes (Pi and Pj) in a concurrent system that utilizes the Peterson's solution for mutual exclusion. I'll begin by presenting the algorithm it employs using these two processes, followed by a practical code example in Python.

Algorithm for Pi Process

do {
  flag[i] = true;
  turn = j;
  while (flag[j] && turn == j);  // Control remains in this while loop until it exits
  // Critical section
 
  flag[i] = false;
 
  // Remainder section
} while (true);

Algorithm for Pj Process

do {
  flag[j] = true;
  turn = i;
  while (flag[i] && turn == i);
  // Critical section
 
  flag[j] = false;
 
  // Remainder section
} while (true);

Note:

• turn (int): The turn variable signifies whose opportunity it is to access the critical section. When turn equals i, it grants access to process Pi to enter its critical section.

• flag (boolean): The flag array serves as an indicator of a process's readiness to enter the critical section. If flag[i] is set to true, it signifies that process Pi is prepared and ready.

• It's important to note that the turn variable is shared, maintaining the same value regardless of the last modification.

Upon first glance, this might appear confusing, doesn't it? However, it's actually quite straightforward. Let's delve into the details to gain a clear understanding of what's happening.

Simply keep in mind that this is indeed a Humble Algorithm. In essence, when one process seeks access to its critical section, instead of proceeding into the critical section itself, it gracefully passes the turn to another process.

When you closely examine the algorithm above, you'll see the following:

• Pi wants to enter the critical section, so it sets flag[i] to true.
• However, Pi yields its turn to process Pj by setting turn to j with turn == j.
• while (flag[j] && turn == j); // The semicolon here keeps control within the loop, preventing exit.
• As long as the above condition remains true, access to the critical section is deferred. Only when this condition becomes false does Pi exit the loop and gain entry to the critical section.

Now, let's proceed to simulate the Peterson's solution in Python.

import threading
 
class PetersonAlgorithm:
    def __init__(self):
        self.flag = [False, False]
        self.turn = 0
 
    def lock(self, process):
        # Set flag for the current process to indicate it wants to enter the critical section
        self.flag[process] = True
        # Set the turn to the other process
        self.turn = 1 - process
 
        # Wait until it's the current process's turn and the other process doesn't want to enter
        while self.flag[1 - process] and self.turn == 1 - process:
            pass
 
    def unlock(self, process):
        # Release the lock by setting the flag of the current process to False
        self.flag[process] = False
 
 
# Example usage
 
# Create a shared counter
counter = 0
 
# Create a PetersonAlgorithm object
peterson = PetersonAlgorithm()
 
# Create two threads that will access the shared counter
def increment():
    global counter
    for _ in range(100000):
        # Lock the critical section
        peterson.lock(0)
        # Critical section
        counter += 1
        # Unlock the critical section
        peterson.unlock(0)
 
def decrement():
    global counter
    for _ in range(100000):
        # Lock the critical section
        peterson.lock(1)
        # Critical section
        counter -= 1
        # Unlock the critical section
        peterson.unlock(1)
 
# Create the threads
thread1 = threading.Thread(target=increment)
thread2 = threading.Thread(target=decrement)
 
# Start the threads
thread1.start()
thread2.start()
 
# Wait for the threads to finish
thread1.join()
thread2.join()
 
# Print the final value of the counter
print("Counter:", counter)

I trust that this explanation has clarified the concept for you. Happy Learning 🙌