Codexion Learning Guide

Introduction

Codexion is a concurrency challenge that models a real-world resource contention problem. Multiple coders (threads) sit around a shared Quantum Compiler and compete for USB dongles (mutex-protected resources) to compile their code. The simulation must prevent burnout (deadline misses) while fairly arbitrating access to limited resources.

Don't worry if terms like "thread", "mutex", or "race condition" mean nothing to you yet — Chapters 1 to 8 build them up one at a time, starting from first principles, before Chapters 9 to 12 assemble them into the full Codexion project. Read them in order the first time through; each chapter leans on the previous one.

This guide will teach you every concept you need to build Codexion from scratch:

• POSIX Threads — Creating and managing concurrent execution flows
• Mutexes — Protecting shared resources from race conditions
• Condition Variables — Efficient waiting and signaling between threads
• The Dining Philosophers Problem — Classic synchronization puzzle
• Real-Time Scheduling — FIFO and Earliest Deadline First (EDF)
• Priority Queues — Heap-based scheduling implementation
• Time Management — Precise timing with gettimeofday

Figure 1: Coders arranged in a circle around the Quantum Compiler, each needing two adjacent dongles to compile.

The Problem Statement

• N coders sit in a circle around a Quantum Compiler
• There are N USB dongles on the table — one between each pair of adjacent coders
• Each coder needs both their left and right dongle to compile
• After compiling, a coder debugs, then refactors, then compiles again
• Each coder has a burnout deadline: if they don't compile within time_to_burnout ms of their last compile, they burn out
• Dongles have a cooldown: after being released, they cannot be taken again for dongle_cooldown ms
• Scheduling can be fifo (arrival order) or edf (earliest deadline first)
• A monitor thread detects burnout and stops the simulation

Walking Through One Coder's Life, Step by Step

Before diving into code, it helps to trace exactly what happens to a single coder, in plain English, from the moment the program starts:

1. The coder is created as a thread and immediately records the current time as their "last compile" timestamp — the burnout clock starts ticking right away, even before they've compiled anything.
2. They try to pick up their left and right dongle. If either is currently held by a neighbour, or is still in cooldown, they cannot proceed — they must wait (Chapters 2 and 4 explain exactly how that waiting should happen without wasting CPU).
3. Once they hold both dongles, they compile for time_to_compile ms. This is the only moment that resets their burnout clock and increments their compile counter.
4. They release both dongles (each now enters cooldown for dongle_cooldown ms) and move on to debug for time_to_debug ms, then refactor for time_to_refactor ms — these two phases don't need any dongle at all.
5. They loop back to step 2 and try to compile again, unless they've already reached compiles_required compiles, in which case their thread function returns and they're done.
6. In parallel, completely independently, a monitor thread is constantly comparing "now" against every coder's last-compile timestamp plus time_to_burnout. The instant any coder crosses that line without having compiled again, the monitor declares a burnout and the whole simulation stops.

Every later chapter is really about implementing one piece of this list correctly and safely when it runs N times in parallel instead of once.

Setup & Compilation

Since Codexion uses POSIX threads, you need to link against the pthread library:

cc -Wall -Wextra -Werror -pthread codexion.c -o codexion

The -pthread flag tells the compiler to link the POSIX thread library and set up thread-safe compilation. On macOS, you may need -lpthread instead.

Required Headers

#include <pthread.h>      /* Threads, mutexes, condition variables */
#include <sys/time.h>     /* gettimeofday */
#include <unistd.h>       /* usleep */
#include <stdio.h>        /* printf */
#include <stdlib.h>       /* malloc, free, atoi */
#include <string.h>       /* memset */

1POSIX Threads

A thread is an independent execution flow within a process. While a process has its own memory space, threads within the same process share that memory. This makes threads lightweight but requires synchronization to prevent conflicts.

Process vs Thread — The Foundation

Before threads make sense, it helps to be precise about what a process is. When you run ./codexion, the operating system creates a process: it gets its own private virtual memory space (its own view of RAM, isolated from every other program), its own file descriptors, its own program counter. Two processes cannot accidentally overwrite each other's variables — the OS enforces that isolation with page tables and hardware memory protection.

A thread lives inside a process. When you call pthread_create, you are not creating a new isolated program — you are creating a second (or third, or eighth) execution flow that runs concurrently but shares the same memory space as every other thread in that process: the same global variables, the same heap-allocated structures, the same file descriptors. This is precisely why threads are useful (no expensive copying or message-passing needed to share data) and precisely why they are dangerous (any thread can silently corrupt data another thread is using, with no OS protection stopping it).

What "Concurrent" Actually Means on Real Hardware

On a machine with a single CPU core, the operating system's scheduler rapidly switches between threads (a few milliseconds each), giving the illusion of simultaneous execution — this is concurrency. On a machine with multiple cores, threads can genuinely run at the exact same instant on different cores — this is parallelism. Codexion's correctness requirements (no lost updates, no missed deadlines) must hold in both cases: your synchronization code cannot assume "only one thread is truly running at a time", because on a multi-core machine that assumption is simply false.

Figure 2: The lifecycle of a POSIX thread from creation to termination.

The Return Type Puzzle: void *

Beginners are often confused by why a thread's start function must have the exact signature void *f(void *arg). The answer is that pthread_create is a single, generic C function that has no idea what data your thread needs or returns — it can only work with a signature that fits any use case. void * ("pointer to anything") is C's way of saying "I don't know or care about the type, you cast it back to whatever it really is inside the function." The argument you pass in comes back out unchanged in the corresponding pthread_join's second parameter if you called pthread_exit with a return value, letting a thread hand a result back to whoever joins it.

Creating a Thread

#include <pthread.h>

void *thread_function(void *arg)
{
    int id = *(int *)arg;
    printf("Thread %d is running\n", id);
    return (void *)0;
}

int main(void)
{
    pthread_t thread;
    int       id = 1;

    /* Create a new thread */
    pthread_create(&thread, NULL, thread_function, &id);

    /* Wait for the thread to finish */
    pthread_join(thread, NULL);

    return 0;
}

Key Functions

Passing Arguments to Threads

Never pass a local variable's address if it might change before the thread reads it. Use dynamically allocated memory or an array:

int main(void)
{
    pthread_t threads[5];
    int       ids[5];
    int       i;

    for (i = 0; i < 5; i++)
    {
        ids[i] = i + 1;
        pthread_create(&threads[i], NULL, thread_function, &ids[i]);
    }

    for (i = 0; i < 5; i++)
        pthread_join(threads[i], NULL);

    return 0;
}

What Happens If You Forget pthread_join?

If main() returns (or calls exit()) before joining every thread it created, the whole process — and every thread inside it — is terminated immediately, mid-work, with no cleanup. This is one of the most common beginner bugs: the program appears to "not print anything" or "stop halfway", when really the child threads simply never got the chance to finish because main raced ahead and ended the process first. In Codexion, main must join every coder thread and the monitor thread before returning, in the right order (see Chapter 11, Part F), or you will lose output non-deterministically — the bug will even seem to appear and disappear between runs, which is a hallmark of concurrency bugs in general.

Joinable vs Detached — Two Different Lifecycles

By default, a thread is joinable: its resources (like its exit status) stay alive after it finishes, until some other thread calls pthread_join on it — exactly like a zombie process waiting to be reaped by wait(). If nobody ever joins it, that memory leaks for the lifetime of the process. A detached thread (via pthread_detach) is the opposite: the system cleans it up automatically the moment it finishes, but as a trade-off you can never pthread_join it afterwards to retrieve a result or simply know it's done. Codexion uses joinable threads throughout, because the monitor and main function genuinely need to know when coders have finished.

2Mutexes

A mutex (mutual exclusion lock) ensures that only one thread can access a critical section at a time. Think of it as a lock on a door: whoever holds the key can enter, everyone else waits outside.

What Exactly Is a "Critical Section"?

A critical section is any piece of code that reads or writes shared state (a global variable, a struct on the heap, a shared array) in a way that would break if two threads executed it at the exact same time. Not all code needs protection — a thread doing purely local, private computation (like sleeping for time_to_compile ms, which touches no shared memory) needs no lock at all. The skill of concurrent programming is largely about correctly identifying which lines are critical sections and locking exactly those — no more (or you lose parallelism for no reason), no less (or you get bugs).

In Codexion, examples of critical sections include: incrementing a coder's compile_count, changing a dongle's holder_id, checking or setting sim_over, and printing a log line (so two coders' output lines don't interleave character-by-character). Each of these needs its own mutex, or a shared one, protecting it.

Figure 3: Thread 1 holds the mutex and accesses the shared resource. Threads 2 and 3 wait.

Basic Mutex Operations

pthread_mutex_t lock;

/* Initialize */
pthread_mutex_init(&lock, NULL);

/* Lock (blocks if already locked) */
pthread_mutex_lock(&lock);

/* Critical section — only one thread here at a time */
shared_counter++;

/* Unlock */
pthread_mutex_unlock(&lock);

/* Destroy when done */
pthread_mutex_destroy(&lock);

Why Mutexes Matter: The Lost Update

Without a mutex, two threads incrementing the same variable can lose updates:

/* Thread A reads counter = 5 */
/* Thread B reads counter = 5 (before A writes) */
/* Thread A writes counter = 6 */
/* Thread B writes counter = 6 (overwrites A's update!) */
/* Expected: 7, Actual: 6 — LOST UPDATE */

Blocking Is the Whole Point

It's worth pausing on what "pthread_mutex_lock blocks if already locked" really means in practice: the calling thread is put to sleep by the operating system — it consumes essentially zero CPU while waiting — and is automatically woken up by the kernel the moment the mutex becomes free. You do not need (and should never write) a loop like while (locked) {} around a mutex; that would be a busy-wait that burns 100% of a CPU core doing nothing useful. The mutex primitive already does the efficient sleep-and-wake for you.

Granularity: One Big Lock vs Many Small Locks

A common beginner instinct is to protect an entire program with a single global mutex, locked at the very start of every thread's work and unlocked at the very end. This is correct (no race condition can happen) but destroys the whole point of using threads: if only one coder can ever be "inside the lock" at a time, your 8 coders run one after another, not concurrently, and you gain nothing over a single-threaded program. Codexion is specifically designed to force you to think about granularity: each dongle typically gets its own mutex, so a coder waiting for dongle 3 does not block a completely unrelated coder who only needs dongles 5 and 6. Locking too coarsely kills performance; locking too finely (or inconsistently) reintroduces race conditions and deadlocks. There is no formula — it's a design decision you justify by reasoning about which operations truly must be mutually exclusive.

Try-Lock (Non-Blocking)

pthread_mutex_trylock attempts to acquire the lock without blocking. It returns 0 on success, EBUSY if already locked:

if (pthread_mutex_trylock(&lock) == 0)
{
    /* Got the lock */
    pthread_mutex_unlock(&lock);
}
else
{
    /* Lock was busy, do something else */
}

Mutex Attributes (Error Checking)

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ERRORCHECK);
pthread_mutex_init(&lock, &attr);
pthread_mutexattr_destroy(&attr);

3Condition Variables

A condition variable allows threads to wait for a condition to become true without consuming CPU. Unlike a mutex which only provides mutual exclusion, a condition variable provides synchronization — threads can sleep until signaled to wake up.

Why Not Just Spin?

/* BAD: Spin-waiting wastes 100% CPU */
while (!ready)
    ; /* CPU burns waiting */

/* GOOD: Condition variable puts thread to sleep */
pthread_mutex_lock(&lock);
while (!ready)
    pthread_cond_wait(&cond, &lock);  /* Thread sleeps, releases lock */
pthread_mutex_unlock(&lock);

The Three Condition Variable Operations

Producer-Consumer Example

This classic pattern shows how condition variables coordinate work between threads:

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  cond = PTHREAD_COND_INITIALIZER;
int             data_ready = 0;

void *consumer(void *arg)
{
    (void)arg;

    pthread_mutex_lock(&lock);
    while (!data_ready)
    {
        /* Atomically: unlock mutex + sleep on cond + relock on wakeup */
        pthread_cond_wait(&cond, &lock);
    }
    /* Now we hold the lock and data_ready is true */
    printf("Consumer: got data!\n");
    data_ready = 0;
    pthread_mutex_unlock(&lock);
    return NULL;
}

void *producer(void *arg)
{
    (void)arg;

    sleep(1);  /* Simulate work */

    pthread_mutex_lock(&lock);
    data_ready = 1;
    pthread_cond_signal(&cond);  /* Wake up consumer */
    pthread_mutex_unlock(&lock);
    return NULL;
}

Why while and Not if?

Always use while with pthread_cond_wait. This protects against spurious wakeups — rare events where a thread wakes up without being signaled. The while loop re-checks the condition:

/* WRONG: If spurious wakeup happens, condition may still be false */
if (!ready)
    pthread_cond_wait(&cond, &lock);

/* CORRECT: Re-check condition after every wakeup */
while (!ready)
    pthread_cond_wait(&cond, &lock);

Timed Wait

pthread_cond_timedwait is essential for Codexion's burnout detection. It waits but returns ETIMEDOUT if the deadline passes:

struct timespec deadline;
clock_gettime(CLOCK_REALTIME, &deadline);
deadline.tv_sec += 1;  /* Wait up to 1 second */

int rc = pthread_cond_timedwait(&cond, &lock, &deadline);
if (rc == ETIMEDOUT)
    printf("Timeout!\n");

The "Lost Wakeup" Bug — Why the Mutex Is Mandatory

It might seem redundant that pthread_cond_wait forces you to hold a mutex. Here's exactly the bug that requirement prevents. Imagine, incorrectly, that checking the condition and waiting on it were two separate, unprotected steps:

/* BROKEN: condition check and wait are not atomic */
if (!ready)              /* (1) consumer checks: not ready yet */
{
    /* --- producer runs right here: sets ready=1, signals --- */
    /*     but NOBODY is waiting on the cond var yet!        */
    pthread_cond_wait(&cond, &lock); /* (2) consumer waits — forever */
}

Between steps (1) and (2), the producer thread could run to completion, set the flag, and signal — but since the consumer wasn't registered as a waiter yet, that signal is lost forever, and the consumer sleeps forever waiting for a wakeup that already happened. This is called a lost wakeup, and it's exactly why pthread_cond_wait takes the mutex as a parameter: it guarantees that "checking the condition" and "starting to wait" happen as one atomic, uninterruptible step relative to the thread doing the signalling (which must also hold the same mutex while it changes the shared condition and signals). This is the single most important invariant to internalize about condition variables.

4The Dining Philosophers Problem

Codexion is a variation of the Dining Philosophers — a classic concurrency problem where N philosophers sit at a round table with N forks. Each philosopher needs two forks to eat. The challenge: prevent deadlock and starvation.

Two Different Failure Modes — Don't Confuse Them

Beginners often lump "deadlock" and "starvation" together, but they are distinct failures with distinct causes, and Codexion explicitly tests for both:

A scheduler can fix one without fixing the other: naive FIFO prevents deadlock (nobody holds a dongle forever without eventually being served) but does not guarantee that the coder closest to burnout gets served first — which is exactly the gap that EDF scheduling (Chapter 6) closes.

Figure 4: Deadlock — every coder holds one dongle and waits for another.

The Deadlock Scenario

If every coder picks up their left dongle simultaneously, then tries to pick up their right dongle, everyone waits forever:

/* DANGEROUS: Can cause deadlock */
pthread_mutex_lock(&left_dongle);   /* Everyone grabs left */
pthread_mutex_lock(&right_dongle);  /* Everyone waits for right -> DEADLOCK */
/* Compile... */
pthread_mutex_unlock(&right_dongle);
pthread_mutex_unlock(&left_dongle);

Why Deadlock Happens: The Four Coffman Conditions

Deadlock is not random bad luck — it is a precise, well-understood phenomenon that can only occur if all four of the following conditions hold simultaneously. Understanding them tells you exactly which lever to pull to prevent it:

1. Mutual exclusion — a resource (a dongle) can only be held by one thread at a time.
2. Hold and wait — a thread holding one resource (its left dongle) is waiting to acquire another (its right dongle) without releasing what it already has.
3. No preemption — a resource cannot be forcibly taken away from the thread holding it; it can only be released voluntarily.
4. Circular wait — there exists a cycle of threads where each is waiting for a resource held by the next one in the cycle (coder 1 waits for coder 2's dongle, who waits for coder 3's, ..., who waits for coder 1's).

Break any one of these four conditions and deadlock becomes structurally impossible, no matter how unlucky your thread scheduling is. Each solution below breaks a different one.

Solution 1: Asymmetric Lock Ordering

This solution breaks circular wait: if every coder agrees on a global ordering for picking up dongles (instead of everyone symmetrically starting with "my left one"), the cycle in condition 4 can never form — there will always be at least one coder who picked up the lower-numbered dongle first and can therefore always get the second one.

Force an ordering: odd-numbered coders pick left first, even-numbered pick right first. This breaks the circular wait condition:

if (coder_id % 2 == 0)
{
    pthread_mutex_lock(&right_dongle);
    pthread_mutex_lock(&left_dongle);
}
else
{
    pthread_mutex_lock(&left_dongle);
    pthread_mutex_lock(&right_dongle);
}

Solution 2: Try-Lock with Backoff

Pick up the first dongle, then try the second. If unavailable, release the first and retry:

while (1)
{
    pthread_mutex_lock(&left_dongle);
    if (pthread_mutex_trylock(&right_dongle) == 0)
        break;  /* Got both! */
    pthread_mutex_unlock(&left_dongle);  /* Release and retry */
    usleep(100);  /* Small delay to prevent livelock */
}

Solution 3: Condition Variables with Scheduler

This is the Codexion approach. Instead of blindly grabbing dongles, coders request access through a centralized scheduler that grants permission based on FIFO or EDF ordering:

/* Coder requests both dongles from scheduler */
request_dongles(coder_id);
/* Scheduler grants access, coder compiles */
compile();
/* Release dongles back to scheduler */
release_dongles(coder_id);

5Time in C

Precise timing is critical for Codexion. You need to measure elapsed time in milliseconds, compute deadlines, and implement cooldowns.

Why Milliseconds, and Why long long?

Codexion's arguments (time_to_burnout, time_to_compile, etc.) are given in milliseconds because that's precise enough for human-observable timing (sub-millisecond precision would be pointless — thread scheduling jitter alone is often a millisecond or more) while staying easy to reason about mentally, unlike raw microseconds. The timestamps themselves are stored as long long (a 64-bit integer, at least 8 bytes) rather than a plain int (usually 4 bytes, max ~2.1 billion) because gettimeofday returns seconds since 1 January 1970 — that value alone is already over 1.7 billion and counting, and once you multiply it by 1000 to get milliseconds it would silently overflow a 32-bit int and wrap around to a negative number, corrupting every deadline comparison in your program. This is a real, common beginner bug — always use a 64-bit type for absolute millisecond timestamps.

gettimeofday

Returns the current time with microsecond precision:

#include <sys/time.h>

long long get_time_ms(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);
    return ((long long)tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}

usleep

Suspends the calling thread for a specified number of microseconds:

#include <unistd.h>

usleep(200000);  /* Sleep for 200 milliseconds */
usleep(5000);     /* Sleep for 5 milliseconds */

Computing Deadlines

long long last_compile_start = get_time_ms();
long long time_to_burnout = 800;  /* ms */

/* Check if burned out */
if (get_time_ms() - last_compile_start > time_to_burnout)
    printf("BURNOUT!\n");

Timed Condition Wait with Absolute Time

struct timespec ms_to_timespec(long long ms)
{
    struct timespec ts;
    struct timeval  tv;

    gettimeofday(&tv, NULL);
    ts.tv_sec = tv.tv_sec + (ms / 1000);
    ts.tv_nsec = (tv.tv_usec * 1000) + ((ms % 1000) * 1000000);
    if (ts.tv_nsec >= 1000000000)
    {
        ts.tv_sec++;
        ts.tv_nsec -= 1000000000;
    }
    return ts;
}

6Scheduling: FIFO vs EDF

When multiple coders request the same dongle, the scheduler decides who gets it first. Codexion implements two scheduling policies.

Figure 5: FIFO serves requests in arrival order. EDF reorders by urgency (earliest deadline).

FIFO (First In, First Out)

Requests are queued in arrival order. Simple, fair, but doesn't account for urgency:

/* Simple linked list queue */
typedef struct s_request
{
    int                 coder_id;
    struct s_request   *next;
} t_request;

typedef struct
{
    t_request   *head;
    t_request   *tail;
} t_fifo_queue;

void fifo_enqueue(t_fifo_queue *q, int coder_id)
{
    t_request *req = malloc(sizeof(t_request));
    req->coder_id = coder_id;
    req->next = NULL;
    if (q->tail)
        q->tail->next = req;
    else
        q->head = req;
    q->tail = req;
}

int fifo_dequeue(t_fifo_queue *q)
{
    t_request *req;
    int         id;

    if (!q->head)
        return -1;
    req = q->head;
    id = req->coder_id;
    q->head = req->next;
    if (!q->head)
        q->tail = NULL;
    free(req);
    return id;
}

EDF (Earliest Deadline First)

Each coder has a burnout deadline computed as last_compile_start + time_to_burnout. EDF serves the coder whose deadline is closest:

/* Priority = deadline (lower = higher priority) */
typedef struct s_request
{
    int                 coder_id;
    long long          deadline;  /* burnout deadline in ms */
} t_request;

/* Min-heap: parent has earlier deadline than children */
typedef struct
{
    t_request   *arr;
    int          size;
    int          capacity;
} t_edf_queue;

A Worked Example: Watch FIFO Fail Where EDF Succeeds

Suppose two coders both become ready to compile at the same instant (t = 0), but only one dongle pair is free at a time so they can't be served simultaneously. Say time_to_burnout = 100ms for both, but coder A last compiled at t = -80 (so their deadline is t = 20) while coder B last compiled at t = -10 (deadline t = 90). Coder A arrived in the queue microseconds after coder B purely by chance.

This is the entire reason Codexion asks you to implement two schedulers: it's not a stylistic choice, it's a demonstration that arrival order and urgency are different things, and a scheduler that only knows about arrival order can let an urgent thread starve even while being perfectly "fair" by its own definition.

7Priority Queue / Min-Heap in C

C89 has no standard priority queue. You must implement a binary min-heap yourself. A heap is a complete binary tree where each parent is smaller than its children.

Why a Plain Array, Not a Pointer-Based Tree?

It looks strange the first time: a "binary tree" implemented as a flat t_heap_node *nodes array with no left/right pointers anywhere. This works because a complete binary tree (every level full except possibly the last, filled left-to-right — which a heap always is by construction) has a predictable, gap-free shape, so its nodes can be numbered 0, 1, 2, 3... in level order and stored at exactly those array indices. The formulas parent = (i-1)/2, left = 2*i+1, right = 2*i+2 then compute tree relationships from pure arithmetic instead of following pointers. The payoff: no malloc per node, better CPU cache locality (neighbouring array elements are physically close in memory, unlike scattered heap-allocated nodes), and dramatically simpler code — at the cost of needing to know (or grow) a capacity up front.

Trace: Inserting Deadlines 50, 20, 80, 10

Walking through heap_insert by hand builds real intuition. Starting from an empty heap, insert coders with deadlines 50, then 20, then 80, then 10 (lower deadline = higher priority = should end up closer to the root):

• Insert 50 → array [50]. Only element, nothing to compare — it's the root.
• Insert 20 → appended at index 1: [50, 20]. Its parent is index 0 (value 50). Since 20 < 50, swap → [20, 50].
• Insert 80 → appended at index 2: [20, 50, 80]. Its parent is index 0 (value 20). Since 80 > 20, no swap needed — heap property already holds.
• Insert 10 → appended at index 3: [20, 50, 80, 10]. Its parent is index 1 (value 50, computed as (3-1)/2 = 1). Since 10 < 50, swap → [20, 10, 80, 50]. Continue up: 10's new parent is index 0 (value 20, (1-1)/2 = 0). Since 10 < 20, swap again → [10, 20, 80, 50]. Now at the root, stop.

Final array [10, 20, 80, 50] — extracting the min always returns 10 first, exactly the coder closest to burnout, in O(log n) work per operation rather than an O(n) linear scan through every waiting coder.

Heap Structure

typedef struct s_heap_node
{
    int         coder_id;
    long long  deadline;  /* priority: lower = higher */
} t_heap_node;

typedef struct
{
    t_heap_node *nodes;
    int          size;
    int          capacity;
} t_heap;

t_heap *heap_create(int capacity)
{
    t_heap *h = malloc(sizeof(t_heap));
    h->nodes = malloc(sizeof(t_heap_node) * capacity);
    h->size = 0;
    h->capacity = capacity;
    return h;
}

Heapify Up (Insertion)

After adding a node at the end, swap it with its parent until the heap property is restored:

void heap_insert(t_heap *h, int coder_id, long long deadline)
{
    int i;
    t_heap_node tmp;

    /* Add at the end */
    i = h->size;
    h->nodes[i].coder_id = coder_id;
    h->nodes[i].deadline = deadline;
    h->size++;

    /* Heapify up: swap with parent while smaller */
    while (i > 0)
    {
        int parent = (i - 1) / 2;
        if (h->nodes[parent].deadline <= h->nodes[i].deadline)
            break;
        /* Swap */
        tmp = h->nodes[parent];
        h->nodes[parent] = h->nodes[i];
        h->nodes[i] = tmp;
        i = parent;
    }
}

Heapify Down (Extraction)

Replace the root with the last element, then swap with the smaller child until the heap property is restored:

t_heap_node heap_extract_min(t_heap *h)
{
    t_heap_node min;
    t_heap_node tmp;
    int         i;
    int         left;
    int         right;
    int         smallest;

    min = h->nodes[0];
    h->size--;
    h->nodes[0] = h->nodes[h->size];

    /* Heapify down */
    i = 0;
    while (1)
    {
        left = 2 * i + 1;
        right = 2 * i + 2;
        smallest = i;

        if (left < h->size && h->nodes[left].deadline < h->nodes[smallest].deadline)
            smallest = left;
        if (right < h->size && h->nodes[right].deadline < h->nodes[smallest].deadline)
            smallest = right;

        if (smallest == i)
            break;

        tmp = h->nodes[i];
        h->nodes[i] = h->nodes[smallest];
        h->nodes[smallest] = tmp;
        i = smallest;
    }
    return min;
}

Complexity

8The Monitor Pattern

A monitor is a design pattern where a dedicated thread continuously checks a condition and takes action when it becomes true. In Codexion, the monitor detects burnout.

Polling vs Event-Driven — A Deliberate Trade-off

Notice that the monitor thread below uses usleep(1000) in a loop — this is polling: repeatedly waking up and checking "has anything changed?" rather than being passively woken up only when something actually happens (which would be the event-driven style you saw with condition variables in Chapter 3). This might look like a step backwards after just learning to avoid busy-waiting, but it's the right tool here for a specific reason: burnout is defined by the absence of an event within a time window ("nobody compiled for this coder in the last time_to_burnout ms"), not by the occurrence of one. A condition variable can be signalled when something happens, but there's no clean way to signal "nothing happened for a while" — so the monitor has no choice but to periodically wake up and check the clock itself. The 1ms polling interval is a deliberate compromise: frequent enough to catch a burnout within the guide's 10ms precision requirement, infrequent enough to barely register on CPU usage (sleeping 999 microseconds out of every 1000).

Figure 6: The monitor thread continuously checks all coders' deadlines against the current time.

Monitor Implementation

typedef struct s_coder
{
    int          id;
    long long   last_compile_start;
    int          compile_count;
    int          burned_out;
} t_coder;

typedef struct s_sim
{
    t_coder             *coders;
    int                  num_coders;
    long long           time_to_burnout;
    int                  sim_over;
    pthread_mutex_t      sim_lock;
} t_sim;

void *monitor_thread(void *arg)
{
    t_sim   *sim = (t_sim *)arg;
    int      i;
    long long now;
    long long elapsed;

    while (1)
    {
        usleep(1000);  /* Check every 1ms */

        pthread_mutex_lock(&sim->sim_lock);
        if (sim->sim_over)
        {
            pthread_mutex_unlock(&sim->sim_lock);
            break;
        }

        now = get_time_ms();
        for (i = 0; i < sim->num_coders; i++)
        {
            if (sim->coders[i].burned_out)
                continue;

            elapsed = now - sim->coders[i].last_compile_start;
            if (elapsed > sim->time_to_burnout)
            {
                sim->coders[i].burned_out = 1;
                sim->sim_over = 1;
                printf("%lld %d burned out\n", now, sim->coders[i].id);
                break;
            }
        }
        pthread_mutex_unlock(&sim->sim_lock);
    }
    return NULL;
}

9Codexion Architecture

Now we combine everything into the Codexion simulation. Here is the high-level architecture:

Figure 7: Each coder cycles through Compile -> Debug -> Refactor repeatedly.

Component Overview

1. Coder Threads — One per coder. Each loops: request dongles -> compile -> debug -> refactor.
2. Dongles — N mutex-protected resources. Each has a state (available/held/cooldown) and a cooldown timer.
3. Scheduler — Centralized queue (FIFO or EDF heap) that grants dongle access to waiting coders.
4. Monitor Thread — Detects burnout by checking if any coder exceeded time_to_burnout since last compile.
5. Logger — Mutex-protected output to prevent interleaved messages.

State Machine per Coder

typedef enum e_state
{
    THINKING,    /* Waiting for dongles */
    COMPILING,   /* Has both dongles */
    DEBUGGING,   /* Just released dongles */
    REFACTORING  /* After debugging */
} t_state;

typedef struct s_coder
{
    int             id;
    pthread_t       thread;
    t_state         state;
    long long       last_compile_start;
    int             compile_count;
    int             burned_out;
} t_coder;

Dongle Structure

typedef struct s_dongle
{
    pthread_mutex_t  mutex;
    int              holder_id;     /* -1 if available */
    long long       released_at;   /* timestamp for cooldown */
    int              in_cooldown;
} t_dongle;

Simulation Parameters

10Data Structures

Complete Simulation Structure

#define MAX_CODERS 200

typedef struct s_sim
{
    /* Config */
    int             num_coders;
    long long       time_to_burnout;
    long long       time_to_compile;
    long long       time_to_debug;
    long long       time_to_refactor;
    int             compiles_required;
    long long       dongle_cooldown;
    int             use_edf;          /* 0 = fifo, 1 = edf */

    /* State */
    t_coder         coders[MAX_CODERS];
    t_dongle        dongles[MAX_CODERS];
    int             sim_over;
    int             all_done;

    /* Scheduler */
    pthread_mutex_t  sched_lock;
    pthread_cond_t   sched_cond;
    t_heap          *edf_queue;       /* NULL if FIFO */
    t_fifo_queue    fifo_queue;

    /* Logging */
    pthread_mutex_t  log_lock;

    /* Monitor */
    pthread_t       monitor;
} t_sim;

Requesting Dongles (Centralized)

Instead of grabbing dongles directly, coders request them through the scheduler. The scheduler checks availability and either grants immediately or queues the request:

void request_dongles(t_sim *sim, int coder_id)
{
    int         left;
    int         right;
    long long   now;
    long long   deadline;

    left = coder_id;
    right = (coder_id + 1) % sim->num_coders;

    pthread_mutex_lock(&sim->sched_lock);

    /* Wait until both dongles are available AND not in cooldown */
    while (!sim->sim_over)
    {
        now = get_time_ms();

        /* Check cooldown */
        if (sim->dongles[left].in_cooldown)
        {
            if (now - sim->dongles[left].released_at >= sim->dongle_cooldown)
                sim->dongles[left].in_cooldown = 0;
        }
        if (sim->dongles[right].in_cooldown)
        {
            if (now - sim->dongles[right].released_at >= sim->dongle_cooldown)
                sim->dongles[right].in_cooldown = 0;
        }

        /* Check availability */
        if (!sim->dongles[left].in_cooldown &&
            !sim->dongles[right].in_cooldown &&
            sim->dongles[left].holder_id == -1 &&
            sim->dongles[right].holder_id == -1)
        {
            /* Grant access */
            sim->dongles[left].holder_id = coder_id;
            sim->dongles[right].holder_id = coder_id;
            log_message(sim, now, coder_id, "has taken a dongle");
            log_message(sim, now, coder_id, "has taken a dongle");
            break;
        }

        /* Not available: queue and wait */
        deadline = sim->coders[coder_id].last_compile_start + sim->time_to_burnout;
        if (sim->use_edf)
            heap_insert(sim->edf_queue, coder_id, deadline);
        else
            fifo_enqueue(&sim->fifo_queue, coder_id);

        pthread_cond_wait(&sim->sched_cond, &sim->sched_lock);

        /* Woken up — remove from queue if still there */
        /* (simplified: in real code, check if we're the head) */
    }

    pthread_mutex_unlock(&sim->sched_lock);
}

Releasing Dongles

void release_dongles(t_sim *sim, int coder_id)
{
    int         left;
    int         right;
    long long   now;

    left = coder_id;
    right = (coder_id + 1) % sim->num_coders;
    now = get_time_ms();

    pthread_mutex_lock(&sim->sched_lock);

    sim->dongles[left].holder_id = -1;
    sim->dongles[left].released_at = now;
    sim->dongles[left].in_cooldown = 1;

    sim->dongles[right].holder_id = -1;
    sim->dongles[right].released_at = now;
    sim->dongles[right].in_cooldown = 1;

    /* Wake up waiting coders to check availability */
    pthread_cond_broadcast(&sim->sched_cond);

    pthread_mutex_unlock(&sim->sched_lock);
}

11Full Implementation

Here is the complete structure of a working Codexion implementation. This is organized into logical sections you can copy, study, and adapt.

Part A: Headers and Utility Functions

#include <pthread.h>
#include <sys/time.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long get_time_ms(void)
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return ((long long)tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}

void precise_sleep(long long ms)
{
    long long start;

    start = get_time_ms();
    while (get_time_ms() - start < ms)
        usleep(100);
}

Part B: Logger (Mutex-Protected Output)

void log_message(t_sim *sim, long long ts, int coder_id, char *msg)
{
    pthread_mutex_lock(&sim->log_lock);
    printf("%lld %d %s\n", ts, coder_id, msg);
    pthread_mutex_unlock(&sim->log_lock);
}

Part C: Coder Thread Routine

void *coder_routine(void *arg)
{
    t_sim   *sim;
    int      id;
    long long ts;

    sim = (t_sim *)arg;
    id = sim->coder_id;  /* passed via thread arg */

    while (1)
    {
        /* Check if simulation ended */
        pthread_mutex_lock(&sim->sched_lock);
        if (sim->sim_over || sim->coders[id].burned_out)
        {
            pthread_mutex_unlock(&sim->sched_lock);
            break;
        }
        pthread_mutex_unlock(&sim->sched_lock);

        /* Request dongles (blocks until available) */
        request_dongles(sim, id);

        /* Compiling */
        ts = get_time_ms();
        sim->coders[id].last_compile_start = ts;
        log_message(sim, ts, id, "is compiling");
        precise_sleep(sim->time_to_compile);
        sim->coders[id].compile_count++;

        /* Release dongles */
        release_dongles(sim, id);

        /* Check if done */
        pthread_mutex_lock(&sim->sched_lock);
        if (sim->coders[id].compile_count >= sim->compiles_required)
        {
            sim->all_done = check_all_done(sim);
            pthread_mutex_unlock(&sim->sched_lock);
            break;
        }
        pthread_mutex_unlock(&sim->sched_lock);

        /* Debugging */
        ts = get_time_ms();
        log_message(sim, ts, id, "is debugging");
        precise_sleep(sim->time_to_debug);

        /* Refactoring */
        ts = get_time_ms();
        log_message(sim, ts, id, "is refactoring");
        precise_sleep(sim->time_to_refactor);
    }
    return NULL;
}

Part D: Argument Parsing

int parse_args(int argc, char **argv, t_sim *sim)
{
    if (argc != 9)
        return 1;

    sim->num_coders = atoi(argv[1]);
    sim->time_to_burnout = atoi(argv[2]);
    sim->time_to_compile = atoi(argv[3]);
    sim->time_to_debug = atoi(argv[4]);
    sim->time_to_refactor = atoi(argv[5]);
    sim->compiles_required = atoi(argv[6]);
    sim->dongle_cooldown = atoi(argv[7]);

    if (!strcmp(argv[8], "fifo"))
        sim->use_edf = 0;
    else if (!strcmp(argv[8], "edf"))
        sim->use_edf = 1;
    else
        return 1;

    /* Validate */
    if (sim->num_coders <= 0 || sim->time_to_burnout <= 0)
        return 1;

    return 0;
}

Part E: Initialization

void init_simulation(t_sim *sim)
{
    int i;
    long long now;

    now = get_time_ms();
    sim->sim_over = 0;
    sim->all_done = 0;

    pthread_mutex_init(&sim->sched_lock, NULL);
    pthread_cond_init(&sim->sched_cond, NULL);
    pthread_mutex_init(&sim->log_lock, NULL);

    for (i = 0; i < sim->num_coders; i++)
    {
        sim->coders[i].id = i + 1;
        sim->coders[i].state = THINKING;
        sim->coders[i].last_compile_start = now;
        sim->coders[i].compile_count = 0;
        sim->coders[i].burned_out = 0;

        sim->dongles[i].holder_id = -1;
        sim->dongles[i].in_cooldown = 0;
        pthread_mutex_init(&sim->dongles[i].mutex, NULL);
    }

    if (sim->use_edf)
        sim->edf_queue = heap_create(sim->num_coders * 2);
    else
        fifo_init(&sim->fifo_queue);
}

Part F: Main Function

int main(int argc, char **argv)
{
    t_sim   sim;
    int     i;

    memset(&sim, 0, sizeof(sim));
    if (parse_args(argc, argv, &sim))
    {
        fprintf(stderr, "Usage: ./codexion n burn compile debug refactor required cooldown {fifo|edf}\n");
        return 1;
    }

    init_simulation(&sim);

    /* Create monitor thread */
    pthread_create(&sim.monitor, NULL, monitor_thread, &sim);

    /* Create coder threads */
    for (i = 0; i < sim.num_coders; i++)
        pthread_create(&sim.coders[i].thread, NULL, coder_routine, &sim);

    /* Wait for all coders */
    for (i = 0; i < sim.num_coders; i++)
        pthread_join(sim.coders[i].thread, NULL);

    /* Signal monitor to stop and wait */
    pthread_mutex_lock(&sim.sched_lock);
    sim.sim_over = 1;
    pthread_mutex_unlock(&sim.sched_lock);
    pthread_join(sim.monitor, NULL);

    /* Cleanup */
    cleanup_simulation(&sim);
    return 0;
}

12Interactive Simulator

This simulator is wired to the exact same arguments your codexion binary takes on the command line (see Chapter 11, Part D — parse_args): n burn compile debug refactor required cooldown {fifo|edf}. Every field below maps 1-to-1 to an argv[] slot, and the simulation loop underneath genuinely uses those numbers to drive timing, deadlines and the win/burnout condition — it isn't just cosmetic.

./codexion 4 1200 400 300 300 3 100 fifo

Quick API Reference

POSIX Threads

Mutexes

Condition Variables

Time Functions

Common Errors

Resources

• Linux pthreads man page
• POSIX.1-2017 pthread.h specification
• OSTEP: Threads and Locks (free book chapter)
• OSTEP: Condition Variables (free book chapter)
• Dining Philosophers Problem - Wikipedia
• Earliest Deadline First - Wikipedia