一 虛擬存儲(chǔ)器概念

虛擬存儲(chǔ)器(Virtual Memory)的基本思想是對(duì)于程序來(lái)說(shuō)，它的程序(code)、數(shù)據(jù)(data)、堆棧(stack)的總大小可以超過(guò)實(shí)際物理內(nèi)存(Physical Memory)的大小，操作系統(tǒng)把當(dāng)前使用的部分內(nèi)容放到物理內(nèi)存中，而把其它未使用的內(nèi)容放到更下一級(jí)存儲(chǔ)器，如硬盤(Disk)或閃存(Flash)上。這樣可以應(yīng)付隨著應(yīng)用程序規(guī)模的擴(kuò)大，導(dǎo)致物理內(nèi)存已經(jīng)無(wú)法容納下這樣的程序。

舉例來(lái)說(shuō)，一個(gè)大小為32MB的程序運(yùn)行在物理內(nèi)存只有16MB的機(jī)器上，操作系統(tǒng)通過(guò)選擇，決定各個(gè)時(shí)刻將程序中一部分放在物理內(nèi)存中，而將其它的內(nèi)容放到硬盤中，并在需要的時(shí)候在物理內(nèi)存和硬盤之間交換程序片段，這樣就可以把大小為32MB的程序放到物理內(nèi)存為16MB的機(jī)器上運(yùn)行。

運(yùn)用程序是運(yùn)行在虛擬存儲(chǔ)器空間的，它的大小由處理器的位數(shù)決定，例如對(duì)于一個(gè)32位處理器來(lái)說(shuō)，其地址范圍就是0~0xFFFF_FFFF，也就是4GB，這個(gè)范圍就是程序能夠產(chǎn)生的地址范圍，其中的某一個(gè)地址就稱為虛擬地址。和虛擬存儲(chǔ)器對(duì)應(yīng)的就是物理存儲(chǔ)器，它是在現(xiàn)實(shí)世界中能夠直接使用的存儲(chǔ)器，其中的某一個(gè)地址就是物理地址。物理存儲(chǔ)器的大小不能夠超過(guò)處理器最大可以尋址的空間，例如32為x86 PC中，不可能使用比4GB更大的物理內(nèi)存了。

在沒(méi)有使用虛擬地址的系統(tǒng)中，處理器輸出的地址會(huì)直接送到物理存儲(chǔ)器中，這個(gè)過(guò)程如圖1所示。

圖1 沒(méi)有使用虛擬存儲(chǔ)器的系統(tǒng)

而如果使用了虛擬地址，則處理器輸出的地址就是虛擬地址了，這個(gè)地址不會(huì)被直接送到物理存儲(chǔ)器中，而是需要先進(jìn)行地址轉(zhuǎn)換，因?yàn)樘摂M地址是沒(méi)有辦法直接尋址物理存儲(chǔ)器的，負(fù)責(zé)地址轉(zhuǎn)換的部件一般稱為內(nèi)存管理單元(Memory Manage Unit，MMU)，如圖2所示。

圖2 使用虛擬存儲(chǔ)器的系統(tǒng)

使用虛擬存儲(chǔ)器，每個(gè)應(yīng)用程序總認(rèn)為它占有處理器的所有地址空間，因此程序可以任意使用處理器的地址資源，不需要考慮地址的限制，由操作系統(tǒng)負(fù)責(zé)調(diào)度，將物理存儲(chǔ)器動(dòng)態(tài)地分配給各個(gè)應(yīng)用程序，將每個(gè)程序的虛擬地址轉(zhuǎn)換為相應(yīng)的物理地址，使程序能夠正常運(yùn)行。通過(guò)這樣的方式可以保護(hù)兩個(gè)程序即使使用了同一個(gè)虛擬地址，它們也會(huì)對(duì)應(yīng)到不同的物理地址，因此可以保護(hù)每個(gè)程序的內(nèi)容不會(huì)被其它程序隨意改寫。

還可以實(shí)現(xiàn)了程序間的共享，例如操作系統(tǒng)提供了打印(printf)函數(shù)，第一個(gè)程序在地址A使用了printf函數(shù)，第二個(gè)程序在地址B使用了printf函數(shù)，操作系統(tǒng)在地址轉(zhuǎn)換的時(shí)候，會(huì)將地址A和地址B轉(zhuǎn)換為同樣的物理地址，這個(gè)物理地址就是printf函數(shù)在物理存儲(chǔ)器中的實(shí)際地址，這樣就實(shí)現(xiàn)了程序共享。

因此使用虛擬存儲(chǔ)器不僅可以降低物理存儲(chǔ)器的容量需求，也可以帶來(lái)另外的好處，如保護(hù)(Protect)和共享(Share)。

可以說(shuō)，如果一個(gè)處理器要支持現(xiàn)代的操作系統(tǒng)，就必須支持虛擬存儲(chǔ)器，它是操作系統(tǒng)一個(gè)非常重要的內(nèi)容，本文重點(diǎn)從硬件層面來(lái)講述虛擬存儲(chǔ)器，涉及到頁(yè)表(Page Table)、程序保序和TLB等內(nèi)容。

二 地址轉(zhuǎn)換

目前最通用的虛擬存儲(chǔ)器實(shí)現(xiàn)方式是基于分頁(yè)(page)的虛擬存儲(chǔ)器。虛擬地址空間以頁(yè)(page)為單位劃分，典型的頁(yè)大小為4KB，相應(yīng)的物理地址空間也進(jìn)行同樣大小的劃分，由于歷史原因，在物理地址空間中不叫做頁(yè)，而稱為frame，它和頁(yè)的大小必須相等。

當(dāng)程序開(kāi)始運(yùn)行時(shí)，會(huì)將當(dāng)前需要的部分內(nèi)容從硬盤中搬移到物理內(nèi)存中，每次搬移的單位就是一個(gè)頁(yè)的大小。由于只有在需要的時(shí)候才將一個(gè)頁(yè)的內(nèi)容放到物理內(nèi)存中，這種方式就稱為demand page，它是處理器可以運(yùn)行比物理內(nèi)存更大的程序。

對(duì)于一個(gè)虛擬地址(Virtual Address)來(lái)說(shuō)，VA[11:0]用來(lái)表示頁(yè)內(nèi)的位置，稱為page offset，VA剩余的部分用來(lái)表示哪個(gè)頁(yè)，也稱為VPN(Virtual Page Number)。

相應(yīng)的，對(duì)于一個(gè)物理地址PA(Physical Address)來(lái)說(shuō)，PA[11:0]用來(lái)表示frame內(nèi)的位置，稱為frame offset，而PA剩余的部分用來(lái)表示哪個(gè)frame，也稱為PFN(Physical Frame Number)。由于頁(yè)和frame的大小是一樣的，所以從VA到PA的轉(zhuǎn)化實(shí)際上也就是從VPN到PFN的轉(zhuǎn)化，offset的部分是不需要變化的。

表3所示的例子，假設(shè)處理器是16位的，則它的虛擬地址范圍是0~0XFFFF，共64KB，頁(yè)的大小是4KB，因此64KB的虛擬地址包括了16個(gè)頁(yè)，即16個(gè)VPN；而這個(gè)系統(tǒng)中物理內(nèi)存只有32KB，它包括了8個(gè)PFN?，F(xiàn)有一個(gè)程序，它的大小大于32KB，因此該程序在運(yùn)行時(shí)不能一次性調(diào)入內(nèi)存中運(yùn)行，這臺(tái)機(jī)器必須有一個(gè)可以存放這個(gè)程序的下一級(jí)存儲(chǔ)器(例如硬盤或內(nèi)存)，以保證程序片段在需要的時(shí)候可以被調(diào)用。

在圖3中，一部分虛擬地址已經(jīng)被映射到了物理空間，例如VPN0(地址范圍0-4K)被映射為PFN2(地址范圍8-12K，圖上畫錯(cuò)了)；VPN1(地址范圍4-8K)被映射為PFN0(地址范圍0-4K)等。

圖3 地址轉(zhuǎn)換的一個(gè)例子

對(duì)于從虛擬地址到物理地址的轉(zhuǎn)換來(lái)說(shuō)，指示對(duì)VPN進(jìn)行操作，頁(yè)內(nèi)的偏移是不需要進(jìn)行轉(zhuǎn)化的，也就是說(shuō)，頁(yè)是進(jìn)行地址轉(zhuǎn)換的最小單位。為了便于理解，以load指令為例行描述：

Load R2, 5[R1]; //假設(shè)R1的值為0

這條load指令在執(zhí)行的時(shí)候，得到的取數(shù)據(jù)的虛擬地址是R1+5=5，也就是地址5會(huì)被送到MMU中，從圖3中可以看到，地址5落在了page0(它的范圍是0-4095)的范圍內(nèi)，而page0被映射到物理地址空間中的frame2(它的地址范圍是8192-12287)，因此MMU將虛擬地址5轉(zhuǎn)換為物理地址8192+5=8197，并把這個(gè)地址送到物理內(nèi)存中取數(shù)據(jù)，物理內(nèi)存并不知道MMU做了什么映射，它只是看到了一個(gè)對(duì)地址8197進(jìn)行讀操作的任務(wù)。

對(duì)于圖3中，如果虛擬地址是32780，則落在了page8范圍內(nèi)，而page8還并沒(méi)有一個(gè)有效的映射，即此時(shí)page8的內(nèi)容沒(méi)有存在于物理內(nèi)存中，而是存在于硬盤中。

MMU發(fā)現(xiàn)這個(gè)頁(yè)沒(méi)有被映射之后，就產(chǎn)生一個(gè)Page Fault的異常送給處理器，這時(shí)候處理器就需要轉(zhuǎn)到Page Fault對(duì)應(yīng)的異常處理程序中處理整個(gè)事情(這個(gè)異常處理程序其實(shí)就是操作系統(tǒng)的代碼)，它必須偶從物理內(nèi)存的八個(gè)frame中找到一個(gè)當(dāng)前很少被使用的，假設(shè)選中了frame1，它和page2有著映射關(guān)系，所以首先將frame1和page2解除映射關(guān)系，此時(shí)虛擬地址空間中page2的地址范圍就被標(biāo)記為沒(méi)有映射的狀態(tài)，然后把需要的內(nèi)容(本例是page8)從硬盤搬移到物理內(nèi)存中frame1的空間，并將page8標(biāo)記為映射到frame1；

如果這個(gè)被替換的fram1是臟(dirty)狀態(tài)的，還需要先將它的內(nèi)容搬移到硬盤中，這里臟的概念和Cache中是一樣的，表示這個(gè)frame以前被修改過(guò)，被修改的數(shù)據(jù)還沒(méi)有來(lái)得及更新到硬盤中，處理完上述的內(nèi)容，就可以從Page Fault的異常處理程序中返回，此時(shí)會(huì)返回到這條產(chǎn)生Page Fault的load指令，并重新執(zhí)行，這時(shí)候就不會(huì)再有產(chǎn)生異常，可以取到需要的數(shù)據(jù)了。

2.1 單級(jí)頁(yè)表

在使用虛擬存儲(chǔ)器的系統(tǒng)中，都是使用一張表格來(lái)存儲(chǔ)從虛擬地址到物理地址(實(shí)際上是VPN到PFN)的對(duì)應(yīng)關(guān)系，這個(gè)表格稱為頁(yè)表(Page Table，PT)。

這個(gè)表格一般是放在物理內(nèi)存中，使用虛擬地址來(lái)尋址，表格中被尋址到的內(nèi)容就是這個(gè)虛擬地址對(duì)應(yīng)的物理地址。每個(gè)程序都有自己的頁(yè)表，用來(lái)將這個(gè)程序中的虛擬地址映射到物理內(nèi)存中的某個(gè)地址，為了指示一個(gè)程序的頁(yè)表在物理內(nèi)存中的位置，在處理器中一般都會(huì)包括一個(gè)寄存器，用來(lái)存放當(dāng)前運(yùn)行程序的頁(yè)表在物理內(nèi)存中的起始地址，這個(gè)寄存器稱為頁(yè)表寄存器(Page Table Register，PTR)，每次操作系統(tǒng)將一個(gè)程序調(diào)入物理內(nèi)存中執(zhí)行的時(shí)候，就會(huì)將寄存器PTR設(shè)置好，當(dāng)然，上面的這種機(jī)制可以工作的前提是頁(yè)表位于物理內(nèi)存中一片連續(xù)的地址空間內(nèi)。

圖4表示了如何使用PTR從物理內(nèi)存中定位到一個(gè)頁(yè)表，并使用虛擬地址來(lái)尋址頁(yè)表，從而找到對(duì)應(yīng)的物理地址的過(guò)程。其實(shí)，使用PTR和虛擬地址共同來(lái)尋址頁(yè)表，這就相當(dāng)于使用它們兩個(gè)共同組成一個(gè)地址，使用這個(gè)地址來(lái)尋址物理內(nèi)存。

圖4中仍然假設(shè)每個(gè)頁(yè)的大小是4KB，使用PTR和虛擬地址共同來(lái)尋址頁(yè)表，找到對(duì)應(yīng)的表項(xiàng)(entry)，當(dāng)這個(gè)表項(xiàng)對(duì)應(yīng)的有效位(valid)為1時(shí)，就表示這個(gè)虛擬地址所在的4KB空間已經(jīng)被操作系統(tǒng)映射到了物理內(nèi)存中，可以直接從物理內(nèi)存中找到這個(gè)虛擬地址對(duì)應(yīng)的數(shù)據(jù)，其實(shí)，這時(shí)候訪問(wèn)當(dāng)前頁(yè)內(nèi)任意的地址，就是訪問(wèn)物理內(nèi)存中被映射的那個(gè)4KB的空間了。

相反，如果頁(yè)表中這個(gè)被尋址的表項(xiàng)對(duì)應(yīng)的有效位是0，則表示這個(gè)虛擬地址對(duì)應(yīng)的4KB空間還沒(méi)有被操作系統(tǒng)映射到物理內(nèi)存中，則此時(shí)就產(chǎn)生了Page Fault類型的異常，需要操作系統(tǒng)從更下一級(jí)的存儲(chǔ)器(例如硬盤或閃存)將這個(gè)頁(yè)對(duì)應(yīng)的4KB內(nèi)容搬移到物理內(nèi)存中。

圖4 通過(guò)頁(yè)表進(jìn)行地址轉(zhuǎn)換

圖4使用了32位的虛擬地址，頁(yè)表在物理內(nèi)存中的起始地址是用PTR來(lái)指示的。虛擬地址的尋址空是232字節(jié)，也就是4GB；物理地址的尋址空間時(shí)232字節(jié)，也就是1GB，這就是對(duì)應(yīng)著實(shí)際物理地址的尋址空間。在頁(yè)表中的一個(gè)表項(xiàng)(entry)能夠映射4KB的大小，為了能夠映射整個(gè)4GB的空間，需要表項(xiàng)的個(gè)數(shù)應(yīng)該是4GB/4KB=1M，也就是220，因此需要20位來(lái)尋址，也就是虛擬地址中除了Page Offset之外的其它部分，也就是說(shuō)32位的虛擬地址中將人為分成兩部分，低12bit用來(lái)尋址一個(gè)頁(yè)內(nèi)的內(nèi)容，高20bit用來(lái)尋址哪個(gè)頁(yè)，因此真正尋址頁(yè)表只需要VPN就夠了。從頁(yè)表中找到的內(nèi)容也不是整個(gè)物理地址，而只是PFN。

從圖4來(lái)看，頁(yè)表中的每個(gè)表項(xiàng)似乎只需要18bit的PFN和1bit的有效位(valid)，也就是總共19bit就夠了。實(shí)際上因?yàn)轫?yè)表是放到物理內(nèi)存中，而物理內(nèi)存中的數(shù)據(jù)位寬都是32bit的，所以導(dǎo)致頁(yè)表中每個(gè)表項(xiàng)的大小也就是32bit，剩余的位用于表示一些其他的信息，如每個(gè)頁(yè)的屬性信息(是否可讀或可寫)等，這樣頁(yè)表的大小就是4B×1M=4MB，也就是說(shuō)，按照目前的描述，一個(gè)程序在運(yùn)行的時(shí)候，需要在物理內(nèi)存中劃分出4MB的連續(xù)空間來(lái)存儲(chǔ)它的頁(yè)表，然后才可以正常地運(yùn)行這個(gè)程序。

需要注意的是，頁(yè)表的結(jié)構(gòu)是不同于cache的，在頁(yè)表中包括了所有VPN的映射關(guān)系，所以可以直接使用VPN對(duì)頁(yè)表進(jìn)行尋址，而不需要使用Tag。

在處理器中，一個(gè)程序?qū)?yīng)的頁(yè)表，連同PC和通用寄存器一起，組成了這個(gè)程序的狀態(tài)，如果在當(dāng)前程序執(zhí)行的時(shí)候，想要另外一個(gè)程序使用這個(gè)處理器，就需要將當(dāng)前程序的狀態(tài)進(jìn)行保存，這樣就可以在一段時(shí)間之后將這個(gè)程序進(jìn)行恢復(fù)，從而使這個(gè)程序可以繼續(xù)執(zhí)行，在操作系統(tǒng)中，通常將這樣的程序稱為進(jìn)程(process)，當(dāng)一個(gè)進(jìn)程被處理器執(zhí)行的時(shí)候，稱這個(gè)進(jìn)程是活躍的(active)，否則就稱之為不活躍(inactive)。操作系統(tǒng)通過(guò)將一個(gè)進(jìn)程的狀態(tài)加載到處理器中，就可以使這個(gè)進(jìn)程進(jìn)入活躍的狀態(tài)。

可以說(shuō)，進(jìn)程是一個(gè)動(dòng)態(tài)的概念，當(dāng)一個(gè)程序只是放在硬盤中，并沒(méi)有被處理器執(zhí)行的時(shí)候，它只是一個(gè)由一條條指令組成的靜態(tài)文件，只有當(dāng)這個(gè)程序被處理器執(zhí)行時(shí)，例如用戶打開(kāi)了一個(gè)程序，此時(shí)才有了進(jìn)程，需要操作系統(tǒng)為其分配物理內(nèi)存中的空間，創(chuàng)建頁(yè)表和堆棧等，這時(shí)候一個(gè)靜態(tài)的程序就變?yōu)榱藙?dòng)態(tài)的進(jìn)程，這個(gè)進(jìn)程可能是一個(gè)，也可能是多個(gè)，這取決于程序本身，當(dāng)然進(jìn)程是有生命期的，一旦用戶關(guān)閉了這個(gè)程序，進(jìn)程也就不存在了，它所占據(jù)的物理內(nèi)存也會(huì)被釋放掉。

一個(gè)進(jìn)程的頁(yè)表指定了它能夠在物理內(nèi)存中訪問(wèn)的地址空間，這個(gè)頁(yè)表當(dāng)然也是位于內(nèi)存中的，在一個(gè)進(jìn)程進(jìn)行狀態(tài)保存的時(shí)候，其實(shí)并不需要保存整個(gè)的頁(yè)表，只需要將這個(gè)頁(yè)表對(duì)應(yīng)的PTR進(jìn)行保存即可。因?yàn)槊總€(gè)進(jìn)程都擁有全部的虛擬存儲(chǔ)器空間，因此不同的進(jìn)程肯定會(huì)存在相同的虛擬地址，操作系統(tǒng)需要負(fù)責(zé)將這些不同的進(jìn)程分配到物理內(nèi)存中不同的地方，并將這些映射(mapping)信息更新到頁(yè)表中(使用store指令就可以完成這個(gè)任務(wù))，這樣不同的進(jìn)程使用的物理內(nèi)存就不會(huì)產(chǎn)生沖突了。

如果按以上方法，每個(gè)進(jìn)程都要占用4MB的物理空間來(lái)存儲(chǔ)頁(yè)表，那運(yùn)行上百個(gè)進(jìn)程時(shí)，那物理內(nèi)存將完全不夠用。但事實(shí)上，一個(gè)程序很難用完整4GB的虛擬存儲(chǔ)器空間，大部分程序只是用了很多一部分，這就造成了頁(yè)表中大部分內(nèi)容其實(shí)都是空的，并沒(méi)有被實(shí)際地使用，這樣整個(gè)頁(yè)表的利用效率其實(shí)是很低的。

可以采用很多方法來(lái)減少一個(gè)進(jìn)程的頁(yè)表對(duì)于存儲(chǔ)空間的需求，最常用的方法是多級(jí)頁(yè)表(Hierarchical Page Table)，這種方法可以減少頁(yè)表對(duì)于物理存儲(chǔ)空間的占用，而且非常容易使用硬件實(shí)現(xiàn)，與之對(duì)應(yīng)的，本節(jié)所講述的頁(yè)表就稱為單級(jí)頁(yè)表(Single Page Table)，也被稱為線性頁(yè)表(Linear Page Table)。

2.2 多級(jí)頁(yè)表

在多級(jí)頁(yè)表的設(shè)計(jì)中，將2.1節(jié)介紹的一個(gè)4MB的線性頁(yè)表劃分為若干個(gè)更小的頁(yè)表，稱它們?yōu)樽禹?yè)表，處理器在執(zhí)行進(jìn)程的時(shí)候，不需要一下子把整個(gè)線性頁(yè)表都放入物理內(nèi)存中，而是根據(jù)需要逐步地放入這些子頁(yè)表。而且，這些子頁(yè)表不再需要占用連續(xù)的物理內(nèi)存空間了，也就是說(shuō)，兩個(gè)相鄰的子頁(yè)表可以放在物理內(nèi)存中不連續(xù)的位置，這樣也提高了物理內(nèi)存的利用效率。但是，由于所有的子頁(yè)表是不連續(xù)地放在物理內(nèi)存中，所以仍舊需要一個(gè)表格，來(lái)記錄每個(gè)子頁(yè)表在物理內(nèi)存中存儲(chǔ)的位置，稱這個(gè)表格為第一級(jí)頁(yè)表(Level1 Page Table)，而那些子頁(yè)表則為第二級(jí)頁(yè)表(Level2 Page Table)，如圖5所示。

圖5 兩級(jí)頁(yè)表

這樣，要得到一個(gè)虛擬地址對(duì)應(yīng)的數(shù)據(jù)，首先需要訪問(wèn)第一級(jí)頁(yè)表，得到這個(gè)虛擬地址所屬的第二級(jí)頁(yè)表的基地址，然后再去第二級(jí)頁(yè)表中才可以得到這個(gè)虛擬地址對(duì)應(yīng)的物理地址，這時(shí)候就可以在物理內(nèi)存中取出相應(yīng)的數(shù)據(jù)。

舉例來(lái)說(shuō)，對(duì)于一個(gè)32位虛擬地址、頁(yè)大小為4KB的系統(tǒng)來(lái)說(shuō)，如果采用線性頁(yè)表，則頁(yè)表的表項(xiàng)個(gè)數(shù)是220，將其分為1024(210)等份，每個(gè)等份就是一個(gè)第二級(jí)頁(yè)表，共有1024個(gè)第二級(jí)頁(yè)表，對(duì)應(yīng)著第一級(jí)頁(yè)表的1024個(gè)表項(xiàng)。也就是說(shuō)，第一級(jí)頁(yè)表需要10位地址進(jìn)行尋址。每個(gè)二級(jí)頁(yè)表中，表項(xiàng)的個(gè)數(shù)是220/210=210個(gè)，也需要10位地址才能尋址第二級(jí)頁(yè)表，如圖6所示過(guò)程的示意圖。

在圖6中，一個(gè)頁(yè)表中的表項(xiàng)簡(jiǎn)稱為PTE(Page Table Entry)，當(dāng)操作系統(tǒng)創(chuàng)建一個(gè)進(jìn)程時(shí)，就在物理內(nèi)存中為這個(gè)進(jìn)程找到一塊連續(xù)的4KB空間(4Bx210=4KB)，存放這個(gè)進(jìn)程的第一級(jí)頁(yè)表，并且將第一級(jí)頁(yè)表在物理內(nèi)存中的起始地址放到PTR寄存器中。通常這個(gè)寄存器都是處理器中的一個(gè)特殊寄存器，例如ARM中的TTB寄存器，x86中的CR3寄存器等。隨著這個(gè)進(jìn)程的執(zhí)行，操作系統(tǒng)會(huì)逐步在物理內(nèi)存中創(chuàng)建第二級(jí)頁(yè)表，每次創(chuàng)建一個(gè)第二級(jí)頁(yè)表，操作系統(tǒng)就要將它的起始地址放到第一級(jí)頁(yè)表對(duì)應(yīng)的表項(xiàng)中，如表1所示為一個(gè)進(jìn)程送出的虛擬地址和第一級(jí)頁(yè)表、第二級(jí)頁(yè)表的對(duì)應(yīng)關(guān)系。

圖6 使用兩級(jí)頁(yè)表進(jìn)行地址轉(zhuǎn)換的一個(gè)例子

表1 虛擬地址和第一級(jí)頁(yè)表、第二級(jí)頁(yè)表的關(guān)系

在圖6中，由于虛擬地址(VA)的p1部分和p2部分的寬度都是10位，因此它們的變化范圍都是0x000-0x3FF，每次當(dāng)虛擬地址的p!部分變化時(shí)，操作系統(tǒng)就需要在物理內(nèi)存中創(chuàng)建一個(gè)新的第二級(jí)頁(yè)表，并將這個(gè)頁(yè)表的其實(shí)瀆職寫到第一級(jí)頁(yè)表對(duì)應(yīng)的PTE中(由虛擬地址的p1部分指定)。

當(dāng)虛擬地址的p1部分不發(fā)生變化，只是p2部分的變化范圍在0x000-0x3FF之內(nèi)時(shí)，此時(shí)不需要?jiǎng)?chuàng)建新的第二級(jí)頁(yè)表。每當(dāng)虛擬地址中的p2部分發(fā)生變化，就表示要使用一個(gè)新的頁(yè)，操作系統(tǒng)將這個(gè)新的頁(yè)從下級(jí)存儲(chǔ)器中(如硬盤)取出來(lái)并放到物理內(nèi)存中，然后將這個(gè)頁(yè)在物理內(nèi)存中的起始地址填充到第二級(jí)頁(yè)表對(duì)應(yīng)的PTE中(由虛擬地址的p2部分指定)。至于虛擬地址的頁(yè)內(nèi)偏移(即Offset)部分，只是用來(lái)在一個(gè)頁(yè)的內(nèi)部找到對(duì)應(yīng)的數(shù)據(jù)，它不會(huì)影響第一級(jí)和第二級(jí)頁(yè)表的創(chuàng)建。

總體來(lái)看，當(dāng)處理器開(kāi)始執(zhí)行一個(gè)程序時(shí)，就會(huì)把第一級(jí)頁(yè)表放到物理內(nèi)存中，直到整個(gè)程序被關(guān)閉為止，因此第一級(jí)頁(yè)表所占用的4KB存儲(chǔ)空間是不可避免的，而第二級(jí)頁(yè)表是否在物理內(nèi)存當(dāng)中，則是根據(jù)一個(gè)程序當(dāng)中虛擬地址的值來(lái)決定，操作系統(tǒng)會(huì)逐個(gè)地創(chuàng)建第二級(jí)頁(yè)表。事實(shí)上，伴隨著一個(gè)頁(yè)表被放入到物理內(nèi)存中，必然會(huì)有第二級(jí)頁(yè)表中的一個(gè)PTE被建立，這個(gè)PTE會(huì)被寫入該頁(yè)在物理內(nèi)存中的起始地址，如果這個(gè)頁(yè)對(duì)應(yīng)的第二級(jí)頁(yè)表還不存在，那么就需要操作系統(tǒng)建立一個(gè)新的第二級(jí)頁(yè)表。

多級(jí)頁(yè)表有個(gè)優(yōu)點(diǎn)就是容易擴(kuò)展，當(dāng)處理器的位數(shù)增加時(shí)，可以通過(guò)增加級(jí)數(shù)的方式來(lái)減少頁(yè)表對(duì)于物理內(nèi)存的占用。如圖7所示。

圖7 使用多級(jí)頁(yè)表進(jìn)行地址轉(zhuǎn)換

在處理器中如果存在多個(gè)進(jìn)程，為這些進(jìn)程分配的物理內(nèi)存之和可能大于實(shí)際可用的物理內(nèi)存，虛擬存儲(chǔ)器的管理使得這些情況下各個(gè)進(jìn)程仍能夠正常運(yùn)行，此時(shí)為各個(gè)進(jìn)程分配的只是虛擬存儲(chǔ)器的頁(yè)，這些頁(yè)有可能存在于物理內(nèi)存中，也可能臨時(shí)存在于更下一級(jí)的硬盤中，在硬盤中這部分空間稱為swap空間。

當(dāng)物理內(nèi)存不夠用時(shí)，將物理內(nèi)存中的一些不常用的頁(yè)保存在硬盤上的swap空間，而需要用到這些頁(yè)時(shí)，再將其從硬盤的swap空間加載到物理內(nèi)存，因此，處理器中等效可以使用的物理內(nèi)存的總量是物理內(nèi)存的大小 + 硬盤中swap空間的大小。

將一個(gè)頁(yè)從物理內(nèi)存中寫到硬盤的swap空間的過(guò)程稱為Page Out，將一個(gè)頁(yè)從硬盤的swap空間放回物理內(nèi)存的過(guò)程稱為Page In，如圖8所示為這兩個(gè)過(guò)程的示意圖。

圖8 Page In和Page Out

利用虛擬存儲(chǔ)器，可以管理每一個(gè)頁(yè)的訪問(wèn)權(quán)限，從硬件的角度來(lái)看，單純的物理內(nèi)存本身不具有各種權(quán)限的屬性，它的任何地址都可以被讀寫，而操作系統(tǒng)則要求在物理內(nèi)存中實(shí)現(xiàn)不同的訪問(wèn)權(quán)限，例如一個(gè)進(jìn)程的代碼段(text)一般不能夠被修改，這樣可以防止程序錯(cuò)誤地修改自己，因此它的屬性就要是可讀可執(zhí)行(r/x)，但是不能夠被寫入；而一個(gè)進(jìn)程的數(shù)據(jù)段(data)要求是可讀可寫的(r/w)；同時(shí)用戶進(jìn)程不能訪問(wèn)屬于內(nèi)核的地址空間。這些權(quán)限的管理就是通過(guò)頁(yè)表(Page Table)來(lái)實(shí)現(xiàn)的，通過(guò)在頁(yè)表中設(shè)置每個(gè)頁(yè)的屬性，操作系統(tǒng)和內(nèi)存管理單元(MMU)可以控制每個(gè)頁(yè)的訪問(wèn)權(quán)限，這樣就實(shí)現(xiàn)了程序的權(quán)限管理。

2.3?Page Fault

如果一個(gè)進(jìn)程中的虛擬地址在訪問(wèn)頁(yè)表時(shí)，發(fā)現(xiàn)對(duì)應(yīng)的PTE中，有效位(valid)為0，這就表示這個(gè)虛擬地址所屬的頁(yè)還沒(méi)有被放到物理內(nèi)存中，因此在頁(yè)表中就沒(méi)有存儲(chǔ)這個(gè)頁(yè)的映射關(guān)系，這時(shí)候就說(shuō)發(fā)生了Page Fault，需要從下級(jí)存儲(chǔ)器(例如硬盤)將這個(gè)頁(yè)取出來(lái)，放到物理內(nèi)存中，并將這個(gè)頁(yè)在物理內(nèi)存中的起始地址寫到頁(yè)表中。Page Fault是異常(exception)的一種，通常它的處理過(guò)程不是由硬件完成的，而是由軟件完成的，確切的說(shuō)，是由操作系統(tǒng)完成的，因?yàn)椴僮飨到y(tǒng)也是軟件。

在有Page Fault時(shí)，處理器會(huì)跳轉(zhuǎn)到這個(gè)異常處理程序的入口地址，異常處理程序會(huì)根據(jù)某種替換算法，從物理內(nèi)存中找到一個(gè)空閑的地方，將需要的頁(yè)從硬盤中搬移進(jìn)來(lái)，并將這個(gè)新的對(duì)應(yīng)關(guān)系寫到頁(yè)表中相應(yīng)的PTE內(nèi)。

需要注意的是，直接使用虛擬地址并不能知道一個(gè)頁(yè)位于硬盤的哪個(gè)位置，也需要一個(gè)機(jī)制來(lái)記錄一個(gè)進(jìn)程的每個(gè)頁(yè)位于硬盤中的位置。

通常，操作系統(tǒng)會(huì)在硬盤中為一個(gè)進(jìn)程的所有頁(yè)開(kāi)辟一塊空間，這就是之前說(shuō)過(guò)的swap空間，在這個(gè)空間中存儲(chǔ)一個(gè)進(jìn)程所有的頁(yè)，操作系統(tǒng)在開(kāi)辟swap空間的同時(shí)，還會(huì)使用一個(gè)表格來(lái)記錄每個(gè)頁(yè)在硬盤中存儲(chǔ)的位置，這個(gè)表格的結(jié)構(gòu)其實(shí)和頁(yè)表是一樣的，它可以單獨(dú)存在，從理論上來(lái)講也可以和頁(yè)表合并在一起，如圖9所示。

圖9 同一個(gè)頁(yè)表中記錄了所有的內(nèi)容

圖9所示在一個(gè)頁(yè)表內(nèi)記錄了一個(gè)進(jìn)程中的每個(gè)頁(yè)在物理內(nèi)存或在硬盤中的位置，當(dāng)頁(yè)表中某個(gè)PTE的有效位(valid)為1時(shí)，就表示它對(duì)應(yīng)的頁(yè)在物理內(nèi)存中，訪問(wèn)這個(gè)頁(yè)不會(huì)發(fā)生Page Fault；相反，如果有效位是0，則表示它對(duì)應(yīng)的頁(yè)位于硬盤中，訪問(wèn)這個(gè)頁(yè)就會(huì)發(fā)生Page Fault，此時(shí)操作系統(tǒng)需要從硬盤中將這個(gè)頁(yè)搬移到物理內(nèi)存中，并將這個(gè)頁(yè)在物理內(nèi)存的起始地址更新到頁(yè)表中對(duì)應(yīng)的PTE內(nèi)。

雖然圖9中，映射到物理內(nèi)存的頁(yè)表和映射到硬盤的頁(yè)表可以放到一起，但在實(shí)際當(dāng)中，物理上它們是分開(kāi)放置的，因?yàn)椴还芤粋€(gè)頁(yè)是不是在物理內(nèi)存中，操作系統(tǒng)都必須記錄一個(gè)進(jìn)程的所有頁(yè)在硬盤中的位置，因此需要單獨(dú)地使用一個(gè)表格來(lái)記錄它。

物理內(nèi)存相當(dāng)于是硬盤的Cache，因?yàn)閷?duì)一個(gè)程序來(lái)說(shuō)，它的所有內(nèi)容其實(shí)都存在于硬盤中，只有最近被使用的一部分內(nèi)容存在物理內(nèi)存中，這樣符合Cache的特征。因?yàn)橐粋€(gè)程序的某些內(nèi)容既存在于硬盤中，也存在于物理內(nèi)存中，當(dāng)物理內(nèi)存中某個(gè)地址的內(nèi)容被改變時(shí)(例如執(zhí)行一條store指令，改變了程序中的某個(gè)變量)，對(duì)于這個(gè)地址來(lái)說(shuō)，在硬盤中的存儲(chǔ)的內(nèi)容就過(guò)時(shí)了，這種情況再Cache中也出現(xiàn)過(guò)，有兩種處理方法。

寫通(Write Through)：將這個(gè)改變的內(nèi)容馬上寫回硬盤中，考慮到硬盤的訪問(wèn)時(shí)間非常慢，這樣的做法是不現(xiàn)實(shí)的；

寫回(Write Back)：只有等到這個(gè)地址的內(nèi)容在物理內(nèi)存中要被替換時(shí)，才將這個(gè)內(nèi)容寫回到硬盤中，這種方式減少了硬盤的訪問(wèn)次數(shù)，因此被廣泛使用。

其實(shí)，寫通(Write Through)的方式只可能在L1 Cache和L2 Cache之間使用，因此L2 Cache的訪問(wèn)時(shí)間在一個(gè)可以接受的范圍之內(nèi)，而且這樣可以降低Cache一致性的管理難度，但是更下層的存儲(chǔ)器需要的訪問(wèn)時(shí)間越來(lái)越長(zhǎng)，因此只有寫回(Write Back)方式才是可以接受的方法。

既然在虛擬存儲(chǔ)器的系統(tǒng)中采用了寫回的方式，當(dāng)發(fā)生Page Fault并且物理內(nèi)存已經(jīng)沒(méi)有空間時(shí)，操作系統(tǒng)需要從其中找到一個(gè)頁(yè)進(jìn)行替換，如果這個(gè)頁(yè)的某些內(nèi)容被修改過(guò)，那么在覆蓋這個(gè)頁(yè)之前，需要先將它的內(nèi)容寫回到硬盤中，然后才能進(jìn)行覆蓋。

為了支持這個(gè)功能，需要記錄每個(gè)頁(yè)是否在物理內(nèi)存中被修改過(guò)，通常是在頁(yè)表的每個(gè)PTE中增加一個(gè)臟(dirty)的狀態(tài)位，當(dāng)一個(gè)頁(yè)的某個(gè)地址被寫入時(shí)，這個(gè)臟的狀態(tài)位會(huì)被置為1。

當(dāng)操作系統(tǒng)需要將一個(gè)頁(yè)進(jìn)行替換之前，會(huì)首先去頁(yè)表中檢查它對(duì)應(yīng)的PTE臟狀態(tài)位，如果為1，則需要先將這個(gè)頁(yè)的內(nèi)容寫回到硬盤中；如果為0，則表示這個(gè)頁(yè)從來(lái)沒(méi)有被修改過(guò)，那么就可以直接將其覆蓋了，因?yàn)樵谟脖P中還保存著這個(gè)頁(yè)的內(nèi)容。

從一個(gè)時(shí)間點(diǎn)來(lái)看物理內(nèi)存，會(huì)存在很多的頁(yè)處于臟的狀態(tài)，這些頁(yè)都被寫入了新的內(nèi)容，當(dāng)然，一旦這些臟的頁(yè)被寫回到硬盤中，它們?cè)谖锢韮?nèi)存中也就不再是臟的狀態(tài)了。

為了幫助操作系統(tǒng)在發(fā)生Page Fault的時(shí)候，從物理內(nèi)存中找到一個(gè)頁(yè)進(jìn)行替換(當(dāng)物理內(nèi)存沒(méi)有空閑的空間時(shí))，需要處理器在硬件層面上提供支持，這可以在頁(yè)表的每一個(gè)PTE中增加一位，用來(lái)記錄每個(gè)頁(yè)最近是否被訪問(wèn)過(guò)，這一位稱為“使用位(use)”，當(dāng)一個(gè)頁(yè)被訪問(wèn)時(shí)，“使用位”被置為1，操作系統(tǒng)周期性地將這一位清零，然后過(guò)一段時(shí)間再去查看它，這樣就能夠知道每一個(gè)頁(yè)在這段時(shí)間是否被訪問(wèn)過(guò)，那么最近這段時(shí)間沒(méi)有被使用過(guò)的頁(yè)就可以被替換了。

這種方式是近似的LRU算法，被大多數(shù)操作系統(tǒng)所使用，由于使用了硬件來(lái)實(shí)現(xiàn)“使用位”，所以操作系統(tǒng)的任務(wù)量被大大地減輕了。

總結(jié)來(lái)說(shuō)，為了處理Page Fault，處理器在硬件上需要提供的支持有如下幾種：

在發(fā)現(xiàn)Page Fault時(shí)，能夠產(chǎn)生對(duì)應(yīng)類型的異常，并且能夠跳轉(zhuǎn)到它的異常處理程序的入口地址；

當(dāng)要寫物理內(nèi)存時(shí)，例如執(zhí)行了store指令，需要硬件將頁(yè)表中對(duì)應(yīng)PTE的臟狀態(tài)位置為1；

當(dāng)訪問(wèn)物理內(nèi)存時(shí)，例如執(zhí)行了store指令，需要硬件將頁(yè)表中對(duì)應(yīng)PTE的“使用位”置為1，表示這個(gè)頁(yè)最近被訪問(wèn)過(guò)。

需要注意的是，在寫回(Write Back)類型的Cache中，load/store指令在執(zhí)行的時(shí)候，只會(huì)對(duì)D-Cache起作用，對(duì)物理內(nèi)存中頁(yè)表的更新可能會(huì)有延遲，當(dāng)操作系統(tǒng)需要查詢頁(yè)表中的這些狀態(tài)位時(shí)，首先需要將D-Cache中的內(nèi)容更新到物理內(nèi)存中，這樣才能夠使用到頁(yè)表中正確的狀態(tài)位。

因此，本節(jié)現(xiàn)在為止，頁(yè)表中每個(gè)PTE的內(nèi)容如圖10所示。

圖10 頁(yè)表中包括的內(nèi)容

三 程序保護(hù)

在現(xiàn)代處理器運(yùn)行的環(huán)境中，存在著操作系統(tǒng)和許多的用戶進(jìn)程，操作系統(tǒng)和用戶對(duì)于存儲(chǔ)空間需要有不同的訪問(wèn)權(quán)限，因此可以在頁(yè)表上來(lái)實(shí)現(xiàn)這個(gè)功能，因?yàn)橐L問(wèn)存儲(chǔ)器的內(nèi)容必須要經(jīng)過(guò)頁(yè)表，所以在頁(yè)表中對(duì)各個(gè)頁(yè)規(guī)定不同的訪問(wèn)權(quán)限是很自然的事。

需要注意的是操作系統(tǒng)本身也需要指令和數(shù)據(jù)，但是考慮到它需要能夠訪問(wèn)物理內(nèi)存中所有的空間，所以操作系統(tǒng)一般不會(huì)使用頁(yè)表，而是直接可以訪問(wèn)物理內(nèi)存，在物理內(nèi)存中有一部分地址范圍專門供操作系統(tǒng)使用，不允許別的進(jìn)程隨便訪問(wèn)它。

在Arm處理器中，采用了兩級(jí)頁(yè)表的方法，第二級(jí)頁(yè)表的每個(gè)PTE中都有一個(gè)AP部分，在Arm v7架構(gòu)中，AP部分直接決定了每個(gè)頁(yè)的訪問(wèn)權(quán)限，如表2所示。

表2?Arm中每個(gè)頁(yè)的權(quán)限管理

在Arm v7架構(gòu)中，規(guī)定處理器可以工作在User模式和Privileged模式，在Privileged模式下，可以訪問(wèn)處理器內(nèi)部所有的資源，因此操作系統(tǒng)會(huì)運(yùn)行在這種模式下，而普通的用戶程序則是運(yùn)行在User模式下。在表2中，AP[2:0]位于PTE中，通過(guò)它，第二級(jí)頁(yè)表可以控制每個(gè)頁(yè)的訪問(wèn)權(quán)限，這樣可以使一個(gè)頁(yè)對(duì)于不同的進(jìn)程有著不同的訪問(wèn)權(quán)限。

既然在頁(yè)表中規(guī)定了每個(gè)頁(yè)的訪問(wèn)權(quán)限，那么一旦發(fā)現(xiàn)當(dāng)前的訪問(wèn)不符合規(guī)定，例如一個(gè)頁(yè)不允許用戶進(jìn)程訪問(wèn)，但是當(dāng)前的用戶進(jìn)程卻要讀取這個(gè)頁(yè)的某個(gè)地址，這樣就發(fā)生了非法訪問(wèn)，會(huì)產(chǎn)生給異常(exception)來(lái)通知處理器，使處理器跳轉(zhuǎn)到異常處理程序中，這個(gè)處理程序一般是操作系統(tǒng)的一部分，由操作系統(tǒng)決定如何處理這種非法的訪問(wèn)，例如操作系統(tǒng)可以終止當(dāng)前的用戶進(jìn)程，以防止惡意的程序?qū)ο到y(tǒng)造成的破壞，圖11為地址轉(zhuǎn)換的過(guò)程中加入了權(quán)限檢查的過(guò)程，注意此時(shí)在PTE中多了用來(lái)進(jìn)行權(quán)限控制的AP部分。

圖11 加入程序保護(hù)之后的地址轉(zhuǎn)換

當(dāng)然如果采用了兩級(jí)頁(yè)表的結(jié)構(gòu)，那么圖11只給出了第二級(jí)頁(yè)表的工作過(guò)程，事實(shí)上在第一級(jí)頁(yè)表中葉可以進(jìn)行權(quán)限控制，而且可以控制更大的地址范圍。

舉例來(lái)說(shuō)，在前文講述的頁(yè)大小為4KB的系統(tǒng)中，第一級(jí)頁(yè)表中每個(gè)PTE都可以映射一個(gè)完整的第二級(jí)頁(yè)表，也就是4KBx1024=4MB的地址范圍。

也就是說(shuō)，第一級(jí)頁(yè)表中的每個(gè)PTE都可以控制4MB的地址范圍，這樣可以更高效地對(duì)大片地址進(jìn)行權(quán)限設(shè)置和檢查。例如可以在第一級(jí)頁(yè)表的每個(gè)PTE中設(shè)置一個(gè)兩位的權(quán)限控制位，當(dāng)其為00時(shí)，它對(duì)應(yīng)的整個(gè)4MB空間都不允許被訪問(wèn)；當(dāng)為11時(shí)，對(duì)應(yīng)的4MB空間將不設(shè)限制，隨便訪問(wèn)；當(dāng)為01時(shí)，需要查看第二級(jí)頁(yè)表的PTE，以獲得關(guān)于每個(gè)頁(yè)自身訪問(wèn)權(quán)限的情況；通過(guò)這種粗粒度(第一級(jí)頁(yè)表的權(quán)限控制)和細(xì)粒度(第二級(jí)頁(yè)表的權(quán)限控制)的組合，可以在一定程度上提高處理器的執(zhí)行效率。

如果存在D-Cache的系統(tǒng)中，處理器送出的虛擬地址經(jīng)過(guò)頁(yè)表轉(zhuǎn)換為物理地址之后，其實(shí)并不會(huì)直接去訪問(wèn)物理內(nèi)存，而是先訪問(wèn)D-Cache。

如果是讀操作，那么直接從D-Cache中讀取數(shù)據(jù)；如果是寫操作，那么也是直接寫D-Cache（假設(shè)命中），并將被寫入的Cacheline置為臟(dirty)狀態(tài)。只要D-Cache是命中的，就不需要再去訪問(wèn)物理內(nèi)存了。

但是，如果處理器送出的虛擬地址并不是訪問(wèn)物理內(nèi)存，而是要訪問(wèn)芯片內(nèi)的外設(shè)寄存器，例如要訪問(wèn)LCD驅(qū)動(dòng)模塊的寄存器，此時(shí)對(duì)這些寄存器的讀寫是為了對(duì)外設(shè)進(jìn)行操作，因此這些地址是不允許經(jīng)過(guò)D-Cache被緩存的，如果被緩存了，那么這些操作將只會(huì)在D-Cache中起作用，并不會(huì)傳遞到外設(shè)寄存器中而真正對(duì)外設(shè)模塊進(jìn)行操作，這樣顯然是不可以的，因此在處理器的存儲(chǔ)器映射(memory map)中，總會(huì)有一塊區(qū)域，是不可以被緩存的。例如MIPS處理器的kseg1區(qū)域就不允許被緩存，它的屬性是uncached，這個(gè)屬性也應(yīng)該在頁(yè)表中加以標(biāo)記，在訪問(wèn)頁(yè)表從而得到物理地址時(shí)，會(huì)對(duì)這個(gè)地址對(duì)應(yīng)的頁(yè)是否允許緩存進(jìn)行檢查，如果發(fā)現(xiàn)這個(gè)頁(yè)的屬性是不允許緩存的，那么就需要直接使用剛剛得到的物理地址來(lái)訪問(wèn)外設(shè)或物理內(nèi)存；如果這個(gè)頁(yè)的屬性是允許被緩存，那么就可以直接使用物理地址對(duì)D-Cache進(jìn)行尋址。

到本小結(jié)為止，總結(jié)起來(lái)，在頁(yè)表中的每個(gè)PTE都包括如下的內(nèi)容：

PFN，表示虛擬地址對(duì)應(yīng)的物理地址的頁(yè)號(hào)； ?

Valid，表示對(duì)應(yīng)的頁(yè)當(dāng)前是否在物理內(nèi)存中；

Dirty，表示對(duì)應(yīng)頁(yè)中的內(nèi)容是否被修改過(guò)；

Use，表示對(duì)應(yīng)頁(yè)中的內(nèi)容是否最近被訪問(wèn)過(guò)；

AP，訪問(wèn)權(quán)限控制，表示操作系統(tǒng)和用戶程序?qū)Ξ?dāng)前這個(gè)頁(yè)的訪問(wèn)權(quán)限；

Cacheable，表示對(duì)應(yīng)的頁(yè)是否允許被緩存。 ?

四 加入TLB和Cache

4.1 TLB的設(shè)計(jì)

4.1.1 概述

對(duì)兩級(jí)頁(yè)表來(lái)說(shuō)，需要訪問(wèn)兩次物理內(nèi)存才可以得到虛擬地址對(duì)應(yīng)的物理地址，而物理內(nèi)存的運(yùn)行速度相對(duì)于處理器本身來(lái)說(shuō)，有幾十倍的差距，因此整體下來(lái)速度很慢的。此時(shí)可以借鑒Cache的設(shè)計(jì)理念，使用一個(gè)速度比較快的緩存，將頁(yè)表中最近使用的PTE緩存下來(lái)，因?yàn)樗鼈冊(cè)谝院筮€可能繼續(xù)使用，尤其對(duì)于取指令來(lái)說(shuō)，考慮到程序本身的串行性，會(huì)順序地從一個(gè)頁(yè)內(nèi)取指令，此時(shí)將PTE緩存起來(lái)是大有益處的，能夠加快一個(gè)頁(yè)內(nèi)4KB內(nèi)容的地址轉(zhuǎn)換速度。

由于歷史原因，緩存PTE的部件一般不稱為Cache，而是稱之為TLB(Translation Lookaside buffer)，在TLB中存儲(chǔ)了頁(yè)表中最近被使用過(guò)的PTE，從本質(zhì)上來(lái)講，TLB就是頁(yè)表的Cache。但是TLB又不同于一般的cache，它只有時(shí)間相關(guān)性(Temporal Locality)，也就是說(shuō)，現(xiàn)在訪問(wèn)的頁(yè)，很有可能在以后繼續(xù)被訪問(wèn)，至于空間相關(guān)性(Temporal Locality)，TLB并沒(méi)有明顯的規(guī)律，因?yàn)樵谝粋€(gè)頁(yè)內(nèi)有很多情況，都可能使程序跳轉(zhuǎn)到其他不相鄰的頁(yè)中取指令或數(shù)據(jù)，也就是說(shuō)，雖然當(dāng)前在訪問(wèn)一個(gè)頁(yè)，但未必會(huì)訪問(wèn)它相鄰的頁(yè)，正因?yàn)槿绱?，Cache設(shè)計(jì)中很多的優(yōu)化方法，例如預(yù)取(prefetching)，是沒(méi)有辦法應(yīng)用于TLB中的。

既然TLB本質(zhì)上是Cache，那么就有三種組織方法：直接相連、組相連和全相連。一般為了減少TLB缺失率，會(huì)用全相連來(lái)設(shè)計(jì)TLB，但容量過(guò)小的TLB會(huì)影響處理器的性能，因此在現(xiàn)代的處理器中，很多都采用兩級(jí)TLB，第一級(jí)TLB采用哈佛結(jié)構(gòu)，分為指令TLB(I-TLB)和數(shù)據(jù)TLB(D-TLB)，一般采用全相連的方式；第二級(jí)TLB是指令和數(shù)據(jù)共享，一般采用組相連的方式，這種設(shè)計(jì)方法和多級(jí)Cache是一樣的。

因?yàn)門LB是頁(yè)表的Cache，那么TLB的內(nèi)容是完全來(lái)自于頁(yè)表的，如圖12為一個(gè)全相連方式的TLB，從處理器送出的虛擬地址首先送到TLB中進(jìn)行查找，如果TLB對(duì)應(yīng)的內(nèi)容是有效的(即valid位為1)，則表示TLB命中，可以直接使用從TLB得到的物理地址來(lái)尋址物理內(nèi)存；如果TLB缺失(即valid位為0)，那么就需要訪問(wèn)物理內(nèi)存中的頁(yè)表，此時(shí)有如下兩種情況：

(1) 在頁(yè)表中找到的PTE是有效的，即這個(gè)虛擬地址所屬的頁(yè)存在于物理內(nèi)存中，那么就可以直接從頁(yè)表中找到對(duì)應(yīng)的物理地址，使用它來(lái)尋址物理內(nèi)存從而得到需要的數(shù)據(jù)，同時(shí)將頁(yè)表中的這個(gè)PTE寫回到TLB中，供以后使用；

(2) 在頁(yè)表中找到的PTE是無(wú)效的，即這個(gè)虛擬地址所屬的頁(yè)不在物理內(nèi)存中，造成這種現(xiàn)象的原因很多，例如這個(gè)頁(yè)在以前沒(méi)有被使用過(guò)，或者這個(gè)頁(yè)已經(jīng)被交換到了硬盤中等，此時(shí)就應(yīng)該產(chǎn)生Page Fault類型的異常，通知操作系統(tǒng)來(lái)處理這個(gè)情況，操作系統(tǒng)需要從硬盤中將相應(yīng)的頁(yè)搬移到物理內(nèi)存中，將它在物理內(nèi)存中的首地址放到頁(yè)表內(nèi)對(duì)應(yīng)的PTE中，并將這個(gè)PTE的內(nèi)容寫到TLB中。

圖12 TLB內(nèi)容

在圖12中，因?yàn)門LB采用了全相連的方式，所以相比頁(yè)表多了一個(gè)Tag的項(xiàng)，它保存了虛擬地址的VPN，用來(lái)對(duì)TLB進(jìn)行匹配查找，TLB中其它的項(xiàng)完全來(lái)自于頁(yè)表，每當(dāng)發(fā)生TLB缺失時(shí)，將PTE從頁(yè)表中搬移到TLB內(nèi)。

4.1.2 TLB缺失

當(dāng)一個(gè)虛擬地址查找TLB，發(fā)現(xiàn)需要的內(nèi)容不在其中時(shí)，就發(fā)生了TLB缺失(miss)，由于TLB本身的容量很小，所以TLB缺失發(fā)生的頻率比較高，很多情況下都可以發(fā)生TLB缺失，主要有以下幾種：

(1) 虛擬地址對(duì)應(yīng)的頁(yè)不在物理內(nèi)存中，所以頁(yè)表也沒(méi)有對(duì)應(yīng)的PTE，自然TLB中也不可能有的；

(2) 虛擬地址對(duì)應(yīng)的頁(yè)在物理內(nèi)存中，所以頁(yè)表中有對(duì)應(yīng)的PTE，但這個(gè)PTE還沒(méi)有放到TLB中，這種情況也經(jīng)常發(fā)生，畢竟TLB的內(nèi)容遠(yuǎn)小于頁(yè)表；

(3) 虛擬地址對(duì)應(yīng)的頁(yè)在物理內(nèi)存中，所以頁(yè)表中有對(duì)應(yīng)的PTE，這個(gè)PTE也曾存在于TLB中，但后來(lái)被替換出去了，現(xiàn)在這個(gè)也又重新使用了，此時(shí)這個(gè)PTE就存在于頁(yè)表中，但不在TLB內(nèi)。

解決TLB缺失的本質(zhì)就是要從頁(yè)表中找到對(duì)應(yīng)的映射關(guān)系，并將其寫回到TLB內(nèi)，這個(gè)過(guò)程稱為Page Table Walk，可以使用硬件狀態(tài)機(jī)來(lái)完成這個(gè)事情，也可以使用軟件來(lái)做這個(gè)事情，各有優(yōu)缺點(diǎn)，各自工作流程如下：

(1) 軟件實(shí)現(xiàn)Page Table Walk，軟件實(shí)現(xiàn)可以保證最大的靈活性，但一般也需要硬件配合，來(lái)減少工作量，一旦發(fā)現(xiàn)TLB缺失，硬件把產(chǎn)生TLB缺失的虛擬地址保存到一個(gè)特殊寄存器中，同時(shí)產(chǎn)生一個(gè)TLB缺失類型的異常，在異常處理程序中，軟件使用保存在特殊寄存器當(dāng)中的虛擬地址去尋址物理內(nèi)存中的頁(yè)表，找到對(duì)應(yīng)的PTE，并寫回到TLB中，很顯然，處理器需要支持直接操作TLB的指令，如寫TLB指令和讀TLB指令等。

對(duì)于超標(biāo)量處理器，對(duì)異常處理時(shí)，會(huì)將流水線中所有的指令抹掉，這樣會(huì)產(chǎn)生一些性能上缺失，但可以實(shí)現(xiàn)靈活的TLB替換算法，MIPS和Alpha處理器一般采用這種方法處理TLB缺失。為了防止在處理TLB缺失的異常處理程序再次發(fā)生TLB缺失，一般將這段異常處理程序放到一個(gè)不需要進(jìn)行地址轉(zhuǎn)換的預(yù)取，這樣就可以直接使用物理地址來(lái)取指令和數(shù)據(jù)，避免再次發(fā)生TLB缺失的情況。軟件處理TLB缺失的過(guò)程如圖13所示。

圖13 軟件處理TLB miss的流程

(2) 硬件實(shí)現(xiàn)Page Table Walk，硬件實(shí)現(xiàn)一般由內(nèi)存管理單元(MMU)完成，當(dāng)發(fā)現(xiàn)TLB缺失時(shí)，MMU自動(dòng)使用當(dāng)前的虛擬地址去尋址物理內(nèi)存中的頁(yè)表，前面說(shuō)過(guò)，多級(jí)頁(yè)表的最大優(yōu)點(diǎn)就是容易使用硬件進(jìn)行查找，只需要使用一個(gè)狀態(tài)機(jī)逐級(jí)進(jìn)行查找就可以，如果從頁(yè)表中找到的PTE是有效的，那么將它寫回到TLB中，這個(gè)過(guò)程全部由硬件自動(dòng)完成的。

當(dāng)然如果MMU發(fā)現(xiàn)查找到的PTE是無(wú)效的，那么就只能產(chǎn)生Page Fault類型的異常，由操作系統(tǒng)來(lái)處理整個(gè)情況。使用硬件處理TLB缺失更適合超標(biāo)量處理器，它不需要打斷流水線，因此從理論上來(lái)說(shuō)，性能會(huì)好一點(diǎn)，但是這需要操作系統(tǒng)保證頁(yè)表已經(jīng)在物理內(nèi)存中建立好了，并且操作系統(tǒng)也需要將頁(yè)表的基地址預(yù)先寫到處理器內(nèi)部的寄存器中(例如PTR寄存器)，這樣才能保證硬件可以正確地尋址頁(yè)表，Arm、PowerPC和x86處理器都采用了這種方法。

對(duì)于組相連或全相連結(jié)構(gòu)的TLB，當(dāng)一個(gè)新的PTE被寫到TLB中時(shí)，如果當(dāng)前TLB中沒(méi)有空閑的位置了，那么就要考慮將其中的一個(gè)表項(xiàng)(entry)進(jìn)行替換。理論上說(shuō)，Cache中使用的替換方法在TLB里也可以，例如最少使用算法(LRU)，但是實(shí)際上對(duì)于TLB來(lái)說(shuō)，隨機(jī)替換(Random)算法可以是一種比較合適的方法，通?？梢圆捎?a href="http://www.brongaenegriffin.com/tags/時(shí)鐘/" target="_blank">時(shí)鐘算法(Clock Algorithm)來(lái)實(shí)現(xiàn)近似的隨機(jī)。

4.1.3 TLB的寫入

當(dāng)一個(gè)頁(yè)從硬盤搬移到物理內(nèi)存之后，操作系統(tǒng)需要知道這個(gè)頁(yè)中的內(nèi)容在物理內(nèi)存中是否被改變過(guò)。如果沒(méi)有被改變過(guò)，當(dāng)這個(gè)頁(yè)需要被替換時(shí)可以直接進(jìn)行覆蓋，因?yàn)榭偰軓挠脖P中找到這個(gè)頁(yè)的備份；如果已經(jīng)被修改過(guò)了，需要先將它從物理內(nèi)存中寫回到硬盤，因此需要在頁(yè)表中，對(duì)每個(gè)被修改的頁(yè)加以標(biāo)記，稱為臟狀態(tài)位(dirty)。當(dāng)物理內(nèi)存中的一個(gè)頁(yè)要被替換時(shí)，需要首先檢查它在頁(yè)表中對(duì)應(yīng)PTE的臟狀態(tài)位，如果它是1，那么就需要先將這個(gè)頁(yè)寫回到硬盤中，然后才能將其覆蓋。

如果采用寫回(Write Back)的TLB，那么使用位(use)和臟狀態(tài)位(dirty)改變的信息并不會(huì)馬上從TLB中寫回到頁(yè)表，只有等到TLB中的一個(gè)表項(xiàng)要被替換的時(shí)候，才會(huì)將它對(duì)應(yīng)的信息寫回到頁(yè)表中，這種方式會(huì)給操作系統(tǒng)進(jìn)行頁(yè)表替換帶來(lái)問(wèn)題，因?yàn)轫?yè)表中記錄的狀態(tài)位(use和dirty)可能是過(guò)時(shí)的。一種比較容易的解決辦法就是操作系統(tǒng)在Page Fault發(fā)生時(shí)，首先將TLB中的內(nèi)容寫回到頁(yè)表，然后就可以根據(jù)頁(yè)表中的信息進(jìn)行后續(xù)處理了。在實(shí)際上，操作系統(tǒng)完全可以認(rèn)為被TLB記錄的所有頁(yè)都是需要被使用的，這些頁(yè)在物理內(nèi)存中不能夠被替換。操作系統(tǒng)可以使用一系誒辦法來(lái)記錄頁(yè)表中哪些PTE被放到了TLB中來(lái)實(shí)現(xiàn)。

如果在系統(tǒng)中使用了D-Cache，那么物理內(nèi)存中每個(gè)頁(yè)的最新內(nèi)容都可能存在于D-Cache中，要將這個(gè)頁(yè)的內(nèi)容寫回到硬盤，首先需要確認(rèn)D-Cache中s會(huì)否保留著這個(gè)頁(yè)的數(shù)據(jù)。因此在進(jìn)行頁(yè)表替換時(shí)，操作系統(tǒng)就必須有能力從D-Cache中找出這個(gè)頁(yè)的內(nèi)容，并將其寫回到物理內(nèi)存中，這部分后面會(huì)介紹的。

雖然對(duì)于TLB和D-Cache都是Cache，但在操作系統(tǒng)對(duì)物理內(nèi)存進(jìn)行頁(yè)表替換時(shí)，所采取的的方法措施有點(diǎn)不同的，TLB中存在的頁(yè)表在物理內(nèi)存中不會(huì)替換，D-Cache中存在數(shù)據(jù)所對(duì)應(yīng)地址的頁(yè)表在物理內(nèi)存中仍然會(huì)被替換，所以此時(shí)也需要將D-Cache的內(nèi)容clean掉，切記兩者的不同之處。

4.1.4 對(duì)TLB進(jìn)行控制

如果由于某些原因?qū)е乱粋€(gè)頁(yè)的映射關(guān)系在頁(yè)表中不存在了，那么它在TLB中也不應(yīng)該存在，而操作系統(tǒng)在一些情況下，會(huì)把某些頁(yè)的映射關(guān)系從頁(yè)表中抹掉，例如：

(1) 當(dāng)一個(gè)進(jìn)程結(jié)束時(shí)，這個(gè)進(jìn)程的指令(code)、數(shù)據(jù)(data)和堆棧(stack)所占據(jù)的頁(yè)表就需要變?yōu)闊o(wú)效，這樣也就釋放了這個(gè)進(jìn)程所占據(jù)的物理內(nèi)存空間。

但是，此時(shí)在I-TLB中可能存在這個(gè)進(jìn)程的程序(code)對(duì)應(yīng)的PTE，在D-TLB中可能還存在著這個(gè)進(jìn)程的數(shù)據(jù)和堆棧的PTE，此時(shí)就需要將I-TLB和D-TLB中和這個(gè)進(jìn)程相關(guān)的所有內(nèi)容置為無(wú)效，如果沒(méi)有使用ASID，最簡(jiǎn)單的做法就是將I-TLB和D-TLB中的全部?jī)?nèi)容都置為無(wú)效，這樣保證新的進(jìn)程可以使用一個(gè)干凈的TLB；如果實(shí)現(xiàn)了ASID，那么只將這個(gè)進(jìn)程對(duì)應(yīng)的內(nèi)容在TLB中置為無(wú)效就可以的；

(2) 當(dāng)一個(gè)進(jìn)程占用的物理內(nèi)存過(guò)大時(shí)，操作系統(tǒng)可能會(huì)將這個(gè)進(jìn)程中的一部分不經(jīng)常使用頁(yè)寫回到硬盤中，這些頁(yè)在頁(yè)表中對(duì)應(yīng)的映射關(guān)系也應(yīng)該置為無(wú)效，此時(shí)當(dāng)然也需要將I-TLB和D-TLB中對(duì)應(yīng)的內(nèi)容置為無(wú)效，但是，一般操作系統(tǒng)會(huì)盡量避免將存在于TLB中的頁(yè)置為無(wú)效，因?yàn)檫@些頁(yè)在以后很可能會(huì)被繼續(xù)使用。

因此，抽象出來(lái)，對(duì)TLB的管理需要包括的內(nèi)容有如下幾點(diǎn)：

能夠?qū)-TLB和D-TLB的所有表項(xiàng)(entry)置為無(wú)效；

能夠?qū)-TLB和D-TLB中某個(gè)ASID對(duì)應(yīng)的所有表項(xiàng)置為無(wú)效；

能夠?qū)-TLB和D-TLB中某個(gè)VPN對(duì)應(yīng)的表項(xiàng)置為無(wú)效；

不同的處理器有著不同的方法來(lái)對(duì)TLB進(jìn)行管理，本節(jié)以Arm為例進(jìn)行說(shuō)明。在Arm處理器中，使用系統(tǒng)控制協(xié)處理器(Arm稱之為CP15)中的寄存器對(duì)TLB進(jìn)行控制，因此處理器只需要使用訪問(wèn)協(xié)處理器的指令(MCR和MRC)來(lái)向CP15中對(duì)應(yīng)的寄存器寫入相應(yīng)的值，就可以對(duì)TLB進(jìn)行操作。CP15中提供了如下的控制寄存器(以I-TLB和D-TLB分開(kāi)的架構(gòu)為例)。

(1) 用來(lái)管理I-TLB的控制寄存器，主要包括以下幾種：

a. 將TLB中VPN匹配的表項(xiàng)置為無(wú)效的控制寄存器，但是VPN相等并不是唯一的條件，還需要滿足兩個(gè)條件：

①?如果TLB中一個(gè)表項(xiàng)的Global位無(wú)效，則需要ASID也相等；

②?如果TLB中一個(gè)表項(xiàng)的Global位有效，則不需要進(jìn)行ASID比較。這個(gè)控制寄存器如圖14所示。

圖14 控制TLB的寄存器——使用VPN

b. 將TLB中ASID匹配的所有表項(xiàng)置為無(wú)效的控制寄存器，但是TLB中那些Global位有效的表項(xiàng)不會(huì)受影響，這個(gè)控制寄存器如圖15所示。

圖15 控制TLB的寄存器——使用ASID

c. 將TLB中所有未鎖定(unlocked)狀態(tài)的表項(xiàng)置為無(wú)效，那些鎖定(locked)狀態(tài)的表項(xiàng)則不會(huì)受到影響。為了加快處理器中某些關(guān)鍵程序的執(zhí)行時(shí)間，可以將TLB中的某些表項(xiàng)設(shè)為鎖定狀態(tài)，這些內(nèi)容將不會(huì)被替換掉，這樣保證了快速的地址轉(zhuǎn)換。

(2) 用來(lái)管理D-TLB的控制寄存器，他們和I-TLB控制寄存器的工作原理一樣，也可以通過(guò)VPN和ASID對(duì)TLB進(jìn)行控制，此處不再贅述；

(3) 為了便于對(duì)TLB的內(nèi)容進(jìn)行控制和觀察，還需要能夠?qū)LB中的內(nèi)容進(jìn)行讀出和寫入，如圖16所示。

圖16 讀取TLB和寫入TLB

由于TLB中一個(gè)表項(xiàng)的內(nèi)容大于32位，所有使用兩個(gè)寄存器來(lái)對(duì)應(yīng)一個(gè)表項(xiàng)，如圖16中的data0和data1寄存器，在Arm的Cortex A8處理器中，這兩個(gè)寄存器位于協(xié)處理器CP15中。當(dāng)讀取TLB時(shí)，被讀取的表項(xiàng)內(nèi)容會(huì)放到這兩個(gè)寄存器中；而在寫TLB時(shí)，這兩個(gè)寄存器中的內(nèi)容會(huì)寫到TLB中，當(dāng)然，要完成這個(gè)過(guò)程，還需要給出尋址TLB的地址，例如一個(gè)表項(xiàng)個(gè)數(shù)為32的TLB，需要5位的地址來(lái)尋址，這個(gè)地址放在指令中指定的一個(gè)通用寄存器中。一般在調(diào)試處理器的時(shí)候，才會(huì)使用圖15所示的功能。

總結(jié)來(lái)說(shuō)，在Arm處理器中對(duì)TLB的控制是通過(guò)協(xié)處理器來(lái)實(shí)現(xiàn)的，因此只需要使用訪問(wèn)協(xié)處理器的指令(MCR和MRC)就可以了，其實(shí)不僅是對(duì)于TLB，在Arm處理器中對(duì)于存儲(chǔ)器的管理，例如Cache和BTB等部件，都是通過(guò)協(xié)處理器來(lái)實(shí)現(xiàn)的，這種方式雖然比較靈活，但不容易使用。

4.2 Cache的設(shè)計(jì)

4.2.1 Cache的設(shè)計(jì)

Cache如果使用物理地址進(jìn)行尋址，就稱為物理Cache(Physical Cache)，使用TLB和物理Cache一起進(jìn)行工作的過(guò)程如圖17所示。

圖17 Physical Cache

圖18 Virtual Cache

?