This project has been created as part of the 42 curriculum by sukang.
While I cannot guarantee that every edge case is handled perfectly or that the implementation is flawless, I have implemented extended output to easily monitor the various states of each coder and USB dongle. The decision was made because the standard output required by the project subject often falls short of providing enough data for deep analysis. Since the 42 curriculum is built on a peer-to-peer evaluation system, I believe it is essential to provide evaluators with clear and detailed information to facilitate a thorough review.
For more details on the implementation, please refer to the Technical Choices section.
The following is the original README.md from the version of the project that was submitted.
This project is reinterpretation of the classic Dining Philosophers problem, a wellknown illustrations of deadlock in operating systems. It is a modified version of the exiting Philosopher project.
- One or more coders sit in a circular inclusive co-working hub. In the center, there is a shared Quantum Compiler.
- The coders alternatively compile, debug, or refactor. While compiling, they are not debugging nor refactoring; while debugging, they are not compiling nor refactoring; and, of course, while refactoring, they are not compiling nor debugging.
- There are USB dongles on the table. There are as many dongles as coders.
- Compiling quantum code requires two dongles plugged in simultaneously, one in each hand: a coder takes their left and right dongles to compile.
- When a coder finishes compiling, they put both dongles back on the table and start debugging. Once debugging is done, they start refactoring. The simulation stops when a coder burns out due to lack of compiling.
- Every coder needs to compile regularly and should never burn out.
- Coders do not communicate with each other.
- Coders do not know if another coder is about to burn out.
- Needless to say, coders should avoid burnout!
-
Thread & Mutex Management: Understanding the usage of threads and mutexes, including synchronization with condition variables.
-
Deadlock & Starvation Avoidance: Learning how to avoid deadlocks and preventing "Burn-out", which refers to a starvation state caused by a process failing to acquire resources for an extended period.
-
Scheduling Optimization: Understanding the impact of execution order among multiple processors and implementing scheduling techniques to improve fairness.
-
Data Structures for Systems: Implementing a Heap data structure specifically designed to manage process priorities within the scheduler.
Commonly referred to as Deadlocks.
Deadlock is a state where two or more threads are stuck in an infinite wait, each holding a resource that another needs. For a deadlock to occur, there must be a least two processors and two shared resources. In this project's scenario, each coder requires two USB dongles to compile their code.
Imagine two coders (Coder A and Coder B) and two USB dongles (USB 1, USB 2).
- Coder A acquires USB 1 and attempts to grab USB 2.
- Simultaneously, Coder B acquires USB 2 and attempts to grab USB 1. Both coders end up waiting indefinitely for the dongle held by the other, resulting in a system freeze.
A deadlock can only occur if all four of Coffman's Conditions are met simultaneously. Conversely, if even on of these conditions is prevented, a deadlock cannot occur.
The four conditions are as follows:
-
Mutual Exclusion: A resource can be held by only one processor at a time.
-
Hold and Wait: A processor holding at least one resource is waiting to acquired additional resources held by other processors.
-
No Preemption: Resource cannot be forcibly taken from a processors. They must be released voluntarily by processor holding them.
-
Circular Wait: A closed chain of processors exists, where each processor holds at least one resource needed by the next processor in the chain.
In this project, I chose to prevent deadlocks by breaking the Circular Wait condition. In most concurrent systems, the first three conditions (Mutual Exclusion, Hold and Wait and No Preemption) are inherent characteristics of the environment. Therefore, breaking the Circular Wait is the most common and practical approach to ensuring system stability.
There are two common ways to break the circle:
- Global Ordering: All coders pick up the lower-numbered USB first.
- Odd/Even Differentiation: Odd-numbered coders pick up the lower-numbered USB first, while even-numbered coders pick up the higher-numbered one first.
I implemented the second approach. While the first method (Global Ordering) effectively prevents deadlocks, it can create a long chain of dependencies where, in the worst cases, only one coder can work at a time. Even if
In this project, both FIFO and EDF schedulers are implemented using a Heap data structure.
- FIFO (First-In, First-Out): Resources are granted in the exact order of request.
- EDF (Earliest Deadline First): Priority is given based on the deadline, calculated as:
last_compile_start + time_to_burnout.
Starvation depends heavily on the Burn-out time setting. If the burn-out time is sufficiently long, starvation may not occur regardless of the scheduler. Therefore, the key metric is which scheduler is more resilient to starvation under tighter time constraints.
| Feature | FIFO Scheduling | EDF Scheduling |
|---|---|---|
| Burn-out Risk | Higher (Ignore urgency) | Lower (Prioritizes urgent tasks) |
| Execution Time | Shorter (Higher efficiency) | Longer (Overhead from waiting) |
| Fairness | Strict arrival order | Urgency-based redistribution |
-
EDF Scheduling:
EDF prioritizes coders nearing their burn-out limit. Even if another coder requested a resource earlier, priority is yielded to a more urgent task. This constant "priority yielding" ensures safety but increases the overall execution time (Total Turnaround Time) due to the accumulated waiting overhead of the deferred tasks. -
FIFO Scheduling:
FIFO strictly follows the request sequence. Since the priority never changes once a request is made, the execution flow is more direct, resulting in a shorter total time compared to EDF. However, because it remains blind to the remaining burn-out time of other coders, the statistical probability of a burn-out (Starvation) is significantly higher.
A Heap is an ideal data structure for priority-based processing, as it consistently maintains the highest or lowest priority element at the root node. By using an array-based implementation, we can also efficiently check for the existence of specific elements.
I implemented a custom Heap that stores data in Key-Value pairs, rather than just keys. This allows the structure to hold complex datasets (such as coder profiles) directly associated with their priority keys.
To maximize extensibility, the Heap accepts custom comparison functions for both keys and values during initialization. These functions follow the standard strcmp/memcmp return convention, enabling the Heap to handle both priority sorting and duplicate detection seamlessly.
By simply changing the value of the Key, the system can switch between different scheduling policies using the same Heap logic:
-
FIFO (First-In, First-Out): The key is set to the request arrival time. Since earlier requests always have an earlier timestamp, the Heap naturally maintains the FIFO order.
-
EDF (Earliest Deadline First): The key is set to the last compilation start time (the "urgency" factor). If a coder's last start time is earlier than those already in the Heap, they automatically gain higher priority.
This design allows complex scheduling behavior to be implemented simply by injecting different time-based values into the priority key.
USB dongles have a mandatory cooldown period after each compilation, during which they cannot be acquired.
The system records the timestamp when a compilation finishes. Any attempt to acquire the dongle is blocked until the current time surpasses the compilation_end_time + cooldown_duration.
A dedicated monitor thread is used to continuously check for burn-out conditions.
- Mechanism: The system records the start time of each coder's last compilation. If the elapsed time exceeds the burn-out threshold, the monitor thread sets a global termination flag, ensuring all threads exit immediately.
- Precision & Resolution: To meet the requirement of terminating all operations within 10ms of a burn-out, the monitor thread operates with a 1ms resolution. While this ensures high precision, it is admittedly less efficient in terms of CPU overhead.
Design Considerations:
A more efficient approach would involve refactoring the mutex-based waiting logic into a
pthread_cond_timedwaitsystem. However, this implementation was prioritized to ensure robustness under any burn-out threshold. If the burn-out time is configured to be shorter than the combined duration of compile + debug + refactor times, a purely event-driven model might fail to catch the burn-out at the exact moment. Since the system must handle arbitrary burn-out limits, the dedicated monitor thread was chosen to guarantee detection and prevent evaluation failure.
Although the fprintf function is technically thread-safe, failing to wrap it in a mutex can lead to corrupted logs.
- The Issue of Atomicity: While fprintf is thread-safe, it does not always guarantee atomic output for an entire string. Internally, the function may split a single string into multiple write operations.
- Interleaved Logs: Without a mutex, when multiple threads call fprintf simultaneously, their output fragments can become interleaved (mixed together). Using a mutex ensures that each log entry is written completely as a single, contiguous block, maintaining readability and data integrity.
The synchronization process follows these steps:
-
Status Verification
Check the Termination Flag and Compilation Counter under mutex protection.
If the Termination Flag is set or the Compilation Counter reaches the target, the coder thread terminates. -
Resource Request (Enqueueing)
Submit a request for the two required USB dongles under mutex protection.
Add the coder's information and a Priority Key to the Heap.- FIFO: The key is the arrival time of the request.
- EDF: The key is the start time of the last compilation (or program start time).
If the coder is already in the Heap, no further action is taken.
-
Priority Check
Check the current coder's priority for both USB dongles under mutex protection.
If the coder is not at the top of the priority queue, the thread sleeps for 1ms and restarts from Step 1. -
Resource Acquisition
Once priority is confirmed, the coder acquires both USB dongles (protected by mutex).
If either the first or second USB is in its cooldown period, the thread waits until the cooldown expires. -
Execution & Timestamping
Removes the current coder's information from the heap.
Begin the compilation process (simulated as a timed wait).- Start Time: Recorded at the beginning of compilation to calculate Burn-out (protected by mutex).
- End Time: Recorded upon completion to calculate the next Cooldown period (protected by mutex).
-
Processing
The Compilation and Refactoring stages are executed sequentially.
-
Iteration
The cycle repeats from Step 1.
To ensure data integrity in a multi-threaded environment, the following structures are protected by mutexes:
- USB Structure: Contains the Heap (priority queue) and Last Usage Timestamp. Since multiple coders access these concurrently, they are strictly protected by mutexes.
- Coder Structure: Contains the Status, Compilation Count, and Last Compilation Start Time. These are accessed by both the coder thread and the Monitor Thread, requiring mutex protection to prevent race conditions.
When I first evaluated the Philosophers project, I found it challenging to accurately monitor the real-time status of each coder. The Codexion project faced the exact same situation. However, the format of the output messages was already fixed as a mandatory requirement, which I could not modify. To work around this, I appended the additional information alongside the required output. This feature can be toggled via a command-line argument.
- Heap Visibility: The system now displays the current state of the priority heap within each USB structure.
- Coder Analytics: It tracks and outputs the start time for each state and the total compilation count for every coder.
This enhanced output significantly improves system visibility, making it much easier to monitor process flow and identify potential bottlenecks or issues during execution.
The left side of the pipe (|) delimiter shows the standard output format provided by the project, while the right side displays the enhanced output format.
$ ./codexion 4 800 200 200 200 10 5 edf 1
0 | 000000 : C#1( 0) START
0 | 000000 : C#2( 0) START
0 | 000000 : U#1 HEAP[1]
0 | 000000 : U#2 HEAP[1]
0 | 000000 : C#3( 0) START
0 | 000000 : U#3 HEAP[3]
0 | 000000 : U#4 HEAP[3]
0 3 has taken a dongle | 000000 : C#3( 0) USB
0 3 has taken a dongle | 000000 : C#3( 0) USB
0 3 is compiling | 000000 : C#3( 0) COMPILE+
0 1 has taken a dongle | 000000 : C#1( 0) USB
0 | 000000 : C#4( 0) START
0 1 has taken a dongle | 000000 : C#1( 0) USB
0 | 000000 : U#3 HEAP[2]
0 | 000000 : U#2 HEAP[1,2]
0 | 000000 : U#1 HEAP[1,4]
0 | 000000 : U#4 HEAP[4]
0 1 is compiling | 000000 : C#1( 0) COMPILE+
200 | 000200 : C#1( 1) COMPILE-
200 1 is debugging | 000200 : C#1( 1) DEBUG+
201 | 000201 : C#3( 1) COMPILE-
201 3 is debugging | 000201 : C#3( 1) DEBUG+
206 4 has taken a dongle | 000206 : C#4( 0) USB
206 4 has taken a dongle | 000206 : C#4( 0) USB
206 4 is compiling | 000206 : C#4( 0) COMPILE+
207 2 has taken a dongle | 000207 : C#2( 0) USB
207 2 has taken a dongle | 000207 : C#2( 0) USB
207 2 is compiling | 000207 : C#2( 0) COMPILE+
400 | 000400 : C#1( 1) DEBUG-
400 1 is refactoring | 000400 : C#1( 1) REFACT+
401 | 000401 : C#3( 1) DEBUG-
401 3 is refactoring | 000401 : C#3( 1) REFACT+
406 | 000406 : C#4( 1) COMPILE-
406 4 is debugging | 000406 : C#4( 1) DEBUG+
408 | 000408 : C#2( 1) COMPILE-
408 2 is debugging | 000408 : C#2( 1) DEBUG+
600 | 000600 : C#1( 1) REFACT-
C#1( 0) START
- C: Stands for Coder.
- #Number: The unique ID assigned to the coder.
- (Number): The current compilation count for that coder.
- Message: Indicates the current status or action (e.g., START, COMPILE, DEBUG, REFACT, BURNOUT, ALL DONE, END).
U#2 HEAP[1,2]
- U: Stands for USB Dongle.
- #Number: The unique ID assigned to the USB dongle.
- HEAP: Represents the internal state of the priority heap for that USB.
- [ , ]: The values inside the brackets represent the priorities of the nodes currently in the heap. Based on the heap structure, the first value has the highest priority.
There is no inherent priority order between the second and third elements based on their positions alone. However, since each USB dongle is shared by only two coders in this project, the maximum number of elements in the heap array is two.
Make
make
For Norminette
make norm
It calls norminette -R CheckForbiddenSourceHeader coders/*.c coders/*.h.
Run without arguments. (=Usage)
$ ./codexion
Usage: ./codexion <number_of_coders> <time_to_burnout> <time_to_compile> <time_to_debug> <time_to_refactor> <number_of_compiles_required> <dongle_cooldown> <scheduler> [use_print_state_ex]
Mandatory arguments:
number_of_coders Number of coders and available dongles.
time_to_burnout (ms) Max interval between compiles before a coder burns out.
time_to_compile (ms) Time taken to compile (requires 2 dongles).
time_to_debug (ms) Time spent in the debugging phase.
time_to_refactor (ms) Time spent in the refactoring phase.
number_of_compiles_required Total compiles per coder needed to finish simulation.
dongle_cooldown (ms) Cooldown period after a dongle is released.
scheduler Arbitration policy: [fifo | edf]
fifo: First In, First Out.
edf: Earliest Deadline First (last_compile + burnout).
Optional arguments:
use_print_state_ex Enable extended output. (0 or 1).
Example:
./codexion 4 390 90 100 100 10 10 fifo
./codexion 4 405 90 100 100 10 10 edf 1
- Dining philosophers problem: https://en.wikipedia.org/wiki/Dining_philosophers_problem
- Heap (data structure) https://en.wikipedia.org/wiki/Heap_(data_structure)