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.

Practice

1. What is the main purpose of Peterson's solution in operating systems?

easy

A. To prevent two processes from accessing a shared resource simultaneously

B. To increase the speed of process execution

C. To allocate memory to processes

D. To schedule processes based on priority

Solution

1. Step 1: Understand the problem Peterson's solution addresses

   Peterson's solution is designed to handle the critical section problem where two processes must not access a shared resource at the same time.

2. Step 2: Identify the main goal of the solution

   The main goal is to ensure mutual exclusion, preventing simultaneous access to shared resources.

3. Final Answer:

   To prevent two processes from accessing a shared resource simultaneously -> Option A

4. Quick Check:

   Mutual exclusion = Prevent simultaneous access [OK]

Hint: Peterson's solution controls access to shared resources [OK]

Common Mistakes:

• Confusing it with process scheduling
• Thinking it manages memory allocation
• Assuming it increases execution speed

2. Which of the following variables is NOT used in Peterson's solution?

easy

A. flag

B. turn

C. counter

D. process_id

Solution

1. Step 1: Recall the variables used in Peterson's solution

   Peterson's solution uses two flags (one per process) and a turn variable to control access.

2. Step 2: Identify the variable not part of the solution

   The variable 'counter' is not used in Peterson's solution; it is unrelated to mutual exclusion control.

3. Final Answer:

   counter -> Option C

4. Quick Check:

   Variables used = flag, turn; counter not used [OK]

Hint: Remember only flag and turn variables are used [OK]

Common Mistakes:

• Assuming process_id is a variable in Peterson's solution
• Confusing counter with flag
• Thinking turn is a counter

3. Consider two processes P0 and P1 using Peterson's solution. If both set their flags to true and turn to 1, which process will enter the critical section first?

medium

A. P0

B. P1

C. Both enter simultaneously

D. Neither enters

Solution

1. Step 1: Analyze the turn variable's role

   The turn variable indicates which process's turn it is to enter the critical section when both want access.

2. Step 2: Apply the given values

   Both flags are true, meaning both want to enter. Since turn is set to 1, process P1 has priority to enter first.

3. Final Answer:

   P1 -> Option B

4. Quick Check:

   Turn = 1 means P1 enters first [OK]

Hint: Turn variable decides which process enters first [OK]

Common Mistakes:

• Assuming both enter simultaneously
• Ignoring the turn variable
• Thinking the first flag set enters first

4. Identify the error in this Peterson's solution snippet for process P0:

flag[0] = true;
turn = 1;
while(flag[1] && turn == 1) {
  // wait
}
// critical section
flag[0] = false;

medium

A. No error; this is correct Peterson's solution code

B. turn should be set to 0 instead of 1

C. flag[0] should be set to false before the while loop

D. The while condition should use OR instead of AND

Solution

1. Step 1: Review the Peterson's solution steps for process P0

   Process P0 sets its flag true, sets turn to the other process (1), then waits while the other process wants to enter and it's their turn.

2. Step 2: Check the correctness of the code snippet

   The code correctly implements the waiting condition and resets the flag after the critical section.

3. Final Answer:

   No error; this is correct Peterson's solution code -> Option A

4. Quick Check:

   Code matches Peterson's solution pattern [OK]

Hint: Check waiting condition and flag reset carefully [OK]

Common Mistakes:

• Changing turn to own process instead of other
• Misplacing flag reset before critical section
• Using OR instead of AND in while condition

5. How does Peterson's solution ensure fairness between two processes competing for a critical section?

hard

A. By allowing the process with higher priority to enter first

B. By locking the resource permanently for the first process

C. By using a random number generator to decide access

D. By using a turn variable to alternate access between processes

Solution

1. Step 1: Understand fairness in Peterson's solution

   Fairness means no process waits forever; both get a chance to enter the critical section.

2. Step 2: Identify how fairness is implemented

   The turn variable ensures that if both processes want access, the one whose turn it is gets priority, then the turn switches, alternating access.

3. Final Answer:

   By using a turn variable to alternate access between processes -> Option D

4. Quick Check:

   Turn variable alternates access = fairness [OK]

Hint: Turn variable alternates access to ensure fairness [OK]

Common Mistakes:

• Thinking priority decides access
• Assuming random choice controls fairness
• Believing resource is locked permanently