# 作業系統CH9 Virtual Memory Management
###### tags: `作業系統 Operating System`

## Background
- 為何我們不希望執行 program 時，將所有內容放進 memory 中
- 有許多程式碼負責不常使用的 erros 或 conditions
- 部份 program routine 不常使用
- 很多 program 使用相同的 library
- 已經配置但沒有被使用的 Arrays, lists & tables
- 我們希望更好的 memory 使用率，真的需要使用的才放入 memory 中
- Virtual memory: 將 user logical memory 從 physical memory 分離
- 因為 logical -> physical 只是 mapping 的問題，所以 logical memory 可以比 physical memory 來的大，可以執行非常大的 process
- 提高 CPU/resources 的使用率，越多 process 在 virtual memory 中，degree 越高，就越容易找到需要某個資源的 process 去使用
- 簡化 compiling 的工作，不需要管 memory 的限制
- 提昇 programs 的執行速度，因為不用將整個 program 讀進 memory，有較低的 I/O load & swap 的負載
- Virtual memory 可以透過以下兩種方式實作
- Demand paging，因為是 fix-size，對硬體使用來說資源分配比較容易管理
- Demand segmentation -> 因 segmentation 大小不固定，要找到空間的複雜度較高，效率較低，但對 user 來說比較容易理解及使用 (heap, stack...etc)
- Virtual Memory vs. Physical Memory

## Demand Paging
### Demand Paging
- 當 Page 被需要時才讀進 memory 中，好處是
- 較少的 I/O 需求 --> 更快的響應
- 較少的 memory 需求 --> 可以有更多 programs 執行
- 當 Page 有 reference 指向它時，代表 Page 被需要
- 若 reference invalid --> abort (沒有 allocate)
- Not-in-memory --> 利用 paging 讀入記憶體 (page fault)
- pure demand paging
- process 啟動時完全沒有 page
- 只有當 page 需要時才讀進 memory
- swapper (midterm scheduler) 管理整個 process ，而 pager 則是管理 process 的一個 page 為單位
- 硬體支援
- Page Table: valid-invalid bit 來表示 page 是否在記憶體中
- 1 -> page in memory
- 0 -> page not in memory
- 一開始該 bits 都設成 0
- Secondary memory (swap space, backing store): page 從 memory 被 swap 出去的儲存空間，通常是 high-speed disk

### Page Fault
相關資料:[MIT6.s081 Lab: xv6 lazy page allocation](https://hackmd.io/@Chang-Chia-Chi/SyVVrPBRt)
- 第一次的 reference 會引發 trap to OS
- 稱為 page fault trap
1. OS 會查看在 PCB 裡頭的 internal table ，確認是 Invalid 或只是 not in memory，決定後續動作
2. 找到一個 empty frame (可以置放 page 的空間)
3. 將 page 從 disk (swap space) 移到 frame
4. 設定 Page-table，將 valid-invalid bit 設為 1
5. 重啟 instruction

### Page Replacement
- 若 page fault 時沒有 free frame 的話
- Swap 一個 frame 回 backing store
- Swap 目標 page 進 frame

### Demand Paging Performance
- Effective Access Time (EAT): $(1-p) * ma + p * pft$
- p 為 page fault rate, ma 為 mem. access time, pft 為 page fault time
- mem. access time 包含找到位置及將資料從 memory chip 搬到 CPU register 的時間
- page fault time 則多了資料在記憶體 - disk 之間 swap 的時間
- pft 遠大於 ma，EAT 基本上由 pft 及 page fault rate 決定
- 假設 ma = 200 ns, pft = 8 ms，若 1000 次產生 1 次 page fault，則速度就會慢上 40 倍 ; 換個角度如果我們希望 page fault 對讀取時間的影響小於 10%，則 page fault rate 必須小於 0.0000025
- Programs 的 refernce 通常是 locality 的，代表 program 通常會存取在鄰近位置的 memory address
- 一個 page fault 可以讀取 4KB 的資料進來
- 大幅降低 page fault 發生的機率
- Page fault time 的時間組成
1. page-fault 中斷
2. 將 page 從 disk 中讀進 memory (最花時間)
3. 重啟 process

## Process Creation
### Process & Virtual Memory
- Demand Paging: 當有需要時才 swap page 進 memory
- Copy-on-Write: parent 跟 child processes 一開始共享 frames，當有內容發生不同時，才會 copy frame
- Memory-Mapped File: 將 file 的 disk content 當作 memory content，用 virtual address space 做 mapping，避開 file system，增加 I/O 效能。通常適用於大檔案，因為 paging 需要 4KB 的空間，小檔案使用會有記憶體空間碎片化的問題

### Copy-on-Write
相關資料:[MIT6.s081 Lab: Copy-on-Write Fork for xv6](https://hackmd.io/@Chang-Chia-Chi/BkMAP0Hk5)
- 允許 parent & child 共享 frames
- 若其中一者變更 frame，則僅對該 frame 進行 copy 的動作
- COW 使得 process creation 有效率(e.g. fork())
- 通常 free frame 時會完全清空，避免前一個 process 使用的一些 content 被其他 process 看見，造成潛在的安全性問題
- When a child process is forked
- After a page is modified

### Memory-Mapped Files
- 方法：
- MMF 透過 disk block to memory frame 的 mapping，讓 I/O 像一般的記憶體存取，略過 file system calls (eg. read(), write())
- file 一開始使用 demand paging 讀取，之後的讀寫動作視作一般的 memory access
- 好處：
- 略過 file system calls (如 read(), write())
- 允許多個 processes 共享 file 的內容

- 壞處：
- 安全性、資料遺失、更多的 programming efforts

- 範例：

## Page Replacement
Page Replacement 的演算法會嚴重影響系統的速度，假設演算法經常將需要用到的 pages swap 去 disk，則 pages 在 memory 跟 disk 一直來回的時間會大幅拖慢系統的效能
### Page Replacement Concept
- 當沒有 free frame 時發生 page fault
- 將整個 process swap 掉，釋放所有 process 佔有的 free frames，但這樣 process 就完全不能使用，並不是一個好方法
- 採用 page replacement ，找到一個目前沒有被使用的 frame 將其 free 掉
- 使用 dirty bit 表示 page 的內容是否被修改過，若 page 沒有被修改過，就直接 free 掉 frame 的內容; 有修改過才將資料寫回 disk ，來減少 page transfers 的 overhead，
- replacement 必須要處理兩個問題
- free-allocation algorithm: 演算法必須決定多少 frames 應該 allocate 給 process
- page-replacement algorithm: 選擇哪些 frames 被取代
### Page Replacement Step
1. 在 disk 中找到需要的 page
2. 若有 free frame，則直接使用; 若沒有 free frame 則執行 page replacement 演算法來選擇被取代的 frame
3. 將需求的 page 讀進 free frame 中，並更新 page & frame tables
4. 重啟 process 的指令

### Page Replacement Algorithms
- 目標：最低的 page-fault rate
- 評估：一連串的 page id (reference string, memory refernces) 為輸入，計算 page fault 發生的次數

#### FIFO algorithm
- 在佇列中最舊的 page 會被取代
- 範例：
- 假設 available memory frames = 3
- 產生 9 次 page fault
- Belady's Anomaly: 即便增加 frames 的數量，page fault 的數量不一定會減少，還有可能會增加
- 假設 available memory frames = 4
- 產生 10 次 page fault
- 因為 Belady's Anomaly，使得我們很難對系統進行調整，例如插越多條記憶體，反而執行速度有機會變慢

#### Optimal (Belady) Algorithm
- 取代未來最長時間不會被使用的 page
- 但實際上我們不會有未來的資訊
- 因此這個演算法比較類似提供我們一個基準

#### LRU Algorithm (Least Recently Used)
- 一種 optimal algorithm 的近似
- 因為無法預測未來，所以我們往回看
- 取代最長時間沒有被使用的 page
- 因為 locality 及時間複雜度低(O(1))的緣故，LRU 很常被使用
- Counter implementation
- 紀錄每個 page 最近被使用的 time-stamp
- 取代 time-stamp 最舊的 page
- 時間複雜度 O(N)
- Stack implementation (實際使用)
- 當 page 被使用時，將 page 移到 double-linked list 最前方
- 可以用 hash map 紀錄 double-linked list 每個 element 的指標，達成 O(1) 的實作
- 取代 linked list 中位在 tail 的 page

#### Stack Algorithm
Optimal & LRU 都是 stack algorithm，有以下這些特性
- n frames 的 pages 一定是 n+1 frames pages 的 subset，也就是說因為 stack 的特性，先被放入的元素一定會先被看到，若增加 frames，也只是在原 stack 後面增加一些 pages 而已
- Stack algorithm 不會有 Belady's anomaly 問題

#### LRU 近似的演算法
- additional-reference-bits algorithm
- second-chance algorithm：2 個 LRU stack
- enhanced second-chance algorithm

#### Counting Algorithms
- LFU Algorithm (least frequently used)
- 每一個 page 有 counter
- 經常被使用的 page 應該要有大的 count value
- MFU Algorithm (most frequently used)
- 不過常用不代表正在用，有可能在某些時刻集中使用，將 count 拉高，但多數時間沒有使用
- 最小的 count 有可能是剛帶進來的，還沒被使用，所以應該留著
- 兩者都不常用
- 要一直執行加法成本很高
- 有 overflow 的問題
- 表現不一定較佳

## Allocation of frames
每個 process 最少都需要一定數量的 frames
### Frame Allocation
- Fixed allocation: 根據 process 在一開始就決定要 allocate 多少 frame
- Equal allocation: 每個 process 配置到的 frames 數目相同
- Proportional allocation: 根據 process 的大小來配置
- Priority allocation
- 在 run time 的時候，根據 process 的優先度決定配置
- 如果 process 發生 page fault
- 選擇 process 本身的一個 frame 來替代
- 或著選擇低優先度的 process 的 frame 來替代
- Local allocation: 只能替換自己的 frames，通常跟 fixed allocation 綁在一起
- Global allocation: 從所有的 frames 中選擇一個來替代
- 可以拿其他 process 的 frame
- 例如讓高優先度的 process 搶低優先度的 process
- 有好的系統表現，所以較常使用
- 會有一個問題是如果一直搶低優先度 process 的 frame，有可能該 process 甚至無法維持最低的 frames 數量，所以要有機制來維持最低 frames，避免 process 被 thrashing

## Thrashing
如果一個 process 沒有足夠的 frames，代表 process 在記憶體中的 frames 數量不足以支撐 process 執行，導致 page fault 一直在發生 (且 page fault 是 instruction level，無法 overlap)，等於 CPU 要一直等待 I/O，造成 CPU 使用率反而下降的情況

- Thrashing 的定義為： 當一個 process 花在 paging 的時間比執行時間更高時，稱為 thrashing


- Thrashing 造成的 performance 問題
- processes 因 page fault 在等待 I/O
- 因此 CPU 使用率下降
- OS 發現 CPU 使用率下降，增加 degree of multiprogramming
- 新產生的 processes 從舊的 processes 搶 frames，導致更多的 page fault
- 結果 CPU 的使用率繼續下降
- 為了避免 Thrashing，必須要控制 degree of multiprogramming

### Working-Set Model
- 從 Locality 的角度思考，對一個 process 而言，我們可以計算在這段時間內使用多少 pages，這個數量就是要 assign 給 process 的 frames 數量
- 因為 process 的需求是動態變化的，所以 locality 會隨時間改變，OS 必須要持續追蹤 processes 的 locality
- 例如 program structure (如 subroutine, loop, stack)
- 或 data structure (array, table...etc)
- Working-set Model
- Working-set window: 觀察的一段時間
- Working-set size: 這一段時間內，被 process reference 到的 page 數
- 每一個 process 的 working set size $WSS_i$
- frames 的總需求數 $D = ∑ WSS_i$
- 如果 D > m (available frames) ，則有 thrashing 發生
- OS 會監控每個 process 的 $WSS_i$，並配置足夠的 frames 給每個 process
- 如果 D << m，增加 degree of multiprogramming
- 如果 D > m，把整個 process suspend (mid-term scheduler) 掉，free 該 process 所有的 frames
- 優點
1. 在最大化 multiprogramming 的情況下，同時防止 thrashing 的發生
2. 可以最大化 CPU 使用率
- 缺點
1. tracking 的成本很高

### Page Fault Frequency Scheme
- 監控每個 process 發生 page fault 的機率，控制 page fault rate 在一定範圍內來防止 thrashing 的現象
- 依據 page fault rate 為每一個 process 建立 upper 跟 lower bounds
- 如果 page fault rate 超過 upper limit，則配置更多的 frames
- 如果 page fault rate 低於 lower limit，則移除部份的 frames

### Working Sets and Page Fault Rates
重點是 memory 的 locality 會變化，所以需要追蹤 process 的使用情況，動態地調整 processes 及 frames 的配置情況


## Reference
1. [清大開放課程 - 作業系統](https://www.youtube.com/watch?v=aK0_PBLWCAM&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV&index=38)
2. [Operating System Concept 9th edition](https://www.os-book.com/OS9/slide-dir/index.html)