# Dining philosophers problem

• Post author:

The dining philosophers problem was formulated by Edsger Dijkstra in 1965. The problem illustrates synchronization issues in systems made up of concurrent tasks. The objective of the problem is to have progress and avoid deadlock in systems. Also, the entities needing resources should get them in reasonable time and not face starvation of resources.

### 1.0 The dining philosophers problem

The dining philosophers problem can be stated as follows.

1. Five philosophers with plates of spaghetti are seated around a table. There are five forks placed on the table such that there is a fork between the plates of any two adjacent philosophers.
2. The philosophers just do two things – think and eat for small duration of times. All philosophers have an infinite capacity to eat. Also, there is an infinite supply of spaghetti, which is replenished automatically in the plates as the philosophers eat.
3. The philosophers do not talk with one another. No philosopher knows whether the others want to think or eat.
4. A philosopher can only eat after picking up the forks on the left and right of his or her plate. A philosopher picks up the two forks, one at a time, subject to availability. If a fork is not available, the philosopher blocks for the fork to become available.
5. After a philosopher finishes eating, he or she puts the forks in their original place.
6. The objective of the problem is to develop an algorithm which will ensure that the scenario of the philosophers thinking and eating, with above-mentioned constraints, progresses indefinitely without any deadlock. If the situation is left laissez-faire, all five philosophers might feel hungry at a point of time, pick up the fork at the left, and block for the second fork. Since no philosopher releases a fork, the system gets into a deadlock. So we need an algorithm for the philosophers to think and eat and also avoid the deadlock. Also, it needs to be ensured that all philosophers get a fair chance to eat and no philosopher starves for spaghetti.

### 2.0 The rationale of the dining philosophers problem

What is the relevance of the dining philosophers problem? In real life, the philosophers would be much wiser than to get into this situation. The dining philosophers problem is an example of deadlock in multi-process or multi-threaded systems. Each philosopher represents a thread of execution. Forks are resources that threads use exclusively to get the work done.

There are four conditions necessary for deadlock to occur in systems.

1. Mutual exclusion. The threads must hold at least one resource in exclusively. The philosophers hold forks in a non-shareable exclusive mode.
2. Hold and wait. The threads must hold at least one resource and wait for another while holding the earlier one. A philosopher holds one fork and, if the other fork has been taken by the neighbor, waits for the second fork.
3. Resources cannot be preempted. A philosopher eats and puts the forks down voluntarily. It is not possible to take a fork from a philosopher.
4. Circular wait. A set of threads, T0, T1, …, T(n-1) must exist where, T0 is waiting for a resource held by T1, T1 is waiting for a resource held by T2, etc. And T(n-1) is waiting for a resource held by T0. This happens when all philosophers pick up the fork on the left and wait for getting the fork on the right.

Since the dining philosopher problem represents a common problem, which is deadlock in multi-threaded systems, we need to solve it and use the principles in other concurrent multi-threaded systems.

There are many solutions to the dining philosophers problem. We will look at two of them. The first involves ordering of resources. The forks are numbered and the philosophers are required to pick up forks with numbers in increasing order. The second involves the use of a central arbitrator, say a waiter, to help the philosophers in their business of thinking and eating.

### 3.0 Solution using ordering of resources

Let the philosophers be code named P0, P1,.., P4. The philosophers are seated P0, P1, .., P4, counter-clockwise. and the forks are numbered f0, f1, …, f4. The fork f0 is kept to the left of philosopher P0. A philosopher is required to pick up the lower numbered fork first. If the lower numbered fork is not available, the philosopher blocks for it. So, reviewing the earlier deadlock scenario, P0 pics up f0, P1 picks up f1, etc. But P4 cannot pick up f4 as P4 has f0 and f4 forks around her. So P4 has to block for fork f0. And we have broken the circular wait requirement for the deadlock. P3, already having the f3 fork can pick up f4 as well and go ahead and eat. And, there is no deadlock.

The operation of picking up a fork is an exclusive operation as only one philosopher can pick up a fork at a time and forks cannot be shared. Only, after a philosopher puts back (releases) a fork, another philosopher can pick it up. To take care of these requirements, forks are implemented as Pthreads mutexes. A philosopher picks up a fork by locking the concerned mutex and releases it by unlocking it.

Here is the program for dining philosophers with ordering of resources.

```/*
*
*   dining-philosophers.c: Program to demonstrate the dining philosophers
*                          problem with ordering of resources (forks)
*
*/

#include <sys/types.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <errno.h>
#include <unistd.h>

// Buffer data structures
#define MAX_BUFFERS 10
char buf [MAX_BUFFERS] [100];
int buffer_index;
int buffer_print_index;

int buffers_available = MAX_BUFFERS;
int lines_to_print = 0;

void *philosopher (void *arg);
void *spooler (void *arg);
void print_string (const char *const str);

int main (int argc, char **argv)
{
int i, r;

// initialization
buffer_index = buffer_print_index = 0;
time_t now = time (NULL);

srand ((unsigned int) (now % 937));

// Create spooler
if ((r = pthread_create (&tid_spooler, NULL, spooler, NULL)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

for (i = 0; i < 5; i++) {
if ((r = pthread_create (&tid_philosopher [i], NULL, philosopher, (void *) &thread_no [i])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
}
// Wait for philosophers to terminate
for (i = 0; i < 5; i++)
if ((r = pthread_join (tid_philosopher [i], NULL)) == -1) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

// No more strings to print?
while (lines_to_print) sleep (1);
// terminate spooler
if ((r = pthread_cancel (tid_spooler)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

exit (0);
}

/* philosopher: think and eat
Philosopher 0 uses forks 0 and 1
Philosopher 1 uses forks 1 and 2
Philosopher 2 uses forks 2 and 3
Philosopher 3 uses forks 3 and 4
Philosopher 4 uses forks 0 and 4
*/
void *philosopher (void *arg)
{
int i, r, fork1, fork2;
int my_id = *((int *) arg);
char my_str [100];

while (1) {
// think or eat?
bool eat = rand () % 2;
if (eat) {
sprintf (my_str, "P %d: %ld Will eat!\n", my_id, time (NULL));
print_string (my_str);
// get first fork
fork1 = (my_id == 4) ? 0 : my_id;
if ((r = pthread_mutex_lock (&fork_mutex [fork1])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
// get second fork
fork2 = (my_id == 4) ? 4 : my_id + 1;
if ((r = pthread_mutex_lock (&fork_mutex [fork2])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
sprintf (my_str, "P %d: %ld Got forks: %d and %d\n", my_id, time (NULL), fork1, fork2);
print_string (my_str);
sprintf (my_str, "P %d: %ld Eating....\n", my_id, time (NULL));
print_string (my_str);

sleep (rand () % 5 + 1);

// release first fork
if ((r = pthread_mutex_unlock (&fork_mutex [fork1])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
// release second fork
if ((r = pthread_mutex_unlock (&fork_mutex [fork2])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
}
else { //think
sprintf (my_str, "P %d: %ld Thinking....\n", my_id, time (NULL));
print_string (my_str);
sleep (rand () % 5 + 1);
}
sprintf (my_str, "P %d: %ld Finished %s", my_id, time (NULL), (eat) ? "eating.\n" : "thinking.\n");
print_string (my_str);
}
}

// print a string on the terminal
void print_string (const char *const str)
{
int r;

// Lock mutex
if ((r = pthread_mutex_lock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

while (!buffers_available)

int j = buffer_index;
buffer_index++;
if (buffer_index == MAX_BUFFERS)
buffer_index = 0;
buffers_available--;

strcpy (buf [j], str);
lines_to_print++;

// Unlock mutex
if ((r = pthread_mutex_unlock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

}
// There is only one spooler thread
void *spooler (void *arg)
{
int r;

while (1) {  // forever
// Lock mutex
if ((r = pthread_mutex_lock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
while (!lines_to_print)

printf ("%s", buf [buffer_print_index]);
lines_to_print--;

buffer_print_index++;
if (buffer_print_index == MAX_BUFFERS)
buffer_print_index = 0;

buffers_available++;

// Unlock mutex
if ((r = pthread_mutex_unlock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

}
}
```

We can compile and run the above program as below.

```\$ gcc dining-philosophers.c -o dining-philosophers -lpthread
\$ ./dining-philosophers
P 1: 1630258433 Thinking....
P 2: 1630258433 Thinking....
P 0: 1630258433 Will eat!
P 0: 1630258433 Got forks: 0 and 1
P 4: 1630258433 Thinking....
P 3: 1630258433 Will eat!
P 0: 1630258433 Eating....
P 3: 1630258433 Got forks: 3 and 4
P 3: 1630258433 Eating....
P 1: 1630258434 Finished thinking.
P 1: 1630258434 Will eat!
P 3: 1630258434 Finished eating.
P 3: 1630258434 Will eat!
P 3: 1630258434 Got forks: 3 and 4
P 3: 1630258434 Eating....
P 3: 1630258435 Finished eating.
P 3: 1630258435 Thinking....
P 0: 1630258435 Finished eating.
P 0: 1630258435 Thinking....
P 1: 1630258435 Got forks: 1 and 2
P 1: 1630258435 Eating....
P 4: 1630258437 Finished thinking.
P 4: 1630258437 Thinking....
P 0: 1630258437 Finished thinking.
P 0: 1630258437 Will eat!
P 2: 1630258438 Finished thinking.
P 2: 1630258438 Thinking....
P 1: 1630258438 Finished eating.
P 1: 1630258438 Thinking....
P 0: 1630258438 Got forks: 0 and 1
P 0: 1630258438 Eating....             ..... P0 is eating
P 2: 1630258440 Finished thinking.
P 2: 1630258440 Thinking....
P 3: 1630258440 Finished thinking.
P 3: 1630258440 Will eat!
P 3: 1630258440 Got forks: 3 and 4
P 3: 1630258440 Eating....             .....  P3 is eating
P 4: 1630258441 Finished thinking.
P 4: 1630258441 Will eat!              ..... P4 decides to eat
P 1: 1630258441 Finished thinking.
P 1: 1630258441 Thinking....
P 3: 1630258442 Finished eating.       ..... P3 finished eating
P 3: 1630258442 Will eat!
P 3: 1630258442 Got forks: 3 and 4
P 3: 1630258442 Eating....             ..... P3 gets to eat again, but not P4, because P0 is eating
P 0: 1630258443 Finished eating.       ..... P0 finished eating
P 0: 1630258443 Will eat!
P 0: 1630258443 Got forks: 0 and 1
P 0: 1630258443 Eating....             ..... P0 again gets to eat, but not P4, because P3 is eating
P 2: 1630258444 Finished thinking.
P 2: 1630258444 Thinking....
P 3: 1630258444 Finished eating.       ..... P3 finished eating, but P4 can't start because P0 is eating
P 3: 1630258444 Thinking....
P 1: 1630258445 Finished thinking.
P 1: 1630258445 Thinking....
P 2: 1630258446 Finished thinking.
P 2: 1630258446 Will eat!
P 2: 1630258446 Got forks: 2 and 3
P 2: 1630258446 Eating....
P 0: 1630258447 Finished eating.       ...... P0 finished eating, Can P4 start now?
P 0: 1630258447 Will eat!
P 0: 1630258447 Got forks: 0 and 1     ...... No way! P0 gets the forks to start eating again.
P 0: 1630258447 Eating....
P 3: 1630258447 Finished thinking.
P 3: 1630258447 Thinking....
P 2: 1630258449 Finished eating.
P 2: 1630258449 Thinking....
P 0: 1630258449 Finished eating.        ...... P0 finished eating
P 0: 1630258449 Thinking....
P 4: 1630258449 Got forks: 0 and 4
P 4: 1630258449 Eating....               ..... At long last, P4 gets to eat. P4 decided to eat at
1630258441 and gets to eat 8 seconds later. When she
wanted to eat both P0 and P3 were eating. They both finished and,
since then, P3 has eaten once more and P0 has eaten twice.

P 1: 1630258449 Finished thinking.
P 1: 1630258449 Thinking....
P 3: 1630258449 Finished thinking.
P 3: 1630258449 Thinking....
P 3: 1630258450 Finished thinking.
....
```

It appears that the above solution is not fair. P0 and P3 dominate the use of forks and P4 has to wait a lot for her turn to eat. So, although, the problem of deadlock is resolved, there is still the problem of starvation of resources for the threads.

### 4.0 Solution using a central arbitrator

The second solution is to take the help of a central arbitrator, the waiter. The waiter is implemented as a mutex. Only one philosopher can eat at any time, even though there are five forks. So, this has less parallelism than the first solution. The program is as below.

```/*
*
*   dining-philosophers-ca.c: Program to demonstrate the dining philosophers
*                             problem with central arbitrator
*
*/

#include <sys/types.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <errno.h>
#include <unistd.h>

// Buffer data structures
#define MAX_BUFFERS 10
char buf [MAX_BUFFERS] [100];
int buffer_index;
int buffer_print_index;

int buffers_available = MAX_BUFFERS;
int lines_to_print = 0;

void *philosopher (void *arg);
void *spooler (void *arg);
void print_string (const char *const str);

int main (int argc, char **argv)
{
int i, r;

// initialization
buffer_index = buffer_print_index = 0;
time_t now = time (NULL);

srand ((unsigned int) (now % 937));

// Create spooler
if ((r = pthread_create (&tid_spooler, NULL, spooler, NULL)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

for (i = 0; i < 5; i++) {
if ((r = pthread_create (&tid_philosopher [i], NULL, philosopher, (void *) &thread_no [i])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
}
// Wait for philosophers to terminate
for (i = 0; i < 5; i++)
if ((r = pthread_join (tid_philosopher [i], NULL)) == -1) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

// No more strings to print?
while (lines_to_print) sleep (1);
// terminate spooler
if ((r = pthread_cancel (tid_spooler)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

exit (0);
}

/* philosopher: think and eat
*/
void *philosopher (void *arg)
{
int i, r, fork1, fork2;
int my_id = *((int *) arg);
char my_str [100];

while (1) {
// think or eat?
bool eat = rand () % 2;
if (eat) {
if ((r = pthread_mutex_lock (&waiter_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
sprintf (my_str, "P %d: %ld Will eat!\n", my_id, time (NULL));
print_string (my_str);
// get first fork
fork1 = my_id;
if ((r = pthread_mutex_lock (&fork_mutex [fork1])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
// get second fork
fork2 = (my_id == 4) ? 0 : my_id + 1;
if ((r = pthread_mutex_lock (&fork_mutex [fork2])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
sprintf (my_str, "P %d: %ld Got forks: %d and %d\n", my_id, time (NULL), fork1, fork2);
print_string (my_str);
sprintf (my_str, "P %d: %ld Eating....\n", my_id, time (NULL));
print_string (my_str);

sleep (rand () % 5 + 1);

// release first fork
if ((r = pthread_mutex_unlock (&fork_mutex [fork1])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
// release second fork
if ((r = pthread_mutex_unlock (&fork_mutex [fork2])) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
sprintf (my_str, "P %d: %ld Finished eating.\n", my_id, time (NULL));
print_string (my_str);
// release waiter
if ((r = pthread_mutex_unlock (&waiter_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
}
else { //think
sprintf (my_str, "P %d: %ld Thinking....\n", my_id, time (NULL));
print_string (my_str);
sleep (rand () % 5 + 1);
sprintf (my_str, "P %d: %ld Finished thinking.\n", my_id, time (NULL));
print_string (my_str);
}
}
}

// print a string on the terminal
void print_string (const char *const str)
{
int r;

// Lock mutex
if ((r = pthread_mutex_lock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

while (!buffers_available)

int j = buffer_index;
buffer_index++;
if (buffer_index == MAX_BUFFERS)
buffer_index = 0;
buffers_available--;

strcpy (buf [j], str);
lines_to_print++;

// Unlock mutex
if ((r = pthread_mutex_unlock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

}
// There is only one spooler thread
void *spooler (void *arg)
{
int r;

while (1) {  // forever
// Lock mutex
if ((r = pthread_mutex_lock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}
while (!lines_to_print)

printf ("%s", buf [buffer_print_index]);
lines_to_print--;

buffer_print_index++;
if (buffer_print_index == MAX_BUFFERS)
buffer_print_index = 0;

buffers_available++;

// Unlock mutex
if ((r = pthread_mutex_unlock (&buf_mutex)) != 0) {
fprintf (stderr, "Error = %d (%s)\n", r, strerror (r)); exit (1);
}

}
}
```

Now, P4 does not have to worry about picking up the smaller numbered fork. Like anybody else, she can pick up the fork on the left and, then, the fork on the right. We can compile and run the above program as below.

```\$ gcc dining-philosophers-ca.c -o dining-philosophers-ca -lpthread
\$ ./dining-philosophers-ca
P 0: 1630295788 Thinking....
P 1: 1630295788 Thinking....
P 2: 1630295788 Will eat!
P 2: 1630295788 Got forks: 2 and 3
P 2: 1630295788 Eating....
P 0: 1630295792 Finished thinking.
P 0: 1630295792 Thinking....
P 1: 1630295792 Finished thinking.
P 1: 1630295792 Thinking....
P 0: 1630295793 Finished thinking.
P 0: 1630295793 Thinking....
P 2: 1630295793 Finished eating.
P 2: 1630295793 Will eat!
P 2: 1630295793 Got forks: 2 and 3
P 2: 1630295793 Eating....
P 2: 1630295795 Finished eating.
P 2: 1630295795 Thinking....
P 4: 1630295795 Will eat!
P 4: 1630295795 Got forks: 4 and 0
P 4: 1630295795 Eating....
P 1: 1630295795 Finished thinking.
P 0: 1630295796 Finished thinking.
P 0: 1630295796 Thinking....
P 4: 1630295797 Finished eating.
P 4: 1630295797 Will eat!
P 4: 1630295797 Got forks: 4 and 0
P 4: 1630295797 Eating....
P 4: 1630295798 Finished eating.
P 4: 1630295798 Thinking....
P 1: 1630295798 Will eat!
P 1: 1630295798 Got forks: 1 and 2
P 1: 1630295798 Eating....
P 4: 1630295799 Finished thinking.
P 4: 1630295799 Thinking....
P 0: 1630295800 Finished thinking.
P 2: 1630295800 Finished thinking.
P 2: 1630295800 Thinking....
P 4: 1630295802 Finished thinking.
P 1: 1630295802 Finished eating.
P 1: 1630295802 Will eat!
P 1: 1630295802 Got forks: 1 and 2
P 1: 1630295802 Eating....
P 2: 1630295804 Finished thinking.
P 2: 1630295804 Thinking....
P 1: 1630295805 Finished eating.
P 1: 1630295805 Will eat!
P 1: 1630295805 Got forks: 1 and 2
P 1: 1630295805 Eating....
P 2: 1630295808 Finished thinking.
P 1: 1630295809 Finished eating.
P 1: 1630295809 Will eat!
P 1: 1630295809 Got forks: 1 and 2
P 1: 1630295809 Eating....
P 1: 1630295811 Finished eating.
P 1: 1630295811 Will eat!
P 1: 1630295811 Got forks: 1 and 2
P 1: 1630295811 Eating....
P 1: 1630295812 Finished eating.
P 1: 1630295812 Thinking....
P 0: 1630295812 Will eat!
P 0: 1630295812 Got forks: 0 and 1
P 0: 1630295812 Eating....
P 0: 1630295814 Finished eating.
P 0: 1630295814 Thinking....
P 2: 1630295814 Will eat!
P 2: 1630295814 Got forks: 2 and 3
P 2: 1630295814 Eating....
P 1: 1630295817 Finished thinking.
P 1: 1630295817 Thinking....
P 1: 1630295818 Finished thinking.
P 1: 1630295818 Thinking....
P 0: 1630295818 Finished thinking.
P 0: 1630295818 Thinking....
P 2: 1630295819 Finished eating.
P 2: 1630295819 Thinking....
P 4: 1630295819 Will eat!
P 4: 1630295819 Got forks: 4 and 0
P 4: 1630295819 Eating....
P 0: 1630295821 Finished thinking.
P 4: 1630295821 Finished eating.
P 4: 1630295821 Thinking....
P 3: 1630295821 Will eat!
P 3: 1630295821 Got forks: 3 and 4
P 3: 1630295821 Eating....
P 1: 1630295823 Finished thinking.
P 2: 1630295823 Finished thinking.
P 2: 1630295823 Thinking....
P 4: 1630295824 Finished thinking.
P 4: 1630295824 Thinking....
P 3: 1630295824 Finished eating.
P 3: 1630295824 Thinking....
P 0: 1630295824 Will eat!
P 0: 1630295824 Got forks: 0 and 1
P 0: 1630295824 Eating....
...
```