Operating Systems CMPSC 473
Concurrency: condition variables; semaphores; misc. synchronization problems
Lecture 25: April 19, 2021 Instructor: Bhuvan Urgaonkar
• •
Administrative
Today’s lecture may take more than the usual 75 minutes
• Please don’t interrupt me at 4:15; if you need to leave, please do so but make sure to watch the rest of the lecture soon
A great resource for synchronization problems: “The Little Book of
Semaphores”
• https://greenteapress.com/semaphores/LittleBookOfSemaphores.pdf
• Usually presents buggy solutions before presenting correct ones
• Try to solve yourself before looking at solution
• Sofar
• Data races and race conditions
• The mutual exclusion approach
• How to implement locks
• Disable interrupts
• Using only atomic loads and stores, e.g., Peterson’s
• Using more complex atomic instructions, e.g., TAS
• Pthreads lock API
• How to use locks
• Liveness conditions
• Today
• Condition variables, pthreads API
• Semaphores
• Several synchronization problems
Outline
Quiz 25.1: Concurrent linked list
Can you improve this for performance?
Quiz 25.2: Spot any problems?
Quiz 25.2: Spot any problems?
MT-Safe (contd.)
• https://man7.org/linux/man-pages/man3/pthread_create.3.html#ATTRIBUTES
MT-Safe (contd.)
• https://man7.org/linux/man-pages/man7/attributes.7.html
Signaling
• Animportantsynchronizationpatternissignaling wherein for threads A and B:
– A reaches a point in its execution beyond which it only wishes to proceed upon the occurrence of an event that is under B’s control
– A “waits” on B upon which A is blocked
– B “signals” when appropriate after which A becomes ready to run
Quiz 25.3
• pthread_joinisaspecialcaseofsignaling.Whatdoyou understand by this?
• Waitoperation
Condition Variables
– When a thread executes a wait call on a condition variable, it is immediately suspended
• It is now is waiting for the event that is represented by the condition variable to occur
• Signaloperation
– Eventually, a thread will cause the event to occur after which it will call the signal method on the corresponding condition variable
• If there are threads waiting on the signaled condition variable, one of the waiting threads will be allowed to resume execution
• If there is no waiting thread on the signaled condition variable, this signal is lost as if it never occurred
cond_t not_full, not_empty; int count == 0;
Produce() {
if (count == N) wait (not_full);
… ADD TO BUFFER, count++ …
signal (not_empty); }
Consume() {
if (count == 0) wait (not_empty);
… REMOVE FROM BUFFER, count– …
signal (not_full); }
What is wrong?
cond_t not_full, not_empty; mutex_lock m;
int count == 0;
Produce() {mutex_lock (m);
if (count == N) wait (not_full,m);
}
… ADD TO BUFFER, count++ …
signal (not_empty); mutex_unlock (m);
Consume() {mutex_lock (m);
if (count == 0) wait (not_empty,m);
}
… REMOVE FROM BUFFER, count– …
signal (not_full); mutex_unlock (m);
NOTE: You can improve this code for more concurrency!
Additional Complexity in Project 4
• Your objects will be variable length
– e.g., (”cmpsc”, 1) will be longer than (“473”, 1)
• You will be solving a multiple producer, single consumer problem
Additional Complexity in
Project 4 (contd.)
Consider 2 producers and 1 consumer with the previous solution
block
ready
no
consume
count=N-1
signal
unlock
count==N?
produce
count=N
signal
unlock
N-1 N
p
cond_t not_full, not_empty; mutex_lock m;
int count == 0;
Produce() {mutex_lock (m);
if (count == N) wait (not_full,m);
}
… ADD TO BUFFER, count++ …
signal (not_empty); mutex_unlock (m);
Consume() {mutex_lock (m);
if (count == 0) wait (not_empty,m);
}
… REMOVE FROM BUFFER, count– …
signal (not_full); mutex_unlock (m);
NOTE: You can improve this code for more concurrency!
Condition Variables
• pthreads functions/data struct
– pthread_cond_t condition = PTHREAD_COND_INITIALIZER; or
pthread_cont_init (condition, attr)
– pthread_cond_wait (condition, mutex) – pthread_cond_signal (condition)
Quiz 25.4
int waitingcount=0 lock m;
;
lock(&m); while (wait
unlock(& sleep (); lock(&m
} unlock(&m
Quiz 25.4 #1
int waitingcount=0 lock m;
;
lock(&m); count = wa while (coun
notify_qu
count–; }
unlock(&m
Quiz 25.4 #2
When CVs are not adequate
• Signal operations on CVs can be “lost”
– If there isn’t a thread doing a wait() when a thread calls signal(), the signal() is forgotten
• Sometimes there is a need to remember all signal operations
• Semaphores offer such “memory”
– Roughly: Semaphores = Integer + Signal/Wait, where the integer counts #signals – #waits
Semaphores
Semaphores Definition (Dijkstra)
• ACK: Lot of material borrowed from “The Little Book of Semaphores” by Allen B. Downey
– Availableonline(free)at:
http://www.greenteapress.com/semaphores/
Semaphores
• Can only be accessed via two indivisible (atomic) operations – wait (S) {
while S <= 0; // no-op S--;
}
– signal (S) {
S++; }
decrement; P() increment; V()
• Note: Busy waiting in these definitions, next slides show how they can be improved to reduce busy waiting
• A semaphore has:
– An integer called count
– A queue that captures blocked requests
– Alockforensuringatomicityofwait()and signal()
• API:
– Initialization to an integer
– Wait:
wait (S) {
while S <= 0; // no-op S--;
}
signal (S) { S++;
}
• Atomically {count--; block and join queue if count < 0;}
– Signal:
• Atomically {count++; wake up a thread if count <= 0}
Less busy waiting
Semaphores for Mutex
• Can only be accessed via two indivisible (atomic) operations
– wait (S) { /* also called decrement */
while S <= 0; // no-op S--;
}
– signal (S) { /* also called increment */
S++; }
• Provides mutual exclusion
– Semaphore S; // initialized to 1
– wait (S);
Critical Section signal (S);
Consequences of the definition
• Ingeneral,thereisnowaytoknowbeforeathread decrements a semaphore whether it will block
• After a thread increments a semaphore and another thread gets woken up, both threads continue running concurrently. There is no way to know which thread, if either, will continue immediately
• When you signal a semaphore, you don’t necessarily know whether another thread is waiting, so the number of unblocked threads may be zero or one.
Meaning of Semaphore Values
• Ifthevalueis+,itrepresentsthenumberof threads that can decrement without blocking
• Ifthevalueis-,itrepresentsthenumberofthreads that are blocked and are waiting
• Ifthevalueis0,itmeanstherearenothreads waiting, but if a thread tries to decrement, it will block
Signaling
• Initial value of sem = 0
• This ensures a1 executes before b1 • Why?
Rendezvous
• •
We want a1 before b2 and b1 before a2
Hint: Create two semaphores aArrived (indicating A has arrived
at the rendevous) and bArrived both initialized to 0;
Rendezvous: Solution 1
• Initialization: – aArrived = 0; – bArrived = 0;
Rendezvous: Solution 2
• Initialization: – aArrived = 0; – bArrived = 0;
Rendezvous: Solutions 1 and 2 Compared
• Initialization: – aArrived = 0; – bArrived = 0;
• Which is likely more efficient?
• Hint: Solution 2 might require one
• extra context switch
Quiz 25.5: Spot any bugs?
sem_t full=0, empty=N; int count == 0;
Produce() {wait (empty);
... ADD TO BUFFER ...
signal (full); }
Consume() {wait (full);
... REMOVE FROM BUFFER ...
}
signal (empty);
Barrier
• Nthreads,eachhasthefollowing“barriercode”: ...
rendezvous critical point ...
• Synchronizationrequirement:
– No thread may execute its critical point unless all threads have executed their rendezvous
Asymmetric Producer
• BufferofcapacityN
• Any number of producers and consumers
• Produceralwaysproducesitemsinpairs
• Consumeralwaysconsumesitemsingroupsofthree
Consumer
Quiz 25.6: Reader Writer
• Anynumberofreadersmaybeintheircriticalsections together
• Ifawriterisinitscriticalsection,nooneelsemaybein their critical section
Reader:
while (1) { read();
Writer:
while (1) { write();
do_other_things(); }}
do_other_things();
Reader:
while (1) {
lock (&m); nreaders++; unlock (&m); read();
lock (&m);
nreaders--;
if (nreaders == 0) signal (&no_readers); unlock (&m);
do_other_things();
Writer:
while (1) {
lock (&m);
while (nreaders > 0)
wait (&no_readers, &m);
write();
unlock (&m);
do_other_things(); }
Init:
int nreaders=0;
mutex_t m;
cond_t no_readers; // signal when no readers remain
}
Dining Philosophers
Flipping Philosophers
Bathroom w/o gender- based seg.
• Penn State is considering a new policy whereby the same bathroom may be used by both men and women. However, at any given time either only women or only men may be using the bathroom. Assume the bathroom has infinite capacity.
• Writethesefunctions:
– Woman_wants_to_enter, Man_wants_to_enter
– Woman_leaves, Man_leaves
The Sleeping Professor Problem
Init:
The Sleeping Professor
Problem
Student:
GetHelp() { blah blah blah
}
int numStudents=0;
cond_t SomeoneNeedsHelp, WaitOurTurn, DoneWithAStudent;
Professor: mutex_t m; HelpStudents() {
lock(&m);
while (numStudents > 0) {
signal(&WaitOurTurn); wait(&DoneWithAStudent, &m);
}unlock(&m);
Student:
while (1) { Study();
ArrivingStudent();
}ArrivingStudent() {
lock (&m); numStudents++;
if (numStudents == 1) {
signal (&WakeProf);
}
wait(&WaitOurTurn, &m); GetHelp(); signal(&DoneWithAStudent); numStudents–;
unlock(&m);
}
}