首頁

# Background

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

優點：

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

# 實現 Virtual Memory 方法

# Demand Paging


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

  • 多加一個 Valid/Invalid Bit 欄位，用以指示 page 是否在 memory 中。

# Demand Paging Performance

Effective Access Time (EAT) = (1 – p) x memory access + p

p = (page fault overhead + swap page out + swap page in + restart overhead)

  • 存取時間會正比於 page fault time（因為 page fault time 所花時間大）
  • program 通常都是 locality 的 reference（access 在附近的 memory）–-> 一個 page fault 會帶進 4KB 的 memory content，降低 page fault 發生的機會

# Copy-on-Write

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

# 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

當 page fault 發生且 memory 無可用 page 時，則 OS 必須執行 page replacement。

  1. OS 必須選擇一個 victim page，將其 swap out 到 disk 來空出一個可用 frame
  2. 再將 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 動作

# Page Replacement Algorithms

  1. FIFO：最先載入的 page 優先視為 victim page
    • 簡單，易於實作
    • 效果挺差的，但不代表是最差的 (在 page replacement 沒有最差，因為無法預知未來)
    • 可能有 Belady 異常現象：當 Process 分配到較多的 Frame 數目其 Page Fault Ratio 不降反升
  2. OPT：以將來長期不會使用的 page 視為 victim Page
    • 效果最佳
    • 不會有 Belady 異常現象
    • 不可能辦到，因為是看未來！不過可以知道 upper bound
  3. LRU：以最近不常使用的 page 視為 victim page
    • 效果不錯 (Page fault ratio 尚可接受)
    • 不會有 Belady 異常現象
    • 製作成本高，需要大量硬體支援 (如：需要 Counter 或 Stack)
  4. LFU：參考次數最少的 page 作為 victim page
    • Need time to warm up and cool down (aging) a page

# LRU 近似法則

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

  • Second Chance：以 FIFO 法則為基礎，搭配 Reference Bit 使用
    1. 每個 page 的初始值 reference bit 值設為 1，每次被指到的 page 其 reference bit 值就改為 0，然後指下一個 page
    2. 如果下一個被指到的 page 其 reference bit 值為 0 的話，則替換該 page
    • 如果 reference bit 值為 1 的話，則將其改為 0，然後指向下一個 page，重複步驟 2
  • Enhance Second Chance
    這個改進 second chance 的方法是為了減少 I/O，使用 (Reference Bit, Modification Bit) 配對值作為挑選 Victim Page 的依據。下列情況越上面越容易成為 victim page :
    1. (0,0)：最近沒被用到過也沒被修改過
    2. (0,1)：最近沒被用到過，但是有被修改過
    3. (1,0)：最近有被用到過，但是沒被修改過
    4. (1,1)：最近有被用到過，也有被修改過

# Prepaging

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

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

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

# Allocation of Frames

# Frame Allocation

  • Fixed allocation
    1. Equal allocation：每個 process 配到的 frame 數目一樣
    2. Proportional allocation：配置數目依據 process 的大小做成長
  • Priority allocation
    • dynamic
    • 利用 Proportional allocation 基於優先權，而不是 size
    • 從優先權低的 process 拿走它的 frame 做替換
  • Local allocation
    • 每個 process 從自己被配給到的 frame 做替換
  • Global allocation
    • process 從全部的 frame 挑選做替換
      eg. 允許高優先權的 process 拿走低優先權的 process 的 frame
    • 好的 performance，使用普遍
    • 每個 process 的一個最小的 frame 數目應該被維護以避免 Thrashing

# Thrashing


一個 process 發生 thrashing 的狀況是在 paging 所花的時間比執行指令還要多

# 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
    • 作法：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 會拉長

# Ref Notes

  • Kipper’s Note
  • Chang-Chia-Chi’s Note
  • 陳品媛的筆記
  • Mr. Opengate. OS - Ch9
  • WillyWangkaa’s Note