8. Address Translation

Info

This is a summary of the 15th chapter of the book “Operating Systems: Three Easy Pieces” by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. The chapter introduces address translation, a key concept in virtualizing memory to provide each process with an isolated address space. Address translation uses hardware to map virtual addresses to physical addresses, ensuring efficient memory use and protection between processes.

Introduction to Address Translation

The document explains virtual memory (VM) and address translation, essential for virtualizing memory while ensuring control and efficiency. In CPU virtualization, the “limited direct execution” (LDE) approach lets programs run directly on hardware but involves the OS during key events like system calls, balancing efficiency with OS control. Similarly, memory virtualization aims to let programs freely use address spaces while securing memory access to prevent cross-process interference.

Core Concepts

1. Address Translation:

   • Uses hardware to map each memory access from a virtual address (used by programs) to a physical address (actual memory location).
   • Achieves an illusion of isolated memory spaces for each process, even as multiple processes share physical memory.

2. Dynamic Relocation with Base and Bounds:

   • In early systems, each CPU had a pair of registers called “base” and “bounds” to allow dynamic relocation.
   • The base register sets the starting physical address for a process’s memory space, translating each virtual address as physical address = virtual address + base.
   • The bounds register limits the address space size, raising an exception if a virtual address is out of bounds, ensuring processes only access their own memory.
   • By allowing each process to view its address space as starting at zero, the base and bounds technique supports dynamic relocation and protects memory access.

3. Interposition in Address Translation:

   • Interposition, or inserting control between actions, is central to address translation.
   • The hardware intercepts each memory access, using the base and bounds registers to map virtual addresses to physical locations and check access bounds.
   • Interposition provides transparency, allowing processes to operate as if they have exclusive access to memory.

Hardware Support Requirements

Dynamic relocation relies on several hardware features:

• Privileged Mode: A CPU mode that restricts certain operations, ensuring only the OS can modify the base/bounds registers.
• Base and Bounds Registers: Each CPU has these registers to facilitate address translation and enforce memory limits.
• Exception Handling: Hardware raises exceptions if a process attempts unauthorized memory access or unauthorized register changes.
• Free List Management: OS uses data structures (often a free list) to track available physical memory slots and allocate them to processes.

Operating System Responsibilities

The OS plays a key role in managing dynamic relocation by:

• Allocating Memory: Assigning address spaces for new processes and updating the free list.
• Handling Exceptions: Terminating processes that attempt illegal memory access or unauthorized register modification.
• Context Switching: Saving and restoring base/bounds values during process switches to ensure each process’s address space remains isolated.
• Relocating Processes: The OS can move a process’s address space by updating the base register if memory needs change during execution.
• Managing Free List: The OS keeps track of which memory slots are available to allocate for new processes, releasing memory when processes terminate.

Example of Address Translation

Consider an example where a process has an address space of 16 KB, loaded into physical memory at 32 KB. If this process attempts to access a virtual address like 1 KB, the translation would calculate the physical address as 33 KB (base 32 KB + 1 KB). If the process tries to access a virtual address beyond its bounds (like 20 KB), an exception will be triggered.

For a more specific example, a process with base set to 16 KB and bounds set to 4 KB translates:

• Virtual address 0 to physical address 16 KB.
• Virtual address 1 KB to physical address 17 KB.
• Virtual address 3 KB to physical address 19 KB.
• Virtual address 4 KB or higher triggers an exception.

Tip

• internal fragmentation: wasted space within a chunk
• external fragmentation: wasted space between chunks

Advantages and Limitations

• Advantages:

  • Efficient and transparent memory mapping.
  • Protection of process memory through strict bounds checking.

• Limitations:

  • Internal Fragmentation: Fixed-size memory slots can lead to wasted space, particularly if a process’s heap and stack do not fully utilize the allocated slot.
  • Scalability Issues: The base-and-bounds model does not adapt well to systems with variable-sized address spaces or more complex memory structures, such as multi-level page tables.

This summary provides an in-depth look at address translation, highlighting the base-and-bounds model’s ability to virtualize memory efficiently while offering control and protection. Future advancements, such as segmentation and paging, aim to address its limitations, particularly around memory utilization and scalability.

Next Chapter: 9.Segmentation