作業系統›Ch8 虛擬記憶體
第 3 題/共 47 題
◀ OS 3/47
3. Paging、Working Set Model、Page Replacement、Virtual Memory
#OS-08-003難PagingWorking Set ModelPage ReplacementVirtual Memory

假設我們有一個 32-bit 處理器的電腦系統,該電腦支援 paged virtual memory。page size 為 8KB。處理器參考的每個位址包含 P 個位元用來索引 page number,D 個位元用來索引 page offset。一開始給定三個空的 frame 來執行一個 process。假設處理器依序參考下列十六進位(hexadecimal)位址來執行該 process:

4DF6BC24 1CA54523 4DF6AC24 1CA55523 23A22260 23BCDFFF 23A23261 23BCCFFF 1CA54523 23B23261

系統中實作了 working-set model,working-set window 大小為 W=6。一般來說,process 傾向有記憶體參考的 locality。Alex 觀察上述參考位址序列所產生的 working set 大小,發現這個參考序列中 working set 的最大大小為 M。因此,Alex 依 locality 原則設計了一個 locality-based 頁面置換演算法。為了實作這個演算法,他將「每個 page 的 referenced likelihood」量化為:該 page 在 working-set window 內被參考的總次數,除以 working-set window 的大小。注意 working-set window 內被參考的 pages 包含處理器目前正嘗試參考的那個 page。當一個十六進位位址被參考時,演算法需要追蹤每個 page 的 referenced likelihood。若發生 page fault,referenced likelihood 最小的 page 會被替換。若多個 pages 有相同的 referenced likelihood,則用 Least Recently Used (LRU) 演算法來打破平手。因此,處理器參考上述十六進位位址序列所產生的總 page fault 數為 F。

請計算 P、D、M、F 的值,選出正確的敘述。

📄 台大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 作業系統》Ch8 虛擬記憶體
本章題號 · 1–20 / 47