# OS筆記-Chapter 9: Virtual Memory

###### tags: `OS`
---
#### 目錄
* 總論
[Chapter 1: Introduction](https://hackmd.io/NoZq3J7IQvOQpcbo_tctjA)
[Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A)
* 行程管理
[Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ)
[Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw)
[Chapter 5: CPU Scheduling](https://hackmd.io/IT5g2wHzTdOtMSDXPVEpOw)
[Chapter 6: Process Synchronization](https://hackmd.io/rv-PNe3ESxi08PElyUTc4Q)
[Chapter 7: Deadlocks](https://hackmd.io/Uu0jDK-rSyKNKq690y146g)
* 記憶體管理
[Chapter 8: Main Memory](https://hackmd.io/4KS_yPkBQzGZfHDisPciog)
<font color="red">Chapter 9: Virtual Memory</font>
* 儲存裝置
[Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg)
[Chapter 11: File System Implementation](https://hackmd.io/bFcrlmefQsGp6hZdbI1MHQ)
[Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q)
[Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg)
* 保護和安全
[Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw)
[Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg)
---

### 背景
* 虛擬記憶體(virtual memory)允許行程可以不必完全存在記憶體中就能執行
* 程式不再被可用實體記憶體總量限制
* 更多程式可一起執行
* 載入或置換各個程式進記憶體所需會減少
* 虛擬記憶體可以比實體記憶體大
* 虛擬位址空間(virtual memory space)
* 只有在堆積或堆疊成長時，虛擬位址空間才需要更多的實體分頁
* 共用程式庫也被視為虛擬位址空間中的一部份(通常唯讀)

### 需求分頁(Demand Paging)
* 程式一開始只載入它所需要的分頁到實體記憶體

* 懶惰置換程式(lazy swapper):當需要某一頁時，將該頁置換進來
* 為置換的輔助記憶體稱為置換空間(swap space)
* 置換程式是處理整個行程，所以使用分頁程式這個詞比較適合

* 分頁錯誤(page-fault)
* 程式想使用一頁尚未被載入記憶體的資料
* 使用有效-無效位元
* 載入需要的頁
* 純粹需求分頁(pure damand paging):直到需要某頁時才把它載入記憶體中

* 參考之區域性(locality of reference):最近剛剛被引用過的一個內存位置容易再次被引用
* 使需求分頁有不錯的效能

* 有效存取時間(effective access time):(1-p)* ma+p*分頁錯誤的時間
* p表示出現分頁錯誤比率(page-fault rate)
* ma(memory acess)表示存取時間

* 以磁碟輸入/輸出作為置換空間，通常要較以檔案系統處理快
* 行程開始前，將全部檔案複製到置換空間
* 分頁被替換時才被複製到置換空間

### 寫入時複製(Copy-on-Write)
* 寫入時複製(Copy-on-Write):一般來說fork()讓父行程與子行程在一開始分享共同的分頁
* 如果有行程想寫入共享的分頁才複製分頁
* 因此許多作業系統對於這些要求提供一池(pool)的空白頁
* 需求時填入零(zero-fill-on-demand):分頁在被配置前已經被填入零，因此清除了此分頁之前的內容

* vfork():不使用寫入時複製，所以必須注意子行程會不會修改父行程的位址空間

### 分頁替換(Page Replacement)
* 過度配置(over-allocating):當每個分頁本來需要10個欄，但有5個欄用不到，因此在40個欄的記憶體中，我們執行8個行程，但任何一個行程可能突然需要它原本的10個分頁，導致欄不足

* 基本分頁替換
* 找一個目前未使用的欄，把它空出來
* 更改分頁表，該欄內容寫入置換空間中
* 分頁錯誤將花兩倍的時間(分頁一出一進)

* 修改位元/髒位元(modify bit/dirty bit)
* 當某頁被改過時，以此位元指示此頁已被修改
* 若某頁沒有修改過，則不需寫回置換空間

* 欄的配置演算法(Frame-allocation algorithm)
* 每個行程配置多少欄
* 哪個欄應該被置換

* 分頁替換演算法(Page-replacement algorithm)
* 最低的分頁錯誤比率
* 欄數越多，通常分頁錯誤越低

* FIFO演算法
* 參考串(Reference string):7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
* Belady's anomaly:配置的欄數增加，分頁錯誤比率卻增加
* 參考串:1,2,3,4,1,2,5,1,2,3,4,5

* 最佳分頁替換(otimal 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

* LRU分頁替換(Least Recently Used Algorithm)
* 替換掉近來最少使用的分頁
* 計數器:在CPU上加入邏輯時中或計數器，每當經過一次記憶體參考後就增加一次，對某頁參考時，就會複製該計數器的值到分頁表上，每次替換最小時間數值的分頁
* 堆疊(stack):將被參考的分頁放到堆疊頂端，堆疊最下面則是近來最少使用的分頁
* 參考串:4,7,0,7,1,0,1,2,1,2,7,1,2

* LRU近似分頁替換法(LRU Approximation Algorithms)
* 參考位元(reference bit):當某頁被參考時被設定，雖然不能知道次序，但能知道那些分頁被使用過
* 額外參考位元:假設8-bit，每次右移一個位元，可代表近8個時間的使用狀況，比較數值大小，數值最小則是近來最少使用的分頁
* 第二次機會演算法(second-chance page-replacement algorithm):以FIFO替換法為主，但當參考位元為1的分頁要被替換時，將參考位元改為0，並給予第二次的機會
* 加強第二次機會演算法
* 以參考位元與髒位元當作依據
1. (0,0):最近沒被存取，也沒被修改
2. (0,1):最近沒被存取，但曾被修改
3. (1,0):最近被存取，但沒被修改
4. (1,1):最近被存取，且曾被修改
* 傾向選擇最近沒被修改的，以降低寫回置換空間所需的時間

* 技術基礎分頁替換(Counting Algorithms)
* 以計數器紀錄每一頁被參考過的次數
* 最不經常使用(LFU,least frequently used):次數最少的被替換
* 最常被使用(MFU,most frequently used):認為次數最少的剛載入不久，將要被使用

* 頁緩衝演算法(Page-Buffering Algorithms)
* 系統有空白欄作為庫存
* 在犧牲欄被寫出之前，頁先被讀入庫存的欄，犧牲欄寫出後，犧牲欄加入庫存

### 欄的配置(Allocation of Frames)
* 每個行程必須配置一個最少量的欄數
* 欄數太低，分頁錯誤比率上升，影響效能

* 配置演算法
* 同等分配(equal allocation):m個欄分給n個行程，每個行程得m/n個欄
* 比例分配(proportional allocation):每個行程得(該行程虛擬記憶體大小/總行程虛擬記憶體大小)* 欄數

* 全體和區域配置
* 全體替換法(global replacement):行程可以從所有欄選出一個替換的欄，包括其他行程使用中的欄
* 區域替換法(local replaccement):行程只能從自己的欄選出一個替換的欄
* 區域替換法可能因頁數不足而延遲行程，通常全體替換法有較好的效能

* 不一致的記憶體存取(NUMA,non-uniform memory access)
* 主記憶體上某些部分被CPU存取的時間比其他部分來的快，取決於CPU與記憶體如何連結
* 必須改變原本視記憶體存取速度一致的演算法，盡可能最小延遲的配置記憶體欄到CPU上的行程
* 地址群組(lgroup):聚集了接近的CPU和記憶體，利用地址群組來配置行程的所有記憶體

### 輾轉現象(Thrashing)
* 輾轉現象
* 若行程沒有足夠的欄，需要新的欄時，將其他行程正在使用的欄替換，等等又要替換回來，導致不斷的出現分頁錯誤
* CPU排班程式發現CPU使用率降低，所以增加多元程式規劃程度，再度導致分頁錯誤增加(替換掉別的行程的欄)

* 優先權替換演算法(priorty replacement algorithm)
* 從自己的欄選出一個替換的欄
* 先替換優先權低的欄
* 不會引起其他行程的輾轉現象
* 但本身會需要等待較長的分頁錯誤時間

* 局部區域模式(locality model)
* 一個局部區域就是一組同時被使用的頁
* 一個程式由多個局部區域組成
* 分配足夠的欄以滿足程式的局部區域，能避免輾轉現象

* 工作組模式(working-set model)
* 工作組欄框(working-set window):檢查最近Δ頁參考
* 工作組(working set):這Δ頁中的頁
* t₁時，工作組={1，2，5，6，7}
* t₂時，工作組={3，4}
* WSSᵢ (working set of Process Pᵢ)
* D(對欄的需求) = Σ WSSᵢ
* D > 可用欄數，發生輾轉現象
* 避免輾轉現象，當D大於可用欄數，系統賄選出一個行程被擱置

* 分頁錯誤頻率(Page-Fault Frequency)
* 當錯誤頻率太高，需要更多欄
* 當錯誤頻率太低，行程有太多欄
* 藉由監測分頁錯誤頻率，以防止輾轉現象
* 超過上限的行程，配置欄
* 超過蝦線的行程，收回欄

* 工作群組與分頁錯誤
* 工作群組剛開始移動時，出現較高的分頁錯誤

### 記憶體對映檔案(Memory-Mapped Files)
* 原本每次檔案被讀取時，需要一次系統呼叫和磁碟的存取，記憶體對映檔案將檔案I/O視為經常性的記憶體存取

* 共用記憶體實際上以記憶體對映檔案來製作

* 記憶體對映I/O(Memory-Mapped I/O):使用記憶體對映到裝置暫存器，適合快速回應的裝置(例如:螢幕)

### 核心記憶體配置(Allocating Kernel Memory)
* 核心記憶體通常從可用記憶體池配置，與平常滿足使用者模式行程的串列不同
* 核心為大小不同的資料結構要求大小不一的記憶體
* 有時需要連續的記憶體

* 夥伴系統(Buddy System)
* 使用2的次方配置器(power-of-2 allocator)
* 最初256KB的連續記憶體被分為兩個夥伴Aʟ，Aʀ
* 合併(coalescing):可將相連的夥伴聯合形成更大的區段
* 內部斷裂問題嚴重

* 平板配置(Slab Allocator)
* 平板:由一個或多個實體連續分頁組成
* 快取(cache):由一個或多個平板組成
* 物件(object)與快取一起存在
* 不會有斷裂
* 預先產生物件，因此能很快配置記憶體
* 物件被標示為已使用、閒置

### 其他考慮的因素(Other Considerations)
* 預先分頁(Prepaging)
* 把所有需要的頁在同一時間都載入記憶體中
* 避免行程剛開始執行時出現一大堆分頁錯誤

* 分頁的大小
* 較小的分頁
* 能減少內部斷裂
* 較佳的解析度(resolution)，能將實際需要的記憶體載入
* 較大的分頁
* 能減少I/O時間
* 雖然分頁大小決定轉移時間，但潛伏與搜尋時間遠遠大於轉移時間
* 能減少分頁錯誤的次數

* TLB範圍(TLB Reach)
* 指TLB能存取的記憶體數量
* TLB範圍 = (TLB Size) X (Page Size)
* 加大TLB範圍(加大分頁)，可能導致一些應用程式根本不需要如此大的分頁
* 有些作業系統提供大小不一的分頁大小

* 程式結構
* 假設一頁128個字元組
* 一欄為一頁，因此造成128* 128個分頁錯誤
* 將程式碼改為如下，則可避免
* 使用者對基本需求分頁有所了解的話，對系統性能有很大的幫助

* I/O交互上鎖(I/O interlock)
* 將分頁鎖在記憶體中，以免導致I/O要求被推進到佇列前端時，該分頁被置換，該欄已被其他行程使用