This project has been created as part of the 42 curriculum by lvasconc.

Codexion

Description

Codexion is a concurrent multithreading simulation inspired by the classic "Dining Philosophers" problem, adapted to explore real-world concurrency challenges. Instead of philosophers competing for forks, coders compete for USB dongles—essential hardware resources required to compile their code.

Goal

The project demonstrates:

• Deadlock prevention through resource ordering and careful synchronization
• Starvation mitigation via scheduling algorithms (FIFO and EDF)
• Burnout detection to track thread resource starvation over time
• Race condition prevention using mutexes and condition variables
• Precise thread coordination in a complex multi-resource scenario

How It Works

Multiple coders must repeatedly execute a compile-debug-refactor cycle:

1. Acquire two consecutive USB dongles (e.g., Coder 2 needs dongles 2 & 3)
2. Compile using the dongles
3. Release the dongles
4. Debug (without resources)
5. Refactor (without resources)
6. Repeat until all required compilations complete

Each coder has a burnout deadline—if they cannot acquire resources and complete a cycle before this deadline expires, the simulation terminates with a burnout event. The scheduler determines which waiting coder gets the next turn at resources.

---

Instructions

Compilation

make

Or using the threaded compilation flag if needed:

cc -pthread -Wall -Wextra -Werror -o codexion main.c init.c util.c utils.c coder_actions.c monitor_actions.c

Execution

./codexion <num_coders> <burnout_ms> <compile_ms> <debug_ms> <refactor_ms> <cycles> <cooldown_ms> <scheduler>

Parameters:

Parameter	Type	Description	Example
num_coders	int	Number of concurrent coders (threads)	5
burnout_ms	int	Deadline threshold per cycle in milliseconds	1000
compile_ms	int	Time to compile with dongles	200
debug_ms	int	Time to debug (without resources)	100
refactor_ms	int	Time to refactor (without resources)	100
cycles	int	Number of compile cycles per coder	7
cooldown_ms	int	Optional delay after releasing dongles	0
scheduler	string	Scheduling strategy: fifo or edf	fifo

Example Runs

Successful execution (adequate time):

./codexion 3 1200 200 100 100 3 0 fifo

Burnout scenario (insufficient time):

./codexion 4 400 200 100 100 7 0 edf

Safe execution with margin:

./codexion 5 3000 200 100 100 7 0 fifo

System output format:

<timestamp_ms> <coder_id> <event>
0 0 has taken a dongle
0 0 has taken a dongle
0 0 is compiling
200 0 is debugging
300 0 is refactoring

---

Blocking Cases Handled

1. Deadlock Prevention

Problem: In the standard dining philosophers problem, circular wait can cause all threads to deadlock—each coder holds one dongle and waits for another, creating a cycle of dependencies.

Solution Implemented:

• Resource Ordering: Odd-numbered coders acquire dongles in reverse order (second then first) while even-numbered coders use normal order. This prevents circular wait dependencies.
• Atomic Mutex Operations: All dongle acquisitions are protected by scheduler (sched_mutex) to serialize access to the resource allocation decision.

Code Evidence (coder_actions.c):

if (c->id % 2 != 0) {
    first = second;
    second = c->id;  // Odd coders acquire in reverse
}

2. Starvation Prevention

Problem: Without scheduling, low-priority threads might wait indefinitely while others continuously acquire resources.

Solutions Implemented:

• FIFO Scheduler: Maintains fairness by serving coders in queue order. The is_waiting[] array tracks which coders are queued.

• EDF (Earliest Deadline First) Scheduler: Prioritizes coders whose burnout deadline is soonest, ensuring those at risk complete work first.

Code Evidence (utils.c):

int is_highest_priority(t_coder *c) {
    if (res->deadlines[i] < res->deadlines[c->id] ||
        (res->deadlines[i] == res->deadlines[c->id] && i < c->id))
        highest = 0;  // Another coder has higher priority
}

3. Burnout Detection

Problem: Coders might exceed their deadline while stuck waiting for resources, simulating thread starvation.

Solution Implemented:

• Deadline Refresh on Request: Every time a coder enters the scheduler queue, their deadline is refreshed to current_time + burnout_threshold in request_dongles().
• Monitor Thread: Continuously checks if any coder's deadline has expired. If exceeded, triggers global stop_sim flag.
• Precise Timing: Uses gettimeofday() for microsecond-level precision via get_now_micros().

Code Evidence (coder_actions.c):

res->deadlines[c->id] = get_now_micros() + (c->time_to_burnout * 1000);

Code Evidence (monitor_actions.c):

if (get_now_micros() > m->deadlines[i]) {
    m->stop_sim = 1;  // Trigger burnout
    printf("%ld %d BURNOUT! Quitting.\n", get_timestamp(m), i);
}

4. Log Serialization (Preventing Garbled Output)

Problem: Multiple threads printing simultaneously can interleave output, making logs unreadable.

Solution Implemented:

• Atomic Print Operations: print_status() holds stop_lock mutex during printf to ensure atomic writes.
• Timestamp Consistency: All logs include a synchronized timestamp (relative to simulation start).

Code Evidence (util.c):

void print_status(t_monitor *m, int id, char *str) {
    pthread_mutex_lock(&m->stop_lock);
    if (!m->stop_sim)
        printf("%ld %d %s\n", get_timestamp(m), id, str);
    pthread_mutex_unlock(&m->stop_lock);
}

5. Race Conditions on Shared State

Problem: Multiple threads access and modify stop_sim, is_waiting[], and deadlines[] simultaneously.

Solution Implemented:

• stop_lock Mutex: Protects global stop_sim flag and deadline array writes.
• sched_mutex: Serializes scheduler operations and waiting status updates.
• Dongle Mutexes: Protect individual resource access (dongles[]).

Coffman's Conditions Check:

• ✅ Mutual Exclusion: Ensured by all mutexes (cannot simultaneously hold same dongle)
• ✅ Hold and Wait: Mitigated by scheduler—coders request all resources at once before waiting
• ✅ No Preemption: Coders voluntarily release resources after work, preventing starvation cycles
• ✅ Circular Wait: Prevented by resource ordering (odd/even strategy)

---

Thread Synchronization Mechanisms

Synchronization Primitives Used

1. pthread_mutex_t (Mutual Exclusion Locks)

Purpose: Ensure only one thread accesses a protected region at a time.

Instances in Codexion:

Mutex	Protected Resource	Purpose
dongles[num_coders]	USB dongle resources	Each mutex guards one dongle; coders lock pairs
sched_mutex	Scheduler queue & waiting state	Serializes scheduling decisions and is_waiting[] updates
stop_lock	Global simulation state	Protects stop_sim flag, deadline checks, atomic logging

Example - Dongle Acquisition (coder_actions.c):

pthread_mutex_lock(&c->monitor->dongles[first]);
print_status(c->monitor, c->id, "has taken a dongle");
pthread_mutex_lock(&c->monitor->dongles[second]);
// Critical section: Coder exclusively uses both dongles
pthread_mutex_unlock(&c->monitor->dongles[second]);
pthread_mutex_unlock(&c->monitor->dongles[first]);

Protection Strategy: Coders acquire dongles in deterministic order (even ascending, odd descending) to prevent deadlock from circular wait.

2. pthread_cond_t (Condition Variables)

Purpose: Allow threads to wait for specific conditions and wake efficiently.

Instance in Codexion:

Condition Variable	Associated Mutex	Triggered By	Purpose
sched_cond	sched_mutex	Resource release (release_turn())	Wake waiting coders when resources become available

Example - Scheduler Wait (monitor_actions.c):

void check_priority_and_burnout(t_coder *c, t_monitor *res) {
    res->is_waiting[c->id] = 1;
    while (!is_highest_priority(c)) {
        pthread_cond_wait(&res->sched_cond, &res->sched_mutex);
        // Awakened when another coder broadcasts
    }
    res->is_waiting[c->id] = 0;  // Got the turn
    return (1);
}

Broadcast Pattern (coder_actions.c):

void release_turn(t_coder *c) {
    pthread_mutex_lock(&res->sched_mutex);
    if (res->scheduler_type == 1)  // EDF scheduler
        pthread_cond_broadcast(&res->sched_cond);  // Wake all waiters
    pthread_mutex_unlock(&res->sched_mutex);
}

3. Custom Thread Coordination via Shared State

Pattern: Boolean arrays and timestamps serve as event markers.

Shared Variable	Type	Purpose	Protection
is_waiting[num_coders]	int array	Track which coders are blocked in scheduler	sched_mutex
deadlines[num_coders]	long array	Store per-coder burnout deadline	stop_lock
stop_sim	int	Global shutdown flag	stop_lock

Example - Cooperative Shutdown (main.c):

while (i < mon->num_coders)
    pthread_join(th[i++], NULL);  // Wait for all coders
pthread_mutex_lock(&mon->stop_lock);
mon->stop_sim = 1;  // Signal monitor thread
pthread_cond_broadcast(&mon->sched_cond);
pthread_mutex_unlock(&mon->stop_lock);
pthread_join(m_th, NULL);  // Wait for monitor

---

Race Condition Prevention Examples

Example 1: Safe Burnout Detection

Potential Race Condition: Monitor thread checks deadline while coder is updating it.

Prevention (request_dongles() + monitor_actions.c):

// Coder side: Update deadline atomically
pthread_mutex_lock(&res->stop_lock);
res->deadlines[c->id] = get_now_micros() + (c->time_to_burnout * 1000);
pthread_mutex_unlock(&res->stop_lock);

// Monitor side: Read deadline atomically
pthread_mutex_lock(&m->stop_lock);
if (get_now_micros() > m->deadlines[i]) {
    m->stop_sim = 1;
}
pthread_mutex_unlock(&m->stop_lock);

Example 2: Safe Logging with Interruption Check

Potential Race Condition: Coder prints after stop_sim is set, or logging from multiple threads simultaneously.

Prevention (util.c):

void print_status(t_monitor *m, int id, char *str) {
    pthread_mutex_lock(&m->stop_lock);
    if (!m->stop_sim)  // Check still inside lock
        printf("%ld %d %s\n", get_timestamp(m), id, str);
    pthread_mutex_unlock(&m->stop_lock);  // Atomic operation
}

Example 3: Scheduler Priority Check (Non-blocking Read)

Potential Race Condition: is_waiting[] or deadlines[] could be modified during priority check.

Prevention (utils.c):

int is_highest_priority(t_coder *c) {
    pthread_mutex_lock(&res->stop_lock);  // Lock BEFORE reading shared state
    while (i < res->num_coders) {
        if (i != c->id && res->is_waiting[i]) {
            // Safe read: deadline cannot change during this block
            if (res->deadlines[i] < res->deadlines[c->id])
                highest = 0;
        }
        i++;
    }
    pthread_mutex_unlock(&res->stop_lock);
    return (highest);
}

---

Resources

References & Documentation

• Dining Philosophers Problem https://en.wikipedia.org/wiki/Dining_philosophers_problem Classic concurrency problem demonstrating deadlock and synchronization challenges.

• POSIX Threads (pthreads) Manual https://man7.org/linux/man-pages/man7/pthreads.7.html Complete reference for pthread_mutex_t, pthread_cond_t, and threading primitives.

• Condition Variables: pthread_cond_t https://man7.org/linux/man-pages/man3/pthread_cond_wait.3p.html Detailed explanation of condition variable semantics and spurious wakeups.

---

How AI Was Used

AI assisted with:

1. Bug Diagnosis and Debugging (10% of AI involvement)

   • Identified the inverted scheduler logic (strcmp instead of !strcmp) causing FIFO to enable EDFt
   • Traced race conditions in shared state access

2. Documentation and Examples (15% of AI involvement)

   • Generated comprehensive test cases with expected outcomes
   • Created timing formulas for burnout prediction
   • Documented synchronization mechanisms with code snippets

3. Code Optimization (5% of AI involvement)

   • Suggested using broadcast instead of individual signals for EDF
   • Fine-tuned sleep precision (50µs granularity in loops)