# Background
* 程式需要在記憶體中才能執行，但整個程式很少被使用
* 錯誤代碼處理、不尋常的例程、大型數據結構=>這些部分在main memory中並不是必要的
* 不需要同時加載整個程式代碼
* 考慮到執行部分加載的程式能力
* 程式不再受到物理記憶體限制
* 每個程式在運行時佔用的記憶體較少，從而可以同時運行更多程式
* 增加 CPU 利用率和吞吐量，而不增加響應時間或周轉時間
* 需要載入或交換程式到記憶體中的 I/O 較少，因此每個使用者程式運行得更快

# Virtual memory
* 虛擬記憶體(virtual memory) - 將用戶邏輯記憶體與物理記憶體分離
* 只需將程式的一部分置於記憶體中以進行執行
* 因此，邏輯地址空間(Logical address space)可以比物理地址空間(Physical address space)大得多
* 允許多個進程共享地址空間
* 促進更有效的進程創建
* 可以同時運行更多程序
* 加載或交換進程所需的I/O更少
* 虛擬地址空間 - 對進程在記憶體中存儲的邏輯視圖
* 通常從地址0開始，直到空間的末尾都是連續的地址
* 而物理記憶體則組織成頁框(page frames)
* MMU 必須將邏輯地址映射到物理地址
* 虛擬記憶體可以通過以下方式實現：
* 需求分頁(Demand paging)
* 需求分段(Demand segmentation)

## Virtual Memory That is Larger Than Physical Memory

## Virtual-address Space of a Process => 進程如何儲存在記憶體中的邏輯視圖
* 通常將堆疊的邏輯位址空間設計為從最大邏輯位址開始並「向下」成長，而堆疊則「向上」成長
* 最大化地址空間使用
* 兩者之間未使用的位址空間是空洞
* 在堆疊或堆疊增長到給定的新頁面之前不需要物理內存
* 啟用稀疏位址空間，並留有成長空間、動態連結庫等
* 透過映射到虛擬位址空間共享系統庫
* 透過將讀寫頁映射到虛擬地址空間來共享內存。
* 可以在 fork() 期間共用頁面，加快進程建立速度

## Shared Library Using Virtual Memory

## Demand Paging => 僅在程式執行期間需要時才載入頁面
* 可以在加載時將整個進程調入內存
* 或者僅在需要時將頁面調入內存
* 需要的I/O 較少，沒有不必要的I/O
* 需要的內存較少
* 響應速度更快
* 用戶更多
* 類似於有交換的分頁系統（下圖）(1)
* 需要頁面 => 參考該頁面
* 無效的參考 => 中止
* 不在記憶體中 => 將其帶到記憶體中
* 懶惰的交換器(Lazy swapper) - 從不將page交換到memory中，除非該page將被需要
* 處理頁面的交換器稱為分頁器(pager)
=> pager會做swap in/out的工作

## Basic Concepts
* 透過交換，pager猜測在再次交換之前將使用哪些page
* 相反，pager僅將這些page放入memory中
* 如何確定哪一組頁面？
* 需要新的 MMU 功能來實現請求分頁
* 如果所需的pages已經駐留在記憶體中(already memory resident)
* 與非請求分頁(non demand-paging)沒有區別
* 如果需要page並且不駐留在記憶體中
* 需要檢測page並將其從storage加載到memory中
* 無需改變程式行為
* 無需程式設計師更改程式碼

## Valid-Invalid Bit
* 每個頁表條目都有一個有效-無效位元關聯
* （v=>記憶體中(In-memory)-記憶體駐留(memory resident), i=> 不在記憶體中(not-in-memory))
* 所有條目上的初始有效-無效位元均設定為 i
* 頁表快照範例：
* 在MMU位址轉換過程中，如果頁表項中的有效-無效位元是i=>缺頁(page fault)

## Page Table When Some Pages Are Not in Main Memory

在上圖中，如果將D加入memory，那page table這裡的第三格就要寫上D在memory中的位址(範例中假設是7)，並加該格的i改成v，這樣之後如果要查找D是否在memory中的時候直接找page table就可以了，不用去找memory

## Steps in Handling Page Fault
1. 如果存在對page的引用，則第一次引用該頁面將捕獲作業系統
* 頁面錯誤(page fault)
2. 作業系統查看另一個表來決定：
* 無效參考=>中止
* 只是記憶體中沒有
3. 尋找空白框架(free frame)
4. 透過計劃的磁碟操作將頁面交換到frame中
5. 重置table以指示記憶體中現在的頁面設定驗證位元 = v
6. 重新啟動導致頁面錯誤的指令

(2)
## Aspects of Demand Paging
* 極端情況－在記憶體中沒有頁面的情況下啟動進程
* 作業系統將指令指標設定為進程的第一條指令，非記憶體駐留 -> 頁面錯誤
* 對於第一次造訪時的所有其他進程頁面
* 純需求分頁(pure demand paging)
* 實際上，給定的指令可以存取multiple pages -> 多個頁面錯誤
* 考慮指令的獲取和解碼，該指令將記憶體中的 2 個數字相加並將結果儲存回內存
* 由於參照點的位置(locality of reference)，疼痛減輕
=> 是因為參照點的位置很接近
* 需求分頁需要的硬體支援包括：
* 具有有效/無效位的page table
* 次要記憶體(Secondary memory)（具有交換空間的交換設備）
* 指令重新啟動

## Instruction Restart
* 需要能夠在頁面錯誤後重新啟動任何指令：
* 如果在指令提取期間(instruction fetch)發生頁面錯誤，我們可以通過再次提取該指令來重新啟動。
* 如果在提取操作數(fetching an operand)時發生頁面錯誤，必須重新提取和解碼指令，然後再提取操作數。
* 例如，將A的內容加到B，將結果放入C：
1. 提取並解碼指令（ADD）。
2. 提取A。
3. 提取B。
4. 將A和B相加。
5. 將和(sum)存儲在C中。

| ADD | A | B | C |
| --- | --- | --- |:---:|
| OP | A | B | C |

* 如果在第5步發生錯誤，則必須重新執行整個指令(不多！只有一條指令)

## Major difficulties
* 當一個指令可能修改多個不同位置時，會出現主要困難。
* 舉例來說，IBM System 360/370 的 MVC（move char.）指令可以一次移動 256 個字節。在移動部分完成後可能發生頁面錯誤。
* 解決方案：
* 微碼計算並嘗試訪問兩個塊的兩端。如果將發生頁面錯誤，它會在此步驟發生，而在修改任何內容之前。
* 使用暫存寄存器來保存被覆蓋位置的值

## Free-Frame List
* 當發生頁面錯誤時，作業系統必須將所需的頁面從次要存儲器帶入主存儲器。
* 大多數作業系統維護一個free-frame list - 這是一個用於滿足這些請求的空閒頁框池(a pool of free frame)。
* 作業系統通常使用稱為需求時零填充的技術(zero-fill-on-demand)來分配空閒頁框 - 在分配之前將frame的內容清零。
* 當系統啟動時，所有可用內存都被放置在自由頁框列表上

## Stages in Demand Paging – Worse Case
* 頁面錯誤導致以下序列發生：
1. 陷阱到作業系統(Trap to the operating system)。
2. 保存用戶寄存器和進程狀態。
3. 確定中斷是頁面錯誤。
4. 檢查頁面引用是否合法，並確定頁面在磁盤上的位置。
5. 向一個空閒頁框發出磁盤讀取請求：
1. 在此設備的隊列中等待，直到讀取請求被服務。
2. 等待設備搜索和/或延遲時間。
3. 開始將頁面傳輸到一個空閒頁框。
6. 在等待期間，將CPU分配給其他用戶。
7. 從磁盤I/O子系統接收中斷（I/O完成）。
8. 保存其他用戶的寄存器和進程狀態。
9. 確定中斷來自磁盤。
10. 修改頁表和其他表，以顯示頁面現在在內存中。
11. 等待CPU再次分配給此進程。
12. 恢復用戶寄存器，進程狀態和新頁表，然後繼續中斷的指令。

## Performance of Demand Paging
* 三個主要活動：
* 服務中斷(Service the interrupt) - 慎重編碼意味著只需要幾百條指令。
* 讀取頁面(Read the page) - 消耗大量時間。
* 重新啟動進程(Restart the process) - 再次只需少量時間
* 頁面錯誤率0≤p≤1：
* 如果 p=0，則沒有頁面錯誤。
* 如果 p=1，則每次引用都是一個錯誤。
* 有效訪問時間（EAT）：
* EAT=(1−p)×內存訪問+p×(頁面錯誤開銷+交換頁面退出+交換頁面加入)
* EAT = (1 – p) x memory access+ p(page fault time)

## Demand Paging Example
* 記憶體存取時間(Memory access time) = 200 奈秒
* 平均頁面錯誤服務時間(Average page-fault sevice time) = 8 毫秒
* EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p) x 200 + p
= 200 + p x 7,999,800
* 1 millisecond = 1000 microsecond = 1000,000nanosecond
* 如果 1,000 次造訪中有一次導致頁面錯誤，則
* EAT = 8.2 microseconds
* 這是 40 倍的減速！！
* 如果希望效能下降 < 10%
* 220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
* p < 0.0000025
* < 每 400,000 次記憶體存取中有一個頁錯誤

## Demand Paging Example 2
* 記憶體存取時間（ma）100奈秒
* EAT = (1 –p) x (100) + p x (25 milliseconds)
= 100 + 24999900 x p
* Page fault rate: 10^-3^
100 + 24999900 x 10^-3^
= 100 + 24999.9
= 25099.9 nanosecond
≈ 250 times slower than 100 nanosecond
* 如果 1000 次中有 1 次造訪導致頁面錯誤，則有效存取時間為 25 微秒
=>減慢 250 倍(slow down by a factor of 250)
* 如果我們想要低於 10% 的退化：
110 > 100 + 24999900 x p
10 > 24999900 x p
p < 0.0000004
* 在請求調頁系統中保持較低的頁面錯誤率非常重要。否則，有效存取時間會增加，從而顯著減慢進程執行速度

## Demand Paging Optimizations
* 即使在同一裝置上，交換空間 I/O 也比檔案系統 I/O 更快
* 交換區分配在更大的區塊中，比檔案系統需要更少的管理
* One option：在進程載入時將整個process image複製到交換空間
* 然後頁進出交換空間 => will be faster
* 用於較舊的 BSD Unix
* Second option：最初從檔案系統請求頁面，但在頁面被取代時將其寫入交換空間
* 用於Linux和Windows
* 仍然需要寫入交換空間
* 不與檔案關聯的頁面（如堆疊和堆疊）－匿名內存(anonymous memory)
* 記憶體中已修改但尚未寫回檔案系統的頁面
* 移動系統
* 一般不支援交換
* 相反，從檔案系統請求頁面並回收read-only pages（例如程式碼）

## Copy-on-Write
* 寫時複製 (Copy-on-Write, COW) 允許父進程和子進程最初共享內存中的相同頁面
* 如果任何一個進程修改了共享頁面，只有在那時頁面才會被複製
* COW允許更高效的進程創建，因為只有被修改的P才會被複製
* fork() 系統呼叫的 vfork() 變體具有父級掛起和子級使用父級的寫時複製地址空間
* 設計讓子級調用
* exec()非常高效(3)

## Before Process 1 Modifies Page C

## After Process 1 Modifies Page C

## What Happens if There is no Free Frame?
* 被進程頁面用完
* kernel、I/O 緩衝區等也有需求
* 每人分配多少？
* 頁面替換－在記憶體中找到一些頁面，但沒有真正使用，將其調出
* 演算法——終止？換出？更換頁面？
* 效能(Performance) – 需要一種能夠將頁面錯誤數量降至最低的演算法
* 同一page可能會多次被調入memory

## Page Replacement
* 透過修改頁面錯誤服務例程以包含頁面替換來防止記憶體過度分配(over-allocation)
* 使用modify（dirty）bit來減少頁面傳輸的開銷 - 只有修改過的頁面才會寫入磁碟
* 頁替換完成了邏輯記憶體和實體記憶體的分離——可以在較小的實體記憶體上提供大的虛擬記憶體

## Need For Page Replacement

## Basic Page Replacement
1. 找到磁碟上所需頁面的位址。
2. 找到一個空閒框架：
* 如果有空閒框架，使用它
* 如果沒有空閒框架，使用頁面置換算法來選擇一個犧牲框架
* 如果犧牲框架已被修改，將其寫回磁碟
3. 將所需頁面帶入（新）空閒框架；更新頁面表和框架表
4. 重新啟動引發陷阱的指令，繼續過程
* 注意，現在對於頁面錯誤可能需要兩次頁面傳輸——增加了有效存取時間（EAT）。

## Page Replacement

## Page and Frame Replacement Algorithms
* 框架分配算法決定
* 給每個進程分配多少框架
* 替換哪個框架
* 頁面置換算法
* 希望在第一次訪問和重新訪問時頁面錯誤率最低
* 通過在特定的記憶體引用字串（引用字串）上運行算法並計算該字串上的頁面錯誤數來評估算法
* 字串只是頁面號碼，而不是完整地址
* 重複訪問同一頁面不會引起頁面錯誤
* 結果取決於可用框架數
* 在我們所有的例子中，引用字串由引用的頁面號碼組成。
* 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

## Graph of Page Faults Versus The Number of Frames

## First-In-First-Out (FIFO) Algorithm
* Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
* 3 frames（每個進程一次可以在記憶體中儲存 3 個頁面）
* 可能因引用字串而異：考慮1,2,3,4,1,2,5,1,2,3,4,5
* 增加更多frame可能會導致更多頁錯誤！
* Belady’s Anomaly
* How to track ages of pages?
* 只需使用先進先出隊列(FIFO queue)

## If there are four frame
* we have 10 page faults

## FIFO Illustrating Belady’s Anomaly

## FIFO Page Replacement
* 易於理解和編程
* 性能不總是理想
* 例如：計數包含一個在初期被初始化且持續使用的重要變量
* 即使選擇了一個正在積極使用的頁面，一切仍然能正確運行——會立即發生一個頁面錯誤來取回這個活躍頁面
* 錯誤的替換選擇會增加頁面錯誤率並減慢進程執行速度，但不會導致錯誤執行

## Optimal Algorithm => 往後看
* OPT 具有所有算法中最低的頁面錯誤率。它永遠不會遇到 Belady’s anomaly
* 替換最長時間內不會被使用的頁面
* 在這個例子中，9 是最優的選擇
* 不幸的是，OPT 很難實現——需要未來引用字串的知識
* 你如何知道這些？
* 無法預知未來
* 用於衡量你的算法性能如何

## Least Recently Used (LRU) Algorithm => 往前看
* 如果我們使用最近的過去作為未來的近似，那麼我們將替換最長時間未被使用的頁面
* 使用過去的知識而非未來的
* 替換最長時間未被使用的頁面
* 將每個頁面的最後使用時間相關聯
* 12faults——比 FIFO 好，但比 OPT 差
* 通常是個不錯的算法，並且經常使用
* 但如何實現呢？

## LRU Algorithm (Cont.)
* 計數器實現：
* 每個頁面條目都有一個計數器；每次通過該條目引用頁面時，將時鐘值複製到計數器中
* 當需要更換頁面時，查看計數器以找到最小值
* 需要遍歷表格
* 堆疊實現：
* 保持一個頁面號碼的雙鏈表形式的堆疊：
* 頁面被引用時：
* 將其移到堆疊頂部
* 需要改變 6 個指針
* 但每次更新更昂貴
* 替換時不需要搜索
* LRU 和 OPT 是沒有 Belady’s Anomaly 的堆疊算法的例子

## Use Of A Stack to Record Most Recent Page References

## LRU Approximation Algorithms
* LRU需要特殊的硬體並且仍然很慢
* Reference bit
* 每個頁面關聯一個位，最初 = 0
* 當頁面被引用時位設定為 1
* 將任何值替換為參考位元 = 0（如果存在）
* 但我們不知道順序
* Second-chance algorithm
* 一般是FIFO，加上硬體提供的參考位
* Clock replacement
* 如果要被替換的頁面有：
* 參考位(reference bit) = 0 -&gt; 替換它
* 參考位(reference bit) = 1，則：
* 將參考位設為 0，將頁面保留在內存中
* 替換下一個頁面，遵循相同的規則

## Second-Chance (clock) Page-Replacement Algorithm

## Second-Chance (clock) Page-Replacement Algorithm

---
## Enhanced Second-Chance Algorithm
* 改進算法，協同使用參考位(reference bit)和修改位(modify bit)（如果可用）
* 使用有序對 (reference, modify)：
* (0, 0) 既未最近使用也未修改——最佳替換頁面
* (0, 1) 未最近使用但已修改——不太好，替換前必須寫出
* (1, 0) 最近使用但乾淨——可能會很快再次使用
* (1, 1) 最近使用且已修改——可能會很快再次使用，且替換前需要寫出
* 當需要頁面替換時，使用時鐘算法(clock scheme)，但按四類中的最低非空類來替換頁面
* 可能需要多次搜索循環隊列
* 優先考慮已修改的頁面以減少所需的I/O次數。

## Counting Algorithms
* 保持每個頁面被引用次數的計數器
* 不常見
* 最少使用頻率 (LFU) 算法：
* 替換計數最小的頁面
* 遭遇這樣的情況：頁面在進程初期被大量使用，但之後不再使用
* 最多使用頻率 (MFU) 算法：
* 基於這樣的論點：計數最小的頁面可能是剛剛被調入的，尚未使用

## Lease Frequently Used (LFU) Algorithm

## Lease Frequently Used (LFU) Algorithm

## Page-Buffering Algorithms
* 維護已修改的頁面。每當分頁設備閒置時，選擇一個已修改的頁面，將其寫入磁盤並重置修改位
* 增加了頁面被選中時為乾淨頁面的概率。保持一個空閒框架池，但記住每個框架中的頁面
* 保留一個空閒框架池(a pool of free frames)，但要記住每個frames中的page。由於在將frame寫入disk時框架內容未修改，因此如果在重用該frame之前需要舊頁面，則可以直接從空閒框架池中重用舊頁面

## Applications and Page Replacement
* 所有這些算法都需要操作系統對未來頁面訪問的猜測
* 某些應用程序具有更好的知識——例如數據庫
* 內存密集型應用程序可能會導致雙緩衝
* 操作系統將頁面的副本保留在內存中作為I/O緩衝
* 應用程序將頁面保留在內存中供自己使用
* 操作系統可以直接訪問磁盤，不干擾應用程序
* 原始磁盤模式(Raw disk mode)
* 繞過緩衝(buffering)、鎖定(locking)等

# Allocation of Frames
* 除了一個框架中包含一條指令之外，其引用可能需要另一個框架。如果使用多級間接引用，則需要更多框架
* 每個進程需要最少數量的frame
* 例如：IBM 370 - 6個頁面來處理 SS MOVE 指令：
* 指令是6bytes，可能跨越2個頁面
* 2個頁面用於處理from
* 2個頁面用於處理to
* from where to where
* 最大值當然是系統中的total frames
* 最壞情況：多級間接引用導致整個虛擬內存必須在物理內存中
* 必須對間接引用的級別設置限制
* 兩種主要的分配方案：
* 固定分配(fixed allocation)
* 優先級分配(priority allocation)
* 有許多變化

## Fixed Allocation
* 等量分配(Equal allocation)：
* 例如，如果有100個frames（在為OS分配frames之後），並且有5個processes，則每個processes分配20個frames
* 保留一些作為空閒框架緩衝池(free frame buffer pool)
* 比例分配(Proportional allocation)：
* 根據process的大小進行分配
* 隨著多道程式設計程度、流程規模的變化而動態變化
* 兩個進程根據自己的「需要」共享可用的frames，而不是平等地共享

## Global vs. Local Allocation
* 全局替換(Global replacement)：
* process從所有frames中選擇一個替換框架；一個進程可以從另一個進程中取走一個框架
* 但進程執行時間可能差異很大
* 全局替換的問題：進程無法控制自己的頁面錯誤率。由於外部環境的不同，同一進程的表現可能會有很大不同
* 但通過量更大，所以更常見
* 局部替換(Local replacement)：
* 每個process只從自己分配的frame集中選擇
* 每個process的性能更加一致，why? => Not computing with other processes
* 但可能導致內存利用率不高

## Reclaiming Pages
* 實施全域頁面替換策略的策略
* 所有內存請求都從空閒框架列表滿足，而不是等待列表下降到零之前才開始選擇要替換的頁面
* 當列表下降到一定閾值以下時觸發頁面替換
* 這種策略旨在確保始終有足夠的空閒內存滿足新的請求

## Reclaiming Pages Example

## Non-Uniform Memory Access
* 到目前為止，所有記憶體都被平等地訪問
* 許多系統都是 NUMA – 存取記憶體的速度各不相同
* 考慮包含 CPU 和記憶體的系統板，透過系統匯流排互連
* NUMA 多處理架構
* 最佳性能來自於將內存分配“靠近”所調度的CPU上
* 並修改調度器以在可能的情況下將線程調度到同一系統板上
* 透過在Solaris中創建lgroups來解決此問題
* lgroups是用於跟蹤CPU / 內存低延遲組的結構
* 由調度器和分頁器使用
* 在可能的情況下，將進程的所有線程都安排在同一lgroup中，並為該進程分配所有內存

## Thrashing
* 如果一個進程沒有足夠的頁面，那麼頁面錯誤率會非常高
* 需要頁面錯誤以獲取頁面
* 替換現有框架
* 但很快需要替換的框架回來
* 這導致：
* CPU利用率低
* 操作系統認為需要增加多程序程度
* 將另一個進程添加到系統中
* Thrashing. 進程正忙於換入和換出頁面
* 在thrashing的時候，為了提高 CPU 使用率並停止抖動，我們必須降低多道程式設計的程度。
* 可以透過使用本地替換演算法來限制抖動的影響：如果一個進程開始抖動，它不能從另一個進程竊取幀並導致後者也抖動。

## Demand Paging and Thrashing
* 局部性模型：
* 當一個進程執行時，它從一個局部性轉移到另一個
* 局部性是一組共同活動的頁面。（參見圖10.15）
* 一個程序通常由幾個不同的局部性組成，這些局部性可能重疊
* 為什麼會發生抖動？
* ∑ 局部性的大小 &gt; 總內存大小
* 為了防止抖動，必須為一個進程提供所需的所有框架
* 局部性由程序結構及其數據結構所定義。局部性模型聲稱所有程序都會展示這種基本的記憶體參考結構
* 通過使用本地或優先級頁面替換來限制影響。

## Locality In A Memory-Reference Pattern

## Working-Set Model
* △≡工作集窗口≡固定數量的頁面引用。例如：10,000條指令。
* WSSi（進程Pi的工作集）=最近△中引用的頁面總數（隨時間變化）。
* 如果△太小，將無法包含整個局部性。
* 如果△太大，將包含幾個局部性。
* 如果△=∞ => 將包含整個程序。
* D = ∑WSSi≡總需求框架數。
* 局部性的近似。
* m = 可用框架總數。
* 如果 D > m => 則會發生抖動，因為某些進程將沒有足夠的框架。然後掛起其中一個進程。
* 策略：如果 D > m，則掛起或換出其中一個進程。
* 工作集策略在防止抖動的同時保持最高的多程序程度，從而優化 CPU 利用率。

## Keeping Track of the Working Set
* 工作集窗口是一個移動窗口。（隨時間演變）
* 用間隔定時器 + 參考位來近似
* 例如：△ = 10,000
* 定時器每5000時間單位中斷一次
* 每個頁面在內存中保留2位
* 每次定時器中斷時，複製並將所有參考位的值設置為0
* 如果內存中的其中一位=1，則該頁面在工作集中
* 為什麼這不完全準確？
* （不知道在5000次引用中的具體位置）
* 改進方法：
* 使用10位並每1000時間單位中斷一次

## Page-Fault Frequency
* 需要比工作集更好的方法來控制抖動。
* 比WSS更直接的方法
* 建立“可接受”的頁面錯誤頻率（PFF）並使用局部替換策略
* 如果實際頻率過低，進程失去框架
* 如果實際頻率過高，進程獲得框架

## Working Sets and Page Fault Rates
* 進程的工作集與其頁面錯誤率之間有直接關係。
* 工作集隨時間變化
* 隨時間會有高峰和低谷
* 開始需求分頁一個新的局部性
* 新局部性的工作集在內存中

## Allocating Kernel Memory
* 內核內存通常從一個與滿足普通用戶模式進程所用的列表不同的空閒內存池中分配。
* 主要有兩個原因：
* 內核請求不同大小結構的內存。
* 內核必須節約使用內存，並嘗試最小化由於碎片化造成的浪費。
* 某些內核內存需要連續的
* 例如設備 I/O。
* 管理空閒內存的兩種策略：
* 夥伴系統（Buddy System）
* Slab 分配（Slab Allocation）

## Buddy System
* 從由物理上連續頁面組成的固定大小段中分配內存
* 使用2的冪次分配器分配內存
* 以2的冪次大小（4KB、8KB、16KB等）滿足請求
* 請求向上捨入到下一個更高的2的冪次（例如請求11KB -> 16KB）
* 當需要比可用分配更小的內存時，當前塊將拆分為下一個更小的2的冪次的兩個夥伴
* 繼續進行直到有合適大小的塊可用
* 例如，假設有256KB的塊可用，內核請求21KB
* 拆分為128KB的A_L和A_R
* 其中一個再分成64KB的B_L和B_R
* 其中一個再分成32KB的C_L和C_R - 其中一個用於滿足請求
* 優點：
* 快速將未使用的塊合併成更大的塊
* 缺點：
* 碎片化

## Buddy System Allocator

## Slab Allocator
* 另一種策略：
* Slab 是一個或多個物理連續的頁面。
* Cache 由一個或多個slab組成。
* 每個獨特的內核數據結構都有一個單獨的cache。
* 每個cache填充了對象——數據結構的實例。
* 當cache創建時，填充的對象標記為空閒。
* 當結構存儲時，對象標記為已用。
* 如果slab充滿了已用對象，則下一個對象從空的slab中分配。
* 如果沒有空的slab，則分配新的slab。
* 好處包括：
* 無碎片化
* 快速滿足內存請求

## Slab Allocation

## Slab Allocator in Linux
* 例如，進程描述符是類型為 struct task_struct 的數據結構，大約佔用1.7KB的內存。
* 新的任務 -> 從緩存中分配新的 struct 。
* 將使用現有的空閒 struct task_struct 。
* Slab 可能處於三種可能的狀態：
* 完全滿 - 全部使用
* 空 - 全部空閒
* 部分 - 混合使用和空閒
* 當需要時，slab分配器：
* 使用部分slab中的空閒 struct 。
* 如果沒有，則從空的slab中取一個。
* 如果沒有空的slab，則創建新的空slab。
* Slab技術最初在Solaris中開始，現在在各種操作系統中都廣泛使用，包括內核模式和用戶模式。
* Linux 2.2時有SLAB，現在有SLOB和SLUB分配器。
* SLOB用於內存有限的系統。
* 簡單的塊列表（Simple List of Blocks）- 為小型、中型和大型對象維護3個列表對象。
* SLUB是性能優化的SLAB，去除了每個CPU的隊列，元數據存儲在頁結構中。

## Other Considerations
* 預分頁(Prepaging)
* 頁大小(Page size)
* TLB範圍(TLB reach)
* 倒置頁表(Inverted page table)
* 程式結構(Program structure)
* I/O互鎖和頁鎖定(I/O interlock and page locking)

## Prepaging
* 為了減少進程啟動時發生的大量頁面錯誤：
* 在引用之前，預先加載進程將需要的所有或部分頁面。
* 但如果預加載的頁面未被使用，則I/O和內存將被浪費。
* 假設預加載了s頁面，其中α部分被使用。
* 成本s * α節省的頁面錯誤 > 或 < 預加載 * （1-α）不必要的頁面的成本？
* α接近零時，預加載會損失。

## Page Size
* 有時操作系統設計者有選擇權
* 尤其是在運行於自定義CPU上時。
* 頁面大小的選擇必須考慮以下因素：
* 為了最小化內部碎片，我們需要較小的頁面大小。
* 頁表大小：較小的頁面大小應該導致較少的I/O和較少的總分配內存。
* 減少I/O開銷的愿望支持使用較大的頁面大小。
* 為了最小化頁面錯誤數量，我們需要使用較大的頁面大小。
* 頁面大小始終是2的冪次方，通常在範圍2^12^（4,096字節）到2^22^（4,194,304字節）之間。
* 平均而言，隨著時間的推移而增加。

## TLB Reach
* TLB範圍 - 從TLB訪問的內存量
* TLB範圍 = (TLB大小) × (頁面大小)
* 理想情況下，每個進程的工作集存儲在TLB中
* 否則會出現大量的頁面錯誤
* 增加頁面大小
* 這可能導致碎片化增加，因為並非所有應用程序都需要大的頁面大小
* 提供多個頁面大小
* 這使得需要較大頁面大小的應用程序有機會使用它們，而不會增加碎片化

## Program Structure
* 程式結構
* 系統性能可以通過用戶（或編譯器）了解底層的需求分頁來改善。
* int[128,128] data;
* 每一行存儲在一個頁面中

* 程式1

for (j = 0; j < 128; j++)
    for (i = 0; i < 128; i++)
        data[i,j] = 0;

* 128 x 128 = 16,384 個頁面錯誤

* 程式2

for (i = 0; i < 128; i++)
    for (j = 0; j < 128; j++)
        data[i,j] = 0;

* 128 個頁面錯誤

## I/O interlock
* I/O互鎖 - 有時需要將頁面鎖定到內存中。
* 一種情況：考慮I/O - 用於從設備複製文件的頁面必須被鎖定，以防止被頁替換算法選中進行驅逐。
* 將頁面固定到內存中。
* 每個框架都關聯有一個鎖定位。如果框架被鎖定，則不能被選中進行替換。
* 經常情況下，一些或所有的OS內核被鎖定到內存中。
* 虛擬內存是實時計算的對立面，因為它可能會在將頁面加載到內存時引入意外的長期延遲，而這會影響進程的執行。
* 實時系統幾乎從不使用虛擬內存。

# Operating System Examples
* Windows
* Solaris

## Windows
* 使用需求分頁與聚類(clustering)。聚類將帶入周圍的頁面。
* 進程被分配工作集最小值和工作集最大值。
* 工作集最小值是進程保證在內存中擁有的頁面的最小數量。
* 一個進程最多可以分配多少頁面，取決於其工作集的最大值。
* 當系統中的空閒內存量下降到一個閾值以下時，將執行自動的工作集修剪，以恢復空閒內存的量。
* 工作集修剪會從具有超出其工作集最小值的頁面的進程中移除頁面。

## Solaris
* 維護一個空閒頁面列表，分配給發生錯誤的進程。
* Lotsfree - 閾值參數（空閒內存量），開始進行分頁。如果空閒頁面數量低於lotsfree，則一個進程開始進行分頁。
* Desfree - 增加分頁的閾值參數。
* Minfree - 開始交換的閾值參數。
* 分頁由pageout進程執行。
* Pageout使用修改過的時鐘算法掃描頁面。
* Scanrate是掃描頁面的速率（將未引用的頁面放入空閒列表）。這個速率從slowscan到fastscan不等。
* 根據可用的空閒內存量，pageout被更頻繁地調用。
* 優先級分頁優先處理進程的代碼頁面。

## Solaris 2 Page Scanner

# Inportant Sentance
1. Why swapping would be difficult if no paging? => you don't have to consider the size of the memory you are swapping
2. Sequence must be right for page fault handling
3. Why we use vfork()? Suppose child wil call exec() to replace itself into another program
4. reel fast you will use the page -> should not take it out