Here you'll find:

• The philosphers project breakdown.
• Theory breakdown for better understanding.
• Tips based on my experince doing this project for people wanting to do it as well.

---

Introduction

The Dining Philosophers Problem is a classic computer science thought experiment that illustrates the challenges of synchronizing concurrent processes. It depicts a group of silent philosophers sitting at a round table who alternate between three states: eating, sleeping, and thinking. The catch is that there is only one fork between each pair of neighbors, but a philosopher needs two forks to eat their spaghetti. This creates a fierce competition for shared resources, serving as a direct metaphor for threads accessing shared memory in an operating system. The ultimate goal is to design an algorithm that allows everyone to eat without causing a Deadlock (where everyone holds one fork and waits forever) or Starvation (where a philosopher dies waiting).

---

📜 Project Specification & Rules

The simulation is governed by a strict set of rules and arguments that define the behavior of the philosophers and their environment.

---

Command Line Arguments

The program must be executed with the following parameters:

./philo number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_meals]

Argument Details

Argument	Unit	Description
number_of_philosophers	—	The number of philosophers and also the number of forks available.
time_to_die	ms	If a philosopher does not start eating within this timeframe (since the start of their last meal or the simulation start), they die.
time_to_eat	ms	The time it takes for a philosopher to eat. They will hold two forks during this period.
time_to_sleep	ms	The time a philosopher spends sleeping.
[number_of_meals]	—	(Optional) If all philosophers eat at least this many times, the simulation ends. If not specified, the simulation stops only upon death.

---

The Round Table Logic

Topology

• Philosophers sit at a round table
• Philosopher 1 sits next to Philosopher N
• Any Philosopher N sits between N-1 and N+1

Resources (Forks)

• There is one fork between each pair of philosophers

Constraint

• To eat, a philosopher must successfully acquire two forks:

  • One on their left
  • One on their right

Edge Case

• If there is only 1 philosopher, there is only 1 fork
• The philosopher cannot eat and will inevitably die

---

System Logs & Technical Constraints

The program must print state changes in a strict, non-scrambled format. Each log entry includes:

• A timestamp (in milliseconds, relative to the simulation start)
• The philosopher's ID

Log Format Examples

timestamp_in_ms X has taken a fork
timestamp_in_ms X is eating
timestamp_in_ms X is sleeping
timestamp_in_ms X is thinking
timestamp_in_ms X died

---

Critical Performance Requirements

Concurrency

• Each philosopher is a thread
• Each fork is a mutex

Latency

• The message announcing a philosopher’s death must be printed no later than 10ms after the actual death event

Data Safety

• Output must not be interleaved or scrambled
• Guaranteed via a dedicated print_lock mutex

---

Theoretical Background

Understanding the core concepts of concurrency is essential to grasp how this simulation works.
The project is built upon three pillars of operating system theory. If you are new to this project or this world Please read the theory part for more context and how it links with my implemnetation:

---

1. Threads (The Philosophers)

A thread is the smallest unit of execution within a process.
Unlike separate processes (which have isolated memory), threads share the same memory space and resources.

In This Project

• Each Philosopher runs as a secondary thread
• The Monitor runs on the Main Thread

Lifecycle & Ownership

• The Main Thread is the parent
• If the Main Thread terminates before secondary threads finish:
  • The entire process exits
  • All philosopher threads are killed mid-execution

Solution

We use pthread_join to ensure:

• The Main Thread waits for all philosophers to finish
• Cleanup and exit happen only after all threads return

---

2. Concurrency vs. Parallelism

The runtime behavior depends on the hardware:

Parallelism

• On multi-core CPUs
• Threads truly execute at the same time

Concurrency (Time Slicing)

• On single-core CPUs
• Or when threads > CPU cores
• The CPU rapidly switches between threads
• Creates the illusion of simultaneous execution

⚠️ Note:
Threads introduce overhead. While they are necessary here, using threads for simple sequential tasks is often inefficient due to the cost of context switching.

---

3. Race Conditions (The Danger)

Because threads share memory, a Race Condition occurs when:

• Two threads read/write the same variable at the same time
• The result depends on the unpredictable execution order

Example

If two philosophers grab Fork 1 simultaneously without protection:

• Both may believe they own the fork
• This leads to duplicated resources and undefined behavior

---

4. Mutexes (The Solution)

A Mutex (Mutual Exclusion lock) protects shared resources.

Analogy: A Bathroom Key

• Lock: A thread takes the key — no one else can enter
• Action: The resource is safely modified
• Unlock: The key is returned — next thread may enter

Mutex Usage in This Project

• Forks: Ensure only one philosopher holds a fork
• Writing (print_lock): Prevents log interleaving
• Reading (dead_lock, meal_lock): Ensures the Monitor reads consistent data

---

🧠 Deep Dive: System Architecture & Deadlocks

To fully master this project, you must understand:

• The boundary between User Space and Kernel Space
• The mathematical conditions that create deadlocks

---

5. The “Iceberg” Architecture: pthread_t vs. The Kernel

A common misconception:

pthread_t is not the thread itself.

It is merely a handle — a remote control.

What is pthread_t?

The value you receive in a variable of type pthread_t is not the thread itself, but only a thread identifier (a handle).

This identifier allows you to refer to the thread in function calls such as:

• pthread_join()
• pthread_detach()
• pthread_cancel()

but it does not contain the actual execution of the thread.

---

🧠 How to Think About It Intuitively

A pthread_t is similar to:

• A pointer
• A token
• A remote control

The operating system gives it to you so you can manage and interact with the thread, but the real thread (its execution context, stack, and scheduling) lives inside the kernel, not in your variable.

In short:
pthread_t is a reference to a thread, not the thread itself.

User Space (Your Heap)

• data->threads is just an array of thread identifiers
• Allocated with malloc

Kernel Space (The OS)

• The real thread lives here:
  • Execution context
  • Stack
  • Registers
  • Scheduling state

---

The free() Trap 🚨

If you call:

free(data->threads);

without calling pthread_join:

• ❌ You destroy the remote control
• ✅ The OS thread keeps running
• ❌ You lose the ability to manage or stop it

The Result

• Threads continue accessing mutexes or memory
• That memory may already be freed
• 💥 Segmentation Fault

---

Why malloc Is Different

• malloc / free:

  • Manages User Space
  • You own it → free destroys it immediately

• pthread_create:

  • Allocates resources in Kernel Space
  • free() only removes your handle
  • pthread_join() tells the Kernel to clean up the real thread

---

6. Understanding Deadlocks (The Coffman Conditions)

A Deadlock is not random — it occurs only if all four conditions are met simultaneously.

Break one, and deadlock becomes impossible.

The 4 Coffman Conditions

1. Mutual Exclusion A resource (fork) can only be held by one philosopher → ❌ Cannot change (forks are physical)

2. Hold and Wait A philosopher holds one fork while waiting for another → ❌ Cannot change (eating requires two forks)

3. No Preemption Resources cannot be forcibly taken → ❌ Cannot steal forks

4. Circular Wait A closed chain where each philosopher waits for the next

---

Our Solution: Break Circular Wait ✅

We eliminate the 4th condition.

Rule

Philosophers must always acquire forks in a global order (Lowest ID fork first)

Why This Works

• The circular dependency becomes mathematically impossible
• The last philosopher will never hold a high-ID fork while waiting on a low-ID fork
• The chain cannot close → no deadlock

---

🧠 Key Insight: Deadlocks are not timing bugs. They are logical states — and logic can be broken deterministically.

---

1. Initialization & Program Entry

The program entry point (main.c) is designed with a high-level abstraction philosophy. It avoids cluttering the main logic with implementation details, delegating tasks to three distinct stages: Validation, Initialization, and Execution.

int main(int argc, char **argv)
{
    // 1. Parse and validate inputs (Numbers only, valid ranges)
    if (validate_args(argc, argv) == ERROR) ...
    
    // 2. Allocate memory and initialize mutexes
    if (init_data(&data, argc, argv) == ERROR) ...
    
    // 3. Start threads and monitor loop
    if (choose_routine_type(&data) == ERROR) ...
    
    return (0);
}

---

2. Data Setup (init_data)

The initialization phase is strictly modularized to ensure memory safety. If any step fails (malloc failure or mutex init failure), a custom clean_program function is triggered to free only the resources allocated up to that point.

The setup is divided into four key components:

Philosopher Creation (create_philos)

• Allocates memory for the t_philo array

• Assigns unique IDs

• Crucial: Initializes a specific meal_lock for each philosopher

  • Protects the last_meal_time variable
  • Prevents data races between the Philosopher thread (writing) and the Monitor thread (reading)

Resource Allocation (create_forks_and_print)

• Allocates the array of forks (mutexes)

• Initializes global mutexes:

  • print_lock: Ensures console output is not interleaved/scrambled
  • dead_lock: Protects the simulation status (philo_is_dead flag)

Argument Parsing

• Converts time arguments to u_int64_t

• Handles the optional Number of Meals argument

  • If not provided, the simulation runs indefinitely (NOT_ACTIVE)

The Circular Topology (hand_out_forks)

To simulate the round table, pointers for the Left and Right forks are assigned using modular arithmetic. This connects the last philosopher back to the first, closing the ring.

// i = current philosopher ID
// n = total number of philosophers
philos[i].left_side_fork  = &forks[i];
philos[i].right_side_fork = &forks[(i + 1) % n];

• Left Fork: The fork at the philosopher's current index
• Right Fork: The fork at the next index (wraps to 0 for the last philosopher)

---

The clean_program Engine

Instead of a generic “free all” approach, clean_program acts as a surgical destructor. It accepts parameters that dictate exactly which resources have been allocated and need to be released.

void clean_program(t_dinning_info *data, int last_mutex_to_failed, int globa)

Key Mechanisms

Partial Mutex Destruction (clean_forks)

If initialization of the 50th fork fails (in a simulation of 100), a naive cleanup would crash if it attempted to destroy the 51st mutex (never initialized).

Solution:

• Iterate from 0 to last_mutex_to_failed
• Call pthread_mutex_destroy only on valid, initialized mutexes
• Simultaneously destroy the meal_lock associated with each philosopher

Staged Global Cleanup (clean_global_mutex)

A Level System tracks the initialization stage of global locks:

• Level 1 (globa >= 1): Destroys print_lock
• Level 2 (globa == 2): Destroys dead_lock

This prevents destroying mutexes that were never created.

Conditional Memory Freeing

• Pointers (data->forks, data->philos, data->threads) are checked for NULL before calling free()
• Prevents double-free errors and freeing unallocated memory

This architecture guarantees clean termination, even during partial initialization failures—no memory leaks, no zombie locks.

---

3. Core Engine: Monitoring & Thread Routines

The simulation relies on a strict separation of duties:

• Monitor (Main Thread): Oversees death and completion checks
• Philosophers (Worker Threads): Execute lifecycle routines

This ensures death checks occur independently of philosopher state (eating, sleeping, thinking).

---

3.1 The Supervisor Architecture (choose_routine_type.c)

While philosopher threads execute finite_routine or infinite_routine, the main thread becomes a non-blocking Monitor.

• Continuous Auditing: Loops over:

  • check_all_philos_death
  • are_they_full

• CPU Optimization:

  • usleep(100) prevents busy-waiting and yields CPU time

• Atomic Flags:

  • is_it_dead() uses a mutex-protected boolean (philo_is_dead)
  • Safely signals all threads to stop immediately upon death

---

3.2 Deadlock Prevention: The Asymmetric Locking Strategy

The classic Circular Wait deadlock is eliminated algorithmically in activities.c.

Rule:

A philosopher must always acquire the lower-ID fork first.

// activities.c
first = min(left_id, right_id);
second = max(left_id, right_id);

pthread_mutex_lock(first);  // Always lock lower ID
pthread_mutex_lock(second); // Then lock higher ID

Why it works: If philosophers 0–3 lock their left forks, philosopher 4 attempts to lock fork 0 (right) before fork 4 (left). Since fork 0 is already held, philosopher 4 waits—leaving fork 4 free for philosopher 3 to finish, breaking the cycle.

---

3.3 High-Precision Timing & “Sliced Sleeping”

Standard usleep is blocking; a 200ms sleep cannot react to a death at 50ms.

Solution: Sliced Sleeping

• Granularity: Sleep in chunks of 500µs
• Responsiveness: After each chunk, check is_it_dead()

The simulation can terminate within ~0.5ms after a death instead of waiting for long sleeps to finish.

---

3.4 Synchronization & Staggering (routines.c)

To avoid a Thundering Herd at t = 0:

Start Gate

• Threads spin-wait on a shared start flag
• Ensures synchronized start_time

Odd/Even Staggering

• Startup: Odd-numbered philosophers wait 2ms

• Runtime:

  • If philosopher count is odd, philos_sleep adds a 1ms delay
  • Prevents starvation in tight loops (e.g. 5 800 200 200)

---

⏱️ Thread Lifecycle & Time Management

1. Thread Initialization & the “Start Gate”

Threads start immediately upon pthread_create, but execution is paused via a synchronization barrier:

static void wait_for_start(t_dinning_info *data, t_philo *philo)
{
    while (!data->start)
        usleep(100); // Spin-wait with backoff to save CPU
    // ...
}

The Monitor sets start_time and flips data->start to TRUE, releasing all threads simultaneously.

---

2. Relative Time System

The simulation uses Relative Time, not absolute system time.

• T = 0: When data->start becomes true
• Current Time: Absolute_Time - Start_Time

This guarantees coherent timestamps and accurate death checks across threads.

---

3. Execution & Zombie Prevention

• Philosophers loop: Eat → Sleep → Think

• Atomic checks before every major action:

  • Printing
  • Eating
  • Sleeping

Zombie Prevention:

• Before printing states, verify is_it_dead()
• Monitor exits loops on death or meal completion
• pthread_join ensures all threads finish before exit

---

💡 Why This Solution? (The Min/Max Elegance)

Compared to Odd/Even or Last-Philosopher-Swap strategies, the Resource Hierarchy (Min/Max) approach is superior:

• Code Uniformity:

  • Every philosopher runs identical logic
  • No special cases (if (id == last))

• Mathematical Guarantee:

  • Circular wait becomes impossible by design
  • Deterministic, not heuristic

• Zero “Magic Delays”:

  • No reliance on hardcoded sleeps
  • Works regardless of CPU speed or scheduler behavior

---

💡 Tips for Future Students

If you are tackling the Dining Philosophers problem, here are the critical lessons learned during the development of this project.

---

1. Consistency in Timekeeping (Relative vs. Absolute)

Choose one time reference and stick to it.

Mixing system time (wall clock) with simulation time (time since start) is the #1 cause of timing bugs.

Recommended Approach:
Use Relative Time:

current_time = now() - start_time

This guarantees that 0ms is always the exact moment the simulation began, regardless of system delays or thread scheduling.

---

2. The “Sliced Sleep” Technique

Avoid a single long sleep like:

usleep(200000); // ❌ Bad

If a philosopher sleeps for 200ms in one block, they become blind to death events during that time.

✅ Correct Approach

Slice the sleep into small chunks:

while (elapsed < limit)
{
    usleep(slice);
    check_death();
}

Performance Warning ⚠️

• Slices that are too small (e.g. 100µs) cause massive context switching
• With many threads, this can saturate the CPU

Sweet Spot: 👉 500µs – 1000µs balances responsiveness and efficiency

---

3. Atomic State Checks (Avoid Zombies)

Always check is_it_dead():

• Before printing
• After every action (eating / sleeping)

Why?

If a philosopher dies while waiting for a fork and you don’t re-check immediately, they might print:

is eating

after they are already dead.

This creates Zombie Philosophers and fails the assignment.

---

4. Protect Your Output

Never use printf without a mutex in a multithreaded program.

❌ Without protection:

100 1 is ea100 2 is sleeping

✅ With protection:

• Use a dedicated print_lock
• Lock → print → unlock

This guarantees clean, readable logs.

---

5. Algorithm Over Hardcoding

Avoid:

• “Magic numbers”

• Special-case logic like:

  if (id == 100) usleep(500);

These solutions:

• Depend on CPU speed
• Break on different machines
• Are fragile and non-deterministic

✅ Recommendation

Use a Resource Hierarchy approach (e.g. the Min/Max Fork Rule)

Why it’s superior:

• Mathematically prevents deadlocks
• No timing hacks
• Scales to any number of philosophers
• Independent of hardware speed

---

6. The “Unlock Before Return” Rule

If a philosopher detects the end of the simulation while holding a fork:

👉 They MUST unlock it before returning

The Trap

Returning early without unlocking causes:

• Neighbor threads to block forever
• pthread_join to hang
• Program never exits → ❌

The Rule

Always follow this pattern rr something like this. I wanted to save lines so it is not explicity like this (i make up for it with some checks) but you get the main idea:

Lock
Check for death
If dead:
    Unlock
    Return
Action

---

7. Surgical Mutex Destruction

Never destroy a mutex that was never initialized.

Scenario

• Creating 200 forks
• Initialization fails at fork 150

❌ Wrong:

destroy all 200 mutexes

✅ Correct:

• Track how many mutexes were successfully created
• Destroy only those

Why?

Calling pthread_mutex_destroy on garbage memory leads to:

• Immediate Segmentation Fault

---

8. The Graceful Exit (No Rage-Quiting)

When a philosopher dies:

❌ Do NOT

• Call exit()
• Call clean_program() from the philosopher thread

The Risk

Other threads may still be running and will:

• Access freed memory
• Crash with Use-After-Free

✅ The Correct Shutdown Sequence

1. Flag Set:

   philo_is_dead = 1
   

2. Wait Let all threads detect the flag and exit naturally

3. Join Main thread waits using pthread_join

4. Clean Only then:

   • Free memory
   • Destroy mutexes

This guarantees a clean, deterministic shutdown with no crashes.

---

🧠 Final Advice: If your solution depends on timing luck, it’s wrong. If it depends on ordering and invariants, it’s solid.

---

Compilation

Use the provided Makefile:

make

---

Execution

./philo [number_of_philosophers] [time_to_die] [time_to_eat] [time_to_sleep] [number_of_times_each_philosopher_must_eat (optional)]

---

Examples

1. Death Test (Should die)

A philosopher dies due to tight time_to_die.

./philo 4 310 200 100

2. Endless Test (Should survive)

Standard simulation with no deaths.

./philo 5 800 200 200

3. Meal Count Test

Stops after each philosopher eats 7 times.

./philo 5 800 200 200 7