Systems, Networks & Concurrency 2019
Mutual Exclusi2on Uwe R. Zimmer – The Australian National University
[Ben-Ari06]
M. Ben-Ari
Principles of Concurrent and Distributed Programming
2006, second edition, Prentice-Hall, ISBN 0-13-711821-X
Mutual Exclusion
References for this chapter
© 2019 Uwe R. Zimmer, The Australian National University page 203 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
must never be interleaved! • No deadlocks: If one or multiple processes try to enter their
• More required properties:
critical sections then exactly one of them must succeed.
• No starvation: Every process which tries to enter one of his critical sections must succeed eventually.
Mutual Exclusion
Problem specification
The general mutual exclusion scenario
• N processes execute (infinite) instruction sequences concurrently. Each instruction belongs to either a critical or non-critical section.
Safety property ‘Mutual exclusion’:
Instructions from critical sections of two or more processes
• Efficiency: The decision which process may enter the critical section must be made efficiently in all cases, i.e. also when there is no contention in the first place.
© 2019 Uwe R. Zimmer, The Australian National University page 204 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Problem specification
The general mutual exclusion scenario
• N processes execute (infinite) instruction sequences concurrently. Each instruction belongs to either a critical or non-critical section.
Safety property ‘Mutual exclusion’:
Instructions from critical sections of two or more processes
• Furtherassumptions:
must never be interleaved!
• Pre- and post-protocols can be executed before and after each critical section. • Processes may delay infinitely in non-critical sections.
• Processes do not delay infinitely in critical sections.
© 2019 Uwe R. Zimmer, The Australian National University page 205 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Atomic load & store operations
Atomic load & store operations
Assumption 1: every individual base memory cell (word) load and store access is atomic Assumption 2: there is no atomic combined load-store access
G : Natural := 0; — assumed to be mapped on a 1-word cell in memory
task body P1 is begin
task body P2 is begin
task body P3 is begin
G := 1
G := 2
G := 3
G := G + G; end P1;
G := G + G; end P2;
G := G + G; end P3;
What is the value of G?
© 2019 Uwe R. Zimmer, The Australian National University
page 206 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
task body P1 is begin
task body P2 is begin
task body P3 is begin
G := 1
G := 2
G := 3
G := G + G; end P1;
G := G + G; end P2;
G := G + G; end P3;
Mutual Exclusion
Mutual exclusion: Atomic load & store operations
Atomic load & store operations
Assumption 1: every individual base memory cell (word) load and store access is atomic Assumption 2: there is no atomic combined load-store access
G : Natural := 0; — assumed to be mapped on a 1-word cell in memory
After the first global initialisation, G can have almost any value between 0 and 24 After the first global initialisation, G will have exactly one value between 0 and 24
After all tasks terminated, G will have exactly one value between 2 and 24
© 2019 Uwe R. Zimmer, The Australian National University page 207 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
type Task_Token is mod 2; Turn: Task_Token := 0;
task body P0 is
task body P1 is
begin loop
begin loop
—— non_critical_section_0;
—— non_critical_section_1;
loop exit when Turn = 0; end loop; —— critical_section_0;
loop exit when Turn = 1; end loop; —— critical_section_1;
Turn := Turn + 1;
Turn := Turn + 1;
end loop; end P0;
end loop; end P1;
Mutual exclusion?
Deadlock?
Starvation?
Work without contention?
© 2019 Uwe R. Zimmer, The Australian National University
page 208 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: First attempt
type Task_Token is mod 2; Turn: Task_Token := 0;
task body P0 is
task body P1 is
begin loop
begin loop
—— non_critical_section_0;
—— non_critical_section_1;
loop exit when Turn = 0; end loop; —— critical_section_0;
loop exit when Turn = 1; end loop; —— critical_section_1;
Turn := Turn + 1;
Turn := Turn + 1;
end loop; end P0;
end loop; end P1;
Mutual exclusion!
No deadlock!
No starvation!
Locks up, if there is no contention!
© 2019 Uwe R. Zimmer, The Australian National University
page 209 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: First attempt
type Task_Token is mod 2; Turn: Task_Token := 0;
task body P0 is
task body P1 is
begin loop
begin loop
—— non_critical_section_0; loop exit when Turn = 0; end loop;
—— non_critical_section_1; loop exit when Turn = 1; end loop;
—— critical_section_0; Turn := Turn + 1;
—— critical_section_1; Turn := Turn + 1;
end loop; end P0;
end loop; end P1;
Mutual exclusion! No deadlock!
No starvation!
Inefficient!
scatter:
© 2019 Uwe R. Zimmer, The Australian National University
page 210 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: First attempt
if Turn = myTurn then Turn := Turn + 1;
end if
into the non-critical sections
type Critical_Section_State is (In_CS, Out_CS); C1, C2: Critical_Section_State := Out_CS;
task body P1 is
task body P2 is
begin loop
begin loop
—— non_critical_section_1;
—— non_critical_section_2;
loop
exit when C2 = Out_CS;
loop
exit when C1 = Out_CS;
end loop;
C1 := In_CS;
end loop;
C2 := In_CS;
—— critical_section_1;
C1 := Out_CS;
—— critical_section_2;
C2 := Out_CS;
end loop; end P1;
end loop; end P2;
Any better?
© 2019 Uwe R. Zimmer, The Australian National University
page 211 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Second attempt
type Critical_Section_State is (In_CS, Out_CS); C1, C2: Critical_Section_State := Out_CS;
task body P1 is
task body P2 is
begin loop
begin loop
—— non_critical_section_1;
—— non_critical_section_2;
loop
exit when C2 = Out_CS;
loop
exit when C1 = Out_CS;
end loop;
C1 := In_CS;
end loop;
C2 := In_CS;
—— critical_section_1;
C1 := Out_CS;
—— critical_section_2;
C2 := Out_CS;
end loop; end P1;
end loop; end P2;
No mutual exclusion!
© 2019 Uwe R. Zimmer, The Australian National University
page 212 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Second attempt
type Critical_Section_State is (In_CS, Out_CS); C1, C2: Critical_Section_State := Out_CS;
task body P1 is
task body P2 is
begin loop
begin loop
—— non_critical_section_1;
—— non_critical_section_2;
C1 := In_CS;
C2 := In_CS;
loop
exit when C2 = Out_CS;
loop
exit when C1 = Out_CS;
end loop;
—— critical_section_1;
end loop;
—— critical_section_2;
C1 := Out_CS;
C2 := Out_CS;
end loop; end P1;
end loop; end P2;
Any better?
© 2019 Uwe R. Zimmer, The Australian National University
page 213 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Third attempt
type Critical_Section_State is (In_CS, Out_CS); C1, C2: Critical_Section_State := Out_CS;
task body P1 is
task body P2 is
begin loop
begin loop
—— non_critical_section_1;
—— non_critical_section_2;
C1 := In_CS;
C2 := In_CS;
loop
exit when C2 = Out_CS;
loop
exit when C1 = Out_CS;
end loop;
—— critical_section_1;
end loop;
—— critical_section_2;
C1 := Out_CS;
C2 := Out_CS;
end loop; end P1;
end loop; end P2;
Mutual exclusion!
Potential deadlock!
© 2019 Uwe R. Zimmer, The Australian National University
page 214 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Third attempt
task body P1 is
task body P2 is
begin loop
begin loop
—— non_critical_section_1;
—— non_critical_section_2;
C1 := In_CS;
C2 := In_CS;
loop
exit when C2 = Out_CS;
C1 := Out_CS; C1 := In_CS;
loop
exit when C1 = Out_CS;
C2 := Out_CS; C2 := In_CS;
end loop;
—— critical_section_1;
end loop;
—— critical_section_2;
C1 := Out_CS;
C2 := Out_CS;
end loop; end P1;
end loop; end P2;
Making any progress?
© 2019 Uwe R. Zimmer, The Australian National University
page 215 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Forth attempt
type Critical_Section_State is (In_CS, Out_CS); C1, C2: Critical_Section_State := Out_CS;
task body P1 is
task body P2 is
begin loop
begin loop
—— non_critical_section_1;
—— non_critical_section_2;
C1 := In_CS;
C2 := In_CS;
loop
exit when C2 = Out_CS;
C1 := Out_CS; C1 := In_CS;
loop
exit when C1 = Out_CS;
C2 := Out_CS; C2 := In_CS;
end loop;
—— critical_section_1;
end loop;
—— critical_section_2;
C1 := Out_CS;
C2 := Out_CS;
end loop; end P1;
end loop; end P2;
Mutual exclusion! No Deadlock!
Mutual Exclusion
Mutual exclusion: Forth attempt
type Critical_Section_State is (In_CS, Out_CS); C1, C2: Critical_Section_State := Out_CS;
Potential starvation! Potential global livelock!
© 2019 Uwe R. Zimmer, The Australian National University page 216 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
task body One_Of_Two_Tasks is other_Task : Task_Range
CSS (other_Task) = Out_CS; if Turn = other_Task then
:= this_Task + 1;
—— non_critical_section
loop
exit when Turn = this_Task;
begin
end loop;
© 2019 Uwe R. Zimmer, The Australian National University
end One_Of_Two_Tasks;
page 217 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Decker’s Algorithm
type Task_Range is mod 2;
type Critical_Section_State is (In_CS, Out_CS);
CSS : array (Task_Range) of Critical_Section_State := (others => Out_CS); Turn : Task_Range := Task_Range’First;
task type One_Of_Two_Tasks
(this_Task : Task_Range);
loop
exit when
CSS (this_Task) := In_CS;
CSS (this_Task) := Out_CS;
CSS (this_Task) := In_CS; end if;
end loop;
—— critical section CSS (this_Task) := Out_CS; Turn := other_Task;
Mutual exclusion! No starvation! No deadlock! No livelock!
Two tasks only!
task body One_Of_Two_Tasks is other_Task : Task_Range
CSS (other_Task) = Out_CS; if Turn = other_Task then
:= this_Task + 1;
—— non_critical_section
loop
exit when Turn = this_Task;
begin
end loop;
© 2019 Uwe R. Zimmer, The Australian National University
end One_Of_Two_Tasks;
page 218 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Decker’s Algorithm
type Task_Range is mod 2;
type Critical_Section_State is (In_CS, Out_CS);
CSS : array (Task_Range) of Critical_Section_State := (others => Out_CS); Turn : Task_Range := Task_Range’First;
task type One_Of_Two_Tasks
(this_Task : Task_Range);
loop
exit when
CSS (this_Task) := In_CS;
CSS (this_Task) := Out_CS;
CSS (this_Task) := In_CS; end if;
end loop;
—— critical section CSS (this_Task) := Out_CS; Turn := other_Task;
type Task_Range is mod 2;
type Critical_Section_State is (In_CS, Out_CS);
task body One_Of_Two_Tasks is other_Task : Task_Range
CSS (this_Task) := In_CS; Last := this_Task;
loop
:= this_Task + 1;
—— non_critical_section
exit when
begin
CSS (other_Task) = Out_CS
or else Last /= this_Task;
© 2019 Uwe R. Zimmer, The Australian National University
end One_Of_Two_Tasks;
page 219 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Peterson’s Algorithm
CSS : array (Task_Range) of Critical_Section_State := (others => Out_CS); Last : Task_Range := Task_Range’First;
task type One_Of_Two_Tasks
(this_Task : Task_Range);
end loop;
—— critical section CSS (this_Task) := Out_CS;
Mutual exclusion! No starvation! No deadlock! No livelock!
Two tasks only!
type Task_Range is mod 2;
type Critical_Section_State is (In_CS, Out_CS);
task body One_Of_Two_Tasks is other_Task : Task_Range
CSS (this_Task) := In_CS; Last := this_Task;
loop
:= this_Task + 1;
—— non_critical_section
exit when
begin
CSS (other_Task) = Out_CS
or else Last /= this_Task;
© 2019 Uwe R. Zimmer, The Australian National University
end One_Of_Two_Tasks;
page 220 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Peterson’s Algorithm
CSS : array (Task_Range) of Critical_Section_State := (others => Out_CS); Last : Task_Range := Task_Range’First;
task type One_Of_Two_Tasks
(this_Task : Task_Range);
end loop;
—— critical section CSS (this_Task) := Out_CS;
must never be interleaved!
• No deadlocks: If one or multiple processes try to enter their critic-
• More required properties:
al sections then exactly one of them must succeed.
• No starvation: Every process which tries to enter one of his critical sections must succeed eventually.
Mutual Exclusion
Problem specification
The general mutual exclusion scenario
• N processes execute (infinite) instruction sequences concurrently. Each instruction belongs to either a critical or non-critical section.
Safety property ‘Mutual exclusion’:
Instructions from critical sections of two or more processes
• Efficiency: The decision which process may enter the critical section must be made efficiently in all cases, i.e. also when there is no contention.
© 2019 Uwe R. Zimmer, The Australian National University page 221 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
• Before a process Pi enters a critical section:
• Pi draws a new number ti > tj ; 6j ! i
• Pi is allowed to enter the critical section iff: 6j ! i : ti < tj or tj = 0
• After a process left a critical section: • Pi resets its ti = 0
Mutual Exclusion
Mutual exclusion: Bakery Algorithm
The idea of the Bakery Algorithm
A set of N Processes P1 fPN competing for mutually exclusive execution of their critical regions. Every process Pi out of P1 fPN supplies: a globally readable number ti (‘ticket’) (initialized to ‘0’).
Issues:
Can you ensure that processes won’t read each others ticket numbers while still calculating?
Can you ensure that no two processes draw the same number?
© 2019 Uwe R. Zimmer, The Australian National University page 222 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
No_Of_Tasks : constant Positive := ...; type Task_Range is mod No_Of_Tasks;
Choosing : array (Task_Range) of Boolean := (others => False); Ticket : array (Task_Range) of Natural := (others => 0);
task type P (this_id: Task_Range);
loop
exit when
task body P is begin
Ticket (id) = 0
loop
or else
—— non_critcal_section_1;
Ticket (this_id) < Ticket (id)
Choosing (this_id) := True;
Ticket (this_id) := Max (Ticket) + 1;
Choosing (this_id) := False;
(Ticket (this_id) = Ticket (id) and then this_id < id);
for id in Task_Range loop if id /= this_id then
end loop; end if;
loop
exit when not Choosing (id);
end loop;
------ critical_section_1; Ticket (this_id) := 0;
end loop;
© 2019 Uwe R. Zimmer, The Australian National University
end loop; end P;
Mutual Exclusion
Mutual exclusion: Bakery Algorithm
or else
page 223 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual exclusion! No deadlock!
No starvation!
No livelock!
Works for N processes!
Extensive and communication intensive protocol
(even if there is no contention)
No_Of_Tasks : constant Positive := ...; type Task_Range is mod No_Of_Tasks;
Choosing : array (Task_Range) of Boolean := (others => False); Ticket : array (Task_Range) of Natural := (others => 0);
task type P (this_id: Task_Range);
loop
exit when
task body P is begin
Ticket (id) = 0 or else
loop
Ticket (this_id) < Ticket (id)
------ non_critcal_section_1;
or else
(Ticket (this_id) = Ticket (id)
Choosing (this_id) := True;
Ticket (this_id) := Max (Ticket) + 1; Choosing (this_id) := False;
and then this_id < id); end loop;
for id in Task_Range loop if id /= this_id then
end if;
end loop;
------ critical_section_1; Ticket (this_id) := 0;
loop
exit when not Choosing (id);
end loop; end P;
end loop;
© 2019 Uwe R. Zimmer, The Australian National University
page 224 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: Bakery Algorithm
Atomic test-and-set operations: • [L := C; C := 1]
Atomic exchange operations: • [Temp := L; L := C; C := Temp]
Mutual Exclusion
Beyond atomic memory access
Realistic hardware support
Memory cell reservations:
• L : =R C; – read by using a special instruction, which puts a ‘reservation’ on C
• ... calculate a
• C :=T
– succeeds iff C was not manipulated by other processors or devices since the reservation
© 2019 Uwe R. Zimmer, The Australian National University page 225 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
type Flag is Natural range 0..1; C : Flag := 0;
task body Pi is
task body Pj is
L : Flag;
L : Flag;
begin loop
begin loop
loop
loop
[L := C; C := 1]; exit when L = 0; —— change process
[L := C; C := 1]; exit when L = 0; —— change process
end loop;
—— critical_section_i; C := 0;
end loop;
—— critical_section_j; C := 0;
end loop; end Pi;
end loop; end Pj;
Does that work?
© 2019 Uwe R. Zimmer, The Australian National University
page 226 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: atomic test-and-set operation
task body Pi is
task body Pj is
L : Flag;
L : Flag;
begin loop
begin loop
loop
loop
[L := C; C := 1]; exit when L = 0; —— change process
[L := C; C := 1]; exit when L = 0; —— change process
end loop;
—— critical_section_i; C := 0;
end loop;
—— critical_section_j; C := 0;
end loop; end Pi;
end loop; end Pj;
Mutual exclusion!, No deadlock!, No global live-lock! Works for any dynamic number of processes.
Individual starvation possible! Busy waiting loops! © 2019 Uwe R. Zimmer, The Australian National University
page 227 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: atomic test-and-set operation
type Flag is Natural range 0..1; C : Flag := 0;
type Flag is Natural range 0..1; C : Flag := 0;
task body Pi is
task body Pj is
L : Flag := 1;
L : Flag := 1;
begin loop
begin loop
loop
loop
[Temp := L; L := C; C := Temp]; exit when L = 0;
—— change process
[Temp := L; L := C; C := Temp]; exit when L = 0;
—— change process
end loop;
—— critical_section_i; L := 1; C := 0;
end loop;
—— critical_section_j; L := 1; C := 0;
end loop; end Pi;
end loop; end Pj;
Does that work?
© 2019 Uwe R. Zimmer, The Australian National University
page 228 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: atomic exchange operation
task body Pi is
task body Pj is
L : Flag := 1;
L : Flag := 1;
begin loop
begin loop
loop
loop
[Temp := L; L := C; C := Temp]; exit when L = 0;
—— change process
[Temp := L; L := C; C := Temp]; exit when L = 0;
—— change process
end loop;
—— critical_section_i; L := 1; C := 0;
end loop;
—— critical_section_j; L := 1; C := 0;
end loop; end Pi;
end loop; end Pj;
Mutual exclusion!, No deadlock!, No global live-lock! Works for any dynamic number of processes.
Individual starvation possible! Busy waiting loops! © 2019 Uwe R. Zimmer, The Australian National University
page 229 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: atomic exchange operation
type Flag is Natural range 0..1; C : Flag := 0;
task body Pi is
task body Pj is
L : Flag;
L : Flag;
begin loop
begin loop
loop
loop
L :=R C; C :=T
exit when Untouched and L = 0; —— change process
L :=R C; C :=T 1;
exit when Untouched and L = 0; —— change process
end loop;
—— critical_section_i; C := 0;
end loop;
—— critical_section_j; C := 0;
end loop; end Pi;
end loop; end Pj;
Does that work?
© 2019 Uwe R. Zimmer, The Australian National University
page 230 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
1;
Mutual Exclusion
Mutual exclusion: memory cell reservation
type Flag is Natural range 0..1; C : Flag := 0;
Any context switch needs to clear reservations
task body Pi is
task body Pj is
L : Flag;
L : Flag;
begin loop
begin loop
loop
loop
L:=RC;C:=T 1;
exit when Untouched and L = 0; —— change process
L:=RC;C:=T 1;
exit when Untouched and L = 0; —— change process
end loop;
—— critical_section_i; C := 0;
end loop;
—— critical_section_j; C := 0;
end loop; end Pi;
end loop; end Pj;
Mutual exclusion!, No deadlock!, No global live-lock! Works for any dynamic number of processes.
Individual starvation possible! Busy waiting loops! © 2019 Uwe R. Zimmer, The Australian National University
page 231 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Mutual exclusion: memory cell reservation
type Flag is Natural range 0..1; C : Flag := 0;
Count : Integer := 0;
task body Enter is
task body Leave is
begin
for i := 1 .. 100 loop
begin
for i := 1 .. 100 loop
Count := Count + 1; end loop;
Count := Count – 1; end loop;
end Enter;
end Leave;
Mutual Exclusion
Mutual exclusion … or the lack thereof
What is the value of Count after both programs complete?
© 2019 Uwe R. Zimmer, The Australian National University page 232 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Negotiate who goes first
Critical section
Indicate critical section completed
Critical section
Count: .word 0x00000000 ldr r4, =Count
ldr r4, =Count mov r1, #1
mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
ldr r2, [r4] add r2, #1 str r2, [r4]
ldr r2, [r4] sub r2, #1 str r2, [r4]
add r1, #1
add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 233 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Critical section
Critical section
Count: .word 0x00000000
Lock:
.word 0x00000000 ; #0 means unlocked
ldr r3, =Lock ldr r4, =Count mov r1, #1
ldr r3, =Lock ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
fail_enter:
fail_leave:
ldr r0, [r3]
cbnz r0, fail_enter ; if locked
ldr r0, [r3]
cbnz r0, fail_leave ; if locked
ldr r2, [r4] add r2, #1 str r2, [r4]
ldr r2, [r4] sub r2, #1 str r2, [r4]
add r1, #1
add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 234 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Critical section
Critical section
Count: .word 0x00000000
Lock:
.word 0x00000000 ; #0 means unlocked
ldr r3, =Lock ldr r4, =Count mov r1, #1
ldr r3, =Lock ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
fail_enter:
fail_leave:
ldr r0, [r3]
cbnz r0, fail_enter ; if locked
ldr r0, [r3]
cbnz r0, fail_leave ; if locked
mov r0, #1 str r0, [r3]
; lock value
; lock
mov r0, #1 str r0, [r3]
; lock value
; lock
ldr r2, [r4] add r2, #1 str r2, [r4]
ldr r2, [r4] sub r2, #1 str r2, [r4]
add r1, #1
add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 235 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Any context switch needs to clear reservations
Critical section
Critical section
Count: .word 0x00000000
Lock:
.word 0x00000000 ; #0 means unlocked
ldr r3, =Lock ldr r4, =Count mov r1, #1
ldr r3, =Lock ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
fail_enter:
fail_leave:
ldrex r0, [r3]
cbnz r0, fail_leave ; if locked mov r0, #1 ; lock value strex r0, [r3] ; try lock cbnz r0, fail_leave ; if touched dmb ; sync memory
ldrex r0, [r3]
cbnz r0, fail_enter ; if locked mov r0, #1 ; lock value strex r0, [r3] ; try lock cbnz r0, fail_enter ; if touched dmb ; sync memory
ldr r2, [r4] add r2, #1 str r2, [r4]
ldr r2, [r4] sub r2, #1 str r2, [r4]
add r1, #1
add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 236 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Any context switch needs to clear reservations
Critical section
Critical section
Count: .word 0x00000000
Lock:
.word 0x00000000 ; #0 means unlocked
ldr r3, =Lock ldr r4, =Count mov r1, #1
ldr r3, =Lock ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
fail_enter:
fail_leave:
ldrex r0, [r3]
cbnz r0, fail_leave ; if locked mov r0, #1 ; lock value strex r0, [r3] ; try lock cbnz r0, fail_leave ; if touched
ldrex r0, [r3]
cbnz r0, fail_enter ; if locked mov r0, #1 ; lock value strex r0, [r3] ; try lock cbnz r0, fail_enter ; if touched
dmb
; sync memory
dmb
; sync memory
ldr r2, [r4] add r2, #1 str r2, [r4]
ldr r2, [r4] sub r2, #1 str r2, [r4]
dmb
mov r0, #0 str r0, [r3]
; sync memory
; unlock value
; unlock
dmb
mov r0, #0 str r0, [r3]
; sync memory
; unlock value
; unlock
add r1, #1
add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 237 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Any context switch needs to clear reservations
Asks for permission
Critical section
Critical section
Count: .word 0x00000000
Lock:
.word 0x00000000 ; #0 means unlocked
ldr r3, =Lock ldr r4, =Count mov r1, #1
ldr r3, =Lock ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
fail_enter:
fail_leave:
ldrex r0, [r3]
cbnz r0, fail_leave ; if locked mov r0, #1 ; lock value strex r0, [r3] ; try lock cbnz r0, fail_leave ; if touched
ldrex r0, [r3]
cbnz r0, fail_enter ; if locked mov r0, #1 ; lock value strex r0, [r3] ; try lock cbnz r0, fail_enter ; if touched
dmb
; sync memory
dmb
; sync memory
ldr r2, [r4] add r2, #1 str r2, [r4]
ldr r2, [r4] sub r2, #1 str r2, [r4]
dmb
mov r0, #0 str r0, [r3]
; sync memory
; unlock value
; unlock
dmb
mov r0, #0 str r0, [r3]
; sync memory
; unlock value
; unlock
add r1, #1
add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 238 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Any context switch needs to clear reservations
Asks for forgiveness
Count: .word 0x00000000
ldr r4, =Count
ldr r4, =Count
mov r1, #1
mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_leave
cmp r1, #100
bgt end_for_enter
enter_strex_fail:
leave_strex_fail:
ldrex r2, [r4] ; tag [r4] as exclusive add r2, #1
strex r2, [r4] ; only if untouched
ldrex r2, [r4] ; tag [r4] as exclusive sub r2, #1
strex r2, [r4] ; only if untouched
cbnz r2, enter_strex_fail add r1, #1
cbnz r2, leave_strex_fail add r1, #1
b for_enter end_for_enter:
b for_leave end_for_leave:
Mutual Exclusion
Mutual exclusion
Light weight solution – sometimes referred to as “lock-free” or “lockless”.
© 2019 Uwe R. Zimmer, The Australian National University page 239 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
• a set of processes agree on a variable S operating as a flag to indicate synchronization conditions
Mutual Exclusion
Beyond atomic hardware operations
Semaphores
Basic definition (Dijkstra 1968)
Assuming the following three conditions on a shared memory cell between processes:
• an atomic operation P on S — for ‘passeren’ (Dutch for ‘pass’):
P(S): [as soon as S > 0 then S := S – 1] this is a potentially delaying operation
• an atomic operation V on S — for ‘vrygeven’ (Dutch for ‘to release’): V(S):[S := S + 1]
then the variable S is called a Semaphore.
© 2019 Uwe R. Zimmer, The Australian National University page 240 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
• an atomic operation Wait on S: (aka ‘Suspend_Until_True’, ‘sem_wait’, …)
Process Pi : Wait (S):
• an atomic operation Signal on S: (aka ‘Set_True’, ‘sem_post’, …)
Process Pi : Signal (S):
[if 7Pj suspended on S then release Pj else S := S + 1]
Mutual Exclusion
Beyond atomic hardware operations
Semaphores
… as supplied by operating systems and runtime environments
• a set of processes P1 fPN agree on a variable S operating as a flag to indicate synchronization conditions
[if S > 0 then S := S – 1
else suspend Pi on S]
then the variable S is called a Semaphore in a scheduling environment.
© 2019 Uwe R. Zimmer, The Australian National University page 241 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Types of semaphores:
• Binary semaphores: restricted to [0, 1] or [False, True] resp.
Mutual Exclusion
Beyond atomic hardware operations
Semaphores
Multiple V (Signal) calls have the same effect than a single call.
• Atomic hardware operations support binary semaphores.
• Binary semaphores are sufficient to create all other semaphore forms.
• General semaphores (counting semaphores): non-negative number; (range lim- ited by the system) P and V increment and decrement the semaphore by one.
• Quantity semaphores: The increment (and decrement) value for the semaphore is specified as a parameter with P and V.
All types of semaphores must be initialized:
often the number of processes which are allowed inside a critical section, i.e. ‘1’.
© 2019 Uwe R. Zimmer, The Australian National University page 242 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Critical section
Critical section
Count: .word 0x00000000
Sema:
.word 0x00000001
ldr r3, =Sema ldr r4, =Count mov r1, #1
ldr r3, =Sema ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
wait_1:
wait_2:
ldr r0, [r3]
cbz r0, wait_1 ; if Semaphore = 0
ldr r0, [r3]
cbz r0, wait_2 ; if Semaphore = 0
……
add r1, #1
add r1, #1
b for_enter
b for_leave
end_for_enter:
end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 243 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Critical section
Critical section
Count: .word 0x00000000
Sema:
.word 0x00000001
ldr r3, =Sema ldr r4, =Count mov r1, #1
ldr r3, =Sema ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
wait_1:
wait_2:
ldr r0, [r3]
cbz r0, wait_1 ; if Semaphore = 0 sub r0, #1 ; dec Semaphore str r0, [r3] ; update
ldr r0, [r3]
cbz r0, wait_2 ; if Semaphore = 0
……
add r1,#1
add r1, #1
b for_enter
b for_leave
end_for_enter:
end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 244 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
sub r0, #1 str r0, [r3]
; dec Semaphore
; update
Any context switch needs to clear reservations
Critical section
Critical section
Count: .word 0x00000000
Sema:
.word 0x00000001
ldr r3, =Sema ldr r4, =Count mov r1, #1
ldr r3, =Sema ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
wait_1:
wait_2:
ldrex r0, [r3]
cbz r0, wait_2 ; if Semaphore = 0 sub r0, #1 ; dec Semaphore strex r0, [r3] ; try update
cbnz r0, wait_2 ; if touched
dmb ; sync memory
ldrex r0, [r3]
cbz r0, wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r0, [r3] ; try update
cbnz r0, wait_1 ; if touched
dmb ; sync memory ……
add r1, #1
add r1, #1
b for_enter
b for_leave
end_for_enter:
end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 245 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Any context switch needs to clear reservations
Critical section
Critical section
Count: .word 0x00000000
Sema:
.word 0x00000001
ldr r3, =Sema ldr r4, =Count mov r1, #1
ldr r3, =Sema ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
wait_1:
wait_2:
ldrex r0, [r3]
cbz r0, wait_2 ; if Semaphore = 0 sub r0, #1 ; dec Semaphore strex r0, [r3] ; try update
cbnz r0, wait_2 ; if touched
ldrex r0, [r3]
cbz r0, wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r0, [r3] ; try update
cbnz r0, wait_1 ; if touched
dmb ; sync memory ……
; sync memory
ldr r0, [r3] add r0, #1 str r0, [r3]
; inc Semaphore
; update
ldr r0, [r3] add r0, #1 str r0, [r3]
; inc Semaphore
; update
add r1, #1
add r1, #1
b for_enter
b for_leave
end_for_enter:
end_for_leave:
© 2019 Uwe R. Zimmer, The Australian National University
page 246 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
dmb
Any context switch needs to clear reservations
Critical section
Critical section
Count: .word 0x00000000
Sema:
.word 0x00000001
ldr r3, =Sema ldr r4, =Count mov r1, #1
ldr r3, =Sema ldr r4, =Count mov r1, #1
for_enter:
for_leave:
cmp r1, #100
bgt end_for_enter
cmp r1, #100
bgt end_for_leave
wait_1:
wait_2:
ldrex r0, [r3]
cbz r0, wait_2 ; if Semaphore = 0 sub r0, #1 ; dec Semaphore strex r0, [r3] ; try update
cbnz r0, wait_2 ; if touched
ldrex r0, [r3]
cbz r0, wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r0, [r3] ; try update
cbnz r0, wait_1 ; if touched
dmb ; sync memory ……
; sync memory
signal_1:
signal_2:
ldrex r0, [r3]
add r0, #1
strex r0, [r3]
cbnz r0, signal_1 ; if touched
ldrex r0, [r3]
add r0, #1
strex r0, [r3]
cbnz r0, signal_2 ; if touched
dmb add b
; sync memory
dmb add b
; sync memory
end_for_enter:
end_for_leave:
r1, #1
r1, #1
for_enter
for_leave
© 2019 Uwe R. Zimmer, The Australian National University
page 247 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
; inc Semaphore
; try update
; inc Semaphore
; try update
dmb
S : Semaphore := 1;
task body Pi is begin
task body Pj is begin
loop
loop
—— non_critical_section_i;
—— non_critical_section_j;
wait (S);
wait (S);
—— critical_section_i;
—— critical_section_j;
signal (S);
signal (S);
end loop; end Pi;
end loop; end Pi;
Works?
© 2019 Uwe R. Zimmer, The Australian National University
page 248 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Semaphores
S : Semaphore := 1;
task body Pi is begin
task body Pj is begin
loop
loop
—— non_critical_section_i;
—— non_critical_section_j;
wait (S);
wait (S);
—— critical_section_i;
—— critical_section_j;
signal (S);
signal (S);
end loop; end Pi;
end loop; end Pi;
Mutual exclusion!, No deadlock!, No global live-lock! Works for any dynamic number of processes
Individual starvation possible!
© 2019 Uwe R. Zimmer, The Australian National University
page 249 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Semaphores
S1, S2 : Semaphore := 1;
task body Pi is begin
task body Pj is begin
loop
loop
—— non_critical_section_i;
—— non_critical_section_j;
wait (S1);
wait (S2);
wait (S2);
wait (S1);
—— critical_section_i;
—— critical_section_j;
signal (S2);
signal (S1);
signal (S1);
signal (S2);
end loop; end Pi;
end loop; end Pi;
Works too?
© 2019 Uwe R. Zimmer, The Australian National University
page 250 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Semaphores
S1, S2 : Semaphore := 1;
task body Pi is begin
task body Pj is begin
loop
loop
—— non_critical_section_i;
—— non_critical_section_j;
wait (S1);
wait (S2);
wait (S2);
wait (S1);
—— critical_section_i;
—— critical_section_j;
signal (S2);
signal (S1);
signal (S1);
signal (S2);
end loop; end Pi;
end loop; end Pi;
Mutual exclusion!, No global live-lock!
Works for any dynamic number of processes. Individual starvation possible!
Deadlock possible!
© 2019 Uwe R. Zimmer, The Australian National University
page 251 of 757 (chapter 2: “Mutual Exclusion” up to page 252)
Mutual Exclusion
Semaphores
• Definition of mutual exclusion
• Atomic load and atomic store operations
• … some classical errors
• Decker’s algorithm, Peterson’s algorithm
• Bakeryalgorithm
• Realistic hardware support
• Atomic test-and-set, Atomic exchanges, Memory cell reservations
• Semaphores
• Basic semaphore definition
• Operating systems style semaphores
Mutual Exclusion
Summary
Mutual Exclusion
© 2019 Uwe R. Zimmer, The Australian National University page 252 of 757 (chapter 2: “Mutual Exclusion” up to page 252)