"The formulation of a problem is often more essential than its solution." -- Albert Einstein
- Foreword
- The Problem
- How the Simulation Works
- Architecture
- In-Depth: Low-Level and Hardware Concepts
- Building
- Usage
- Demonstration
- Project Structure
- References
In 1965, Edsger W. Dijkstra introduced the Dining Philosophers problem as an examination exercise for students at the Technische Hogeschool Eindhoven. What appeared to be a simple riddle about philosophers and forks became one of the foundational problems in the study of concurrent computing -- a domain where multiple computations execute during overlapping time periods, competing for shared resources, and where the correctness of a program depends not only on what is computed, but on when and in what order.
This project is a from-scratch implementation in C, using nothing beyond the POSIX threads API and standard system calls. Every thread, every mutex, every microsecond of timing is managed explicitly. There are no high-level abstractions hiding the machinery. What you see is what the hardware executes.
A fixed number of philosophers sit at a round table. Between each pair of adjacent philosophers lies a single fork. A philosopher spends their life cycling through three states: thinking, eating, and sleeping. To eat, a philosopher must acquire both the fork to their left and the fork to their right. After eating, they put both forks down and sleep. After sleeping, they think, and the cycle repeats.
There is one constraint that makes this non-trivial: if a philosopher does not begin eating within a fixed duration (time_to_die milliseconds) since the start of their last meal (or since the simulation began, for the first meal), they die, and the simulation terminates immediately.
The core difficulties that arise from this seemingly simple setup are:
- Deadlock: If every philosopher picks up their left fork simultaneously, they all wait forever for the right fork. No progress is ever made.
- Starvation: Even without deadlock, an unfair scheduling pattern can cause one philosopher to be perpetually denied access to forks while its neighbors eat freely.
- Race conditions: When multiple threads read and write shared memory (timestamps, counters, status flags) without synchronization, the program's behavior becomes undefined -- not just incorrect, but unpredictable at the hardware level.
This implementation resolves all three failure modes.
-
Initialization. The program parses command-line arguments, validates all values, and allocates shared data structures: an array of philosopher records, one mutex per fork, a data-protection mutex, and a print-serialization mutex.
-
Thread creation. One POSIX thread is spawned for each philosopher. Each thread enters an independent loop: acquire two forks, eat, release forks, sleep, think, repeat. Threads are staggered at startup to prevent initial contention.
-
Monitoring. A dedicated monitor thread runs concurrently, scanning every philosopher at sub-millisecond intervals. If any philosopher's elapsed time since their last meal exceeds
time_to_die, the monitor declares death and halts the simulation. If all philosophers have reached the optional meal target, it declares success. -
Synchronization. Every access to shared state -- last meal timestamps, meal counters, simulation flags -- is wrapped in
pthread_mutex_lock/pthread_mutex_unlockpairs. Print output is serialized through its own mutex to prevent interleaved terminal writes. -
Termination. All philosopher threads are joined. The monitor thread is joined. All mutexes are destroyed via
pthread_mutex_destroy. All heap memory is freed. The program exits cleanly.
.
├── imgs/ Demonstration images and GIF
├── src/
│ ├── main.c Entry point: init, launch, join, cleanup
│ ├── philo.h Type definitions and function prototypes
│ ├── Makefile Build rules (cc, -Wall -Wextra -Werror -pthread)
│ ├── args/
│ │ ├── args_1.c Argument validation, data init, memory allocation
│ │ └── args_2.c Safe string-to-integer with overflow protection
│ ├── monitor/
│ │ └── monitor.c Death detection and meal completion monitoring
│ ├── print/
│ │ ├── print_1.c Thread-safe action logger and statistics renderer
│ │ └── print_2.c Banner, parameter display, and footer
│ ├── routine/
│ │ ├── routine_1.c Core philosopher loop: eat, sleep, think cycle
│ │ ├── routine_2.c Thread creation and joining
│ │ └── routine_3.c Fork acquisition/release, single-philo case, meal logic
│ └── time/
│ └── time.c Millisecond clock and busy-wait precision sleep
└── Philosophers.pdf Subject specification
The following sections describe what actually happens beneath the source code -- at the operating system, CPU, and hardware level -- when this program runs.
Each philosopher is a POSIX thread (pthread_t) created via pthread_create. At the operating system level, a thread is the smallest unit of execution that the kernel's scheduler can dispatch to a CPU core.
On a modern multicore processor, multiple threads execute truly simultaneously -- one per physical (or logical, in the case of SMT/Hyper-Threading) core. On a single-core machine, the kernel interleaves threads through preemptive multitasking: a hardware timer interrupt fires at regular intervals (typically every 1--10 ms, configurable via the kernel's HZ or tickless settings), and the scheduler's interrupt handler decides whether to continue the current thread or switch to another.
A context switch involves:
- Saving the running thread's entire register file -- program counter, stack pointer, general-purpose registers, floating-point/SIMD state, and any thread-local storage pointer -- into a kernel structure called the thread control block (TCB).
- Loading the saved register state of the next thread from its TCB.
- Flushing or tagging TLB entries if transitioning between address spaces (not applicable here, since all threads share the same virtual address space within a single process).
The cost of a context switch is on the order of 1--10 microseconds on modern hardware, depending on cache warmth and whether floating-point state must be saved. Linux uses the Completely Fair Scheduler (CFS) by default, which models each thread's virtual runtime and always dispatches the thread with the smallest accumulated runtime, ensuring statistical fairness.
In this program, every philosopher thread has its own stack and local variables but shares the heap-allocated t_data structure. This shared memory is where synchronization becomes critical.
A mutex (pthread_mutex_t) provides mutual exclusion. When a thread calls pthread_mutex_lock, it attempts to acquire exclusive ownership. If another thread already holds the lock, the caller blocks: the kernel removes it from the CPU's run queue and places it on a wait queue associated with that mutex. When the owning thread calls pthread_mutex_unlock, the kernel wakes one waiting thread and moves it back to the run queue.
The implementation of mutex locking relies on atomic compare-and-swap (CAS) instructions provided directly by the CPU's instruction set architecture:
-
x86/x86-64: The
LOCK CMPXCHGinstruction performs a read-modify-write cycle on a memory location while asserting the processor'sLOCK#signal on the memory bus (or, on modern CPUs, locking the relevant cache line). This prevents any other core from accessing that cache line for the duration of the operation, guaranteeing atomicity even across cores. -
ARM (ARMv7 and later): The
LDREX/STREX(load-exclusive / store-exclusive) instruction pair uses the cache coherence protocol's exclusive state to detect contention. If another core modifies the target memory between theLDREXandSTREX, the store fails, and the thread retries in a loop. -
On Linux, the fast path of a mutex uses the
futex(fast userspace mutex) system call. If the lock is uncontended, the entire lock/unlock cycle completes in userspace with a single atomic instruction -- no kernel transition at all. Only when contention is detected does the thread enter the kernel to sleep on the futex wait queue.
This program uses three categories of mutexes:
| Mutex | Purpose |
|---|---|
fork_mutexes[i] |
One per fork. A philosopher must hold both adjacent fork mutexes to eat. These model the contested physical resources. |
data_mutex |
Protects all shared simulation state: simulation_stop, death_occurred, last_meal_time, meals_eaten, satisfied_count, total_meals. |
print_mutex |
Serializes printf calls. Without this, concurrent writes to stdout's internal buffer would interleave, producing garbled output. |
On a multicore processor, each core maintains its own L1 and L2 caches. When core 0 writes a value, that write initially lands in core 0's L1 cache. For core 1 to see the updated value, the hardware must propagate the change through the cache coherence protocol.
The dominant protocol on x86 systems is MESI (Modified, Exclusive, Shared, Invalid), which assigns one of four states to each cache line:
| State | Meaning |
|---|---|
| Modified | This core has written to the line. It holds the only valid copy. |
| Exclusive | This core holds the only copy, but it has not been modified. |
| Shared | Multiple cores hold copies. All copies match main memory. |
| Invalid | The line is stale. A read will trigger a cache miss. |
When core 0 writes to a cache line that core 1 holds in Shared state, core 0's write triggers an invalidation message on the interconnect (or snoop bus). Core 1 marks its copy as Invalid. The next time core 1 reads that address, it misses in cache, fetches the updated line from core 0 (via cache-to-cache transfer) or main memory, and sees the new value.
Why this matters for this program: Mutexes serve as memory barriers (also called memory fences). The POSIX specification guarantees that:
pthread_mutex_lockissues an acquire barrier: all loads after the lock see the most recent writes from any core that previously held the lock.pthread_mutex_unlockissues a release barrier: all stores before the unlock are visible to any core that subsequently acquires the lock.
Without these barriers, a compiler or CPU could reorder memory operations across the lock boundary, and a thread might operate on stale cached data indefinitely. This is why every access to simulation_stop, last_meal_time, and other shared fields in this codebase is enclosed within pthread_mutex_lock / pthread_mutex_unlock pairs. The protection is not only against concurrent writes -- it is a guarantee of visibility through the hardware cache hierarchy.
Deadlock occurs when a set of threads forms a circular chain: each holds one resource and waits for another resource held by the next thread in the chain. In the Dining Philosophers problem, the naive approach -- "pick up left fork, then right fork" -- creates exactly this cycle when all philosophers act simultaneously.
The four Coffman conditions, all of which must hold simultaneously for deadlock to occur, are:
- Mutual exclusion -- each fork can be held by at most one philosopher.
- Hold and wait -- a philosopher holds one fork while waiting for another.
- No preemption -- a fork cannot be forcibly taken from a philosopher.
- Circular wait -- a cycle exists in the wait-for graph.
This implementation breaks condition 4 (circular wait) using a resource ordering strategy:
- Even-numbered philosophers acquire
left_forkfirst, thenright_fork. - Odd-numbered philosophers acquire
right_forkfirst, thenleft_fork.
This imposes a partial order on resource acquisition. Because not all threads acquire forks in the same rotational direction around the table, a complete cycle in the wait-for graph is structurally impossible. At least one philosopher in any contending set will always be able to acquire both forks, eat, and release them, breaking any potential chain.
Additionally, for odd philosopher counts, the last philosopher receives an extra initial delay (usleep(2000)) to further stagger the startup pattern and prevent timing-based collisions at the boundary.
Even in a deadlock-free system, starvation can occur if the scheduling pattern perpetually favors certain threads. This implementation mitigates starvation through several coordinated mechanisms:
-
Staggered thread startup. Even-ID philosophers delay 1 ms before entering the main loop. Odd-ID philosophers delay 0.1 ms. For odd philosopher counts, the last philosopher delays 2 ms. This distributes the initial wave of fork acquisition evenly, preventing a thundering herd scenario.
-
Post-think micro-delays. After the think phase, each philosopher calls
usleep(500 us for odd counts, 100 us for even counts). This briefly yields the CPU via a kernel scheduling point, giving neighboring threads an opportunity to acquire forks. -
High-frequency monitoring. The death monitor scans philosopher states every 100 microseconds -- fast enough to detect death within the required tolerance, but not so aggressively as to saturate the
data_mutexwith lock contention.
The sleep_precise function implements a busy-wait (spin loop) for accurate timing:
void sleep_precise(long long milliseconds)
{
long long start = get_time_ms();
while ((get_time_ms() - start) < milliseconds)
usleep(100);
}Standard kernel sleep functions (usleep, nanosleep) request the scheduler to suspend the calling thread for at least the specified duration. The actual wake-up time depends on scheduler latency, timer resolution, and system load. On a busy system, a usleep(200000) (200 ms) call might not return for 210 ms or more.
The busy-wait approach solves this by polling the current time repeatedly and only exiting when the target duration has truly elapsed. The usleep(100) inside the loop is a deliberate compromise:
- It yields the CPU on each iteration, preventing the thread from consuming 100% of a core.
- It maintains sub-millisecond accuracy, since each
usleep(100)resumes within roughly 100--200 microseconds. - Each iteration triggers a brief kernel entry, during which the scheduler may dispatch another thread, ensuring cooperative behavior.
Time measurement uses gettimeofday, which reads the system's wall-clock time with microsecond resolution.
On x86 processors, the underlying hardware clock is the TSC (Time Stamp Counter) -- a 64-bit register (IA32_TSC) that increments at a fixed rate tied to the processor's base or reference clock frequency. On modern CPUs with an "invariant TSC" (constant-rate TSC), this frequency is independent of power states and dynamic frequency scaling, making it a reliable monotonic time source.
The Linux kernel exposes TSC-based time to user-space processes through the vDSO (virtual Dynamic Shared Object) -- a small shared library mapped into every process's address space by the kernel. Functions like gettimeofday and clock_gettime are implemented inside the vDSO so that they bypass the kernel entirely: the function reads the TSC via the RDTSC or RDTSCP instruction (which executes in a few nanoseconds), applies a precomputed scaling factor from the vDSO data page, and returns the result -- all without a system call or context switch. This makes the busy-wait loop in sleep_precise efficient despite its high call frequency.
Requires a POSIX-compliant system (Linux, macOS) with cc (or gcc / clang) and make.
cd src
make # Build the executable
make clean # Remove object files
make fclean # Remove object files and the executable
make re # Full rebuild (fclean + all)The binary is produced as src/philo.
./philo number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]
| Argument | Description |
|---|---|
number_of_philosophers |
The number of philosophers (and forks) seated at the table. Must be a positive integer. |
time_to_die (ms) |
Maximum time in milliseconds a philosopher can go without eating before dying. |
time_to_eat (ms) |
Duration in milliseconds that eating takes. The philosopher holds two forks for this entire period. |
time_to_sleep (ms) |
Duration in milliseconds that sleeping takes. |
number_of_times_each_philosopher_must_eat |
Optional. The simulation stops successfully when every philosopher has eaten at least this many meals. |
All values must be positive integers within the range of a 32-bit signed integer.
./philo 4 410 200 200 7
All four philosophers reach the required meal count. The simulation terminates gracefully with zero deaths.
./philo 1 800 200 200
With only one philosopher and one fork, eating requires two forks, which is impossible. The philosopher dies exactly at time_to_die.
./philo 4 310 200 100
When time_to_die barely exceeds time_to_eat, any scheduling delay is fatal. The monitor detects and reports death within milliseconds of the deadline.
| File | Responsibility |
|---|---|
src/main.c |
Program entry point. Orchestrates initialization, thread lifecycle, statistics output, and resource cleanup. |
src/philo.h |
Central header. Defines t_data, t_philo, and t_safe_atoi structures. Declares all function prototypes. |
src/Makefile |
Build system. Compiles with cc -Wall -Wextra -Werror -pthread. |
src/args/args_1.c |
Parses and validates all arguments. Allocates fork mutexes and the philosopher array. Initializes every field. |
src/args/args_2.c |
safe_atoi -- converts strings to integers with whitespace handling, sign detection, and overflow protection. |
src/monitor/monitor.c |
Monitor thread. Continuously scans for philosopher death and meal-count completion at sub-millisecond intervals. |
src/print/print_1.c |
Thread-safe action printer with color-coded, timestamped output. Post-simulation statistics renderer. |
src/print/print_2.c |
Decorative banners, simulation parameter display, and footer. |
src/routine/routine_1.c |
Core philosopher routine. Manages the eat-sleep-think cycle with stop-condition checks at every transition. |
src/routine/routine_2.c |
create_threads and wait_threads -- spawns and joins all philosopher threads. |
src/routine/routine_3.c |
Fork acquisition with deadlock-safe ordering, fork release, single-philosopher edge case, and meal tracking logic. |
src/time/time.c |
get_time_ms (millisecond clock via gettimeofday) and sleep_precise (busy-wait loop with usleep yielding). |
- Dijkstra, E. W. (1971). Hierarchical Ordering of Sequential Processes. Acta Informatica, 1(2), 115--138.
- Coffman, E. G., Elphick, M., & Shoshani, A. (1971). System Deadlocks. ACM Computing Surveys, 3(2), 67--78.
- Butenhof, D. R. (1997). Programming with POSIX Threads. Addison-Wesley.
- Drepper, U. (2011). Futexes Are Tricky. Red Hat.
- Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual.
- Kerrisk, M. (2010). The Linux Programming Interface. No Starch Press.
- The Open Group. POSIX.1-2017: Threads.
- Linux man-pages project.
pthread_create(3),pthread_mutex_lock(3p),futex(2),gettimeofday(2).
CHIKI Badreddine -- GitHub | LinkedIn
Implementation, architecture, documentation, and technical writing.
Developed as part of the 42 school curriculum.