Deadlock Avoidance Practical

Deadlock Avoidance

• Use try_lock() with a timeout

  • Instead of blocking lock()
  • May result in livelock

• Use std::lock()

  • Lock both mutexes in a single operation

• Use hierarchical ordering

  • Lock lower-numbered mutexes first

// after declaring lfork and rfork
if (lfork > rfork) {
  std::swap(lfork, rfork);
}

#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 philosopher who has picked up one fork will put it down again
// If they cannot pick up the other fork they need
constexpr auto time_out = think_time;

// 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 forks
void print(int n, const std::string &str, int lfork, int rfork) {
  std::lock_guard<std::mutex> print_lck(print_mutex);
  std::cout << "Philosopher " << names[n] << str;
  std::cout << lfork << " and " << rfork << '\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 forks are ", lfork, rfork);
  print(nphilo, " is thinking...");

  std::this_thread::sleep_for(think_time);

  print(nphilo, " reaches for forks ", lfork, rfork);

  std::lock(fork_mutex[lfork], fork_mutex[rfork]);
  print(nphilo, " picks up forks ", lfork, rfork);
  print(nphilo, " is eating...");
  ++mouthfuls[nphilo];

  std::this_thread::sleep_for(eat_time);

  print(nphilo, " puts down fork ", lfork, 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";
  }
}