Operating systems

Operating systems

Virtual memory, paging, the page cache, and Linux I/O models: blocking calls, epoll, io_uring, and event-loop backpressure.

• Linux I/O Models & Event Loops

  6 studies
  1. 1.Linux I/O Models - Blocking, Non-Blocking, epoll, io_uring & Event LoopsEvery server spends most of its life **waiting**: for a client to send bytes, for a disk, for a downstream service. An I/O model is simply the answer to "what does a thread do while it waits?". With **blocking I/O** the thread sleeps inside `read()` and you need one thread per in-flight connection. With **non-blocking I/O + readiness multiplexing** (`select`/`poll`/`epoll`/`kqueue`) one thread asks the kernel "which of my 50,000 sockets are ready?" and only touches those. With **completion-based I/O** (`io_uring` on Linux, IOCP on Windows) you hand the kernel the whole operation and buffer and collect results later. Runtimes such as Node/libuv, Nginx, Netty, Tokio and the Go netpoller are all built from these pieces; knowing which one sits under your framework explains its scaling limits, its failure modes ("someone blocked the event loop") and its tuning knobs.
  2. 2.File Descriptors & Non-Blocking I/O - Syscalls, EAGAIN, Partial Writes & FramingOn Unix, a socket, pipe, file, eventfd or timerfd is a **file descriptor (fd)**: a small integer indexing a per-process table that points at a kernel object. Every byte you move crosses the user/kernel boundary through a **syscall** (`read`, `write`, `recv`, `send`, `accept`). In **blocking** mode, `read()` on an empty socket puts your thread to sleep until data arrives. With `O_NONBLOCK` set (via `fcntl` or `SOCK_NONBLOCK`), the same call returns immediately with `-1` and `errno = EAGAIN` (also spelled `EWOULDBLOCK`). Non-blocking mode alone is useless (you'd spin); it's the building block that readiness APIs like epoll sit on. Two consequences every server must handle: **partial writes** (the kernel accepted only part of your buffer) and **arbitrary read boundaries** (TCP is a byte stream, so you need framing).
  3. 3.select vs poll vs epoll vs kqueue - Readiness, Level vs Edge Triggering & Thundering HerdsReadiness multiplexing lets one thread wait on many fds. **`select`** (1983, BSD) passes bitmaps of fds into the kernel on every call, is capped at `FD_SETSIZE` (1024 on glibc), and both kernel and app scan all of them. **`poll`** removes the cap with an array of `pollfd`, but still copies and scans the whole set every call: O(watched). **`epoll`** (Linux 2.6) keeps the interest set inside the kernel (`epoll_ctl` once per fd) and `epoll_wait` returns only the ready ones: O(ready). **`kqueue`** (FreeBSD/macOS) is the BSD equivalent and also handles timers, signals, process and file events through one API. On top of that you choose **level-triggered** (keep telling me while data remains, the default and the safest) or **edge-triggered** (`EPOLLET`, tell me once per change, and you must drain to `EAGAIN`). At multi-thread scale you also have to handle the **thundering herd** and accept distribution.
  4. 4.io_uring & Zero-Copy - Submission/Completion Rings, Batching, sendfile & splice**io_uring** (Linux 5.1, 2019, by Jens Axboe) is a completion-based I/O interface. The app and kernel share two ring buffers in memory: the **submission queue (SQ)** where you write operation descriptors (SQEs: read this fd into this buffer, accept, send, fsync, open...), and the **completion queue (CQ)** where the kernel posts results (CQEs with your `user_data` tag and a result code). One `io_uring_enter()` syscall can submit hundreds of operations; with **SQPOLL** a kernel thread polls the SQ and you may need no syscall at all. Unlike epoll it works for **regular files** as well as sockets, and supports registered files and fixed buffers to cut per-op overhead. The cost: a large, fast-moving kernel attack surface, so many platforms restrict it. Next to it sit the classic **zero-copy** tools: `sendfile`, `splice`, `MSG_ZEROCOPY`, and `mmap`, which reduce copies rather than syscalls.
  5. 5.Reactor vs Proactor - How libuv, Nginx, Netty, Tokio & the Go Netpoller WorkTwo design patterns turn OS I/O primitives into a programming model. A **reactor** waits for *readiness* (epoll, kqueue, select) and dispatches to a handler that then performs the non-blocking read or write itself: "socket 7 is readable, go read it". A **proactor** starts an *operation* and dispatches the *completion*: "your read on socket 7 finished, here are 4,096 bytes". Linux servers are mostly reactors because epoll is readiness-based; Windows IOCP and Linux io_uring are completion-based, so runtimes built on them are proactors. Every major runtime is some arrangement of these: **libuv** (Node) is a single-threaded reactor plus a threadpool that fakes completions for files; **Nginx** runs one reactor per worker process; **Netty** runs one reactor per event-loop thread; **Tokio** runs reactor-driven futures on a work-stealing pool; **Go's netpoller** hides a reactor under goroutines so your code looks blocking.
  6. 6.Thread-per-Connection vs Event Loop vs Async Tasks - Blocking the Loop, C10K & BackpressureThe concurrency model you choose sets where your server breaks. **Thread-per-connection** breaks on memory and context switches as concurrent connections grow, and on pool exhaustion when a dependency slows down. **Event loops** break when anything blocks the loop: a CPU-heavy JSON parse, a sync file read, a blocking DNS lookup, a regex with catastrophic backtracking. All one loop's connections stall together and timers (including health checks) fire late. **Async tasks and green threads** (Tokio, asyncio, goroutines, virtual threads) remove the per-connection thread cost but not the need for **backpressure**: if you accept or read faster than you can process or write, queues and buffers grow until memory runs out. The senior answer is always the same three moves: keep the I/O path non-blocking, offload CPU work to a bounded pool, and propagate backpressure (bounded queues, `write()`-returns-false / `drain`, stop reading, shed load at the edge).

• Virtual Memory — Paging, Swapping & Caches

  6 studies
  1. 1.Virtual Memory — Paging, Swapping, and Why Caches ExistEvery cache you will ever design is a smaller, faster copy of something bigger and slower, plus a rule for what to throw away. Virtual memory is the original version of that idea, built into the CPU and the kernel. A process sees a huge private address space; the kernel and MMU map small fixed-size pages of it onto physical RAM frames, keep a hot subset resident, and push the rest to disk or never materialize it at all. Once you understand page tables, the TLB, page faults, the page cache, eviction (CLOCK and working sets), huge pages, NUMA, and overcommit, three things you touch daily stop being magic: why Redis and a database buffer pool behave the way they do on a real box, why a container gets OOM-killed when the dashboard said "plenty of memory", and why vLLM chose to manage KV cache with block tables that look exactly like page tables. This hub gives the mental model and the map; five sibling lessons go deep.
  2. 2.Address Spaces — Paging, Segmentation, Paged Segmentation, and the TLBAn address space is a contract: the process sees contiguous private addresses, the hardware and kernel decide where the bytes actually live. Segmentation splits memory into variable-size logical regions with a base and a limit; paging splits it into fixed-size pages mapped through a page table; paged segmentation does both. Paging won because fixed-size units kill external fragmentation and make sharing, swapping, and lazy allocation trivial, but it costs page-table memory and a translation on every access. The TLB is the cache that makes that translation nearly free, and its limited reach is why random access over large heaps is slower than the big-O suggests. This lesson builds both translators in code and ends with the interview staples: multi-level tables, TLB shootdowns, ASIDs and PCIDs, and why these ideas reappear in database page ids and LLM block tables.
  3. 3.Faults, Swapping, and Thrashing — Working Set and the ClockA page fault is not an error; it is how the kernel implements laziness. Minor faults map a page that is already in RAM or hand out a zeroed frame in about a microsecond. Major faults read from disk or swap and cost tens of microseconds on NVMe or milliseconds on spinning disk, which is three to five orders of magnitude slower than a DRAM access. Old systems swapped whole processes; modern ones page on demand and reclaim individual pages with an approximation of LRU called CLOCK (Linux uses active and inactive lists, and newer kernels MGLRU). When the combined working sets of running processes exceed RAM, the system spends its time faulting instead of working: thrashing. This lesson builds FIFO, LRU, CLOCK, and Belady's OPT, shows the thrashing cliff, explains copy-on-write fork (Redis BGSAVE), and maps every idea onto cache design and KV-cache preemption.
  4. 4.The Page Cache — OS Cache vs Application Cache vs Buffer PoolLinux caches file contents in otherwise idle RAM: the page cache. Every buffered read and write, every mmap of a file, and every database that does not bypass it goes through this cache, keyed by file and offset and evicted by kernel policy. On top of it you usually stack more caches: a database buffer pool keyed by page id, an in-process LRU keyed by object, a shared Redis keyed by business identity, a CDN keyed by URL, and in LLM serving a KV cache keyed by token prefix. Each layer exists because it knows something the layer below cannot: object boundaries, transaction visibility, invalidation events, network locality, or the fact that a KV block can be recomputed. Stacking them carelessly double-caches the same bytes, wastes RAM, and lets one layer's eviction sabotage another. This lesson explains the read and write paths, mmap versus read versus direct I/O, why Postgres and InnoDB made opposite choices, why Redis is not the page cache, and how to pick the layer for each kind of data.
  5. 5.Scaling Memory — Huge Pages, NUMA, Bandwidth, and OvercommitMemory does not scale by adding gigabytes alone. Four walls appear as working sets grow. First, translation: with 4 KiB pages the TLB covers only a few megabytes, so large random-access heaps pay page walks constantly; huge pages (2 MiB, 1 GiB) multiply TLB reach but bring compaction stalls, bloat, and copy-on-write amplification. Second, locality: multi-socket servers are NUMA, so memory attached to the other socket is slower and its interconnect is shared. Third, bandwidth: many workloads, including LLM decode, are limited by bytes per second, not FLOPs or cores, so the fix is moving fewer bytes. Fourth, promises: Linux overcommits virtual memory, and when the bet fails the OOM killer picks a victim, often your largest cache. This lesson covers each wall with tradeoff tables, a TLB-reach and bandwidth calculator, an overcommit simulator, and the container and Kubernetes angle.
  6. 6.From Pages to KV Cache — Block Tables, Fragmentation, and Prefix CacheThis lesson is the OS lens on LLM KV cache, not a second PagedAttention tutorial. The existing lesson on PagedAttention teaches the block table, the attention kernel, and continuous batching; read it for engine internals. Here we take the vocabulary of the previous lessons and apply it: contiguous per-request KV reservation is segmentation and fails the same way, with internal waste from worst-case sizing and external fragmentation from churn; fixed-size KV blocks with a per-sequence block table are paging; block size is the page-size tradeoff; prefix caching is a page cache keyed by token content with refcounts and LRU; preemption by swapping blocks to CPU or recomputing them is demand paging where the backing store can be computation. We quantify fragmentation, build a prefix block cache that evicts like the kernel does, and work through swap versus recompute and KV offload tiers. The goal is to answer why PagedAttention uses pages, in OS terms, and to know exactly where the analogy breaks.