# Ch21 ~ Ch22 Swapping
過去我們都假設 Virtual memory 一定可以放進 physical memory，但這不現實，因此我們引入了 **swap space** 的概念。透過與硬碟的互動，我們成功提升了 virtual memory 的大小

## Swap space
- OS 預留硬碟裡的一部分作為 swap space，當 memory 不夠時可以交換
- 允許 OS 同時執行多個 process，如果 physical memory 不夠也能運作

## Present bit
在每個 PTE 上面新增一個 **present bit**
- **present bit = 1**：Page 在 physical memory 中
- **present bit = 0**：Page 在磁碟上，需要觸發 page fault

## Page fault(miss)
:::warning
Page fault **不是非法操作！**　只是代表資料尚未進來 memory
:::
- page 不在記憶體中 -> **page-fault handler** 負責從硬碟讀入
- 因為**讀取硬碟的時間遠大於讀取 memory**，系統可以切換去執行其他 process

## Page replacement mechanism
- 若無可用記憶體 -> OS 會執行** page replacement policy**
- **目標**：挑選一個 page 把它踢去硬碟

### 硬體流程
- 從 TLB 查詢
- 查詢 Page table
- present bit = 1：直接取用 PFN
- present bit = 0：執行 **swap**

### 軟體流程
- OS 找頁框、進行 I/O、更新 PTE、重新執行指令。

## Page replacement policies
- 決定要踢掉誰

### AMAT（Average Memory Access Time）
- **公式**：$AMAT = T_M + P_{miss} \times T_D$
- $T_M$：Physical memory 的存取時間
- $T_D$：硬碟的讀取時間
- $P_{miss}$：page fault 的機率
- 策略的核心目標：讓 $P_{miss}$ 下降

### Optimal（Belady's Algorithm）
- **概念**：踢掉未來最晚用到的 page
- **問題**：我們無法預知未來，故無法實作

### LRU(Least recently used)
- **概念**：踢掉**最久沒被用**的 page