Address Translation

Limited Direct Execution (LDE): When process, in certain times such as systemcalls and timer interrupt happens, OS interrupts process to prevent problems. OS gets little support from hardware to do its best to provide efficient virtualization and gets out of the process’s way.

• We want:

  • efficiency: hence requires hardware support; using TLB, pagetable…
  • control: OS guarantees no access to the memory of the application program -> needs hardware support.
  • flexibility: Ez to use address space and ez to program-system.

• Address Translation = hardware-based address translation

  • Can be thought as an additional function of LDE.
  • Through address translation:
    • Hardware translate the virtual address (instruction, load, store) to the physical address.
    • Hardware translates (changes) to relocate the memory reference of programs into the real ones.
    • Of course, OS needs to know empty/used memory space, and control/manage the memory use -> To setup the hardware to ensure the correct/translation of the memory address.

From now on we assume that user address space is consecutive, not too big, smaller than the physical memory, and each address space is the same

Dynamic (hardware-based) relocation = base and bound

1. Each CPU needs two hardware register; one base, one bound (or limit) register.
2. This base and bound pair allows us to allocate address space where we want.
3. In this setupt, each program is written and compiled like address 0 (virtual).
4. At the start of the program, OS decides the physical memory location, and set base register as of it.
   • physical address = virtual address + base (This is how address translation happens).
5. As reallocation is possible later

Note: Static allocation has a main problem: has no protection at all -> can have illegal access from other processes + hard to reallocate later.

6. Bound register is used for protection.
   • Process first checks if the memory reference is legal - by checking bound.
   • If process reference out of base-bound region -> CPU runs exception, kills the process.
   • Meaning it literally indicates the bound of the region (as we already knows the start; base).

Note: Base and Bound registers are hardware structure that exists in CPU chip

Memory management unit (MMU): Processes that help address translation; for more detailed memory management, more circuits are needed in MMU.

Hardware support: summary

1. Needs two CPU modes:
   • Kernel (privileged): Has access to entire computer.
   • User: Application program runs under this mode, has limitations to do something.
2. Process status word: One bit in a register represents the current execution state of CPU.
3. Base and Bound registers; part of MMU
   • Physical address = virtual address + base.
   • Hardware must be able to check if it is legal address; check is done using bound register and other CPU circuits (the other MMU).
   • Hardware must provide instruction that changes base and bound register values (kernel instructinos).
   • Hardware must be able to trigger the exceptions (its handler).

OS issues

To implement base-bound method virtualization memory, it needs three important points.

1. At the process creation, OS needs to find memory space which will become address space.
   • OS memory sees memory as an array of slot, and manage each slot’s usage; finding the free list (the empty space).
2. At the process termination, deallocate the memory so that can be used later. OS puts the memory to free list and manage all the relavant data structures.
3. OS needs to perform additional steps when context switch happens.
   • Each CPU has a pair of base and bound registers, and each program must have different physical memory address. Hence, OS needs to save and store the base-bound when context switch happens in the PCB.
     Note: If process is not running state, OS can easily move the physical address space easily; copy into the new address, and update the base register in PCB -> Hence program does not realize there was a change as it happens before the restore.
4. OS provides exception handler, or helper function.
   • OS installes handler during the boot through privilege instructions.
     Note: memory translation is handled by hardware, no intervention from OS.
   • We still follows the LDE, but OS interven only when process does illegal action.

Summary

Dynamic reallocation is inefficient -> cause internal fragmentation (gapped-space is being wasted).
Internal fragmentation can be avoided by Generalizing base-bound; which is called segmentation.