CONCURRENCY: Reader/Writer Locks + DEADLOCK
Andrea Arpaci-Dusseau CS 537, Fall 2019
ADMINISTRIVIA
– Project 4 turned in – no significant problems
– Project 5 available now (xv6 Memory)
– Greatlysimplified!J
– Due next Monday 11/4 (5pm)
– Request new project partner if desired (web form)
– Midterm 2: Nov 11/6 (Wed) from 7:30-9:30pm
– Two”quizzes”onraceconditionsinCanvas
– Nextlecturesomereview,somesampleproblems
AGENDA / LEARNING OUTCOMES
Concurrency abstractions
• How to implement reader/writer locks with semaphores?
• What types of concurrency bugs occur?
• How to fix atomicity bugs (with locks)?
• How to fix ordering bugs (with condition variables)?
• How does deadlock occur?
• How to prevent deadlock (with waitfree algorithms, grab all locks atomically, trylocks, and ordering across locks)?
RECAP
Concurrency Objectives
Mutual exclusion (e.g.,A and B don’t run at same time) solved with locks
Ordering (e.g., B runs after A does something) solved with condition variables and semaphores
Condition Variables
wait(cond_t *cv, mutex_t *lock)
– assumes the lock is held when wait() is called
– puts caller to sleep + releases the lock (atomically) – when awoken, reacquires lock before returning
signal(cond_t *cv)
– wake a single waiting thread (if >= 1 thread is waiting) – if there is no waiting thread, just return, doing nothing
cv A B C D lock D A
signal(cv) – what happens? release(lock) – what happens?
INTRODUCING Semaphores
Condition variables have no state (other than waiting queue) – Programmer must track additional state
Semaphores have state: track integer value
– State cannot be directly accessed by user program,
but state determines behavior of semaphore operations
SUMMARY: Semaphores
Semaphores are equivalent to locks + condition variables
– Can be used for both mutual exclusion and ordering
Semaphores contain state
– How they are initialized depends on how they will be used – Init to 0: Join (1 thread must arrive first, then other)
– Init to N: Number of available resources
sem_wait(): Decrement and waits until value >= 0
sem_post(): Increment value, then wake a single waiter (atomic)
Can use semaphores in producer/consumer and for reader/writer locks
Dining Philosophers
Problem Statement
– N Philosophers sitting at a round table
– Each philosopher shares a chopstick (or fork) with neighbor
– Each philosopher must have both chopsticks to eat
– Neighbors can’t eat simultaneously
– Philosophers alternate between thinking and eating
Each philosopher/thread i runs : while (1) {
think();
take_chopsticks(i);
eat();
put_chopsticks(i);
}
0
0 4
4 3
1
1
2 3
2
Dining Philosophers: Attempt #1
Two neighbors can’t use chopstick at same time Must test if chopstick is there and grab it atomically
Represent each chopstick with a semaphore Grab right chopstick then left chopstick
Code for 5 philosophers:
sem_t chopstick[5]; // Initialize each to 1 take_chopsticks(int i) {
wait(&chopstick[i]);
wait(&chopstick[(i+1)%5]); 4 }
Deadlocked!
0 0
4 3
put_chopsticks(int i) { signal(&chopstick[i]); signal(&chopstick[(i+1)%5]);
}
1
1
2 3
2
Dining Philosophers
• Two solutions
– Having one philosopher grab resource in other order;
Break circular dependencies
– Phrase in terms of safety and liveness criteria;
Don’t hold on to one resource while waiting for next
Dining Philosophers: Attempt #2
Grab lower-numbered chopstick first, then higher-numbered
sem_t chopstick[5]; // Initialize to 1
take_chopsticks(int i) {
if (i < 4) {
wait(&chopstick[i]);
wait(&chopstick[i+1]);
} else {
wait(&chopstick[0]); wait(&chopstick[4]); 4
Philosopher 3 finishes take_chopsticks() and eventually calls put_chopsticks();
Who can run then?
What is wrong with this solution???
0 0
1 4
1
}
3
2 3
2
sem_t mayEat[5]; // how to initialize? sem_t mutex; // how to init?
int state[5] = {THINKING}; take_chopsticks(int i) {
wait(&mutex); // enter critical section state[i] = HUNGRY;
testSafetyAndLiveness(i); // check if I can run signal(&mutex); // exit critical section wait(&mayEat[i]);
}
put_chopsticks(int i) {
wait(&mutex); // enter critical section state[i] = THINKING;
test(i+1 %5); // check if neighbor can run now test(i+4 %5);
signal(&mutex); // exit critical section }
testSafetyAndLiveness(int i) { if(state[i]==HUNGRY&&state[i+4%5]!=EATING&&state[i+1%5]!=EATING) {
state[i] = EATING;
signal(&mayEat[i]); }}
Reader/Writer Locks
Protect shared data structure; Goal:
Let multiple reader threads grab lock with other readers (shared) Only one writer thread can grab lock (exclusive)
– No reader threads
– No other writer threads
Two possibilities for priorities – different implementations 1) No reader waits unless writer in critical section
• How can writers starve?
2) No writer waits longer than absolute minimum
• How can readers starve?
Let us see if we can understand code...
Readers have priority
Version 1
Reader/Writer Locks
1 typedef struct _rwlock_t {
2 sem_t lock;
3 sem_t writelock;
4 int readers;
5 } rwlock_t;
6
7 void rwlock_init(rwlock_t *rw) {
8
9
10 11 }
rw->readers = 0;
sem_init(&rw->lock, 1);
sem_init(&rw->writelock, 1);
13
14
15
16
17
18
19 }
T1: acquire_readlock() T2: acquire_readlock() T3: acquire_writelock() T2: release_readlock() T1: release_readlock()
// who runs?
T4: acquire_readlock()
Reader/Writer Locks
void rwlock_acquire_readlock(rwlock_t *rw) {
sem_wait(&rw->lock); rw->readers++;
if (rw->readers == 1)
sem_wait(&rw->writelock); sem_post(&rw->lock);
21
22
23
24
25
26
27 }
29 rwlock_acquire_writelock(rwlock_t *rw) { sem_wait(&rw->writelock); } 31 rwlock_release_writelock(rwlock_t *rw) { sem_post(&rw->writelock); }
void rwlock_release_readlock(rwlock_t *rw) {
sem_wait(&rw->lock); rw->readers–;
if (rw->readers == 0)
T3: release_writelock()
// what happens next?
sem_post(&rw->writelock); sem_post(&rw->lock);
// what happens? T5: acquire_readlock() // where blocked?
READER/Writer Locks
13
14
15
16
17
18
19
21
22
23
24
25
26
27 }
29 rwlock_acquire_writelock(rwlock_t *rw) { sem_wait(&rw->writelock); } 31 rwlock_release_writelock(rwlock_t *rw) { sem_post(&rw->writelock); }
void rwlock_acquire_readlock(rwlock_t *rw) {
}
sem_wait(&rw->lock); rw->readers++;
if (rw->readers == 1)
T1: acquire_readlock() T2: acquire_readlock() T3: acquire_writelock() T4: acquire_readlock()
sem_wait(&rw->writelock); sem_post(&rw->lock);
// what happens?
void rwlock_release_readlock(rwlock_t *rw) {
sem_wait(&rw->lock); rw->readers–;
if (rw->readers == 0)
sem_post(&rw->writelock); sem_post(&rw->lock);
Writers have priority Three semaphores
– Mutex
– O K To R e a d
– OKToWrite
– Semaphores used in similar way to myEat[i] in Dining Philosphers, but one for all readers, one for all writers)
How to initialize? Shared variables
Waiting Readers, ActiveReaders Waiting Writers Active Writers
Version 2
Acquire_readlock() {
Sem_wait(&mutex);
If (ActiveWriters +
WaitingWriters==0) {
sem_post(OKToRead);
ActiveReaders++;
} else WaitingReaders++;
Sem_post(&mutex);
Sem_wait(OKToRead);
Release_readlock() { Sem_wait(&mutex);
ActiveReaders–;
If (ActiveReaders==0 &&
WaitingWriters > 0) {
ActiveWriters++;
WaitingWriters–;
Sem_post(OKToWrite);
Sem_post(&mutex);
}
() {
(&mutex);
Acquire_writelock
Sem_wait
ActiveWriters
ActiveWriters
sem_post
} else
Sem_post
If (
==0) {
+
++;
ActiveReaders
+
WaitingWriters
(
WaitingWriters
OKToWrite
); ++;
(&mutex);
Release_writelock() {
Sem_wait(&mutex);
ActiveWriters–;
If (WaitingWriters > 0) {
ActiveWriters++;
WaitingWriters–;
Sem_post(OKToWrite);
(
T1: acquire_readlock() T2: acquire_readlock() T3: acquire_writelock() T4: acquire_readlock()
// what happens?
… release_readlock() x 2 T3: release_writelock()
Sem_wait
);
OKToWrite
}
}
}
} else while(WaitingReaders>0) { ActiveReaders++; WaitingReaders–; sem_post(OKToRead);
}
Sem_post(&mutex);
CONCURRENCY BUGS
Correctness is important
Concurrency in Medicine: Therac-25 (1980’s)
“The accidents occurred when the high-power electron beam was activated instead of the intended low power beam, and without the beam spreader plate rotated into place. Previous models had hardware interlocks in place to prevent this, but Therac-25 had removed them, depending instead on software interlocks for safety.The software interlock could fail due to a race condition.”
“…in three cases, the injured patients later died.”
Source: http://en.wikipedia.org/wiki/Therac-25
75 60 45 30 15
0
Concurrency Study
Atomicity
Order
Deadlock
Other
My SQL
Lu etal. [ASPLOS 2008]:
Ap ach e
Mo zil l a
Ope nOff ic e
For four major projects, search for concurrency bugs among >500K bug reports. Analyze small sample to identify common types of concurrency bugs.
Bugs
Thread 1:
if (thd->proc_info) { …
fputs(thd->proc_info, …);
Thread 2:
thd->proc_info = NULL;
… }
Atomicity: MySQL
What’s wrong?
Test (thd->proc_info != NULL) and write (fputs to thd->proc_info) should be atomic
Fix Atomicity Bugs with Locks
Thread 1:
pthread_mutex_lock(&lock);
if (thd->proc_info) { …
fputs(thd->proc_info, …);
… }
pthread_mutex_unlock(&lock);
Thread 2:
pthread_mutex_lock(&lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&lock);
75 60 45 30 15
0
Concurrency Study
Atomicity
Order
Deadlock
Other
My SQL
Lu etal. [ASPLOS 2008]:
Ap ach e
Mo zil l a
Ope nOff ic e
For four major projects, search for concurrency bugs among >500K bug reports. Analyze small sample to identify common types of concurrency bugs.
Bugs
Thread 1:
void init() {
…
mThread =
PR_CreateThread(mMain, …);
Thread 2:
void mMain(…) {
…
mState = mThread->State;
… }
… }
Ordering: Mozilla
What’s wrong?
Thread 1 sets value of mThread needed by Thread2
How to ensure reading MThread happens after mThread initialization?
Fix Ordering bugs with Condition variables
Thread 1:
void init() {
…
mThread =
PR_CreateThread(mMain, …);
pthread_mutex_lock(&mtLock);
mtInit = 1;
pthread_cond_signal(&mtCond);
pthread_mutex_unlock(&mtLock);
Thread 2:
void mMain(…) {
…
mutex_lock(&mtLock);
while (mtInit == 0)
Cond_wait(&mtCond, &mtLock);
Mutex_unlock(&mtLock);
mState = mThread->State;
… }
… }
75 60 45 30 15
0
Concurrency Study
Atomicity
Order
Deadlock
Other
My SQL
Lu etal. [ASPLOS 2008]:
Ap ach e
Mo zil l a
Ope nOff ic e
For four major projects, search for concurrency bugs among >500K bug reports. Analyze small sample to identify common types of concurrency bugs.
Bugs
Deadlock
No progress can be made because two or more threads are waiting for the other to take some action and thus neither ever does
STOP
STOP
STOP
STOP
STOP
A
STOP
STOP
STOP
STOP
B
A
STOP
STOP
STOP
Both cars arrive at same time Is this deadlocked?
STOP
B
A
STOP
STOP
STOP
STOP
A
B
STOP
STOP
STOP
STOP
A
B
STOP
STOP
STOP
STOP
STOP
STOP
STOP
B
4 cars arrive at same time Is this deadlocked?
D
C
A
STOP
STOP
STOP
STOP
4 cars move forward same time Is this deadlocked?
D
B
A
C
STOP
STOP
STOP
STOP
Deadlock!
D
B
A
C
STOP
STOP
STOP
STOP
Deadlock Theory
Deadlocks can only happen with these four conditions: 1. mutual exclusion
2. hold-and-wait
3. no preemption
4. circular wait
Can eliminate deadlock by eliminating any one condition
B
D
A
C
STOP
STOP
STOP
STOP
1. mutual exclusion 2. hold-and-wait 3. no preemption 4. circular wait
Can deadlock happen with these two threads?
Thread 1:
lock(& A); lock(&B);
Code Example
Thread 2:
lock(&B); lock(& A);
Circular Dependency
wanted by
wanted by
Thread 2
Thread 1
holds
Lock A
Lock B
holds
Thread 1:
lock(&A);
lock(&B);
Fix Deadlocked Code
Thread 2:
lock(&B);
lock(&A);
Thread 1
lock(&A);
lock(&B);
How would you fix this code?
Thread 2
lock(&A);
lock(&B);
Non-circular Dependency
Thread 1
holds
Lock A
wanted by
wanted by
Thread 2
Lock B
set_t *set_intersection (set_t *s1, set_t *s2) { set_t *rv = malloc(sizeof(*rv)); mutex_lock(&s1->lock); mutex_lock(&s2->lock);
for(int i=0; i
set_add(rv, s1->items[i]); mutex_unlock(&s2->lock);
mutex_unlock(&s1->lock); }
Thread 1: rv = set_intersection(setA, setB); Thread 2: rv = set_intersection(setB, setA);
Encapsulation
Modularity can make it harder to see deadlocks Solution?
if (m1 > m2) {
// grab locks in high-to-low address order
pthread_mutex_lock(m1);
pthread_mutex_lock(m2);
} else {
pthread_mutex_lock(m2);
pthread_mutex_lock(m1);
}
Any other problems?
Code assumes m1 != m2 (not same lock)
Deadlock Theory
Deadlocks can only happen with these four conditions: 1. mutual exclusion
2. hold-and-wait
3. no preemption
4. circular wait
Can eliminate deadlock by eliminating any one condition
B
D
A
C
STOP
STOP
STOP
STOP
1. Mutual Exclusion
Problem: Threads claim exclusive control of resources that they require Strategy: Eliminate locks!
Try to replace locks with atomic primitive:
int CompAndSwap(int *addr, int expected, int new) Returns 0 fail, 1 success
Wait-Free Algorithms
void add (int *val, int amt)
{
Mutex_lock(&m);
*val += amt;
Mutex_unlock(&m);
}
void add (int *val, int amt) { do {
int old = *val;
} while(!CompAndSwap(val, old, old+amt);
}
Wait-Free Algorithm: Linked List Insert
void insert (int val) {
node_t *n = Malloc(sizeof(*n)); n->val = val;
lock(&m);
n->next = head;
head = n;
unlock(&m);
void insert (int val) {
node_t *n = Malloc(sizeof(*n)); n->val = val;
do {
n->next = head;
} while (!CompAndSwap(&head,
n->next, n));
}}
2. Hold-and-Wait
Problem:Threads hold resources while waiting for additional resources
Strategy: Acquire all locks atomically once. Can release locks over time, but cannot acquire again until all have been released
How? Use a meta lock:
lock(&meta);
lock(&L1);
lock(&L2);
lock(&L3);
…
unlock(&meta);
// CS1
unlock(&L1);
// CS 2
Unlock(&L2);
lock(&meta);
lock(&L2);
lock(&L1);
unlock(&meta);
// CS1
unlock(&L1);
// CS2
Unlock(&L2);
lock(&meta);
lock(&L1);
unlock(&meta);
// CS1
unlock(&L1);
2. Hold-and-Wait
Problem:Threads hold resources while waiting for additional resources
Strategy: Acquire all locks atomically once. Can release locks over time, but cannot acquire again until all have been released
How to do this? Use a meta lock:
Disadvantages?
Must know ahead of time which locks will be needed Must be conservative (acquire any lock possibly needed) Degenerates to just having one big lock
3. No preemption
Problem: Resources (e.g., locks) cannot be forcibly removed from threads that are Strategy: if thread can’t get what it wants, release what it holds
top:
lock(A);
if (trylock(B) == -1) {
unlock(A);
Disadvantages?
goto top; }
…
Livelock:
no processes make progress, but the state of involved processes constantly changes
Classic solution: Exponential back-off
4. Circular Wait
Circular chain of threads such that each thread holds a resource (e.g., lock) being requested by next thread in the chain.
Strategy:
– decide which locks should be acquired before others – if A before B, never acquire A if B is already held!
– document this, and write code accordingly
Works well if system has distinct layers
Lock Ordering in Xv6
Creating a file requires simultaneously holding: • a lock on the directory,
• a lock on the new file’s inode,
• a lock on a disk block buffer,
• idelock,
• ptable.lock
Always acquires locks in order listed
Summary
When in doubt about correctness, better to limit concurrency (i.e., add unnecessary locks, one big lock)
Concurrency is hard, encapsulation makes it harder!
Have a strategy to avoid deadlock and stick to it
Choosing a lock order is probably most practical for reasonable performance