CH6 Virtual Memory
==
###### tags: `計算機組織`

## Introduction
- 盡量避免存取 memory
- 把 RAM 當成 disk 的 cache。
- 動機:
- 可以讓多個 program 更有效且安全的共享 memory
- 可以允許 program 取用超過 primary memory 的記憶體空間。
- 是 disk 裡的 virtual space 跟 main memory(physical memory) 做對應
- CPU 給出的 address 是 virtual (byte) address 不是 memory (byte) address (不是存取 physical memory byte address)
- block 還是最基本單位，但叫做 page。
### virtual space
- virtual space 裡的一個 block 就叫做 virtual page
- 他的編號叫做 virtual page number
- 同時 run 5 個程式，就會有 5 個 virtual space 和 physical memory 做對應。
- virtual memory是一種技術將 virtual space 轉換成 physical memory 的 address。
### physical memory
- physical page
- physical page number

### Swap space
- The space on the disk reserved for the full virtual memory space of process.
- virtual space 是 process 在 swap space 裡的 copy。
- 過度使用 swap space 會造成 swap thrashing。
- 不只在電腦，高階的電腦會把他 copy 到 flash memory 裡面

## cache v.s virtual memory
- page 通常是 4KB。
- block 通常就幾個 word 而已。

- 因為 disk 和 memory 的速度差很多，也就是 miss penalty 造成的
- virtual memory 的整體策略就是避免存取硬碟。
- fully 可以減少 page(block) 的競爭
- 因為我們無法承受 replace 錯誤後的風險，所以使用較保守的 LRU。
- 在 cach block size 太大會造成 miss penalty 太高，太小又會沒有 spacial locality 的好處，導致 miss rate 變高
- 因為移動讀寫頭佔讀取時間的大多數，所以一次拿多一點利用 spacial locality 減少讀取次數。

## 機制
- page table 的起始位置存在 Page Table Register(PTR) 裡面
- CPU 要存取 data 時，給的會是 virtual memory
- 需要將 virtual memory 轉換成 physical address。
- virtual memory 會先被除以 Page offset(Page size) 得到 virtual page number。
- 利用得到的 VPN 查詢 page talbe。
- PTR + VPN 找到 physical page number
- physical page number 和並 offset = physical memory
- 最後就可以取的 data 在 physical memory 的位置。
- 在 memory 裡面，OS 的空間裡面
- 每個程式裡面都有自己的 page table，用 virtual page number 去查
- page offset + physical page number = physical address

### Page fault

- 由 OS 處理，cache miss 是由硬體(cache controller)處理
- 如果 valid bit = 0，透過 ==exception mechanism==
- active v.s inactive : 佔不佔用處理器
- process = program counter + page table + register

### Page table
- about page table
- 儲存 virtual memory 和 physical memory 的資料。
- 存在 memory 裡面 (OS 空間裡面)
- 每個 process 會 maintain 一個自己的 page table。
- 要用 VPN 查
- **valid bit** : 有沒有存在 physical memory 裡面。
- **VPN**: virtual page number
- **PPN** : physical page number
- **reference bit / use bit** :
- page 數太多了
- 使用過這個 page 這個 bit 轉成 1
- OS 會定期把這個 bit 清除成 0。 :arrow_right: approximate LRU
- **dirty bit**: dirty bit 是 1(modified page) 要copy back 回 virtual space

### Page table size calculation

- page table 是放在 main memory 裡面的
- physical address / page offset = PPN
- ==page table 裡 entry 不到一個 word 用一個 word 來裝==，避免計算 page table 裡的 page number時，做乘法運算。

- page offset = page 的大小
- physical address 是 36 bits
- 一個在 page table 裡的 entity 是 26 bits ，但是memory 的一次存取量就是 1 byte，所以是 32 bits
- number of virtual pages = $\frac{2^{40}B}{2^{14}B}=2^{26}$ MB
- $2^{26}\times32$ = 256 MB
- 硬碟位置要比 PPN 長太多了

## Reduce page table size
### One limit register
- 因為 process 實際上不太可能用到那麼多空間
- 預設一個 page size
- 當 virtual page number 大於等於 limit register 時，才動態增加 entry，使 page table 變大
### Two limit register
- memory 是往下長的
- 可以看出 process memory 增長的位置在 stack 和 heap 中間
- 所以用兩個 register 看如果大於 `stack` 或小於 `heap` page 的個數，再增加 entry 進 page table。
- 一個program 會有 2 個 page table
- MIPS 就是用此種方式
### Inverted page table
- 直接紀錄 physical page 被 virtual page 佔據的 state，因為 PPN 小於 VPN
- 有 hash funtion 查看 entry
- 沒比中 page fault approximate LRU
- 如果題目沒說 page table numbers = physical page numbers
### Multilevel of page table
- 每一個 page table 的大小都是一個 page
- 每一層記錄下一層 table 的起始位置。
- 用時間換空間
- 題目問 page table 的大小，就是算全部的大小
- 不是所有的 page table 都在 memory 裡面，用到才會。

### Allow the page to be paged
- 存取和 maintain 的機制跟第四個方法不同
- 把最近用的 page 放在 memory 裡面
- 等到 page fault 再搬要用的 page

- $\frac{4KB}{4} = 1024$
- 4KB + 1024$\times$ 4KB = 4.004 MB

- 32 bits - 8 bits = 24 bits
- $2^{24}\times 16KB$ = 256 GB
- $\frac{2{54}}{2^{14}} = 2^{40}$
- $2^{40}\times 4$ bytes = 4 TB
- 256 GB - $2^{26}$ = $2^{38}- 2^{26}$

## Translation lookside buffer
### Introduction
- TLB 像是 page table 的 cache
- 持續追蹤最近用到的 address，避免存取 page table。
- 用來加速 virtual address 轉成 physical address 的轉換。

:face_with_head_bandage: 因為 page table 是存在 main memory 裡面的，所以需要花兩次的 memory 的存取時間
- memory access to obtain physical address(去存取 page table)
- access to get the data

:face_with_monocle: 因為 entry 的存取也有 locality，位置轉換資訊也會有 locality。

:face_with_cowboy_hat: tips: 1 個 page 可以裝 1 K個指令，因為一個指令是 4 Byte

### TLB 的structure
- 多一個 tag
- virtual page number / cache block 總數
- 商數是 tag
- 餘數是 index
- valid : 是否在 physical memory 裡面
- dirty : 是否要 write back
- reference : 用來決定這個 page 是否要被置換。
- PPN : physical page number

### Direct map 的 TLB 存取模式
- TLB 和 page table 會同時比較
- 如果 TLB miss 去看 page table
- 如果 page table miss，就是 page fault
- 是由誰處理 miss ?
- page fault 由 OS 處理
- 理論上 TLB miss 軟硬體都可以處理，但 MIPs 由 OS 處理，因為 TLB miss 會產生 exception(page fault handle 的時間和 TLB miss 會 overlap)
- cache miss 是由硬體處理。

### TLB size calculation
- TLB 在 SRAM，所以自訂 bit。
- page table 在 memory 裡面，不能自訂
- 通常會給 virtual addrees 和 physical address 的長度
- entry 看不出來就是集合( set )
- VPN / TLB entries 數 = tag

- virtual address = 32 bits
- physical address = 30 bits
- TLB 有 16 blocks
- page size = 4 Kbytes = 12 bits
- VPN = 32 - 12 = 20 bits
- tag = 20 - 4 = 16 bits
- PPN = 30 - 12 = 18 bits
- (2+16+18)$\times$ 16 = 576 bits

## Two way set associative
- 判斷不了是集合還是 entry，所以是 set。

- 64 Kbytes / 128 bytes / 2 = 8
- 32 - 8 - 7 = 17
- D = 128 $\times$ 8 = 1024 bits
- E = 17 + 1 = 18
- H = 13 bits
- G = 9 bits
- F = 64 - 13 - 9 = 42
- I(PPN) = 32 - 13 = 19


## TLB in pipeline

- 一個指令最多會造成 4 次 cache miss
- instruction TLB miss
- instruction cache miss
- Data TLB miss
- data cache miss

## problem
- virtual address $\rightarrow$ VPN
- VPN = $\frac{virtual\space address}{page\space offset}$
- tag = $\frac{VPN}{sets\space amount}$
- index = VPN % sets amount


## TLB miss and page fault 處理
### TLB miss
- only miss in TLB
- not only miss in TLB but also miss in main memeory(page fault)
- 不可能發生的 miss 組合
- TLB hit， page table miss
- cache hit, physical memory miss
- page table hit, physical miss
### Handle
- TLB miss 在 MIPS 裡面由 software (OS)處理 TLB : TLB Exception
- page fault 由 OS 搬到 main memory
- 偵測 (detection) 都由硬體
- miss handle的統整

## Virtual memory with Cach
- vritual address $\rightarrow$ PPN
- PPN + page offset $\rightarrow$ physical address
- phsical address $\rightarrow$ block address
- block address $\rightarrow$ 在 cache 的位置

- full associative cache, direct mapped cache
- 14Kbytes, 64 bytes
- $2^8\times 2^6$ = $2^{14}$ = 16Kbytes
- $2^{32} = 4$ Gbytes
- physical addressed.