2017年12月19日 星期二

OS - Ch9 虛擬記憶體 Virtual Memory

於
標籤：
 

虛擬記憶體是記憶體管理的一部份，由於議題較多獨立出一個章節，enjoy it : )

2015.1.15 初版
2017.8.24 二版
2017.12.19 新增 Memory-Mapped Files 章節




一、虛擬記憶體


虛擬記憶體 (Virtual Memory) 會讓應用程式認為其擁有連續可用的記憶體（一個連續完整的位址空間），而實際上，其通常是被分隔成多個實體記憶體碎片，還有部分暫時儲存在外部磁碟記憶體上，需要時才進行資料交換。

優點：

  • 允許程式大小大於實體記憶體 (physical memory) 大小情況下，程式仍然能執行。 
  • OS 的負擔，程式設計師無負擔。
  • 記憶體的各個小空間皆有機會被利用到，記憶體使用度上升。
  • 提高 multiprogramming degree，提昇 CPU 使用度。
  • 每一次的 I/O transfer time 下降，因為不用將整個程式的所有 page 載入。(然而載入整個程式很耗費 I/O transfer time，因為總傳輸次數變多。)


1. 實現 Virtual Memory 方法：Demand Paging


 以 paging 為基礎，採用 lazy swapper 技巧。即程式執行之初不將全部的 pages 載入 memory，僅載入執行所須的 pages，如要處理 page fault 問題，由 OS 另行處理。

  • 多加一個 Valid/Invalid Bit 欄位，用以指示 page 是否在 memory 中。  
  • Effective Access Time (EAT) = (1 – p) x memory access + p (page fault overhead + swap page out + swap page in + restart overhead)  



2. Copy on Write


copy-on-write (COW) 是一種最佳化策略，在 copy-on-write 策略中如果有多個呼叫者同時要求相同資源（如記憶體或磁碟上的資料儲存），則他們會共同取得相同的指標指向相同的資源，直到某個呼叫者試圖修改資源的內容時，系統才會真正複製一份專用副本給該呼叫者，而其他呼叫者所見到的最初的資源仍然保持不變。

因此，將 copy-on-write 應用在 parent fork child process 時，只有 child process 改變 page 內容時才配新 frame (copy)，如此一來可以增加建立 process 的效率，因為大部分情況 child process 並不會對資料段寫入。


fork 使用 copy-on-write 的探討：

  • fork() 使用 copy-on-write
    • parent process 會和 child process concurrent 執行，要達到這種效果，CPU 要有 MMU 硬體支援。
  • vfork() 不使用 copy-on-write
    • parent 和 child process 除了 stack 其他都共享。 
    • vfork() 通常用於沒有 MMU 的 OS，此時 parent process 會被暫停，直到 child process執行了 exec() 或 exit()。







二、Page Replacement Algorithm


當 page fault 發生且 memory 無可用 page 時，則 OS 必須執行 page replacement。OS 必須選擇一個 victim page，將其 swap out 到 disk 來空出一個可用 frame，再將 lost page swap in 到此 frame。

  • swap out 和 swap in 分別是 2 個 disk I/O 的動作 (慢!)。
  • swap in 是必要的，一定要將 lost page 置入到 memory 中。
  • swap out 不盡然是必要的！需視 victim page 是否曾被修改，利用 dirty bit 來判斷，節省不必要的 I/O 動作。 


1. Page Replacement Algorithms



FIFO：最先載入的 page 優先視為 victim page。 

  • 簡單，易於實作 
  • 效果挺差的，但不代表是最差的 (在 page replacement 沒有最差，因為無法預知未來)
  • 可能有 Belady 異常現象：當Process分配到較多的Frame數目其Page Fault Ratio不降反升。 


OPT：以將來長期不會使用的 page 視為 victim Page。 

  • 效果最佳
  • 不會有 Belady 異常現象 
  • 不可能辦到，因為是看未來！不過可以知道 upper bound。


LRU：以最近不常使用的 page 視為 victim page。

  • 效果不錯 (Page fault ratio尚可接受)
  • 不會有 Belady 異常現象
  • 製作成本高，需要大量硬體支援 (如:需要Counter或Stack) 


LFU：參考次數最少的 page 作為 victim page。

  • Need time to warm up and cool down (aging) a page



[用心去感覺] LRU and OPT algorithm never suffer from Belady's anomaly 

idea : 數學歸納法。LRU and OPT belong to a class "stack algorithm".

the set of pages in RAM when frame #=n is a subset of the set of pages in RAM when frame #=n+1. When there are n+1 frames, LRU will include one more least recently used page. So does OPT.



2. LRU 近似法則 


由於 LRU 製作成本過高，因此產生以下方法近似 LRU 效果。這些近似方法都有可能退化成 FIFO，會遇到 Belady 異常情況。


1. Second Chance

以 FIFO 法則為基礎，搭配 Reference Bit 使用。

每個 page 的初始值 reference bit 值設為 1，每次被指到的 page 其 reference bit 值就改為 0，然後指下一個 page，如果下一個被指到的 page 其 reference bit 值為 0 的話，則替換該 page。


2. Enhance Second Chance

這個改進 second chance 的方法是為了減少 I/O，使用 (Reference Bit, Modification Bit) 配對值作為挑選 Victim Page 的依據。下列情況越上面越容易成為 victim page :

  • (0,0)：最近沒被用到過也沒被修改過。
  • (0,1)：最近沒被用到過，但是有被修改過。
  • (1,0)：最近有被用到過，但是沒被修改過。
  • (1,1)：最近有被用到過，也有被修改過。



3. Prepaging


Prepaging 會事先猜測程式執行之初會使用哪些 page，並預先將這些 pages 載入。

  • 優點：若猜得準確，則可以避免程式執行之初大量 Page Fault 發生。 
  • 缺點：若猜測錯誤，則先前載入 page 的 I/O 動作白白浪費。


而 pure demand paging 程式執行之初不預先載入任何 page，執行之初會產生大量的 page fault，由於載入的 page 皆是 process 所需的頁面，故後續的 page fault ratio 會下降至合理值 (趨於穩定)。




三、Performance Issue



1. frame 的分配多寡對 page fault ratio 之影響


一般來說，Process所分配到的 frame 愈多，則 page fault ratio 愈低。 process 所分配的頁框數目有最少數目與最大數目的限制，此兩類數目限制均取決於硬體因素。
  • 最大數目的限制：由 physical memory size 決定 
  • 最少數目的限制：由機器指令結構決定，必須能讓任何一個機器指令順利執行完成，即機器指令執行過程中，Memory Access可能之最多次數。
    • e.g. IF - ID - EX - MEM - WB 中，IF 必有記憶體存取，MEM、WB可能有必有記憶體存取，因此最少的 frame 數目為 3。


2. page size 對 page fault ratio 之影響 (TLB reach)


page size 愈小則 ...

缺點：

  • page fault ratio 愈高
  • page table size 愈大
  • 執行整個 process 的 I/O 時間愈大 

優點：

  • 內部碎裂愈小
  • 單一 page 的 transfer Time 愈小
  • locality愈集

目前趨勢傾向於設計大的 page size。

[感覺] TLB size 加大 : cost 高且 entry 數增加有限，不一定能涵蓋 working set。


3. page structure 對 page fault ratio 之影響


所使用的資料結構與演算法是不是好的。判斷好或不好，在於符不符合 locality。

  • Good : Loop, Subroutine, Counter, Stack, Array, Sequential Code Execution, Global Data Area, Sequential Search. 
  • Bad : Link list, Hashing Binary Search, goto, jump.

array 的相關處理程式，最好與 array 在記憶體中的儲存方式一致 (即 Row-major, Column-major 相關概念)。


4. I/O interlock


Pages must sometimes be locked into memory. Consider I/O. Pages that are used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm.




四、Thrashing


Thrashing 現象：

  • 若 Process 分配到的 frame 不足，則會經常發生 page fault，此時必須執行 page replacement。
  • 若採用 global replacement policy，則此 process 會替換其它 process 的 page 以空出 frame，造成其它 process 也會發生 page fault，而這些 process 也會去搶其它 process 的 frame，造成所有 process 皆在處理 page fault。
  • 所有 process 皆忙於 swap in/out，造成 CPU idle。(CPU idle 時 OS 會企圖引進更多的 process 進入系統讓 Thrashing 現象更嚴重。)




Thrashing的解決方法：

1. 降低 multiprogramming degree

2. 利用 page fault ratio 控制來防止 thrashing

OS 規定合理的 page fault ratio 之上限與下限值，把 ratio 控制在一個合理範圍內。
  • 若某 process 的 page fault ratio > 上限值，則 OS 應多分配額外的 frame 給該 process。 
  • 若某 process 的 page fault ratio < 下限值，則 OS 應從該 process 取走多餘的 frame，以分配給其它有需要的 process。


 3. 利用 working set model

預估各 process 在不同執行時期所需的 frame 數目，並依此提供足夠的 frame 以防止thrashing。

緣由：process 執行時對於 memory 的存取區域具 locality 性質。

  • Temporal locality：Process目前所存取的記憶體區域過不久後會再度被存取，e.g. loop, subroutine, counter, stack. 
  • Spatial locality：process 目前所存取的記憶體區域其鄰近區域極有可能也會被存取，e.g. array, sequential code execution, global data area.

作法：OS 設定一個 working set window size t，以 t 次記憶體存取中，所存取到的不同Page 之集合，此一集合稱為 working set。而 working set 中的 process 個數，稱為 working set size (WSS)。



假設有 n 個 processes，令：

  • WSSi 為 process i 在某時期的 working set size。 
  • D 為某時期所有 process 之 frame 總需求量，D 為所有 process 的 WSS 總和。
  • M 為 physical memory 大小 (可用 frame 總數) 

  1. D ≤ M，OS 會依據 WSSi，分配足夠的 frame 給 process，可防止 thrashing。 
  2. D > M，則 OS 會選擇 process 暫停執行，直到 D ≤ M 為止，此時回到 1. 處理，等到未來 frame 足夠時再恢復原先暫停的 process。

優點：

  • 可以防止 thrashing 產生，對於 prepaging 亦有幫助。 

缺點：

  • 以上一次的 working set 來預估下一次的 working set，不易制定精確的 working set。
  • 若前後的 working set內容差異太大，則 I/O transfer time 會拉長。




五、記憶體映射檔案 Memory-Mapped Files


記憶體映射檔案 (Memory-Mapped Files) 會讓一段虛擬記憶體對應於一個檔案，將檔案 I/O 視為經常性的記憶體，而非一般的 open(), read(), write() 標準系統存取。這讓程式設計師可以藉由撰寫記憶體映射檔案相關的函式庫程式 (如 c 的 mmap, java 的 java.nio package) 直接從虛擬記憶體讀取檔案內容，達到加速 I/O 效能的目的，整理其特性如下：

  • 高速檔案存取 (主要目的)
    • 比直接讀寫檔案快幾個數量級
    • 傳統檔案每次被讀取時需要一次系統呼叫和一次磁碟存取
  • 將大檔案載入到記憶體。
    • 導致內部碎片空間浪費 (對齊頁，通常為 4 KB)。
    • 對映檔案區域的能力取決於於記憶體定址的大小：在 32 bit 機器中，不能超過 4GB。
    • 可能導致頁面錯誤的數目增加
  • 可讓多個程式共享記憶體，直接對記憶體進行讀取和寫入來修改檔案。 
  • 使程式動態載入
    • 為 Linux dynamic loading 實作方式。



[範例] 記憶體映射檔案函數 mmap

Linux 提供了記憶體映射檔案的函數 mmap，它把檔案內容映射到一段虛擬記憶體，

(範例待補)





References


Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720

聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/

洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057

藏經閣 - fork()與vfork()的比較
http://tw.tonytuan.org/2009/04/vforkuclinux.html

Javin Paul - 10 Things to Know about Memory Mapped File in Java
https://www.codeproject.com/Tips/683614/10-Things-to-Know-about-Memory-Mapped-File-in-Java
http://translate17.com/article/712

oreilly - Memory-Mapped Files
http://archive.oreilly.com/oreillyschool/courses/Python4/Python4-15.html





技術提供：Blogger.
 
© 2023 Mr. Opengate