* Virtual memory - 允許使用者的 logical memory 與physical memory 進行分離
1. 運行一個非常大的process
* Logical address space 空間可以比physical address space大得多

2. 提高 CPU/resourse 利用率
* 更高程度的多道程序設計程度

3. 簡化 compile 任務
* 讓程序員擺脫 memory 限制

4. 更快地運行程序
* 加載或交換所需的 I/O 更少

* Virtual memory 可以通過以下方式實現
* Demand paging
* Demand segmentation：由於規模可變而更加複雜


## Demand Paging
* 僅在需要時才將page而不是整個process放入Memory

* 所需 I/O 更少→ 響應更快
* 所需Memory 更少→ 更多用戶
* 當存在對page的引用時，需要page
> 無效參考 → 中止
不在Memory 中 → 通過paging進入Memory
### pure demand paging
當 process 啟動時，OS不會立即將任何 page 載入main memory，等到 process 真正需要訪問某個 page 時才進行載入。
> 啟動一個沒有page的process
> 除非需要，否則切勿將page放入Memory

* swapper （中期調度程序）操縱整個process，而pager 則關注process的各個page
* Hardware 支持
> Page Table：valid-invalid bit
>>1 → Memory 中的page
>>0 → page 不在Memory 中

* 最初，所有這些bits 均設置為 0
> 輔助Memory （交換空間、後備存儲）：通常使用高速disk （交換設備）



## Page Fault
當 process 首次訪問一個尚未載入 main memory 的 page 時，會觸發Page Fault。
→ OS透過執行一個稱為 "Page Fault Trap" 來中斷處理程序。

在Page Fault處理程序中，作業系統會進行以下操作：
1. OS查看internal table（PCB中）來決定
> 無效引用 → 中止
只是不在memory中 → 繼續
2. 獲取一個空frame
3. 將 page 從 disk （交換空間）交換到frame中
4. 復位 page table，有效-無效位=1
5. 重啟指令


### Demand Paging
如果發生 page fault時沒有空閒frame
> 將 frame 交換到 backing store
> 將 page 從 backing store 交換到 frame 中
> 不同的 page 替換算法選擇不同的 frames 進行替換

**Demand Paging 性能**
有效訪問時間 (EAT)：(1 - p) * ma + p * pft

■ 示例：ma = 200ns, pft = 8ms
> EAT = (1-p)* 200ns + p * 8ms
> = 200ns - p * 200ns + p * 8ms
> = 200ns + (8ms - 200ns) * p
> = 200ns + (8,000,000ns - 200ns) * p
= 200ns + 7 ,999,800ns * p

* EAT 是平均 page 訪問時間
* p 是缺頁率
* 200ns 是記憶體讀取 page 時間
* 8ms 是磁碟讀取 page 時間
如果缺頁率為 1%，則 EAT 為 8.2μs，比沒有 page fault時的 200ns 慢了 40 倍。

缺頁率越高， page fault的次數越多，EAT 就越高。EAT 的高低會直接影響系統的性能。

對於降解率低於 10% 的情況：
220 > 200 + 7,999,800 * p。
p < 0.0000025 -> 399,990 次訪問中有 1 次出現 page fault

* programs 往往有 locality of reference
* locality 意味著程序經常訪問靠近的memory addresses
> 由於locality的存在，當程式遇到一個page fault時，通常會帶來一個 page 的內容，一般為4KB大小。這種批量帶來的內容可以減少未來的頁面fault，因為程式在接下來的執行中可能會再次訪問這些附近的內容。大大減少 page fault 的發生

page fault 時間的主要組成部分（約 8 ms）
1. 提供 page fault 中斷服務
2. 從 disk 讀入 page （最昂貴）
3. 重啟 process

第1條和第3條指令可以減少到幾百條
> page 切換時間接近8ms

## Process Creation
### Process & Virtual Memory
* Demand Paging：僅調入包含第一條指令的page
* Copy-on-Write：父 process 和子 process 最初共享相同的 frames ，並在寫入 page 時進行 frames複製
* Memory-Mapped file：將文件映射到 virtual address space 以繞過file system calls（例如read()、write()）

### Copy-on-Write
允許父process和子process共享Memory 中的相同frame
如果任一process修改了frame，則僅複製frame
COW允許高效的 process 創建（例如fork()）
空閒 frame 是從 a pool of zeroed-out frames 分配的（安全原因）
> frame內容被擦除為0



### Memory-Mapped Files
* 方法：
> MMF 通過將 disk 塊映射到 Memory frame，允許將文件 I/O 視為常規 Memory 訪問
最初使用 demand paging 讀取文件。 後續對文件的讀取/寫入將被視為普通 Memory 訪問

* 益處：
> 通過使用Memory 訪問而不是 read() 和 write() 系統調用來加快文件訪問速度
▸ 允許多個process映射同一文件，從而允許共享Memory 中的page

* 擔憂：
> 安全（訪問控制）、數據丟失、更多編程工作



### Page Replacement
當發生 page fault 並且沒有空閒 frame 時，swap 一個 process，釋放其所有 frames ，或者
> 將一個已經駐留在 Main memory 中的 page 移出，並將需要的 page 調入到 Main memory ，從而為 process 提供所需的數據。
>
> 這個過程就是 page replacement。

透過使用 dirty bit，作業系統可以更加智能地選擇需要 replacement 出去的 page ，從而減少對儲存設備的讀寫開銷，提高系統效能。

> "Dirty bit" 是 virtual memory 管理中的一個標誌位，用於跟蹤 page 是否被修改過。
>
> 當處理器或 process 對一個 page 進行 write 操作時，作業系統會將這個 page 的 dirty bit 設置為1，表示 page 內容已被修改。
>
> 如果 page 沒有被寫過，則 dirty bit 被設置為0。

* frame-allocation 算法：

* 確定分配給 process 的 frames
* page-replacement 算法：
* 選擇要更換的frame

目標：最低 page fault率
* 評估：針對 memory 引用字符串（引用字符串）運行併計算 page fault數
* 參考字符串： 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5


## First-In-First-Out (FIFO) 算法
* FIFO隊列中最舊的 page 被替換
* 參考字符串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
* 3 個 frame（可用 memory frame = 3）
**→ 9 個 page fault**

### FIFO 說明 Belady 的異常情況
* 更多分配的frame是否能保證更少的page fault？
* 參考字符串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
* 4 frame（可用 memory frame = 4）
**→10 個page fault！**


* Belady 異常
> 使用 FIFO 算法時增加 main memory 更多 frame 數量。
→ 導致更多page fault

這種現象稱為Belady's Anomaly（Belady 異常）

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

4 frames: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
**->6 個 page faults!**


## LRU Algorithm (Least Recently Used)
* 一種與 optimal algorithm 的近似算法
* 因為無法預測未來，所以我們往回看
* 取代最長時間沒有被使用的 page
* 因為 locality 及時間複雜度低 (O(1)) 的緣故，LRU 很常被使用

### LRU算法實現
* Counter implementation
> 引用的 page ：time-stamp 被複製到計數器中
> replacement ：刪除最舊的計數器
>> 需要線性搜索...
* Stack implementation
>引用的 page ：移至 double-linked list 頂部
> replacement：去掉底部的 page
4 frames ：1、2、3、4、1、2、5、1、2、3、4、5


## Stack Algorithm
* 算法的屬性

Stack 算法：memory 中的 pages 集
n frames 始終是 memory 中包含 n +1 frames的 pages 集的子集
* Stack 算法不會受到 Belady 異常的影響
* optimal 算法和LRU算法都是 stack 算法

## Counting 算法
* LFU算法（least frequently used）
> 想法：
> 假設被使用次數最少的 page 在未來也很可能不會被使用，因此選擇最少使用次數的 page 進行 replacement 。
* MFU算法（most frequently used）
> 想法：
> 與 LFU 算法相反，假設被使用次數最多的 page 在未來還會被頻繁使用，因此選擇使用次數最多的 page 進行 replacement 。

* 兩種算法都是為每一個 page 保留一個計數器，根據 page 的使用頻率來進行 replacement
* 兩種計數算法都不常見
1. 實施成本高昂
2. 不太近似 OPT 算法

## Allocation of frames
每個 process 最少都需要一定數量的 frames


例如：IBM 370-6 page 處理Storage to Storage MOVE指令：
兩個 operands 都在主存中，第一個 operands 是B1( Reg.ID )+D1，第二個operands 是B2( Reg.ID )+D2, L plua 1是長度。
- 指令為 6 個字節，可能跨越 2 頁
- 可以跨 2 頁移動內容

## Frame Allocation

* Fixed allocation
> 均等分配-100 frames，5 process → 20 frames/ process
> 按比例分配——根據 process 的大小進行分配
* Priority allocation
> 使用基於優先級而不是大小的比例分配
> 如果 process P 產生 page fault
>> 選擇替換其框架之一
> 從優先級較低的 process 中選擇替換
* Local allocation：
>每個process從自己的一組分配frame中進行選擇
* Global allocation：
>process從所有frame集合中選擇一個替換frame
>一個process可以奪走另一個process的一frame
>例如，允許高優先級process從低優先級process獲取frame
>良好的系統性能，因此被廣泛使用
>每個process必須保持最小數量的frame以防止垃圾

## Thrashing的定義

當系統遇到高度的 memory 需求，但physical memory 不足以滿足這些需求時，就會出現Thrashing。這種情況通常發生在運行多個 memory 密集型應用程序或處理大量數據的情況下。

當處理器不斷地將 page 從 disk swapping 到 memory ，然後再將其他page swapping 回disk，這樣的過程不斷重複，導致系統耗費大量時間在 swapping pages 上，而無法執行實際工作。

如果process沒有“足夠”的frame
> 該process沒有 # 個frame來支持正在使用的page
→非常高的paging活動


如果process花在調頁上的時間多於執行的時間，則該process正在Thrashing

## Thrashing
Thrashing導致的性能問題（假設使用全局替換）
> process排隊等待 I/O 交換（page fault）

→ CPU利用率低
→ 作業系統提高了多道程序設計的程度
→ 新process從舊process中獲取frame
→ 更多page fault，因此更多 I/O
→ CPU 利用率進一步下降

為了防止Thrashing，必須為每個process提供足夠的frame：
>Working-set模型、page fault頻率

## Working-set模型

Working-set 模型是 virtual memory 管理中的一個重要概念，用於描述一個 process 在執行過程中所需要的 page 集合。這個模型有助於了解 process 在一段時間內的 page 使用情況，並可用於改進 page replacement 算法和 main memory 分配策略。

Locality：一組經常一起使用的page
Locality model：當process執行時，它從一個Locality移動到另一個Locality
> 程序結構（subroutine, loop, stack）
> 數據結構（array, table）

在基於 Locality 的 Working-set 模型中， process 的 page 引用模式被假設具有 Locality。

這種 Locality 導致 process 的 Working-set 在特定時間內會集中在一組近似的 page 中。

Working-set 模型：引入了一個參數 Δ（增量），用於定義 Working-set 窗口的大小。

Working-set 窗口：是一個時間範圍，在這個範圍內， process 的 Working-set 會被追蹤和維護。

Working-set 窗口內的 page 集合包含了 process 在最近 Δ 次 page 引用中訪問的所有 page 。


■ 使用 Working-set 大小防止 Thrashing
> WSS_i：process i 的Working-set大小
>> D = WSS_i（總需求frame）
>
> 如果 D > m（可用frame）-> Thrashing
> 作業系統監控每個process的 WSS_i，並為該process分配足夠的frame
如果 D < m，則增加 MP 程度
如果 D > m，則暫停process

優點:
1. 防止Thrashing，同時保持盡可能高的多道程序設計程度
2. 優化CPU利用率

缺點：追踪成本太高

## Page Fault Frequency方案
Page fault frequency 直接測量和控制 page-fault 率以防止 thrashing
> 建立 process 所需 page-fault 的上限和下限

* 如果 page-fault 率超過上限

* 為process分配另一個frame
* 如果 page-fault 率低於下限
* 從 process 中刪除frame


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