Course Operating Systems

Lecture 5: Process/Thread Synchronization

Part A: Critical Section and Argumentation Structure
PartB: HW Primitives and Synchronization Objects

EDA093, DIT 401

Study Period 1
Ack: several figures in the slides are from the books
- Modern Operating Systems by A. Tanenbaum, H. Bos
- The art of multiprogramming, by M. Herlihy, Shavit
- OS Concepts by Silberschatz et-al
- Operating systems by W. Stallings

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 1

 Recall: OS’s job: help processes/threads* run

What do processes/threads need?

- get CPU to run
- create processes/threads
- collaborate/synchronize
- get memory to run
- do IO, access files
- ….
Our focus here;
in particular through shared-memory

(*) In this discussion we sometimes use the terms thread/process interchangeably

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 2

 Why synchronize?
Because collaboration implies possibilities and risks…

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 3

 … shared data access: possibilities but also risks…
shared var BALANCE: eg 20000 kr
Bank thread A Bank thread B
local var b
local var a

a ← BALANCE // read shared variable

a ← a + 5000 b ← BALANCE // read shared variable
BALANCE ← a // write shared variable b ← b – 2000
BALANCE ← b // write shared variable
t

Oooops!! BALANCE: 18000 kr!!!!

aka RACE CONDITION

Problem: need to ensure that each process/thread is executing its critical section (e.g
read&update BALANCE) exclusively/atomically (one process/thread at a time)

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 4

 Another similar example*
shared var MDFO (measured distance from obstacle) //eg here 20 m
parameter SafetyMargin // eg 15 m
sense/control thread A control/sensor thread B
local var a local var b

a ← MDFO // read shared

a ← min (a, 10) // calculation using sensor reading b ← MDFO // read shared
MDFO ← a // write shared b ← min (b, 30) // calculation using sensor reading
MDFO ← b // write shared

t if MDFO < SafetyMargin then [brake] if MDFO < SafetyMargin then [brake]

Oooops RACE CONDITION

MDFO is still 20 m, no brake activated ……

Problem: need to ensure that each thread is executing its critical section (e.g
read&update MDFO) exclusively /atomically
(*) Oversimplified example, to get a feeling of context

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 5

 Yet another similar example*
Shared var SMAF (some measure of air flow): eg here 20
Parameter MaxAllowedFlow eg set to 25

Sense/control thread A Sense/control thread B

a ← SMAF // read shared
a ← max (a, 30) // calculation using sensor reading b ← SMAF // read shared
SMAF ← a // write shared b ← max (b, 10) // calculation using sensor reading
SMAF ← b // write shared

if SMAF > MaxAllowedFlow then [change flaps’ orientation] if SMAF > MaxAllowedFlow then [change flaps’ orientation]
t
Oooops RACE CONDITION
SMAF is still 20, no flaps changed orientation ……

Problem: need to ensure that each thread is executing its critical section (e.g
read&update SMAF) exclusively /atomically

(*) Oversimplified example, to get a feeling of context

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 6

 Questions

Do we need to be able to find such risks?

Do we need to argue about correctness when we propose solutions to
such problems?

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 7

 Roadmap PartA

• The critical-section (CS) problem

• CS for 2 threads using Read/Write memory-access primitives

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 8

 The Critical-Section (aka Critical Region) Problem
Structure of process/thread P
• n processes/threads competing Repeat
• Each of them has a code segment, called critical section, in entry section (to achieve “lock” effect)
which e.g. shared data is accessed. critical section
• Assumption (for this discussion): no process failures exit section (to achieve “unlock”)
remainder section
Forever

Problem formulation:
A solution must provide the entry and exit sections
It must ensure:
1. Mutual Exclusion. Only one process/thread at a time is allowed to
execute in its critical section.
2. Progress (no deadlock/no livelock). If no process/thread is in its critical
section and some is/are trying, some must enter its critical section in
bounded time.
3. Fairness / Bounded Waiting / no starvation. Variety of formulations, eg
– FCFS; or bounded #bypasses, …

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 9

 Critical section: desirable behaviour
A enters or
irrevocably decides to enter
critical region

/thread

B waits
/thread

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 10

 Roadmap Part A

• The critical-section (CS) problem

i.e thread A, B which may share R/W
variables (can be read or written
• CS for 2 threads using Read/Write memory-access primitives atomically) need to synchronize
– Let’s start with simple approaches actions to solve the CS problem

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 11

 Let’s think together: (ie instead of )
(1): “check-competition” approach
Shared var flagA, flagB: boolean;
// indicate A’s, B’s intention to enter; initially both false
Thread A // B is symmetric
repeat
Q: Does the “check-
while flagB == true do [nothing] //busywait competition” method solve the
flagA ← true CS problem?
[critical section] No, mutual exclusion can be
flagA ← false violated
[remainder section]
forever
Recall: a solution must ensure:
1. Mutual Exclusion: Only one thread at a time is allowed to execute in its critical section (CS)
2. Progress: If no thread is in its CS and some is/are trying, some process/thread must enter its CS in finite time.
3. Fairness / Bounded Waiting / no starvation: Eg FCFS; or bounded #bypasses

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 12

 “check-competition”: mutual exclusion property?
Can the algo violate the mutual exclusion requirement? Shared var flagA, flagB: boolean;
i.e. Can it happen that there is a point in time s.t. A and B concurrently in CS? //init both false
• Assume it can and w.l.o.g. consider the decision step by A (Dstep(A)) to enter CS: Thread A // B is symmetric
repeat
• A sees flag[B] == false => next step by A is Fstep (A); while flagB == true do [nothing] Dstep
• can Dstep(B) happen between Dstep(A) and Fstep(A) and lead B to a wrong decision? flagA ← true Fstep
• Yes…. [critical section]
flagA ← false
• i.e. we showed,using a counterexample that this algo can violate the mutual exclusion req. [remainder section]
Dstep(A) A sees Fstep(A) sets forever
flagB == false => flagA to true
A decides to enter CS

A in CS

Bin CS
Can Dstep(B) happen here
i.e. see flagA == false? Pstep(B) sets
YES=> B decides to enter CS flagB to true
Time
too, before A exits !!!

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 13

 Let’s think together: (ie instead of )
(2): “check-order” (after-you) approach
Shared var turn: (idA..idB) // initially eg idA
// indicates whose turn it is to enter CS
Thread A // B is symmetric
repeat
while turn ≠ idA do [nothing] //busywait Does the “check-order” method
[critical section] solve the CS problem?
turn ← idB No, progress is not guaranteed
[remainder section]
forever

Recall: a solution must ensure:

1. Mutual Exclusion: Only one thread at a time is allowed to execute in its critical section (CS)
2. Progress: If no thread is in its CS and some is/are trying, some process/thread must enter its CS in finite time.
3. Fairness / Bounded Waiting / no starvation. Eg FCFS; or bounded #bypasses, …

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 14

 “check-order”: mutual exclusion property?
Can the algo violate the mutual exclusion requirement?
Shared var turn: (A..B) // initially eg A
i.e. Can it happen that there is a point in time s.t. A and B concurrently in CS? // indicates whose turn it is to
enter CS
• Assume it can and w.l.o.g. consider the decision step by A (Dstep(A)) to enter CS:
Thread A // B is symmetric
• A sees turn == idA => A’s next step is a step (call it S) in its CS repeat
• can Dstep(B) happen between Dstep(A) and S and lead B to a wrong decision? while turn ≠ idA do [nothing] Dstep
[critical section]
• No, only A can set turn to idB and A makes no such step then, hence B must wait! turn ←idB
• i.e. we have reached a contradiction to the assumption that mutual exclusion is [remainder section]
violated; hence we proved that the algo guarantees the mutual exclusion requirement forever

Dstep(A) A sees turn

== idA => A decides Step S
to enter its CS
A in CS

B in CS
Can Dstep(B) happen here
i.e. see turn == idB ? Time
NO, only A can set turn to idB, i.e.
B must wait
[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 15
 “check-order”: progress property?
Can the algo violate the progress requirement?
Shared var turn: (A..B) // initially eg A
i.e. Can it happen that there is a case when no thread is in its CS and some is trying, and has // indicates whose turn it is to
to wait for unbounded time? enter CS
Thread A // B is symmetric
• Assume it can and w.l.o.g. consider B waiting in its while loop:
repeat
• B sees turn == idA => it needs to wait while turn ≠ idA do [nothing] Dstep
• Only A can set turn to idB [critical section]
turn ←idB
• if A is in its Remainder Section for unboubded time, B will wait for unbounded time [remainder section]
• i.e. we proved, using a counterexample that the algo can violate the progress requirement forever

A executes in its
remainder section
for unbounded time
.....

B in while loop, seeing turn == idA Can Dstep(B)

happen here i.e. see turn == idB ? Time
No, only A can set turn to idB, i.e. B must wait, for
unbounded time …
[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 16
 Roadmap Part A

• The critical-section (CS) problem

i.e thread A, B which may share R/W
variables (can be read or written
• CS for 2 threads using Read/Write memory-access primitives atomically) need to synchronize
– Simple approaches did not work actions to solve the CS problem

– What can we do better?

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 17

 Let’s think together: (ie instead of )
(3): “check-order&competition” approach
Shared var turn: (idA..idB) // initially e.g. idA
Shared var flagA, flagB: boolean // initially false
Does the “check-
thread A // B is symmetric order&competition” approach
repeat solve the problem?
flagA ← true
turn ← idB
while (flagB and turn == idB) do [nothing]
[critical section]
flagA← false
[remainder section]
forever
Recall: a solution must ensure:
1. Mutual Exclusion: Only one thread at a time is allowed to execute in its critical section (CS)
2. Progress: If no thread is in its CS and some is/are trying, some process/thread must enter its CS in finite time.
3. Fairness / Bounded Waiting / no starvation. Eg FCFS; or bounded #bypasses, …

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 18

 Peterson’s algo (= check order&competition):
Proof sketch/arguments
1. Can it violate mutual exclusion? Shared var turn: (idA..idB) // initially e.g. idA
Shared var flagA, flagB: boolean // initially false
Assume there is a point in time s.t. A and B concurrently in CS.
w.l.o.g. consider A’s decision step (Dstep(A)) before entering: thread A // B is symmetric
repeat
Case i: A sees flagB == false flagA ← true Fstep
turn ← idB Tstep
⇒ Dstep(A) -> Fstep(B) while (flagB and turn == idB) do [nothing] Dstep
(from algo) Fstep(B) -> Tstep(B) [critical section]
flagA← false Estep
=> B’s check will cause B to wait, contradicting assumption, ie this cannot happen [remainder section]
forever

Dstep(A) sees flag[B] == false,

A decides to enter its CS
in CS Time
-> , denote ”happened before

in CS
Fstep(B) sets Tstep(B) sets B’s check will see flagA == true
flagB to true turn to idA and turn == idA
Hence B must WAIT! 19 (But we are not done, we
have one more case…)

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 19

Peterson’s algo (= check order&competition):
Proof mutual exclusion (cont)
1. Can it violate mutual exclusion? (cont): Shared var turn: (idA..idB) // initially e.g. idA
Shared var flagA, flagB: boolean // initially false
Is there is a point in time s.t. A and B concurrently in CS?
Recall we assume it can and w.l.o.g. consider A’s Dstep before entering: thread A // B is symmetric
repeat
Case ii: Dstep(A) sees turn == A => flagA ← true Fstep
turn ← idB Tstep
Fstep(A) -> Tstep(A) -> Tstep(B) =>
while (flagB and turn == idB) do [nothing] Dstep
B’s check will fail , contradicting assumption <qed> [critical section]
flagA← false Estep
[remainder section]
forever

Dstep(A) sees
Tstep(A) turn == idA
sets turn to idB A decides to enter its CS

in CS
Fstep(A)
sets flagA to true Time
in CS

-> , denote Tstep(B) B’s check sees

”happened before flagA == true and turn == idA
sets turn to idA
hence B must WAIT!
[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 20
 Peterson’s algo (= check order&competition):
Proof progress
2. Can it violate progress?: Is there is a case s.t. no thread in CS and A and/or B
need to wait unbounded time?
Shared var turn: (idA..idB) // initially e.g. idA
Shared var flagA, flagB: boolean // initially false
Assuming there is, wlog consider B’s waiting loop: thread A // B is symmetric
we can reach the conclusion that this is impossible to wait without A being in CS, repeat
with the key-argument that Flag(A)->Tstep(A)->Tstep(B) => A can go in CS flagA ← true Fstep
turn ← idB Tstep
(Homework: complete the figure and the slightly more detailed argumentation as while (flagB and turn == idB) do [nothing] Dstep
[critical section]
we did with the previous slides) flagA← false Estep
[remainder section]
forever

A not in CS throughout the time

Time

B in while loop: can it see turn == idA and flagA == true

for unbounded time if no thread is in CS?

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 21

 Peterson’s algo (= check order&competition):
Proof fairness (bounded waiting)
Shared var turn: (idA..idB) // initially e.g. idA
3. Can it violate fairness? : Is there is a case s.t. one thread needs to wait while the Shared var flagA, flagB: boolean // initially false
other enters CS unbounded many times?
thread A // B is symmetric
Assuming there is, wlog consider B waiting in the while loop, seeing turn == idA and repeat
flagA == true unbounded times and A enetring CS more than once ….. flagA ← true Fstep
turn ← idB Tstep
Key argument: If B waits for A, upon A re-requesting, A sets turn to idB, hence A will while (flagB and turn == idB) do [nothing] Dstep
wait for B to go ahead => B can be bypassed at most once by A. [critical section]
flagA← false Estep
(Homework: complement the argumentation with more detail as we did with the [remainder section]
previous slides) forever
A will see FlagB == true
Fstep(A) Tstep(A) sets and turn == idB
Estep(A) turn to idB hence it must WAIT

in CS in CS

Time

B in while loop: can it see turn == idA and flagA == true

Fstep(B) sets
for unbounded time and A entering CS many times?
flagB to true

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 22

 Peterson’s algo (check order&competition):
Summary of correctness arguments
Shared var turn: (idA..idB) // initially e.g. idA
1. Mutual exclusion: by way of contradiction Shared var flagA, flagB: boolean // initially false
Assume, towards contradiction: A, B concurrently in CS thread A // B is symmetric
w.l.o.g. consider A’s Dstep before entering: repeat
flagA ← true Fstep
– Case i: A sees flag[B] == false => turn ← idB Tstep
while (flagB and turn == idB) do [nothing] Dstep
Dstep(A) -> Fstep(B) -> Tstep(B) =>
[critical section]
B’s check will fail, contradicting assumption <qed> flagA← false Estep
– Case ii: A sees turn == A => [remainder section]
forever
Fstep(A) -> Tstep(A) -> Tstep(B) =>
B’s check will fail , contradicting assumption <qed>
-> means ”happened before

2. Progress: not possible for any of threads A and B to wait forever

Key-argument: not possible since either (i) the other thread is not competing or (ii) turn variable will resolve the tie

3. Bounded waiting:
Key argument: wlog: If A waits for B, upon B re-requesting, B sets turn to A, hence B will wait for A to go ahead => A
can be bypassed at most once by B.

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 23

 On counterexamples & proofs by way of contradiction:

• This way of thinking and arguing, when we are presented with a solution to a synchronization
problem/race-condition (ie try to “attack” it, try to find if it does not work), is practical and useful (and
thus very common)
• It is very frequently used when arguing about correctness/incorrectness of proposed solutions. This way
of arguing helps us to:

(i) give a proof by contradiction that a proposition in focus is _correct_, e.g. that mutual exclusion is
preserved;
– see about proofs by way of contradiction @ eg http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-
assignments/Contradiction-Proofs.pdf p 1-4 or
http://web.stanford.edu/class/archive/cs/cs103/cs103.1152/lectures/02/Small02.pdf p 45-47
(ii) OR identify a counter-example, which implies that the proposition in focus is _incorrect_ (i.e. it
_disproves_ the proposition)
– see also https://mathforlove.com/lesson/counterexamples/ and/or https://study.com/academy/lesson/counterexample-in-
math-definition-examples.html and/or http://web.stanford.edu/class/archive/cs/cs103/cs103.1152/lectures/02/Small02.pdf

study these links if you are not familiar

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 24

 Summary Part A
• Critical Section problem; arguing about solutions and no-solutions
– focused on 2 threads, using only R/W shared variables
– @home: work with the homework questions on the slides + study/practice arguing for
correctness by way of contradictions (or for mistakes by finding a counter example)
Next topic(s) in the 3-lecture part on Synchronization, Resource allocation and Deadlocks: in-depth on
critical sections and related problems
– n-thread CS
• Using stronger hardware support than just R/W variables; 1 vs many CPUs/cores
• Synchronization objects: semaphores
• Discussion on busy-waiting
– Common synchronization problems
• Bounded buffer (producer-consumer)
• Dinning philosophers: resource-allocation (here we will focus also on deadlock-prevention)
• Narrow Bridge (+ Lab 2-3)
– More on synchronization methodology
• Lamport’s bakery algo + Turing award 2013 topic
• Readers/writers and a touch on lock-free synchronization
• Example synchronization objects by common OS

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 25

 Roadmap Part B
Part A was about:
• The critical-section (CS) problem
• CS for 2 threads using Read/Write memory-access primitives
– Examples attempts that do not solve the problem
– Peterson’s algorithm
– Argumentation structure (proof by way of contradiction, disproof by counterexample)

Now:
• Help from other hardware synchronization primitives; n-thread CS

• Semaphores

• Other synchronization objects

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 26

 Critical section through hardware support (1):
interrupt disabling
Recall: a process/kernel-thread runs until it invokes an operating-system service or until it is
interrupted/preempted
• i.e. interrupt-disabling disallows interleaving and can guarantee uninterrupted execution of a critical
section, ie,

Interrupt_disable
[critical section]
Interrupt_enable

Is there a down side?!

• If run in sinlge-processor system: limited ability to interleave programs
• In multiprocessors: disabling interrupts on one processor/core will not guarantee absence of race
conditions by threads running on other processors/cores

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 27

 Critical section through Hardware Support (2):
Read-modify-write (RMW) instructions
Reading and writing of a memory location together as one
atomic step (not subject to interference from other instructions)
e.g. TestAndSet, FetchAndAdd, CompareAndSwap,
LoadLinked/StoreConditional , …

i.e. not only simple atomic

reads and writes as underlying
communication primitives….
How can this help?

fig: http://preshing.com/20120612/an-
introduction-to-lock-free-programming/

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 28

 Critical Section through Hardware Support (2-cont):
RMW instructions
TestAndSet (aka TAS) Instruction Definition:
boolean TestAndSet (boolean *target){
boolean rv = *target;
*target := true;
return rv} // Executed atomically by the HW

Shared Boolean var lock; initialized to false

repeat
while(TestAndSet(&lock)) do [nothing];
[critical section] TAS
TAS variable
lock := false; Variable
Is set
[remainder section]
forever

Simple, right?
Homework training: argue as we did for Peterson’s algo regarding correctness (mutual exclusion, progress) ;
what about fairness???

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 29

 Critical Section through Hardware Support (2-cont):
RMW instructions
TestAndSet (aka TAS) Instruction Definition: CompareAndSwap (aka CAS) Instruction Definition:
boolean TestAndSet (boolean *target){ int CompareAndSwap(int *V, int expected, int
boolean rv = *target; new_value) {
*target := true; int temp := *V;
return rv} // Executed atomically by the HW if (temp == expected) then *V := new_value;
return temp} // Executed atomically by the HW
Shared Boolean var lock; initialized to false
repeat Shared int var lock; initialized to 0;
while(TestAndSet(&lock)) do [nothing];
repeat{
[critical section]
while CompareAndSwap(&lock,0,1)!=0) do nothing;
lock := false;
[critical section]
[remainder section]
lock := 0 ;
forever
[remainder section]
forever
Simple, right?
Homework training: argue as we did for Peterson’s algo regarding correctness (mutual exclusion, progress) ;
what about fairness???

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 30

 Read-modify-write (RMW) instructions: parenthesis

Parenthesis: How can the hardware execute such operations atomically?

• in a uniprocessor they are executed without interrupt;
• in multiprocessors they are executed with e.g. locked system bus
(ie critical section on hardware level)

fig: http://preshing.com/20120612/an-
introduction-to-lock-free-programming/

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 31

 Roadmap Part B
Part A was about:
• The critical-section (CS) problem
• CS for 2 threads using Read/Write memory-access primitives
– Examples attempts that do not solve the problem
– Peterson’s algorithm
– Argumentation structure (proof by way of contradiction, disproof by counterexample)

Now:
• Help from other hardware synchronization primitives; n-thread CS
– Let’s reflect on busy waiting (aka spinning) …..

• Semaphores

• Other synchronization objects

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 32

 Let’s reflect on busy waiting (aka spinning) …..
– Rather simple, convenient; BUT:
– Busy-waiting consumes processor time unnecessarily
– Starvation is possible when using methods as in prev slide
– (cf next slide for a method to maintain turn and avoid starvation)

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 33

 Bounded-waiting Critical Section with TestAndSet() and busy-waiting for n threads :
pesudocode thread i
Shared var lock: boolean // init false;
Shared var waiting[0..n-1]: array of boolean // init all false;
do
waiting[i] := TRUE;
while (waiting[i] && TestAndSet(&lock) ) do [nothing]; //busywait
waiting[i] := FALSE;
[critical section ]
j = (i + 1) % n;
while ((j != i) && !waiting[j]) do // find next one waiting, to help it (handover the “lock” )
j := (j + 1) % n;
if (j == i) then
lock := false; // completed one round without handing over; release “lock”
else
waiting[j] := false; // hand-over “lock”
[remainder section ]
forever;
Homework training: argue as we did with Peterson’s algo regarding correctness (mutual exclusion, progress, fairness)
[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 34
 Let’s reflect on busy waiting/spinning (cont) …..
Even Deadlock possible if spinning in non-preemptive priority-based scheduling: example scenario:
threads/processes on the same CPU and:
• low priority thread LP executes in critical section
• higher priority thread HP needs to access its CS
• the higher priority thread HP is dispatched (ie occupies the processor) and busy-waits for the LP to exit
from its critical section…..
Dispatch HP thread, to spin
(forever!) to enter its CS

Interrupt

LP thread in CS

Time

In lab 2&3 you will work on avoiding spinning

• Using blocking (in a blocking-queue)
[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 35
 Roadmap Part B
Part A was about:
• The critical-section (CS) problem
• CS for 2 threads using Read/Write memory-access primitives
– Examples attempts that do not solve the problem
– Peterson’s algorithm
– Argumentation structure (proof by way of contradiction, disproof by counterexample)

• Help from other hardware synchronization primitives; n-thread CS

– Reflections on busy-waiting

• Semaphores

• Other synchronization objects

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 36

 Semaphores

Special variables/data-objects used for signaling

– Accessible via (i.e. API) atomic Wait and Signal operations
– If a process is waiting for a signal, it is blocked until that signal is “sent”

Definition of the signal() operation Definition of the wait() operation

signal(S) { wait(S) {
S++; // and unblock from queue if applicable while (S == 0) do; // here spin; alt. block in a queue
} // Executed atomically S--;
} // Executed atomically

 Binary semaphore – value can be only 0 or 1

 Counting semaphore – value can vary

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 37

 Critical section of n threads using semaphores

Shared var mutex_sem : binary semaphore // init = 1

Thread i
repeat
wait(mutex_sem);
[critical section]
signal(mutex_sem);
[remainder section]
forever;

Homework training: (i) argue as we did for Peterson’s algo; (ii) compare with the methods that use TAS or CAS

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 38

 Semaphores as General Synchronization Tools

Q: how to execute code segment B in TB only after code segment A has been executed in TA:

A: use semaphore flag, initialized to 0

TA TB
 
opA wait(flag)
signal(flag) opB

TB will be able to proceed from wait(flag) only after signal(flag) is executed by TA

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 39

 Roadmap Part B
Part A was about:
• The critical-section (CS) problem
• CS for 2 threads using Read/Write memory-access primitives
– Examples attempts that do not solve the problem
– Peterson’s algorithm
– Argumentation structure (proof by way of contradiction, disproof by counterexample)

Now:
• Help from other hardware synchronization primitives; n-thread CS
– Discussion on busy-waiting

• Semaphores

• Other synchronization objects

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 40

 Other synchronization operations/constructs:
Tools for programmers to solve critical section and synchronization
problems (can be implemented using hardware atomic instructions or
algorithms such as Peterson’s or other such tools); eg:
mutex lock x; API :
– x.acquire() wait/block if x is not available; else make x not
available Fig source: Gerdes, Mike. (2013). Timing
Analysable Synchronisation Techniques for
– x.release() unblock a waiting/blocked process; else make x Parallel Programs on Embedded Multi-Cores.
available
• If implemented with busy waiting, called spinlock
• Homework: show how to implement a mutex lock using (i) TAS or
(ii) semaphores(hint: check how to solve CS using TAS or
semaphores)
Condition Variables: condition x; API:
• x.wait () – a process that invokes the operation is blocked.
• x.signal () – unblocks one of processes that invoked x.wait () (if any;
else, does nothing)
Other high-level synchronization constructs
– Monitors (combination of mutex locks and condition variables)
– Barriers
[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 41
 Linux Synchronization provides system calls for:
+ let’s think together: (ie alt to )

• semaphores
• spin locks for multiprocessors (for short critical sections): why?
– [hint: wastes CPU time and can cause deadlocks if used with strict priority
scheduling on uniprocessor]
• futex
– try_lock through 1 invocation of RMW instruction; if already locked, then process
enters blocked queue; why?
 [Balance the cost of entering a queue directly with the cost of spinning on the
RMW instruction]
– https://man7.org/linux/man-pages/man2/futex.2.html

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 42

 Windows XP Synchronization

• processor-specific interrupt masks to protect access to global resources

on uniprocessors
• busy-wait spinlocks on multiprocessors
– why not on uniprocessors?
– [hint: can cause deadlocks if used with strict priority scheduling]
• dispatcher objects
– may act as mutexes, semaphores, or provide events (similar to condition variables)

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 43

 Pthreads Synchronization
OS-independent; provides:
• mutex locks with blocking queues
(also fairness in mind)

• condition variables

• Non-portable extensions include:

– read-write locks (we will discuss
these in upcoming lectures)
– spin locks

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects

 Discussion

• How are synchronization tools/objects like semaphores available to programmers?

– OS calls or prg-language libraries
– Some languages provide RMW instructions as such tools/data-types/objects (e.g.
iOS AtomicAdd, C++ AtomicFetchAndAdd)

• Why does the OS care for such tools?

– Needs for its own shared data (eg ready queues for scheduling, process tables, etc)
– Provides primitives for kernel-level threads synchronization

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 45

 Summary – critical section (CS), 2- and n-thread methods & objects/primitives
• 2-thread method, using R/W variables [Peterson’s algorithm]
• arguing about solutions and no-solutions
• n-thread CS
– Using stronger hardware support than just R/W variables; 1 vs many CPUs/cores
– Synchronization objects: semaphores and some more
– Discussion on busy-waiting
• @home: work with the homework questions on the slides
• Next:
– Common synchronization problems:
• Bounded buffer (producer-consumer)
• Dinning philosophers: resource-allocation (here we will focus also on deadlock-prevention)
• Narrow Bridge (+ Lab 2&3)
– More on synchronization methodology
• Lamport’s bakery algo + Turing award 2013 topic
• Readers/writers and a touch on lock-free synchronization
• …

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 46

 Reading instructions (on all the synchronization topics we discuss)
Modern OS by Tanenbaum-Bos:
- careful study of sections 2.3.1-2.3.6, 2.5.2
- Complement (Bakery alg.) through
http://web.cs.iastate.edu/~chaudhur/cs611/Sp09/notes/lec03.pdf
- Quicker reading, for awareness, of sections 2.3.7-2.3.10
Alt. from OS Concepts: Silberschatz-et-al: Sections 6.1-6.7, 6.9

-Matching review questions at e.g.

http://codex.cs.yale.edu/avi/os-book/OS9/review-dir/index.html

Optional reading, other sources:

1. Leslie Lamport (recipient of ACM Turing award 2013). Turing lecture: The computer science of concurrency (with special
mention to the Bakery algo)
Commun. ACM 58, 6 (May 2015), 71-76. DOI= http://dx.doi.org/10.1145/2771951
2. Large variety of synch methods: how to think/decide? Cf also eg:
A Study of the Behavior of Synchronization Methods in Commonly Used Languages and Systems; D. Cederman, B.
Chatterjee, N. Nguyen, Y. Nikolakopoulos, M. Papatriantafilou, P Tsigas, 27th IEEE International Parallel & Distributed
Processing Symposium, IPDPS 2013 http://www.computer.org/csdl/proceedings/ipdps/2013/4971/00/4971b309-abs.html
3.M. Herlihy&Shavit,”The art of Multiprogramming, By Herlihy & Shavit) (http://cs.brown.edu/courses/cs176/lectures.shtml)
4. P. Fatourou: Spin Locks and Contention https://www.csd.uoc.gr/~hy586/material/lectures/cs586-Section3.pdf

[MP] – OS 05_ Process/thread synch: CS & argumentation; primitives & objects 47