# Address Translation

## Fixed Size Address Space

最簡單的實作就是將記憶體切成固定大小，行程各自佔用一格，以這個例子中就是 16 KB 為一格


## Base & Bound Register

使用 Base 和 Bound Register 分別紀錄行程記憶體位址 `0` 對應到實體記憶體的位址和行程佔用的記憶體大小，當行程要存取記憶體時就將虛擬記憶體地址加上 Base Register 的值，然後由處理器去實體記憶體用計算好的位址去存取，以下例子的行程位在實體記憶體位址 16 KB，而行程大小為 4 KB，當存取的範圍超過 16 + 4 KB 時就會產生錯誤，而 Base 和 Bound Register 也可以稱為記憶體管理單元 (MMU, Memory Management Unit)，而 Base 和 Bound Register 的值只能在 Kernel Mode 被修改，因為行程的記憶體配置由 OS 處理


## Exception

例外 (Exception) 在行程試圖非法存取記憶體時由硬體發起，因為 MMU 可以偵測到記憶體存取是否合法，若不合法就執行例外處理 (Exception Handler)，Exception Handler 在剛開機時由 OS 在 Kernel Mode 設定，當發生例外時通常會將行程終止並釋放記憶體，將屬於行程的記憶體加到 Free List 讓 OS 配置其他行程到此記憶體區塊


## 課後問題

The program `relocation.py` allows you to see how address translations are performed in a system with base and bounds registers. See the `README` for details.

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.

    $ ./relocation.py -s 1 -c
    
    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) --> SEGMENTATION VIOLATION
      VA  1: 0x00000105 (decimal:  261) --> VALID: 0x00003741 (decimal: 14145)
      VA  2: 0x000001fb (decimal:  507) --> SEGMENTATION VIOLATION
      VA  3: 0x000001cc (decimal:  460) --> SEGMENTATION VIOLATION
      VA  4: 0x0000029b (decimal:  667) --> SEGMENTATION VIOLATION

    $ ./relocation.py -s 2 -c

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

    Base-and-Bounds register information:

      Base   : 0x00003ca9 (decimal 15529)
      Limit  : 500

    Virtual Address Trace
      VA  0: 0x00000039 (decimal:   57) --> VALID: 0x00003ce2 (decimal: 15586)
      VA  1: 0x00000056 (decimal:   86) --> VALID: 0x00003cff (decimal: 15615)
      VA  2: 0x00000357 (decimal:  855) --> SEGMENTATION VIOLATION
      VA  3: 0x000002f1 (decimal:  753) --> SEGMENTATION VIOLATION
      VA  4: 0x000002ad (decimal:  685) --> SEGMENTATION VIOLATION

    ./relocation.py -s 3 -c

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

    Base-and-Bounds register information:

      Base   : 0x000022d4 (decimal 8916)
      Limit  : 316

    Virtual Address Trace
      VA  0: 0x0000017a (decimal:  378) --> SEGMENTATION VIOLATION
      VA  1: 0x0000026a (decimal:  618) --> SEGMENTATION VIOLATION
      VA  2: 0x00000280 (decimal:  640) --> SEGMENTATION VIOLATION
      VA  3: 0x00000043 (decimal:   67) --> VALID: 0x00002317 (decimal: 8983)
      VA  4: 0x0000000d (decimal:   13) --> VALID: 0x000022e1 (decimal: 8929)

2. 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?
> 設 Bound Register 為 `930`

    $ ./relocation.py -s 0 -n 10 -l 930 -c

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

    Base-and-Bounds register information:

      Base   : 0x0000360b (decimal 13835)
      Limit  : 930

    Virtual Address Trace
      VA  0: 0x00000308 (decimal:  776) --> VALID: 0x00003913 (decimal: 14611)
      VA  1: 0x000001ae (decimal:  430) --> VALID: 0x000037b9 (decimal: 14265)
      VA  2: 0x00000109 (decimal:  265) --> VALID: 0x00003714 (decimal: 14100)
      VA  3: 0x0000020b (decimal:  523) --> VALID: 0x00003816 (decimal: 14358)
      VA  4: 0x0000019e (decimal:  414) --> VALID: 0x000037a9 (decimal: 14249)
      VA  5: 0x00000322 (decimal:  802) --> VALID: 0x0000392d (decimal: 14637)
      VA  6: 0x00000136 (decimal:  310) --> VALID: 0x00003741 (decimal: 14145)
      VA  7: 0x000001e8 (decimal:  488) --> VALID: 0x000037f3 (decimal: 14323)
      VA  8: 0x00000255 (decimal:  597) --> VALID: 0x00003860 (decimal: 14432)
      VA  9: 0x000003a1 (decimal:  929) --> VALID: 0x000039ac (decimal: 14764)

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?
> 預設的實體記憶體大小為 16 KB，因此在 Bound Register 值為 `100` 時最大的的 Base Register 值為 $16 \times 1024 - 100$
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.