1 Logistics

We encourage group work with buddy programming..

Buddy programming is when

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 four 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_t philosopher[5];
pthread_mutex_t chopstick[5];

void *eat(void *arg) {
    int n = (int) (long)arg;
    // 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[]) {
    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]);

    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.

(You may be able to make a deadlock occur more reliably by having all threads try to lock at closer to the same time with a barrier. Declaring a global

pthread_barrier_t barrier;

which is initialized with

pthread_barrier_init(&barrier, 5);

and having each thread wait on the barrier before acquiring their first lock:

pthread_barrier_wait(&barrier);

.)

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 is not one of the deadlock prevention strategies we discussed in lecture, but it 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,

(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,

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:

Your implementation can vary the amount of time threads wait so long as:

You can use:

If successful:

3 Check off

Either:

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.