3.1_8 兩級(jí)頁(yè)表

（一）單級(jí)頁(yè)表存在的問(wèn)題

??某計(jì)算機(jī)系統(tǒng)按字節(jié)尋址，支持32位的邏輯地址，采用分頁(yè)存儲(chǔ)管理，頁(yè)面大小為4KB，頁(yè)表項(xiàng)長(zhǎng)度為4B。

??4KB = $2^{12}B$，因此頁(yè)內(nèi)地址要用12位表示，剩余20位表示頁(yè)號(hào)。

??因此，該系統(tǒng)中用戶進(jìn)程最多有$2^{20}$頁(yè)。相應(yīng)的，一個(gè)進(jìn)程的頁(yè)表中，最多會(huì)有$2^{20}=1M=1,048,576$個(gè)頁(yè)表項(xiàng)，所以一個(gè)頁(yè)表最大需要$2^{20}?4B=2^{22}B$，共需要$2^{22}/2^{12}=2^{10}$個(gè)頁(yè)框存儲(chǔ)該頁(yè)表。

??根據(jù)頁(yè)號(hào)查詢頁(yè)表的方法：K號(hào)頁(yè)對(duì)應(yīng)的頁(yè)表項(xiàng)存放位置 = 頁(yè)表始址 + K * 4。

??要在所有的頁(yè)表項(xiàng)都連續(xù)存放的基礎(chǔ)上才能用這種方法找到頁(yè)表項(xiàng)。

??因此，在這個(gè)系統(tǒng)當(dāng)中，某個(gè)進(jìn)程，光對(duì)它的頁(yè)表進(jìn)行存儲(chǔ)，就有可能需要專門分配$2^{10}=1024$個(gè)連續(xù)的頁(yè)框。

??為每個(gè)進(jìn)程都要分配許多連續(xù)的頁(yè)框，這顯然是很吃力的，完全不具備離散存儲(chǔ)的優(yōu)點(diǎn)?！@是單級(jí)頁(yè)表的第一個(gè)明顯的缺點(diǎn)。

??根據(jù)局部性原理可知，很多時(shí)候，進(jìn)程在一段時(shí)間內(nèi)只需要訪問(wèn)某幾個(gè)頁(yè)面就可以正常運(yùn)行了。因此沒(méi)有必要讓整個(gè)頁(yè)表都常駐內(nèi)存。

??這是單級(jí)頁(yè)表存在的第二個(gè)問(wèn)題。

（二）如何解決單級(jí)頁(yè)表的問(wèn)題？

問(wèn)題一

??頁(yè)表必須連續(xù)存放，因此當(dāng)頁(yè)表很大時(shí)，需要占用很多個(gè)連續(xù)的頁(yè)框。

??思考：我們是如何解決進(jìn)程在內(nèi)存中必須連續(xù)存儲(chǔ)的問(wèn)題的？

??答：將進(jìn)程地址空間分頁(yè)，并為其建立一張頁(yè)表，記錄各頁(yè)面的存放位置。——同樣的思路，再次套用，就可用于解決“頁(yè)表必須連續(xù)存放”的問(wèn)題，把必須連續(xù)存放的頁(yè)表再分頁(yè)。

??解決方案：

??可將長(zhǎng)長(zhǎng)的頁(yè)表進(jìn)行分組，使每個(gè)內(nèi)存塊剛好可以放入一個(gè)分組（比如上個(gè)例子中，頁(yè)面大小4KB，每個(gè)頁(yè)表項(xiàng)4B，每個(gè)頁(yè)面可存放1K個(gè)頁(yè)表項(xiàng)，因此每1K個(gè)連續(xù)的頁(yè)表項(xiàng)為一組，每組剛好占一個(gè)內(nèi)存塊，再將各組離散地放到各個(gè)內(nèi)存塊中）。

??另外，要為離散分配的頁(yè)表再建立一張頁(yè)表，稱為頁(yè)目錄表，或稱外層頁(yè)表，或稱頂層頁(yè)表。

問(wèn)題二

??沒(méi)有必要讓整個(gè)頁(yè)表常駐內(nèi)存，因?yàn)檫M(jìn)程在一段時(shí)間內(nèi)可能只需要訪問(wèn)某幾個(gè)特定的頁(yè)面。

??解決方案：

??可以在需要訪問(wèn)頁(yè)面時(shí)才把頁(yè)面調(diào)入內(nèi)存（虛擬存儲(chǔ)技術(shù)）。可以在頁(yè)表項(xiàng)中增加一個(gè)標(biāo)志位，用于表示該頁(yè)面是否已經(jīng)調(diào)入內(nèi)存。

??缺頁(yè)中斷肯定是在執(zhí)行某條指令、這個(gè)指令想訪問(wèn)到某一個(gè)暫時(shí)還沒(méi)有被調(diào)入內(nèi)存的頁(yè)面而產(chǎn)生的。所以，這個(gè)中斷信號(hào)和當(dāng)前執(zhí)行的指令有關(guān)。因此，這種中斷應(yīng)該屬于內(nèi)中斷。（對(duì)于缺頁(yè)中斷的相關(guān)內(nèi)容，在之后會(huì)更加詳細(xì)的介紹）

（三）兩級(jí)頁(yè)表的原理、地址結(jié)構(gòu)

??32位邏輯地址空間，頁(yè)表項(xiàng)大小為4B，頁(yè)面大小為4KB，則頁(yè)內(nèi)地址占12位。

??頁(yè)號(hào)占20位，則進(jìn)程最多有$2^{20}$個(gè)頁(yè)面。

??按照剛才的思路，我們可以把這么大的一個(gè)頁(yè)表，拆分成多個(gè)小的分組。每個(gè)小分組的大小可以讓它剛好能夠裝入一個(gè)內(nèi)存塊。

??我們每個(gè)內(nèi)存塊的大小是4KB，而頁(yè)表項(xiàng)的大小是4B，所以一個(gè)頁(yè)面可以存放1K個(gè)頁(yè)表項(xiàng)。——所以，我們把這個(gè)大的頁(yè)表拆分成一個(gè)個(gè)的小分組，其中，每個(gè)小分組當(dāng)中也有1024個(gè)頁(yè)表項(xiàng)，如圖所示。

??另外，我們給這些“小頁(yè)表”進(jìn)行編號(hào)，0號(hào)頁(yè)表、1號(hào)頁(yè)表……、1023號(hào)頁(yè)表。

??進(jìn)行這樣的拆分后，我們就把$2^{20}$個(gè)頁(yè)表項(xiàng)的大頁(yè)表，拆分成了$2^{10}$個(gè)小頁(yè)表，且每個(gè)小頁(yè)表中有$2^{10}$個(gè)頁(yè)表項(xiàng)。

??需要注意“頁(yè)號(hào)”的分配。例如，在原來(lái)的大頁(yè)表當(dāng)中，頁(yè)號(hào)為1024的頁(yè)表項(xiàng)，它經(jīng)過(guò)分配以后，它應(yīng)該是變成了1號(hào)頁(yè)表當(dāng)中的頁(yè)號(hào)為0的頁(yè)表項(xiàng)。

??在得到拆分好的$2^{10}=1024$個(gè)小頁(yè)表之后，由于每個(gè)小頁(yè)表的大小也都是4KB（剛好是內(nèi)存塊的大小），因此每個(gè)小頁(yè)表都可以各自放到一個(gè)頁(yè)框當(dāng)中。

??所以，為了記錄這些小頁(yè)表最終存放到的內(nèi)存塊的位置。我們需要對(duì)這些小頁(yè)表再建立上一級(jí)的表。這個(gè)上一級(jí)的表就叫做“頁(yè)目錄表”（或頂級(jí)頁(yè)表、外層頁(yè)表）。

??那么相應(yīng)的，我們下一級(jí)的那1024個(gè)小頁(yè)表就可以稱之為“二級(jí)頁(yè)表”。

??在采用這樣的兩級(jí)頁(yè)表之后，邏輯地址結(jié)構(gòu)也需要發(fā)生相應(yīng)的變化。我們可以把以前20位的頁(yè)號(hào)，拆分成兩個(gè)部分——第一個(gè)部分是10位的，用來(lái)表示“一級(jí)頁(yè)號(hào)”；第二個(gè)部分是10位的，用來(lái)表示“二級(jí)頁(yè)號(hào)”。（且10位二進(jìn)制數(shù)剛好足夠表示0 ~ 1023）

（四）如何實(shí)現(xiàn)地址變換

??例：將邏輯地址(0000000000, 0000000001, 111111111111)轉(zhuǎn)換為物理地址（用十進(jìn)制表示）。

分析

??1.按照地址結(jié)構(gòu)將邏輯地址拆分成三部分。

??2.從PCB中讀出頁(yè)目錄表始址，再根據(jù)一級(jí)頁(yè)號(hào)查頁(yè)目錄表，找到下一級(jí)頁(yè)表在內(nèi)存中的存放位置。

??根據(jù)題目信息，可知，要查詢的邏輯地址，其一級(jí)頁(yè)號(hào)是0，即“頁(yè)目錄表”中的0號(hào)表項(xiàng)。（即下圖中的第一項(xiàng)，其對(duì)應(yīng)內(nèi)存塊號(hào)是3）

??根據(jù)一級(jí)頁(yè)表查出，其二級(jí)頁(yè)表存放的物理位置在內(nèi)存塊號(hào)為3的地方。于是就可以從內(nèi)存當(dāng)中對(duì)應(yīng)位置讀出該二級(jí)頁(yè)表。

??根據(jù)題目條件，可知邏輯地址當(dāng)中的“二級(jí)頁(yè)號(hào)”是頁(yè)號(hào)1，即查找二級(jí)頁(yè)表中頁(yè)號(hào)為1的頁(yè)表項(xiàng)，即上圖中間的二級(jí)頁(yè)表的第二項(xiàng)。

??3.根據(jù)二級(jí)頁(yè)號(hào)查表，找到最終想訪問(wèn)的內(nèi)存塊號(hào)。

??通過(guò)二級(jí)頁(yè)表的查找，可以知道，最終我們想要查找的邏輯地址是在4號(hào)內(nèi)存塊中。

??4.結(jié)合頁(yè)內(nèi)偏移量得到物理地址。

??最后，我們根據(jù)所訪問(wèn)的內(nèi)存塊號(hào)，結(jié)合頁(yè)內(nèi)偏移量，得出最終的物理地址。

??我們最終要訪問(wèn)的內(nèi)存塊號(hào)為4，并且每個(gè)內(nèi)存塊的大小為4KB。那么，該內(nèi)存塊的起始地址為4 * 4096 = 16384。同時(shí)，由題目條件可知，頁(yè)內(nèi)偏移量轉(zhuǎn)換為十進(jìn)制之后是1023。

??最終物理地址為：16384 + 1023 = 17407。

（五）需要注意的幾個(gè)細(xì)節(jié)

??1.若采用多級(jí)頁(yè)表機(jī)制，則各級(jí)頁(yè)表的大小不能超過(guò)一個(gè)頁(yè)面。

例題：

??某系統(tǒng)按字節(jié)編址，采用40位邏輯地址，頁(yè)面大小為4KB，頁(yè)表項(xiàng)大小為4B，假設(shè)采用純頁(yè)式存儲(chǔ)，則要采用（）級(jí)頁(yè)表，頁(yè)內(nèi)偏移量為（）位？

分析：

??首先，比較容易確定的是“頁(yè)內(nèi)偏移量的位數(shù)”。頁(yè)面大小是4KB，且是按字節(jié)編址。所以，頁(yè)內(nèi)偏移量應(yīng)該占12位。而剩余的28位就應(yīng)該是用來(lái)表示頁(yè)號(hào)的。

??另外，由于頁(yè)面大小是4KB，每個(gè)頁(yè)表項(xiàng)大小是4B，所以每個(gè)頁(yè)面可以存放$2^{10}$ =1024個(gè)頁(yè)表項(xiàng)。

??由于采用多級(jí)頁(yè)表機(jī)制時(shí)，各級(jí)頁(yè)表的大小不能超過(guò)一個(gè)頁(yè)面。所以，各級(jí)頁(yè)表當(dāng)中，頁(yè)表項(xiàng)的個(gè)數(shù)最多不能超過(guò)$2^{10}$個(gè)?！鄳?yīng)地，各級(jí)的頁(yè)號(hào)所占位數(shù)不能超過(guò)10位?！?#xff0c;28位的頁(yè)號(hào)，我們可以把它分成三個(gè)部分。

??2.兩級(jí)頁(yè)表的訪存次數(shù)分析（假設(shè)沒(méi)有快表機(jī)構(gòu)）。

??第一次訪存：訪問(wèn)內(nèi)存中的頁(yè)目錄表（頂級(jí)頁(yè)表）；

??第二次訪存：訪問(wèn)內(nèi)存中的二級(jí)頁(yè)表；

??第三次訪存：訪問(wèn)目標(biāo)內(nèi)存單元。

??如果是單級(jí)頁(yè)表，不考慮快表的話，在訪問(wèn)一個(gè)邏輯地址的時(shí)候只需兩次訪存。

??可見(jiàn)，兩級(jí)頁(yè)表雖然解決了我們之前提出的單級(jí)頁(yè)表的兩大問(wèn)題，但是這種內(nèi)存空間利用率的上升所同時(shí)付出的代價(jià)就是，邏輯地址需要更多一次的訪存，就會(huì)導(dǎo)致我們?cè)L問(wèn)某個(gè)邏輯地址的時(shí)候就要花費(fèi)更長(zhǎng)的時(shí)間。這也是兩級(jí)頁(yè)表相比于單級(jí)頁(yè)表的一個(gè)比較明顯的缺點(diǎn)。

??如果我們繼續(xù)分析三級(jí)頁(yè)表、四級(jí)頁(yè)表的訪存次數(shù)……

??會(huì)發(fā)現(xiàn)，其實(shí)有一個(gè)規(guī)律：n級(jí)頁(yè)表在訪問(wèn)邏輯地址的時(shí)候，訪存次數(shù)是n+1次。（在不考慮快表機(jī)構(gòu)的情況下）

總結(jié)