承接上文我們講完了頁(yè)式管理和段式管理，接下來(lái)讓我們深入講解一下快表和二級(jí)頁(yè)表

快表

快表和計(jì)算機(jī)組成原理講的Cache原理如出一轍。為了減少訪存的次數(shù)，OS在訪問(wèn)頁(yè)面的時(shí)候創(chuàng)建了快表（Translation Lookaside Buffer ，簡(jiǎn)稱(chēng)TLB），包含最近使用過(guò)的頁(yè)表表項(xiàng)，避免了反復(fù)查詢(xún)處于內(nèi)存中的頁(yè)表。

如圖所示，OS會(huì)先根據(jù)TLB是否命中決定是否訪問(wèn)在內(nèi)存中的頁(yè)表，如果命中就直接拿著快表表項(xiàng)組合已有的偏移量構(gòu)成物理地址。反之，OS會(huì)繼續(xù)訪問(wèn)頁(yè)表找到對(duì)應(yīng)的頁(yè)表項(xiàng)，得到物理地址，然后將該頁(yè)表項(xiàng)加入到快表中以備下次查詢(xún)。如果快表和頁(yè)表都沒(méi)有找到，就會(huì)引發(fā)缺頁(yè)中斷，有關(guān)內(nèi)容我們下一章節(jié)會(huì)詳細(xì)敘述。

二級(jí)頁(yè)表

首先，我們先思考一個(gè)問(wèn)題，假設(shè)的是32位邏輯地址，頁(yè)面大小為4kb，并且假設(shè)頁(yè)表項(xiàng)大小為4B，那么一個(gè)進(jìn)程最多有多少頁(yè)，需要分配的頁(yè)框占據(jù)多少空間？

---

頁(yè)面大小是4KB，也就是需要12位表示業(yè)內(nèi)偏移量，總共有32位邏輯地址，剩余20位組成頁(yè)號(hào)，也就是一個(gè)進(jìn)程最多有2^{20個(gè)頁(yè)，每個(gè)頁(yè)對(duì)應(yīng)一個(gè)頁(yè)號(hào)，而一個(gè)頁(yè)號(hào)對(duì)應(yīng)一個(gè)頁(yè)表項(xiàng)，則至少需要2}20 *4 = 2^22個(gè)字節(jié)的空間存放，即4GB的空間。
實(shí)際上，我們普通電腦的內(nèi)存不過(guò)8GB、16GB，如果光是一個(gè)進(jìn)程就干掉4GB，那顯然是捉襟見(jiàn)肘的。同時(shí)，由于一個(gè)進(jìn)程的頁(yè)面是連續(xù)存放的，那么一個(gè)進(jìn)程就要連續(xù)分配4GB/4Kb = 1024個(gè)頁(yè)面，顯然一次性給一個(gè)進(jìn)程分配這么多頁(yè)面也是不合理的。

---

實(shí)際上，進(jìn)程不會(huì)一次訪問(wèn)所有的頁(yè)面，而是只會(huì)訪問(wèn)特定的頁(yè)面，所以我們不需要一次性分配所有的頁(yè)面。為了解決進(jìn)程頁(yè)面必須連續(xù)存放的問(wèn)題，我們采用解決進(jìn)程在內(nèi)存中連續(xù)存放的思路，使用二級(jí)頁(yè)表，把頁(yè)面存放離散化。

如圖所示，我們已知頁(yè)表是一種索引結(jié)構(gòu)，進(jìn)程有2^20個(gè)頁(yè)也就是有0~1048575的頁(yè)號(hào)，我們?cè)诖嘶A(chǔ)上分組，每1024個(gè)為一組，總共就是1024組，然后在每一組中的頁(yè)號(hào)對(duì)1024取余，統(tǒng)一成0~1023。然后再在這1024組上建一層索引，也就構(gòu)成了我們的頁(yè)目錄。

奇妙的是，按照1024劃分，每一個(gè)二級(jí)頁(yè)表剛好對(duì)應(yīng)一個(gè)頁(yè)框，而頁(yè)目錄表也是一個(gè)頁(yè)框（1024*4B = 4KB）。也就是說(shuō)，我們將原先連續(xù)的頁(yè)面按照頁(yè)框大小分組，然后在分組上建索引得到了一個(gè)新的頁(yè)表——頁(yè)目錄表。

現(xiàn)在，我們查詢(xún)就要分為兩次：先查頁(yè)目錄表，對(duì)應(yīng)的內(nèi)存塊號(hào)是存二級(jí)頁(yè)表的內(nèi)存位置，然后再查二級(jí)頁(yè)表，二級(jí)頁(yè)表中的內(nèi)存塊號(hào)就是實(shí)際訪存的內(nèi)存塊號(hào)了。

與之對(duì)應(yīng)，二級(jí)頁(yè)表的邏輯地址結(jié)構(gòu)部分，原先的前20位頁(yè)號(hào)就要拆成一級(jí)頁(yè)號(hào)和二級(jí)頁(yè)號(hào)。
其中，查頁(yè)目錄表就是查一級(jí)頁(yè)號(hào)對(duì)應(yīng)的內(nèi)存塊號(hào)，然后根據(jù)該內(nèi)存塊號(hào)找到內(nèi)存中對(duì)應(yīng)的二級(jí)頁(yè)表，然后根據(jù)二級(jí)頁(yè)號(hào)查二級(jí)頁(yè)表找到對(duì)應(yīng)的內(nèi)存塊號(hào)，就是實(shí)際訪存的內(nèi)存塊。
而一級(jí)頁(yè)號(hào)總共是10位，因?yàn)榭偣灿?024個(gè)二級(jí)頁(yè)表，二級(jí)頁(yè)號(hào)也有10位，因?yàn)槊總€(gè)二級(jí)頁(yè)表有1024個(gè)頁(yè)表項(xiàng)。

建立多級(jí)頁(yè)表本質(zhì)上就是建立多重索引。二級(jí)頁(yè)表就是借助二重索引的迭代查詢(xún)來(lái)實(shí)現(xiàn)對(duì)于一重索引的離散化。

舉一個(gè)更具體的例子

假設(shè)我們的32位的邏輯地址如圖所示，根據(jù)10+10+12的原則，一級(jí)頁(yè)號(hào)就是0，二級(jí)頁(yè)號(hào)就是1，頁(yè)內(nèi)偏移就是1023.
我們先在頁(yè)目錄表中查一級(jí)頁(yè)號(hào)對(duì)應(yīng)的內(nèi)存塊號(hào)3，再到與之對(duì)應(yīng)的二級(jí)頁(yè)表中查詢(xún)二級(jí)頁(yè)號(hào)1，得知內(nèi)存塊號(hào)4是最終需要訪問(wèn)的內(nèi)存塊，結(jié)合頁(yè)面大小4KB，最終的訪問(wèn)地址是4*4K+1023 = 17407。

幾個(gè)細(xì)節(jié)

一般來(lái)說(shuō)，各級(jí)頁(yè)表大小不能超過(guò)一個(gè)頁(yè)面，不然就又會(huì)出現(xiàn)頁(yè)面連續(xù)存放的問(wèn)題。
所以上述例子中，每級(jí)頁(yè)表最多2^10個(gè)，占用10位，40位邏輯地址就至少需要三級(jí)頁(yè)表，即（40-12）/ 3 向上取整。

假設(shè)不考慮TLB，訪存次數(shù)根據(jù)頁(yè)表級(jí)數(shù)N而定，因?yàn)轫?yè)表也是存儲(chǔ)在內(nèi)存中的，所以查詢(xún)每一級(jí)頁(yè)表都需要訪存，最終訪存次數(shù)是N+1。

至于一開(kāi)始提到的進(jìn)程自身頁(yè)表存儲(chǔ)量最高可達(dá)4GB，現(xiàn)有的內(nèi)存容量無(wú)法滿足需求的解決方案，我們將會(huì)在下一章的虛擬存儲(chǔ)中提及。