# Chap. 09 - Virtual memory management
> 課程內容 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
**Note:** [#Copy-On-Write](#Q-請說明何謂-Copy-On-Write-COW) [#page replacement](#Q-為什麼需要做到-page-replacement-) [#thrashing](#Q-請簡單說明-thrashing-的定義與解決方式)
## Content
* [Background](#Background)
* [Demand paging](#Demand-paging)
* [1. Demand paging](#1-Demand-paging)
* [2. Page fault](#2-Page-fault)
* [3. Page replacement](#3-Page-replacement)
* [Process creation](#Process-creation)
* [1. Copy-on-write](#1-Copy-on-write)
* [2. Memory-mapped files](#2-Memory-mapped-files)
* [Page replacement](#Page-replacement)
* [1. Concept](#1-Concept)
* [2. Page replacement step](#2-Page-replacement-step)
* [3. Page replacement algorithm](#3-Page-replacement-algorithm)
* [3.1 FIFO algorithm](#31-FIFO-algorithm)
* [3.2 Optimal algorithm](#32-Optimal-algorithm)
* [3.3 LRU algorithm](#33-LRU-algorithm)
* [3.4 Counting algorithm](#34-Counting-algorithm)
* [Allocation of frame](#Allocation-of-frame)
* [1. Frame allocation](#1-Frame-allocation)
* [Thrashing](#Thrashing)
* [1. Definition](#1-Definition)
* [2. Thrashing](#2-Thrashing)
* [2.1 Working-set model](#21-Working-set-model)
* [2.2 Page fault frequency scheme](#22-Page-fault-frequency-scheme)
## Background
> Why we don't want to run a program that is entirely in memory ?
> * 大部分的 code 都是在處理**不常見的錯誤**或**例外機制**
> * Program 中大部分的區塊比較少用到
> * 多數 program 都會用到**相同的 library**
> * **陣列**被分配到空間常常沒有用到
上述的前三種狀況都可以用 dinamic linking/loading 解決，但第四個能夠用 virtual memory 解決。
> [!Note]
> 使用 virtual memory 的目的是要有**更好的記憶體使用率**，甚至是更好的減少 access 的次數。
Ｖirtual memory 是把硬碟(disk)當作記憶體的延伸儲存空間。將 user logical memory 與 physical memory 分離，讓 user 可以使用連續的記憶體空間，不受 physical space 的大小限制。
優點：
(1) To run a extremely large process
因為 logical space 比 physical space 大很多
(2) To increase CPU utilization
能夠使用的記憶體空間變大，可以提供給更多的 process 使用，提升 **degree of multi-programming**。
(3) To simplify programming task
使用者不會受到 memory space 的限制
(4) To run programs faster
較少的 I/O 運算可以提升 program 的速度。因為若沒有 VM 就會需要載入完整的 program。
> [!Note]
> 從 disk 重新移動到 memory 的動作不是載入(load)
常用的方法有兩種：
* Demand paging(較常見)
* Demand segmentation
## Demand paging
### 1. Demand paging
Process 在使用前並**不會**一次性的載入到記憶體中，而是**以 page 為單位**，當某個 page **有需要**時才會由 swapper 載入至記憶體中，優點有二：
* 需要較少的 I/O 運算，提升速度
* 需要較少的記憶體空間，能夠讓更多 program 執行
---
Q：何謂需要某個 page 的時候？
A：當 CPU 引用(reference)某個 page 的時候
有兩種會導致 reference 失敗的情況(page fault)
* Invalid reference
* 指的是 logical address 對應到的 page 是無效的(Ex: 超過大小)
* Not-in-memory
* 引用的 page **尚未載入**到記憶體中
有一種最簡單的方式，稱為 pure demand paging。當 process 開始執行的時候不會載入任何的 page 到記憶體中，只有當某個 page 有需要時才會將其載入。但這種方法在程式剛開始執行的時候會持續的發生 not in memory 的錯誤。
> [!Note]
> What is reference ?
> CPU 嘗試存取(access)某個記憶體位址中的內容，通常是讀取或輸入的請求。
Demand page 的實作會仰賴下面幾種 hardware 的支援
* 會在 page table 上使用一個 valid-invalid bit 表示該 page 是否在記憶體中：
* = 1：表示 page 在記憶體中
* = 0：表示 page 不在記憶體中
* page 載入時一開始都會將所有 bit 設為 0
* Second memory(backing store)
* 用來存放**尚未載入**到記憶體中的 page
如下圖所示，一開始執行時是沒有載入任何 page 到記憶體中，每個 page 的 valid-invalid bit 都設為 0，只要在載入後才會設為 1。
<img src="https://hackmd.io/_uploads/rktDYMVIJx.jpg" width=500>
> [!Important]
> 連結 process 的五大生命週期(new, ready, running, terminated, waiting)。OS 在一開始的 new 階段並不會把完整的 program 從硬碟載入到記憶體中，而是完成以下幾件事：
>
> * 載入 process control block
> * 載入基本的 code segment
> * 初始化 page table(valid-invalid bit = 0)
>
> 之後就將 process 送入 ready queue 等待執行，執行過程中如果需要引用某個尚未載入的 page，才會再載入到記憶體中。
### 2. Page fault
引用(reference)某個 page 時發生錯誤的狀況稱為 **page fault**，此時 hardware 會發出一個 trap 通知 OS 介入。Page fault 的整體流程如下：
* OS 會**檢查 PCB**，判斷是哪種問題引發 page fault
* Invalid reference，直接終止
* Not in memory，繼續往下面步驟執行
* 從 **frame list** 中找到一個 free frame
* 從硬碟中的 swap space 中把 page 移動(swap)到 free frame 中
* 重新設置 page table 中的 valid-invalid bit = 1
* 再次執行 instruction
### 3. Page replacement
當 frame list 中**沒有可用的 free frame** 時，需要**強迫**從現有的 frame 中踢出一個 page 到硬碟中，並與 backing store 中的 page 交換，這個過程稱為 **page replacement**。需要注意的重點是，移除的 frame 要**怎麼選擇**。(後面會提到)
> [!Note]
> backing store：在硬碟中某個用來執行 swap 的特殊的空間
## Process creation
與 process 還有 virtual memory 相關的重要概念與技術有三個
* Demand paging
* Copy-on-write
* Memory-mapped file
### 1. Copy-on-write
Copy-on-write(COW) 是針對 `fork()` 的行爲。當使用 `fork()` 創建 child process 時，child process 會複製一份**與 parent process ==完全相同==的資料**，但這樣的動作非常**浪費記憶體**空間。
所以 COW 的方法只會讓 parent 與 child **共享==相同==的記憶體**內容(i.e., frame)，只有當其中一個 process 的 frame 需要修改時，才會**複製==需要修改==的 frame**，節省使用空間。
如下圖所示(搭配程式碼)，一開始使用 `fork()` 創建 child process 時會回傳一個 process ID(`pid`)，此時 parent 與 child 是直接共享 frame，不用另外複製。
```c=
#include <stdio.h>
void main(){
int pid;
pid = fork();
```
<img src="https://hackmd.io/_uploads/SyghctM48yg.png" width=600>
當某個 process 的內容被修改時，才會**複製**一個 page 的內容
```c=+
in (pid != 0){ // parent
int test1 = 0;
}
printf("process ends");
}
```
<img src="https://hackmd.io/_uploads/SkIJcMV8Jg.png" width=600>
> [!Tip] **Interview Ques.**
> ##### Q: 請說明何謂 Copy-On-Write (COW)
> 當 child process 被創建後會與 parent process 共享同一個 page。當其中一方試圖對共享的 page 寫入資料時會觸發 page fault 並將這個 page 複製一份，讓寫入方有屬於自己的副本。這種設計的目的在於能有效節省記憶體空間。
### 2. Memory-mapped files
讓 user 透過 memory access 的方式(i.e., like array access)做檔案的 read/write，而不是透過 fread/fwrite 等 system call 的方式進行。簡單來說就是把檔案的 bytes stream 放到記憶體之中，直接從記憶體讀取檔案的二進制內容。
優點：
* 速度更快
* 更容易做到 sharing
缺點：
* data lost(因為記憶體是揮發性的儲存裝置)
## Page replacement
### 1. Concept
當 page fault 發生且**沒有** free frame 可以使用時，必須先**移除**某些 frame 才能載入需要的 page，有兩種移動方式：
* 移動(swap out)整個 process 的 frame
* Page replacement：挑選一個**現在沒在使用**的 frame 並釋放它
* 使用一個 **dirty bit** 來記錄 page 載入到記憶體後**有沒有被修改過**
* 如果有**被修改**過，則釋放時需要將**修改後的資料==寫回 disk 中==**
* **沒被修改**過可以**直接釋放**
* Dirty bit 的目的是加速 paga transfer 的速度
> [!Note]
> Process 在執行時只是把它從 disk 複製一份到 memory 中，使用完再寫回 disk。但其實很多時候 process 只有做讀取，在記憶體中是沒有被修改的。
Demand paging 兩大需要考慮的問題 :
* Frame-allocaiton algorithm：決定每個 process 可以被**分配到多少的 frame**
* Page-replacement algorithm：決定**哪個 frame 要被替換**
### 2. Page replacement step
* 找到造成 page fault 的 page(i.e., desired page)在 disk 中的位址
* 尋找 free frame
* 有 free frame 就直接使用
* 沒有則使用 page replacement 選擇要被替換的 frame
* 將 desired page 載入到新的 free frame 並更新 page table
* 再次執行 instruction
### 3. Page replacement algorithm
常見的 page replacement algorithm 有以下幾種：
* FIFO algorithm
* Optimal algorithm
* LRU algorithm
* Counting algorithm
* LFU
* MFU
不論是哪一種，最終**目的都一樣**，希望**最小化 page fault 發生的機率**。以下的介紹中 page 的引用順序都是以 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 為例，並假設有 3 個可用的 free frame。
#### 3.1 FIFO algorithm
First-In-First-Out(FIFO) algorithm，類似 queue 的概念，**最先載入**的 page 會最**先被替換**，如下圖所示，紅字表示引用該 page 時發生了 page fault。
(註 : frame/page 在 memory 中的順序不重要)
* Reference page 1：<font color="ff0000">page fault</font>
* 一開始因為沒有載入任何的 page，所以會發生 page fault
* Reference page 2：<font color="ff0000">page fault(同上)</font>
* Reference page 3：<font color="ff0000">page fault(同上)</font>
* Reference page 4：<font color="ff0000">page fault</font>
* page 4 不在 frame 中，同樣發生 page fault
* 但此時 frame 已經滿了，無法直接載入 page 4
* 需要先**踢掉 page 1(first in)**，再**載入** page 4
* Reference page 1：<font color="ff0000">page fault(同上)</font>
* Reference page 2：<font color="ff0000">page fault(同上)</font>
* Reference page 5：<font color="ff0000">page fault(同上)</font>
* Reference page 1：nothing
* page 1 已經在 frame 中，直接使用
(後續省略)
整體來說會發生 9 次的 page fault
> [!Note]
> **Belady's anomaly**
> 理論上，增加 frame 的數量可以使 page fault 次數減少，但實際上不會減少，甚至有可能增加。
> 
#### 3.2 Optimal algorithm
**最晚被使用**到的 page 會**先被踢出去**。但這個方法是**不可能**做到，因為需要知道**未來的使用順序**才有可能找到最晚被使用到的 page。
> [!Note]
> Optimal algorithm 是理論上的最佳解，可作為 baseline 比較。
如下圖所示，以 1, 2, 3, 4, 1, 2, **5**, 1, 2, 3, 4, 5 的 reference order 為例：
* Reference page 1：<font color="ff0000">page fault</font>
* Reference page 2：<font color="ff0000">page fault</font>
* Reference page 3：<font color="ff0000">page fault</font>
* Reference page 4：<font color="ff0000">page fault</font>
* Reference page 1：nothing
* Reference page 2：nothing
* Reference page 5：<font color="ff0000">page fault</font>
* 目前的 frame 中有 page 1, 2, 3, 4
* 在未來 page 4 最晚被用到，所以先踢掉他
* 再載入 page 5
(後續省略)
整體而言會發生 6 次的 page fault
#### 3.3 LRU algorithm
Least Recently Used(LRU) algorithm 與 optimal algorithm 相反，是回頭找**最久沒被使用**的 page 替換掉。普遍最常用的一種方式，效果通常是最好的。有兩種實作方式：
* Counter implement
* 每當一個 page 被引用(reference)時，會將對應的 **time stamp**(時間戳記)存入計數器(counter)之中。當需要替換時再**尋找最久的** counter
* 缺點是需要一個 linear search 來尋找最久的 counter
* Stack implement
* 會以 hash map + double linked list 實作
* 每當一個 page 被引用，會將**該 page 移動到 ==double linked list== 的頂端**(top)，需要**替換時再從==底端==(bottom)移除==最久==沒被使用**的
(下圖為 stack implement 的圖解_
* Reference page 1：<font color="ff0000">page fault</font>
* Reference page 2：<font color="ff0000">page fault</font>
* Reference page 3：<font color="ff0000">page fault</font>
* Reference page 4：<font color="ff0000">page fault</font>
* Reference page 1：nothing
* page 1 **再次**被使用，**移動到 top 端**
* Reference page 2：nothing
* page 2 再次被使用，移動到 top 端
* Reference page 5：<font color="ff0000">page fault</font>
* page 3 再 bottom 端最久沒被使用，**移除**後換成 page 5
* Reference page 1：nothing
* page 1 再次被使用，移動到 top 端
(後續省略)
> [!Note]
> **Stack algorithm do not suffer from Belady's anomaly**
>
> 當 stack size 變大時，表示 frame 數量增加，此時原來的 page 一樣會再裡面，所以 page fault 不會變大。
#### 3.4 Counting algorithm
Counting algorithm 是**以==使用次數==為主**的演算法，分為兩種
* Least Frequently Used(LFU) algorithm
* 踢掉**使用頻率最低**的 page
* 核心想法：因為使用頻率越高的 page 代表**越活躍，越常被使用**
* Most Frequently Used(MFU) algorithm
* 踢掉**使用頻率最高**的 page
* 核心想法：目前頻率最高，可能只是在某個時間點頻繁使用到，在**未來可能不再使用**
> [!Tip] **Interview Ques.**
> ##### Q: 為什麼需要做到 page replacement ?
> 因為記憶體空間有限，當 process 需要載入新的 page 但所有的 frame 都被佔用時就必須選擇一個現有的 page 與要被載入的新的 page 作替換。
>
> ##### Q: 請舉幾個你知道的 replacement 的演算法 ?
> Page replacement 的重點是要選擇要釋放哪一個現有的 page
> * FIFO: 先被載入的 page 先被釋放
> * LRU: 最久沒被使用到的 page 先被釋放
## Allocation of frame
前面只考慮單一 process 替換的問題，接下來要考慮的是**多個 process 的使用**，包含==每個 process 應該被分配到多少的 frame==。
### 1. Frame allocation
(1) Fixed allocation：每個 process 分配固定的 frame，可細分為兩種
* Equal allocation：所有的 process 均分全部的 frame
* 假設 100 frames 與 5 process，則每個 process 可以分配到 20 個 frames
* Proportional allocation：**根據 process 的大小==按比例==分配** frame 的數量
(2) Priority allocation：**根據 process 的優先度**來分配
當 procecss 發生 page fault 時的處理方式如下：
* 先從自己的 frame 中替換(replacement)
* 如果自己的無法替換，再從其他較低優先度的 process 替換
(3) Local allocation
* Process 從自己的 frame 中選擇要替換的 frame
* 通常與 fixed-allocaiton 搭配使用
(4) Glocal allocation
* Process 能夠從其他的 process 中選擇要替換的 frame
* 通常會搭配 priority 使用，是比較常見的方式
## Thrashing
### 1. Definition
當 page fault 發生時，需要從 disk 讀取資料到 memory，此時 CPU 需要做 I/O 運算。當 page fault 頻繁發生，則 CPU 處理 I/O 的時間就會變長，根本原因就是**沒有足夠的 frame 可以使用**。
> Definition
> A process is thrashing if it is spending more time paging than executing
> [!Tip] **Interview Ques.**
> #### Q: 請簡單說明 thrashing 的定義與解決方式
> Thrashing 是指因為記憶體空間不夠導致 process 頻繁發生 page fault，OS 必須不斷進行 page replacement 導致 CPU 大部分時間都在處理 replacement 的操作，讓效能急劇下降。
>
> ##### Q: 該如何解決 ?
> 因為 thrashing 常發生在多工(multi-programming)系統中，因為系統允許可執行的 process 太多，所以可以選擇降低多工的程度(degree of multi-programming)來避免 thrashing。
### 2. Thrashing
當發生 thrashing 的時候，通常會進入一個**惡性循環**，導致 CPU 效能降低
1. Process 在 waiting queue **等待 I/O** 做 swap(page fault)
2. CPU **使用率下降**
3. OS **增加 degree of multi-programming**
4. 新的 process 從舊的 process 之中**拿取更多的 frame** 使用
5. **更多的 page fault** 與 I/O
6. CPU **使用率再度降低**
從此不斷惡性循環。通常 thrashing 發生的時候，performance 通常會**劇烈下降**。要預防 thrashing 的發生，必須**提供足夠的 frame 使用**，有兩種方式：(1) working-set model (2) Page fault frequency
#### 2.1 Working-set model
> [!Note]
> Process 在執行時會有**局部性**(locality model)，在**某段時間內都會使用到==同一個區塊==的 page**，執行結束後再移動到其他區塊的 page 執行。例如：loop、stack、array 等結構都有這種性質
Working-set mode 是利用 process 的 locality model 性質來預防 thrashing 的發生
* Working-set window, $\Delta$：一段時間內所有 page 的集合
* Working-set, $WS(t)$：最近 $\Delta$ 個 page reference 中的 page 集合
以下圖為例，假設 $\Delta = 10$
針對 working-set size 的設計，可以預防 thrashing
* WSS$_i$：working-set size for process $i$
* D = $\Sigma_i$ WSS$_i$ (所有 process 需要的 frame 數量)
* m = 可取得的 frame 數量
* 若 D > m 則會發生 thrashing
* OS 會監督每個 process 的 WSS$_i$，並且分配足夠的 frame
* 若 D << m：可以增加 degree of multi-programming
* 若 D> M：停止 process 預防 thrashing
(但此方法實作不易)
#### 2.2 Page fault frequency scheme
另一種方式是**從 page fult 的角度**出發，將 page fault 的發生率控制在一定的範圍內
* 當 page fault rate 超過上限，則分配更多的 frame 給 process
* 當 page fault rate 低於下限，則從 process 中拿走多餘的 frame
Sign in with Wallet
Connect another wallet