Deadlock-Free Solution to Dining Philosophers Problem Using Semaphores

 

Deadlock-Free Solution to Dining Philosophers Problem Using Semaphores

---

1. Aim

To implement a deadlock-free solution for the Dining Philosophers Problem using semaphores.

---

2. Objective

• To study process synchronization

• To avoid deadlock and race conditions

• To ensure mutual exclusion using semaphores

---

3. Problem Statement

Five philosophers sit around a circular table. Each philosopher alternates between thinking and eating.

To eat, a philosopher must acquire both left and right chopsticks.

The challenge is to design a solution that:

• Avoids deadlock

• Avoids race condition

• Allows maximum parallelism

---

4. Theory

Why Deadlock Occurs (Naive Solution)

If all philosophers pick up their left chopstick first, a circular wait occurs → deadlock.

---

Deadlock-Free Strategy Used

We use a binary semaphore room that allows only 4 philosophers to try picking chopsticks at the same time.

This breaks circular wait, one of the four deadlock conditions.

---

5. Semaphores Used

Semaphore	Purpose
room	Limits philosophers entering dining room
chopstick[i]	Represents each chopstick
mutex	Protects critical output section

---

6. Algorithm

1. Philosopher waits on room

2. Picks up left chopstick

3. Picks up right chopstick

4. Eats

5. Puts down chopsticks

6. Signals room

---

7. Deadlock-Free Guarantee

• Maximum 4 philosophers can compete for 5 chopsticks

• At least one philosopher can always eat

• Circular wait is eliminated

---

8. C Program Implementation

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define N 5

sem_t room;
sem_t chopstick[N];
sem_t mutex;

void* philosopher(void* num) {
    int id = *(int*)num;

    while (1) {
        // Thinking
        printf("Philosopher %d is thinking\n", id);
        sleep(1);

        sem_wait(&room);  // enter dining room

        sem_wait(&chopstick[id]);              // left chopstick
        sem_wait(&chopstick[(id + 1) % N]);    // right chopstick

        sem_wait(&mutex);
        printf("Philosopher %d is eating\n", id);
        sem_post(&mutex);

        sleep(2);

        sem_post(&chopstick[id]);
        sem_post(&chopstick[(id + 1) % N]);

        sem_post(&room);  // leave dining room
    }
}

int main() {
    pthread_t tid[N];
    int phil[N];

    sem_init(&room, 0, N - 1);   // allow only 4 philosophers
    sem_init(&mutex, 0, 1);

    for (int i = 0; i < N; i++)
        sem_init(&chopstick[i], 0, 1);

    for (int i = 0; i < N; i++) {
        phil[i] = i;
        pthread_create(&tid[i], NULL, philosopher, &phil[i]);
    }

    for (int i = 0; i < N; i++)
        pthread_join(tid[i], NULL);

    return 0;
}

---

9. Sample Output

binuvp@debian-workstation:~$ gcc dinp.c binuvp@debian-workstation:~$ ./a.out Philosopher 0 is thinking Philosopher 3 is thinking Philosopher 4 is thinking Philosopher 1 is thinking Philosopher 2 is thinking Philosopher 0 is eating Philosopher 3 is eating Philosopher 0 is thinking Philosopher 1 is eating Philosopher 3 is thinking Philosopher 4 is eating Philosopher 1 is thinking Philosopher 4 is thinking Philosopher 3 is eating Philosopher 0 is eating Philosopher 3 is thinking Philosopher 2 is eating Philosopher 0 is thinking Philosopher 4 is eating Philosopher 2 is thinking

10. Observations

• No deadlock occurs

• Multiple philosophers can eat simultaneously

• Chopsticks are accessed mutually exclusively

---

11. Result

The dining philosophers problem was successfully implemented using semaphores, ensuring deadlock-free execution and proper process synchronization.