# Ch.5-4 Virtual Memory
###### tags: `Computer Organization`, `計算機組織`
## 前言
* virtual memory是為了讓程式有「<font color=blue>自己在用全部、完整的記憶體＆擁有連續的記憶體位址</font>」的錯覺
* 為了讓程式在**實體**記憶體中的任何一個位子都可以運作
當程式要存取記憶體時，就會給他一個virtual address space，這個虛擬記憶體就只有這個程式可以用；程式<font color=red>實際</font>要執行時，才會放到physical address space
* 所以實作virtual memory的時候，要進行「轉換」，讓他可以對應到physical memory位址
* 實際上，disk相對memory就相當於memory相對cache
只是cache只用hardware控制（cache controller）
而virtual memory的管理，需要CPU hardware + OS合作
## 名詞
1. page：virtual memory system中，block放在disk的稱呼
2. frame：virtual memory system中，block放在physical memory的稱呼
3. page fault：virtual memory要的資料不在physical memory中，而在disk中的狀況（如CPU在cache找不到資料，要去memory找，稱為miss的概念）


virtual memory system就是在決定要把disk中的誰放到physical memory中，
或是把physical memory中的誰給replace掉

## Address Translation
:::info
virtual memory都會對應到某個位址，可能是physical memory或disk的。
當一個程式要執行時，如果他的virtual memory address對應到...
* physical memory的某個frame（白色部分），很好
* disk（灰色部分），則稱為page fault
:::
:::info
virtual address sapce的大小是**由處理器的定址能力決定的**
physical address spcae則是依據系統特性（看你掛多大的RAM"吧"）

這個例子中：virtual address有32bit；而physical address為1G大，需要30個bit表示
因為page size是4K，所以virtual address跟physical address都有12bit的page offset（用來表示所需資料在這個page/frame中的哪一個位子）
剩下的bit用來儲存page number

**注意**：因為有可能無法在physical memory中找到資料，所以virtual address也會存disk中資料的位址
:::
### Paging

做address translation就好比mapping
要把virtual address映射到正確的physical address

:::info
圖中流程：
有個程式要動作了，processor產生一個virtual address
(粉框)然後這個virtual address去找對應的physical address
如果有找到，就走a'那條路，直接去physical memory拿資料
如果沒有，就是發生page fault，走$\Phi$那條路，去disk找資料放physical memory
:::
## Basic Issues in Virtual Memory
因為virtual memory也是memory hierarchy的一環
所以也需要討論如`block placement`、`block identification`、`block representation`、`write strategy`的問題
只是有點小改變，變成：
1. Size of data blocks：如何選擇block的大小
2. Placement policy：page應該被放在memory的哪一個位置
3. Replacement policy：physical frame不足時，如何決定換掉誰
4. Demand load policy：把disk的資料搬到frame的時機
（如OS中的demand paping - 需要時才把東西搬進去）
## Block Size and Placement Policy
因為CPU存取一次disk需要花`數百萬個cycle`，所以發生一次page fault的miss penalty很大
為了減少miss penalty，virtual memory中的page size應該要足夠大
為了減少page fault的機率，採用<font color=red>fully associative</font>的placement policy
### Address Translation Mechanism
為了記錄每一個virtual memory對應的位址，需要藉助**table**（圖中右上）
這個table稱為page table，index由virtual memory的page編號表示；資料由virtual memory對應於physical中的哪一個frame表示（-表示在disk中）
圖中下半部分的粉紅框，就是一個轉換virtual跟physical的機制，要借助table完成
#### Example
整個virtual memory的大小是$2^{20}$bytes
每個page的大小是$2^{10}$bytes
問virtual address = 7414的狀況下，在physical memory的哪裡？
:::info
1. $7414/2^{10} = 7414/1024 = 7$
目的在於"求出位於第幾的virtual page"
2. 根據table發現，第7個virtual page對應第5個physical frame
3. $7414\ mod\ 1024 = 246$
目的在於"<font color=blue>求出7414會分布在一個page/frame中的哪個位址</font>"
4. $1024*5 + 246 = 5366$
目的在於"<font color=blue>求出實際位於physical memory的位址</font>"
因為是在physical的第5個frame其中第246個位子，所以這樣算。
:::
### Page Tables
<font color=red>！！**page table很重要**！！</font>

當CPU產生一組virtual address之後，只要用address / page size就可以得出"是在哪一個page"
由此當作index，藉由查詢table，得到frame的編號
並可以由硬體支援，提供一個page table register，指向page table的base address
有了base跟index，就可以把所有的virtual page轉換成physical frame

* 如果找得到對應的frame，就可以把所需資料取出來
且這個page table entry還會存有reference/dirty bit等可供參考
* 如果都沒有對應的frame，page table也可以指引要去哪裡才能找到disk上的page
### Page Fault: What Happens When You Miss?
硬體<font color=blue>無法</font>直接處理page fualt的狀況，所以會由軟體(OS)解決（更準確地說是「不建議用硬體處理」，實務上也不會用硬體處理）
:::info
原因：
1. CPU存取一次硬碟，要數百萬個cycle，很久
但是由智慧/複雜的程式完成，時間花費比較少，也能減少page fault rate
2. OS可以將發生page fault的process進行context-switch
（放入waiting queue，拿別的process到ready queue；等到page fault的狀況結束，才把原本的process重新放回ready queue）
:::
### Handling Page Faults
OS處理page fault步驟：
1. 挑出一個frame丟掉（存回disk，以騰出空間給下一個page）
2. 把page從disk中拿出，載入frame
3. 更新page table
4. 交還控制權給硬體，繼續動作

要做到以上事情，OS必須要：
1. 在disk上騰出一塊區域，能放下一個process所有的page
2. 具有"可以紀錄page在disk哪個位子"的資料結構（如page table），才能有效地找資料
3. 為了要做replacement，要具有"可以記錄process在frame的位址"的資料結構
## Page Replacement and Writes
* 因為存取disk要花費太長時間，所以為了減少要去存取的機會，就要減少page fualt rate。於是會選擇在replacement policy上採用**LRU**
* write strategy的部分也不可能選擇write through，因為這將花掉非常多的時間；所以會採用write-back（用dirty bit紀錄page是否被修改過）
### Page Replacement: 1-bit LRU
概念跟OS中的second-chance algorithm很相似

## Impact of Paging - Huge Page Table
:::warning
virtual memory system中很重要的議題：
**page table size**
:::
假設page的狀況如下：
則每個process的page table都是4MB大，且必須為連續
倘若有很多process同時在執行，將會占滿整個physical memory
所以要如何決定page table size，是很重要的
以下幾個方法：
1. 限制一個小的size，如果不夠用再擴增
2. 給定兩個table，一個從記憶體位址低的往高的成長，另一個則反過來
3. hashing（inverting page table）
4. multi-level page table：把page table切成好幾個小段，就可以不連續
5. paged page table：把page table切成很多小小的一塊，每一塊就是一個page（可以融入virtual memory system方便管理）
### Hashing: Inverted Page Tables
* inverted page table：記錄<font color=blue>在physical frame</font>的page資訊
* page table：紀錄<font color=blue>一個process所擁有的、完整的page所在</font>的資訊
:::warning
inverted page table不是用來取代page table的
inverted page table最大的好處是「節省要用的physical memory」
因為可以把page table存在disk，physical memory存inverted page table就好
:::
:::info
運作方式：
CPU一樣會產生一個virtual address
然後會經過一個hash function存到inverted page table中
當process需要某個資料的時候，優先從inverted page table中尋找，看看裡面已有的physical frame對應的virtual page是不是跟現在需要資料的process所對應的virtual page一樣
如果一樣，就可以直接拿來用；不一樣則page fault
:::
### Two-level Page Tables
:::info
本來一個page size是4KB，也就是12bit
那在32bit的定址能力中，就會剩下20bit用作page number
這裡將他平分，切成10bit、10bit
由第一個10bit形成第一層的page table，指向第二層的page table

* 第一層只有一個page table，包含$2^{10} = 1024$個entry
其中每個entry又各自對應到一個第二層的page table
* 第二層有1024個page table（因為第一層page table有1024個entry）
又因為第二層可以用10bit，所以每個page table又有1024個entry
* 這裡令第二層page table中的每個entry對應到一個page
相當於切成好幾個page table而每個都代表一個page
所以這個例子中的two-level page table也是paged page table
:::
:::info
優點：
可以跟virtual memory system結合，好管理（可以放在physical memory或disk）
也不用擔心page table太大，占掉過多physical memory
:::
:::warning
可以與資料結構中的**tree**比較
第一層page table視為一個node，第二層的page table都是這個node的subtree
每個subtree下又會有1024個subnode，這些subnode就是frame
:::
## Impact of Paging – More Memory Access!

圖中可以發現，因為採用virtual memory system
所以需要存取page table，變相要多存取一次physical memory
由於memory速度比起CPU慢很多，這樣會拖慢速度
所以創造了一個"類似cache"的東西，叫做Translation Lookaside Buffer(TLB)

### Making Address Translation Practical
:::warning
TLB可以視為page table的cache
:::

如果CPU要進行virtual memory accesss
他就會先去TLB看看有沒有用過
運氣好，有用過，就可以從TLB直接得到位址，直接存去cache或physical memory
如果沒有用過（TLB miss），就要去physical memory查詢page table


過去：
CPU產生virtual address之後，只能去看page table，再去找資料

:::info
現在：
經過一次查詢page table去找physical memory或disk的資料後
就把查詢結果存到TLB中

之後如果CPU又產生了virtual address
會率先去找TLB有沒有過去用過的紀錄，如果有，就可以直接得到physical address
如果沒有，才要去page table查詢
好處是：有在TLB的話，可以省去查詢一次page table的時間
:::
:::danger
main concept：
跟cache一樣，都是利用**locality**的性質
:::
#### Translation Lookaside Buffer
通常，採用RISC的CPU都會有一個MMU（memory management unit）專門做記憶體管理，其中會包含TLB、page table lookup等相關事項

下面講述TLB的特質：
1. size不大
2. 可以採用fully associative、set associative、direct mapped
3. miss發生時，可能由硬體或軟體(OS)幫忙處理
#### TLB Hit or Miss
* TLB hit on read
CPU要read的時候TLB hit：直接存取位址＆資料
* TLB hit on write
CPU要write的時候TLB hit：存取位址＆資料，並將dirty bit設為1
（因為日後若發生swap，才知道要把這個page寫回memory或disk）
* TLB miss
可能有兩種狀況：
1. 只是TLB不夠大所以放不下，東西還有在page table中：只要透過硬體或OS幫忙處理即可>>根據page table中的資訊，存取physical memory後順便放入TLB
2. ★☆東西根本不在page table中（也發生了page fault）：只能靠OS幫忙處理>>把合適的page從disk找出，load到frame上☆★
## Page Fault Handler
1. 從disk中的swap區，找出所需資料
2. 從memory中，挑出要replacement的frame
（如果dirty bit = 1還必須要同時寫回disk）
3. 從disk拿出page，放入frame（還要記得更新page table）
## TLB and Cache運作流程
下圖展示了完整的TLB、cache access的過程
下圖是TLB、cache運作的流程圖
可以發現，最糟的狀況是TLB、page table、cache全都miss
下表是TLB、page table、cache的各種狀況
下面三種不可能發生，因為：
1. 不可能TLB hit結果不在page table中；都會是先在page table中，才存到TLB中
2. 不可能TLB miss、page table也miss，結果cache hit；因為前兩者miss代表東西不在memory中，不在memory怎麼可能會在cache中呢

## Summary
記憶體只要大，就慢；可是快，很貴，為了成本只能小
想要又大、又快、又便宜的記憶體，就要採用**memory hierarchy**
因為程式執行時，具有locality的特性，所以可以cache、TLB輔助