假設我們有一個 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 的值,選出正確的敘述。
參考答案與解析
答案 (B)。32-bit處理器,page size 8KB=2^13,故D=13,P=32-13=19。將10個十六進位位址右移13位得page number序列:A,B,A,B,C,D,C,D,B,E(5個不同page)。以W=6計算每個時間點trailing window的distinct page數,最大值M=4(出現在第6、7、8、10個參考點)。以3個frame模擬locality-based置換(依window內該頁被參考次數/W排序,最少者淘汰,同分用LRU):依序在第1、2、5、6、7、10次參考發生page fault,共F=6次。代入(B) M+D+P+F=4+13+19+6=42,恰好成立;其餘選項不成立。