philosophers.c

/**
 * Problem statement
Five philosophers dine together at the same table. Each philosopher has his own
plate at the table. There is a fork between each plate. The dish served is a kind
 of spaghetti which has to be eaten with two forks. Each philosopher can only
 alternately think and eat. Moreover, a philosopher can only eat his spaghetti
  when he has both a left and right fork. Thus two forks will only be available
  when his two nearest neighbors are thinking, not eating. After an individual philosopher
   finishes eating, he will put down both forks.
 The problem is how to design a regimen (a concurrent algorithm) such that no philosopher will
 starve; i.e., each can forever continue to alternate between eating and thinking,
  assuming that no philosopher can know when others may want to eat or think
  (an issue of incomplete information).
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define N 5

typedef enum {
    THINKING = 0,
    HUNGRY = 1,
    EATING = 2
} State;

size_t left(size_t i) {
    return (i - 1 + N) % N;
}

size_t right(size_t i) {
    return (i + 1) % N;
}

State state[N];
pthread_mutex_t critical_region_mtx;
pthread_mutex_t output_mtx;

sem_t both_forks_available[N];

size_t my_rand(size_t min, size_t max) {
    static int initialized = 0;
    if (!initialized) {
        srand(time(NULL));
        initialized = 1;
    }
    return rand() % (max - min + 1) + min;
}

void test(size_t i) {
    if (state[i] == HUNGRY &&
        state[left(i)] != EATING &&
        state[right(i)] != EATING) {
        state[i] = EATING;
        sem_post(&both_forks_available[i]);
    }
}

void think(size_t i) {
    size_t duration = my_rand(400, 800);
    pthread_mutex_lock(&output_mtx);
    printf("%zu is thinking %zums\n", i, duration);
    pthread_mutex_unlock(&output_mtx);
    usleep(duration * 1000);
}

void take_forks(size_t i) {
    pthread_mutex_lock(&critical_region_mtx);
    state[i] = HUNGRY;
    pthread_mutex_lock(&output_mtx);
    printf("\t\t%zu is HUNGRY\n", i);
    pthread_mutex_unlock(&output_mtx);
    test(i);
    pthread_mutex_unlock(&critical_region_mtx);
    sem_wait(&both_forks_available[i]);
}

void eat(size_t i) {
    size_t duration = my_rand(400, 800);
    pthread_mutex_lock(&output_mtx);
    printf("\t\t\t\t%zu is eating %zums\n", i, duration);
    pthread_mutex_unlock(&output_mtx);
    usleep(duration * 1000);
}

void put_forks(size_t i) {
    pthread_mutex_lock(&critical_region_mtx);
    state[i] = THINKING;
    test(left(i));
    test(right(i));
    pthread_mutex_unlock(&critical_region_mtx);
}

void* philosopher(void* arg) {
    size_t i = *(size_t*)arg;
    while (1) {
        think(i);
        take_forks(i);
        eat(i);
        put_forks(i);
    }
    return NULL;
}

int main() {
    printf("dp_14\n");
    pthread_t t[N];
    pthread_mutex_init(&critical_region_mtx, NULL);
    pthread_mutex_init(&output_mtx, NULL);
    for (size_t i = 0; i < N; i++) {
        sem_init(&both_forks_available[i], 0, 0);
    }
    for (size_t i = 0; i < N; i++) {
        pthread_create(&t[i], NULL, philosopher, &i);
    }
    for (size_t i = 0; i < N; i++) {
        pthread_join(t[i], NULL);
    }
    pthread_mutex_destroy(&critical_region_mtx);
    pthread_mutex_destroy(&output_mtx);
    for (size_t i = 0; i < N; i++) {
        sem_destroy(&both_forks_available[i]);
    }
    return 0;
}