Operating Systems

Introduction to OS

What Does an OS Do?

An operating system sits between the raw hardware and the applications you write. It has two jobs that are in tension with each other: act as a resource manager (deciding who gets the CPU, memory, disk, and devices, and for how long) and act as an abstraction layer (hiding the ugly details of hardware behind clean interfaces like files, sockets, and processes).

• Process management — creating, scheduling, and terminating processes/threads; providing each process the illusion of owning the CPU.
• Memory management — giving each process the illusion of a large, private, contiguous address space via virtual memory.
• File & storage management — organizing bytes on disk into files and directories, and managing free space.
• I/O & device management — mediating access to devices via drivers, buffering, and interrupt handling.
• Protection & security — isolating processes from each other and from the kernel via privilege levels and permissions.
• Networking — implementing protocol stacks and exposing sockets to user space.

Types of OS

System Calls vs Library Calls

A system call is a request from user-space code to the kernel to perform a privileged operation — reading a file, allocating memory pages, creating a process. It crosses the user/kernel boundary via a trap instruction (e.g. syscall on x86-64), which costs a mode switch and is measurably more expensive than a normal function call. A library call is an ordinary function call resolved entirely in user space (e.g. strlen, `std::sort`) — it may or may not invoke a system call internally. printf, for instance, is a library call that buffers output in user space and eventually issues a write() system call when the buffer flushes.

Kernel Mode vs User Mode

CPUs implement at least two privilege levels enforced by a hardware mode bit (x86 calls these "rings", 0 = most privileged). In user mode, code cannot execute privileged instructions (like changing page tables, halting the CPU, or directly touching device registers) — attempting to do so triggers a trap into the kernel. In kernel mode, the OS has unrestricted hardware access. The only way to move from user to kernel mode is through a controlled entry point: a system call, an interrupt, or an exception (like a page fault or divide-by-zero) — never an arbitrary jump. This is the fundamental protection mechanism that keeps one buggy or malicious process from corrupting another process or the OS itself.

Monolithic vs Microkernel

Processes

Program vs Process vs Thread

A program is a passive entity — an executable file on disk containing instructions and static data. A process is a program in execution: an active entity with its own address space, open file descriptors, and execution state. A thread is a unit of execution within a process; all threads of a process share the same address space, heap, and file descriptors, but each has its own stack, registers, and program counter.

Process Control Block (PCB)

The kernel represents every process with a data structure — in Linux, struct task_struct — commonly called the Process Control Block. It's the process's identity as far as the OS is concerned.

Process States

A process moves through a well-defined set of states over its lifetime:

            admitted             scheduler dispatch
   NEW  ─────────────────▶ READY ─────────────────▶ RUNNING
                              ▲                         │
                              │   I/O or event           │ exit
                    interrupt │   completion              ▼
                              │                     TERMINATED
                              │                         ▲
                              │      I/O or event wait   │
                          WAITING ◀──────────────────────┘
                                     (running process
                                      blocks on I/O)

• New — process is being created (PCB allocated, but not yet admitted to the ready queue).
• Ready — process has everything it needs except the CPU; waiting in the ready queue for the scheduler.
• Running — instructions are actually executing on a CPU core.
• Waiting/Blocked — process is waiting on an event (I/O completion, a lock, a signal) and cannot make progress even if given the CPU.
• Terminated — process has finished execution; its PCB may briefly remain (zombie) until the parent collects the exit status.

Context Switching

A context switch is the act of saving the state of the currently running process and restoring the state of another. It happens on: a timer interrupt (quantum expiry), a higher-priority process becoming ready, a blocking system call, or an interrupt. Context switching is pure overhead — no useful work is done during the switch itself. Costs include:

• Saving/restoring registers and program counter (cheap, microseconds).
• Switching page tables (updating CR3 on x86) — flushes TLB entries not tagged with an ASID/PCID, causing a burst of TLB misses afterward.
• Cache pollution — the new process's working set evicts the old process's data from L1/L2 cache, causing cache misses as it warms back up.

This is exactly why thread context switches (same address space, no page-table switch) are cheaper than process context switches.

fork() / exec() & Copy-on-Write Intermediate

Unix splits "create a process" and "run a different program" into two separate calls, which is unusual compared to Windows' single CreateProcess — but it's extremely powerful because it lets the shell set up file descriptors (for redirection/pipes) between the fork and the exec.

#include <unistd.h>
#include <sys/wait.h>
#include <stdio.h>

int main() {
    pid_t pid = fork();          // duplicate the calling process

    if (pid < 0) {
        perror("fork failed");
    } else if (pid == 0) {
        // Child: pid == 0 here
        printf("child: about to exec\n");
        execlp("/bin/ls", "ls", "-l", NULL);   // replaces child's image
        perror("exec failed");   // only reached if execlp fails
        _exit(1);
    } else {
        // Parent: pid == child's real PID here
        int status;
        waitpid(pid, &status, 0);   // reap child, avoid zombie
        printf("child exited with status %d\n", WEXITSTATUS(status));
    }
    return 0;
}

fork() creates a near-identical copy of the calling process (same code, data, open file descriptors) and returns twice: 0 in the child, the child's PID in the parent. Naively copying the entire address space would be wasteful, especially since most forks are immediately followed by an exec() that throws the copy away. So modern Unix kernels use copy-on-write (COW): fork() duplicates only the page tables, marking every page read-only and shared between parent and child. The first time either process writes to a shared page, the CPU raises a page fault, and the kernel transparently allocates a private copy of just that one page for the writer. If neither process writes before the child execs, zero data pages are ever copied.

exec() family (execve, execlp, execvp, ...) replaces the calling process's address space, code, and data with a new program, keeping the same PID and open file descriptors (unless marked close-on-exec).

Zombie & Orphan Processes

A zombie process has terminated (called exit()), but its PCB/exit-status entry still occupies a slot in the process table because its parent hasn't called wait()/waitpid() to collect it yet. Zombies consume no memory or CPU beyond the PCB slot, but if a parent leaks them indefinitely (never reaping), it can exhaust the system's PID table.

An orphan process is one whose parent terminated before it did. Orphans are automatically re-parented to init (PID 1) or a subreaper (e.g. systemd), which periodically calls wait() on its children specifically to reap zombies. So an orphan is not a leak — it's a zombie you'd actually have to worry about if it weren't for re-parenting.

CPU Scheduling

Scheduling Criteria

Long / Short / Medium-Term Schedulers

• Long-term scheduler (admission scheduler) — decides which jobs are admitted into the ready queue from the job pool. Controls the degree of multiprogramming. Runs infrequently.
• Short-term scheduler (CPU scheduler / dispatcher) — decides which ready process runs next on the CPU. Runs very frequently (every few milliseconds), so it must be fast.
• Medium-term scheduler — swaps processes out of memory (to disk) to reduce the degree of multiprogramming when memory is under pressure, and swaps them back in later. Sits between "in memory, ready" and "suspended."

FCFS (First-Come, First-Served) Basic

Non-preemptive; processes run strictly in arrival order. Simple, but suffers the convoy effect: a single long CPU-bound process at the front makes every short process behind it wait, tanking average waiting time.

Average waiting time = (0 + 24 + 27 + 30) / 4 = 20.25. Reordering to P2, P3, P4, P1 (shortest first) would drop this dramatically — which is exactly the motivation for SJF below.

SJF — Shortest Job First (Preemptive & Non-Preemptive) Intermediate

Picks the process with the smallest CPU burst next. Provably optimal for minimizing average waiting time among non-preemptive algorithms, but requires knowing burst times in advance — in practice these are only estimated (e.g. via exponential averaging of past bursts). The preemptive variant is called SRTF (Shortest Remaining Time First): a newly arrived process with a shorter remaining burst can preempt the currently running one.

Average waiting time = (0 + 3 + 6 + 9) / 4 = 4.5 — far better than FCFS's 20.25 on the same workload. The catch: starvation — a long process can be perpetually skipped if short processes keep arriving.

Priority Scheduling

Each process gets a priority number; the CPU is allocated to the highest-priority ready process (convention varies — often lower number = higher priority). Can be preemptive or non-preemptive. Same starvation risk as SJF (a low-priority process may never run) — solved with aging: gradually increase the priority of processes that have waited a long time.

Round Robin Intermediate

Preemptive, time-sliced version of FCFS: each process gets a fixed time quantum; if it doesn't finish, it's preempted and moved to the back of the ready queue. Fair and good for response time, but throughput depends heavily on quantum size — too small and context-switch overhead dominates; too large and it degenerates into FCFS.

Worked example: P1 = 24, P2 = 3, P3 = 3, quantum = 4.

| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 |
0    4    7   10   14   18   22   26   30

P2 and P3 finish in their first slice (burst ≤ quantum). P1 needs 6 total slices of work (24/4). Waiting times: P1 = 30 − 24 = 6, P2 = 7 − 3 = 4, P3 = 10 − 3 = 7. Average waiting time = (6 + 4 + 7) / 3 = 5.67.

Multilevel Queue

The ready queue is split into several separate queues by process category (e.g. "foreground/interactive" and "background/batch"), each with its own scheduling algorithm (e.g. RR for foreground, FCFS for background), plus a fixed policy for scheduling between queues (e.g. strict priority, or a time-slice split like 80% CPU to foreground, 20% to background). Processes are permanently assigned to a queue at creation — there's no movement between queues, which is the main weakness this algorithm has relative to the next one.

Multilevel Feedback Queue (MLFQ)

The most general CPU-scheduling algorithm: like multilevel queue, but processes can move between queues based on observed behavior. Typical setup: multiple queues with increasing quantum sizes and decreasing priority. A new process starts in the highest-priority (shortest quantum) queue. If it uses its entire quantum (behaves CPU-bound), it's demoted to a lower-priority, longer-quantum queue. If it blocks on I/O before its quantum expires (behaves interactively), it stays at the same or is promoted to a higher-priority level. This approximates SJF without requiring the OS to know burst times in advance — interactive/short jobs naturally stay in the fast queues, CPU-bound jobs sink to the slow ones. To prevent starvation of long jobs, MLFQ implementations periodically boost all processes back to the top queue.

Algorithm Comparison

Linux CFS (Completely Fair Scheduler)

Linux's default scheduler since 2.6.23 (being succeeded by EEVDF in newer kernels, but CFS concepts are still the standard interview answer). Instead of fixed time slices, CFS models an idealized "perfectly fair" CPU that gives every runnable task an equal, infinitesimally small share of the CPU simultaneously, then approximates it in practice. Each task accumulates vruntime (virtual runtime) proportional to the CPU time it has actually consumed, weighted by its nice value (lower nice = higher weight = vruntime accumulates slower = gets scheduled more). Runnable tasks are kept in a red-black tree keyed by vruntime; the scheduler always picks the leftmost node (smallest vruntime = most "owed" CPU time). Running a task increases its vruntime, which naturally moves it rightward in the tree, letting other tasks take a turn — no fixed quantum bookkeeping needed the way RR requires.

Threads & Concurrency

User-Level vs Kernel-Level Threads

Multithreading Models

These describe how user-level threads are mapped onto kernel-level threads:

• Many-to-One — many user threads map to a single kernel thread. Fast creation/switching, but one blocking syscall blocks all threads, and no real parallelism across cores. (Old green threads, early Solaris Green Threads.)
• One-to-One — each user thread maps to its own kernel thread. True parallelism, a blocking syscall only blocks that thread — but thread creation is as expensive as kernel thread creation, and OSes often cap the number of kernel threads. (Linux pthreads, Windows threads.)
• Many-to-Many — m user threads multiplexed onto n kernel threads (n ≤ m). Combines flexibility of many-to-one with the parallelism of one-to-one; the runtime/kernel can create as many kernel threads as needed up to hardware limits. (Historic Solaris; conceptually similar to how Go's goroutine scheduler multiplexes goroutines onto OS threads, though Go's is a user-space M:N scheduler layered on top of one-to-one OS threads rather than an OS-level M:N model.)

Thread Pools

Creating a new OS thread per task is expensive (kernel thread creation + stack allocation) and an unbounded number of threads can exhaust memory or cause excessive context-switch thrashing. A thread pool pre-creates a fixed (or bounded, dynamically-sized) set of worker threads that pull tasks off a shared queue, amortizing thread-creation cost across many tasks and capping concurrency to something the hardware can actually handle in parallel (commonly sized around the core count for CPU-bound work).

#include <vector>
#include <queue>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>

class ThreadPool {
public:
    explicit ThreadPool(size_t n) {
        for (size_t i = 0; i < n; ++i) {
            workers_.emplace_back([this] { workerLoop(); });
        }
    }

    void submit(std::function<void()> task) {
        {
            std::lock_guard<std::mutex> lock(mtx_);
            tasks_.push(std::move(task));
        }
        cv_.notify_one();
    }

    ~ThreadPool() {
        {
            std::lock_guard<std::mutex> lock(mtx_);
            stop_ = true;
        }
        cv_.notify_all();
        for (auto &t : workers_) t.join();
    }

private:
    void workerLoop() {
        while (true) {
            std::function<void()> task;
            {
                std::unique_lock<std::mutex> lock(mtx_);
                cv_.wait(lock, [this] { return stop_ || !tasks_.empty(); });
                if (stop_ && tasks_.empty()) return;
                task = std::move(tasks_.front());
                tasks_.pop();
            }
            task();   // run outside the lock
        }
    }

    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mtx_;
    std::condition_variable cv_;
    bool stop_ = false;
};

Benefits & Costs of Multithreading

Green Threads

Green threads are threads scheduled entirely by a runtime/library in user space rather than by the OS kernel — essentially the many-to-one or many-to-many model applied by a language runtime. They enable extremely cheap "threads" (sometimes millions of them) since creation/switching avoids syscalls entirely. Examples: original Java green threads (pre-JDK 1.2), Ruby's fibers, Go's goroutines (M:N over OS threads), Erlang's lightweight processes. The tradeoff is the same as many-to-one/many-to-many: the runtime needs cooperative scheduling points or must intercept blocking syscalls (e.g. via a non-blocking I/O + event loop underneath) to avoid stalling every green thread when one does blocking I/O.

Process Synchronization

Race Conditions

A race condition occurs when the correctness of a program depends on the relative timing/interleaving of concurrent operations on shared data. The classic example: two threads both executing counter++ on a shared integer.

int counter = 0;

void increment() {
    counter++;   // NOT atomic! Compiles roughly to:
                 //   load  reg, counter
                 //   add   reg, 1
                 //   store counter, reg
}

If two threads interleave load-add-store, both can read counter = 5, both compute 6, both store 6 — one increment is silently lost. This is why counter++ on a plain int shared across threads is a bug even though it looks like one operation in source code.

Critical Section Problem

A critical section is a code segment that accesses shared resources and must not be executed by more than one thread/process concurrently. Any correct solution must satisfy three requirements:

• Mutual exclusion — no two processes may be inside their critical sections simultaneously.
• Progress — if no process is in its critical section, and some processes wish to enter, only those processes not in their remainder section can participate in deciding who enters next, and this decision can't be postponed indefinitely.
• Bounded waiting — there's a limit on how many times other processes can enter their critical section after a process has requested entry and before that request is granted (prevents starvation).

Peterson's Solution Intermediate

A classic software-only solution for two processes, using a flag[] array and a turn variable.

volatile int flag[2] = {0, 0};
volatile int turn;

// Process 0
void enter_critical_p0() {
    flag[0] = 1;
    turn = 1;
    while (flag[1] && turn == 1) { /* busy wait */ }
    // critical section
}
void exit_critical_p0() { flag[0] = 0; }

// Process 1
void enter_critical_p1() {
    flag[1] = 1;
    turn = 0;
    while (flag[0] && turn == 0) { /* busy wait */ }
    // critical section
}
void exit_critical_p1() { flag[1] = 0; }

Each process announces intent (flag[i] = 1), then politely yields the "turn" to the other. It satisfies all three critical-section requirements for exactly two processes. It's mostly of historical/theoretical interest today: it relies on sequential memory consistency, which modern compilers and out-of-order CPUs don't guarantee without explicit memory barriers — a compiler is free to reorder those stores/loads, and Peterson's algorithm silently breaks on real hardware without volatile/atomics with proper memory ordering.

Mutex vs Semaphore vs Monitor

Producer-Consumer Problem Intermediate

Also called the bounded-buffer problem: producers generate items into a fixed-size buffer, consumers remove them. Need to block producers when the buffer is full, block consumers when it's empty, and protect the buffer index/count from concurrent access.

#define N 8
sem_t empty_slots, filled_slots;
pthread_mutex_t mtx;
int buffer[N], in = 0, out = 0;

void init() {
    sem_init(&empty_slots, 0, N);   // N empty slots initially
    sem_init(&filled_slots, 0, 0);  // 0 filled slots initially
    pthread_mutex_init(&mtx, NULL);
}

void producer(int item) {
    sem_wait(&empty_slots);         // wait for a free slot
    pthread_mutex_lock(&mtx);
    buffer[in] = item;
    in = (in + 1) % N;
    pthread_mutex_unlock(&mtx);
    sem_post(&filled_slots);        // signal: one more item available
}

int consumer() {
    sem_wait(&filled_slots);        // wait for an item
    pthread_mutex_lock(&mtx);
    int item = buffer[out];
    out = (out + 1) % N;
    pthread_mutex_unlock(&mtx);
    sem_post(&empty_slots);         // signal: one more free slot
    return item;
}

The two counting semaphores (empty_slots, filled_slots) handle blocking/signaling; the mutex handles mutual exclusion on the shared indices. A full C++ std::mutex + std::condition_variable implementation appears later in Practical Coding.

Readers-Writers Problem Intermediate

Multiple readers may access shared data concurrently (reads don't conflict), but a writer needs exclusive access (no readers or other writers at the same time). The "first" readers-writers problem favors readers (a writer can starve if readers keep arriving); the "second" favors writers. A fair solution needs to bound both.

int read_count = 0;
pthread_mutex_t read_count_mtx;   // protects read_count
sem_t resource;                   // guards the actual data (writers hold this)

void reader() {
    pthread_mutex_lock(&read_count_mtx);
    read_count++;
    if (read_count == 1) sem_wait(&resource);   // first reader locks out writers
    pthread_mutex_unlock(&read_count_mtx);

    // ---- read shared data ----

    pthread_mutex_lock(&read_count_mtx);
    read_count--;
    if (read_count == 0) sem_post(&resource);    // last reader lets writers in
    pthread_mutex_unlock(&read_count_mtx);
}

void writer() {
    sem_wait(&resource);
    // ---- write shared data ----
    sem_post(&resource);
}

In production code, use a purpose-built primitive instead of hand-rolling this: POSIX pthread_rwlock_t, or C++17 std::shared_mutex (lock_shared() for readers, lock() for writers).

Dining Philosophers Problem Advanced

Five philosophers sit at a round table with five forks (one between each adjacent pair). Each philosopher needs both their left and right fork to eat. If every philosopher simultaneously picks up their left fork, none can get a right fork — deadlock via circular wait. This models resource allocation with cyclic dependencies. Standard fixes:

• Resource ordering — number the forks; every philosopher picks up the lower-numbered fork first. Breaks the circular-wait condition (see Deadlock Prevention).
• Asymmetry — have one philosopher (arbitrarily) pick up right-then-left while all others pick up left-then-right, breaking the symmetric cycle.
• Arbitrator/waiter — a mutex/semaphore that only allows N−1 philosophers to attempt picking up forks simultaneously, guaranteeing at least one can always complete.

pthread_mutex_t fork_mtx[5];

void philosopher(int i) {
    int left = i;
    int right = (i + 1) % 5;
    int first  = (left < right) ? left  : right;   // lower-numbered first
    int second = (left < right) ? right : left;

    pthread_mutex_lock(&fork_mtx[first]);
    pthread_mutex_lock(&fork_mtx[second]);

    // ---- eat ----

    pthread_mutex_unlock(&fork_mtx[second]);
    pthread_mutex_unlock(&fork_mtx[first]);
}

Sleeping Barber Problem Advanced

A barbershop has one barber, one barber chair, and N waiting chairs. If there are no customers, the barber sleeps. A customer who arrives while the barber sleeps wakes him up; a customer who arrives while the barber is busy sits in a waiting chair if one is free, or leaves if all are full. This models a bounded-buffer producer-consumer scenario with a twist: it's a classic exercise in expressing "wake a sleeping server" and "reject when full" correctly with semaphores.

#define CHAIRS 4
sem_t customers;      // count of waiting customers, barber waits on this
sem_t barber_ready;   // signals a customer that the barber is ready
pthread_mutex_t mtx;  // protects waiting count
int waiting = 0;

void barber() {
    while (1) {
        sem_wait(&customers);      // sleep until a customer arrives
        pthread_mutex_lock(&mtx);
        waiting--;
        pthread_mutex_unlock(&mtx);
        sem_post(&barber_ready);   // invite the customer to the chair
        // ---- cut hair ----
    }
}

void customer() {
    pthread_mutex_lock(&mtx);
    if (waiting < CHAIRS) {
        waiting++;
        pthread_mutex_unlock(&mtx);
        sem_post(&customers);      // notify barber
        sem_wait(&barber_ready);   // wait for barber's chair
        // ---- get haircut ----
    } else {
        pthread_mutex_unlock(&mtx);
        // no chairs free — leave
    }
}

Deadlocks

Four Necessary Conditions (Coffman Conditions)

A deadlock can only occur if all four of these hold simultaneously:

1. Mutual exclusion — at least one resource is held in a non-shareable mode.
2. Hold and wait — a process holding at least one resource is waiting to acquire additional resources held by others.
3. No preemption — a resource can only be released voluntarily by the process holding it, never forcibly taken away.
4. Circular wait — a set of processes {P0, P1, ..., Pn} exists such that P0 waits on a resource held by P1, P1 waits on P2, ..., Pn waits on P0.

Breaking any one of these four is sufficient to prevent deadlock — this is exactly the strategy behind deadlock prevention below.

Resource Allocation Graph

A directed graph with two types of nodes (processes, resources) and two types of edges: a request edge (P → R, process requests resource) and an assignment edge (R → P, resource is held by process). If the graph contains no cycle, no deadlock exists. If it contains a cycle: with single-instance resources, a cycle always means deadlock; with multi-instance resources, a cycle is necessary but not sufficient — deadlock may still be avoided if enough instances are free for some process in the cycle to finish and release its hold.

Deadlock Prevention

Attack one of the four necessary conditions structurally so deadlock becomes impossible:

Deadlock Avoidance — Banker's Algorithm Advanced

Rather than statically preventing deadlock, avoidance dynamically checks, before granting a resource request, whether granting it could still leave the system in a safe state — a state where there exists at least one order in which all processes can finish, even if each immediately requests its declared maximum. The Banker's algorithm requires each process to declare its maximum resource need in advance.

Worked example — 5 processes (P0–P4), 3 resource types (A, B, C), Available = (3, 3, 2):

Safety algorithm: find a process whose Need ≤ Available; simulate it finishing (add its Allocation back to Available); repeat.

• Available = (3,3,2). Need[P1] = (1,2,2) ≤ (3,3,2) ✓ → run P1, release (2,0,0) → Available = (5,3,2)
• Need[P3] = (0,1,1) ≤ (5,3,2) ✓ → run P3, release (2,1,1) → Available = (7,4,3)
• Need[P4] = (4,3,1) ≤ (7,4,3) ✓ → run P4, release (0,0,2) → Available = (7,4,5)
• Need[P0] = (7,4,3) ≤ (7,4,5) ✓ → run P0, release (0,1,0) → Available = (7,5,5)
• Need[P2] = (6,0,0) ≤ (7,5,5) ✓ → run P2

Safe sequence found: P1 → P3 → P4 → P0 → P2. Since a safe sequence exists, the system is in a safe state. On every new resource request, the Banker's algorithm tentatively grants it, re-runs this safety check, and rolls back the grant if no safe sequence exists — that request is made to wait instead.

Deadlock Detection & Recovery

If prevention/avoidance aren't used, the OS can instead allow deadlocks to happen, periodically run a detection algorithm (essentially the same cycle-search as the resource-allocation graph, generalized to multi-instance resources via a wait-for graph or the Banker's-style algorithm with actual allocations instead of max claims), and then recover:

• Process termination — kill all deadlocked processes (simple, wasteful), or kill them one at a time, re-checking for deadlock after each, until the cycle breaks.
• Resource preemption — forcibly take a resource from one process and give it to another, rolling that process back to a safe checkpoint. Needs care to avoid starving the same process repeatedly (must bound how many times a process can be picked as a victim).

Livelock vs Deadlock vs Starvation

Inter-Process Communication (IPC)

Because each process has its own private address space, they can't just share variables the way threads can — they need the kernel's help to exchange data. Here are the standard Unix/Linux mechanisms.

Pipes

An unnamed, unidirectional, in-kernel byte stream created with pipe(), with a read end and a write end. Only usable between processes that share a common ancestor (typically parent/child after fork()), since the file descriptors must be inherited. This is exactly what the shell's | operator uses under the hood.

int fd[2];
pipe(fd);                 // fd[0] = read end, fd[1] = write end
pid_t pid = fork();
if (pid == 0) {
    close(fd[0]);          // child writes
    write(fd[1], "hi", 2);
    close(fd[1]);
} else {
    close(fd[1]);          // parent reads
    char buf[3] = {0};
    read(fd[0], buf, 2);
    close(fd[0]);
}

Named Pipes (FIFOs)

Like a pipe, but has a name in the filesystem (created with mkfifo()), so unrelated processes can open it by path and communicate — no shared ancestry required. Still a byte stream, still unidirectional (though two FIFOs give you bidirectional communication).

Message Queues

A kernel-managed queue of discrete, typed messages (not a raw byte stream) that unrelated processes can send to and receive from by referencing the queue (System V msgget/msgsnd/msgrcv, or POSIX mq_open/mq_send/mq_receive). Messages persist in the queue even if no process is currently reading, and can be prioritized/typed for selective receive.

Shared Memory

The fastest IPC mechanism: the kernel maps the same physical memory pages into multiple processes' address spaces (shmget/shmat, or POSIX shm_open + mmap). After setup, there is zero kernel involvement in the actual data transfer — processes read/write directly, just like threads would. The tradeoff is that the kernel provides no synchronization: you must pair shared memory with an explicit synchronization mechanism (a semaphore, typically also placed in shared memory, or a named mutex) to avoid races.

Sockets

A general-purpose, bidirectional communication endpoint that works both locally (Unix domain sockets, identified by a filesystem path, avoids network stack overhead) and across a network (TCP/UDP sockets, identified by IP + port). The only IPC mechanism here that transparently extends to communicating with a process on a different machine.

Signals

Asynchronous notifications sent to a process to inform it of an event, interrupting its normal control flow to run a signal handler (or a default action if none is registered). Signals carry no data payload beyond the signal number itself (traditional signals — real-time signals add a small integer payload).

IPC Comparison Table

Memory Management

Contiguous Allocation

Each process is allocated one contiguous block of physical memory.

• Fixed partitioning — physical memory is divided into fixed-size partitions at boot; each partition holds exactly one process. Simple, but wastes memory when a process is smaller than its partition (internal fragmentation), and caps the maximum process size.
• Variable partitioning — partitions are created exactly the size of each incoming process. No internal fragmentation, but as processes come and go, memory becomes a patchwork of used/free blocks of varying sizes (external fragmentation) — allocators use strategies like first-fit, best-fit, and worst-fit to pick which free hole to use.

Fragmentation & Compaction

Compaction shuffles allocated blocks together to merge scattered free space into one large block — but it requires relocatable code (base-register relocation) and pausing/copying running processes, which is expensive. This expense is one of the main reasons paging (below) largely displaced pure contiguous allocation in general-purpose OSes: paging sidesteps external fragmentation entirely by allocating in fixed-size frames that don't need to be contiguous.

Paging

Physical memory is divided into fixed-size frames; a process's logical address space is divided into same-size pages. A per-process page table maps each virtual page number to a physical frame number — pages need not be contiguous in physical memory, which eliminates external fragmentation completely (at the cost of some internal fragmentation in the last page).

Logical address = (page number p, offset d)

physical_address = page_table[p].frame_number * FRAME_SIZE + d

// e.g. 32-bit address, 4KB pages (12-bit offset):
// virtual addr 0x004031A4
//   page number  = 0x00403 (top 20 bits)
//   offset       = 0x1A4   (bottom 12 bits)

Multilevel & Inverted Page Tables

A single flat page table for a modern 64-bit address space would be enormous (e.g. a naive single-level table could require gigabytes just for the table itself), so real systems use:

• Multilevel (hierarchical) page tables — the page table itself is paged. A top-level table's entries point to second-level tables, which point to actual frames (x86-64 uses 4 levels: PML4 → PDPT → PD → PT). Unused regions of the address space never need their lower-level tables allocated at all, saving memory. Cost: a TLB miss now requires walking multiple levels (multiple memory accesses) instead of one.
• Inverted page table — instead of one table per process, keep a single system-wide table with one entry per physical frame, storing which (process, virtual page) currently occupies it. This makes table size proportional to physical memory rather than virtual address space × number of processes, but lookups by virtual address now require a search — mitigated with a hash table keyed by (PID, virtual page).

Translation Lookaside Buffer (TLB)

A small, fast, hardware cache of recent virtual-to-physical page-table translations, located in the CPU's memory management unit (MMU). On every memory access, the MMU checks the TLB first:

• TLB hit — translation found in the TLB; physical address obtained in roughly one cycle, no page-table walk needed.
• TLB miss — translation not cached; the MMU (or, on some architectures, the OS) walks the page table (potentially multiple memory accesses for a multilevel table), then caches the result in the TLB for next time.

EAT = hit_ratio * (TLB_time + memory_time)
    + (1 - hit_ratio) * (TLB_time + page_table_walk_time + memory_time)

// e.g. TLB access = 10ns, memory access = 100ns, hit ratio = 98%
EAT = 0.98 * (10 + 100) + 0.02 * (10 + 100 + 100)
    = 0.98 * 110 + 0.02 * 210
    = 107.8 + 4.2 = 112 ns

On a context switch, TLB entries from the old process are potentially stale for the new process (different address space). Some CPUs tag TLB entries with an address-space ID (ASID on ARM, PCID on x86) so entries from multiple processes can coexist without a full flush; without that, the OS must flush the entire TLB on every context switch, causing a burst of TLB misses right after — another reason process context switches are costlier than thread switches.

Segmentation

Memory is divided along logical boundaries meaningful to the program — code segment, stack segment, heap segment, data segment — rather than fixed-size mechanical chunks. Each segment has a base and limit; a logical address is (segment number, offset). This maps naturally to how programmers/compilers think (matches the structure of a program) and allows different protection per segment (code = read/execute, stack = read/write), but reintroduces external fragmentation since segments are variable-sized, just like variable partitioning.

Segmentation with Paging

Combine both: divide the address space into logical segments, then divide each segment into fixed-size pages. This is what x86 historically did (segments containing paged memory) — you get segmentation's logical/protection benefits and paging's fragmentation-free physical allocation. Modern x86-64 in practice uses segmentation only minimally (mostly flat segments) and relies on paging for the heavy lifting, but the concept remains a common interview topic because it explains why both mechanisms exist and how they can compose.

Virtual Memory

Demand Paging

Instead of loading a process's entire address space into physical memory at start, pages are loaded lazily, only when actually referenced. Each page-table entry has a valid/invalid bit; a page not yet in memory is marked invalid. This lets processes run with a memory footprint far smaller than their full virtual address space, and lets total virtual memory across all processes exceed physical RAM.

Page Faults

Accessing a page marked invalid triggers a page fault trap into the kernel. The handler:

1. Checks whether the access is actually valid (page exists on disk/swap but isn't loaded) or truly illegal (segmentation fault) — checked against the process's valid virtual memory regions.
2. If valid: find a free physical frame (or evict one via a page replacement algorithm if none is free).
3. Schedule a disk read to load the page's contents into that frame (this is why a page fault is orders of magnitude slower than a TLB miss — it involves actual disk/SSD I/O).
4. Update the page table (mark valid, set frame number) and the TLB.
5. Restart the faulting instruction.

Page Replacement Algorithms Advanced

When physical memory is full and a new page must be brought in, the OS must evict an existing page. Worked example — reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 frames:

FIFO (evict the oldest-loaded page, shown above): 9 page faults with 3 frames. See Belady's Anomaly for what happens with 4 frames on this same string.

• FIFO — evicts the page that has been in memory the longest, regardless of usage. Simple (just a queue), but can behave counter-intuitively (Belady's anomaly).
• Optimal (OPT / Bélády's algorithm) — evicts the page that won't be used for the longest time in the future. Provably minimizes page faults, but requires knowing the future reference string, so it's only usable as a theoretical benchmark to compare other algorithms against.
• LRU (Least Recently Used) — evicts the page that hasn't been used for the longest time in the past, as an approximation of OPT (relies on temporal locality — recently used pages are likely to be used again soon). Exact LRU needs a timestamp or stack update on every memory reference, which is expensive in hardware, so real systems use approximations:
  • Clock / Second-Chance algorithm — frames arranged in a circular list with a "use" (reference) bit set by hardware on access. A clock hand sweeps looking for a frame with use-bit = 0 to evict; if it finds use-bit = 1, it clears the bit and gives that page a "second chance," advancing the hand. Approximates LRU cheaply — this is what most real kernels (including Linux's variant, the "two-list" active/inactive LRU-ish scheme) actually implement, since true LRU bookkeeping is too costly at scale.

Belady's Anomaly

Counter-intuitively, for some page-replacement algorithms (FIFO being the classic example), adding more physical frames can increase the number of page faults, even though intuition says more memory should only help. Running the same reference string (1,2,3,4,1,2,5,1,2,3,4,5) with FIFO and 4 frames instead of 3:

More frames, more faults — the anomaly. LRU and OPT never exhibit this anomaly; they belong to a class called stack algorithms, where the set of pages held with n frames is always a subset of the set held with n+1 frames, which mathematically guarantees faults can only decrease (or stay the same) as frames increase. FIFO is not a stack algorithm, which is precisely why it can misbehave this way.

Thrashing & Working Set Model

Thrashing occurs when a process (or the system as a whole) spends more time servicing page faults than doing actual useful work — typically because the degree of multiprogramming is too high relative to available physical memory, so every process's pages keep getting evicted by other processes before they're reused, causing a cascading storm of faults. CPU utilization actually drops as thrashing worsens, which historically caused OSes to (wrongly) respond by admitting more processes to raise utilization — making thrashing worse.

The working set model is the standard fix: define a process's working set as the set of pages it has referenced in the last Δ (delta) time units. The OS tracks each process's working set size and only keeps a process resident if the sum of all working sets fits in physical memory; otherwise, it suspends (swaps out) some processes entirely via the medium-term scheduler, rather than letting everyone starve for frames simultaneously.

Copy-on-Write

Already covered in depth under Process Creation and revisited at the page-table level in Advanced Topics — the short version: pages are shared read-only between parent and child after fork(), and a private copy is made lazily, only on the first write, via a page fault.

Memory-Mapped Files

mmap() maps a file (or device) directly into a process's virtual address space, so file I/O becomes ordinary memory reads/writes instead of explicit read()/write() syscalls. The kernel uses the exact same demand-paging machinery: accessing an unmapped page of the file triggers a page fault, and the kernel transparently loads that page from disk into the page cache and maps it in. Benefits: no need to copy data between kernel buffers and user buffers (the page cache is the mapped memory — zero-copy), and multiple processes mapping the same file share the same physical pages automatically. This is also how shared libraries (.so/.dll) are loaded, and how shared memory (shm_open + mmap) is implemented under the hood.

File Systems

File Allocation Methods

Unix-family file systems (ext2/3/4, etc.) use indexed allocation via inodes: a fixed-size inode holds file metadata (permissions, timestamps, size) plus a small number of direct block pointers, one single-indirect pointer (points to a block full of pointers), one double-indirect (points to a block of pointers to blocks of pointers), and one triple-indirect — letting a compact, fixed-size inode address files ranging from a few bytes to many terabytes.

Free Space Management

• Bitmap — one bit per block, 1 = allocated, 0 = free. Compact, and finding contiguous free runs is a fast bit-scan, but the bitmap itself must be kept in memory for performance and persisted carefully.
• Linked list of free blocks — free blocks are chained together; no extra structure size cost, but no way to quickly find a large contiguous run.
• Grouping — the first free block stores addresses of the next N free blocks (one of which itself stores the addresses of the next N, and so on), enabling fast retrieval of many free blocks at once.
• Counting — since free blocks often come in contiguous runs, store (start block, count of contiguous free blocks) pairs instead of one entry per block — much more compact for typical fragmentation patterns.

Directory Structures

Journaling File Systems

A crash (power loss, kernel panic) in the middle of a multi-step metadata update (e.g. creating a file: allocate inode, write directory entry, update free-space bitmap) can leave the file system in an inconsistent state. Journaling borrows the write-ahead-log idea from databases: before making the actual changes, the file system writes a description of the intended changes to a dedicated journal/log area. If the system crashes mid-update, on reboot the file system replays the journal to either complete or cleanly roll back the interrupted operation, rather than needing a slow full-disk consistency scan (like old fsck on non-journaled ext2).

• Metadata-only journaling (e.g. ext3/ext4 default ordered mode) — only file-system metadata (inodes, bitmaps, directory entries) is journaled; actual file data is written directly. Fast, protects structural consistency, but data written right before a crash may still be lost/incomplete.
• Full (data) journaling — both metadata and data are journaled. Strongest consistency guarantee, but roughly doubles the write I/O (data is written once to the journal, once to its final location).

Disk Scheduling Algorithms Advanced

Worked example — request queue 98, 183, 37, 122, 14, 124, 65, 67, disk head starting at cylinder 53, cylinders range 0–199 (assume the head moves toward higher-numbered cylinders first where direction matters):

SSTF minimizes movement for this specific snapshot but can starve requests far from the current hotspot if nearby requests keep arriving. SCAN/LOOK variants bound the worst-case wait (a request is serviced at most within one full sweep), which is why real disk schedulers (and the conceptually similar Linux I/O elevator schedulers) favor SCAN/LOOK-family algorithms over pure SSTF. C-SCAN/C-LOOK give more uniform wait times than SCAN/LOOK because they treat the disk as a circular list (no double-density of service near the reversal point).

Concurrency Primitives & Modern Concepts

Spinlocks vs Mutexes Intermediate

Both provide mutual exclusion, but they handle contention differently:

Atomic Operations & Compare-And-Swap

An atomic operation completes as a single indivisible step from every other thread/core's point of view — no other thread can observe it half-done. Modern CPUs provide hardware-level atomic instructions (e.g. x86 LOCK-prefixed instructions, ARM LDXR/STXR) that lock-free algorithms and languages' atomic types build on. The most important one is Compare-And-Swap (CAS):

#include <atomic>

std::atomic<int> counter{0};

void lock_free_increment() {
    int expected = counter.load();
    int desired;
    do {
        desired = expected + 1;
        // atomically: if counter == expected, set counter = desired,
        // and return true. Otherwise, load the *current* value into
        // `expected` and return false, so the loop retries.
    } while (!counter.compare_exchange_weak(expected, desired));
}

CAS(address, expected, new_value) atomically checks whether the memory at address still equals expected; if so, it writes new_value and reports success, otherwise it does nothing and reports failure (usually also returning the current value so the caller can retry). This single primitive is powerful enough to implement essentially all lock-free data structures — it's the hardware foundation everything else in this section builds on.

Memory Barriers & Memory Model Basics

Both compilers and CPUs reorder instructions for performance, as long as the reordering is invisible to a single-threaded observer. Across threads, though, this reordering can become visible and break assumptions — a classic case: thread A writes data = 42; ready = true;, thread B reads if (ready) use(data); — without ordering guarantees, the CPU or compiler could make ready = true visible to thread B before data = 42 is, and B would read a stale/garbage data.

A memory barrier (fence) is an instruction that constrains this reordering — e.g. "no load/store after this point may be reordered before this point." C++'s std::atomic exposes this via memory ordering parameters:

std::mutex internally establishes acquire/release semantics around lock/unlock, which is exactly why plain int shared data protected by a mutex is safe without any explicit atomics — the mutex's lock/unlock already act as the necessary fences.

False Sharing

CPU caches operate on fixed-size cache lines (commonly 64 bytes), not individual variables. If two threads on different cores frequently write to two different variables that happen to sit on the same cache line, the cache-coherence protocol (e.g. MESI) will bounce that line between cores' caches on every write from either side — even though the threads aren't logically sharing any data. This looks exactly like real lock contention in a profiler, but there's no actual synchronization primitive involved.

struct Counters {
    std::atomic<long> a;   // written by thread 1
    std::atomic<long> b;   // written by thread 2 — likely same cache line as `a`!
};

// Fix: pad so each counter owns its own cache line
struct alignas(64) PaddedCounter {
    std::atomic<long> value;
    char padding[64 - sizeof(std::atomic<long>)];
};

Lock-Free Data Structures

A lock-free algorithm guarantees system-wide progress: at least one thread always completes its operation in a bounded number of steps, even if other threads are paused, crash, or are descheduled indefinitely at arbitrary points. This is a much stronger guarantee than "no explicit locks used" — it's a formal progress property. Contrast with:

• Obstruction-free — a thread makes progress only if it eventually runs without interference from other threads (weakest).
• Lock-free — the system as a whole always makes progress, though any individual thread could theoretically be starved forever by other threads winning every CAS race.
• Wait-free — every individual thread is guaranteed to complete in a bounded number of steps, regardless of what other threads do (strongest, hardest to achieve).

A canonical building block is a lock-free stack using CAS on the head pointer:

template <typename T>
struct LockFreeStack {
    struct Node { T value; Node* next; };
    std::atomic<Node*> head{nullptr};

    void push(T v) {
        Node* n = new Node{v, head.load()};
        while (!head.compare_exchange_weak(n->next, n)) {
            // n->next was updated to the current head on failure; retry
        }
    }

    bool pop(T& out) {
        Node* old_head = head.load();
        while (old_head &&
               !head.compare_exchange_weak(old_head, old_head->next)) {
            // retry with the updated old_head on failure
        }
        if (!old_head) return false;
        out = old_head->value;
        delete old_head;   // unsafe without a reclamation scheme — see note below
        return true;
    }
};

The delete above is a simplification that's actually unsafe in a truly concurrent setting — a thread could still be reading old_head when another thread pops and frees it (the ABA problem and use-after-free hazards). Production lock-free code needs a memory reclamation scheme (hazard pointers, epoch-based reclamation, or RCU — see RCU) to safely free memory that other threads might still be dereferencing.

std::mutex vs std::atomic in Practice

Advanced & Rare Topics

Topics in this section go beyond what most standard courses cover — useful for senior/staff-level systems interviews, or simply to stand out.

Real-Time Scheduling: EDF & RMS Advanced

Real-time scheduling cares about deadlines, not just fairness/throughput.

• Rate Monotonic Scheduling (RMS) — a static-priority algorithm: each periodic task gets a fixed priority inversely proportional to its period (shorter period = higher priority). Optimal among static-priority algorithms. A well-known sufficient (not necessary) schedulability test for n tasks: total CPU utilization ≤ n(2^(1/n) − 1) (approaches ~69% as n grows).
• Earliest Deadline First (EDF) — a dynamic-priority algorithm: at any instant, run whichever ready task has the nearest absolute deadline. Provably optimal among all scheduling algorithms (static or dynamic) for uniprocessor systems — if any algorithm can schedule a task set to meet all deadlines, EDF can too. It can achieve up to 100% CPU utilization (vs RMS's ~69% worst-case bound), but priorities change dynamically at runtime, which adds bookkeeping overhead and makes worst-case analysis and implementation trickier than RMS's fixed priorities.

NUMA Architecture

On multi-socket systems, each CPU socket has its own local bank of physical RAM ("Non-Uniform Memory Access"). Any CPU can access any RAM, but accessing memory attached to a remote socket is significantly slower (extra hop over the inter-socket interconnect, e.g. Intel's UPI or AMD's Infinity Fabric) than accessing its own local memory. This has direct scheduling and memory-allocation implications: the OS scheduler tries to keep a thread running on the same NUMA node as the memory it allocated ("NUMA affinity"), and migrating a thread across nodes can silently tank performance even though the CPU itself is idle and "available." High-performance systems often pin threads to a NUMA node and allocate memory with node-local policies (Linux numactl, mbind()) rather than trusting the default scheduler to get this right under load.

Read-Copy-Update (RCU) Advanced

RCU is a synchronization mechanism (heavily used in the Linux kernel) optimized for workloads that are overwhelmingly read-heavy with occasional writes. The core idea: readers access shared data with zero synchronization overhead — no locks, no atomic operations, just a plain pointer dereference — while writers create a new copy of the data, modify the copy, and then atomically swap a single pointer to publish it. Old readers that grabbed the pointer before the swap keep safely reading the old version until they finish; the old version is only freed after the kernel proves no reader could still hold a reference to it (via a "grace period" — waiting until every CPU has passed through a quiescent state, guaranteeing no in-progress RCU read-side critical section from before the update is still running).

This trades write cost (copy + wait for grace period + free) for essentially free reads — the opposite tradeoff of a reader-writer lock, which adds overhead to every reader to protect against writers. RCU shines in kernel data structures like routing tables that are read millions of times per second but updated rarely.

fork() + Copy-on-Write at the Page-Table Level

Revisiting fork() at the mechanism level: when fork() is called, the kernel does not copy any physical page frames. Instead it:

1. Allocates a new page table for the child, copying the parent's page-table entries (not the underlying data) — child and parent's entries now point at the same physical frames.
2. Clears the writable bit on every page-table entry (both parent's and child's) that was previously writable, and marks the underlying physical page as COW (tracked via a reference count on the frame, incremented to 2).
3. Returns from the fork; both processes now run with identical, shared, read-only-marked memory.
4. The first time either process writes to one of these pages, the CPU raises a page fault because the page-table entry says read-only even though the process's logical permissions say writable. The kernel's fault handler recognizes this specific case (COW fault, distinguishable from a real permissions violation via a bit tracked per-VMA/mapping), allocates a fresh physical frame, copies the page's contents into it, updates only the faulting process's page-table entry to point at the new frame with write permission restored, and decrements the original frame's reference count.
5. If the reference count on the original frame drops to 1, the remaining process's entry can be marked writable again directly (no more sharing, no need to keep faulting).

This is why fork() is fast even for processes with huge address spaces — the cost is proportional to page-table size (a few memory pages' worth of entries), not to actual memory content size, and if the child execs immediately (the overwhelmingly common case), zero data pages are ever duplicated.

Containers vs Virtual Machines Advanced

Both provide isolation, but at fundamentally different layers:

Docker-style containers rely on two Linux kernel mechanisms:

• Namespaces — restrict what a process group can see. Each namespace type virtualizes one kind of global kernel resource: pid (process sees itself as PID 1, can't see host processes), mnt (its own filesystem mount view/root), net (its own network interfaces, routing table, ports), uts (its own hostname), ipc (its own IPC/shared-memory namespace), user (its own UID/GID mapping — root inside the container can map to an unprivileged UID outside).
• cgroups (control groups) — restrict what a process group can use: CPU shares/quotas, memory limits (with OOM-killing on breach), block I/O bandwidth, and (cgroup v1) device access. This is how Docker enforces --memory and --cpus limits.

A container is, under the hood, just an ordinary Linux process (visible in the host's own ps output with a normal host PID) that happens to have been launched inside a set of namespaces and attached to a cgroup — there's no separate "container kernel" or hypervisor involved, which is exactly why containers are so much lighter than VMs, and also exactly why a kernel-level exploit can potentially escape a container in a way it can't escape a VM.

Interrupt Handling: Top & Bottom Halves

When a hardware device (disk, NIC, keyboard) needs attention, it raises a hardware interrupt, which the CPU services by jumping to an Interrupt Service Routine (ISR) — but ISRs run with (some) interrupts disabled and must be extremely fast, or the system becomes unresponsive to other events. Linux (and most modern kernels) splits interrupt handling into two halves:

• Top half — the actual hardware interrupt handler. Does the absolute minimum required immediately (e.g. acknowledge the interrupt to the device, copy a small amount of critical data), then schedules the rest of the work to run later and returns as fast as possible.
• Bottom half — the deferred, larger chunk of work, run later with interrupts enabled (so it doesn't block other hardware from interrupting). Linux implements this via softirqs (static, compiled-in, used for the highest-throughput paths like networking), tasklets (built on softirqs, dynamically registerable, guaranteed not to run the same tasklet concurrently on two CPUs), and workqueues (run in normal (schedulable, can sleep) process context, for bottom-half work that needs to block, e.g. on a mutex or I/O).

This split is why a network card can sustain extremely high packet rates without freezing the rest of the system — the top half does only the minimal urgent work per packet, and the bulk of protocol processing happens in a softirq that can be preempted by the next top-half interrupt if needed.

Syscall Overhead & vDSO

Every system call costs a user→kernel→user mode transition — saving/restoring registers, potential TLB and cache effects, and (on x86, historically) the cost of the syscall/sysenter instruction itself, further inflated post-Spectre/Meltdown by mitigations like KPTI (kernel page-table isolation, which forces an extra page-table switch on every syscall to prevent user-space from speculatively reading kernel memory). For very frequently called, read-only-ish syscalls — most notably gettimeofday()/clock_gettime() — this overhead is disproportionate to the actual work (reading a counter).

The Linux kernel's answer is the vDSO (virtual Dynamic Shared Object): the kernel maps a small, read-only page of actual kernel code (plus kernel-updated data like the current time) directly into every process's address space. Calling clock_gettime() through glibc transparently calls into this mapped vDSO code — a plain function call in user space, no trap, no mode switch at all — which reads the kernel-maintained time data directly. This turns a syscall that would otherwise cost hundreds of nanoseconds into one costing a few nanoseconds, for exactly the handful of syscalls where it's safe (no side effects on kernel state, purely observational).

Priority Inversion & Priority Inheritance Advanced

Priority inversion occurs when a high-priority task is indirectly blocked by a low-priority task, because the low-priority task holds a lock the high-priority task needs — but the situation gets worse when an unrelated, medium-priority task preempts the low-priority lock holder (since the scheduler sees no reason not to, the medium task isn't waiting on anything), starving the high-priority task indefinitely even though it's "more important" than both.

The priority inheritance protocol is the standard fix: when a high-priority task blocks waiting for a lock held by a lower-priority task, the lock holder temporarily inherits the waiting task's higher priority for as long as it holds the lock — preventing any merely-medium-priority task from preempting it in the meantime. Once it releases the lock, its priority reverts to normal. This bounds the priority-inversion delay to the length of one critical section, instead of potentially unbounded time.

Practical Coding

Common OS-flavored coding interview exercises, worked in full C++.

Thread-Safe LRU Cache in C++ Advanced

A classic systems-coding question combining a data-structure design (doubly linked list + hash map for O(1) get/put) with correct locking. The linked list tracks recency order (most-recently-used at the front); the hash map gives O(1) lookup from key to the corresponding list node.

#include <unordered_map>
#include <mutex>
#include <list>
#include <optional>

template <typename K, typename V>
class LRUCache {
public:
    explicit LRUCache(size_t capacity) : capacity_(capacity) {}

    std::optional<V> get(const K& key) {
        std::lock_guard<std::mutex> lock(mtx_);
        auto it = index_.find(key);
        if (it == index_.end()) return std::nullopt;

        // Move the accessed node to the front (most recently used)
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }

    void put(const K& key, const V& value) {
        std::lock_guard<std::mutex> lock(mtx_);
        auto it = index_.find(key);
        if (it != index_.end()) {
            it->second->second = value;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }

        if (items_.size() >= capacity_) {
            auto& lru = items_.back();       // least recently used
            index_.erase(lru.first);
            items_.pop_back();
        }

        items_.emplace_front(key, value);
        index_[key] = items_.begin();
    }

private:
    using ListType = std::list<std::pair<K, V>>;
    size_t capacity_;
    ListType items_;                                     // front = MRU, back = LRU
    std::unordered_map<K, typename ListType::iterator> index_;
    std::mutex mtx_;
};

Producer-Consumer with std::mutex + std::condition_variable Intermediate

#include <queue>
#include <mutex>
#include <condition_variable>
#include <thread>
#include <iostream>

template <typename T>
class BoundedQueue {
public:
    explicit BoundedQueue(size_t capacity) : capacity_(capacity) {}

    void push(T item) {
        std::unique_lock<std::mutex> lock(mtx_);
        not_full_.wait(lock, [this] { return queue_.size() < capacity_ || done_; });
        if (done_) return;
        queue_.push(std::move(item));
        lock.unlock();
        not_empty_.notify_one();
    }

    bool pop(T& out) {
        std::unique_lock<std::mutex> lock(mtx_);
        not_empty_.wait(lock, [this] { return !queue_.empty() || done_; });
        if (queue_.empty()) return false;   // done_ and drained
        out = std::move(queue_.front());
        queue_.pop();
        lock.unlock();
        not_full_.notify_one();
        return true;
    }

    void shutdown() {
        {
            std::lock_guard<std::mutex> lock(mtx_);
            done_ = true;
        }
        not_empty_.notify_all();
        not_full_.notify_all();
    }

private:
    std::queue<T> queue_;
    size_t capacity_;
    bool done_ = false;
    std::mutex mtx_;
    std::condition_variable not_full_;
    std::condition_variable not_empty_;
};

int main() {
    BoundedQueue<int> q(5);

    std::thread producer([&] {
        for (int i = 0; i < 20; ++i) q.push(i);
        q.shutdown();
    });

    std::thread consumer([&] {
        int value;
        while (q.pop(value)) {
            std::cout << "consumed: " << value << "\n";
        }
    });

    producer.join();
    consumer.join();
}

Implementing a Counting Semaphore

C++20 added std::counting_semaphore directly, but interviewers often want you to build one from a mutex + condition variable to prove you understand what a semaphore actually is underneath.

#include <mutex>
#include <condition_variable>

class CountingSemaphore {
public:
    explicit CountingSemaphore(int initial_count) : count_(initial_count) {}

    // P() / wait() / acquire()
    void acquire() {
        std::unique_lock<std::mutex> lock(mtx_);
        cv_.wait(lock, [this] { return count_ > 0; });
        --count_;
    }

    // V() / signal() / release()
    void release(int n = 1) {
        {
            std::lock_guard<std::mutex> lock(mtx_);
            count_ += n;
        }
        if (n == 1) cv_.notify_one();
        else        cv_.notify_all();
    }

    bool try_acquire() {
        std::lock_guard<std::mutex> lock(mtx_);
        if (count_ > 0) { --count_; return true; }
        return false;
    }

private:
    std::mutex mtx_;
    std::condition_variable cv_;
    int count_;
};

// Usage: a binary semaphore (count_ starts at 1) behaves like a mutex,
// except any thread may call release() -- there's no ownership check,
// which is the key distinction discussed under Mutex vs Semaphore.

References & Further Reading

• Operating Systems: Three Easy Pieces (OSTEP) — free online textbook
• GeeksforGeeks — Operating Systems
• The Linux Kernel Documentation (kernel.org)
• Linux Kernel Docs — RCU (Read-Copy-Update)
• cppreference — Thread support library (std::mutex, std::condition_variable, std::atomic)
• man7.org — fork(2)
• man7.org — signal(7)
• man7.org — namespaces(7)
• Docker Documentation — Get Started Overview
• Wikipedia — Completely Fair Scheduler (Linux CFS)