Software solutions: turn and flag attempts, Peterson's algorithm

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Name the three requirements of a critical-section solution. from Lesson 3.1.1
2. What does RR do when a process uses up its quantum? from Lesson 2.2.1
3. What is a thread's private state? from Lesson 1.2.1

1 · The Hook

Before special hardware instructions existed, people tried to solve the critical-section problem with ordinary variables. The first three ideas everyone has are all wrong, each in a different way, and GATE loves asking which requirement a given piece of code breaks. The fourth idea, Peterson's solution, gets everything right for two processes.

3 · Core Concept

Predict First — the answer

Yes. Both can see lock == 0 before either sets it to 1. Checking and setting are two separate steps.

In plain words

Two processes, P0 and P1, use shared variables to agree who may enter. "Waiting" here means looping on a condition until it becomes false (busy waiting). We check each attempt against the three requirements. Peterson's idea: say "I want to go", then politely offer the turn to the other one. If both want in, whoever offered last waits.

For process i, let j = 1 − i be the other process.

Attempt 1: a lock variable

while (lock == 1) ;   // wait
lock = 1;
/* critical section */
lock = 0;

Fails mutual exclusion: both can pass the while before either sets lock = 1.

Attempt 2: strict alternation (a turn variable)

while (turn != i) ;   // wait for my turn
/* critical section */
turn = j;             // give the turn away

• Mutual exclusion ✓ (turn is either 0 or 1).
• Progress ✗: the processes must take strict turns. If P0 goes off to do a long remainder section, P1 can enter once, then waits for P0 to take its turn, even though the CS is free.

Attempt 3: two flags

flag[i] = true;       // I want to enter
while (flag[j]) ;     // wait while the other wants to
/* critical section */
flag[i] = false;

• Mutual exclusion ✓.
• Progress ✗: if both set their flags before either checks, both wait for ever. Two processes each waiting for the other for ever is called a deadlock.

Peterson's solution (flags + turn)

flag[i] = true;                    // I want to enter
turn = j;                          // but you may go first
while (flag[j] && turn == j) ;     // wait only if you want it AND it is your turn
/* critical section */
flag[i] = false;                   // I am done

• Mutual exclusion ✓: if both want in, turn holds the value written last, so exactly one of them sees "it's the other's turn" and waits.
• Progress ✓: if the other doesn't want in, flag[j] is false and I enter at once.
• Bounded waiting ✓: after I leave, if I try again I set turn = j, so the waiting process gets in next (it waits at most one turn).
• Works for two processes; uses busy waiting. (On modern CPUs that reorder memory operations it needs extra "memory barrier" instructions.)

Order matters. If Peterson's first two lines are swapped (turn = j; before flag[i] = true;), mutual exclusion breaks: P0 sets turn = 1; P1 sets turn = 0, sets flag[1], sees flag[0] false and enters; P0 sets flag[0], sees turn == 0 (its own turn) and enters too.

4 · Visual

Peterson, both want in at the same time

P0: flag[0]=T   turn=1                 check: flag[1] && turn==1 ? -> turn is 0 -> ENTER
P1:       flag[1]=T   turn=0           check: flag[0] && turn==0 ? -> yes  -> WAIT
                           ^ written last, so P1 is the one that waits

5 · Worked Examples

Example 1 Easy

Strict alternation, turn = 0. P0 enters and leaves once (turn becomes 1), then spends an hour in its remainder section. P1 wants to enter twice. What happens?

Solution

P1 enters once (turn = 1), sets turn = 0 on leaving, then waits for P0 even though no one is in the CS: progress is violated.

Example 2 Medium

Two-flag attempt: give an order of steps that makes both processes wait for ever.

Solution

P0 sets flag[0] = true; P1 sets flag[1] = true; now P0 loops on flag[1] and P1 loops on flag[0]: deadlock.

Example 3 GATE

In Peterson's solution a student replaces while (flag[j] && turn == j) by while (flag[j] && turn == i) but also writes turn = i instead of turn = j. Is mutual exclusion still guaranteed?

Solution

Yes. Now each process offers the turn to itself and waits while it is its own turn. Whoever wrote turn last still waits, so the logic is the same with the roles of the two values swapped. (Checked by trying every interleaving.)

6 · GATE Traps

• Peterson's order is: flag first, then turn; swapping breaks mutual exclusion.
• Strict alternation satisfies mutual exclusion but not progress.
• The flags-only attempt can deadlock: a progress failure.
• Peterson's solution is for 2 processes and uses busy waiting (CPU time is wasted while spinning).

7 · Memory Hook

"Raise your flag, give away the turn, wait only if the other wants it and it's theirs."

8 · Connect the Dots

Software solutions are delicate and slow. The next lesson uses special hardware instructions that read and write a variable in one indivisible step, which makes locks simple.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Strict alternation

Strict alternation with a shared turn variable violates which requirement?

1. (A) Both mutual exclusion and progress
2. (B) Progress
3. (C) None of them
4. (D) Mutual exclusion

Q2 · MCQ · 1 mark(s) — Flags

In the two-flag attempt (set your flag, then wait while the other's flag is set), what can go wrong?

1. (A) Both processes waiting for ever
2. (B) Nothing
3. (C) Both processes in the critical section together
4. (D) One process entering twice in a row

Q3 · MCQ · 1 mark(s) — Lock variable

The simple lock variable (while (lock == 1); lock = 1;) fails because:

1. (A) it can deadlock
2. (B) it violates mutual exclusion
3. (C) it needs special hardware
4. (D) it only works for 3 processes

Q4 · MSQ · 2 mark(s) — Peterson

Which statements about Peterson's solution (two processes) are true?

1. (A) It avoids busy waiting
2. (B) It guarantees progress
3. (C) It guarantees mutual exclusion
4. (D) It guarantees bounded waiting

Q5 · MCQ · 2 mark(s) — Swapped lines

Peterson's code for process i is changed to: turn = j; flag[i] = true; while (flag[j] && turn == j); What happens?

1. (A) Deadlock becomes possible
2. (B) It is still correct
3. (C) Bounded waiting is lost but mutual exclusion holds
4. (D) Mutual exclusion can be violated

10 · Rule Card

• Lock variable: fails mutual exclusion.
• Strict alternation (turn): mutual exclusion ✓, progress ✗.
• Two flags: mutual exclusion ✓, progress ✗ (deadlock).
• Peterson: flag[i] = true; turn = j; wait while (flag[j] && turn == j). All three ✓, 2 processes, busy waiting.
• Swapping Peterson's first two lines breaks mutual exclusion.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

busy waitinglock variable attemptstrict alternationtwo-flag attemptdeadlock (first meaning)Peterson's solutionwhy the order of Peterson's lines matters