OSTEP Chapter 15: Address Translation

This is part of our series going through OSTEP book chapters. The OSTEP textbook is freely available at Remzi's website if you like to follow along.

This chapter extends the CPU virtualization playbook to memory. It's the same recipe: let the program run directly on the hardware, but interpose at carefully chosen points so the OS retains control. For memory, this happens at every memory access. Every load, store, and instruction fetch gets translated by hardware from a virtual to a physical address.

The mechanism here is called dynamic relocation, dating to the late 1950s. The base register holds the physical address where the process's address space starts, the bounds register holds its size. On every memory reference the hardware adds base and checks against bounds. If the address is out of range, the CPU raises an exception, and the OS kills the offender.

This takes collaboration between hardware and the OS. Hardware provides privileged mode, the base/bounds registers, translation circuitry, exception generation, and privileged instructions to update the registers. The OS provides memory allocation (a free list, in the simplest case), base/bounds management across context switches, and the exception handlers themselves.

Because there is only one base/bounds pair per CPU, the OS must save and restore them in the process control block(PCB). This means that while a process is descheduled, the OS can freely move its address space and then update the saved base. The process wakes up oblivious to this, hence the name dynamic relocation.

The chapter is transparent about what base-and-bounds gets wrong. The relocated process gets a fixed-size slot, but its stack and heap occupy only a small fraction of it, which means that the space in between causes internal fragmentation. With every process getting the same fat slot regardless of actual footprint, the physical memory fills up quickly. The segmentation discussion, coming next chapter, aims to fix this.