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 one, and we expect you to make substantial progress on an additional one.

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.

To help idenitfy 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 Required approach: 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,

• 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 Extra approach 1: Resource hierarchy

Submission filename: dp-rh.c

This implementation should ensure there is no deadlock by using the Resource hierarch 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 Extra approach 2: Message passing

Submission filename: dp-mp.c

This implementation should ensure there is no deadlock by using the Chandy/Misra solution.

You’ll probably need to add some kind of data structure to keep track of who owns which chopstick and which chopsticks are dirty, as well as functions to handle requesting chopsticks.

(The functions that handle requesting chopsticks probably need data structures to track pending requests. Depending on your implementation strategy, you might also want some way to wait for a message. My personal preference would be using something like condition variables for this operation. But perhaps(?) more simply you could do this with only mutexes by ensuring that some other thread has a lock and waiting for a lock to be released. Or, alternately, you use a very inefficient solution of a loop that locks, checking a flag variable, and unlocks until the flag is finally set.)

This is definitely more involved than the other two files, but also will give you a better understanding of how to use pthreads’ mutex objects (and other synchronization primitives, like condition variables) to solve non-trivial problems.

If correctly implemented,

• There will be no deadlock; the program will always terminate
• Philosopher 0 will always eat without waiting, starting with both chopstick 0 and chopstick n − 1 (where n is the number of philosophers).

3 Check off

Either:

• submit solutions including at least one of the extra approaches to the submission site
  • submit separate files for each approach.
  • use the filenames dp-arb.c, dp-rh.c, and/or dp-mp.c.
• OR have a TA see your program working:
  • the required approach should be completed;
  • at least one of the extra approaches should be complete or have substantial progress by the end of the lab time. (If you have extra time in the lab, we would prefer you attempt both extra approaches, but we will not require this.)

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.