Deadlock

A deadlock is a circular waiting condition in which two or more threads are blocked forever, waiting for each other to release a resource. Deadlocks are a common problem in concurrent systems, and they can be difficult to detect and debug.

Do you remember the Dining Philosophers problem from CS 105?
Do I ever! A group of people devoted to eating spaghetti? What's not to love?!?!
Meh. I thought I could forget about that one.
Well, it's a classic example of a problem where a careless solution can lead to deadlock. Let's review it.
September 19 is International Talk Like a Pirate Day. Arrr! Can we make it about pirates instead?
Sure, why not? We can talk about pirates and deadlocks. Arrr!

The Dining Pirates Problem

In the dining pirates problem, a group of pirates are sitting around a table, and between each pair of pirates there is a single cutlass, as shown below:

Pirates alternate between three states:

Eating: A pirate must have two cutlasses to eat.
Arguing: A pirate puts down both cutlasses and argues about treasure.
Hungry: The pirate wants to eat (but currently can't because they don't have both cutlasses).

The problem is to design a synchronization protocol that both prevents deadlock and ensures that no pirate starves.

Hay! Why do they need two cutlasses to eat?
It's a pirate thing. You wouldn't understand.
Actually, in the history of eating implements, there was a time period when people really did eat with two knives. One of those knives evolved into the fork we know today, but that actually happened fairly late. In the US, the fork didn't become common until the 19th century, as people had switched to using a knife and a spoon for eating. There's a whole difference between North America and Europe when it comes to how to use a knife and fork to eat because of this difference in the adoption of different eating utensils.
Anyhoo, back to the pirates.

Dijkstra proposed the original Dining Philosophers problem in 1965 as a way to illustrate the problem of deadlock in concurrent systems. In his version, the problem involves a group of philosophers sitting at a round table with a fork between each pair of philosophers where they are all eating spaghetti. Each philosopher must have two forks to eat. The philosophers alternate between hungry/eating and thinking.

It would have made more sense if they had been eating Chinese food with chopsticks, but that's another story.

Here's some code for the dining pirates problem:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include "synch.h"

#define NUM_PIRATES 5

struct lock *cutlass[NUM_PIRATES];
pthread_t pirate_thread[NUM_PIRATES];

void
rand_sleep(void)
{
        usleep(100000 + (rand() % 200000));  /* Sleep for 100-250 ms */
}

void *
pirate(void *arg)
{
        int i = *(int *)arg;
        int left = i;
        int right = (i + 1) % NUM_PIRATES;

        while (1) {
                /* Argue about treasure */
                printf("Pirate %d be arguin' about the treasure...\n", i);
                rand_sleep();

                printf("Pirate %d be eyein' the cutlasses...\n", i);

                /* Grab the left cutlass */
                lock_acquire(cutlass[left]);
                printf("Pirate %d grabbed the left cutlass %d!\n", i, left);

                /* Momentary confusion from too much grog */
                rand_sleep();

                /* Grab the right cutlass */
                lock_acquire(cutlass[right]);
                printf("Pirate %d grabbed the right cutlass %d!\n", i, right);

                /* Use both cutlasses */
                printf("Pirate %d be eatin', swingin' both cutlasses!\n", i);
                rand_sleep();

                /* Release the cutlasses */
                lock_release(cutlass[right]);
                lock_release(cutlass[left]);
        }

        return NULL;
}

int
main(void)
{
        int i;
        int pirate_ids[NUM_PIRATES];

        /* Initialize the locks */
        for (i = 0; i < NUM_PIRATES; i++) {
                char lock_name[20];
                snprintf(lock_name, sizeof(lock_name), "cutlass_%d", i);
                cutlass[i] = lock_create(lock_name);
                if (cutlass[i] == NULL) {
                        fprintf(stderr, "Failed to create lock for cutlass %d\n", i);
                        exit(1);
                }
        }

        /* Create the pirate threads */
        for (i = 0; i < NUM_PIRATES; i++) {
                pirate_ids[i] = i;
                if (pthread_create(&pirate_thread[i], NULL, pirate, &pirate_ids[i]) != 0) {
                        fprintf(stderr, "Failed to create thread for pirate %d\n", i);
                        exit(1);
                }
        }

        /* Allow ten seconds of pirate fun... */
        sleep(10);

        /* ...then kill the fun in case you leave it running in OnlineGDB or the CS 134 server */
        printf("Avast, ye scurvy dogs! The Royal Navy be here! The pirates be done for!\n");

        /* We won't clean up since we're might be deadlocked, just exit */

        return 0;
}

When we run this code, we're likely to see results similar to the following:

Pirate 0 be arguin' about the treasure...
Pirate 1 be arguin' about the treasure...
Pirate 2 be arguin' about the treasure...
Pirate 3 be arguin' about the treasure...
Pirate 4 be arguin' about the treasure...
Pirate 0 be eyein' the cutlasses...
Pirate 0 grabbed the left cutlass 0!
Pirate 1 be eyein' the cutlasses...
Pirate 1 grabbed the left cutlass 1!
Pirate 2 be eyein' the cutlasses...
Pirate 2 grabbed the left cutlass 2!
Pirate 4 be eyein' the cutlasses...
Pirate 4 grabbed the left cutlass 4!
Pirate 3 be eyein' the cutlasses...
Pirate 3 grabbed the left cutlass 3!

and then nothing more because everyone is stuck waiting (well, actually nothing for ten seconds, then the program exits to avoid hanging around forever).

Wait. Why are they all waiting again?
It's a deadlock. They're all waiting for the cutlass that the pirate next to them has, around in a circle. They each have the left cutlass, but they're waiting for the right cutlass, which the pirate next to them already has.
Oh, around in a circle like chasing your tail? I can relate to that!

You can try the code yourself, but be aware that there is some randomness. Sometimes it may actually take a while to deadlock. Since the program stops after ten seconds, if it doesn't deadlock before then, just try running it again.

Try the code in Online GDB

A Simple Fix

When Dijkstra proposed the Dining Philosophers problem (originally on a homework assignment for his students), he imagined a simple solution: If the issue is a circular wait, we just need to break the circle. We can do so by making one of the pirates pick up the cutlasses in the opposite order.

We can thus change the code from

        int left = i;
        int right = (i + 1) % NUM_PIRATES;

        int left = i;
        int right = (i + 1) % NUM_PIRATES;
        if (right < left) {
            int temp = left;
            left = right;
            right = temp;
        }

In this version, cutlasses have an intrinsic order, and we always pick up the lowest-numbered cutlass first. As a result, the last pirate will pick up the cutlasses in the opposite order from all the others.

Key Idea: Break the circular wait by imposing a total order on the resources.

An Issue with the Fix

If we run this code with this pipeline to count how often each pirate gets to eat

./dp-okay | fgrep 'be eatin' | sort | uniq -c

we might see (fairly repeatable) results like this:

   9 Pirate 0 be eatin', swingin' both cutlasses!
  13 Pirate 1 be eatin', swingin' both cutlasses!
  14 Pirate 2 be eatin', swingin' both cutlasses!
  15 Pirate 3 be eatin', swingin' both cutlasses!
   9 Pirate 4 be eatin', swingin' both cutlasses!

We see that while everyone gets to eat, the pirates at the ends of the table are eating less often than the pirates in the middle. While this issue doesn't rise to the level of starvation, it does show that the fix isn't perfect.

When Dijkstra proposed the problem, he didn't realize how much fascination it would hold for computer scientists. The problem has been studied extensively, and many solutions have been proposed. Some of these solutions are more complex than others, but they all aim to ensure that—at the very least—no pirate starves and no deadlock occurs, but ideally allow all the pirates to eat as often and as fairly as possible.

A Better Fix

Here's one way of solving the problem with locks and condition variables. Now, instead of one lock per cutlass, we have a global lock for the table, an array tracking the status of each pirate, and a condition variable for each pirate.

When a pirate can't eat, they wait on their condition variable. When they wake up, they check to see if they can eat. If they can't, they wait again.
When a pirate finishes eating, they signal to wake up their neighbors.

We've also added code so that when the Royal Navy arrives (after ten seconds), the pirates will escape, ending the program cleanly.

#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>
#include "synch.h"

#define NUM_PIRATES 5

enum pirate_state { ARGUING, HUNGRY, EATING };
const char *state_names[] = {"ARGUING", "HUNGRY", "EATING"};

struct lock *table_lock;
struct cv *pirate_jab[NUM_PIRATES];
volatile enum pirate_state state[NUM_PIRATES];
volatile bool royal_navy = false;
pthread_t pirate_thread[NUM_PIRATES];

void
rand_sleep(void)
{
        usleep(100000 + (rand() % 200000)); /* Sleep for 100-250 ms */
}

void
pirate_maybe_escape(int pirate_id)
{
        if (royal_navy) {
                printf("Pirate %d be seein' the Royal Navy and be escapin'!\n",
                       pirate_id);
                lock_release(table_lock);
                pthread_exit(NULL);
        }
}

#define left(i) ((i + NUM_PIRATES - 1) % NUM_PIRATES)
#define right(i) ((i + 1) % NUM_PIRATES)

bool
should_eat(int i)
{
        return state[i] == HUNGRY && state[left(i)] != EATING &&
               state[right(i)] != EATING;
}

void
take_cutlasses(int pirate_id)
{
        lock_acquire(table_lock);
        pirate_maybe_escape(pirate_id);
        state[pirate_id] = HUNGRY;
        printf("Pirate %d be hungry and eyein' the cutlasses...\n", pirate_id);
        while (!should_eat(pirate_id)) {
                printf("Pirate %d be waitin' for cutlasses...\n", pirate_id);
                cv_wait(pirate_jab[pirate_id], table_lock);
                printf("Pirate %d be wakin' up and eyein' the cutlasses...\n",
                       pirate_id);
                pirate_maybe_escape(pirate_id);
        }
        state[pirate_id] = EATING;
        printf("Pirate %d be eatin' with both cutlasses!\n", pirate_id);
        lock_release(table_lock);
}

void
drop_cutlasses(int pirate_id)
{
        lock_acquire(table_lock);
        state[pirate_id] = ARGUING;
        printf("Pirate %d be done eatin' and ready to argue again!\n",
               pirate_id);
        cv_signal(pirate_jab[left(pirate_id)], table_lock);
        cv_signal(pirate_jab[right(pirate_id)], table_lock);
        pirate_maybe_escape(pirate_id);
        lock_release(table_lock);
}

void *
pirate(void *arg)
{
        int pirate_id = *(int *) arg;

        while (1) {
                /* Argue about treasure */
                printf("Pirate %d be arguin' about the treasure...\n",
                       pirate_id);
                rand_sleep();

                take_cutlasses(pirate_id);

                /* Eat and swing cutlasses */
                rand_sleep();

                drop_cutlasses(pirate_id);
        }

        return NULL;
}

int
main(void)
{
        int i;
        int pirate_ids[NUM_PIRATES];

        /* Initialize the table lock */
        table_lock = lock_create("table_lock");

        /* Initialize the condition variables and states */
        for (i = 0; i < NUM_PIRATES; i++) {
                char cv_name[20];
                snprintf(cv_name, sizeof(cv_name), "pirate_cv_%d", i);
                pirate_jab[i] = cv_create(cv_name);
                state[i] = ARGUING;
        }

        /* Create the pirate threads */
        for (i = 0; i < NUM_PIRATES; i++) {
                pirate_ids[i] = i;
                if (pthread_create(&pirate_thread[i], NULL, pirate,
                                   &pirate_ids[i]) != 0) {
                        fprintf(stderr,
                                "Failed to create thread for pirate %d\n", i);
                        exit(1);
                }
        }

        /* Allow ten seconds of pirate fun... */
        sleep(10);

        printf("Avast, ye scurvy dogs! The Royal Navy be here! Arrr!\n");

        /* Alert the pirates that the Royal Navy is here */
        lock_acquire(table_lock);
        royal_navy = true;
        lock_release(table_lock);

        /* Wait for the threads to finish */
        for (i = 0; i < NUM_PIRATES; i++) {
                pthread_join(pirate_thread[i], NULL);
        }

        lock_destroy(table_lock);
        for (i = 0; i < NUM_PIRATES; i++) {
                cv_destroy(pirate_jab[i]);
        }

        return 0;
}

If we run this code and count how often each pirate gets to eat, we get results like

  19 Pirate 0 be eatin' with both cutlasses!
  19 Pirate 1 be eatin' with both cutlasses!
  17 Pirate 2 be eatin' with both cutlasses!
  18 Pirate 3 be eatin' with both cutlasses!
  19 Pirate 4 be eatin' with both cutlasses!

The numbers will vary from run to run, but there is no single pirate who always or almost always eats less than the others. You can try the code yourself…

Try the code in Online GDB

What did we like?
I liked that the pirates all got to eat and no one starved.
Not biasing who gets to eat was a good thing, and the code seemed pretty straightforward.
Avast! I took a crack at increasing the number of pirates, and behold! it still worked like a ship in full sail! More pirates is always better! Arrr!
Those are all good points. Any downsides?
Well, I wondered about the fact that we're waking up the neighbors even if they don't need to eat. I guess it's harmless, but it's not the most efficient thing to do.
Good point. A nice thing about condition variables is that it is harmless to send a wake-up to a thread that isn't sleeping (try that with semaphores and you'll probably have a problem).
But if you wanted to be more efficient, you could use the should_eat function to only send wake-ups when necessary.
What about the single lock for the table? Could that be a problem? (In the old code we had one lock per cutlass.)
That's a good question. The lock protects the state array and the royal_navy flag, and update and query operations on these are quick, so it's only held for a short time. With only five pirates, it's not a problem, but if we had a lot more pirates, it could be a source of contention.
It's a trade-off between simplicity and efficiency. In this case, simplicity won out.

Takeaways

Deadlock is the result of circular waiting.
Breaking the circle can prevent deadlock.
- One way to break the circle is to impose a total order on the resources.
Sometimes, we can just adopt a different approach that avoids the circular-wait problem entirely.

Also, to help you in your OS/161 coding, the lock system in OS/161 has a deadlock-detection system called Hangman. If you're interested, you can read more about it.
We'll come back to deadlock detection and prevention in a later lesson.

(When logged in, completion status appears here.)

Previous Page Next Page

CS 134

Warning: Missing Prerequisites