// The dining philosophers problem, using Windows threads and critical sections.
// Adam Sampson <ats@offog.org>

// Five philosophers live in a college. Most of the time they're thinking, but
// occasionally they get hungry and head to the dining room for a meal.  In the
// dining room there's a round table with a bowl of spaghetti in the middle and
// five forks.  (Golden forks, since this is a very prestigious college, but
// because they're gold they can only afford five of them.) To eat spaghetti, a
// philosopher has to pick up both the fork on his left and the fork on his
// right.  Once he's full, he puts the forks back down and returns to work.
//
// This works fine until one day all the philosophers get hungry at the same
// time, and they all sit down and pick up the fork to their left at once...
// deadlock!
//
// (Standard fixes for the deadlock: have philosopher 0 pick up the fork on his
// right first; have the philosophers pick up both forks in parallel; have a
// doorman who stops more than N - 1 philosophers from entering the dining room
// at once.)
//
// PI only appears to detect the deadlock when it actually happens...

#include <stdio.h>
#include <windows.h>

// Deadlock occurs immediately if this is commented out (because the
// philosophers all immediately rush to the table).  With this defined,
// deadlock is still possible, but it'll take a while to occur.
#define USE_SLEEP

// The number of philosophers.
#define N 5

// (I tried declaring the forks as individual variables rather than an array,
// and got the same result.)
CRITICAL_SECTION forks[N];

DWORD WINAPI philosopher(void *arg)
{
	const int id = (int) arg;

	CRITICAL_SECTION *lfork = &forks[id];
	CRITICAL_SECTION *rfork = &forks[(id + 1) % N];

	char prefix[(N * 10) + 1];
	for (int i = 0; i < (id * 10); i++) {
		prefix[i] = ' ';
	}
	prefix[id * 10] = '\0';

	// This'd normally be a while (true), but I thought it might be more
	// useful to have it stop after a while (results the same either way).
	for (int cycles = 0; cycles < 20; cycles++) {
		printf("%sThinking\n", prefix);
#ifdef USE_SLEEP
		Sleep(30 * (id + 1));
#endif
		printf("%sHungry\n", prefix);
		EnterCriticalSection(lfork);
			printf("%sGot left\n", prefix);
			EnterCriticalSection(rfork);
				printf("%sGot right\n", prefix);
				printf("%sEating\n", prefix);
#ifdef USE_SLEEP
				Sleep(40 * (id + 1));
#endif
				printf("%sFull!\n", prefix);
			LeaveCriticalSection(rfork);
		LeaveCriticalSection(lfork);
	}

	return 0;
}

int main(int argc, char *argv[]) {
	for (int i = 0; i < N; i++) {
		InitializeCriticalSection(&forks[i]);
	}

	HANDLE phils[N];
	for (int i = 0; i < N; i++) {
		phils[i] = CreateThread(0, 0, philosopher, (void *) i, 0, NULL);
	}
	WaitForMultipleObjects(N, phils, TRUE, INFINITE);

	for (int i = 0; i < N; i++) {
		DeleteCriticalSection(&forks[i]);
	}
}