Three doorbells, one front desk
By now you have met every way the CPU can be pulled out of ordinary user code and into the kernel — but you met them one at a time, in different rungs, so it is worth gathering them on one table. There are exactly three. A device finishes its work and rings an interrupt: that is the doorbell, asynchronous and involuntary, arriving at a moment your program did not choose. Your own program deliberately asks the kernel for a service with an system call like "read(fd, buf, n)", which the hardware delivers as a trap: synchronous and entirely voluntary, the program reaching out on purpose. And an instruction goes wrong — divide by zero, touch an illegal address, hit a page fault — which raises an exception: synchronous like a trap, but involuntary like an interrupt, an accident the program never asked for.
Here is the unifying idea that ties this whole rung together: the kernel does not build three separate machines for these three events. It builds one. All three are funnelled through the same lookup table you met with interrupts — on x86 that is the interrupt descriptor table, the IDT — where each event carries a small vector number and the table turns that number directly into the address of the routine that handles it. A timer interrupt might be vector 32; a page-fault exception is vector 14; the system-call trap is its own dedicated vector. One front desk, one directory taped inside it, three kinds of visitor. The CPU does not care why it was summoned; it just reads the vector, indexes the table, switches into kernel mode, and jumps.
synchronous? voluntary? example ---------+--------------+-------------+--------------------------- interrupt| no | no | disk done, key pressed, timer trap | yes | yes | read(fd, buf, n) (system call) exception| yes | no | divide-by-zero, page fault all three -> vector number -> index the IDT -> handler address
Synchronous vs asynchronous, and why it matters
That little table hides a distinction worth slowing down on, because it changes how the kernel must behave. A trap and an exception are synchronous: they are caused by the instruction currently executing, so they happen at a precise, reproducible point — run the same code with the same inputs and the same trap fires at the same spot every time. An interrupt is asynchronous: it is caused by the outside world, so it can land between any two instructions, and re-running your program will not reproduce its exact timing. This is the same honest distinction you have been carrying since the concurrency rung — interleaving is unpredictable, and the kernel must be correct no matter where an asynchronous event slips in.
Why does the synchronous/asynchronous split matter so much in practice? Because of restartability and blame. When an exception is synchronous and precise, the kernel knows exactly which instruction caused it, can fix the problem (fetch the missing page), and restart that very instruction — the quiet miracle behind demand paging. An asynchronous interrupt blames no instruction in particular; the program was innocent, so the kernel must save its state untouched, do the device's bidding, and return as if the program blinked and missed nothing. The two even differ in masking: the CPU can temporarily disable (mask) most interrupts when it is in a delicate section, telling the doorbell "hold on a moment," but it cannot mask a divide-by-zero — the instruction has already gone wrong, and there is no holding that back.
Now flip the question: the kernel needs memory too
Here is a thought that catches most people off guard. While handling an interrupt or a page fault, the kernel constantly needs to allocate memory of its own — a fresh buffer for an arriving network packet, a new entry in the page table, a structure to describe a file the kernel just opened. But the kernel cannot phone a friend: there is no higher authority to ask for memory, no malloc handed down from above. The kernel is the building manager, and the building manager keeps the only set of keys to the storeroom. So the kernel must run its own allocators, in its own address space, fast enough to keep up with thousands of interrupts a second. The rest of this guide is about those allocators — and the surprise is that one is not enough.
Why two? Because kernel memory requests come in two wildly different shapes, and a single tool serves neither well. Some requests are big and page-sized or larger: "give me four contiguous pages for a new I/O buffer." Others are tiny and fantastically frequent: "give me one 96-byte structure to describe this process," repeated millions of times as processes come and go. Serving a 96-byte request by carving up whole 4 KB pages would waste almost the entire page — that is the internal fragmentation you met in the paging rung, the slack inside a fixed block. So the kernel layers two allocators: a coarse one that hands out runs of whole pages, and a fine one that sits on top and subdivides those pages into tiny objects with almost no waste.
The buddy system: handing out whole pages
The coarse layer is the buddy system, and it is delightfully simple once you see the picture. The kernel keeps free memory in blocks whose sizes are all powers of two — 1 page, 2 pages, 4 pages, 8 pages, and so on — sorted into lists, one list per size. When you ask for, say, 3 pages, the buddy system rounds up to the next power of two (4 pages) and finds a free block of that size. If the smallest free block is larger than you need, it splits it in half, and half again, until it has a block of just the right size — and each half it creates is called the buddy of the other.
- Round up. A request for 3 pages rounds up to 4 (the next power of two). The buddy system never hands out odd sizes; this rounding is a small internal fragmentation cost it accepts on purpose.
- Find or split. Look in the 4-page list. If it is empty, look in the 8-page list, take one block, and split it into two 4-page buddies — keep one, put the other on the 4-page list.
- Hand it over. Mark the chosen block as allocated and return its address. The split blocks remember their size and position so freeing can undo it later.
- Free and coalesce. When the block is freed, check whether its buddy is also free. If so, merge the two back into one bigger block — and check that bigger block's buddy too, merging upward as far as it can.
That last step is the whole point and the reason for the power-of-two scheme. Because a block and its buddy are always the same size and sit at predictable, aligned addresses, the kernel can find a freed block's buddy with a single quick calculation — flip one bit of the address — and check in constant time whether they can merge. Merging fights external fragmentation: without coalescing, memory would slowly shatter into a confetti of small free blocks with no large run left, even when plenty of total memory is free. The buddy system keeps stitching the confetti back into large sheets. The honest trade-off is that rounding every request up to a power of two wastes a little memory inside each block — internal fragmentation again — which is exactly why we need a second, finer allocator on top.
The slab allocator: tiny objects, no waste
The fine layer is the slab allocator, and it solves a problem the buddy system would be terrible at. The kernel allocates the same kinds of small object over and over: process-control blocks, file structures, network buffers, directory entries. Imagine a kitchen that constantly needs identical small bowls. You would not smash a whole dinner plate every time you need one bowl and glue a new bowl out of the shards. Instead you keep a shelf stocked with ready-made bowls of exactly that size; grab one when you need it, wash it and put it back when you are done. A slab is that shelf: one or more pages (gotten from the buddy system) pre-divided into a row of equal-sized slots, all dedicated to one type of object.
Two clever ideas make this fast in ways a general allocator cannot match. First, because every slot in a slab is exactly the size of one object, there is essentially no internal fragmentation and no searching for a fit — allocation is just "take the next free slot," a constant-time grab, and freeing is "mark this slot free again." Second, and more subtly, the allocator caches the objects in their initialized state. When you free a process-control block, the slab allocator does not scrub it; it leaves the structure's reusable scaffolding in place, so the next allocation skips most of the setup. Reusing a warm, half-built object instead of constructing one from cold bytes is where a lot of the speed comes from — the bowl is already the right shape, you just refill it.
One honest caveat before we move on, because allocators inside a kernel live with constraints user programs never face. Kernel memory often cannot be paged out — a buffer the disk is about to write into must stay put at a fixed frame, or the DMA transfer would scribble over the wrong place. And a handler running in interrupt context cannot afford to wait: it must not block on a slow path while allocating, because, as you saw, the top half of an interrupt handler runs with interrupts disabled and has no process to put to sleep. So kernel allocators must often promise to either succeed immediately or fail immediately, never "hang on while I free up some room." These pressures are exactly why the kernel runs lean, specialized allocators instead of the comfortable, blocking malloc your user programs enjoy. The next guide picks up the thread that runs through all of this — how the kernel keeps its own shared data correct while interrupts and multiple cores all reach for it at once.