一生科科準備資工在職專班讀書筆記 — 作業系統 CH9 Virtual Memory Management

我看了 CH9 的課程後才發現我太早寫 paging 的作業了，有一些進階的細節應該要參考一下 Virtual Memory Management，作業的修改我寫在這篇好了，剛好可以搭配本章內容。

前情提要 CH8 主要探討了關於程式碼到執行程序的記憶體管理方式，使用 page table + MMU 可以映射虛擬的 address 到實體 address，以一個執行程序為單位很方便分配記憶，只要有空位就可以放 page ，但如果一個執行程序就佔滿整個記憶體呢? 是不是整台電腦就被那一個巨大程序獨佔呢? 所以進階一點我們應該要做的是動態載入 page ，進而需要考慮如何抽換 frame 跟分配 frame 給程序，因為當記憶體裡面塞滿越多程序表示每個程序分到的frame 越少，然後產生 page fault 的機率就越高，page fault 發生就需要去 disk 找到缺失的 page ，然後將 page 換到記憶體，而 diskIO 通常是毫秒等級的，表示電腦效率(或說CPU 利用率) 一定會下降，所以接下來就討論各種管理 Virtual Memory 的細節吧!

Demand Paging

就如他的名字，要用的時候再載入 page，所以一開始載入程序 kernel 要為了程序建立 process control block 跟一個空白的 page table，可以先載入 virtual address 但是對應的 physical address 可以空白，然後需要 valid bit 欄位，也都先填入 false (表示 invalid)，當要執行程式時，一定會發生 page fault 然後才載入需要的 page 然後 PC (program counter ) - 4 然後執行目標機器碼，通成一個 page 4 KB 對於 32 bit 電腦來說可以放入 1024 條指令，接下來因為 cache locality ，所以雖然 page fault 需要 access disk 的成本，但是發生的機率會相對低

Page fault

page fault 是當 kernel 查找 page table 時，發現 valid bit 欄位是 false ，所以其實 page fault 是一種 trap (軟體中斷)，我記得之前考古題被騙過QQ，page fault 也可能來自兩種狀況

1. 完全沒有載入過

2. 載入過但是被 swap 機制換到 disk

Copy-on-Write

當需要開一個新的程序 kernel 會執行 fork() ，這時 kernel 為新程序產生一個新的 PCB (新的PID) 但是其內容物(如: page table)都會跟被 fork 的程序共享，直到兩個程序發生變化才產生新的各自的 page。

Memory-Mapped Files

直接將 disk 檔案跟記憶體 mapping

原本的檔案機制是由 kernel fs 管理，Memory-Mapped Files 則可以跳過 kernel 的交互層，缺點是相對難管理，需要自行建立更新到 disk 的時機跟邏輯。

Demand segmentation

除了 Demand Paging 其實也可以 Demand segmentation 問題是 segmentation 大小並不固定，這表示在找空位的時候比較好費時間而且也容易把空間碎片化，所以通常不會這樣做!

other

segmentation 我一直很不懂到底是何時作用的，問了ai 後才比較清楚，首先segment 可以分成 code, data, stack 這在 elf 裡面會分配不同的 virtual address 範圍，這樣也比較好管理，當一開始建立 PCB 時，即可分配 page 涵蓋多大的 segment，且不同類型 segment 通常不會放同一個 page 這樣也比較好管理 valid bit ，如 runtime 中才執行 malloc() 要用到 heap，那也是 runtime 才建立內容物是 heap 區段的 page，如下圖，如果程式有 bug ，在取 heap 內容物時指到 0x3000 -0x7fff 之外的 virtual address 就會跳出 segmentation fault。

Page Replacement

dirty bit

既然大家要輪流使用 frame 就需要 write back 機制，所以 page table 需要在加入 dirty bit 欄位，當需要把 page 踢出 frame 時，應該要檢查 dirty bit 欄位，確保修改過的資料有同步到 disk。

Algorithms

確保 page fault 機率越少越好

First-In-First-Out (FIFO) Algorithm

這應該毋需多言，會發生 Belady’s Anomaly 就是說加大 frame 總數並不會改善效率

Optimal (Belady) Algorithm

未來用不上的先換。通常 scheduling 應該一次就把整個 future plan 做完，很多時候 future plan 也是動態的，所以這個演算法不太容易實現。

LRU Algorithm (Least Recently Used)

• Counter implementation : 需要另外 maintain counter 跟 timestamp
• Stack implementation : 使用一個 double linked list ( why double linked list ? : 當 page hit 該 page 需要被提到 Stack 最底層，page fault 則要剔除Stack 最上層，所以跟以往的 stack 機制有點差別，需要 list 比較好實現 )

Other Algorithm

Allocation of Frames

假如有指令橫跨多的 page 該怎麼半，我們應該確保每個 process 可以分配一定數量的 page 到 frame 才合理

• Fixed allocation:

一開始就訂好 frames 大小，固定或是依程序比例，需要抽換 page 就使用 Local allocation，因為一開始就分配好位置了，所以就與分配好的位置抽換就好。

• Priority allocation:

可以選擇與自己已經在 frame 中的 page 換或是將 Priority 較低的程序的 page 換掉，通常對於效能比較好，必須設置 minimum number of frames ，不然可能發生 Thrashing。

Thrashing monitor

使用 CPU 用 register 運算、 CPU 跟 register 跟 memory 交互、 disk 跟 memory 交互來完成一項任務，幾乎不可能做到平行執行，當讀到一行機器碼發現資料還沒在 memory ，需要先從 disk 找到搬運到 memory ，然後運算時又把數值載入 register 才能利用 ALU ，因此如果 memory 中 process 越多能分配到的 frames一定減少，frames 越小快取命中率就越低，則電腦卡在 disk 跟 memory 交互越頻繁 CPU 利用率就越下降，尷尬的是電腦發現CPU 利用率又會推論可能是 memory 中 process 太少了，接著情況就更加糟糕。

為此有兩個方式解決:

• Working-Set Model: 計算固定時間內 process 用了多少 page，就分配多少 frame (Working-Set)，把運行中的 process 的 Working-Set 加總如果 > total frame 表示 Thrashing 正在發生，monitor 成本很高。

• Page Fault Frequency Scheme:

設置 upper bound , lower bound 利用新增或停止 process 維持 Page Fault Frequency 在目標區間，即可避免 Thrashing

修改 Paging 作業

之前寫的有點不合理，一開始分配就寫死 physical ，要做 demand paging 應該一開始 table 的 physical address 無須配置且 valid bit 填入 false。

原本的 code 先分配了 physical address

修改版 code/userprog/addrspace.cc

AddrSpace::Load 則是會將程式碼載入記憶體而且ㄧ旦執行就把所有程式碼放到記憶體，一樣會違反 demand paging ，所以這步驟把記憶體 assign 全部捨棄，相反可以把讀取的 elf 相關資訊都先記起來 SegmentInfo

修改版 code/userprog/addrspace.cc, addrspace.h

如果你嘗試重新編譯執行應該會遇到 Unexpected user mode exception 2 ，也就是 page fault

exception 被定義在 code/machine/machine.h

往下 trace 會發現錯誤傳遞到 exception.cc ，應該在這邊攔截處理，BadVAddrReg 紀錄是哪個 virtual address 遇到 page fault 應該為它載入 page 到 memory

修改版 code/userprog/exception.cc

新增 AddrSpace::HandlePageFault 找到 virtual address 跟需要載入的區段並更新 page table

修改版修改版 code/userprog/addrspace.cc, addrspace.h

重新編譯後執行

最後討論

我其實還是很不會，多靠 ai 寫的，其中我發現在取得 virtual address page fault 要載入 page 這段期時有個地方小小奇怪，在找 virtual page number 時，理所當然的會用 virtual address / page size ，但是我前面也提到了 code segment 會分段分配 address ，所以當 address 跨度很大表是中間會有很多 virtual page number 其實不需要用到，但是如果查表要快就一定是用 array 或是 hash table ，如果是稀疏表該怎麼半，空很多沒用的 entry?

ai 說 hierarchy page table 可以解決這個問題，所以目前我的 NachOS 還是有這快不夠完善QQ，現在能跑是因為測試碼很小，之後有需要再來完善吧~

最近緩慢的在看 Scott Meyers 的 Effective Modern C++ ，第一章都還沒看完就已經覺得很撞牆，我的 C++ 學得很隨便，大多時候是寫 leetcode 一邊查語法練的，所以其實我一直跟 C++ 的 pointer , reference 很不熟，現在這本書教進階的程式碼封裝搭配 compiler 規則，資訊量整個大爆炸，我的一個小方法就是去問 AI 這個東西(lvalue, rvalue, type deduction)當初設計的目的是什麼，通常會比較有幫助於理解為甚麼會有這些語法或是用法(不同型別的變數傳到 type deduction 後的行為)，排列組合的出來的結果實在太多我還在消化。

主要是想發表一下感想，難怪沒有 C++ programmer 敢說自己是 coding 高手。