Operating Systems CMPSC 473
Concurrency: Mutex locks, liveness conditions
Lectures 24: April 15, 2021 Instructor: Bhuvan Urgaonkar
• •
• •
Administrative
P3 report
• Only graphs/explanation of Expt 2 if you would like 10% bonus
• Everything else is being collected via Google forms
P4 is out, due on April 29
• No extensions
• IMPORTANT: Raj will be giving a code overview and answering questions on Friday; go prepared; will be recorded
Next Tuesday’s class will be held on Monday (3 pm); last lecture on synchronization; following 3 lectures will be on IO management + finals prep/hints + wrapup
Today’s lecture will contain a significant part of the solution to Project 4
• 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
• Next
• Pthreads lock API
• How to use locks
• Liveness conditions
• Condition variables, pthreads API
• Several synchronization problems
Outline
• Definition:
void Swap (boolean *a, boolean *b) {
boolean temp = *a; *a = *b;
*b = temp:
}
Swap Instruction
Mutex lock using Swap
• Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key.
• Solution:
while (true) {
key = TRUE;
while ( key == TRUE) Swap (&lock, &key );
// critical section lock = FALSE;
}
// remainder section
Pthreads lock API
• #include
• int pthread_mutex_lock (pthread_mutex_t *mutex);
• int pthread_mutex_unlock (pthread_mutex_t *mutex);
• On your own: int pthread_mutex_trylock (pthread_mutex_t *mutex);
E.g. #1: Shared Bank Account
lock mutex;
PROCESS 1 (wife’s transaction): …
Withdraw (amt) {
lock(mutex);
Bal -= amt;
unlock(mutex);
return; }
PROCESS 2 (husband’s transaction): …
Withdraw (amt) {
lock(mutex);
Bal -= amt;
unlock(mutex);
return; }
Quiz 25.1
E.g., #2: Producer-Consumer
lock mutex;
while (true) {
/* produce an item and put in nextProduced */
lock (mutex);
while (count == BUFFER_SIZE); // do nothing
unlock (mutex);
buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; lock (mutex);
count++;
unlock (mutex);
}
while (true) {
lock (mutex);
while (count == 0); // do nothing
unlock (mutex);
nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE;
lock (mutex);
count–;
unlock (mutex);
/* consume the item in nextConsumed */ }
• Shared variables: count, buffer
P-C: Deadlock!
lock mutex;
while (true) {
/* produce an item and put in nextProduced */
buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; lock (mutex);
count++;
unlock (mutex);
}
lock (mutex);
while (count == BUFFER_SIZE); // do nothing
unlock (mutex);
while (true) {
lock (mutex);
while (count == 0); // do nothing
unlock (mutex);
nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE;
/* consume the item in nextConsumed */ }
lock (mutex);
count–;
unlock (mutex);
• Consumerconsumesoneitemfromafullbuffer
• Cannot decrement count since lock held by producer
• Producer waiting on count to become less than BUFFER_SIZE • Consumerwaitingfortheproducertoreleasethelock
while(true) { Lock(C) Lock(A)
CS Unlock(C) Unlock(A)
}
Deadlock
while(true) { Lock(A) Lock(C)
CS Unlock(A) Unlock(C)
}
• INFORMAL:Deadlockisastateofaconcurrentprogramwherein each thread waits on a resource (e.g., lock ) held by another and none may release the resource they hold because they are waiting thesmselves
Quiz 25.2
while(true) { Lock(C) if(TryLock(A))
break Sleep() Unlock(C)
}
Livelock
while(true) { Lock(A) if(TryLock(C))
break Sleep() Unlock(A)
}
Quiz 25.3
• What do you expect the CPU utilization to be in the deadlock and livelock scenarios of the last 2 slides?
• Deadlock:
• if the lock is based on spinning (spinlock) -> 100%
•If the lock is based on blocking -> whatever results from the activity of the thread holding the lock
• Livelock: •Close to 0
Mutex Liveness Conditions
• 1. no deadlock: if a process is in its entry section at some time, then
later some process is in its critical section
• 2. progress/no lockout/no starvation: if a process is in its entry section at some time, then later the same process is in its critical section
• 3. bounded waiting: no lockout + while a process is in its entry section, other processes enter the critical section no more than a certain number of times.
• These conditions are increasingly strong (each implies the previous ones)
– Exercise: Prove this
Mutual Exclusion: Traffic Analogy
If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
2
4
1
3
Mutual Exclusion: Traffic Analogy
If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
3
Only one car can be in the square area between the stop signs at a given time
2
4
1
2. Progress: Traffic Analogy
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
2. Progress: Traffic Analogy
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
If the square is empty and there is some car, it will get to cross
(no starvation)
3. Bounded Waiting: Traffic
Analogy
A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
Assumethateachprocessexecutesatanonzerospeed
No assumption concerning relative speed of the N processes
2
4
1
3
Any car has to wait at most for 3 others to pass after it stops (fairness)