Transcript Synchronization - HMC Computer Science

CS 105
“Tour of the Black Holes of Computing”
Synchronization Methods
Topics



Mutual-exclusion methods
Producer/consumer problem
Readers/writers problem
Deadlock and Starvation
Three bad things can happen in concurrency
Inconsistency: incorrect results, e.g. from races
Deadlock: Nobody can make progress
Starvation: No deadlock, but somebody doesn’t make
progress
–2–
CS 105
Mutual Exclusion
Need ways to enforce critical sections

Prevent race conditions that cause errors
Requirements for mutual exclusion



Safety: only one process/thread at a time inside CS
Progress: if nobody has access and somebody wants in,
somebody gets in
No starvation: if you want in, you will eventually get in
Desirable properties:



–3–
Efficiency: can get into CS in relatively few instructions
Low load: waiting for CS doesn’t waste resources
Fairness: if you want in, nobody else gets in ahead of you
twice
CS 105
Additional Requirements
Synchronization is tricky to get right



Failure to protect critical sections
Incorrect use of primitives
Deadlock
Programmer-friendliness is big plus
–4–
CS 105
Hardware Mutex Support
Test and Set


Read word, set it nonzero, and set condition codes
All in one indivisible operation
Compare and Swap



Read word, compare to register; if match then store some
other register into word
Again, indivisible
Generalization of Test & Set
Double Compare and Swap


–5–
Extends CAS to two (noncontiguous) locations
Turns out to not be that useful; omitted in current designs
CS 105
Example of Test and Set
enter_critical_region:
leal lock, %eax
.L1: tsl (%eax)
; Set lock NZ, set CC
jne .L1
; Loop if was already NZ
; We now have exclusive access
ret
leave_critical_region:
movl $0, lock
ret
–6–
CS 105
Evaluating Test and Set
+ Very fast entry to unlocked region
+ Easy to implement (except on multi-core hardware!)
+ Guarantees safety & progress
- Wastes CPU when waiting (spin lock/busy wait)
- Doesn’t make it easy for other threads to run
- Extremely high memory (i.e., bus) traffic
- Prone to errors (e.g., forget to unlock)
- Prone to starvation
For these reasons, test & set is used only to implement
higher-level constructs.
–7–
CS 105
Semaphores
Higher-level construct, discussed previously



Invented by Edsger Dijkstra
P(sem) or wait(sem) decrements and possibly waits
V(sem) or signal(sem) increments and lets somebody else in
Usually implemented by operating system


Allows scheduler to run different thread while waiting
OS can guarantee fairness and no starvation
 Or can even enforce priority scheme

More flexibility for user (e.g., can count things)
Still error-prone


–8–
P’s and V’s must be matched
Single extra V blows mutual exclusion entirely (compare
Test & Set)
CS 105
Monitors
High-level mutual-exclusion construct



Invented by C.A.R. “Tony” Hoare (also quicksort inventor)
Difficult or impossible to use incorrectly
Like Java/C++ class: combines data with functions needed
to manage it
Keys to monitor correctness




Data is available only to functions within monitor
Specific functions (gatekeepers) control access
Only one process/thread allowed inside monitor at a time
Queues keep track of who is waiting for monitor
Turns out to be hard to do certain things with monitors

–9–
Programmers wind up standing on heads or implementing
things like semaphores
CS 105
Problems in Synchronization
Many standard problems in concurrent programming





Producer/consumer
Readers/writers
Dining philosophers
Drinking philosophers
Etc.
Standard problems capture common situations
Also give way to evaluate proposed synchronization
mechanisms
– 10 –
CS 105
The Producer/Consumer
Problem
Two processes communicate


Producer generates things (e.g., messages) into a buffer
Consumer takes those things and uses them
Correctness requirements



Producer must wait if buffer is full
Consumer must not extract things from empty buffer
Order must be maintained
Solutions



– 11 –
Can be done with just load/store (but tricky)
We have seen simple semaphore-based solution for oneelement buffer
Perfect application for monitors
CS 105
Producer/Consumer with
Monitors
monitor producerconsumermonitor;
var buffer[0..slots-1] of message;
slotsinuse: 0..slots;
nexttofill, nexttoempty: 0..slots-1;
bufferhasdata, bufferhasspace: condition;
procedure fillslot(var data: message) begin
if slotsinuse = slots;
then wait(bufferhasspace);
buffer[nexttofill] := data;
nexttofill := (nexttofill + 1) mod slots;
slotsinuse := slotsinuse + 1;
signal(bufferhasdata);
end;
– 12 –
CS 105
Producer/Consumer with
Monitors (continued)
procedure emptyslot(var data: message) begin
if slotsinuse = 0;
then wait(bufferhasdata);
data := buffer[nexttoempty];
nexttoempty = (nexttoempty + 1) mod slots;
slotsinuse := slotsinuse – 1;
signal(bufferhasspace);
end;
begin
slotsinuse := 0;
nexttofill := 0;
nexttoempty := 0;
end;
– 13 –
CS 105
The Readers/Writers Problem
More complex than producer/consumer



Many processes accessing single resource
Some read, some write (some could do both)
OK for many to read at once
 No danger of stepping on each others’ feet

Only one writer allowed at a time
Examples:


– 14 –
Shared access to file
ATMs displaying or updating bank balance
CS 105
Readers/Writers with
Semaphores (Polling Version)
semaphore mutex = 1;
int nreaders = 0, nwriters = 0;
void reader()
{
while (1) {
P(mutex);
while (nwriters != 0) {
V(mutex);
wait_a_while();
P(mutex);
}
nreaders++;
V(mutex);
read();
P(mutex);
nreaders--;
V(mutex);
}
}
– 15 –
CS 105
Readers/Writers with
Semaphores (Polling continued)
void writer()
{
while (1) {
P(mutex);
while (nreaders + nwriters != 0) {
V(mutex);
wait_a_while();
P(mutex);
}
nwriters++;
V(mutex);
write();
P(mutex);
nwriters--;
V(mutex);
}
}
– 16 –
CS 105
Readers/Writers with
Semaphores (Polling continued)
What are the drawbacks of this approach?
How can we write a non-polling version?
– 17 –
CS 105
Readers/Writers with Monitors
monitor readersandwriters;
var readers: integer;
someonewriting: boolean;
readallowed, writeallowed: condition;
procedure beginreading begin
if someonewriting or queue(writeallowed)
then wait(readallowed);
readers := readers + 1;
signal(readallowed);
end;
procedure donereading begin
readers := readers – 1;
if readers = 0 then signal(writeallowed);
end;
– 18 –
CS 105
Readers/Writers with Monitors
(continued)
procedure beginwriting begin
if readers ¬= 0 or someonewriting
then wait(writeallowed);
someonewriting := true;
end;
procedure donewriting begin
someonewriting := false;
if queue(readallowed)
then signal(readallowed);
else signal(writeallowed);
end;
begin
readers := 0;
someonewriting := false;
end;
– 19 –
CS 105
Readers/Writers with Monitors
Characteristics of solution





– 20 –
No starvation
Arriving readers wait if writer is waiting
Group of readers runs after each writer
Arrival order of writer, writer, reader runs in different order
Requires several auxiliary variables
CS 105
Dining Philosophers
Models many important synchronization problems
Most famous concurrency problem
Posed by Dijkstra
Characteristics


Five philosophers alternate thinking and eating
Only food is spaghetti
 Requires two forks



Each philosopher has assigned seat at round table
One fork between each pair of plates
Problem: control access to forks, such that everyone can eat
 Note that “pick up left, then pick up right” doesn’t work (why?)

– 21 –
Solvable with semaphores or monitors
CS 105
Drinking Philosophers
Extension of dining philosophers, due to K.M. Chandy
Arbitrary number of philosophers
Each likes own drink, mixed from bottles on table


Can only mix drink when holding all necessary bottles
Each drink uses different subset of bottles
Problem: control access to bottles, such that there is
no deadlock and no starvation
Solution uses Dining Philosophers as sub-problem.
– 22 –
CS 105