Peterson's solution in Operating Systems - Full Explanation

Introduction

Imagine two people trying to use the same bathroom but only one can enter at a time. Without a clear way to decide who goes first, they might both try to enter or wait forever. Peterson's solution solves this problem for two processes trying to use a shared resource without conflicts or delays.

Explanation

Mutual Exclusion

Peterson's solution ensures that only one process can enter its critical section at a time. It uses two shared variables to coordinate access, preventing both processes from running their critical code simultaneously.

Only one process can be in the critical section at any moment.

Turn Variable

A shared variable called 'turn' indicates which process has the priority to enter the critical section. This variable helps avoid deadlock by giving one process the chance to proceed while the other waits.

The 'turn' variable controls which process gets priority to enter.

Flag Variables

Each process has a flag that it sets to true when it wants to enter the critical section. These flags let the processes know if the other is interested in entering, helping them decide whether to wait or proceed.

Flags show each process's intention to enter the critical section.

Waiting Condition

A process waits if the other process wants to enter and it is not its turn. This waiting condition ensures fairness and prevents both processes from entering at the same time.

Processes wait if it's not their turn and the other wants to enter.

Real World Analogy

Two friends want to use a single bathroom. Each friend raises their hand to show they want to enter. They agree to let the friend whose turn it is go first. If it's not your turn and the other friend wants to enter, you wait patiently until your turn comes.

Mutual Exclusion → Only one friend can be inside the bathroom at a time.

Turn Variable → The agreed order deciding which friend goes first.

Flag Variables → Each friend raising their hand to show they want to enter.

Waiting Condition → Waiting outside if it's not your turn and the other friend wants to enter.

Diagram

Diagram

┌───────────────┐       ┌───────────────┐
│ Process 0     │       │ Process 1     │
│               │       │               │
│ flag[0] = true│       │ flag[1] = true│
│ turn = 1      │◄──────│ turn = 0      │
│ Wait if flag[1] and turn == 1 │       │ Wait if flag[0] and turn == 0 │
│ Enter critical│       │ Enter critical│
│ section      │       │ section       │
└───────────────┘       └───────────────┘

Diagram showing two processes using flags and turn variable to coordinate entry into critical section.

Key Facts

Mutual Exclusion → Ensures only one process accesses the critical section at a time.

Turn Variable → Shared variable indicating which process has priority to enter.

Flag Variable → Boolean variable showing a process's intention to enter the critical section.

Deadlock → A situation where processes wait forever and none proceed.

Peterson's solution → A software method to achieve mutual exclusion between two processes.

Common Confusions

Believing Peterson's solution works for more than two processes.

Believing Peterson's solution works for more than two processes. Peterson's solution is designed only for two processes; it does not scale to more without modification.

Thinking the 'turn' variable alone prevents conflicts.

Thinking the 'turn' variable alone prevents conflicts. Both 'turn' and 'flag' variables work together; 'turn' alone cannot ensure mutual exclusion.

Assuming Peterson's solution works on all hardware without issues.

Assuming Peterson's solution works on all hardware without issues. Peterson's solution requires sequential consistency in memory operations, which some modern hardware may not guarantee without memory barriers.

Summary

Peterson's solution uses two flags and a turn variable to let two processes share a resource safely.

It guarantees that only one process enters the critical section at a time, preventing conflicts.

The solution is simple but only works correctly for two processes and requires specific memory behavior.