考慮一個分頁系統(paging system),page size 為 2KB,實體記憶體(physical memory)大小為 64KB。令 P 表示實體位址(physical address)所需的位元數,L 表示邏輯位址(logical address)所需的位元數。
傳統做法(conventional way)中,記憶體裡儲存一個 single-level page table,若以傳統方式實作,page table 在記憶體中含有 1024 筆 entries。記憶體存取時間為 180 奈秒(ns)。假設傳統 page table 的 hit ratio 為 60%,平均 page fault service time 為 30,000 微秒(μs)。因此,傳統做法(single-level page table)的 effective memory access time 為 X。
Alex 想考慮使用 "inverted page table" 來改善邏輯位址轉實體位址的轉換。經仔細計算後,他發現 inverted page table 需要 N 筆 entries。此外,Alex 考慮使用 translation look-aside buffer (TLB) 硬體來實作 inverted page table 的概念。搜尋 TLB 需要 20 奈秒(ns)。假設 inverted page table 的 hit ratio 為 90%。Alex 做法(TLB-implemented inverted page table)的 effective memory access time 為 Y。因此,Alex 的做法改善了 effective memory access time,其中 A < speedup(以 effective memory access time 計) < B,這裡 A、B 為正整數。
請計算 P、L、X、N、Y、A、B 的值,選出正確的敘述。
參考答案與解析
答案 (A)。P=log2(64KB)=16;page table有1024=2^10筆entries,加上page size 2KB=2^11(offset 11 bits),故L=10+11=21。X(傳統single-level page table)=0.6×(180+180)+0.4×30,000,000ns=12,000,216ns。inverted page table的N=實體frame數=64KB/2KB=32。Y(TLB+inverted page table)=0.9×(20+180)+0.1×30,000,000ns=3,000,180ns。speedup=X/Y≈3.9997,介於3與4之間,故A=3,B=4(正整數上下界)。代入(A) 2L+3P+5N+A³+B²=2(21)+3(16)+5(32)+27+16=42+48+160+27+16=293,恰好成立;其餘選項代入皆不成立。