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>

pthread_barrier_t barrier; // optional: to hopefully make deadlock more consistent

pthread_t philosopher[5];
pthread_mutex_t chopstick[5];

void *eat(void *arg) {
    int n = (int) (long)arg;

    // optional: sync up threads to make deadlock hopefully happen more consistently
    pthread_barrier_wait(&barrier);

    // take two chopsticks
    pthread_mutex_lock(&chopstick[n]);
    printf("Philosopher %d got chopstick %d\n", n, n);
    pthread_mutex_lock(&chopstick[(n+1)%5]);
    printf("Philosopher %d got chopstick %d\n", n, (n+1)%5);
    
    printf ("Philosopher %d is eating\n",n);
    sleep(1);
    
    // set them back down
    printf("Philosopher %d set down chopstick %d\n", n, (n+1)%5);
    pthread_mutex_unlock(&chopstick[(n+1)%5]);
    printf("Philosopher %d set down chopstick %d\n", n, n);
    pthread_mutex_unlock(&chopstick[n]);
    return NULL;
}

int main(int argc, const char *argv[]) {
    pthread_barrier_init(&barrier, NULL, 5);

    for(int i = 0; i < 5; i += 1)
        pthread_mutex_init(&chopstick[i], NULL);

    for(int i =0; i < 5; i += 1)
        pthread_create(&philosopher[i], NULL, eat, (void *)(size_t)i);

    for(int i=0; i < 5; i += 1)
        pthread_join(philosopher[i], NULL);

    for(int i=0; i < 5; i += 1)
        pthread_mutex_destroy(&chopstick[i]);

    pthread_barrier_destroy(&barrier);

    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:

1. declare a global arbitrator mutex
2. initialize that mutex in main
3. lock it and
4. 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 different Philosopher 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 following Philosopher 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 and usleep() or nanosleep() 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.