---
# System prepended metadata

title: OS-Chap9 - Virtual Memory_虛擬記憶體
tags: [作業系統 Operating System note, 110-1, 寫完了寫完了寫完了好快樂, '2021']

---

# OS-Chap9 - Virtual Memory_虛擬記憶體
###### tags: `作業系統 Operating System note`, `寫完了寫完了寫完了好快樂`, `110-1`, `2021`
# Contents
[TOC]

---
# Background
- 為何要有 Virtual memory
> - 程式在被 CPU 執行之前，必須先把程式的內容載入到到一段 **連續的記憶體空間**
> - 如此一來 CPU 才能根據記憶體中的的程式一行一行執行下去
> - 同時開啟很多應用程式時，記憶體會長的像下面這樣
> ![](https://i.imgur.com/luvHwlo.png)
> - 之後每當有新啟動的程式，系統就會從剩餘的記憶體中分配一段 連續的空間 給他，而若有程式結束了，那系統也會把他佔用的記憶體清除掉
> - 雖然這個做法聽起來很美好，但實務上卻很常遇到 **記憶體碎片化** 的問題
> - 記憶體碎片化 = Memory Fragmentation
>     - 雖然剩餘 total memory space 夠大，但因為這些 space 被切割成大大小小的區塊，導致**沒有一段足夠大的連續空間可以使用**
>     - ex. 原本我的記憶體最右側還剩下 3GB 可以使用
>    ![](https://i.imgur.com/wy9gpzP.png)
>    此時如果把 VSCode 關掉，就會有 6GB 的 free memory space
>    ![](https://i.imgur.com/4wMnDXi.png)
>    - **即便有 6GB 的 free memory，但如果現在想打開 ==4GB== 的 Minecraft 來玩，系統就會因為==找不到連續的 4GB 而無法開啟==**
>> - 一般在使用電腦時，程式都會開開關關，所以碎片化的問題*會越來越嚴重*。雖然看似有很多 free memory，但因為這些空間太碎了，所以什麼程式都開不起來。

# Chapter Objective
- **虛擬記憶體 (Virtual Memory)** 會**讓應用程式認為其擁有連續可用的記憶體（一個連續完整的位址空間）**。
- #### 實際上，其通常是==被分隔成多個實體記憶體碎片==，還有*部分暫時儲存在外部磁碟記憶體上*，==需要時才進行資料交換==。
- 通常 Virtual Memory Space > Physical Memory Space
    ![](https://i.imgur.com/enjKRxB.jpg)
- Benefit
    1. 增加 CPU/resource utilization
        - 每個 processes 在 running 時，不會同時使用到整段 process 的 code，所以只需要占用少量的 physical memory space(RAM)，因此同一時間內可以執行更多 program。
       > - 相對提高 CPU 使用率和輸出量，也不會增加 response time 和 turnaround time。
    2. 可以執行一個 extramely large 的 process。
        - 因為通常 Virtual Memory Space(Logical address space) > Physical Memory Space
    3. /* 看不懂 ppt......wwwww */
    4. 讓 program 執行得更快
        - 較少的 I/O 要被 load/s 或是要將 process 搬上搬下


# Implementation method
###### - Virtual address space 是以 logical 的觀點看 process 如何存放在記憶體
- #### virtual memory 的實作方式有兩種，demand paging 跟 demand segmentation。
1. Demand paging -> 有需求再 paging，因為是 fix-size，對硬體使用來說資源分配比較容易管理。
2. Demand segmentation -> 因 segmentation 大小不固定，要找到空間的複雜度較高，效率較低，但對 user 來說比較容易理解及使用 (heap, stack…etc)。

## Copy-on-Write(COW) 
>   #### 有作業！ :star: :star: :star:
- 是一種最佳化策略。
- 在 copy-on-write 策略中如果**有多個呼叫者(processes) 同時要求相同資源（如記憶體或磁碟上的資料儲存）**，則他們會**共同取得指向相同的資源的 pointer**。
- 直到==某個呼叫者(child/parent process)試圖**修改**資源的內容時，**系統才會真正複製一份專用副本給該呼叫者**==，而其他呼叫者所見到的最初的資源仍然保持不變。
- 用網路的例子來解釋一下吧！ ![](https://i.imgur.com/FphdWpF.png)
    - 解釋一下下下下下：
        - fork() 作為一個 function 被呼叫，==這個函數會有兩次返回==，將 child process 的 PID 返回給 parent process ，==0 返回給 child process==。
            (如果小於 0，則說明創建 child process 失敗)。
            (如果大於 0，則表示此 process 為 parent process)。
        - 當前 process 調用fork()，會創建一個跟當前 process 完全相同的 child process (除了pid)，所以 child process 同樣是會執行fork()之後的 code。
- 再來看一下課本的例子。
1. ![](https://i.imgur.com/LzJ7aIr.png)
    ⊙ A 呼叫 fork() 產生一個 child process
    ⊙ 依照 COW 策略，在 child 或 parent process 改動(寫入write/modificate) shared memory 前，兩個 process 共用相同的 memory。
2. ![](https://i.imgur.com/lcr6P2O.png)
    ⊙ 因為 parent process 試圖改動兩者共用的 memory，所以會複製一個相同的 memory 給 parent process 使用。
- 因此，將 copy-on-write 應用在 parent fork child process 時，==**只有 child process 改變 page 內容**時，**才配新 frame (copy)**==，如此一來可以增加建立 process 的效率，因為大部分情況 child process 只會讀取 parent process 的內容，並不會對資料段寫入。


## demand paging
### concept
- 以 paging 為基礎來應用。
- 使用 lazy swapper 的方法：
    - 當 page 被需要時(在被 read/write時)，才把 page swap 進去，而==這個是由 pager 所決定的==。
>     程式執行之初，不會將全部的 Pages 全數載入 MM 中，而是僅載入執行所須的 Pages 到 MM 中，其餘的 Pages 全數置於 Blocking Store中。若執行所需的 Pages 都在 MM，則一切正常執行；反之，則要處理 Page Fault 問題，由 OS 另行處理。
> ###### 簡單來說，process在執行前，pager會先猜測process會用到哪些page，然後只載入那些page。
> - page 會被需要的意思 = 不會把整段 process 都複製到 memory(page) 中的意思。
>     - 也就是說，I/O 只有在需要執行 I/O 時才進行 input/output 
>       => faster response
>     - 也就是說，process 只有在當下馬上需要執行該段 code 時才放入 page
>       => Less memory needed
>       => more users (could use at the same time) 

### Hardware Support
1. Page Table 多加一個 “valid-invalid bit” 欄位，用以指示 Page 是否在 Memory 中。
    - 1 ➜ valid ➜ page in memory
    - 0 ➜ invalid ➜ page not in memory
>     初始化時全部 bit 設為 0 
2. Secondary Memory __輔助記憶體（通常是磁碟(disk)）
3. Instruction restart

### Search paging 的過程 /// 等同於 memory management 的 paging
![](https://i.imgur.com/eA5Xrq7.png)
![](https://i.imgur.com/cY92Vfv.png)
- 藍筆：想要找的 page 已經被放在 TLB 的 page table，所以可以直接從 RAM 裏頭找到要的 information
- 粉紅筆：想要找的 page 並不存在 RAM 中，若想要找該 information，就得進到 Secondary Memory 找想要的資料。
> 好懶的看圖解釋，有空再打。
>1. User 送出 logic address 到 PCB 的 page 找
>2. 
>3. 
>4. 
>5. 





### Page Fault :star2: :star2: :star2: 
#### Definition 
- **當一個 process 試圖存取沒有載入 memory 的 page 時，則會產生一個中斷的 trap**

#### 處理程序
![](https://i.imgur.com/u4JsexW.png)
1. OS 收到由 Page Fault 所引起的 trap (中斷)
    • 由 Memory Management Unit （MMU）發出。
2. OS 暫停目前 Process 的執行，並保存此 Process 的狀態。
3. OS 會去判斷此 Memory Access 位址是否合法。若非法(illegal)則終止此 Process，否則表示是由 Page Fault 所引起!!
＜page is on backing store＞
4. OS 去 Memory 檢查有無 Free Frame。若沒有，則必須執行 “Page Replacement” 以空出一個可用頁框。
＜get an empty frame＞
5. OS 去 Disk 中找到 Lost Page 之所在位置。
6. 將此 Lost Page 載入到可用頁框。
＜bring in missing page＞
7. 修改 Page Table，指明此 Page 所在頁框，並將 Invalid Bit(0) 改成 Valid Bit。
＜reset page table,  valid bit = 1＞
8. 恢復原先Process中斷前之執行。
＜restare instruction＞
> 補充一下課本圖
> ![](https://i.imgur.com/uYvdlxX.jpg)

## 一些關於 demanding page 的觀念
1. **pure demand paging** :程式執行之初，不預先載入任何Page。
    - 若剛開始執行 process 時，**沒有任何一個page存在於 memory 中**，則會==一直發生 page fault==，一直到 frame 滿了會恢復正常。
    ＜沒有任何預測的動作，只有在需要 page 時才會載入記憶體內＞
    - 優: 載入的 Page 皆是 Process 所需的頁面，故後續的Page Fault Ratio 會下降至合理值 (趨於穩定)。
    - 缺: 執行之初，會產生大量的Page Fault。
> 《補充》 **Prepaging(預先分頁)**   
> 事先猜測程式執行之初會使用哪些 Page，並預先將這些 Pages 載入。
優：若猜得準確，則可以避免程式執行之初大量 Page Fault
發生。
缺：若猜測錯誤，則先前載入 Page 的 I/O 動作白白浪費。
2. 當**讓一個指令執行存取多個 page 時，有可能會發生多個 page fault**，這時可以**運用 locality of reference**。
> locality觀念為：當有一個 page 被存取時，附近的資料也會很快被存取。
> (類似物以類聚的概念，相似的 page 一定都在附近)

### Performance of Demand Paging
####  效能主要取決於以下三者
1. 到 OS 裡的中斷服務常式(interrupt service routine) 找 page fault interrupt。
2. 從 disk 中找所需的 page。(swap in to page from disk)
    :star: **最耗時** :star: ≈ $8 ms$
3. 跳回被中斷的 process，並重被中斷的地方繼續開始 process。 
- 相較於 2. 所耗費的時間，1. 和 3. 只要幾百行指令就可以完成

:star: 為了解決 page fault 太常產生的情況，

#### 計算 :exclamation: 太簡單不考 :exclamation: 
- Page Fault Rate (Page fault 的機率) (0 <= p <= 1)
    - p = 0，沒有 page fault
    - p = 1，每次 paging 都是 page fault
- Effective Access Time(EAT) 
    = (1-p) x memory access + p(page-fault service time)
    > page-fault service time = page fault overhead + swap page out + swap page in
    - ex. 
        - 記憶體存取時間為 $200$ nanoseconds$( = 10^{-9}s)$
        - 平均page fault處理時間為 $8$ milliseconds$( = 10 ^{-3}s = 10^6 ns)$
    - EAT = (1-p) x 200 + p x 8000000 
        - if 一個 access 產生了 1000 個 page fault cases, then p = 1/1000
        - EAT = $8.2$ microseconds$( = 10^{-6} s= 10^3 s)$ 
    - 對記憶體來說 performance 並不好，因為 page fault 發生的機率太高了！



## Page Replacement Algorithm
- 當 **page fault 發生**且 **Memory 沒有可用頁框(free frame)** 時，若 OS 想要找到可以用的 frame，就要考慮用何種"尋找方法"(演算法)來找到 free frame。
- Implement
    - OS 必須選擇一個**犧牲者(Victim Page)**，將其 ==Swap Out 到 Blocking Store (e.g. Disk)==，以空出一個可用頁框，再將 ==Lost Page 載入(Swap In)到此頁框。==
        ![](https://i.imgur.com/iCOvt5U.jpg)
> 《補充》
> Swap Out 和 Swap In 分別是 2 個 Disk I/O 的動作。
>     • Swap In 是必要的。(∵一定要將Lost Page置入到MM中)
>     • **Swap Out 不盡然是必要的。**(==需視 Victim Page 是否曾被修改==)
>> :exclamation: 是否可將非必要的Swap Out省掉？ :exclamation: 
➞可以！
➞所以可以節省不必要的 I/O 動作。！
>> - 判斷依據：Victim Page 從執行之初一直到準備被替換之前是否曾被寫入或修改？
>>   - (Yes: 須回存至H.D.；No: 可刪除或覆蓋)
>> - 利用 “Modification Bit” (或Dirty Bit) 來實行上述判斷依據，以節省 Victim Page 之 Swap Out I/O 的時間。
>>   - Modification Bit = 0：表示此頁面的內容**未**曾被修改過。（所以初始化=0）
>>   - Modification Bit = 1：表示此頁面的內容曾被修改過。


### 1. FIFO(先進先出) :exclamation: 太簡單不考 :exclamation: 
- **最先載入記憶體的 Page(Oldest Page)**，優先視為 Victim Page。
    > = the oldest page in FIFO will be repalced。
- eg.
    - 假設 available memory frames = 3 (3 frames)
    - reference string : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
        ![](https://i.imgur.com/PZxIULu.png)
        - 紅字是 page fault 的次數，黑字是 hit 的次數
        - page fault = 9 times
        - Page Fault Ratio = 9/12 = 75%
- eg.
    - 假設 available memory frames = 4 (4 frames)
    - 同上題的 reference string : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
        ![](https://i.imgur.com/oT1wL3u.png)
        - page fault = 10 times
        - Page Fault Ratio = 10/12 = 83.33%
- :star: 上方這種狀況稱為「Belady Anomaly」➜Belady 異常狀態 :star:
    - 在使用FIFO算法作為缺頁置換算法時，分配的缺頁增多，但缺頁率反而提高。
    - 如下方圖示
        ![](https://i.imgur.com/36eUF77.png)
                frame 的大小
    
### 2. OPT(Optimal) algorithm(最佳)
- 把「**將來長期不會使用的Page**」，視為Victim Page。
![](https://i.imgur.com/6BUWi8K.jpg)
- Page fault Ratio = 9/20 = 45%
- Performance
    - 效果最佳 (∵Page fault ratio最低)
    - 不會有 Belady 異常現象
    - 很難製作，通常做為理論研究與比較之用。
        (因為根本沒辦法預知 future 會讀入什麼東西)

### 3. LRU algorithm
###### Least Recently Used = LRU
- 把「**最近不常使用的Page**」，視為Victim Page。
![](https://i.imgur.com/dI5RAL0.jpg)
- Performance
    - 效果不錯 (Page fault ratio尚可接受)
    - 不會有 Belady 異常現象
    - 製作成本高，需要大量硬體支援 (如：需要Counter或Stack)
- Implement Way
    - By Counter (計數器) ((做為Logical Timer
        - 切確記錄每個 Page 最後一次的參考時間
        - 參考時間最小者即是 LRU Page
        - 作法：
            1. Counter 初值為0
            2. 每個 Page 皆有一個附屬的 Register，用以存 Counter 的值。
            3. 當有 Memory Access 動作發生，則 Counter 值加1，並且將 Counter 值設定給被存取頁面的附屬 Register。
            4. LRU Page 即是 Register 值最小的 Page。
            ![](https://i.imgur.com/Rtjoiki.png)

    - By $Stack$
        1. Stack 頂端放的是最後 (最近) 參考的 Page
        2. Stack 底端即為LRU Page。
        3. 當某 Page 被參考到，則會將此 Page 從Stack 中取出，並 Push 回 Stack 成為頂端的Page。
            ![](https://i.imgur.com/oU0DP0A.png)

#### LRU Approximation Algorithm(LRU 近似法則)
###### ∵LRU製作成本過高 & page fault ratio 仍不低
1. #### Second Chance (二次機會法則)
- 以 **FIFO** 法則為基礎，搭配 **Reference Bit** 使用。
    - 作法：
        1. 先以 FIFO 挑出 Page
        2. 檢查此 Page 的 Reference Bit：
            • 若為 1，表示最近有被參考過，則給予這個 page 第二次機會，故放棄此 Page 作為 Victim Page。
                --- 並將 Reference Bit 值重設為 0，且將此 page 的到達時間設重置為目前時間，再 goto 上方 step "1."。
            • 若為 0，表示最近沒有被參考過，則選擇此 Page 作為 Victim Page。
    - ex.
        ![](https://i.imgur.com/F6nXWdj.png)
- 實作方法：環狀 queue(有時稱為 clock)
- 
>    - 所有 Page 的 Reference Bit 皆為 0 或 1 ，則退化成 FIFO Algo。∴可能有Belady Anomaly。

2. #### Enhance Second Chance (加強式二次機會法則)
- 用 **(Reference Bit, Modification Bit) 配對值**，將這裡個 bit 視為一組有序對，作為挑選 Victim Page 的依據。
- 以二進位無號數來使用，取**最小值**做為 Victim Page 若有 ≥ 2個Page 具有相同最小值，則以 **FIFO** 為準。
    - 可以得到以下四種類型： **(Ｒ →Reference Bit, Ｍ →Modification Bit)** 
        - (0, 0)➜ 表示沒使用過，也沒被修改過 ➯ **最佳 victim page**。
        - (0, 1)➜ 表示近期沒被使用過，但曾被修改過 ➯ 因此 page 需要被寫入(存回) disk，才可被替換，故沒有那麼好。
        - (1, 0)➜ 表示近期有被使用過，但沒被修改過 ➯ 可能很快又被使用到(locality)。
        - (1, 1)➜ 表示近期被使用過，也被修改過 ➯ 可能會再度被使用到，若想選擇此 page 作為 victim page，必須先將她存回儲存裝置。 
- ex. ![](https://i.imgur.com/dR8jMHV.png)

### 4. Counting algorithm
###### teacher say :arrow_right:《現在不實作、只要知道名字就好，不用特別了解》
- 以**頁面之參考次數**作為挑選 Victim Page 的依據
#### 4.1 LFU
###### (least frequently used)
- 參考次數最少的 Page 作為 Victim Page
- 每一個 page 有 counter
- Idea
    - 經常被使用的 page 應該要有大的 count value。

 
 
#### 4.2 MFU 
###### (most frequently used)
- 參考次數最多的 Page 作為 Victim Page
- 常用不代表正在用，有可能在某些時刻集中使用，將 count 拉高，但多數時間沒有使用
- Idea
    - 最小的 count 有可能是剛帶進來的，還沒被使用，所以應該留著。
- example
    ![](https://i.imgur.com/JzxAbJk.png)
    - 計算過程
    - 當 page 被取代時， count 也得歸零![](https://i.imgur.com/1wYoGVM.png)
    - 根據 FIFO，故先取代第一個進來的 page 1![](https://i.imgur.com/Oauc3A8.png)
    ![](https://i.imgur.com/YGT9zhG.png)
    - Result ![](https://i.imgur.com/ddEaUa6.png)
![](https://i.imgur.com/Zan385k.png)


    



#### Conclusion
- 兩者都不常用
    1. Page Fault Ratio太高 (∴不常使用)
    2. 要一直執行加法成本很高(∵需要硬體支援, ∴too expansive)
    3. 會有Belady Anomaly, 表現不一定較佳 

# Allocation of Frames
- 每個 process 最少都需要一定數量的 frames
## Frame Allocation
### Fixed allocation
- 根據 process 的數量，一開始就決定要 allocate 多少 frame 給每個 process。
- **Equal Allocation:** 
    - 每個 process 配置到的 frames 數目相同
    - ex. 總共有 100 frames & 5 processes
      ➜ 20 frames/ process
      ≈ 每個 process 都給 k 片
- **Proportional Allocation:**
    - 根據 process 的大小來配置。
### Priority allocation
- 在 run time 的時候，使用 Proportional Allocation 的切割 memory 方式，且根據 process 的優先度(priority)決定配置。
- 若 process 發生 page fault
    1. 選擇 process 本身的一個 frame 來替代
    2. 或選擇低優先度(low priority)的 process 的 frame 來替代。


### Local allocation
###### frame 的局部性
- 選 victim 時，只能替換自己的 frames，通常跟 fixed allocation 綁在一起。

### Global allocation
- 從所有的 frames 中選擇一個來替代。
    ≈ 可以拿其他 process 的 frame
- ex. 讓高優先度(high priority) 的 process 拿走低優先度(low priority)的 process。
    >    - :exclamation: 可能產生一個問題 :exclamation: 
        - 如果一直搶低優先度 process 的 frame，有可能該 process 無法維持最低的 frames 數量，所以==要有機制來維持最低 frames==，避免 process 被 **trashing**。
- 因為這個方法的 performance 還不錯，所以常被使用。

## Trashing (震/振?盪)
- Definition: 當一個 process 花在 paging 的時間比執行時間更高時，稱為 thrashing  ≈ 一直在 swap 
- Background 詳細版補充(看一下比較能理解)
    1. 在 Multiprogramming 且 Demand Paging 的環境中，若 **Process 分配到的頁框數不**，則其會**經常發生 Page Fault**，此時**必須執行 Page Replacement**。
    2. 若==採用 “Global Replacement Policy”==，則**此 Process 會替換(搶奪)其它 Process 的 frame**，而造成其它 Process 也會發生 Page Fault，而這些Process 也會去搶其它 Process 之頁框，如此一再循環發生，==造成**所有 Process 皆在處理 Page Faults**==。
    3. 因為所有 Process 皆忙於 Page 的 Swap In/Out，造成 CPU 經常 idle，**CPU Utilization 下降**。此時 OS(Multiprogramming Sys.) 將企圖引進更多的 Processes 進入系統。
    4. 新進入的 Processes 又會因為頁框數不足，而又發生 Page Faults，又與其它 Process 搶奪頁框，導致 CPU又再次 idle。但是 OS 再度企圖拉高 Multiprogramming Degree。
     - 結論：
        如此現象一再發生，造成 **CPU Utilization 急速下降**，**Throughput↓**，==所有 Process 花在處理　Page Fault 的時間遠大於正常執行時間，稱之為 Thrashing。==
- 在分界點右半邊的 CPU 使用率急遽下降。
    ![](https://i.imgur.com/5gFlNTm.png)
- improve way: 把 multiprogramming 的 process 數量減少(∵frames 不夠 process 使用)



### Solution of Trashing
#### 1. Working-set model :star:
- “預估” 各 Process 在不同執行時期所需的頁框數，並依此提供足夠的頁框數，以防止 Thrashing。 
- Process 執行時，對於 Memory 的存取區域並非是均勻(Uniform)的，而是具有區域性(Locality) 的特質。
> - Locality
> 1. Temporal Locality (時間區域性)
>    - Process 目前所存取的記憶體區域，過不久後會**再度被存取**。
>    - Ex: Loop, Subroutine, Counter, Stack
> 2. Spatial Locality (空間區域性)
>    - Process目前所存取的記憶體區域，其**鄰近區域極有可能也會被存取**。
>    - Ex: Array, Sequential Code Execution, Global Data Area
- Working-Set Model(此方法會用到的名詞)
    - Working-Set Window : Δ(delta) ➜ a parameter
    - Working Set
    - Working Set Size : (WSS)
- 做法：
    1. OS 設定一個 Working Set Window (Δ) 大小。
    2. 以 Δ 次記憶體存取中，所存取到的不同 Page 的集合，此一集合稱為 Working Set。
    3. 而 Working Set 中的 Process 個數，稱為 Working Set Size (WSS)。
    - 不同時期，Δ 可能不一樣
- Simple Example
    ![](https://i.imgur.com/jVXcAhB.png)
- Simple Example
    ![](https://i.imgur.com/pJoiiQb.jpg)
- Working-Set Model(更多 process 時會用到的名詞)
    - 假設有 $n$ 個 Processes，令：
        1. $WSS_i$ = $Process_i$ 在某時期的 Working Set Size。
        2. total demand frames = D = 某時期所有 Processes 之頁框總需求量。
            即：D = $∑_i^nWSS_i$
        3. M 為 Physical Memory 大小 (可用頁框總數)
- Case 1: D ≤ M ➜ increase degree of MP(MultiProgramming)
    • OS 會依據 $WSS_i$，分配足夠的頁框數給$Process_i$，則可防止 Thrashing。
- Case 2: D > M ➜ suspend a process
    • OS 會選擇 Process 暫停執行，直到 D ≤ M 為止。 
    此時即回到 Case 1，等到未來記憶體頁框足夠時，再恢復原先的 Suspended Process。
- advantage 
    - 監控 the degree of MP ，能夠有效的防止 Thrashing 產生
    - 對於 Prepaging 亦有幫助
    - 有效提升 CPU 的使用率
- disadvantage
    - 即時監控對 CPU 而言是 waste 的(因為沒有真的在執行 process 要做的事)
    - 用上一次的 Working Set 來預估下一次的 Working Set，不易制定精確的Working Set。
    - 若前、後的 Working Set 內容差異太大，則 I/O Transfer Time 會拉長。
        - ex.![](https://i.imgur.com/clD7QrA.png)



#### 2. Page-fault frequency :star:
- **OS 規定合理的 Page Fault Ratio 之上限值(upper bounds)下限值(lower bounds)**，把該 ratio 控制在一個合理範圍內。
    **(∵有振盪發生時， Page Fault Ratio 一定是處於高檔)**
    - Case 1: 若==某 Process 的 **Page Fault Ratio > 上限值(upper bounds)**，則 **OS 應多分配額外的頁框給該 Process。**==
        (ex. 從 priority 低的 process 拿走 frames)
        > 把其他 process 過多的 frame 拿來用！(因為本身的 page fault 太大，表示沒有足夠的 frame 可以使用，所以需要跟其他 process 拿一點 frame)
    - Case 2: 若==某 Process 的 **Page Fault Ratio < 下限值(lower bounds)**，則 **OS 應從 Process 取走多餘的頁框**==，以分配給其它有需要的 Process。
        > 把過多的 frame 抽走一點(因為本身就不太會產生 page fault，表示 frame 太多了！)
        
![](https://i.imgur.com/AdwgVgL.png)


#### 3. 降低Multiprogramming Degree



# HomeWork
## 9.2
![](https://i.imgur.com/3Esf50t.png)
- $(a).$ Will the thread change state if it incurs a page fault? If so, to what new state?
- Answer: 
    - Yes, a tread **changes from the Running state to the Blocked state** when a page fault occurs.
    - When a page fault occurs, the process starts to wait for I/O operation to finish. The OS does several things while the process is waiting. It checks whether the page is really invalid or just on disk, finds a free memory frame, schedules a disk access to load the page into t the frame, updates the page table with the new logical-physical mapping, updates the valid bit of that entry, and eventually restarts the process by change its state from Blocked to Ready.
- $(b).$ Will the thread change state if it generates a TLB miss that is resolved in the page table? If so, to what new state?
- Answer:
    -  Not necessarily. 
    - If a page table entry is not found in the TLB (TLB miss), the page number is used to index and process the page table. 
        -  If **the page is already in main memory**, then **TLB is updated to include the new page entry**, while the process execution continues since there is **no I/O operation needed**. 
        -  If the page is **NOT in the main memory**, a ==page fault== is generated. In this case, the process needs to **change to the Blocked state** and **wait for I/O to access the disk.** This is the same procedure as in the first question.
- $(c).$ Will the thread change state **if an address reference is resolved** in the page table? If so, to what new state?
- Answer:
    - No, because **no I/O operation is needed** is the address reference is resolved in the page table, which indicates the page needed is loaded in the main memory already.
 
![](https://i.imgur.com/79Z5wME.png)


## 9.4
![](https://i.imgur.com/6LgZ33w.png)
Copy on Write ==allows processes to share pages rather than each having a separate copy of the pages.== However, when one process tried to write to a shared page, then a trap is generated and the OS makes a separate copy of the page for each process. This is commonly used in a fork() operation where the child is supposed to have a complete copy of the parent address space. Rather than create a separate copy, the OS allows the parent and child to share the parent's pages. However, since each is supposed
to have its own private copy of the pages, the pages are copied when one of them attemps a write. 
The hardware support required to implement is simply the following:
on each memory access, the page table needs to be consulted to check whether the page iswrite-protected. If it is indeed write-protected, a trap would occur and the operating system could resolve the issue.
![](https://i.imgur.com/hctLZXC.png)
![](https://i.imgur.com/Y0hZhHL.png)



## 9.6
![](https://i.imgur.com/IUEMjzc.png)
![](https://i.imgur.com/RzUmo1u.png)
![](https://i.imgur.com/2drkim9.png)


## 9.8
![](https://i.imgur.com/Bpgw8Cj.png)
![](https://i.imgur.com/TQoX4Qr.png)
![](https://i.imgur.com/cbb0ATZ.png)


## 9.9
![](https://i.imgur.com/5jDynM2.png)
![](https://i.imgur.com/hJ6ZU4Z.png)
![](https://i.imgur.com/h3oqxj7.png)
![](https://i.imgur.com/aFXKqUy.png)
![](https://i.imgur.com/ArU8g1A.png)
![](https://i.imgur.com/R3Cb32j.png)
![](https://i.imgur.com/j8wJe5J.png)


## 9.12
![](https://i.imgur.com/98I7Ym3.png)
![](https://i.imgur.com/2V63w2S.png)
![](https://i.imgur.com/qjhYitV.png)
![](https://i.imgur.com/smeNp6i.png)


## 9.14
![](https://i.imgur.com/A7AcV9V.png)
![](https://i.imgur.com/l5DjGcK.png)
![](https://i.imgur.com/u3fUasW.png)
![](https://i.imgur.com/ej5QQUv.png)


## 9.17
![](https://i.imgur.com/VsRgUmp.png)
![](https://i.imgur.com/75nVvOS.png)
![](https://i.imgur.com/ezxzLgV.png)
![](https://i.imgur.com/RWJiFXY.png)
![](https://i.imgur.com/fb6FZ4P.png)


## 9.19
![](https://i.imgur.com/gSZW8fg.png)
![](https://i.imgur.com/SgvPApI.jpg)


## 9.21
![](https://i.imgur.com/zzZ1Iof.png)
![](https://i.imgur.com/qFAT5nJ.png)

# Reference
- [從作業系統的角度來談為什麼需要「虛擬記憶體」](https://medium.com/starbugs/why-do-os-need-virtual-memory-b47d6eeecbce)
- 














