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

Description

Codexion is a concurrency simulation project designed to master resource synchronization, thread management, and scheduling algorithms. The simulation involves a group of coders sitting around a circular table, competing for shared resources (USB dongles) to compile their quantum code.

The goal is to orchestrate these coders using POSIX threads and mutexes to ensure they eat (compile), sleep (debug), and think (refactor) without running into race conditions, deadlocks, or burning out due to resource starvation. The project requires implementing specific scheduling policies (FIFO and EDF) to optimize resource allocation.

Instructions

Compilation

To compile the project, run the following command at the root of the repository:

make

This will generate the codexion executable.

Execution

The program takes the following arguments:

./codexion <nb_coders> <t_burnout> <t_compile> <t_debug> <t_refactor> <nb_compiles> <cooldown> <scheduler>

• nb_coders: Number of coders (and dongles).
• t_burnout: Time in ms before a coder burns out if they haven't started compiling.
• t_compile: Duration of compilation.
• t_debug: Duration of debugging.
• t_refactor: Duration of refactoring.
• nb_compiles: Number of times each coder must compile to stop the simulation.
• cooldown: Time in ms a dongle remains unavailable after use.
• scheduler: Scheduling policy (fifo or edf).

Example

./codexion 2 210 100 50 50 5 10 edf

Blocking cases handled

This project addresses several critical concurrency issues:

• Deadlock Prevention (Dijkstra's Solution): To prevent a circular wait (deadlock) where every coder holds their left dongle and waits for the right one, I implemented a strict resource hierarchy.

• Coders always attempt to lock the dongle with the lower ID (index) first, then the higher one.

• Implementation: In init_coder, the order of first_dongle and second_dongle is determined by comparing their indices.

• Starvation Prevention (EDF Scheduler): Under the EDF (Earliest Deadline First) policy, the simulation prioritizes the coder closest to burnout. By comparing the last_compile_time, the system ensures that critical threads access resources before those with more time margin, effectively preventing starvation provided the parameters allow a mathematical solution.

• Dongle Cooldown: The project handles resource "cool down" periods. Even if a mutex is available, a coder cannot take a dongle if the dongle_cooldown time hasn't elapsed since its last release. The coder is put to sleep (ft_usleep) until the resource is truly ready.

• Precise Burnout Detection: A dedicated Monitor Thread runs in parallel to check the health of all coders. It detects burnout within the required 10ms precision window, even if a coder is currently sleeping or waiting for a mutex, ensuring immediate simulation termination.

• Log Serialization: To prevent garbled output from multiple threads writing to stdout simultaneously, all logs are protected by a dedicated mutex (print_mutex).

Thread synchronization mechanisms

The project uses the following POSIX primitives and logic:

• Mutexes (pthread_mutex_t):

• Dongle Protection: Each dongle has a mutex to ensure mutual exclusion.

• Shared Data: Coders' last_compile_time and nb_compiles are protected to prevent data races between the coder thread and the monitor thread.

• Simulation State: A global flag simulation_running is protected to allow clean exit across all threads.

• Condition Variables (pthread_cond_t): Used to manage the waiting queue for dongles. Coders wait on a condition variable when a dongle is busy or in cooldown, avoiding busy-waiting (CPU spinning). pthread_cond_broadcast is used to wake up waiting coders when a resource is released or when the simulation ends.

• Priority Queue (Heap) Implementation: The subject requires a Priority Queue (Heap) for scheduling.

• Context: Since a dongle is shared by exactly two specific neighbors (Circular Topology), the waiting queue size is strictly bounded to .

• Implementation: An array of 2 elements is technically a valid Binary Tree (Index 0 is Root, Index 1 is Left Child).

• Logic:

• Insert (Sift Up): When adding a coder to the queue in EDF mode, we compare the new coder with the existing one (if any). If the new coder has an earlier deadline (priority), we swap them. This maintains the Heap Property (Parent Child).

• Pop (Sift Down): When the resource is taken, the second coder (if present) moves to position 0, effectively becoming the new root.

• This provides a highly optimized Heap implementation tailored for the specific constraints of the problem.

Resources

• Documentation:

• man pthreads

• Modern C Programming (O'Reilly) - Threads and Atomics chapters.

• Articles on the Dining Philosophers Problem (Dijkstra's algorithm).

• AI Usage: AI assistance was used during this project for:

• Debugging: Analyzing race conditions in the initial implementation of the monitor thread.

• Edge Case Analysis: Understanding the mathematical limits of the circular topology (specifically why 3 coders with specific timings cause bottlenecks).

• Subject Clarification: Verifying the specific requirements for the Heap implementation regarding the constraint.

• Drafting: Helping structure this README file to ensure all mandatory sections were covered.