Operating Systems & Concurrency

Process Anatomy & the PCB

A process is an instance of an executing program with its own virtual address space, open-file table, credentials, and at least one thread of control. The kernel tracks each process via a Process Control Block (PCB) — in Linux this is struct task_struct (~1.7 KB per task on x86_64, 2024 vintage).

Virtual address-space layout (x86_64 Linux, typical)

PCB fields — what the kernel tracks per process

Process states — the five-state machine

Threads & the TCB

A thread is an independently schedulable flow of execution that shares its address space, file table, and signal handlers with sibling threads. On Linux, threads are just task_structs created with clone(CLONE_VM|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|…) — the PCB is the TCB. Shared resources are stored once in mm_struct / files_struct and pointed to by every thread.

Per-thread (TCB) vs per-process state

User vs kernel threads

• 1:1 (kernel threads) — every userspace thread maps to one kernel task_struct. Linux NPTL, Windows threads, modern macOS all do this. Blocking a thread only blocks that thread; multiple threads can run on multiple cores simultaneously.
• N:1 (green threads) — many user threads multiplexed onto one kernel thread. A blocking syscall freezes every sibling. Historic early Java (Solaris green threads, GNU Pth). Simple, but no multicore.
• M:N (hybrid) — user scheduler maps M user threads onto N kernel threads. Go's goroutines, Rust's (former) greenlets, Erlang BEAM. Cheap context switches in userspace; requires a runtime to trap blocking syscalls.

fork / exec / wait

POSIX fork() creates a duplicate of the calling process. The child gets a new PID, a copy of the parent's memory (copy-on-write), a duplicate FD table, and picks up execution on the instruction after fork returns.

/* fork_demo.c — classic fork/exec/wait pipeline */
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    pid_t pid = fork();
    if (pid < 0) { perror("fork"); return 1; }

    if (pid == 0) {
        /* child: replace our image with /bin/ls */
        char *argv[] = { "ls", "-la", NULL };
        execvp(argv[0], argv);
        perror("execvp");      /* only reached if exec fails */
        _exit(127);
    }

    /* parent: wait for the child and inspect its exit status */
    int status;
    waitpid(pid, &status, 0);
    if (WIFEXITED(status))
        printf("child exited with %d\n", WEXITSTATUS(status));
    return 0;
}

What actually happens on fork

1. Kernel copies task_struct — trivial bytes.
2. Clones mm_struct by copying page tables, not physical pages. All writable pages are marked read-only. This is copy-on-write (COW).
3. Duplicates the FD table (refcount++ on each file*).
4. Copies signal dispositions (but not pending signals).
5. Sets the child's return value to 0 and the parent's to the child PID.
6. Schedules the child; the first page written triggers a fault, the kernel copies that page only.

fork cost breakdown (x86_64 Linux, 2024)

Context Switch Cost

A context switch is the kernel replacing the executing thread's saved state with another thread's. The direct cost is saving and restoring registers. The indirect cost — cache and TLB pollution — often dwarfs it.

Direct cost breakdown

Indirect cost: what you pay after the switch

• TLB flush: cross-address-space switch on non-PCID CPUs flushes the TLB entirely; the first few thousand memory references miss. PCID (CR4.PCIDE) tags entries by ASID so the cost is near-zero.
• Cache pollution: T2 evicts T1's working set from L1/L2. When T1 resumes, cold misses re-fetch from L3 or RAM. Measured indirect cost for unrelated workloads: 10–100 µs.
• Branch-predictor state: Spectre mitigations (IBPB, STIBP) on cross-trust-domain switches can add ~5 µs on older CPUs.

IPC Mechanisms

Processes do not share memory by default, so they communicate through kernel-mediated channels:

Virtual Address Spaces

Each process sees a private, contiguous virtual address space. x86_64 uses 48-bit canonical addresses (256 TiB) split into a user half (0x0000_0000_0000_0000 .. 0x0000_7fff_ffff_ffff) and a kernel half (0xffff_8000_0000_0000 and up). Addresses between are non-canonical and fault on use. 5-level paging raises the limit to 57 bits (128 PiB), gated by CR4.LA57.

Why bother with virtual memory? Three wins:

• Isolation — process A cannot read/write process B's pages because their page tables point to different physical frames.
• Sparseness — a process claims 256 TiB of logical space and only pays for pages it touches (the kernel populates page-table entries lazily on fault).
• Relocation & sharing — shared libraries and COW pages live in physical memory once but are mapped into many virtual spaces.

Paging & Page-Table Entries

Memory is divided into fixed-size pages (4 KiB default; 2 MiB and 1 GiB “huge pages” available). The MMU translates a virtual page number (VPN) to a physical frame number (PFN) by walking the multi-level page table anchored at CR3.

x86_64 4-level paging (48-bit virtual address)

Page-Table Entry (4 KiB page, x86_64) — the bits that matter

Virtual → Physical Translation (with TLB miss walk)

The hot path checks the TLB; on miss, the hardware page-table walker (PMH on Intel) walks all four levels. The visualization below steps through a load of address 0x7FFE_1234_5ABC.

Cost of a miss

• Best case — all four PTEs in L1d: ~4 cycles × 4 + transit = ~20 ns.
• Typical case — PTEs in L2/L3: ~100–200 ns for the walk.
• Worst case — PTEs in RAM or not present: a full page fault is tens of microseconds; swapping from disk is milliseconds.

TLB & Miss Handling

The Translation Lookaside Buffer is a small, fully or set-associative cache of recent VPN → PFN mappings. Modern CPUs have a split L1 TLB (dTLB + iTLB), unified L2 TLB, and separate large-page TLBs:

Who flushes the TLB?

• Writing CR3 (cross-address-space switch) flushes all non-Global entries — unless PCID (CR4.PCIDE=1) tags entries by ASID.
• INVLPG addr flushes one VPN — issued after a PTE edit.
• INVPCID invalidates by PCID (kernel path).
• Spectre-style mitigations (IBPB) may invalidate the branch predictor but not the TLB.
• A multi-core TLB flush is a “shootdown” — one core IPIs the others to run their INVLPG; this is why large unmap operations on big multicore machines are expensive.

Segmentation & mmap

Historic segmentation (Intel 80286/386) sliced the address space into length-limited segments with distinct CS/DS/SS/ES bases. x86_64 reduced it to a relic: all segments have base=0, limit=infinity. Only fs and gs bases survive as pointers to per-thread / per-CPU data (TLS).

Instead, Linux exposes virtual memory areas (VMAs) through mmap. Each VMA has a base, length, protection (r/w/x), and backing object (file, dev/zero, or anonymous).

/* memory-map a 64 MiB file, read lazily by page fault */
#include <sys/mman.h>
#include <fcntl.h>

int fd = open("data.bin", O_RDONLY);
void *base = mmap(NULL, 64*1024*1024, PROT_READ,
                  MAP_PRIVATE, fd, 0);
/* touching base[0] triggers a page fault; kernel populates the
   page from the page cache (or reads it in). zero-copy for reads. */
madvise(base, 64*1024*1024, MADV_RANDOM);  /* hint */

Anonymous vs file-backed

• Anonymous (MAP_ANONYMOUS): backed by swap, zero-filled on first touch. Used by malloc's large allocations and per-thread stacks.
• File-backed: pages are populated from the file on fault; dirty pages flushed back on writeback or msync. Shared mappings (MAP_SHARED) propagate writes to the file and to other mappers.

Page Fault Handling

A #PF is raised when the MMU sees P=0, a permission violation, or a non-canonical address. The kernel's do_page_fault classifies the fault by looking up the faulting address in the VMA list:

Goals & Metrics

A scheduler picks which ready thread gets the CPU next. It is pulled in four directions that conflict:

• Throughput — jobs completed per unit time. Maximized by minimizing context switches.
• Turnaround time — finish − arrival. Shorter = better responsiveness for batch.
• Waiting time — time spent in the ready queue. A proxy for perceived latency.
• Response time — first time the job runs after arrival. Critical for interactive workloads.
• Fairness — every thread of equal priority makes comparable progress. Violated by starvation.

Two orthogonal knobs:

• Preemptive vs non-preemptive — can the scheduler forcibly take the CPU back?
• Priority vs time-slice — who gets to run, or for how long?

Benchmark Workload

To compare schedulers apples-to-apples, we run the same five processes through each algorithm:

Total work = 22 units. Below we derive waiting time (how long each process sat in the ready queue) and turnaround time (completion − arrival) for each scheduler.

FCFS (First-Come First-Served)

Non-preemptive. Runs jobs in arrival order. Simple to implement, easy to starve: a 10-second burst arriving at time 0 delays every subsequent 1-ms job behind it — the convoy effect.

Derivation of averages

/* FCFS dispatcher (kernel-style pseudocode in C) */
struct task *fcfs_pick_next(struct runqueue *rq) {
    if (list_empty(&rq->tasks)) return NULL;
    return list_first_entry(&rq->tasks, struct task, run_list);
}
void fcfs_enqueue(struct runqueue *rq, struct task *t) {
    list_add_tail(&t->run_list, &rq->tasks);   /* append in arrival order */
}

SJF / SRTF (Shortest Job First)

Non-preemptive SJF picks the ready job with the smallest CPU burst. Preemptive SJF = SRTF (Shortest Remaining Time First): if a shorter job arrives, kick the current one out. Provably optimal for mean waiting time — but requires knowing burst length, which production systems must estimate via exponential averaging.

Derivation of averages

Round Robin (RR)

Preemptive. Every ready process gets a fixed time quantum q in FIFO order. When q expires the job goes to the tail of the queue. q too small → high switch overhead; too large → degenerates into FCFS.

Below we simulate RR with q = 2. Arrivals enter the queue tail as they appear.

Derivation (q=2)

/* Round-robin scheduler skeleton */
struct task *rr_pick_next(struct runqueue *rq) {
    return list_first_entry(&rq->tasks, struct task, run_list);
}
void rr_tick(struct task *t, struct runqueue *rq) {
    if (--t->quantum == 0) {
        t->quantum = RR_QUANTUM;              /* e.g. 4 ms */
        list_move_tail(&t->run_list, &rq->tasks);
        schedule();                           /* forces resched */
    }
}

Multi-Level Feedback Queue (MLFQ)

Several priority queues (Q0 highest .. Qn lowest). A job starts in Q0. If it uses its full quantum it drops to Q(i+1). If it voluntarily yields (I/O) before the quantum ends, it stays — interactive jobs float near the top, CPU-bound ones sink. Periodic priority boost at interval S raises everyone back to Q0 to prevent starvation.

Rules (Arpaci-Dusseau):

1. If Priority(A) > Priority(B): A runs.
2. If Priority(A) == Priority(B): round-robin.
3. New job enters at the highest priority.
4. If a job uses its entire time allotment at a level, it drops.
5. After time S, move all jobs to the topmost queue (boost).

CFS — Linux Completely Fair Scheduler

CFS picks the runnable task with the smallest vruntime (virtual runtime). The tasks sit in a red-black tree indexed by vruntime; picking the leftmost node is O(log n). “Fair” = every task makes the same vruntime progress over sched_latency.

Nice values map to weights: nice 0 → 1024, each nice step multiplies by ~1.25. Effective time-slice = sched_latency × (weight / total_weight), so a higher-weighted task runs longer slices and accumulates vruntime slower:

/* Simplified CFS vruntime update (kernel/sched/fair.c) */
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;
    if ((s64)delta_exec <= 0) return;
    curr->exec_start = now;
    curr->vruntime  += calc_delta_fair(delta_exec, curr);  /* weighted */
    update_min_vruntime(cfs_rq);
}

CFS knobs

Linux 6.6+ replaces CFS with EEVDF (Earliest Eligible Virtual Deadline First) — still a weighted-fair queue, but with a proper deadline-based ordering that reduces latency outliers.

Head-to-Head Summary

Race Conditions & Atomicity

A race condition arises when two threads access the same memory location concurrently, at least one is a write, and there is no happens-before ordering between them. The canonical example is an unprotected counter:

/* counter.c — the classic race */
int counter = 0;
void *work(void *arg) {
    for (int i = 0; i < 1000000; ++i)
        counter++;           /* load, inc, store — 3 instructions */
    return NULL;
}
/* 4 threads: expected 4,000,000; observed 3,127,841 (lost updates). */

Each counter++ compiles to mov, inc, mov. Interleave two threads and a read can miss an update from another core. The fix is either a mutex or an atomic (hardware lock xadd).

Critical-section requirements (Dijkstra / Lamport)

• Mutual exclusion — at most one thread inside.
• Progress — no thread outside the section blocks entry.
• Bounded waiting — once you request entry you wait at most k entries by others.

Mutexes & Spinlocks

A mutex is a binary, owned lock: only the holder can unlock. Under contention the loser either spins (CPU-busy) or sleeps (kernel-parked).

/* Test-and-set spinlock (toy, no back-off) */
typedef struct { _Atomic int flag; } spin_t;

static inline void spin_lock(spin_t *s) {
    while (atomic_exchange_explicit(&s->flag, 1,
                                   memory_order_acquire)) {
        while (atomic_load_explicit(&s->flag,
                                   memory_order_relaxed))
            __builtin_ia32_pause(); /* spin-hint */
    }
}
static inline void spin_unlock(spin_t *s) {
    atomic_store_explicit(&s->flag, 0, memory_order_release);
}

Why not just spin forever?

• Priority inversion — a high-priority spinner burns CPU while the low-priority holder is waiting for CPU; neither makes progress.
• Cache-line ping-pong — every spinner issues cache-line-exclusive requests; the lock line bounces between cores.
• Power — spinning defeats C-states; phones and laptops hate it.

Linux userspace uses futexes: the fast path is an atomic CAS entirely in userspace; only on contention does the loser call FUTEX_WAIT into the kernel.

Semaphores — Counting & Binary

A semaphore holds an integer. wait/P(s) decrements (blocking if it would go negative); signal/V(s) increments (waking one waiter). Dijkstra's original design is the seed of most sync primitives.

• Binary semaphore — values in {0,1}. Looks like a mutex but anyone can signal it (no ownership). Good for signalling.
• Counting semaphore — models a pool of N resources (connection pool, bounded buffer slots).

/* POSIX sem_t — counting semaphore bounding connection pool */
#include <semaphore.h>

static sem_t slots;
sem_init(&slots, 0, 16);          /* 16 available */

void *handler(void *arg) {
    sem_wait(&slots);            /* P: block if 0 */
    conn_t c = pool_take();
    serve(c);
    pool_return(c);
    sem_post(&slots);            /* V: wake one */
    return NULL;
}

Monitors & Condition Variables

A monitor is a higher-level construct: an object whose methods are mutually exclusive (implicit mutex) and whose threads rendezvous via condition variables. Java's synchronized + wait/notify is a direct descendant. POSIX models it as a pthread_mutex_t paired with a pthread_cond_t.

CV operations:

• wait(mutex) — atomically release the mutex and block. On wake, reacquire the mutex before returning.
• signal() / notify() — wake one waiter (no-op if empty).
• broadcast() / notifyAll() — wake all waiters (they contend for the mutex).

Wait semantics: Hoare vs Mesa

Bounded-Buffer Producer-Consumer (2P + 2C, size 4)

Two producers, two consumers, a circular buffer of 4 slots. Three semaphores coordinate: empty counts free slots (init 4), full counts produced items (init 0), and mutex protects buffer indices (binary, init 1).

/* bounded_buffer.c — classic Bernstein/Dijkstra pattern */
#define N 4
item_t buf[N];
int   in = 0, out = 0;
sem_t empty, full, mutex;
sem_init(&empty, 0, N);
sem_init(&full,  0, 0);
sem_init(&mutex, 0, 1);

void *producer(void *_) {
    for (;;) {
        item_t it = produce_next();
        sem_wait(&empty);            /* at least one slot */
        sem_wait(&mutex);            /* critical section */
        buf[in] = it; in = (in + 1) % N;
        sem_post(&mutex);
        sem_post(&full);             /* signal consumers */
    }
}
void *consumer(void *_) {
    for (;;) {
        sem_wait(&full);
        sem_wait(&mutex);
        item_t it = buf[out]; out = (out + 1) % N;
        sem_post(&mutex);
        sem_post(&empty);
        consume(it);
    }
}

Order of acquiring semaphores matters

Both producer and consumer acquire their counting semaphore before the mutex. Reverse it and you deadlock: producer holds mutex while blocked on empty, consumer cannot acquire mutex to release a slot.

The Four Coffman Conditions (1971)

All four must hold simultaneously for deadlock. Break any one and deadlock is impossible.

Canonical example — the opposite-direction lock order

/* Thread A */          /* Thread B */
pthread_mutex_lock(&m1);      pthread_mutex_lock(&m2);
pthread_mutex_lock(&m2);      pthread_mutex_lock(&m1);  /* wait — deadlock */
/* work */                    /* work */
pthread_mutex_unlock(&m2);    pthread_mutex_unlock(&m1);
pthread_mutex_unlock(&m1);    pthread_mutex_unlock(&m2);
/* Fix: both sides acquire in m1-then-m2 order. */

Resource Allocation Graph (RAG)

Model processes as circles, resources as squares. An edge from process → resource means “requests”; resource → process means “currently allocated to.” Deadlock in a single-instance system iff there is a cycle. With multiple instances, a cycle is necessary but not sufficient — check actual availability.

Detection via Cycle Finding

With a RAG in memory, detect deadlock by running DFS and looking for a back-edge in the directed graph. Kernel deadlock detectors (lockdep in Linux) keep an in-memory chain of lock-acquire-order pairs and flag any new edge that would complete a cycle, before the deadlock actually happens.

# Simple DFS cycle-detection on a wait-for graph (Python)
def has_cycle(adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in adj}
    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:       # back-edge = cycle
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False
    return any(dfs(v) for v in adj if color[v] == WHITE)

Recovery strategies once deadlock is detected

• Process termination — kill all deadlocked processes, or pick a victim by cost (total CPU spent, priority, resources held).
• Resource preemption — force-release a resource; requires rollback to a safe checkpoint (common in DBs via transaction abort).
• Operator intervention — log, alert, manual cleanup. Used when correctness trumps availability.

Prevention vs Avoidance

Banker's Algorithm — Avoidance by Safety Check

Dijkstra 1965. Given each process's maximum claim, grant a request only if the post-grant state is safe — i.e. there exists an ordering of processes that can all complete with current available resources.

Inputs (for n processes, m resource types):

• Max[n][m] — max units process i will ever need of resource j.
• Alloc[n][m] — units currently held.
• Need[i][j] = Max[i][j] - Alloc[i][j] — remaining demand.
• Available[m] — pool.

Worked example: 5 processes, 3 resource types (A, B, C)

Total resources: A=10, B=5, C=7. Initial state:

Available = Total - Sum alloc = (3, 3, 2).

Reference implementation

/* bankers.py — classic safety algorithm */
def is_safe(avail, max_need, alloc):
    n, m = len(alloc), len(avail)
    need = [[max_need[i][j] - alloc[i][j] for j in range(m)]
            for i in range(n)]
    work = avail[:]
    finish = [False] * n
    order = []
    while True:
        progressed = False
        for i in range(n):
            if finish[i]: continue
            if all(need[i][j] <= work[j] for j in range(m)):
                for j in range(m): work[j] += alloc[i][j]
                finish[i] = True
                order.append(i)
                progressed = True
        if not progressed: break
    return (all(finish), order)

Inodes & On-Disk Layout

UNIX file systems separate metadata (an inode) from the data blocks. An inode carries: mode, uid/gid, timestamps, size, refcount, and pointers to data blocks. Directories are just special files whose data is a table of name → inode.

Directories, Hard Links & Path Resolution

A directory is a file whose data blocks contain (name, inode_number) records. ls reads that; stat then resolves each inode. The filesystem tree is a directed graph with hard links (more than one name per inode) and soft links (a file whose content is the path to traverse).

Hard vs soft links

# Observe hard vs soft links
$ echo hello > a
$ ln   a hard      # hard link — same inode, nlink = 2
$ ln -s a soft     # symlink — separate inode
$ stat -c '%i %h %n' a hard soft
12345 2 a
12345 2 hard
12346 1 soft

Journaling — Crash Consistency without fsck

Without a journal, a crash during a multi-block write can leave the filesystem inconsistent (e.g., inode says 1 MiB but only 512 KiB of data blocks allocated). The journal is a circular log of transactions: group metadata edits, write them to the log first, then the main filesystem.

Phases of a journalled write (ext4 in data=ordered mode)

1. Begin txn — gather all dirty inodes, bitmaps, and directory blocks for this syscall.
2. Data write — write user data blocks to their final location. Wait for them to be durable.
3. Journal log — write the metadata edits (inodes, bitmaps) to the journal with a descriptor block. Wait.
4. Commit record — write a single commit block with checksum. This is the atomic point: either the commit is durable (txn replayable) or it isn't (txn will be discarded).
5. Checkpoint — later, write the metadata to the main filesystem and mark the journal space reusable.

Journal modes

LFS vs COW

Traditional (ext4, XFS) update data blocks in-place and use a journal for metadata. Two alternative designs eliminate in-place updates entirely:

Log-Structured FS (LFS / F2F / NILFS)

• All writes (data + metadata) are appended to a log.
• An inode map (imap) tracks “where is the latest version of inode i?”
• Reads follow imap → inode → data blocks (same as regular FS).
• A segment cleaner compacts partially-dead segments to reclaim space.
• Ideal for flash: write-heavy, sequential, no RMW amplification.

Copy-on-Write (ZFS, btrfs, APFS)

• Never overwrite a live block. Every update writes to a new location and replaces pointers up the tree.
• A superblock atomically swings to the new root — all edits atomic.
• Cheap snapshots: retain an old root, its subtree is still reachable.
• End-to-end checksums on every block (optional) — catches silent bit rot.
• Write amplification: editing a byte may rewrite the path from root to leaf.

Crash Consistency & fsync

Even with a journal you must invoke fsync(fd) to tell the kernel “flush my data to durable storage.” Without it the page cache may hold your write for seconds. fsync on a directory ensures directory entries are durable (critical for rename-based atomic replace).

/* Durable atomic file replace (POSIX) */
int fd = open("data.new", O_WRONLY|O_CREAT|O_TRUNC, 0644);
write(fd, payload, len);
fsync(fd);                    /* flush data */
close(fd);
rename("data.new", "data"); /* atomic on same FS */
int dfd = open(".", O_RDONLY|O_DIRECTORY);
fsync(dfd);                   /* flush dir entry, else rename can be lost */
close(dfd);

Blocking / Non-blocking / Sync / Async Matrix

Two orthogonal properties govern any read or write:

• Blocking vs non-blocking — does the call wait when data isn't ready?
• Synchronous vs asynchronous — does the caller do the I/O itself, or ask the kernel to do it and notify when done?

select / poll / epoll / kqueue

All four let a single thread monitor many FDs. They differ in how the FD set is conveyed and how scalable they are:

/* epoll event loop skeleton */
int ep = epoll_create1(0);
struct epoll_event ev = { .events = EPOLLIN|EPOLLET, .data.fd = sock };
epoll_ctl(ep, EPOLL_CTL_ADD, sock, &ev);

for (;;) {
    struct epoll_event evs[64];
    int n = epoll_wait(ep, evs, 64, -1);
    for (int i = 0; i < n; ++i) {
        int fd = evs[i].data.fd;
        if (evs[i].events & EPOLLIN) {
            /* ET mode: drain until EAGAIN */
            for (;;) {
                ssize_t r = read(fd, buf, sizeof(buf));
                if (r < 0 && errno == EAGAIN) break;
                if (r <= 0) { close(fd); break; }
                handle(fd, buf, r);
            }
        }
    }
}

Edge vs Level Triggered

io_uring — True Async I/O on Linux

Introduced in Linux 5.1 (2019). Two lock-free shared-memory ring buffers (SQ: submission, CQ: completion) between userspace and kernel. The app writes SQEs; the kernel consumes them, does the I/O, writes CQEs. Zero syscalls per I/O in the busy case (IORING_SETUP_SQPOLL polls the SQ from a kernel thread).

What it subsumes

• Every read/write/send/recv/accept/connect/openat/stat/close/fsync — submittable, batchable.
• Buffered, direct, and zero-copy (IORING_OP_SEND_ZC).
• Chained / linked SQEs: “open, then read, then close” as a single submission.
• Registered buffers + files: skip reference counting per I/O.

Common epoll / Event-Loop Bugs

Futures & Promises

A future is a handle to a value that will arrive later. A promise is the write side of that pair — whoever computes the value completes the promise, which fulfils all futures derived from it. Semantically identical to a continuation-passing callback, but composable.

# Python futures/async composition
import asyncio, aiohttp

async def fetch(session, url):
    async with session.get(url) as r:
        return await r.text()

async def main(urls):
    async with aiohttp.ClientSession() as s:
        # All fetches run concurrently; gather awaits all.
        pages = await asyncio.gather(*(fetch(s, u) for u in urls))
        return [len(p) for p in pages]

asyncio.run(main(["https://a.example/", "https://b.example/"]))

Combinators you must know

• map — transform the eventual value.
• flatMap / then — chain another future that depends on this one's result.
• all / gather — wait for N futures, return a list of N results.
• race / any — return the first to succeed (or fail).
• timeout — cancel after a deadline.

Actor Model — Isolation by Mailbox

Each actor is a lightweight process with private state and a mailbox. Communication is one-way messages: actor A sends to B's mailbox, B processes messages one at a time. Because state is private and access is serial, no locks required. Erlang/OTP, Akka, Elixir popularized it.

# Actor-style counter with a single mailbox coroutine
import asyncio

async def counter_actor(inbox):
    n = 0
    while True:
        msg = await inbox.get()
        if msg == "inc": n += 1
        elif isinstance(msg, tuple) and msg[0] == "get":
            msg[1].set_result(n)
        elif msg == "stop":
            return

Strengths / weaknesses

• + No shared state, no locks, compositional supervision trees.
• + “Let it crash” recovery — a supervisor restarts a failing actor.
• − Ordering only within a mailbox; cross-actor invariants require careful protocol design.
• − Bounded mailboxes or you risk unbounded memory growth under back-pressure.

CSP Channels (Hoare, 1978 → Go)

Communicating Sequential Processes: goroutines synchronize by sending values through typed channels, not shared memory. Unbuffered channels are rendezvous (sender blocks until receiver arrives); buffered channels act as a bounded queue.

// Go: pipeline of goroutines via channels
package main
import "fmt"

func producer(ch chan<- int) {
    for i := 0; i < 5; i++ { ch <- i }
    close(ch)
}
func consumer(ch <-chan int, done chan<- bool) {
    for v := range ch { fmt.Println(v) }
    done <- true
}
func main() {
    ch := make(chan int, 2)
    done := make(chan bool)
    go producer(ch)
    go consumer(ch, done)
    <-done
}

Event Loop — Single-threaded Concurrency

One thread running a FIFO of callbacks. Non-CPU work (network, disk, timers) is delegated to the kernel (epoll/kqueue) or a small threadpool (libuv); the loop only dispatches ready tasks. JS engines (Node, browsers) and Python's asyncio both work this way.

async / await Mechanics

Syntactic sugar over state machines. The compiler translates each async def into a class with methods send, throw, close; each await becomes a suspension point. The runtime drives the state machine from an event loop.

# Roughly what "async def f()" becomes at the bytecode level
class AwaitableF:
    def __init__(self): self.state = 0
    def send(self, val):
        if self.state == 0:
            self.state = 1
            return some_future           # suspend
        elif self.state == 1:
            result = val                   # future's value
            raise StopIteration(result)    # done

Reordering & Visibility

Two threads on two cores see a different order of the same stores. This isn't a bug; it's the architecture. Both the compiler and the CPU freely reorder instructions that are independent within a single thread. Cross-thread visibility requires explicit synchronization.

Who reorders what?

Hardware model strengths

• x86/x86_64 — TSO (Total Store Ordering). Stores don't reorder with earlier stores; loads don't reorder with earlier loads or stores. Only reordering allowed: a store followed by a load to a different address.
• ARM64 — Relaxed. Any pair of independent memory ops can reorder. Requires explicit dmb/ldar/stlr.
• POWER — Even weaker than ARM. Must fence often.

Happens-Before — The Reasoning Primitive

Define a partial order “hb” over events in a program. If a hb b, then a's writes are visible when b executes. The rules are few and compose transitively:

1. Program order — within a thread, earlier statements hb later ones.
2. Unlock / Lock — an unlock of m hb every subsequent lock of m.
3. Release / Acquire — an atomic store-release hb every atomic load-acquire that reads it.
4. Volatile (Java) — a write to a volatile hb every subsequent read of that volatile.
5. Thread start / join — t.start() hb everything in t; everything in t hb t.join() returning.
6. Transitivity — a hb b and b hb c implies a hb c.

Acquire / Release / SeqCst

/* Dekker-style publication with release/acquire (C11) */
_Atomic int  flag = 0;
int          payload;

void producer(void) {
    payload = 42;                                   /* non-atomic write */
    atomic_store_explicit(&flag, 1,
                          memory_order_release);
}
void consumer(void) {
    while (atomic_load_explicit(&flag,
                                 memory_order_acquire) == 0) { }
    printf("%d\n", payload); /* guaranteed to see 42 */
}

Fences & Barriers

A fence is a standalone instruction that restricts reordering around it without itself being a read or write. Use when you need ordering without an atomic op:

• Full fence (mfence / dmb ish): no load or store moves across.
• Load fence (lfence): earlier loads complete before later loads.
• Store fence (sfence): earlier stores complete before later stores.
• Compiler fence only: asm volatile("" ::: "memory") — prevents the compiler from reordering, but no hardware barrier.

The ABA Problem on a Lock-Free Stack

The canonical CAS-based pop is: read head, read head->next, CAS head from old to next. If between your read and CAS someone pops A, pops B, then pushes A back — head is still A, CAS succeeds, but head->next now points at freed memory.

Fixes

• Versioned pointers (double-word CAS) — store (ptr, version) in 128 bits; every pop increments version. cmpxchg16b on x86.
• Hazard pointers (Michael, 2004) — before dereferencing a shared pointer, publish it as “in use”; reclaimers skip nodes announced by any thread.
• Epoch-based reclamation (crossbeam in Rust) — a node is freed only when no thread is in an older epoch.
• RCU (Linux kernel) — reclaim after a grace period in which every CPU has context-switched.

/* Treiber stack pop with DWCAS versioned head */
struct Node { int v; Node* next; };
struct Head { Node* p; uint64_t ver; };
_Atomic(struct Head) head;

Node* pop(void) {
    struct Head old, neu;
    do {
        old = atomic_load(&head);
        if (!old.p) return NULL;
        neu.p   = old.p->next;
        neu.ver = old.ver + 1;       /* defeats ABA */
    } while (!atomic_compare_exchange_weak(&head, &old, neu));
    return old.p;
}

Module Summaries

Latency Numbers Every OS Candidate Should Know

Rapid-Fire Q&A

POSIX / Linux Command Matrix