Peterson's Algorithm: A Solution for Mutual Exclusion
Peterson's algorithm is a classic solution to the critical section problem in concurrent programming. It is a simple and elegant algorithm that ensures mutual exclusion, meaning that only one process can access a shared resource at a time.
The Critical Section Problem
The critical section problem arises when multiple processes need to access shared resources. Without proper synchronization, these processes might interfere with each other, leading to incorrect results. The goal is to design a protocol that guarantees:
- Mutual exclusion: Only one process can be in the critical section at any given time.
- Progress: If no process is in the critical section and some processes want to enter, only those processes that are not in their non-critical sections can participate in the decision of which process will enter the critical section next.
- Bounded waiting: There is a limit on the number of times other processes can enter the critical section before a given process is allowed to enter.
Peterson's Algorithm
Peterson's algorithm uses two shared variables:
flag[i]: This boolean array, whereirepresents the process ID, indicates whether processiwants to enter the critical section.turn: This variable indicates which process has the priority to enter the critical section.
Here's a Python implementation of Peterson's algorithm:
import threading
class PetersonLock:
def __init__(self):
self.flag = [False, False]
self.turn = 0
def lock(self, process_id):
self.flag[process_id] = True
self.turn = 1 - process_id
while self.flag[1 - process_id] and self.turn == 1 - process_id:
pass
def unlock(self, process_id):
self.flag[process_id] = False
def critical_section(lock, process_id):
lock.lock(process_id)
# Access shared resource
print(f"Process {process_id} in critical section.")
lock.unlock(process_id)
if __name__ == '__main__':
lock = PetersonLock()
thread1 = threading.Thread(target=critical_section, args=(lock, 0))
thread2 = threading.Thread(target=critical_section, args=(lock, 1))
thread1.start()
thread2.start()
How it Works
- Initialization: Both
flagvalues are set toFalse, andturnis set to 0. - Entry Protocol:
- A process sets its
flagtoTrueto indicate its intention to enter the critical section. - It sets
turnto the other process's ID to give the other process priority. - The process then enters a busy waiting loop, checking if the other process also wants to enter and has priority.
- A process sets its
- Critical Section: Once the condition in the loop is false, the process has successfully entered the critical section.
- Exit Protocol: After exiting the critical section, the process sets its
flagtoFalseto signal that it's no longer in the critical section.
Advantages and Disadvantages
Advantages:
- Simple and efficient: Peterson's algorithm is easy to understand and implement.
- Fairness: The
turnvariable ensures that if both processes want to enter the critical section simultaneously, they take turns.
Disadvantages:
- Busy waiting: The process uses a busy wait loop, which can waste CPU cycles.
- Limited to two processes: The algorithm is designed for only two processes.
Conclusion
Peterson's algorithm is a valuable tool for understanding and implementing synchronization in concurrent programming. While it has limitations, it provides a simple and elegant solution for ensuring mutual exclusion for two processes.
