Dekkers Algorithm - Learning Module

Loading content...

0/240

Flag Mechanism

Expressing Intent in Concurrent Systems

In sequential programming, intention is implicit in execution order. If you write doA(); doB();, your intent to do A before B is directly expressed in the code.

Concurrent programming destroys this luxury. Multiple processes execute simultaneously, and there's no inherent ordering between their actions. When Process A wants to access a shared resource, Process B has no way to know this—unless Process A explicitly declares its intent.

This is the fundamental role of the flag variables in Dekker's Algorithm. Each process has its own flag that it sets when it wants to enter the critical section. By reading the other process's flag, a process can detect potential conflict before it becomes a safety violation.

This page examines the flag mechanism in comprehensive detail: how flags are used to express intent, how they enable contention detection, how the critical "back-off" behavior prevents deadlock, and the subtle ordering requirements that make the mechanism correct.

What You Will Learn

By the end of this page, you will understand how flag variables express intent in Dekker's Algorithm, why the 'set flag before check' ordering is essential for safety, how the back-off protocol prevents deadlock while preserving mutual exclusion, and the subtle atomicity requirements for flag operations.

Flag Semantics and Intent Declaration

Dekker's Algorithm uses two Boolean flag variables, one for each process:

boolean flag[2] = {FALSE, FALSE};

Semantic Meaning:

flag[i] = FALSE: Process i is not interested in the critical section
flag[i] = TRUE: Process i wants to enter the critical section, or is in the critical section

Importantly, a flag being TRUE doesn't mean the process is definitely in the critical section—it means the process is either:

Trying to enter (in entry protocol)
Currently inside (in critical section)
About to exit (before clearing flag in exit protocol)

Ownership Rules:

Each flag is written only by its owner but read by the other process:

Process 0 writes flag[0]; Process 1 reads flag[0]
Process 1 writes flag[1]; Process 0 reads flag[1]

This single-writer/multiple-reader pattern simplifies reasoning because there are no write-write conflicts on individual flags.

Flag States and Their Meanings
flag[0]	flag[1]	Interpretation
FALSE	FALSE	Neither process wants critical section; CS is available
TRUE	FALSE	Process 0 wants/has CS; Process 1 is uninterested
FALSE	TRUE	Process 1 wants/has CS; Process 0 is uninterested
TRUE	TRUE	CONTENTION: Both want CS; turn variable decides

Flags as Reservations

Think of flags like making a reservation at a single-table restaurant. Setting your flag is like calling ahead to reserve the table. The other diner can see your reservation and know they'll need to wait. But unlike reservations, there's no central host—both diners check each other's reservations directly.

The Intent-Action Gap:

A critical subtlety is the gap between intent (setting the flag) and action (entering the critical section). A process sets its flag before it knows whether it can enter. This is the fundamental principle that distinguishes Dekker's approach from failed alternatives:

In failed approaches, processes check-then-claim: they check if the resource is free, then claim it. The race is between check and claim.
In Dekker's approach, processes claim-then-negotiate: they claim intent first, then negotiate entry based on who else has claimed intent.

By reversing the order, the race condition is eliminated. Both processes declare intent, then—knowing both intents—they can safely determine who should proceed.

The Critical Ordering: Set Before Check

The most critical aspect of the flag mechanism is the ordering:

Always set your flag BEFORE checking the other's flag.

This ordering is non-negotiable. Reversing it breaks mutual exclusion.

Why Set Before Check?

Consider what happens if we check before setting:

check_before_set_broken.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// BROKEN: Check before set
// This violates mutual exclusion!
 
void process_i_broken(int i, int j) {
    // Entry section (WRONG ORDER)
    
    // First, check if other wants to enter
    while (flag[j] == TRUE) {
        // Wait for other to leave
    }
    // Here, flag[j] is FALSE... but between this check
    // and the next line, the other process can also check!
    
    // Now set our flag
    flag[i] = TRUE;  // TOO LATE - other may have also passed check!
    
    // === CRITICAL SECTION ===
    // DANGER: Both processes may be here!
    // === END CRITICAL SECTION ===
    
    flag[i] = FALSE;
}
 
/*
 * FAILURE TRACE:
 * 
 * Time    Process 0                    Process 1
 * ----    ---------                    ---------
 * t1      while(flag[1]==TRUE)?        
 *         -> FALSE (flag[1]=FALSE)
 * t2      // about to set flag[0]      while(flag[0]==TRUE)?
 *                                      -> FALSE (flag[0]=FALSE)
 * t3      flag[0] = TRUE               flag[1] = TRUE
 * t4      === CRITICAL SECTION ===     === CRITICAL SECTION ===
 * 
 * MUTUAL EXCLUSION VIOLATED!
 * Window between check and set is exploitable.
 */

Now the Correct Ordering:

When we set before check, the race window is closed:

set_before_check_correct.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// CORRECT: Set before check
// This ensures mutual exclusion
 
void process_i_correct(int i, int j) {
    // Entry section (CORRECT ORDER)
    
    // First, declare intent to enter
    flag[i] = TRUE;  // Commit to trying before observing
    
    // Now check if other wants to enter
    while (flag[j] == TRUE) {
        // Other also wants to enter
        // Use turn to decide who backs off
        // (details omitted - see turn mechanism)
    }
    // Here, flag[j] is FALSE, meaning:
    // - Other finished critical section, OR
    // - Other never wanted critical section, OR
    // - Other backed off (will retry)
    
    // === CRITICAL SECTION ===
    // Safe: either we came first, or we won the negotiation
    // === END CRITICAL SECTION ===
    
    flag[i] = FALSE;  // Signal departure
}
 
/*
 * WHY THIS WORKS:
 * 
 * Time    Process 0                    Process 1
 * ----    ---------                    ---------
 * t1      flag[0] = TRUE              
 * t2                                   flag[1] = TRUE
 * t3      while(flag[1]==TRUE)?        while(flag[0]==TRUE)?
 *         -> TRUE! stay in loop        -> TRUE! stay in loop
 * t4      // Contention detected!      // Contention detected!
 * t5      // Use turn to resolve       // Use turn to resolve
 * 
 * Both see contention. No race to critical section.
 * Turn variable determines who proceeds safely.
 */

Memory Ordering Assumption

The 'set before check' correctness relies on sequential consistency: the write to flag[i] is visible to the read of flag[j]. On modern processors with relaxed memory models, memory barriers may be required to enforce this ordering. This is one of Dekker's Algorithm's limitations on modern hardware, which we'll explore in a later page.

The Invariant Established by Set-Before-Check:

If Process i is in the critical section, then:
  flag[i] was set before Process i checked flag[j]
  
Consequently:
  Either flag[j] was FALSE when checked (no contention)
  Or flag[j] was TRUE and Process j eventually backed off
  
In both cases:
  Process j is not in the critical section simultaneously

This invariant is the foundation of mutual exclusion in Dekker's algorithm.

Contention Detection via Flags

Once a process has set its flag, it enters the contention detection phase by checking the other process's flag.

The Decision Tree:

contention_detection.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// After setting flag[i] = TRUE
 
if (flag[j] == FALSE) {
    // NO CONTENTION
    // The other process either:
    // - Never wanted the critical section
    // - Already finished and left
    // - Backed off (temporarily withdrew)
    //
    // In all cases: safe to proceed immediately
    
    goto critical_section;
    
} else {
    // CONTENTION DETECTED (flag[j] == TRUE)
    // The other process also wants the critical section
    // 
    // We cannot both enter, so we must negotiate
    // This is where the turn variable comes in
    
    if (turn == i) {
        // I have priority - stay in loop, wait for other to back off
        // The other process, seeing turn != j, will back off
    } else {
        // I do not have priority - I must back off
        // Clear my flag, wait for my turn, then retry
    }
}

Understanding the Detection Loop:

The check of flag[j] is embedded in a while loop, not an if statement. This is crucial:

while (flag[j] == TRUE) {
    // Handle contention
}

The loop continues as long as the other process's flag remains TRUE. This handles the following scenarios:

Initial contention: Both set flags, one backs off, other waits
Retry after back-off: Backed-off process re-sets flag, contention recurs
Spurious check: Memory subsystem might show stale FALSE briefly

The loop ensures that a process only exits when it definitively observes flag[j] == FALSE—meaning the other process is not contending.

Contention Detection Properties

•Conservative: Assumes contention if other's flag is TRUE, even if they're about to back off
•Polling-based: Continuously checks until condition satisfied (busy waiting)
•Eventually terminating: The turn mechanism guarantees at least one process sees the other's flag drop
•Order-sensitive: Works only because flag was set before this check happens

Why Not Use a Single Flag?

A common question is: why have two separate flags? Why not a single 'occupied' flag? The answer is that a single flag creates the check-then-act race. With separate flags, each process writes its own flag (eliminating write contention) and reads the other's flag (detecting conflict). This separation is what enables correct conflict detection.

The Back-Off Protocol

The back-off protocol is where Dekker's Algorithm prevents deadlock. When both processes want to enter and one doesn't have the turn, that process must temporarily withdraw its claim to allow the other to proceed.

The Back-Off Sequence:

backoff_protocol.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Inside the contention handling loop
// Process i has set flag[i] = TRUE and sees flag[j] == TRUE
// turn != i, so Process i must back off
 
void back_off_protocol(int i, int j) {
    // Step 1: Withdraw my claim temporarily
    flag[i] = FALSE;
    
    /*
     * WHY THIS IS ESSENTIAL:
     * 
     * Without this, we have:
     *   flag[i] = TRUE, flag[j] = TRUE
     *   Process i waiting for flag[j] to become FALSE
     *   Process j waiting for flag[i] to become FALSE
     *   DEADLOCK - neither will ever proceed
     * 
     * By clearing flag[i], we break the deadlock:
     *   flag[i] = FALSE, flag[j] = TRUE
     *   Process j sees flag[i] = FALSE
     *   Process j exits its waiting loop
     *   Process j enters critical section
     */
    
    // Step 2: Wait for my turn
    while (turn != i) {
        // Busy wait
        // The other process will eventually exit and set turn = i
    }
    
    /*
     * WHY WAIT FOR TURN:
     * 
     * We can't immediately re-raise our flag because:
     * - The other process might still be in critical section
     * - If we raise flag[i] too soon, we might cause new contention
     *   before the current contention is resolved
     * 
     * By waiting for turn, we ensure the other process has finished
     * and has transferred priority to us.
     */
    
    // Step 3: Reassert my claim
    flag[i] = TRUE;
    
    /*
     * NOW WE HAVE PRIORITY:
     * 
     * turn = i, so if there's new contention, WE stay in the loop
     * and the OTHER process must back off.
     * 
     * Go back to the top of the outer while loop to re-check flag[j].
     * If flag[j] is FALSE, we enter critical section.
     * If flag[j] is TRUE, we spin (we have priority, other will back off).
     */
}
 
/*
 * COMPLETE TRACE: Both want to enter, turn = 0
 * 
 * Time  P0 flag[0]  P1 flag[1]  turn  P0 Location          P1 Location
 * ----  ----------  ----------  ----  ------------         ------------
 * t1    TRUE        FALSE       0     set flag[0]          
 * t2    TRUE        TRUE        0                          set flag[1]
 * t3    TRUE        TRUE        0     while(flag[1])       while(flag[0])
 * t4    TRUE        TRUE        0     turn==0,spin                  turn!=1!  
 * t5    TRUE        FALSE       0     while(flag[1])       flag[1]=FALSE (backoff)
 * t6    TRUE        FALSE       0     exit while           while(turn!=1)
 * t7    TRUE        FALSE       0     === CRITICAL ===     spinning
 * ...
 * t20   TRUE        FALSE       1     turn=1 (exit)        spinning
 * t21   FALSE       FALSE       1     flag[0]=FALSE        while(turn!=1)?
 * t22   FALSE       FALSE       1                          exit turn wait
 * t23   FALSE       TRUE        1                          flag[1]=TRUE
 * t24   FALSE       TRUE        1                          while(flag[0])? exit
 * t25   FALSE       TRUE        1                          === CRITICAL ===
 */

Properties of the Back-Off Protocol:

1. Deadlock Prevention: When both flags are TRUE and turn = i, Process j (with turn != j) backs off by clearing its flag. This guarantees that Flag j becomes FALSE, allowing Process i to exit its waiting loop and enter the critical section.

2. Preservation of Safety: Backing off doesn't break mutual exclusion. When Process j clears its flag, it's explicitly giving up its claim. It cannot enter the critical section until it re-raises its flag and successfully passes through the entry protocol.

3. Priority Handoff: By waiting for turn == j before re-raising its flag, Process j ensures it will have priority on the next contention. This is how fairness is achieved.

4. Bounded Waiting: Process j's wait for turn is bounded. Process i will eventually exit and set turn = j. At that point, Process j can retry with priority.

The After-You Dilemma

The back-off protocol is like two polite people at a door, each saying 'after you.' With just politeness, you get livelock—both keep deferring. Dekker's solution adds the turn variable: one person has priority and MUST go first. The other defers and waits, knowing their turn will come. This converts infinite mutual deference into orderly sequencing.

Flag Transitions and State Machine

Understanding Dekker's Algorithm deeply requires understanding exactly when and why flags change. Each process's flag follows a specific pattern of transitions:

Flag State Machine for Process i:

flag_state_machine.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
FLAG[i] STATE TRANSITIONS
 
┌──────────────────────────────────────────────────────────────────┐
│                                                                  │
│  ┌─────────┐                                    ┌─────────┐     │
│  │  FALSE  │ ─────── flag[i] = TRUE ──────────▶ │  TRUE   │     │
│  │(Idle/   │ (Want to enter critical section)   │(Wanting/│     │
│  │Remainder)│                                   │In CS)   │     │
│  └─────────┘                                    └────┬────┘     │
│       ▲                                              │          │
│       │                                              │          │
│       │                                              │          │
│       │     flag[i] = FALSE                          │          │
│       │     (Exit critical section)                  │          │
│       │                                              │          │
│       └──────────────────────────────────────────────┘          │
│                                                                  │
│                         BACKOFF LOOP                             │
│                              │                                   │
│                              ▼                                   │
│  ┌─────────┐         ┌───────────────┐         ┌─────────┐      │
│  │  TRUE   │ ───────▶│    FALSE      │────────▶│  TRUE   │      │
│  │(Wanting)│ backoff │(Backed off,   │ turn=i  │(Have    │      │
│  │         │         │waiting turn)  │         │priority)│      │
│  └─────────┘         └───────────────┘         └─────────┘      │
│                                                                  │
└──────────────────────────────────────────────────────────────────┘
 
TRANSITIONS:
 
1. FALSE → TRUE (Entry Protocol Start)
   Trigger: Process wants to enter critical section
   Condition: None (always allowed)
   Action: flag[i] = TRUE
   Next: Check flag[j]
 
2. TRUE → FALSE (Backoff)
   Trigger: Contention detected and turn != i
   Condition: flag[j] == TRUE && turn != i
   Action: flag[i] = FALSE
   Next: Wait for turn == i
 
3. FALSE → TRUE (Re-entry after backoff)
   Trigger: Turn transferred to i
   Condition: turn == i
   Action: flag[i] = TRUE
   Next: Re-check flag[j]
 
4. TRUE → FALSE (Exit Protocol)
   Trigger: Leaving critical section
   Condition: Was in critical section
   Action: flag[i] = FALSE (and turn = j)
   Next: Remainder section

Transition Invariants:

Several invariants govern Flag transitions:

Invariant 1: Only self-modification

flag[i] is only modified by Process i

Invariant 2: TRUE requires intent

flag[i] == TRUE implies Process i intends to enter or is in critical section

Invariant 3: Critical section requires TRUE flag

Process i in critical section implies flag[i] == TRUE

Invariant 4: Exit clears flag

After executing exit protocol, flag[i] == FALSE

Invariant 5: Backoff is temporary

If Process i backs off (clears flag while wanting entry),
it will re-raise flag after turn is transferred

Complete Flag Lifecycle
Phase	Flag Value	Meaning	What Process Is Doing
Remainder	FALSE	Not interested in CS	Non-critical work
Entry (initial)	TRUE	Wants to enter	About to check flag[j]
Entry (waiting)	TRUE	Has priority, waiting	Spinning on flag[j]
Entry (backoff)	FALSE	Deferred to other	Waiting for turn transfer
Entry (retry)	TRUE	Has turn, trying again	Re-checking flag[j]
Critical Section	TRUE	In critical section	Executing critical code
Exit	FALSE	Finished	Gave turn, cleared flag

Common Mistakes with Flag Handling

When implementing or modifying Dekker's Algorithm, several mistakes commonly occur with flag handling. Understanding these helps avoid bugs and deeper understanding of why the algorithm works.

Mistake 1: Not Backing Off

mistake_no_backoff.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// MISTAKE: Not clearing flag during contention
// Results in DEADLOCK
 
while (flag[j] == TRUE) {
    if (turn != i) {
        // WRONG: Just wait, don't back off
        while (turn != i) {
            // Spin forever
        }
        // flag[i] is still TRUE!
        // Other process is also spinning on flag[i]
        // DEADLOCK!
    }
}
 
// CORRECT: Back off by clearing flag
while (flag[j] == TRUE) {
    if (turn != i) {
        flag[i] = FALSE;  // ESSENTIAL: Let other proceed
        while (turn != i) {
            // Now other can see flag[i] = FALSE and enter
        }
        flag[i] = TRUE;  // Re-raise after turn transferred
    }
}

Mistake 2: Not Re-raising Flag After Backoff

mistake_no_reraise.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// MISTAKE: Not re-raising flag after backoff
// Results in SAFETY VIOLATION
 
while (flag[j] == TRUE) {
    if (turn != i) {
        flag[i] = FALSE;
        while (turn != i) {
            // Wait for turn
        }
        // WRONG: Forgot to set flag[i] = TRUE!
        // flag[i] is still FALSE
    }
}
 
// Now we exit the while loop:
// - flag[j] might be TRUE (other process re-entered)
// - flag[i] is FALSE (we never re-raised it)
// - We're about to enter critical section with flag[i] = FALSE!
// - Other process doesn't see us as contending!
// - MUTUAL EXCLUSION CAN BE VIOLATED!

Mistake 3: Checking Flag Before Setting

mistake_check_first.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// MISTAKE: Check before set
// Creates classic race condition
 
// WRONG ORDER:
while (flag[j] == TRUE) {
    // Wait for other to finish
}
flag[i] = TRUE;  // TOO LATE!
 
// Between the while loop exit and setting flag[i],
// the other process can:
// 1. Check flag[i] (sees FALSE)
// 2. Set flag[j] to TRUE
// 3. Check flag[i] again (still FALSE)
// 4. Enter critical section
//
// Then we set flag[i] = TRUE and also enter!
// MUTUAL EXCLUSION VIOLATED!
 
// CORRECT ORDER:
flag[i] = TRUE;
while (flag[j] == TRUE) {
    // Handle contention
}

Summary of Flag Mistakes

•Not backing off → Deadlock (both flags TRUE forever)
•Not re-raising after backoff → Safety violation (mutual exclusion broken)
•Checking before setting → Race condition (check-then-act bug)
•Clearing flag before turn transfer (exit) → Possible fairness issues
•Using wrong flag index (i vs j) → Complete algorithm failure

Delicate Algorithm

Dekker's Algorithm is often described as 'delicate' because small changes break it. The precise ordering and timing of flag operations matter. This is why Peterson's simpler algorithm is preferred for teaching—it has fewer places to make mistakes while achieving the same properties.

Summary: The Flag Mechanism

We've explored the flag mechanism in Dekker's Algorithm in comprehensive detail. Let's consolidate the key insights:

Key Takeaways

•Flags express intent — flag[i] = TRUE means 'I want to enter or am in the critical section'
•Set before check — Always set your flag before checking the other's flag to prevent race conditions
•Contention detection — If the other's flag is TRUE, contention exists and must be resolved
•Backoff is essential — The non-favored process clears its flag, waits for turn, then re-raises
•Single-writer per flag — Each process writes only its own flag, eliminating write-write conflicts
•Flag in critical section — A process's flag is TRUE throughout its time in the critical section
•Order matters everywhere — Entry, exit, and backoff all have specific orderings that must be followed

What's Next:

Having understood both the turn mechanism (previous page) and the flag mechanism (this page), we're ready for a direct comparison between Dekker's Algorithm and Peterson's Algorithm. The next page examines the structural similarities and differences, why Peterson's version is simpler, and when each approach might be preferred.

Page Complete

You now understand the flag mechanism in Dekker's Algorithm—how flags express intent, how contention is detected and resolved, and why the precise ordering of flag operations is critical for correctness. This completes our examination of the algorithm's core mechanisms. Next, we compare Dekker's approach with Peterson's simpler alternative.