15 - Mechanism: Address Translation.md

Address Translation in Virtual Memory

The Crux

• How to efficiently and flexibly virtualize memory?
• How to provide the flexibility needed by applications?
• How to maintain control over which memory locations an application can access?
• How to ensure application memory accesses are properly restricted?
• How to do all of this efficiently?

Mechanism: Address Translation

• Hardware transforms each memory access (instruction fetch, load, store) by changing the virtual address provided by the instruction to a physical address where the desired information is located.
• On each memory reference, an address translation is performed by the hardware to redirect application memory references to their actual locations in memory.
• The hardware cannot virtualize memory alone; the OS must intervene at key points to set up the hardware for correct translations and manage memory.

Assumptions

• The user's address space must be placed contiguously in physical memory.
• The size of the address space is less than the size of physical memory.
• Each address space is exactly the same size.

Dynamic (Hardware-based) Relocation

• Uses two hardware registers: base register and bounds (limit) register.
• Base register allows the address space to be placed anywhere in physical memory.
• Bounds register ensures the process can only access its own address space.
• Physical address = virtual address + base
• If the virtual address is out of bounds (greater than or equal to bounds, or negative), the CPU raises an exception.

Hardware Support

• Privileged mode to prevent user-mode processes from executing privileged operations.
• Base/bounds register pair per CPU for address translation and bounds checks.
• Circuitry to perform translations and check limits.
• Privileged instructions for the OS to set base/bounds registers before letting a user program run.
• Privileged instructions for the OS to register exception handlers.
• Ability to raise exceptions when processes try to access privileged instructions or out-of-bounds memory.

Operating System Issues

• Allocate memory for new processes and reclaim memory from terminated processes (free list).
• Set base/bounds registers properly upon context switch.
• Handle exceptions (likely action is to terminate offending process).

Summary

• Address translation allows the OS to control every memory access from a process, ensuring accesses stay within the bounds of the address space.
• Hardware support performs the translation quickly for each access, turning virtual addresses (process's view) into physical addresses (actual view).
• Base-and-bounds virtualization is efficient but can lead to internal fragmentation (wasted space inside allocated units).
• More sophisticated machinery is needed to better utilize physical memory and avoid internal fragmentation (e.g., segmentation).

Questions & Answers:

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.

User@Linux:~/ostep-homework/vm-mechanism$ python3 relocation.py -s 1

ARG seed 1
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x0000363c (decimal 13884)
  Limit  : 290

Virtual Address Trace
  VA  0: 0x0000030e (decimal:  782) --> PA or segmentation violation?
  VA  1: 0x00000105 (decimal:  261) --> PA or segmentation violation?
  VA  2: 0x000001fb (decimal:  507) --> PA or segmentation violation?
  VA  3: 0x000001cc (decimal:  460) --> PA or segmentation violation?
  VA  4: 0x0000029b (decimal:  667) --> PA or segmentation violation?

Only VA 1 is in bounds. Its virtual address is `0x0000363c (13884) + 0x00000105 (261) = 0x00003741 (14145)

1. Run with these flags: -s 0 -n 10. What value do you have to set -l (the bounds register) to in order to ensure that all the generated virtual addresses are within bounds?

User@Linux:~/ostep-homework/vm-mechanism$ python3 relocation.py -s 0 -n 10
 
ARG seed 0
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x00003082 (decimal 12418)
  Limit  : 472

Virtual Address Trace
  VA  0: 0x000001ae (decimal:  430) --> PA or segmentation violation?
  VA  1: 0x00000109 (decimal:  265) --> PA or segmentation violation?
  VA  2: 0x0000020b (decimal:  523) --> PA or segmentation violation?
  VA  3: 0x0000019e (decimal:  414) --> PA or segmentation violation?
  VA  4: 0x00000322 (decimal:  802) --> PA or segmentation violation?
  VA  5: 0x00000136 (decimal:  310) --> PA or segmentation violation?
  VA  6: 0x000001e8 (decimal:  488) --> PA or segmentation violation?
  VA  7: 0x00000255 (decimal:  597) --> PA or segmentation violation?
  VA  8: 0x000003a1 (decimal:  929) --> PA or segmentation violation?
  VA  9: 0x00000204 (decimal:  516) --> PA or segmentation violation?

Since the largest virtual address value is 929, we will need to set -l to 930 in order to ensure that all the generated virtual addresses are within bounds

1. 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?

Ans:

Address space size:1k

Physical space size: 16k

Base: 2201

Therefore maximum value that base can be set to is 16k - 1k = 15000

1. Run some of the same problems above, but with larger address spaces (-a) and physical memories (-p).

User@Linux:~/ostep-homework/vm-mechanism$ python3 relocation.py -s 1 -n 10 -l 100 -p 20000 -a 4000

ARG seed 1
ARG address space size 4000
ARG phys mem size 20000

Base-and-Bounds register information:

  Base   : 0x00000a7f (decimal 2687)
  Limit  : 100

Virtual Address Trace
  VA  0: 0x00000d3d (decimal: 3389) --> PA or segmentation violation?
  VA  1: 0x00000bef (decimal: 3055) --> PA or segmentation violation?
  VA  2: 0x000003fc (decimal: 1020) --> PA or segmentation violation?
  VA  3: 0x000007bd (decimal: 1981) --> PA or segmentation violation?
  VA  4: 0x00000705 (decimal: 1797) --> PA or segmentation violation?
  VA  5: 0x00000a2e (decimal: 2606) --> PA or segmentation violation?
  VA  6: 0x00000c52 (decimal: 3154) --> PA or segmentation violation?
  VA  7: 0x00000177 (decimal:  375) --> PA or segmentation violation?
  VA  8: 0x00000071 (decimal:  113) --> PA or segmentation violation?
  VA  9: 0x00000d0f (decimal: 3343) --> PA or segmentation violation?

1. 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.

I asked Claude AI to make a program after a few modifications I could use it to generate a graph.

Program Code:

import subprocess
import matplotlib.pyplot as plt

asize = 1024  # Address space size
num_runs = 10  # Number of runs for each limit value

limit_values = range(0, asize + 1, asize // 10)  # Limit values from 0 to address space size
fractions = []

for limit in limit_values:
    valid_count = 0
    total_count = 0
    for seed in range(num_runs):
        output = subprocess.check_output(["python", "relocation.py", "-s", str(seed), "-a", str(asize), "-p", str(asize * 2), "-l", str(limit), "-c", "-n", "100"])
        output = output.decode("utf-8")
        valid_count += output.count("VALID")
        total_count += 100
    fraction = valid_count / total_count
    fractions.append(fraction)

plt.plot(limit_values, fractions)
plt.xlabel("Limit Value")
plt.ylabel("Fraction of Valid Addresses")
plt.title("Fraction of Valid Addresses vs. Limit Value")
plt.savefig('result.png')

The graph will be stored as result.png