Deadlock Practical

Dining Philosophers Rules

• A philosopher has two states: thinking and eating

• Each fork can only be held by one philosopher at a time

  • A philosopher can only pick up one fork at a time
  • A philosopher must pick up both forks before they can eat
  • When a philosopher finishes eating, they put down both forks immediately
  • A philosopher may pick up a fork as soon as it is put down by another

• A philosopher has no awareness of other philosopher's actions

• If a philosopher does not eat at all, they will die of starvation

• Intended scenario

  • Philosopher thinks
  • Philosopher picks up left fork
  • Philosopher thinks
  • Philosopher picks up right fork
  • Philosopher eats
  • Philosopher puts down both forks
  • Philosopher thinks

Implementation

• A separate thread for each philosopher
• Each fork has an associated mutex

// A mutex prevents more than one philosopher picking up the same fork
std::mutex fork_mutex[nforks];

// A philosopher thread can only pick up a fork if it can lock the corresponding mutex
// Try to pick up the left fork
fork_mutex[lfork].lock();

// Try to pick up the right fork
fork_mutex[rfork].lock();

// Succeeded - the philosopher can now eat

#include <chrono>
#include <iostream>
#include <mutex>
#include <string>
#include <thread>
#include <vector>

using namespace std::literals;

constexpr int nforks = 5;
constexpr int nphilosophers = nforks;
std::string names[nphilosophers] = {"A", "B", "C", "D", "E"};

// Keep track of how many times a philosopher is able to eat
int mouthfuls[nphilosophers] = {0};

// A philosopher who has not picked up both forks is thinking
constexpr std::chrono::duration think_time = 2s;

// A philosopher has picked up both forks is eating
constexpr std::chrono::duration eat_time = 1s;

// A mutex prevents more than one philosopher picking up the same fork
// A philosopher thread can only pick up a fork if it can lock the corresponding
// mutex
std::mutex fork_mutex[nforks];

// Mutex to protect output
std::mutex print_mutex;

// Interactions with a fork
void print(int n, const std::string &str, int forkno) {
  std::lock_guard<std::mutex> print_lck(print_mutex);
  std::cout << "Philosopher " << names[n] << str << forkno << '\n';
}

// The philosopher's state
void print(int n, const std::string &str) {
  std::lock_guard<std::mutex> print_lck(print_mutex);
  std::cout << "Philosopher " << names[n] << str << '\n';
}

// Thread which represents a dining philosopher
void dine(int nphilo) {
  // Philosopher A has fork 0 on their left, and fork 1 on their right
  // Philosopher B has fork 1 on their left, and fork 2 on their right
  // ...
  // Philosopher E has fork 4 on their left, and fork 0 on their right

  // Each philosopher must pick up their left fork first
  int lfork = nphilo;
  int rfork = (nphilo + 1) % nforks;

  print(nphilo, "\'s left fork is number ", lfork);
  print(nphilo, "\'s right fork is number ", rfork);
  print(nphilo, " is thinking...");

  std::this_thread::sleep_for(think_time);

  print(nphilo, " reaches for fork number ", lfork);

  // Try to pick up the left fork
  fork_mutex[lfork].lock();
  print(nphilo, " picks up fork ", lfork);
  print(nphilo, " is thinking...");

  std::this_thread::sleep_for(think_time);

  print(nphilo, " reaches for fork number ", rfork);

  // Try to pick up the right fork
  fork_mutex[rfork].lock();
  print(nphilo, " picks up fork ", rfork);
  print(nphilo, " is eating...");

  std::this_thread::sleep_for(eat_time);

  print(nphilo, " puts down fork ", lfork);
  print(nphilo, " puts down fork ", rfork);
  print(nphilo, " is thinking...");

  fork_mutex[lfork].unlock();
  fork_mutex[rfork].unlock();
  std::this_thread::sleep_for(think_time);
}

int main() {
  // Separate thread for each philosopher
  std::vector<std::thread> philos;
  for (int i = 0; i < nphilosophers; ++i) {
    philos.push_back(std::move(std::thread{dine, i}));
  }

  for (auto &philo : philos) {
    philo.join();
  }

  // How many times were the philosophers able to eat ?
  for (int i = 0; i < nphilosophers; ++i) {
    std::cout << "Philosopher " << names[i];
    std::cout << " had " << mouthfuls[i] << " mouthfuls\n";
  }
}

Deadlock

• All the philosophers pick up their left fork

• None of the right forks are available

  • B picks up fork 2
  • Fork 2 is A's right fork
  • A cannot eat without picking up fork 2
  • Fork 2 will not become available until B has finished eating
  • B cannot start eating because C has taken fork 3

• The philosopher threads are deadlocked

  • The philosophers cannot enter the "eating state"