多階分頁系統的問題

近來天逐漸變得涼爽了。一早在辦公室把門打開，邊聽廣播邊享受悠閒時光。突然有人敲門，原來是兩個大學部的學生，說要問我一個作業系統問題。

作業系統是我隔壁辦公室老師上的課，想必是時間還早，這兩位學生找不到老師，看我辦公室門是開的，所以過來碰碰運氣。

她們的問題是這樣的。有一個五階的分頁系統(Paging System)，總共用了50個位元作為分頁號碼(Paging Number)，如下圖所示：

學生的問題是為何這五階的分頁系統，分別用了四個12位元與一個2位元的位址，一定要像上圖那樣排列，為何不是像下面這樣的設計。

也就是為何兩位元的那階一定要是第一階，而不是放在最後一階？

由於好久沒有碰作業系統了，她們的問題我以前也沒有想過，所以就老實告訴她們這個問題我要想一下。這兩位學生也就很客氣的告退。

她們走後，我拿起紙筆推算了一下，很快就瞭解這是簡單的問題，可惜追出去她們已經走遠了。

把問題簡化一下就可以明白為什麼。考慮下面這種兩階的分業系統。

我們可以計算這樣的設計下，儲存分頁表(Paging Table)所需要的空間。第一階分頁表中有2的2次方共4筆記錄。第二階分頁表共有4個，每個分頁表共需2的12次方筆記錄。故總共所需的紀錄數目為

2^2 + 2^2 * 2 ^ 12           ...(1)

如果是下面這樣的設計，則分頁表所需的記錄數目依照上面的推論可得為

2^12 + 2 ^ 12 * 2^2         ...(2)

上面(1)(2)兩式的第二項相同，但(1)式的第一項較小，所以知道前一種設計比較省儲存空間。