Peterson's solution in Operating Systems - Step-by-Step Execution

Concept Flow - Peterson's solution

Process 0 wants to enter

↓

Set flag[0

↓

Set turn = 1

↓

Wait while flag[1

↓

Enter critical section

↓

Set flag[0

↓

Process 0 leaves critical section

Each process signals intent, sets turn to the other, then waits if the other wants in and it's their turn, ensuring only one enters the critical section at a time.

Execution Sample

Operating Systems

flag[0] = true
turn = 1
while (flag[1] and turn == 1):
    pass
# critical section
flag[0] = false

Process 0 tries to enter critical section, waits if Process 1 is inside or has priority, then enters and finally leaves.

Analysis Table

Step	Process	flag[0]	flag[1]	turn	Condition (flag[other] and turn == other)	Action
1	P0	true	false	1	false	P0 sets flag[0]=true, turn=1, proceeds
2	P1	true	true	0	true	P1 sets flag[1]=true, turn=0, waits because flag[0]=true and turn=0
3	P0	true	true	0	false	P0 condition false (turn !=1), enters critical section
4	P1	true	true	0	true	P1 still waits
5	P0	true	true	0	false	P0 in critical section
6	P1	true	true	0	true	P1 still waits
7	P0	true	true	0	false	P0 in critical section
8	P1	true	true	0	true	P1 still waits
9	P0	false	true	0	false	P0 leaves critical section, sets flag[0]=false
10	P1	false	true	0	false	P1 condition false, proceeds to critical section

💡 P0 enters critical section when flag[1] is false or turn is not 1, ensuring mutual exclusion.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 9	After Step 10
flag[0]	false	true	true	false	false
flag[1]	false	false	true	true	true
turn	0	1	0	0	0

Key Insights - 3 Insights

Why does each process set the turn variable to the other process before waiting?

Setting turn to the other process gives priority to the other process if both want to enter, preventing deadlock as shown in execution_table steps 1 and 2.

What happens if both processes set their flags to true at the same time?

The process for which turn != other will proceed immediately (condition false), while the other waits until the first exits, ensuring mutual exclusion (see steps 3-8).

How does Peterson's solution ensure no two processes are in the critical section simultaneously?

Because a process waits if the other wants in and it's the other's turn, only one process can pass the waiting condition and enter the critical section at a time (step 9).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the condition value for Process 0's wait?

A false

B undefined

C true

D null

💡 Hint

Check the 'Condition' column at step 3 for Process 0.

At which step does Process 0 leave the critical section?

A Step 2

B Step 9

C Step 5

D Step 10

💡 Hint

Look for the action where P0 leaves critical section and sets flag[0]=false.

If Process 1 never sets flag[1] to false, what happens to Process 0?

A P0 ignores flag[1]

B P0 enters critical section immediately

C P0 waits forever

D P0 sets turn to itself

💡 Hint

Refer to the waiting condition in the execution_table where flag[1] is true and turn is 1.

Concept Snapshot

Peterson's solution uses two flags and a turn variable.
Each process sets its flag true and gives turn to the other.
It waits if the other wants in and it's their turn.
This ensures only one process enters critical section at a time.
No special hardware needed, works for two processes.

Full Transcript

Peterson's solution is a method to allow two processes to share a resource without conflict. Each process signals its desire to enter by setting a flag true and then sets the turn to the other process. It waits while the other process wants to enter and it is the other's turn. This waiting ensures only one process enters the critical section at a time, preventing conflicts. When a process finishes, it sets its flag false, allowing the other to proceed. This method avoids deadlock and ensures mutual exclusion using simple shared variables.