COMP2310 - Week 4 - Solutions to Critical Section Problem

Solutions

Dekker's Algorithm

• Task Q is identical with swapped variables

$Turn$ -> Allows right to insist on entering

task body P is
begin
    loop
    
    -- Non-critical section P

    Want_P := True;

    loop exit when Want_Q = False;
        if Turn = 2 then
            Want_P := False;
            await Turn = 1;
            Want_P := True;
    end loop;

    -- Critical section P

    Turn := 2;
    Want_P := False;
    end loop;
end P;

Satisfies

• Mutual exclusion
• No deadlock
• No starvation

Drawbacks

• Only works for two tasks

Bakery Algorithm

• Solves for $n$ critical regions

• $P_1 ... P_N$ competing to access critical regions. Each process $P_i$ supplies a globally readable number $t_i$ initialised to 0.

• ALl processes are equal and must coordinate, i.e. no controlling process

• Before a process $P_i$ enters a critical section:

  1. $P_i$ draws a new number $t_i > t_j; \forall j \ne i$
     • Take first number $t_i$, it reads all other tickets, find max ticket value and adds one.
  2. Check if $P_i$ is allowed to enter the critical section, iff: $\forall j \ne i : t_i < t_j \land t_j = 0$
  3. After a process $P_i$ leaves a critical section, the ticket number is reset, $t_i$ -> 0 (Set to 0)

Realistic Hardware Support

Atomic test-and-set operations

[L := C; C:= 1]

Atomic exchange operations

[Temp := L; L := C; C := Temp]

Memory cell reservations

$L$ $:=^R$ $C$ -> Read by using special instruction that puts reservation on $C$

then, calcualte new value for $C$

$C$ $:=^T$ $<new-value>$ for $C$ -> Succeeds iff $C$ was not manipulated by processors or devices since the reservation