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
- The user's address space must be placed contiguously in physical memory
- The size of the address space is not too big; specifically, that it is less than the size of physical memory
- Each address space is exactly the same size
An Example
Imagine there is a process whose address space as indicated in Figure 15.1.
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.
In Figure 15.2, the OS uses the first slot of physical memory for itself, and it has relocated the process from the example above into the slot starting at physical memory address 32KB. The other two slots are free (16 KB - 32 KB and 48 KB - 64 KB).
Here comes the question: how can we relocate this process in memory in a way that is transparent to the process?
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:
Each memory reference generated by the process is a *virtual address; the hardware in turn adds the contents of the base register to this address and the result is a physical address that can be issued to the memory system.
In the example above, consider the following instruction:
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.
