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

Codexion: Concurrency and Scheduling Simulation

Description

Codexion is a modernized, advanced variation of Edsger W. Dijkstra’s classic "Dining Philosophers" concurrency problem. Instead of philosophers and forks, this simulation features coders and USB dongles. The goal of the project is to safely orchestrate multiple threads (coders) competing for limited shared resources (dongles) to compile code without "burning out" (starving).

Unlike the traditional problem, this simulation introduces mandatory hardware cooldowns and strict arbitration policies. Access to shared resources is strictly regulated by a custom-built Min-Heap Priority Queue, enforcing either FIFO (First In, First Out) or EDF (Earliest Deadline First) scheduling algorithms to guarantee fair access and prevent starvation.

Feature List

• Dynamic Concurrency: Spawns distinct POSIX threads for every coder alongside a dedicated, highly precise monitor thread.
• Custom Scheduling Algorithms: Supports both FIFO (fairness by arrival) and EDF (fairness by impending burnout deadline) using a fully custom Priority Queue.
• Hardware Cooldowns: Enforces strict, millisecond-accurate unavailability periods for physical dongles after they are released.
• Parallel Bypass Logic: Allows lower-priority coders to intelligently bypass the queue and compile simultaneously if their required hardware does not conflict with higher-priority requests, maximizing throughput.
• Precision Monitoring: Detects starvation (burnout) within a strict <10ms window without continuously busy-looping the CPU.
• Thread-Safe Logging: Strictly serializes all standard output to prevent interleaved or garbled console logs.
• Leak-Free Execution: Cleanly allocates, manages, and frees all memory and threading primitives, executing flawlessly under Valgrind (Memcheck/Helgrind) and ThreadSanitizer.

Instructions

Compilation

The project includes a Makefile that compiles the source files. To compile the project, run:

make

Other available commands:

• make clean: Removes the object files.
• make fclean: Performs clean and removes the codexion executable.
• make re: Recompiles the entire project from scratch.

Execution

Run the executable with the following mandatory arguments:

./codexion <num_coders> <time_to_burnout> <time_to_compile> <time_to_debug> <time_to_refactor> <req_compiles> <cooldown> <scheduler>

• num_coders: The number of coders (and the number of dongles).
• time_to_burnout: Time (in ms) a coder can go without compiling before burning out.
• time_to_compile: Time (in ms) spent holding two dongles to compile.
• time_to_debug: Time (in ms) spent debugging.
• time_to_refactor: Time (in ms) spent refactoring.
• req_compiles: If all coders compile this many times, the simulation ends successfully. (Must be a positive integer).
• cooldown: Time (in ms) a dongle is locked after being released.
• scheduler: The arbitration policy: fifo or edf.

Testing & Edge Cases

During development, specific edge cases were used to detect architectural faults and harden the simulation against deadlocks and data races. You can test them using the following commands:

• Standard Run: ./codexion 4 3000 200 200 200 2 100 fifo

Verifies basic functionality, scheduling, and standard lifecycle. Below is a sample of a correct, parallel execution where coders successfully reach the required 2 compiles without burning out:

0 1 has taken a dongle
0 1 has taken a dongle
0 1 is compiling
0 3 has taken a dongle
0 3 has taken a dongle
0 3 is compiling
200 1 is debugging
200 3 is debugging
300 2 has taken a dongle
300 2 has taken a dongle
300 2 is compiling
300 4 has taken a dongle
300 4 has taken a dongle
300 4 is compiling
400 1 is refactoring
400 3 is refactoring
500 2 is debugging
500 4 is debugging
600 1 has taken a dongle
600 1 has taken a dongle
600 1 is compiling
600 3 has taken a dongle
600 3 has taken a dongle
600 3 is compiling
700 2 is refactoring
700 4 is refactoring
800 1 is debugging
800 3 is debugging
900 2 has taken a dongle
900 2 has taken a dongle
900 2 is compiling
900 4 has taken a dongle
900 4 has taken a dongle
900 4 is compiling
1100 2 is debugging
1100 4 is debugging
--- Simulation Finished Safely ---

• The Deadlock Trap:

./codexion 2 200 100 0 0 2 0 fifo

This highly constrained environment initially caused an AB-BA Lock Inversion between the Monitor thread (trying to print a burnout) and a Coder thread (trying to grab the arbitrator). It led to the architectural decision to unlock the arbitrator early before executing terminal output.

• The ThreadSanitizer & Helgrind Stress Test:

./codexion 4 1000 200 200 200 2 0 edf

Compiled with -fsanitize=thread or run with valgrind --tool=helgrind, this test verified the absolute absence of Data Races. It exposed circular wait potentials, when the last coder grabs the dongle which the first coder also grabs, leading to the implementation of Hierarchical Locking and a dedicated state_lock (comparing the integer IDs of the two required dongles and forcing the coders to strictly lock the lower-numbered mutex first, breaking the circular wait graph).

Common Tests

• ./codexion 4 1000 200 200 200 5 100 fifo : even group
• ./codexion 5 1000 200 200 200 5 100 fifo : odd group
• ./codexion 200 2000 60 60 60 2 60 edf : scale limit
• ./codexion 1 800 200 200 200 5 0 fifo : lone coder
• ./codexion 4 199 200 200 200 5 0 fifo : burn out
• ./codexion 4 800 200 200 200 3 0 fifo | grep "has taken a dongle" | wc -l : no duplication
• ./codexion 4 2000 100 100 100 3 600 fifo : cooldown
• ./codexion 5 600 150 150 150 5 50 fifo : scheduler burns
• ./codexion 5 600 150 150 150 5 50 edf : scheduler persists
• valgrind --tool=helgrind ./codexion 10 1000 60 60 60 5 60 edf : serialization

Technical Choices

• C & POSIX Threads: The simulation is written strictly in C, utilizing the <pthread.h> library for multithreading. It complies with the rigid "42 Norm" coding standard (e.g., maximum of 5 functions per file, strict 25-line limits per function).
• Min-Heap Array: The Priority Queue was implemented as an array-backed Min-Heap rather than a linked list. This ensures contiguous memory access for better cache performance and maintains O(log n) time complexity for insertions and removals.
• Condition Variables vs. Busy-Waiting: Instead of burning CPU cycles in standard while loops waiting for hardware, the architecture utilizes pthread_cond_wait and pthread_cond_timedwait. This allows threads to sleep efficiently and instantly wake when the OS signals that resources are available.
• Granular Lock Segregation: Rather than relying on a single massive mutex that bottlenecks the entire application, the architecture splits responsibilities into multiple locks: a state_lock for lightweight variables, a print_lock for terminal I/O, and an arbitrator for complex logical state checks.

Blocking Cases Handled

This simulation actively mitigates all major concurrency pitfalls:

• Deadlock Prevention & Coffman’s Conditions: Deadlocks typically occur when the "Hold and Wait" condition is met. This is prevented by the central arbitrator mutex. A coder evaluates the state of both required dongles simultaneously. If both are not free, the coder does not pick up either dongle; instead, they enter a sleep state.
• Circular Wait Prevention (Hierarchical Locking): To prevent ThreadSanitizer from detecting lock-order inversions (e.g., Coder 4 locks Dongle 3 then 0, while Coder 1 locks 0 then 1), coders are forced to physically lock their assigned dongle mutexes in strictly ascending numerical order.
• Starvation Prevention (Liveness): The custom Priority Queue completely eliminates starvation. If edf (Earliest Deadline First) is selected, coders with imminent burnout deadlines bypass recently active coders. If fifo is selected, strict arrival order is maintained.
• Cooldown Handling: Dongle hardware cooldowns are enforced by logging a dongle_ready_time timestamp. The system checks current_time >= dongle_ready_time. If the cooldown hasn't expired, the coder uses pthread_cond_timedwait to sleep exactly until the millisecond the cooldown drops.
• Precise Burnout Detection: Standard usleep() is imprecise due to OS thread scheduling. Burnout is managed by a standalone monitor thread that constantly checks current_time - last_compile against time_to_burnout, utilizing highly optimized gettimeofday queries.
• Log Serialization: To prevent jumbled standard output, all terminal output is routed through a thread-safe logging function protected by a dedicated print_lock mutex.

Thread Synchronization Mechanisms

To ensure thread-safe communication and state management, the architecture relies heavily on POSIX synchronization primitives:

• pthread_mutex_t:

• Dongles Array: Each physical dongle has its own mutex. While the logical state (free/cooldown) is managed by the arbitrator, the actual locking of the dongle mutex guarantees absolute exclusive access.

• Print Lock: Ensures printf calls are safely serialized.

• Arbitrator: The core "global lock" of the simulation. It protects the Priority Queue array, the dongle_ready_time arrays, and condition variable checks.

• State Lock: A lightweight, dedicated lock explicitly used to protect reads and writes of shared state variables (like sim_active, last_compile, and compiles_done), completely eliminating Data Races without bottlenecking the main arbitrator.

• pthread_cond_t:

• Coder Condition Array: Instead of busy-looping, a coder thread evaluates if it can compile. If it cannot, it calls pthread_cond_wait (or pthread_cond_timedwait for cooldowns). This safely puts the thread to sleep and unlocks the arbitrator for others.

• When a coder drops their dongles, they call pthread_cond_signal on the sleeping threads, instructing them to wake up, re-lock the arbitrator, and check if their requested dongles are now available.

• Preventing Race Conditions: A race condition could occur if a coder checks the priority queue, determines they can compile, but gets suspended by the OS before actually locking the dongles. Because the entire can_compile evaluation, queue extraction, and LLONG_MAX state claim happens sequentially inside the locked arbitrator mutex, the state is mathematically guaranteed not to change.

• Thread-Safe Communication with Monitor: When the monitor detects a burnout, it must cleanly shut down coders who are currently sleeping. The monitor locks the state_lock, sets sim_active to 0, locks the arbitrator, and uses pthread_cond_broadcast to instantly wake all sleeping coders. The coders wake up, notice the simulation is inactive, immediately drop their requests, and safely exit to be joined by the main thread.

Resources

• Classic References:

• Dining Philosophers Problem (Wikipedia)

• POSIX Threads (pthread) Documentation

• Coffman's Conditions for Deadlock

• CodeVault: POSIX Threads (pthreads) Playlist - An incredibly comprehensive video series breaking down mutexes, condition variables, and practical C multithreading concepts.

• AI Usage: During the development of this project, I used an AI assistant (Google's Gemini) as a virtual tutor and guide. The AI assisted by explaining complex thread synchronization concepts (like the mathematical mapping of a Min-Heap onto a flat array), and structuring a phased approach to the architecture. It was highly instrumental in analyzing -fsanitize=thread and Helgrind outputs, helping to identify and resolve unprotected data races via a dedicated state_lock, and fixing AB-BA lock-order inversions through Hierarchical Locking. It also provided guidance on adhering to the strict 42 Norm requirements by suggesting clean functional abstractions.