Changelog:
- 25 March 2024: update deadlocking code to use barriers to hopefully make deadlock more consistent, instead of hvaing separate advice about using barriers
- 27 March 2024: remove stray backticks in commands
- 27 March 2024: correct
four approaches
tothree approaches
- 29 Oct 2024: adjust discussion of arbitrator strategy not to suggest it was not mentioned in lecture at all (sinec it was in some sections)
1 Logistics
We encourage group work with buddy programming
..
Buddy programming is when
- You each create your own code
- You share development, looking at one another’s work and so on
- You catch each other up if one is behind or stuck
2 Task
We provide a threaded implementation of the Dining Philosophers problem. This is a famous, if somewhat contrived, example of deadlock. You’ll modify it to not have deadlock. We give three approaches to this; you’ll need to do at least two and make significant progress on a third.
2.1 Deadlocking code
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
; // optional: to hopefully make deadlock more consistent
pthread_barrier_t barrier
[5];
pthread_t philosopher[5];
pthread_mutex_t chopstick
void *eat(void *arg) {
int n = (int) (long)arg;
// optional: sync up threads to make deadlock hopefully happen more consistently
(&barrier);
pthread_barrier_wait
// take two chopsticks
(&chopstick[n]);
pthread_mutex_lock("Philosopher %d got chopstick %d\n", n, n);
printf(&chopstick[(n+1)%5]);
pthread_mutex_lock("Philosopher %d got chopstick %d\n", n, (n+1)%5);
printf
("Philosopher %d is eating\n",n);
printf (1);
sleep
// set them back down
("Philosopher %d set down chopstick %d\n", n, (n+1)%5);
printf(&chopstick[(n+1)%5]);
pthread_mutex_unlock("Philosopher %d set down chopstick %d\n", n, n);
printf(&chopstick[n]);
pthread_mutex_unlockreturn NULL;
}
int main(int argc, const char *argv[]) {
(&barrier, NULL, 5);
pthread_barrier_init
for(int i = 0; i < 5; i += 1)
(&chopstick[i], NULL);
pthread_mutex_init
for(int i =0; i < 5; i += 1)
(&philosopher[i], NULL, eat, (void *)(size_t)i);
pthread_create
for(int i=0; i < 5; i += 1)
(philosopher[i], NULL);
pthread_join
for(int i=0; i < 5; i += 1)
(&chopstick[i]);
pthread_mutex_destroy
(&barrier);
pthread_barrier_destroy
return 0;
}
This can be run as
clang -O2 -lpthread dp.c && ./a.out
Because thread scheduling is somewhat random in practice, you may need to run the program several times in a row to see a deadlock.
To help identify deadlocks and other synchronization problems more reliably, we strongly recommend using ThreadSanitizer:
clang -O2 -lpthread -fsanitize=thread dp.c && ./a.out
This will run slower (though not noticably so for this program), but tries to idenitfy cases where the program does not implement a resource hierarchy strategy (that is, does not use consistent order for acquiring locks). It also will (with varying reliablity) detect several other kinds of thread usage errors (like race conditions).
2.2 Approach 1: Arbitrator
Submission filename:
dp-arb.c
Ensure there is no deadlock by using the Arbitrator solution. A correct solution can be just four lines:
- declare a global arbitrator mutex
- initialize that mutex in
main
- lock it and
- unlock it, both in
eat
, so that only one philosopher can reach for chopsticks at a time
(This deadlock strategy makes the thread take turns waiting for resources (the chopsticks), so only one thread can wait at a time. With only one thread waiting at a time, we can’t have a cyclic dependency.)
If correctly implemented,
- There will be no deadlock; the program will always terminate
- The output will never have two
Philosopher i got chopstick
lines with a differentPhilosopher j got chopstick
line in between
(When this strategy is run under ThreadSanitizer, it may report that
there is a lock order inversion
representing a potential
deadlock, because thread sanitizer is checking for the constistent lock
order solution for preventing deadlock; it’s not programmed to identify
this strategy.)
2.3 Approach 2: Resource hierarchy
Submission filename:
dp-rh.c
This implementation should ensure there is no deadlock by using the Resource hierarchy solution.
Require every philosopher to pick up their lower-numbered chopstick before their higher-numbered chopstick.
If correctly implemented,
- There will be no deadlock; the program will always terminate
- After a
Philosopher i got chopstick j
line, any followingPhilosopher i got chopstick k
line will have a k > j.
2.4 Approach 3 : Retry with backoff
Submission filename:
dp-backoff.c
This implementation should ensure there is no deadlock by acquiring the lock on the second chopstick in a way that will fail if it is already locked. If acquiring the second chopstick fails, it should set down the first chopstick, and retry the whole process.
To avoid livelock
where threads continue retrying
indefinitely, threads should use randomized exponential backoff
to limit how often retry and make it unlikely that two threads which
both decide to retry at the same time end up retrying at the same
time.
For example:
- after locking fails the first time, a thread could wait a pseudorandomly chosen amount of time between 50 and 100 microseconds
- after locking fails a second time, a thread could wait a pseudorandomly chosen amount of time between 100 and 200 microseconds
- after locking fails a third time, a thread could wait a pseudorandomly chosen amount of time between 200 and 400 microseconds
- and so on
Your implementation can vary the amount of time threads wait so long as:
- the average increases by a multiplicative factor each time (to keep threads from hogging all the processor time just retrying); and
- the exact amount of time is always randomized (so threads that started being exactly in sync with each other will not stay in sync)
You can use:
pthread_mutex_trylock
to attempt to get a mutex lock and detect when this is not immediately possible.pthread_mutex_trylock
will return 0 when successful, and some non-zero value when locking fails.rand()
to generate pseudorandom numbers andusleep()
ornanosleep()
to have threads wait for varying amounts of time.
If successful:
- There will be no deadlock; the program will always terminate.
- One philosopher will usually end up trying to acquire the lock several times before succeeding.
3 Check off
Either:
- submit solutions for all the approaches
- OR have a TA see your program working:
- at least two of the required approaches should be completed;
- the remaining approach should have significant progress
For an in-person checkoff, TAs may ask to see your code and ask a
questions along the lines of why this line here instead of there?
which all team members should be prepared to answer.