Memory management

A logical (virtual) address is the address a program generates. A physical address is the address seen by the memory unit. The set of all logical addresses is the logical address space, and the set of all physical addresses is the physical address space.

Binding of instructions and data to addresses can happen at compile time (absolute code, the load address is fixed), at load time (relocatable code, addresses fixed when the program is loaded) or at execution time (addresses can change while the program runs). Only execution-time binding allows a process to be moved in memory after it has started, and it needs hardware support.

The memory-management unit (MMU) is the hardware that maps a logical address to a physical address on every reference. In the simplest scheme a relocation register (base) is added to every logical address, and a limit register is compared against it first: if the logical address is not less than the limit, the hardware traps to the operating system.

In contiguous allocation each process occupies one unbroken block of memory. With fixed partitions memory is divided into partitions of preset sizes and each holds at most one process; the unused part of a partition is internal fragmentation. With variable partitions a process gets exactly the memory it asks for, so there is no internal fragmentation, but as processes finish the free memory breaks into scattered holes. Total free memory may be enough for a request while no single hole is: this is external fragmentation.

Compaction shifts the allocated blocks together so that all free memory becomes one hole. It removes external fragmentation but is possible only with execution-time binding, because processes change address. Paging avoids external fragmentation altogether.

Trace for variable partitions. Free holes in address order are 150, 450, 250, 350 and 600 KB. Requests arrive in the order 200, 400, 120 and 480 KB, and the holes left over after each allocation stay in place. For best fit and worst fit, ties are broken by the lower address (none occur in this trace). The table shows the hole chosen for each request.

Paging divides the logical address space into fixed-size pages and physical memory into frames of the same size. A process may be placed in any free frames, so there is no external fragmentation. The only waste is internal fragmentation in the last page of a process (under the usual assumption that process sizes are random, about half a page per process on average). Page size is a power of two so that the address splits cleanly into bits.

A logical address of $n$ bits with page size $2^d$ bytes splits into a page number (the high $n-d$ bits) and an offset (the low $d$ bits). The page number indexes the page table, whose entry holds the frame number (plus valid, protection and other bits). The physical address is the frame number followed by the same offset. Convention: memory is byte-addressable, $K=2^{10}$, $M=2^{20}$, $G=2^{30}$ unless stated.

Example of the split: with 4 KB pages the logical address $\text{0x3A7F5}$ has offset $\text{0x7F5}$ (the low 12 bits, three hex digits) and page number $\text{0x3A}$. If the page table maps page $\text{0x3A}$ to frame $\text{0x15}$, the physical address is the frame number followed by the offset: $\text{0x157F5}$.

The page table is kept in main memory. The page-table base register (PTBR) points to it and, where used, a page-table length register (PTLR) holds the number of entries; a page number not less than the PTLR value traps. A context switch only reloads the PTBR. Paging also makes sharing easy: reentrant (read-only) code can be shared by making entries in several processes' page tables point to the same frames, so one copy in memory serves them all.

A single-level table for a large address space can itself be huge. Multi-level (hierarchical) paging pages the page table: the page number is split into several parts, the first indexes an outer table, and so on, and only the tables that are actually in use need to exist. The standard GATE assumption is that every table at every level fits exactly in one page.

Inverted page table: one entry per physical frame rather than per page, holding the process id and page number stored in that frame. The table size depends on physical memory, not on the virtual address space, and so does not grow with the number of processes. Lookup by page number needs a search, so a hash is usually used to find the entry. A drawback is that sharing a frame between processes is awkward, because each frame has only one entry and so one (process, page) pair.

Hashed page table: the page number is hashed to select a bucket holding a chain of entries (page number, frame number, next pointer); the chain is searched for a match. It is used for address spaces larger than 32 bits.

With paging, each logical reference costs extra memory accesses to read the page-table entries. The translation look-aside buffer (TLB) is a small, fast associative cache of recent page-number to frame-number mappings. On a TLB hit the frame is known immediately and only the data access to memory is needed. On a miss the page table is walked in memory and the entry is then loaded into the TLB. The hit ratio $h$ is the fraction of references that hit.

The TLB holds mappings of the running process. On a context switch it must be flushed, unless each entry carries an address-space identifier (ASID) naming its process. With ASIDs, entries of several processes can stay in the TLB together.

Segmentation follows the programmer's view: a program is a set of variable-length segments (code, stack, data and so on). A logical address is a pair (segment number $s$, offset $o$). The segment table has one entry per segment with a base (starting physical address) and a limit (segment length). The segment-table base register (STBR) locates the table in memory and the segment-table length register (STLR) holds the number of segments.

Segmentation has no internal fragmentation but suffers external fragmentation, since segments are variable-sized and are placed in contiguous memory. Segmentation with paging pages each segment: the segment number selects a segment-table entry that points to that segment's page table, and the offset is then split into page number and page offset. This removes external fragmentation while keeping segment-level protection and sharing.