Peterson Algorithm for Mutual Exclusion

Introduction

Peterson Algorithm is a classic software solution for mutual exclusion between two processes. It uses shared variables instead of special hardware instructions.

It is usually studied after Dekker’s Algorithm because it solves the same two-process critical section problem with cleaner and more symmetric logic. The main focus is to understand why flag and turn work together.

Shared Variables

Peterson Algorithm uses two shared variables: flag and turn.

flag shows interest, but it cannot safely resolve a conflict by itself. turn resolves conflict, but it is useful only when both processes are interested.

Algorithm Flow for Process Pi

For process Pi, the algorithm follows a compact sequence.

• Show interest: Pi sets flag[i] = true.

• Give priority: Pi sets turn = j, giving Pj priority if both want to enter.

• Wait on conflict: Pi waits while flag[j] == true and turn == j.

• Enter critical section: Pi enters when the waiting condition becomes false.

• Release interest: Pi sets flag[i] = false after leaving.

• Remainder section: Pi continues with code outside the critical section.

The important point is that Pi waits only when both conditions are true: the other process wants to enter, and the other process currently has priority.

Compact Pseudocode

For process Pi, where the other process is Pj, the algorithm can be written as:

flag[i] = true
turn = j

while flag[j] == true and turn == j:
    wait

critical section

flag[i] = false

remainder section

This is a teaching algorithm for understanding mutual exclusion. It is not a modern replacement for mutexes, semaphores, monitors, or hardware-supported atomic operations.

Why Mutual Exclusion Holds

Mutual exclusion means both processes cannot be inside the critical section at the same time.

Suppose both Pi and Pj want to enter. Then both flags become true. At that point, turn can hold only one value.

• If turn = i: Pj waits because Pi has priority.

• If turn = j: Pi waits because Pj has priority.

Both processes cannot have priority at the same time. So both cannot pass the waiting condition together, which protects the critical section.

Progress and Bounded Waiting

Progress means the decision to enter the critical section should not be postponed forever when entry is possible. If only Pi wants to enter, then flag[j] is false, so Pi does not wait unnecessarily.

Bounded waiting means a waiting process should not be bypassed endlessly. When both processes want to enter, turn gives priority to one of them. After that process exits, it clears its flag, allowing the other process to enter.

Dekker vs Peterson Algorithm

Dekker’s Algorithm and Peterson Algorithm both solve the two-process mutual exclusion problem using flags and a turn variable. The difference is how they handle conflict.

Peterson Algorithm is easier to reason about because each process follows the same simple pattern: show interest, give priority to the other, wait only on conflict, then clear interest after exit.

Assumptions and Limitations

Peterson Algorithm works in the classic teaching model under important assumptions.

• Two-process scope: The basic form is designed for two processes.

• Atomic reads and writes: Shared-variable reads and writes are assumed to behave indivisibly.

• Expected memory ordering: Operations are assumed to be observed in the order the algorithm needs.

• Busy waiting: A waiting process spins while checking the condition.

Modern processors and compilers may reorder memory operations unless proper memory-ordering guarantees are used. So Peterson Algorithm is best learned as a synchronization concept, not as a practical lock for production systems.

Summary

Peterson Algorithm is a classic two-process solution for the critical section problem. It uses flag to show interest and turn to resolve conflict when both processes want to enter.

The core flow is simple: show interest, give priority to the other process, wait only if the other process is interested and has priority, enter the critical section, and clear interest on exit.