Dining Philosophers Problem in C – pthreads and Deadlock Prevention

The Dining Philosophers problem is a classic synchronization puzzle introduced by Edsger Dijkstra to illustrate deadlock and resource contention. Five philosophers sit at a round table with a single fork between each pair of neighbors — five forks total. Each philosopher alternates between thinking and eating, but eating requires picking up both the fork on their left and the fork on their right. Since forks are shared with neighbors, this is a real model for how concurrent programs compete for limited shared resources — database connections, file locks, network sockets — and it’s a standard exercise in operating systems courses.

If every philosopher picks up their left fork at the same time, all five forks are taken and nobody can pick up a right fork — a deadlock, where every thread waits forever. This page implements the classic fix using POSIX threads (pthreads) and mutexes in C.

How It Works — Step by Step

1. Represent each fork as a mutex (a lock that only one thread can hold at a time).
2. Run each philosopher as a separate thread that loops through thinking and eating.
3. To eat, a philosopher must lock both their left and right fork’s mutex.
4. The critical fix: every philosopher picks up their left fork first, then their right — except one, who picks up right first, then left. This breaks the circular wait that causes deadlock.
5. After eating, both forks are unlocked so neighboring philosophers can use them.

Why the asymmetry prevents deadlock

Deadlock requires a circular chain: philosopher 0 waits for the fork held by philosopher 1, who waits for the fork held by philosopher 2, and so on back to philosopher 0. If one philosopher reaches for forks in the opposite order, that circular chain can never fully form — at least one philosopher will always be able to get both forks and eat, which eventually frees up forks for everyone else.

C Program for the Dining Philosophers Problem

/* Dining Philosophers Problem in C (pthreads)
 * Compile: gcc -ansi -Wall -Wextra dining.c -o dining -lpthread */
#include <stdio.h>
#include <pthread.h>

#define N 5
#define MEALS 2

pthread_mutex_t fork_mutex[N];

void *philosopher(void *arg)
{
    int id = *(int *)arg;
    int left = id;
    int right = (id + 1) % N;
    int meal;

    for (meal = 0; meal < MEALS; meal++) {
        printf("Philosopher %d is thinking.\n", id);

        /* Break the symmetry: the last philosopher picks up the
           right fork first, everyone else picks up left first.
           This prevents the circular-wait deadlock. */
        if (id == N - 1) {
            pthread_mutex_lock(&fork_mutex[right]);
            pthread_mutex_lock(&fork_mutex[left]);
        } else {
            pthread_mutex_lock(&fork_mutex[left]);
            pthread_mutex_lock(&fork_mutex[right]);
        }

        printf("Philosopher %d is eating (meal %d).\n", id, meal + 1);

        pthread_mutex_unlock(&fork_mutex[left]);
        pthread_mutex_unlock(&fork_mutex[right]);
    }

    printf("Philosopher %d has finished eating.\n", id);
    return NULL;
}

int main(void)
{
    pthread_t philosophers[N];
    int ids[N];
    int i;

    for (i = 0; i < N; i++)
        pthread_mutex_init(&fork_mutex[i], NULL);

    for (i = 0; i < N; i++) {
        ids[i] = i;
        pthread_create(&philosophers[i], NULL, philosopher, &ids[i]);
    }

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

    for (i = 0; i < N; i++)
        pthread_mutex_destroy(&fork_mutex[i]);

    printf("All philosophers finished eating. No deadlock occurred.\n");

    return 0;
}

How to Compile and Run

This program uses POSIX threads, so it needs the -lpthread link flag:

gcc -ansi -Wall -Wextra dining.c -o dining -lpthread
./dining

Sample Output (one possible run)

Important: unlike a single-threaded program, the exact interleaving of “thinking” and “eating” lines will differ between runs — that’s expected with real concurrency. What must stay true on every run is that the program terminates and every philosopher finishes. Here is one actual run:

Philosopher 0 is thinking.
Philosopher 2 is thinking.
Philosopher 2 is eating (meal 1).
Philosopher 2 is thinking.
Philosopher 2 is eating (meal 2).
Philosopher 2 has finished eating.
Philosopher 1 is thinking.
Philosopher 0 is eating (meal 1).
Philosopher 0 is thinking.
Philosopher 0 is eating (meal 2).
Philosopher 0 has finished eating.
Philosopher 3 is thinking.
Philosopher 3 is eating (meal 1).
Philosopher 3 is thinking.
Philosopher 3 is eating (meal 2).
Philosopher 3 has finished eating.
Philosopher 1 is eating (meal 1).
Philosopher 1 is thinking.
Philosopher 1 is eating (meal 2).
Philosopher 1 has finished eating.
Philosopher 4 is thinking.
Philosopher 4 is eating (meal 1).
Philosopher 4 is thinking.
Philosopher 4 is eating (meal 2).
Philosopher 4 has finished eating.
All philosophers finished eating. No deadlock occurred.

This program was run 5 times consecutively during testing with no deadlock or hang in any run.

Code Explanation

• fork_mutex[N] — one mutex per fork. pthread_mutex_lock() blocks the calling thread until it can acquire that specific fork, which is exactly the “picking up a fork” behavior we want to model.
• Asymmetric lock order for the last philosopher — this single if branch is the entire deadlock fix. Removing it (making every philosopher pick up left-then-right) reliably reproduces a deadlock with 5 threads.
• left = id, right = (id + 1) % N — the modulo wraps the last philosopher’s right fork back around to fork 0, closing the circle of 5 philosophers and 5 forks.
• Why MEALS is small — this is a demonstration program, not a real server; a fixed number of meals lets every thread terminate so pthread_join() returns and the program exits cleanly.

Time and Space Complexity

What This Program Teaches

• Deadlock and the circular-wait condition — one of the four necessary conditions for deadlock, and how breaking just one of them (here, “wait circularly” via lock ordering) prevents it entirely.
• pthreads and mutexes — creating threads with pthread_create(), protecting shared resources with pthread_mutex_t, and waiting for completion with pthread_join().
• Why concurrent program output is nondeterministic — the OS scheduler decides which thread runs when, so correctness must be judged by invariants (no deadlock, every philosopher eats) rather than by matching one fixed output.

Related Programs

• Producer-Consumer Problem in C
• File Locking Using Semaphores in C
• FCFS Scheduling in C
• Round Robin Scheduling in C

Recommended Books

• The C Programming Language – Kernighan & Ritchie (India) | Amazon.com
• C Programming: A Modern Approach – K.N. King (India) | Amazon.com

Practice OS concurrency and C fundamentals with the C Programming Quiz App — 500+ MCQs covering scheduling, synchronization, pointers, and more.
Download on Google Play →