Memory Management

Introduction

Did you know that when a CPU executes an instruction, it doesn't actually see where your data is physically located in your computer's RAM? Instead, it relies on a sophisticated hardware and software illusion called virtual memory to translate abstract locations into physical hardware coordinates in nanoseconds. Without this seamless coordination, running multiple apps at once would be completely impossible. In this lesson, we will explore how operating systems manage, share, and protect main memory.

Learning Objectives:

• Distinguish between logical and physical addresses and analyze the critical role of the Memory Management Unit (MMU) in dynamic address translation.
• Apply first-fit, best-fit, and worst-fit contiguous allocation strategies and analyze the causes of internal and external fragmentation.
• Trace the mechanics of page translation and evaluate how Translation Look-aside Buffers (TLBs) optimize effective memory-access time.
• Compare structural variations of page tables (hierarchical, hashed, inverted) and examine real-world memory architectures across IA-32, x86-64, and ARMv8.

Memory Background and Hardware Protection

To understand memory management, we must first look at the hardware boundaries. Main memory and the CPU core registers are the only direct-access storage devices available to the CPU. There are no machine instructions that can directly fetch data from a hard disk or solid-state drive; any disk-bound program or data must first be copied into RAM before the CPU can interact with it.

The Memory Stall and the Cache Remedy CPU registers are built into the processing core and can be accessed within a single CPU clock cycle. Main memory, however, must be accessed via a transaction on the system memory bus. This transaction can take many CPU cycles. While waiting, the processor experiences a memory stall. To mitigate this intolerable delay, fast, hardware-managed cache memory is placed directly on the CPU chip to accelerate access without requiring operating-system intervention.

Hardware Address Protection For correct system operation, we must protect the operating system from user processes, and protect user processes from one another. Since intervening on every memory access would carry a massive performance penalty, this protection is implemented in hardware.

One common approach uses two registers:

• Base Register: Holds the smallest legal physical memory address allocated to a process.
• Limit Register: Specifies the size of the range of legal addresses.

For example, if a base register holds 300040 and the limit register is 120900, the program can legally access physical addresses from 300040 through 420939 inclusive.

When a program executes in user mode, the hardware automatically compares every memory reference against these two registers. Any attempt to access memory outside this legal range triggers a trap to the operating system, which treats it as a fatal addressing error. These registers can only be loaded using a privileged instruction in kernel mode, ensuring that user programs cannot modify their own boundaries.

Address Binding and Address Spaces

Before a program can run, it resides on a disk as a binary executable file. The operating system must load the program into memory and set up its process context. During this lifecycle, addresses are represented in different ways across several translation steps.

Address Binding Stages Address binding is the mapping of symbolic addresses to absolute physical memory addresses. This can occur at three different stages:

• Compile Time: If you know exactly where the process will reside in memory ahead of time, the compiler can generate absolute code. If this location changes later, the entire program must be recompiled.
• Load Time: If the binding location is not known at compile time, the compiler generates relocatable code. Final binding is delayed until the loader places the program in memory.
• Execution Time: If a process can be moved from one memory segment to another during runtime, binding must be delayed until execution. This is the approach used by most modern operating systems and requires specialized hardware support.

Logical vs. Physical Addresses Understanding the distinction between address types is central to modern memory management:

• Logical Address: An address generated by the CPU (often called a virtual address when execution-time binding is active).
• Physical Address: The address loaded into the memory-address register of the physical RAM unit.

The runtime mapping from logical (virtual) to physical addresses is handled by a hardware device called the Memory-Management Unit (MMU).

Under a simple dynamic relocation scheme, the MMU uses a relocation register (which acts as a base register). When a user process generates a logical address, the value in the relocation register is added to it before it is sent to memory. The user program never sees the physical address; it manipulates logical pointers starting at address 0, while the hardware dynamically handles the relocation transparently.

Dynamic Loading, Dynamic Linking, and Shared Libraries

To optimize physical memory usage, operating systems avoid loading unused code and resources into RAM unnecessarily.

Dynamic Loading With dynamic loading, a program routine is not loaded into memory until it is explicitly called by the running program. All routines are kept on disk in a relocatable format. When a routine is called, the calling program checks if it is already in memory. If not, the relocatable linking loader is called to bring it in. This is highly beneficial for handling large, rarely used blocks of code, such as specialized error-handling routines. Crucially, dynamic loading does not require explicit operating system support; it is designed and managed by the application programmer.

Dynamic Linking and Shared Libraries In contrast to dynamic loading, dynamic linking requires operating system assistance.

• Static Linking: The system loader combines all referenced library modules directly into the binary program image, wasting memory and storage by duplicating library code for every executable.
• Dynamic Linking: The linking of system libraries (such as the standard C library, libc) is postponed until execution time.

These dynamically linked libraries (DLLs), also known as shared libraries, allow multiple processes to share a single copy of the library in physical memory.

When an application references a shared library routine, the loader checks if the DLL is already in memory. If it is, the loader adjusts the application's address tables to point to the shared instance. To prevent compatibility issues when libraries are updated, version numbers are embedded in both the program and the library files. Programs will continue utilizing older library versions if major, incompatible updates are made.

Contiguous Memory Allocation and Fragmentation

In early operating systems, contiguous memory allocation was the standard practice. Under this scheme, memory is usually divided into two partitions: one for the resident operating system (often placed in high memory), and one for user processes. Each process is contained in a single, contiguous section of memory.

Variable-Partition Allocation In a variable-partition scheme, the operating system tracks which parts of memory are available (free blocks called "holes") and which are occupied. When a new process arrives, the OS searches the set of holes for one large enough to accommodate it. Over time, memory becomes a scattering of holes of various sizes.

Choosing which hole to allocate to a process is known as the dynamic storage-allocation problem. The three most common strategies are:

• First-Fit: Allocate the first hole that is big enough. This is generally the fastest search strategy.
• Best-Fit: Search the entire list (unless sorted by size) and allocate the smallest hole that is big enough. This leaves the smallest leftover hole.
• Worst-Fit: Search the entire list and allocate the largest hole. This leaves the largest leftover hole, which may be more useful for subsequent requests.

Simulations show that first-fit and best-fit yield far superior storage utilization compared to worst-fit.

Fragmentation Problems Contiguous memory allocation suffers from two forms of fragmentation:

• External Fragmentation: Occurs when there is enough total free memory to satisfy an allocation request, but the available space is split into many small, non-contiguous holes. Statistical analysis reveals the 50-percent rule: for every $N$ allocated blocks, another $0.5 N$ blocks are lost to external fragmentation, leaving up to one-third of memory unusable.
• Internal Fragmentation: Occurs when memory is allocated in fixed-size blocks. If a process requests slightly less memory than the block size (e.g., requesting 18,462 bytes from an 18,464-byte block), the leftover space is wasted inside the allocated partition.

Compaction One solution to external fragmentation is compaction. This process shuffles memory contents to place all free memory together into one large block. However, compaction is only possible if address binding is dynamic and done at execution time. Moving programs and updating their base registers can be extremely computationally expensive.

Paging: The Basic Method

Paging is a memory-management scheme that permits a process's physical address space to be non-contiguous. This completely avoids external fragmentation and the need for expensive memory compaction.

Pages and Frames Under a paging scheme:

• Physical memory is broken into fixed-sized blocks called frames.
• Logical memory is broken into blocks of the same size called pages.

When a process is executed, its pages are loaded from the disk into any available physical frames. Because of this structure, the logical address space is completely decoupled from the physical address space.

Every address generated by the CPU is divided by the hardware into two parts:

1. Page Number ($p$): Used as an index into a per-process page table.
2. Page Offset ($d$): Represents the displacement within the page.

Address Translation Steps To translate a logical address to a physical address, the MMU performs the following:

1. Extracts the page number $p$ and uses it to look up the entry in the process's page table.
2. Retrieves the corresponding physical frame number $f$ from the table.
3. Replaces the page number $p$ with the frame number $f$ in the address, while keeping the offset $d$ identical.

Page Sizing Mechanics Page sizes are defined by hardware and are always powers of 2 (typically ranging from 4 KB to 8 KB, though some modern systems support larger "huge pages" of 2 MB or more). Defining sizes in powers of 2 makes address translation simple. If the logical address space size is $2^m$ and the page size is $2^n$ bytes, then the high-order $m - n$ bits designate the page number, and the low-order $n$ bits represent the offset.

Internal Fragmentation in Paging While paging eliminates external fragmentation, it still suffers from internal fragmentation. Because physical memory is allocated in integer units of frames, the final frame allocated to a process is rarely completely filled. On average, internal fragmentation wastes half a page per process. Although smaller page sizes would reduce this waste, larger pages are preferred because they reduce page table overhead and improve disk I/O efficiency.

Paging: Hardware Support and TLBs

Since page tables are unique to each process, a pointer to the current process's page table is stored in its Process Control Block (PCB). When a context switch occurs, the CPU's dispatcher reloads the hardware page-table pointer.

The Page-Table Base Register (PTBR) In small systems, the page table can be implemented using high-speed registers. However, modern systems require millions of page-table entries, making register-based tables impractical. Instead, the page table is kept in main memory, and a Page-Table Base Register (PTBR) points directly to it.

This register-based approach speeds up context switches, but it introduces a major performance bottleneck: accessing a single piece of data now requires two memory accesses—one to retrieve the frame number from the page table, and another to access the actual data. This cuts memory performance in half.

Translation Look-Aside Buffer (TLB) To solve this performance bottleneck, hardware designers use a special, highly associative, high-speed hardware cache called a Translation Look-Aside Buffer (TLB).

The lookup process is highly efficient:

1. The CPU generates a logical address.
2. The MMU checks if the page number is cached in the TLB (a TLB hit). If it is, the frame number is immediately available, completing the access in a single step.
3. If the page is not in the TLB (a TLB miss), the MMU must perform a slow memory reference to the page table. Once retrieved, the translation is cached in the TLB for subsequent accesses.

Some TLBs store Address-Space Identifiers (ASIDs). An ASID uniquely identifies the process that owns a page entry, providing address protection and allowing the TLB to hold translations for multiple processes simultaneously. If ASIDs are not supported, the entire TLB must be flushed on every context switch to avoid referencing stale translation data.

Calculating Effective Memory-Access Time (EAT) We can calculate memory performance using the TLB hit ratio (the percentage of times a page number is found in the TLB):

$$\text{EAT} = (\text{Hit Ratio} \times \text{TLB Access Time}) + ((1 - \text{Hit Ratio}) \times \text{Miss Access Time})$$

If memory access takes 10 nanoseconds, a TLB hit takes 10 ns. A TLB miss requires a page table lookup (10 ns) plus the actual memory access (10 ns), totaling 20 ns.

• With a 80% hit ratio: $\text{EAT} = 0.80 \times 10 + 0.20 \times 20 = 12\text{ ns}$ (a 20% performance slowdown).
• With a 99% hit ratio: $\text{EAT} = 0.99 \times 10 + 0.01 \times 20 = 10.1\text{ ns}$ (only a 1% slowdown).

Memory Protection Features Each page-table entry includes status bits to enforce security and access controls:

• Read-Write / Read-Only Bit: Restricts execution or writing on specific pages.
• Valid-Invalid Bit: A 'valid' bit indicates the page is in the process's legal logical address space. An 'invalid' bit indicates the page does not belong to the process, triggering an address trap if accessed.
• Page-Table Length Register (PTLR): Used by some systems to define the active size of the page table, preventing the system from allocating memory for unused table entries.

Shared Pages and Page Table Structures

Paging makes it easy for multiple processes to share common system libraries and resources.

Shared Pages If code is reentrant (meaning it is non-self-modifying and never changes during execution), multiple processes can safely execute it at the same time. Rather than duplicating a 2 MB system library like libc across 40 user processes (which would consume 80 MB of RAM), the operating system loads a single copy of the library into physical memory. The page tables of all 40 processes map their respective virtual pages to those same physical frames, reducing total memory consumption to just 2 MB.

Hierarchical Paging Modern systems support large, 32-bit or 64-bit logical address spaces. Under a 32-bit system with 4 KB pages, a flat page table requires over 1 million entries ($2^{20}$). At 4 bytes per entry, a single process needs 4 MB of contiguous RAM just to store its page table.

To avoid allocating this table contiguously, we can use hierarchical paging (also called forward-mapped paging), where the page table itself is paged. In a two-level paging scheme, a 32-bit logical address is broken down as follows:

• A 10-bit outer page table index ($p_1$).
• A 10-bit inner page table displacement ($p_2$).
• A 12-bit page offset ($d$).

For 64-bit architectures, two-level hierarchical tables are insufficient because the outer page table remains excessively large. Extending this to 3- or 4-level tables requires too many memory accesses to resolve a single address.

Hashed Page Tables For address spaces larger than 32 bits, a hashed page table is a highly effective alternative. The virtual page number is passed to a hash function, which maps it to an entry in the hash table. Each slot in the hash table contains a linked list of elements (to handle collisions) containing:

1. The virtual page number.
2. The mapped physical frame number.
3. A pointer to the next element in the list.

A variation of this is the clustered page table, where each hash table entry points to a block of several contiguous pages. This is highly efficient for sparse address spaces where memory access is scattered.

Inverted Page Tables While standard page tables grow with the size of the virtual address space, an inverted page table scales with physical memory.

An inverted page table has exactly one entry for each real physical frame in the system. Each entry stores:

• The virtual address of the page.
• The Address-Space Identifier (ASID/PID) of the process that owns it.

This significantly reduces the memory required to store translations. However, searching the table is more difficult. Because the table is sorted by physical frame number, searching by virtual address requires scanning the entire table. To speed up lookups, an inverted page table is paired with a hash table and a TLB.

One drawback of inverted page tables is that they make shared memory difficult to implement. Since there is only one entry per physical frame, a physical frame cannot be mapped to multiple virtual addresses simultaneously.

Swapping: Standard and Paging-based

A process must be in physical memory to run. However, if the active processes require more memory than is physically available, the system can temporarily move inactive processes to secondary storage using a technique called swapping.

Standard Swapping Standard swapping moves entire processes (including all of their code, data, and execution context) between main memory and a fast secondary backing store. While this allows the system to run more programs than can fit in physical RAM, moving entire processes is extremely slow and is rarely used in modern desktop and server operating systems.

Swapping with Paging Modern systems use a variation called swapping with paging (often referred to simply as paging). Instead of swapping an entire process, the OS only swaps out individual pages:

• Page-Out: Moves an inactive page from physical memory to the backing store.
• Page-In: Retrieves a page from the backing store and loads it back into an available physical frame when it is accessed.

This dramatically reduces the amount of data that needs to be copied, allowing the system to run efficiently even when physical memory is overcommitted.

Swapping on Mobile Platforms Mobile operating systems (such as Apple's iOS and Google's Android) do not support swapping in any form. Mobile devices use solid-state flash memory for storage, which has limited write cycles before it becomes unreliable. Additionally, mobile storage controllers have lower write throughput than desktop systems.

Instead of swapping:

• iOS: Asks running applications to voluntarily free up allocated memory. If memory remains critically low, the OS will terminate inactive applications.
• Android: Saves the application's state to flash memory and then terminates the process. When the user reopens the app, it can quickly restore its saved state.

Case Studies: Intel and ARM Architectures

To see how these concepts are applied in the real world, let's look at the memory management designs of two dominant computer architectures.

IA-32 (32-Bit Intel) Architecture Memory management in IA-32 is split into two sequential steps: segmentation and paging. The CPU generates a logical address, which is passed to the segmentation unit to produce a intermediate linear address. This linear address is then passed to the paging unit, which generates the final physical address.

• IA-32 Segmentation: The logical address is a pair containing a 16-bit selector and a 32-bit offset. The selector references a segment descriptor in either the Local Descriptor Table (LDT) or the Global Descriptor Table (GDT), which contains the segment's base address and limit. If the offset is valid, the base address is added to the offset to create a 32-bit linear address.
• IA-32 Paging: Supports 4 KB or 4 MB pages. For 4 KB pages, a two-level paging hierarchy is used. The CR3 register points to the process's page directory. The high 10 bits of the linear address index into this directory to locate the page table, the middle 10 bits locate the frame in the page table, and the final 12 bits define the physical offset.
• Page Address Extension (PAE): To support more than 4 GB of RAM on 32-bit systems, Intel introduced PAE. This changes the paging model to a three-level hierarchy using a Page Directory Pointer Table, extending physical addressing from 32 bits to 36 bits (allowing up to 64 GB of physical RAM).

x86-64 (64-Bit Intel/AMD) Architecture Although the x86-64 architecture is theoretically 64-bit, current implementations use a 48-bit virtual address space.

• It uses a 4-level paging hierarchy with 4 KB pages.
• When paired with PAE, it translates 48-bit virtual addresses into 52-bit physical addresses (supporting up to 4,096 terabytes of RAM).

ARMv8 (64-Bit Mobile/Embedded) Architecture ARMv8 is designed for mobile and embedded devices, offering highly flexible page sizing through three translation granules:

• 4 KB Granule: Supports up to 4 levels of page tables, with 4 KB pages and optional 2 MB or 1 GB contiguous regions.
• 16 KB Granule: Supports 4 levels of page tables, with 16 KB pages and 32 MB regions.
• 64 KB Granule: Supports 3 levels of page tables, with 64 KB pages and 512 MB regions.

To optimize lookups, ARMv8 implements a two-tiered TLB design. The inner layer contains two fast micro TLBs (one for instructions and one for data) that support ASIDs. If a lookup misses in the micro TLB, the system checks the larger, outer main TLB. If both miss, a hardware-managed page table walk is performed.

Summary

Let's review the key concepts we've covered in this lesson:

• Hardware Separation: The CPU uses base and limit registers to enforce memory protection, ensuring that user processes cannot access operating system space or other processes' memory.
• Dynamic Relocation: The Memory-Management Unit (MMU) translates logical addresses generated by the CPU into physical addresses in RAM during execution.
• Contiguous vs. Paged Allocation: Contiguous allocation causes external fragmentation, which requires expensive memory compaction. Paging eliminates external fragmentation by breaking physical memory into fixed-size frames and logical memory into pages.
• TLB Acceleration: Because storing page tables in memory requires two memory accesses per address, a Translation Look-Aside Buffer (TLB) is used to cache translations and restore near-native memory access speeds.
• Page Table Architectures: To handle large address spaces without wasting RAM, operating systems use hierarchical paging (paging the page table), hashed page tables (using linked lists for collisions), or inverted page tables (scaling with physical memory rather than virtual space).
• Swapping and Platforms: Desktop operating systems use page-level swapping to overcommit memory, while mobile platforms avoid swapping entirely due to the write limits of flash memory, relying instead on voluntary memory release or process termination.