Mechanism: Address Translation

CPU: limited direct execution (LDE)

In virtualizing memory, we will pursue efficiency and control.

CRUX: How to efficiently and flexibly virtualize memory?

Technique: hardware-based address translation / address translation, changing the virtual address provided by the instruction to a physical address.

Interposition is powerful: On of the usual benefits of such an approach is transparency.

Dynamic (Hardware-based) Relocation

base and bounds / dynamic relocation:

• base register
• bounds / limit register

$$physical \ address =virtual \ address + base$$

The base and bounds registers are hardware structures kept on the chip (one pair per CPU). Sometimes people call the part of the processor that helps with address translation the memory management unit (MMU).

Hardware Support: A Summary

• 2 CPU modes:

  • The OS runs in privileged mode / kernel mode, where it has access to the entire machine; applications run in user mode, where they are limited in what they can do. A single bit, perhaps stored in some kind of processor status word, indicates which mode the CPU is currently running in; upon certain special occasions (e.g., a system call or some other kind of exception or interrupt), the CPU switches modes.

• base and bounds registers: MMU

  • The hardware should provide special instructions to modify the base and bounds registers, allowing the OS to change them when different processes run. These instructions are privileged; only in kernel ode can the registers be modified.
  • The CPU must be able to generate exceptions in situations where a user tries to access memory illegally; in this case, the CPU should stop executing the user program and arrange for the OS “out of bounds” exception handler to run. The CPU should raise an exception and run the “tried to execute a privileged operation while in user mode” handler. The CPU must provide a method to inform it of the location of these handlers; a few more privileged instructions are thus needed.

  Operating System Issues

  free list: a data structure that tracks memory usage.

  Specifically, when the OS decides to stop running a process, it must save the values of the base and bounds registers to memory, in some per-process structure such as the process structure or process control block (PCB).

Problems

• Internal fragmentation: the stack and heap are too small. The space is wasted.

Homework

1. Run with seeds 1, 2, and 3, and compute whether each virtual address generated by the process is in or out of bounds. If in bounds, compute the translation.
   • SV PA SV SV SV
   • PA PA SV SV SV
   • SV SV SV PA PA
2. Run with these flags: -s 0 -n 10. What value do you have set -l (the bounds register) to in order to ensure that all the generated virtual addresses are within bounds?
   • 929
3. Run with these flags: -s 1 -n 10 -l 100. What is the maximum value that base can be set to, such that the address space still fits into physical memory in its entirety?
   • 16283
4. Run some of the same problems above, but with larger address spaces (-a) and physical memories (-p).
5. What fraction of randomly-generated virtual addresses are valid, as a function of the value of the bounds register? Make a graph from running with different random seeds, with limit values ranging from 0 up to the maximum size of the address space.