Unit 2 · Concurrent Processes

Lecture 4: Dekker’s solution

Learning outcomes

Explain why Dekker’s algorithm is an early correct software-only solution for two processes.
Use want[2] (flags) and turn to describe the back-off and retry mechanism.
Reason (at idea level) how Dekker satisfies mutual exclusion, progress, and bounded waiting.
Identify the practical limitation: busy waiting (spinning).

Prerequisites

-- Lecture 3: Mutual Exclusion & Critical Section Problem (three requirements). -- Meaning of a critical section: shared data must not be updated concurrently. -- Basic idea of concurrency: CPU can interleave steps unpredictably (race condition risk).

Lecture Notes

Main content

Dekker’s Solution (Two-Process Mutual Exclusion)

1) Quick recap: What a correct solution must guarantee

Any solution to the critical-section problem must satisfy: Mutual Exclusion (only one in CS), Progress (if CS is free and someone wants in, do not postpone forever), and Bounded Waiting (no starvation).

2) Dekker’s Solution — the core idea

Dekker’s algorithm is a classic two-process mutual exclusion protocol. It uses: (i) intent flags to show “I want to enter” and (ii) a turn variable as a tie-breaker. The key mechanism is back-off and retry: if both processes want the critical section, the one whose turn it is not will temporarily withdraw its request (sets its flag to false), waits for the turn to change, and then tries again.

Key mechanism: Back-off

If both want to enter, the process whose turn it is NOT will set its flag to false, wait until turn changes, then set its flag to true again (retry).

3) Shared variables and assumptions

Shared variables

want[0], want[1] (boolean): whether P0/P1 wants to enter CS
turn (0 or 1): who should get priority when both want CS

Classic assumptions (for understanding)

Only two processes: P0 and P1.
Reads/writes of a single shared variable are treated as atomic.
Algorithm uses busy waiting (spin loops).

4) Dekker’s algorithm (generic pseudocode)

Below is a clean two-process version (for process P_i, where j = 1 − i).

// Shared:
boolean want[2] = {false, false};
int turn = 0;   // 0 or 1

// Code for process Pi (i = 0 or 1, j = 1 - i)
do {
  want[i] = true;                 // 1) I want to enter CS

  while (want[j]) {               // 2) other also wants CS?
    if (turn == j) {              // 3) if it is the other’s turn
      want[i] = false;            // 4) back off (withdraw request)
      while (turn == j) {
        ;                         // 5) wait (busy wait)
      }
      want[i] = true;             // 6) retry
    }
  }

  // -------- critical section --------

  turn = j;                       // 7) give the other a chance next
  want[i] = false;                // 8) I am leaving CS

  // -------- remainder section --------
} while (true);

Dekker’s algorithm resolves “both want to enter” using turn and a temporary back-off.

5) Why Dekker works (exam-friendly reasoning)

Mutual Exclusion

If want[j] = false, Pi enters CS.
If both want CS, turn forces one process to back off, so they cannot both pass the while-condition together.

Progress

If CS is free and only one process wants to enter, it enters immediately.
If both want to enter, one is selected by the current value of turn; the other backs off and retries.

Bounded Waiting

On exit, the process sets turn = j, giving the other process priority next.
This prevents a process from continuously re-entering and starving the other.

Practical note

Dekker (like other classic software-only mutual exclusion algorithms) uses busy waiting. Real operating systems typically implement mutexes/semaphores using hardware support to avoid long spinning. The textbook also notes that even classic software-only approaches (shown via Peterson) are mainly for algorithmic understanding because modern architectures do not always guarantee correct behavior under all reorderings.

Worked Example

Scenario: Both P0 and P1 request the critical section at the same time

Assume initially: turn = 0, want[0]=false, want[1]=false. Now both set their flags to true almost simultaneously.

Step	P0 (i=0, j=1)	P1 (i=1, j=0)
1	`want[0] = true`	`want[1] = true`
2	Sees `want[1] == true` → enters while-loop	Sees `want[0] == true` → enters while-loop
3	Checks `turn == 1` → false (since turn=0) → does not back off	Checks `turn == 0` → true → backs off: `want[1]=false`
4	Now sees `want[1] == false` → enters critical section	Waits while `turn == 0` (spin), then retries later
5	On exit: sets `turn = 1`, then `want[0]=false`	Now `turn == 1` → stops waiting, sets `want[1]=true` again, and enters CS next

Takeaway

When both want to enter, exactly one backs off due to turn. This prevents deadlock and enforces mutual exclusion.

One-Page Summary

Dekker’s solution is a classic software-only mutual exclusion algorithm for two processes.
Uses two shared items: want[2] (intent flags) and turn (tie-breaker).
Back-off and retry: if both want CS, the process whose turn it is not sets its flag to false, waits for turn to change, then tries again.
Mutual exclusion: two processes cannot pass the entry logic simultaneously because one backs off in the conflict case.
Progress: if CS is free and someone wants in, the protocol allows entry (no indefinite postponement by non-requesting processes).
Bounded waiting: on exit, a process sets turn to the other, preventing starvation.
Limitation: uses busy waiting (spinning), so it is mainly used for understanding; real OS uses locks/semaphores built with hardware support.