The Dining Philosophers

In this lesson, we will discuss another classical concurrency problem, the dining philosophers problem.

We'll cover the following

One of the most famous concurrency problems posed, and solved, by Dijkstra, is known as the dining philosopher’s problem“Hierarchical ordering of sequential processes” by E.W. Dijkstra. Available online here: http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF. Presents numerous concurrency problems, including Dining Philosophers. The Wikipedia page about this problem is also useful.. The problem is famous because it is fun and somewhat intellectually interesting; however, its practical utility is low. However, its fame forces its inclusion here; indeed, you might be asked about it in some interview, and you’d really hate us if you miss that question and don’t get the job. Conversely, if you get the job, please feel free to send us a nice note, or some stock options.

The basic setup for the problem is this (as shown in the figure above): assume there are five “philosophers” sitting around a table. Between each pair of philosophers is a single fork (and thus, five total). The philosophers each have times where they think and don’t need any forks, and times where they eat. In order to eat, a philosopher needs two forks, both the one on their left and the one on their right. The contention for these forks, and the synchronization problems that ensue, are what makes this a problem we study in concurrent programming.

Here is the basic loop of each philosopher, assuming each has a unique thread identifier p from 0 to 4 (inclusive):

Press + to interact
while (1) {

    think();

    get_forks(p);

    eat();

    put_forks(p);

}

The key challenge, then, is to write the routines get_forks() and put_forks() such that there is no deadlock, no philosopher starves and never gets to eat, and concurrency is high (i.e., as many philosophers can eat at the same time as possible). Following Downey’s solutions“The Little Book of Semaphores” by A.B. Downey. Available at the following site: http://greenteapress.com/semaphores/. A nice (and free!) book about semaphores. Lots of fun problems to solve, if you like that sort of thing., we’ll use a few helper functions to get us towards a solution. They are:

Press + to interact
int left(int p)  { return p; }
int right(int p) { return (p + 1) % 5; }

When philosopher p wishes to refer to the fork on their left, they simply call left(p). Similarly, the fork on the right of a philosopher p is referred to by calling right(p); the modulo operator therein handles the one case where the last philosopher (p=4) tries to grab the fork on their right, which is fork 0. We’ll also need some semaphores to solve this problem. Let us assume we have five, one for each fork: sem_t forks[5].

Broken solution

We attempt our first solution to the problem. Assume we initialize each semaphore (in the forks array) to a value of 1. Assume also that each philosopher knows its own number (p). We can thus write the get_forks() and put_forks() routine as shown below.

Press + to interact
void get_forks(int p) {

    sem_wait(&forks[left(p)]);

    sem_wait(&forks[right(p)]);

}



void put_forks(int p) {

    sem_post(&forks[left(p)]);

    sem_post(&forks[right(p)]);

}

The intuition behind this (broken) solution is as follows. To acquire the forks, we simply grab a “lock” on each one: first the one on the left, and then the one on the right. When we are done eating, we release them. Simple, no? Unfortunately, in this case, simple means broken. Can you see the problem that arises? Think about it.

The problem is the deadlock. If each philosopher happens to grab the fork on their left before any philosopher can grab the fork on their right, each will be stuck holding one fork and waiting for another, forever. Specifically, philosopher 0 grabs fork 0, philosopher 1 grabs fork 1, philosopher 2 grabs fork 2, philosopher 3 grabs fork 3, and philosopher 4 grabs fork 4; all the forks are acquired, and all the philosophers are stuck waiting for a fork that another philosopher possesses.

We’ll study deadlock in more detail soon; for now, it is safe to say that this is not a working solution.

A solution: breaking the dependency

The simplest way to attack this problem is to change how forks are acquired by at least one of the philosophers; indeed, this is how Dijkstra himself solved the problem. Specifically, let’s assume that philosopher 4 (the highest numbered one) gets the forks in a different order than the others (code given below); the put_forks() code remains the same.

Press + to interact
void get_forks(int p) {

    if (p == 4) {

        sem_wait(&forks[right(p)]);

        sem_wait(&forks[left(p)]);

    } else {

        sem_wait(&forks[left(p)]);

        sem_wait(&forks[right(p)]);

    }

}

Because the last philosopher tries to grab right before left, there is no situation where each philosopher grabs one fork and is stuck waiting for another; the cycle of waiting is broken. Think through the ramifications of this solution, and convince yourself that it works.

There are other “famous” problems like this one, e.g., the cigarette smoker’s problem or the sleeping barber problem. Most of them are just excuses to think about concurrency; some of them have fascinating names. Look them up if you are interested in learning more, or just getting more practice thinking in a concurrent manner“The Little Book of Semaphores” by A.B. Downey. Available at the following site: http://greenteapress.com/semaphores/. A nice (and free!) book about semaphores. Lots of fun problems to solve, if you like that sort of thing..

You can run the above-mentioned solution in the code widget below:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#include "common.h"
#include "common_threads.h"

#ifdef linux
#include <semaphore.h>
#elif __APPLE__
#include "zemaphore.h"
#endif

typedef struct {
    int num_loops;
    int thread_id;
} arg_t;

sem_t forks[5];
sem_t print_lock;

void space(int s) {
    Sem_wait(&print_lock);
    int i;
    for (i = 0; i < s * 10; i++)
        printf(" ");
}

void space_end() {
    Sem_post(&print_lock);
}

int left(int p)  {
    return p;
}

int right(int p) {
    return (p + 1) % 5;
}

void get_forks(int p) {
    if (p == 4) {
        space(p); printf("4 try %d\n", right(p)); space_end();
        Sem_wait(&forks[right(p)]);
        space(p); printf("4 try %d\n", left(p)); space_end();
        Sem_wait(&forks[left(p)]);
    } else {
        space(p); printf("try %d\n", left(p)); space_end();
        Sem_wait(&forks[left(p)]);
        space(p); printf("try %d\n", right(p)); space_end();
        Sem_wait(&forks[right(p)]);
    }
}

void put_forks(int p) {
    Sem_post(&forks[left(p)]);
    Sem_post(&forks[right(p)]);
}

void think() {
    return;
}

void eat() {
    return;
}

void *philosopher(void *arg) {
    arg_t *args = (arg_t *) arg;

    space(args->thread_id); printf("%d: start\n", args->thread_id); space_end();

    int i;
    for (i = 0; i < args->num_loops; i++) {
        space(args->thread_id); printf("%d: think\n", args->thread_id); space_end();
        think();
        get_forks(args->thread_id);
        space(args->thread_id); printf("%d: eat\n", args->thread_id); space_end();
        eat();
        put_forks(args->thread_id);
        space(args->thread_id); printf("%d: done\n", args->thread_id); space_end();
    }
    return NULL;
}
                                                                             
int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "usage: dining_philosophers <num_loops>\n");
        exit(1);
    }
    printf("dining: started\n");
    
    int i;
    for (i = 0; i < 5; i++) 
        Sem_init(&forks[i], 1);
    Sem_init(&print_lock, 1);

    pthread_t p[5];
    arg_t a[5];
    for (i = 0; i < 5; i++) {
        a[i].num_loops = atoi(argv[1]);
        a[i].thread_id = i;
        Pthread_create(&p[i], NULL, philosopher, &a[i]);
    }

    for (i = 0; i < 5; i++) 
        Pthread_join(p[i], NULL); 

    printf("dining: finished\n");
    return 0;
}

Get hands-on with 1400+ tech skills courses.