petersons algorithm - TarisMajor/5143-OpSystems GitHub Wiki

Peterson’s Algorithm

Peterson’s Algorithm is a classic mutual exclusion algorithm used in concurrent programming to ensure that two processes do not simultaneously enter a critical section, which could lead to race conditions. It was designed by Gary Peterson in 1981 for two processes. The algorithm is based on shared variables to allow mutual exclusion without requiring hardware support. It uses two variables (flag[] and turn) to ensure that only one process enters the critical section at a time.

Description:

flag[]: An array of boolean values used by each process to indicate its intention to enter the critical section. turn: A shared variable that helps decide which process should be allowed into the critical section when both processes are requesting access. Each process sets its flag to true to indicate its desire to enter the critical section and then checks if the other process has set its flag and whether it’s the other process' turn to enter the critical section. If both processes wish to enter, the turn variable ensures that one process waits for the other.

Key Points:

Ensures mutual exclusion: Only one process can enter the critical section at a time. Avoids deadlock: A process will always eventually enter the critical section. Starvation-free: Both processes get a chance to execute, preventing indefinite waiting.

Source: Peterson, G. (1981). "Peterson's Algorithm". ACM Transactions on Computer Systems.