// Mutual deadlock
// Two threads wait for the other to unlock a mutex
#include <thread>
#include <mutex>
#include <iostream>
#include <chrono>

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA()
{
	std::cout << "Thread A trying to lock mutex 1...\n";
	std::lock_guard<std::mutex> lck_guard(mut1);		// Acquire lock on mut1
	std::cout << "Thread A has locked mutex 1\n";
	std::this_thread::sleep_for(50ms);	                // Do some work
	std::cout << "Thread A trying to lock mutex 2...\n";
	std::lock_guard<std::mutex> lck_guard2(mut2);		// Wait for lock on mut2
	std::cout << "Thread A has locked mutex 2\n";
	std::this_thread::sleep_for(50ms);	                // Do some work
	std::cout << "Thread A releases all its locks\n";
}

void funcB()
{
	std::cout << "Thread B trying to lock mutex 2...\n";
	std::lock_guard<std::mutex> lck_guard1(mut2);	    // Acquire lock on mut2
	std::cout << "Thread B has locked mutex 2\n";
	std::this_thread::sleep_for(50ms);	                // Do some work
	std::cout << "Thread B trying to lock mutex 1...\n";
	std::lock_guard<std::mutex> lck_guard2(mut1);	    // Wait for lock on mut1
	std::cout << "Thread B has locked mutex 1\n";
	std::this_thread::sleep_for(50ms);	                // Do some work
	std::cout << "Thread B releases all its locks\n";
}

int main()
{
	std::thread thrA(funcA);
	std::thread thrB(funcB);
	
	thrA.join(); thrB.join();
}

// Avoid deadlock by writing the threads
// so that they lock the mutexes in the same order
#include <thread>
#include <mutex>
#include <iostream>
#include <chrono>

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA()
{
	std::cout << "Thread A trying to lock mutex 1...\n";
	std::lock_guard<std::mutex> lck_guard(mut1);        // Acquire lock on mut1
	std::cout << "Thread A has locked mutex 1\n";
	std::this_thread::sleep_for(50ms);	                // Do some work
	std::cout << "Thread A trying to lock mutex 2...\n";
	std::lock_guard<std::mutex> lck_guard2(mut2);       // Wait for lock on mut2
	std::cout << "Thread A has locked mutex 2\n";
	std::this_thread::sleep_for(50ms);                  // Do some work
	std::cout << "Thread A releases all its locks\n";
}

void funcB()
{
	std::cout << "Thread B trying to lock mutex 1...\n";
	std::lock_guard<std::mutex> lck_guard1(mut1);       // Acquire lock on mut1
	std::cout << "Thread B has locked mutex 1\n";
	std::this_thread::sleep_for(50ms);                  // Do some work
	std::cout << "Thread B trying to lock mutex 2...\n";
	std::lock_guard<std::mutex> lck_guard2(mut2);	    // Wait for lock on mut2
	std::cout << "Thread B has locked mutex 2\n";
	std::this_thread::sleep_for(50ms);	                // Do some work
	std::cout << "Thread B releases all its locks\n";
}

int main()
{
	std::thread thrA(funcA);
	std::thread thrB(funcB);
	
	thrA.join(); thrB.join();
}

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

//  A pholosopher theard 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 pic up the right fork
fork_mutex[rfork].lock();

// Succeeded - This philosopher can now eat
//

// Dining philosophers problem (part 1)
//
// 5 philosophers sit at a round table which has 5 forks on it.
// A philosopher has a fork at each side of them.
// A philosopher can only eat if they can pick up both forks.
// If a philosopher picks up the fork on their right,
// that prevents the next philosopher from picking up their left fork.
//
// All the philosophers pick up their left fork at the same time
// They wait to pick up their right fork (which is also their neighbour's left fork)
// Their neighbour is waiting to pick up their own right fork
// All the philosophers are waiting for their neighbour
//
// The philosophers are blocked indefinitely.
// Deadlock
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <string>
#include <chrono>

using namespace std::literals;

// Some data about the problem
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 auto think_time = 2s;

// A philosopher has picked up both forks is eating
constexpr auto 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;

// Functions to display information about the 'nth' philosopher

// Interactions with a fork
void print(int n, const std::string& str, int forkno)
{
	std::lock_guard<std::mutex> print_lock(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_lock(print_mutex);
	std::cout << "Philosopher " << names[n] << str << '\n';
}

// Thread which represents a dining philosopher
void dine(int phil_no)
{
	// 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 = phil_no;
	int rfork = (phil_no+1) % nforks;

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

	std::this_thread::sleep_for(think_time);

	// Make an attempt to eat
	print(phil_no, " reaches for fork number ", lfork);

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

	// Succeeded - now try to pick up the right fork
	std::this_thread::sleep_for(think_time);

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

	fork_mutex[rfork].lock();

	// Succeeded - this philosopher can now eat
	print(phil_no, " picks up fork ", rfork);
	print(phil_no, " is eating...");
	
	std::this_thread::sleep_for(eat_time);

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

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

int main()
{
	// Start a 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";
	}
}

// Use std::scoped_lock to avoid deadlock
// All the mutexes are locked in a single operation
// Requires C++17 compiler
#include <thread>
#include <mutex>
#include <iostream>
#include <chrono>	

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA()
{
	std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
	std::scoped_lock scoped_lck(mut1, mut2);
	std::cout << "Thread A has locked mutexes 1 and 2\n";
	std::this_thread::sleep_for(50ms);
	std::cout << "Thread A releasing mutexes 1 and 2...\n";
}

void funcB()
{
	std::cout << "Thread B trying to lock mutexes 2 and 1...\n";
	std::scoped_lock scoped_lck(mut2, mut1);
	std::cout << "Thread B has locked mutexes 2 and 1\n";
	std::this_thread::sleep_for(50ms);
	std::cout << "Thread B releasing mutexes 2 and 1...\n";
}

int main()
{
	std::thread thrA(funcA);
	std::thread thrB(funcB);
	
	thrA.join(); thrB.join();
}

// Use std::adopt_lock to avoid deadlock
#include <thread>
#include <mutex>
#include <iostream>
#include <chrono>

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA()
{
	std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
	std::lock(mut1, mut2);				               // Lock both mutexes
	std::cout << "Thread A has locked mutexes 1 and 2\n";
	
	// Adopt the locks
	std::unique_lock<std::mutex> uniq_lk1(mut1, std::adopt_lock);   // Associate each mutex
	std::unique_lock<std::mutex> uniq_lk2(mut2, std::adopt_lock);   // with a unique_lock
	std::cout << "Thread A has adopted the locks\n";
	
	std::this_thread::sleep_for(50ms);
	std::cout << "Thread A releasing mutexes 1 and 2...\n";
}

void funcB() {
	std::cout << "Thread B trying to lock mutexes 2 and 1...\n";
	lock(mut2, mut1);				               // Lock both mutexes
	std::cout << "Thread B has locked mutexes 2 and 1\n";
	
	// Adopt the locks
	std::unique_lock<std::mutex> uniq_lk2(mut2, std::adopt_lock);   // with a unique_lock
	std::unique_lock<std::mutex> uniq_lk1(mut1, std::adopt_lock);   // Associate each mutex
	std::cout << "Thread B has adopted the locks\n";
	
	std::this_thread::sleep_for(50ms);
	std::cout << "Thread B releasing mutexes 2 and 1...\n";
}

int main() {
	std::thread thrA(funcA);
	std::thread thrB(funcB);
	
	thrA.join(); thrB.join();
}

// Use std::defer_lock to avoid deadlock
#include <thread>
#include <mutex>
#include <iostream>
#include <chrono>

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA()
{
    std::unique_lock<std::mutex> uniq_lk1(mut1, std::defer_lock);	// Associate mutex with lock...
    std::unique_lock<std::mutex> uniq_lk2(mut2, std::defer_lock);	// ...but don’t lock it yet
	
	std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
    std::lock(uniq_lk1, uniq_lk2);								    // Now lock both of them
	std::cout << "Thread A has locked mutexes 1 and 2\n";
	std::this_thread::sleep_for(50ms);
	std::cout << "Thread A releasing mutexes 1 and 2...\n";
}

void funcB() {
    std::unique_lock<std::mutex> uniq_lk2(mut2, std::defer_lock);	// Associate mutex with lock...
    std::unique_lock<std::mutex> uniq_lk1(mut1, std::defer_lock);	// ...but don’t lock it yet
	
	std::cout << "Thread B trying to lock mutexes 2 and 1...\n";
    std::lock(uniq_lk2, uniq_lk1);									// Now lock both of them
	std::cout << "Thread B has locked mutexes 2 and 1\n";
	std::this_thread::sleep_for(50ms);
	std::cout << "Thread B releasing mutexes 2 and 1...\n";
}

int main() {
	std::thread thrA(funcA);
	std::thread thrB(funcB);
	
	thrA.join(); thrB.join();
}

// Use std::defer_lock to avoid deadlock
#include <thread>
#include <mutex>
#include <iostream>
#include <chrono>

using namespace std::literals;

std::mutex mut1;
std::mutex mut2;

void funcA()
{
    std::unique_lock<std::mutex> uniq_lk1(mut1, std::defer_lock);   // Associate mutex with lock...
    std::unique_lock<std::mutex> uniq_lk2(mut2, std::defer_lock);   // ...but don’t lock it yet
	
	std::cout << "Thread A trying to lock mutexes 1 and 2...\n";
    
	// Now lock both of them
	auto idx = std::try_lock(uniq_lk1, uniq_lk2);
	if (idx != -1) {
		std::cout << "try_lock failed on mutex with index " << idx << '\n';
	}
	else {
		std::cout << "Thread A has locked mutexes 1 and 2\n";
		std::this_thread::sleep_for(50ms);
		std::cout << "Thread A releasing mutexes 1 and 2...\n";
	}
}

void funcB() {
    std::unique_lock<std::mutex> uniq_lk2(mut2, std::defer_lock);   // Associate mutex with lock...
    std::unique_lock<std::mutex> uniq_lk1(mut1, std::defer_lock);   // ...but don’t lock it yet
	
	std::cout << "Thread B trying to lock mutexes 2 and 1...\n";
    
	// Now lock both of them
	auto idx = std::try_lock(uniq_lk2, uniq_lk1);
	if (idx != -1) {
		std::cout << "try_lock failed on mutex with index " << idx << '\n';
	}
	else {
		std::cout << "Thread B has locked mutexes 2 and 1\n";
		std::this_thread::sleep_for(50ms);
		std::cout << "Thread B releasing mutexes 2 and 1...\n";
	}
}

int main() {
	std::thread thrA(funcA);
	std::thread thrB(funcB);
	
	thrA.join(); thrB.join();
}

// Dining philosophers problem (part 2a)
//
// 5 philosophers sit at a round table which has 5 forks on it.
// A philosopher has a fork at each side of them.
// A philosopher can only eat if they can pick up both forks.
// If a philosopher picks up the fork on their right,
// that prevents the next philosopher from picking up their left fork.
//
// The philosophers try to pick up both forks at the same time.
// If they succeed, they can eat.
// If not, both forks are available to their neighbours.
//
// All philosophers are able to eat.
// No deadlock
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <string>
#include <chrono>

using namespace std::literals;

// Some data about the problem
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 auto think_time = 2s;

// A philosopher has picked up both forks is eating
constexpr auto 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;

// Functions to display information about the 'nth' philosopher

// Interactions with forks
void print(int n, const std::string& str, int lfork, int rfork)
{
	std::lock_guard<std::mutex> print_lock(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_lock(print_mutex);
	std::cout << "Philosopher " << names[n] << str << '\n';
}

// Thread which represents a dining philosopher
void dine(int phil_no)
{
	// 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 = phil_no;
	int rfork = (phil_no+1) % nforks;
	
	print(phil_no, "\'s forks are ", lfork, rfork);
	print(phil_no, " is thinking...");

	std::this_thread::sleep_for(think_time);

	// Make an attempt to eat
	print(phil_no, " reaches for forks ", lfork, rfork);

	// Try to pick up both forks
	std::lock(fork_mutex[lfork], fork_mutex[rfork]);
	print(phil_no, " picks up fork ", lfork, rfork);

	// Succeeded - this philosopher can now eat
	print(phil_no, " is eating...");
	++mouthfuls[phil_no];
	
	std::this_thread::sleep_for(eat_time);

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

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

int main()
{
	// Start a 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] << " mouthful\n";
	}
}

// Dining philosophers problem (part 2b)
//
// 5 philosophers sit at a round table which has 5 forks on it.
// A philosopher has a fork at each side of them.
// A philosopher can only eat if they can pick up both forks.
// If a philosopher picks up the fork on their right,
// that prevents the next philosopher from picking up their left fork.
//
// Each philosopher tries to pick up their lowest numbered fork first.
// For philosopher E, this leaves their right fork free. This breaks
// the deadlock and allows philosopher D to eat, followed by the others.
//
// All philosophers are able to eat.
// No deadlock
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <string>
#include <chrono>

using namespace std::literals;

// Some data about the problem
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 auto think_time = 2s;

// A philosopher has picked up both forks is eating
constexpr auto 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;

// Functions to display information about the 'nth' philosopher

// Interactions with forks
void print(int n, const std::string& str, int lfork, int rfork)
{
	std::lock_guard<std::mutex> print_lock(print_mutex);
	std::cout << "Philosopher " << names[n] << str;
	std::cout << lfork << " and " << rfork << '\n';
}

// Interactions with a fork
void print(int n, const std::string& str, int forkno)
{
	std::lock_guard<std::mutex> print_lock(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_lock(print_mutex);
	std::cout << "Philosopher " << names[n] << str << '\n';
}

// Thread which represents a dining philosopher
void dine(int phil_no)
{
	// 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 = phil_no;
	int rfork = (phil_no+1) % nforks;

	if (lfork > rfork) {
		std::swap(lfork, rfork);
	}

	print(phil_no, "\'s forks are ", lfork, rfork);
	print(phil_no, " is thinking...");

	std::this_thread::sleep_for(think_time);

	// Make an attempt to eat
	print(phil_no, " reaches for fork number ", lfork);

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

	// Succeeded - now try to pick up the right fork
	std::this_thread::sleep_for(think_time);

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

	fork_mutex[rfork].lock();

	// Succeeded - this philosopher can now eat
	print(phil_no, " picks up fork ", rfork);
	print(phil_no, " is eating...");
	++mouthfuls[phil_no];

	std::this_thread::sleep_for(eat_time);

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

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

int main()
{
	// Start a 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] << " mouthful\n";
	}
}

// Livelock caused by poorly implemented deadlock avoidance
// If the thread cannot get a lock, sleep and try again
// However, all the threads wake up at the same time
#include <thread>
#include <mutex>
#include <iostream>
#include <string>
#include <chrono>

using namespace std::literals;

std::mutex mut1, mut2;

void funcA()
{
	std::this_thread::sleep_for(10ms);
	bool locked = false;
	while (!locked) {
		std::lock_guard<std::mutex> lck_guard(mut1);  // Lock mut1
		std::cout << "After you, Claude!\n";
		std::this_thread::sleep_for(2s);
		locked = mut2.try_lock();                           // Try to lock mut2
	}
	if (locked)
		std::cout << "ThreadA has locked both mutexes\n";
}

void funcB() {
	bool locked = false;
	while (!locked) {
		std::lock_guard<std::mutex> lk(mut2);         // Lock mut2
		std::cout << "After you, Cecil!\n";
		std::this_thread::sleep_for(2s);
		locked = mut1.try_lock();                           // Try to lock mut1
	}
	if (locked)
		std::cout << "ThreadB has locked both mutexes\n";
}

int main() {
	std::thread thrA(funcA);
	std::this_thread::sleep_for(10ms);
	std::thread thrB(funcB);

	thrA.join(); thrB.join();
}

void funcA()
{
	std::scoped_lock scoped_lck(mut1, mut2);  //lock both mutexes
}
void funcB()
{
	std::scoped_lock scoped_lck(mut2, mut1);  //lock both mutexes
}

// std::shared_lock and std::lock() avoid deadlock
// when locking multiple mutexes. They also avoid livelock.
#include <thread>
#include <mutex>
#include <iostream>
#include <string>
#include <chrono>	

using namespace std::literals;

std::mutex mut1, mut2;

void funcA() {
	std::this_thread::sleep_for(10ms);

	std::cout << "After you, Claude!" << std::endl;
	std::scoped_lock scoped_lck(mut1, mut2);		 // Lock both mutexes
	std::this_thread::sleep_for(2s);
	std::cout << "Thread A has locked both mutexes\n";
}

void funcB() {
	std::cout << "After you, Cecil!\n";
	std::scoped_lock scoped_lck(mut2, mut1);		 // Lock mutexes
	std::this_thread::sleep_for(2s);
	std::cout << "Thread B has locked both mutexes\n";
}

int main() {
	std::thread thrA(funcA);
	std::this_thread::sleep_for(10ms);
	std::thread thrB(funcB);

	thrA.join(); thrB.join();
}

// Dining philosophers problem (part 3)
//
// 5 philosophers sit at a round table which has 5 forks on it.
// A philosopher has a fork at each side of them.
// A philosopher can only eat if they can pick up both forks.
// If a philosopher picks up the fork on their right,
// that prevents the next philosopher from picking up their left fork.
//
// All the philosophers pick up their left fork at the same time
// They wait to pick up their right fork (which is also their neighbour's left fork)
// If a philosopher cannot pick up the right fork, they put down the left fork
// and go back to thinking.
//
// If all the philosophers pick up their left fork at the same time,
// and put it down at the same time, they will still not be able to eat.
// Livelock
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <string>
#include <chrono>

using namespace std::literals;

// Some data about the problem
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 auto think_time = 2s;

// A philosopher has picked up both forks is eating
constexpr auto 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;

// Functions to display information about the 'nth' philosopher

// Interactions with a fork
void print(int n, const std::string& str, int forkno)
{
	std::lock_guard<std::mutex> print_lock(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_lock(print_mutex);
	std::cout << "Philosopher " << names[n] << str << '\n';
}

// Thread which represents a dining philosopher
void dine(int phil_no)
{
	// 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 = phil_no;
	int rfork = (phil_no+1) % nforks;

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

	std::this_thread::sleep_for(think_time);

	// Make an attempt to eat
	print(phil_no, " reaches for fork number ", lfork);

	// Try to pick up the left fork
	bool locked = false;

	while (!locked) {
		fork_mutex[lfork].lock();
		print(phil_no, " picks up fork ", lfork);
		print(phil_no, " is thinking...");

		// Succeeded - now try to pick up the right fork
		std::this_thread::sleep_for(think_time);
		print(phil_no, " reaches for fork number ", rfork);

		locked = fork_mutex[rfork].try_lock();

		if (!locked) {
			print(phil_no, " puts down fork ", lfork);
			std::this_thread::sleep_for(think_time);
			fork_mutex[lfork].unlock();
		}
	}

	// Succeeded - this philosopher can now eat
	print(phil_no, " picks up fork ", rfork);
	print(phil_no, " is eating...");
	++mouthfuls[phil_no];

	std::this_thread::sleep_for(eat_time);

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

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

int main()
{
	// Start a 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] << " mouthful(s)\n";
	}
}