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 to three 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

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,

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