Mechanism: Address Translation

Crux: How to efficiently and flexibly virtualize memory?

We use hardware-based address translation, or just address translation for short. With address translation, the hardware transforms each memory access, changing the virtual address provided by the instruction to a physical address where the desired information is actually located.
Hardware only cannot virtualize memory, and the OS must get involved at key points to set up the hardware so that the correct translations take place; it must thus manage memory, keeping track of which locations are free and which are in use, and judiciously intervening to maintain control over how memory is used.

Assumptions

1. The user's address space must be placed contiguously in physical memory
2. The size of the address space is not too big; specifically, that it is less than the size of physical memory
3. Each address space is exactly the same size

An Example

Imagine there is a process whose address space as indicated in Figure 15.1.

image.png

It is a short code sequence as follows:

void func()
    int x;
    ...
    x = x + 3; // this is the line of code we are interested in

The compiler turns this line of code into assembly, which might look something like this in x86:

128: movl 0x0(%ebx), %eax   ;load 0+ebx into eax
132: addl $0x03, %eax           ;add 3 to eax register
135: movl %eax, 0x0(%ebx)   ;store eax back to mem

It presumes that the address of x has been placed in the register ebx, and then loads the value at the address into the general-purpose register eax using the movl instruction (for "longword" move). The next instruction adds 3 to eax, and the final instruction stores the value in eax back into memory at the same location.
You can see how both the code and data are laid out in the process's address space in Figure 15.1.
An example of what physical memory might look like once this process's address has been placed in memory is found in Figure 15.2.

image.png

Dynamic (Hardware-based) Relocation

This method is also referred to as base and bounds.
We'll need two hardware registers within each CPU: one base register, and the other the bounds (or limit) register. This base-and-bounds pair is going to allow us to place the address space anywhere we'd like in physical memory while ensuring that the process can only access its own address space.
Each program is written and compiled as if it is loaded at address 0. But when it starts running, the OS decides where in physical memory it should be loaded and sets the base register to that value. In the example in Figure 15.2, the value of the base register is 32KB.
When any memory reference is generated by the process, it is translated by the processor in the following manner:

image.png

128: movl 0x0(%ebx), %eax

The PC is set to 128. When the hardware needs to fetch this instruction, it first adds the value to the base register value of 32 KB (32768) to get a physical address of 32896; the hardware then fetches the instruction from that physical address. Next, the processor begins executing the instruction. At some point, the process then issues the load from virtual address 15 KB (the address stored in ebx), which the processor takes and again adds to the base register (32 KB), getting the final physical address of 47 KB and thus the desired contents.
This relocation of the address happens at runtime, and because we can move address spaces even after the process has started running, the technique is often referred to as dynamic relocation.
As for the bounds register, it helps with protection. Specifically, the processor will first check that the memory reference is within bounds to make sure it is legal; in the example above, the bounds register would always be set to 16KB. If a process generates a virtual address that is greater than the bounds, or one that is negative, the CPU will raise an exception, and the process will likely be terminated. The point of the bounds is thus to make sure that all addresses generated by the process are legal and within the “bounds” of the process.
The base and bounds registers are hardware structures kept on the chip (one pair per CPU), and they are also called the memory management unit (MMU).
The bounds register can either hold the size of the address space or the physical address of the end of the address space, but the first method is simpler.

OS Issues

1. The OS must take action when a process is created, finding space for its address space in memory.

Under our assumptions, the OS can simply view physical memory as an array of slots, and track whether each one is free or in use. When a new process is created, the OS will have to search a data structure (often called a free list) to find room for the new address space and then mark it used.

2. The OS Must take action when a process is terminated, reclaiming all of its memory for use in other processes or the OS.

Upon termination of a process, the OS puts its memory back on the free list, and cleans up any associated data structures as need be.

3. The OS must take action when a context switch occurs.

The values of the base and bounds register differ for each running program, thus, the OS must save and restore these register when it switches between processes. Specifically, the values are saved in a per-process structure such as the process structure or process control block (PCB).

When a process is stopped, it is possible for the OS to move an address space from one location in memory to another, and the value of the base register that is stored in the PCB should also be updated.
Access to the base and bounds registers is privileged.

Summary

This simple structure has its inefficiencies. As you can see in Figure 15.2, the relocated process is using physical memory from 32 KB to 48 KB; however, because the process stack and heap are not too big, all of the space between the two is simply wasted, which is called internal fragmentation.