Transcript Synchronization

CS 105
“Tour of the Black Holes of Computing”
Synchronization Methods
Topics



Mutual-exclusion methods
Producer/consumer problem
Readers/writers problem
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, e.g.,
FIFO or priority
Desirable properties:



–2–
Efficiency: can get into CS in relatively few instructions
Low load: waiting for CS does not 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 of features is big plus
•
•
•
–3–
Understood
Symmetrical
Fully implemented by OS and Languages
CS 105
Hardware Mutex Support – Lowest
Level
Test and Set


Read word, set it nonzero, and set condition codes
All in one indivisible operation
Compare and Swap



–4–
Read word, compare to register, if match then store second
register into word
Again, indivisible
Generalization of Test & Set
CS 105
Example of Test and Set
enter_critical_region:
/* read mem, set cc, store mem
leal lock, %eax ; address of lock to 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:
xor %eax, %eax ; make it 0
movl %eax, lock ; set lock to 0
ret
–5–
CS 105
Evaluating Test and Set
+ Very fast entry to unlocked region
+ Easy to implement – if hardware support
+ Guarantees safety & progress
- Wastes CPU when waiting (spin lock/busy wait)
- Does not 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. OS provides higher level
constructs
–6–
CS 105
Semaphores
Higher-level construct



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/process 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


–7–
P’s and V’s must be matched – user problem
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
Difficult or impossible to use incorrectly – system enforced
Like Java/C++ class: combines data with functions needed
to manage it
Keys to monitor correctness – enforced by system




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

–8–

Programmers wind up standing on heads or implementing
things like semaphores
Real Solution ??
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 a method to evaluate proposed synchronization
mechanisms, i.e., act as benchmarks
–9–
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
Solutions



– 10 –
Can be done with just load/store (but very very tricky)
We have seen simple semaphore-based solution for oneelement buffer
Perfect application for monitors
CS 105
Producer/Consumer with Monitors
/* Board */
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;
– 11 –
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 //set up code
slotsinuse := 0;
nexttofill := 0;
nexttoempty := 0;
end;
– 12 –
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’ face

Only one writer allowed at a time
 should readers wait for writer, i.e., get the latest value?
Examples:


– 13 –
Shared access to file
ATMs displaying or updating bank balance
CS 105
Readers/Writers with Semaphores
(Polling Version)
Semaphore gate = 1; // let someone in
// what is the critical section
int nreaders = 0, nwriters = 0;
void reader()
{
while (1)
{
P(gate);
// my turn
while (nwriters != 0)
{
// there is a writer
V(gate); // give back access
wait_a_while();
P(gate); // try again
}
nreaders++;
V(gate); // give back access
read();
P(gate); // done reading, access nreaders
nreaders--;
V(gate);
}
}
– 14 –
CS 105
Readers/Writers with Semaphores
(Polling continued)
void writer()
{
while (1) {
P(gate);
while (nreaders + nwriters != 0) {
V(gate);
wait_a_while();
P(gate);
}
nwriters++;
V(gate);
write();
P(gate);
nwriters--;
V(gate);
}
}
– 15 –
CS 105
Readers/Writers with Semaphores
(Polling continued)
What are the drawbacks of this approach?
How can we write a non-polling version?
– 16 –
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;
– 17 –
CS 105
Readers/Writers with Monitors cont.
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;
18 –
CS 105
Readers/Writers with Monitors
Characteristics of solution





– 19 –
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

– 20 –
Solvable with semaphores or monitors
CS 105
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
– 21 –
CS 105
Drinking Philosophers
Extension of dining philosophers
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
– 22 –
CS 105