Overview Critical Sections Multiple Resources
1
Concurrency Appreciation
Christine Rizkallah
CSE, UNSW Term 3 2020
Overview Critical Sections Multiple Resources
Definitions
Definition
Concurrency is an abstraction for the programmer, allowing programs to be structured as multiple threads of control, called processes. These processes may communicate in various ways.
Example Applications: Servers, OS Kernels, GUI applications.
Anti-definition
Concurrency is not parallelism, which is a means to exploit multiprocessing hardware in order to improve performance.
2
Overview Critical Sections Multiple Resources
Sequential vs Concurrent
We could consider a sequential program as a sequence (or total order) of actions: ••••••···
The ordering here is “happens before”. For example, processor instructions:
LD R0,X LDI R1,5 ADD R0,R1 ST X,R0
A concurrent program is not a total order but a partial order. ◦◦◦◦◦◦···
••••••···
This means that there are now multiple possible interleavings of these actions — our program is non-deterministic where the interleaving is selected by the scheduler.
3
Overview Critical Sections Multiple Resources
Concurrent Programs
Consider the following concurrent processes, sharing a variable n.
var n := 0
p1: var x := n; p2: n:=x+1;
q1: vary:=n; q2: n:=y−1;
r1: var z := n; r2: n:=z+1;
Question
What are the possible returned values?
4
Overview Critical Sections Multiple Resources
A Sobering Realisation
How many scenarios are there for a program with n processes consisting of m steps each?
n=23456 m= 2 6 90 2520 113400 222.8
3 20 1680 218.4 227.3 236.9 4 70 34650 225.9 238.1 251.5 5 252 219.5 233.4 249.1 266.2 6 924 224.0 241.0 260.2 281.1
(nm)! m!n
5
Overview Critical Sections Multiple Resources
Volatile Variables
var y,z := 0,0
p1: var x;
p2: x:=y+z;
q1: y:=1; q2: z:=2;
Question
6
What are the possible final values of x?
What about x = 2? Is that possible?
It is possible, as we cannot guarantee that the statement p2 is executed atomically — that is, as one step.
Typically, we require that each statement only accesses (reads from or writes to) at most one shared variable at a time. Otherwise, we cannot guarantee that each statement is one atomic step. This is called the limited critical reference restriction.
Overview Critical Sections Multiple Resources
Synchronisation
In order to reduce the number of possible interleavings, we must allow processes to synchronise their behaviour, ensuring more orderings (and thus fewer interleavings).
◦◦◦◦◦◦···
••••••···
The red arrows are synchronisations.
7
Overview Critical Sections Multiple Resources
Atomicity
The basic unit of synchronisation we would like to implement is to group multiple steps into one atomic step, called a critical section.
A sketch of the problem can be outlined as follows:
forever do
non-critical section pre-protocol critical section post-protocol
forever do
non-critical section pre-protocol critical section post-protocol
8
The non-critical section models the possibility that a process may do something else. It can take any amount of time (even infinite).
Our task is to find a pre- and post-protocol such that certain atomicity properties are satisfied.
Overview Critical Sections Multiple Resources
Desiderata
We want to ensure two main properties:
Mutual Exclusion No two processes are in their critical section at the same time.
Eventual Entry (or starvation-freedom) Once it enters its pre-protocol, a process will eventually be able to execute its critical section.
Question
Which is safety and which is liveness? Mutex is safety, Eventual Entry is liveness.
9
Overview Critical Sections Multiple Resources
First Attempt
We can implement await using primitive machine instructions or OS syscalls, or even using a busy-waiting loop.
var turn := 1
forever do
p1 non-critical section
p2 await turn = 1;
p3 critical section
p4 turn := 2
forever do
q1 non-critical section
q2 await turn = 2;
q3 critical section
q4 turn := 1
Question
Mutual Exclusion? Yup!
Eventual Entry? Nope! What if q1 never finishes?
10
Overview Critical Sections Multiple Resources
Second Attempt
var wantp, wantq := False, False
forever do
p1 non-critical section
p2 await wantq = False;
p3 wantp := True;
p4 critical section
p7 wantp := False
forever do
q1 non-critical section
q2 await wantp = False;
q3 wantq := True;
q4 critical section
q7 wantq := False
11
Mutual exclusion is violated if they execute in lock-step (i.e. p1q1p2q2p3q3 etc.)
Overview Critical Sections Multiple Resources
Third Attempt
var wantp, wantq := False, False
forever do
p1 non-critical section
p2 wantp := True;
p3 await wantq = False;
p4 critical section
p7 wantp := False
forever do
q1 non-critical section
q2 wantq := True;
q3 await wantp = False;
q4 critical section
q7 wantq := False
12
Now we have a stuck state (or deadlock) if they proceed in lock step, so this violates eventual entry also.
Overview Critical Sections Multiple Resources
Fourth Attempt
var wantp, wantq := False, False
forever do
p1 p2 p3 p4 p5
p6 p7
non-critical section
wantp := True; while wantq do
wantp := False;
wantp := True od
critical section
wantp := False
forever do
q1 q2 q3 q4 q5
q6 q7
non-critical section
wantq := True; while wantp do
wantq := False;
wantq := True od
critical section
wantq := False
13
We have replaced the deadlock with live lock (looping) if they continuously proceed in lock-step. Still potentially violates eventual entry.
Overview Critical Sections Multiple Resources
14
Fifth Attempt
var wantp, wantq := False, False var turn := 1
forever do
p1 p2 p3 p4 p5 p6 p7
p8
p9 p10
non-critical section
wantp = True; while wantq do
if turn = 2 then wantp := False; await turn = 1; wantp := True
fi od
critical section
turn := 2 wantp := False
forever do
q1 q2 q3 q4 q5 q6 q7
q8
q9 q10
non-critical section
wantq = True; while wantp do
if turn = 1 then wantq := False; await turn = 2; wantq := True
fi od
critical section
turn := 1 wantq := False
Overview Critical Sections Multiple Resources
Reviewing this attempt
The fifth attempt (Dekker’s algorithm) works well except if the scheduler pathologically tries to run the loop at q3 · · · q7 when turn = 2 over and over rather than run the process p (or vice versa).
What would we need to assume to prevent this?
Fairness
The fairness assumption means that if a process can always make a move, it will eventually be scheduled to make that move.
With this assumption, Dekker’s algorithm is correct.
15
Overview Critical Sections Multiple Resources
Machine Instructions
There exists algorithms to generalise this to any number of processes (Peterson’s algorithm), but they’re outside the scope of this course.
What about if we had a single machine instruction to swap two values atomically, XC?
var common := 1
var tp := 0 forever do
p1 non-critical section
repeat
p2 XC(tp, common)
p3 untiltp=1
p4 critical section
p5 XC(tp, common)
var tq := 0 forever do
q1 non-critical section
repeat
q2 XC(tq, common);
q3 untiltq=1
q4 critical section
q7 XC(tq, common)
16
Overview Critical Sections
Multiple Resources
Locks
The variable common is called a lock. A lock is concurrency control in a programming language abstracted into an abstract data type, with two
Taking the lock — the first exchange (step Releasing the lock — the second exchange
the most common means of implementation. Typically it is
operations: p2/q2)
(step p5/q5)
var lock
forever do
p1 non-critical section
p2 take (lock)
p3 critical section
p4 release (lock)
forever do
q1 non-critical section
q2 take (lock);
q3 critical section
q4 release (lock);
17
Overview
Critical Sections
Multiple Resources
Dining Philosophers
Five philosophers sit around a dining table with a huge bowl of spaghetti in the centre,
five plates, and five forks, all laid out evenly. For whatever reason, philosophers can eat spaghetti only with two forksa. The philosophers would like to alternate between eating and thinking.
aThis is obviously a poor adaptation of an old problem from the East where requiring two chopsticks is more convincing.
18
Overview Critical Sections Multiple Resources
19
Looks like Critical Sections
forever do
think pre-protocol eat post-protocol
For philosopher i ∈ 0…4:
f0,f1,f2,f3,f4
forever do
think
take(fi ) take(f(i+1) mod 5)
eat
release(fi ) release(f(i+1) mod 5)
Deadlock is possible (consider lockstep).
Overview Critical Sections Multiple Resources
Fixing the Issue
f0,f1,f2,f3,f4
Philosophers 0. . . 3
Philosopher 4
forever do
think
take(fi ) take(f(i+1) mod 5)
eat
release(fi ) release(f(i+1) mod 5)
forever do
think
take(f0 ) take(f4 ) eat release(f0 ) release(f4 )
20
We have to enforce a global ordering of locks.