Concurrency

Dekker’s Algorithm

The algorithm uses shared flags and a turn variable to ensure that only one thread can enter the critical section at a time, preventing race conditions without relying on busy waiting or requiring special hardware instructions.

Program is a modification of combination of the alternation program but with variable rather than fixed priority assignment.

The shared variable Last indicates which thread was last in the bathroom by alternately pointing at the two intent variables in uMain::main; this corresponds to the new chalk board on the outside of the bathroom door.

Figure 6.7

The entry protocol sets intent to enter and only does further checking if the other thread also wants to enter. Then the threads divide into the high and low priority threads at line 3, depending on which thread was last in the critical section. The high-priority thread (not last in the bathroom) proceeds to line 7 without retracting its intent and waits for the other thread to retract its intent or exit the critical section. The low-priority thread retracts its intent at line 4 and waits at line 5 for the other thread to exit the critical section. When the high-priority thread exits the critical section, the priority switches (assignment to Last), and the low-priority thread becomes the high-priority thread moving to line 7 and waiting for the other thread to retract its intent or exit the critical section.

Alternate implementation of Dekker’s algorithm:

Figure 6.8

The outer loop (line 2) is where the high-priority thread busy waits, and the inner loop (line 6) is where the low-priority thread busy waits. The if statement (line 4) controls which thread has low or high priority. The low-priority loop is nested in the high-priority loop because of the two steps in the exit protocol: setting Last and retracting intent. The low priority thread in the nested loop of the entry protocol might detect Last having changed, exit the busy loop, but still have to wait for the other thread to complete the exit protocol by retracting its intent. Think of what could go wrong if the low priority thread did not wait for the other thread to complete all the exit protocol before preceding into the critical section. In the case of simultaneous arrival, the thread last in the critical section is directed to the low-priority code, where it retracts intent (line 5), so the other thread can make progress. Hence, livelock is prevented by alternating on simultaneous arrival, and rule 4 is satisfied.

In Dekker’s algorithm, the low-priority thread retracts intent, so when the high- priority thread exits the critical section and attempts reentry, it does not exclude itself.

Nested Loop Structure implementation

In Dekker’s algorithm, the nested loop structure enforces that:

• The high-priority thread loops at the outer level while waiting for the low-priority thread to finish.
• The low-priority thread loops at the inner level, ensuring it only proceeds when the other thread has fully exited, including updating Last and retracting its intent.

Unbounded overtaking? allowed by the new low-priority thread.

Dekker has unbounded overtaking (not starvation)

because race loser retracts intent.

• $\Rightarrow$ thread exiting critical does not exclude itself for reentry.
  • T0 exits critical section and attempts reentry
  • T1 is now high priority (Last != me) but delays in low-priority busy-loop and resetting its intent.
  • T0 can enter critical section unbounded times until T1 resets its intent
  • T1 sets intent $\Rightarrow$ bound of 1 as T0 can be entering or in critical section

Dekker's algorithm is W-safe and R-unsafe

the bits are scrambled during simultaneous assignment.

This fact is easy to see because the only assignment to the shared variable, Last, occurs in the exit protocol and the other thread cannot make progress out of the entry protocol until both assignments in the exit protocol are finished.

Dekker’s algorithm can be modified to be RW-safe:

• Last == &me is too rigid. So the waiting condition is weakened by replacing it with you == WantIn && Last == &me, where the new condition enables progress should the other thread not return.
• On exit, Last is not changed if a thread makes repeated entries, the assignment causes Last to flicker.