一、端到端地址翻譯示例

從圖上看，TLBI占了t位，而TLBT占了n-p-t位。

上節(jié)我們剛把TLB開(kāi)了個(gè)頭，多說(shuō)無(wú)益，還是具體來(lái)玩?zhèn)€實(shí)際例子吧，具體來(lái)做一個(gè)端到端（虛擬地址到物理地址）的地址翻譯示例，來(lái)統(tǒng)籌下之前講的知識(shí)點(diǎn)。先來(lái)做如下約定：

1、老規(guī)矩，存儲(chǔ)器按字節(jié)尋址，訪(fǎng)問(wèn)也按一字節(jié)訪(fǎng)問(wèn)；

2、虛擬地址14位長(zhǎng)（n=14），物理地址12位長(zhǎng)（m=12），位數(shù)少點(diǎn)玩起來(lái)方便；

3、頁(yè)面大小是64字節(jié)（P=64），也就是說(shuō)（p=6）

4、TLB是四路組相聯(lián)，總共16個(gè)條目；

5、L1 d-cache是物理尋址、直接映射的，行大小為4字節(jié)，總共有16個(gè)組。

這里得先貼出各個(gè)單元內(nèi)的數(shù)據(jù)快照，以便分析，首先是TLB。

先看上面的圖，要明確一點(diǎn)，引入TLB就是為了進(jìn)一步分級(jí)VPN的，而分解方式跟VPN本身的頁(yè)表邏輯可能沒(méi)有對(duì)應(yīng)關(guān)系！

由于頁(yè)面大小64字節(jié)，p=6，因此虛擬頁(yè)偏移VPO占用6位，既然是6位，再看虛擬地址是14位長(zhǎng)(事先約定的，所以不是32位)，剩下VPN是8位，也就是說(shuō)TLB需要處理2⁸也就是256個(gè)VPN值。而TLB是四路組相聯(lián)，從上到下0~3這四路，由VPN的低兩位——TLBI來(lái)標(biāo)識(shí)；而TLB的四組中每組有四個(gè)條目，要處理總共256個(gè)VPN，它們被分成四路，也就是說(shuō)每組還要對(duì)口處理64個(gè)VPN（256÷4=64）……注意到剩了6位給TLBT，他就是所謂的標(biāo)記位，正剛好就能區(qū)分2⁶=64個(gè)VPN，因此不管某個(gè)VPN被映射到哪一組，在同一組內(nèi)是不會(huì)出現(xiàn)VPN重復(fù)歧義現(xiàn)象的，由TLBI確定組，再由TLBT確定標(biāo)記位，于是8位VPN就這樣通過(guò)6+2的方式被TLB分解和存儲(chǔ)！

好，那假設(shè)現(xiàn)在CPU要讀取虛擬地址0x03d4處的值會(huì)出現(xiàn)什么情況？我們先把0x03d4分解成VPN+VPO形式：

轉(zhuǎn)換成14位的0x03d4：

(0x03)(0xd4)

000011	11010100

轉(zhuǎn)化成VPN+VPO：

VPN(0x0F)VPO(0x14)

0 0 0 0 1 1 1 1	0 1 0 1 0 0

實(shí)踐發(fā)現(xiàn)，VPN和VPO的值與0x03d4已經(jīng)完全沒(méi)關(guān)系了，這是16進(jìn)制表示法的弱點(diǎn)，雖然方便，但不如二進(jìn)制來(lái)的直觀。好了，接下來(lái)我們看看物理內(nèi)存中頁(yè)表的情況：

我們既然都知道物理地址是由PPN+PPO組成的，而頁(yè)偏移PPO和VPO又是等價(jià)已知的，現(xiàn)在通過(guò)查看頁(yè)表又曉得VPN的0x0F是對(duì)應(yīng)的PPN是0D，那物理地址不已經(jīng)出來(lái)了么等于0x0D14！如果你是CPU你這么做就傻X了，還查什么頁(yè)表啊！頁(yè)表存儲(chǔ)在物理內(nèi)存中，直接訪(fǎng)問(wèn)內(nèi)存會(huì)消耗大量時(shí)間，MMU里明明有TLB緩存都不知道用么？好接下來(lái)看看VPN的0x0F是如何被TLB分解的：

哇咔咔，還記得之前分析的TLBI兩位和TLBT六位的結(jié)論么？忘了自己去看加粗字，現(xiàn)在用上了。兩個(gè)量居然都是0x03。再回看TLB的圖，先找組索引TLBI的0x03剛好是第四排，而標(biāo)記位TLBT的0x03剛好是該組第二個(gè)條目，并且其有效位是1，因此PPN順利取出了0D！

如果TLB里沒(méi)有怎么辦？那就是TLB不命中，這時(shí)候才直接去物理內(nèi)存中找PTE，就跟第一個(gè)想法一樣的——奇慢！

好了，物理地址0x0D14到是獲得了，你該不會(huì)想又跑到物理主存中去取值吧？別忘了這還有L1高速緩存呢：

行大小為4字節(jié)，總共16個(gè)組，怎么看？當(dāng)然還是得先從物理地址0x0D14開(kāi)始看，別忘了，先按物理地址的格式來(lái)分解：

分解后發(fā)現(xiàn)，組索引CI的值是0x05，也就是L1緩存里索引5,這一行，其中標(biāo)記位為0D，與物理地址中CT的值0x0D匹配；最后看偏移量OO是0x0，沒(méi)有偏移，于是終于得到我們查詢(xún)了半天的數(shù)值：0x36，于是MMU將其返回給CPU——注意，此例中完全沒(méi)有物理內(nèi)存的訪(fǎng)問(wèn)過(guò)程！

2020-11-26所補(bǔ)充
對(duì)上面的補(bǔ)充：
【0】寫(xiě)在前面-為什么需要虛擬存儲(chǔ)器?
0.1）定義：虛擬存儲(chǔ)器其實(shí)就是借用了磁盤(pán)地址空間，還記得當(dāng)初我們安裝CentOS，劃分的swap 文件系統(tǒng)嗎？
0.2）VM簡(jiǎn)化了鏈接和加載、代碼和數(shù)據(jù)共享，以及應(yīng)用程序的存儲(chǔ)器分配：（摘自CSAPP）
（1） 簡(jiǎn)化鏈接： 每個(gè)進(jìn)程都擁有獨(dú)立的虛擬地址空間， 且空間范圍一致；（它是可重定向目標(biāo)文件使用相對(duì)物理地址的前提）
（2） 簡(jiǎn)化加載： 加載器從不實(shí)際拷貝任何數(shù)據(jù)從磁盤(pán)到存儲(chǔ)器。每個(gè)頁(yè)初次被調(diào)用哦時(shí)， 要么是CPU取指時(shí)引用， 要么是一條正在執(zhí)行的指令引用一個(gè)存儲(chǔ)器位置時(shí)引用，VM系統(tǒng)會(huì)按需自動(dòng)調(diào)入數(shù)據(jù)頁(yè)；
（3） 簡(jiǎn)化共享： 多個(gè)虛擬頁(yè)面可以映射到同一個(gè)共享物理頁(yè)面上；
（4） 簡(jiǎn)化存儲(chǔ)器分配： 當(dāng)需要額外的堆空間， os分配連續(xù)的虛擬存儲(chǔ)器頁(yè)面，這些VP可以映射都任意的物理頁(yè)面，這些物理頁(yè)面可以任意分散在存儲(chǔ)器中；
0.3）我還想多問(wèn)一句，為什么有了高速緩存，還需要TLB-translation lookaside buffer,翻譯后備緩沖器呢？
**Reason： **
引入局部性原則： （摘自CSAPP）
局部性原則保證了在任意時(shí)刻， 程序?qū)⑼谝粋€(gè)較小的活動(dòng)頁(yè)面集合上工作，這個(gè)集合
叫做工作集（working set）或者常駐集（resident set）。

換句話(huà)說(shuō)， 局部性原則揭示了一個(gè)現(xiàn)象：在一段時(shí)間內(nèi)，我們會(huì)反復(fù)調(diào)入或調(diào)入同一個(gè)或
幾個(gè)虛擬頁(yè)頁(yè)面；而且，每次CPU產(chǎn)生一個(gè)VA時(shí)， MMU就必須查閱PTE，
以便將VA翻譯為PA， 注意是每次，所以開(kāi)銷(xiāo)很大；

解決方法： 為了消除這樣的開(kāi)銷(xiāo)，在MMU中包括了一個(gè)關(guān)于PTE的小緩存，稱(chēng)為翻譯后備緩沖器；
關(guān)鍵點(diǎn)： 所有的地址翻譯步驟都是在芯片上的MMU中執(zhí)行的， 因此執(zhí)行速度非常快；
你要知道計(jì)算機(jī)中共有7級(jí)存儲(chǔ)結(jié)構(gòu)，訪(fǎng)問(wèn)CPU中的存儲(chǔ)空間（MMU）的速度比訪(fǎng)問(wèn)緩存的速度可是快了幾個(gè)數(shù)量級(jí)的。

【1】說(shuō)了這么多，看個(gè)荔枝（以下TLB + 頁(yè)表 + 高速緩存 是我們手動(dòng)模擬的）（圖片摘自CSAPP）：

【2】題目：說(shuō)有虛擬地址 0x03d7， 虛擬存儲(chǔ)器系統(tǒng)如何將其翻譯成物理地址和訪(fǎng)問(wèn)緩存的。
【3】解答：將以上虛擬地址用二進(jìn)制表示，如下：

我們看到：
VPN=bit13~bit6 =0x0f；
VPO=bit5~bit0 = 0x17；
TLBT（行索引or標(biāo)記）=bit13~bit8=0x03;

（這里，為什么我管標(biāo)記叫做行索引，說(shuō)到本質(zhì)，叫其行索引，并沒(méi)有什么不妥，
因?yàn)楸緦?shí)例中，cache采用的是直接映射，即每個(gè)組就只有一行，所以行索引在此處無(wú)意；
但若cache是采用組相聯(lián)映射或全相聯(lián)映射的話(huà)，每組就有多行，行索引就起到作用了）；

TLBI（組索引）=bit7~bit6=0x3;

相關(guān)聲明declaration寫(xiě)在前面：
d1) 我們這里是考慮命中的情況，當(dāng)然，如果不命中， MMU需要從主存中取出相應(yīng)的PTE；
d2） PS： 命中與否，是看TLB中是否有請(qǐng)求的PTE；
d3）虛擬地址14位，而物理地址12位；

翻譯過(guò)程： （干貨）
（1） MMU（MMU存在于CPU中，是硬件）從虛擬地址中抽取VPN=0x0f；
（2） 再?gòu)腣PN中抽取出TLBT（行索引）=0x03, TLBI（組索引）=0x3，用于索引翻譯后備存儲(chǔ)器TLB；
（3） 帶著TLBT和TLBI 查看TLB，發(fā)現(xiàn)第3組， 有標(biāo)記位03（當(dāng)然，這是手動(dòng)設(shè)置的，便于模擬），且有效位=1，故命中；
（4） 命中后，將PPN=0D返回給MMU；
（5） MMU將PPN=0x0D=bit11~bit6 和 虛擬地址的VPO=0x17=bit5~bit0 連接起來(lái)，形成物理地址PA 》》 0x357

6） 如上圖所示：我們得到了CT-Cache Tag=0x0D， CI-Cache Index=0x5， CO-Cache Offset=0x3；即得到了緩存標(biāo)記CT=0x0d，緩存組索引CI=0x5，緩存偏移CO=0x3；
（7） 依據(jù)CT、CI、CO，查詢(xún)高速緩存（c圖）， 第5組的標(biāo)記位-0x0D， 故命中；
（8） 在看緩存偏移是0x3，所以取出塊3字節(jié)0x1D；
對(duì)于CT + CI + CO， 我再說(shuō)的明白一點(diǎn)： CT就是行索引， CI就是組索引， CO就是塊索引；

二、多級(jí)頁(yè)表
多級(jí)頁(yè)表作用：通過(guò)只為進(jìn)程實(shí)際使用的那些虛擬地址內(nèi)存區(qū)請(qǐng)求頁(yè)表來(lái)減少內(nèi)存使用量（出自《深入理解Linux內(nèi)核》第三版51頁(yè)）

在解釋多級(jí)頁(yè)表之前，先來(lái)梳理下概念，免得后面的內(nèi)容看暈：

1、頁(yè)表：緩存了很多頁(yè)面信息（有效位+物理頁(yè)號(hào)）的表；

2、各頁(yè)面信息分別由頁(yè)表中每個(gè)PTE記錄，

3、頁(yè)面：就是對(duì)應(yīng)虛擬存儲(chǔ)器（磁盤(pán)空間）中各空間

4、頁(yè)號(hào)（PN）：MMU根據(jù)虛擬頁(yè)號(hào)VPN索引頁(yè)表對(duì)應(yīng)的具體PTE，從中提取出其中的物理頁(yè)號(hào)PPN，一般都是數(shù)組直接對(duì)應(yīng)關(guān)系

好了，既然概念解釋清楚了，那么頁(yè)表大小頁(yè)面大小應(yīng)該不會(huì)再搞混了吧：頁(yè)面大小對(duì)應(yīng)虛擬存儲(chǔ)器每個(gè)分頁(yè)大小，而PET的大小就是存儲(chǔ)一條對(duì)應(yīng)地址翻譯信息所占用的空間大小，那么頁(yè)表大小就是該頁(yè)表內(nèi)所有PTE大小的總和。

我們?cè)賮?lái)回憶下，一個(gè)32位系統(tǒng)，有2³²個(gè)地址，每個(gè)地址標(biāo)識(shí)一個(gè)字節(jié)的數(shù)據(jù)，那么地址能訪(fǎng)問(wèn)到的數(shù)據(jù)就涵蓋了2³²字節(jié)，也就是(2²) * (2¹⁰) * (2¹⁰) * (2¹⁰)B數(shù)據(jù)，也就是4GB數(shù)據(jù)。

如果我們每個(gè)末級(jí)頁(yè)面的大小是4kB，那么4GB的數(shù)據(jù)就被分割成1M個(gè)頁(yè)面（注意單位是”個(gè)“不是字節(jié)，說(shuō)的頁(yè)面?zhèn)€數(shù)呢！這里按2¹⁰進(jìn)階,不是10³），好，如果我們又知道每個(gè)PTE的空間開(kāi)銷(xiāo)是占4字節(jié)大小，也就是說(shuō)頁(yè)表中處理每個(gè)頁(yè)面都需要占用4B，處理1M個(gè)頁(yè)面的頁(yè)表自然就要在物理內(nèi)存中占用4MB的空間……教材上確實(shí)沒(méi)分析得這么明顯，我如此講解應(yīng)該立馬知道，4MB駐留空間是腫么得來(lái)了吧！天~4MB大小的頁(yè)表，檢索起來(lái)效率一定很低，如何設(shè)計(jì)操作系統(tǒng)才能把頁(yè)表縮小以改進(jìn)性能呢？（注意不是在討論頁(yè)表里每一項(xiàng)頁(yè)面所映射的4kB空間）

好了好了，先否定掉剛才4MB末級(jí)頁(yè)表規(guī)模的提案，因?yàn)楝F(xiàn)在有另一個(gè)假設(shè)也是4MB，那就是，如果我們把4GB總的虛擬存儲(chǔ)器空間，先等分成一份份4MB大小（而不是之前的4kB大小），那就會(huì)分出1k份出來(lái)，也就是1024份空間。如果我們有一個(gè)專(zhuān)門(mén)的頁(yè)表（I），其中剛好有1024個(gè)PTE，就剛好能標(biāo)識(shí)這1024份空間。但是呢，總覺(jué)得這1024個(gè)4MB的末級(jí)頁(yè)面空間（注意不是頁(yè)表空間）每個(gè)都太大了，也就是VPO太大了，難以精確定位其偏移量，于是我們聯(lián)想到之前在設(shè)計(jì)單級(jí)頁(yè)表結(jié)構(gòu)中，末級(jí)頁(yè)面大小本來(lái)想分成4KB（就是一個(gè)頁(yè)面能緩存的空間大小），如果我們把每份4MB空間再細(xì)分成1024個(gè)末級(jí)頁(yè)面映射，完全可以在每份4MB空間中再設(shè)立另一個(gè)專(zhuān)門(mén)的頁(yè)表（II），其中也剛好有1024個(gè)PTE，就剛好可以把末級(jí)頁(yè)面映射成4KB大小。而且既然（I）中每個(gè)PTE對(duì)應(yīng)一份4MB空間，而每份空間又對(duì)應(yīng)一個(gè)（II），那么（I）中每一個(gè)PTE就可以和某一個(gè)（II）建立聯(lián)系，于是多級(jí)頁(yè)表的概念產(chǎn)生了！……也許當(dāng)年最早的os設(shè)計(jì)者就是沿著這種思路思考出來(lái)二級(jí)頁(yè)表的概念：

先不管最左邊那些亂七八糟的虛存分配，先看最右邊，從VP0~VP2047這2k個(gè)頁(yè)（注意是頁(yè)不是字節(jié)！），我們發(fā)現(xiàn)，每一個(gè)頁(yè)VPx都被二級(jí)頁(yè)表中的一個(gè)PTE所對(duì)應(yīng)，而一個(gè)完整的二級(jí)表有1024個(gè)PTE分別對(duì)應(yīng)1024個(gè)VP，圖中所謂的2k個(gè)頁(yè)需要兩個(gè)二級(jí)頁(yè)表才能對(duì)應(yīng)完成。而我們又知道一個(gè)末級(jí)頁(yè)面是4KB大小，那1024個(gè)末級(jí)頁(yè)面總共就是4MB大小，也就說(shuō)每個(gè)二級(jí)頁(yè)表都對(duì)應(yīng)4MB大小的數(shù)據(jù)！好了，再看一級(jí)頁(yè)表，它每個(gè)PTE對(duì)應(yīng)的就是這樣一個(gè)二級(jí)頁(yè)表，也就是說(shuō)，一級(jí)頁(yè)表每個(gè)PTE都對(duì)應(yīng)4MB大小的數(shù)據(jù)，那么總共1024個(gè)PTE的一級(jí)頁(yè)表，剛好可以完整對(duì)應(yīng)4GB大小的空間！
我們發(fā)現(xiàn)，所謂的兩級(jí)頁(yè)表層次結(jié)構(gòu)，是不是很像三維數(shù)組int PT[1024] [1024] [1024]？由于末尾是int型占4字節(jié)，末級(jí)頁(yè)面大小就是1024個(gè)4字節(jié)也就是4kB。
好了，為啥要整二級(jí)頁(yè)表呢？最起碼有三點(diǎn)好處。其一，如果一級(jí)頁(yè)表的PTE為空，那就不存在對(duì)應(yīng)下標(biāo)的二級(jí)頁(yè)表，能節(jié)省大量潛在的空間；其二，只有一級(jí)頁(yè)表需要一直保存在物理內(nèi)存中，二級(jí)頁(yè)表則不然，只有經(jīng)常使用的需要保存在物理內(nèi)存——還是為了節(jié)省空間^^，其三，也就是上面提過(guò)的問(wèn)題，這樣每個(gè)頁(yè)表都只有1024個(gè)PTE，由于每個(gè)PTE本身只占用4B大小，因此每個(gè)頁(yè)表就只占用4kB空間了！——空間空間還是為了空間！
插一句，上面說(shuō)的如此設(shè)計(jì)每個(gè)頁(yè)表只占4kB，和我們說(shuō)的每個(gè)末級(jí)頁(yè)面只占4kB，概念上完全是兩回事，但如此設(shè)計(jì)卻顯得優(yōu)雅。頁(yè)表和頁(yè)面的概念在這里灰?；页Ｈ菀赘慊?#xff01;切記不要搞混！切忌搞混！萬(wàn)萬(wàn)不能搞混！重要的事情說(shuō)三遍！！
節(jié)省空間固然好，但如何在頁(yè)表中查找PTE呢？比如我的頁(yè)面大小是4KB，回憶下上節(jié)虛擬地址的結(jié)構(gòu)是VPN+VPO，其中VPO是頁(yè)面偏移，要滿(mǎn)足4KB偏移大小，VPO就需要12位（2¹²=1k*4）,那么VPN就剩下32-12=20位可用，10位剛好可表示1024個(gè)值，于是我用10位去標(biāo)識(shí)一級(jí)頁(yè)表中1024個(gè)PTE，再用10位去標(biāo)識(shí)每個(gè)一級(jí)頁(yè)表PTE中存儲(chǔ)的二級(jí)頁(yè)表中的1024個(gè)PTE，于是這樣劃分的虛擬地址就能將上圖的頁(yè)表層次結(jié)構(gòu)全部標(biāo)識(shí)清楚：

VPN1(10)VPN2(10)VPO(12)

有沒(méi)有瞬間覺(jué)得虛擬地址被玩壞的感覺(jué)？k級(jí)虛擬地址對(duì)應(yīng)k級(jí)頁(yè)表，多么高大上又樸實(shí)無(wú)華簡(jiǎn)易的思想！

總結(jié)

以上是生活随笔為你收集整理的2020-11-25（《深入理解计算机系统》多级页表详解）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。