The Dining Philosophers - Leetcode Solution

The Dining Philosophers problem is a classic multi-threading problem in computer science. The problem statement is as follows:

There are five philosophers sitting around a circular table. Each philosopher has a plate of spaghetti in front of them and a fork on either side. The philosophers can either be eating, thinking, or waiting to eat. To eat, a philosopher must hold both forks on either side of them. However, each fork can only be held by one philosopher at a time. Therefore, the problem is to create a program where the philosophers can eat without getting into a deadlock.

We can solve this problem using the following steps:

Step 1: Assign a unique ID to each philosopher and fork:

#define N 5 // number of philosophers and forks
 
int philosopher_id[N] = { 0, 1, 2, 3, 4 };
pthread_mutex_t fork_mutex[N];

Step 2: Create a method for each philosopher to pick up the forks:

void pickup_forks(int id) {
    int left = id; // fork on the left
    int right = (id + 1) % N; // fork on the right
 
    // wait until the forks are available
    pthread_mutex_lock(&fork_mutex[left]);
    pthread_mutex_lock(&fork_mutex[right]);
 
    // eat
    printf("Philosopher %d is eating\n", id);
 
    // release the forks
    pthread_mutex_unlock(&fork_mutex[right]);
    pthread_mutex_unlock(&fork_mutex[left]);
}

Step 3: Implement the philosopher's behavior using threads:

void* philosopher(void* arg) {
    int id = *(int*)arg;
 
    while (1) {
        // think
        printf("Philosopher %d is thinking\n", id);
        usleep(1000000); // wait for 1 second
 
        // pick up the forks
        pickup_forks(id);
    }
 
    return NULL;
}

Step 4: Initialize mutex locks for each fork:

int main() {
    // initialize mutex locks for each fork
    for (int i = 0; i < N; i++) {
        pthread_mutex_init(&fork_mutex[i], NULL);
    }
 
    // create threads for each philosopher
    pthread_t threads[N];
    for (int i = 0; i < N; i++) {
        pthread_create(&threads[i], NULL, philosopher, &philosopher_id[i]);
    }
 
    // join threads
    for (int i = 0; i < N; i++) {
        pthread_join(threads[i], NULL);
    }
 
    // destroy mutex locks for each fork
    for (int i = 0; i < N; i++) {
        pthread_mutex_destroy(&fork_mutex[i]);
    }
 
    return 0;
}

In this solution, we created a mutex lock for each fork and used the pthread library in C to create threads for each philosopher. Each philosopher continually thinks and waits for the forks to become available. Once the forks are available, the philosopher picks them up and eats for a fixed amount of time before releasing the forks for other philosophers to use. This program ensures that no deadlock occurs since only one philosopher can pick up a fork at a time.

1