一 虛擬存儲器概念

虛擬存儲器(Virtual Memory)的基本思想是對于程序來說，它的程序(code)、數據(data)、堆棧(stack)的總大小可以超過實際物理內存(Physical Memory)的大小，操作系統把當前使用的部分內容放到物理內存中，而把其它未使用的內容放到更下一級存儲器，如硬盤(Disk)或閃存(Flash)上。這樣可以應付隨著應用程序規模的擴大，導致物理內存已經無法容納下這樣的程序。

舉例來說，一個大小為32MB的程序運行在物理內存只有16MB的機器上，操作系統通過選擇，決定各個時刻將程序中一部分放在物理內存中，而將其它的內容放到硬盤中，并在需要的時候在物理內存和硬盤之間交換程序片段，這樣就可以把大小為32MB的程序放到物理內存為16MB的機器上運行。

運用程序是運行在虛擬存儲器空間的，它的大小由處理器的位數決定，例如對于一個32位處理器來說，其地址范圍就是0~0xFFFF_FFFF，也就是4GB，這個范圍就是程序能夠產生的地址范圍，其中的某一個地址就稱為虛擬地址。和虛擬存儲器對應的就是物理存儲器，它是在現實世界中能夠直接使用的存儲器，其中的某一個地址就是物理地址。物理存儲器的大小不能夠超過處理器最大可以尋址的空間，例如32為x86 PC中，不可能使用比4GB更大的物理內存了。

在沒有使用虛擬地址的系統中，處理器輸出的地址會直接送到物理存儲器中，這個過程如圖1所示。

圖1 沒有使用虛擬存儲器的系統

而如果使用了虛擬地址，則處理器輸出的地址就是虛擬地址了，這個地址不會被直接送到物理存儲器中，而是需要先進行地址轉換，因為虛擬地址是沒有辦法直接尋址物理存儲器的，負責地址轉換的部件一般稱為內存管理單元(Memory Manage Unit，MMU)，如圖2所示。

圖2 使用虛擬存儲器的系統

使用虛擬存儲器，每個應用程序總認為它占有處理器的所有地址空間，因此程序可以任意使用處理器的地址資源，不需要考慮地址的限制，由操作系統負責調度，將物理存儲器動態地分配給各個應用程序，將每個程序的虛擬地址轉換為相應的物理地址，使程序能夠正常運行。通過這樣的方式可以保護兩個程序即使使用了同一個虛擬地址，它們也會對應到不同的物理地址，因此可以保護每個程序的內容不會被其它程序隨意改寫。

還可以實現了程序間的共享，例如操作系統提供了打印(printf)函數，第一個程序在地址A使用了printf函數，第二個程序在地址B使用了printf函數，操作系統在地址轉換的時候，會將地址A和地址B轉換為同樣的物理地址，這個物理地址就是printf函數在物理存儲器中的實際地址，這樣就實現了程序共享。

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

可以說，如果一個處理器要支持現代的操作系統，就必須支持虛擬存儲器，它是操作系統一個非常重要的內容，本文重點從硬件層面來講述虛擬存儲器，涉及到頁表(Page Table)、程序保序和TLB等內容。

二 地址轉換

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

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

對于一個虛擬地址(Virtual Address)來說，VA[11:0]用來表示頁內的位置，稱為page offset，VA剩余的部分用來表示哪個頁，也稱為VPN(Virtual Page Number)。

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

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

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

圖3 地址轉換的一個例子

對于從虛擬地址到物理地址的轉換來說，指示對VPN進行操作，頁內的偏移是不需要進行轉化的，也就是說，頁是進行地址轉換的最小單位。為了便于理解，以load指令為例行描述：

Load R2, 5[R1]; //假設R1的值為0

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

對于圖3中，如果虛擬地址是32780，則落在了page8范圍內，而page8還并沒有一個有效的映射，即此時page8的內容沒有存在于物理內存中，而是存在于硬盤中。

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

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

2.1 單級頁表

在使用虛擬存儲器的系統中，都是使用一張表格來存儲從虛擬地址到物理地址(實際上是VPN到PFN)的對應關系，這個表格稱為頁表(Page Table，PT)。

這個表格一般是放在物理內存中，使用虛擬地址來尋址，表格中被尋址到的內容就是這個虛擬地址對應的物理地址。每個程序都有自己的頁表，用來將這個程序中的虛擬地址映射到物理內存中的某個地址，為了指示一個程序的頁表在物理內存中的位置，在處理器中一般都會包括一個寄存器，用來存放當前運行程序的頁表在物理內存中的起始地址，這個寄存器稱為頁表寄存器(Page Table Register，PTR)，每次操作系統將一個程序調入物理內存中執行的時候，就會將寄存器PTR設置好，當然，上面的這種機制可以工作的前提是頁表位于物理內存中一片連續的地址空間內。

圖4表示了如何使用PTR從物理內存中定位到一個頁表，并使用虛擬地址來尋址頁表，從而找到對應的物理地址的過程。其實，使用PTR和虛擬地址共同來尋址頁表，這就相當于使用它們兩個共同組成一個地址，使用這個地址來尋址物理內存。

圖4中仍然假設每個頁的大小是4KB，使用PTR和虛擬地址共同來尋址頁表，找到對應的表項(entry)，當這個表項對應的有效位(valid)為1時，就表示這個虛擬地址所在的4KB空間已經被操作系統映射到了物理內存中，可以直接從物理內存中找到這個虛擬地址對應的數據，其實，這時候訪問當前頁內任意的地址，就是訪問物理內存中被映射的那個4KB的空間了。

相反，如果頁表中這個被尋址的表項對應的有效位是0，則表示這個虛擬地址對應的4KB空間還沒有被操作系統映射到物理內存中，則此時就產生了Page Fault類型的異常，需要操作系統從更下一級的存儲器(例如硬盤或閃存)將這個頁對應的4KB內容搬移到物理內存中。

圖4 通過頁表進行地址轉換

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

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

需要注意的是，頁表的結構是不同于cache的，在頁表中包括了所有VPN的映射關系，所以可以直接使用VPN對頁表進行尋址，而不需要使用Tag。

在處理器中，一個程序對應的頁表，連同PC和通用寄存器一起，組成了這個程序的狀態，如果在當前程序執行的時候，想要另外一個程序使用這個處理器，就需要將當前程序的狀態進行保存，這樣就可以在一段時間之后將這個程序進行恢復，從而使這個程序可以繼續執行，在操作系統中，通常將這樣的程序稱為進程(process)，當一個進程被處理器執行的時候，稱這個進程是活躍的(active)，否則就稱之為不活躍(inactive)。操作系統通過將一個進程的狀態加載到處理器中，就可以使這個進程進入活躍的狀態。

可以說，進程是一個動態的概念，當一個程序只是放在硬盤中，并沒有被處理器執行的時候，它只是一個由一條條指令組成的靜態文件，只有當這個程序被處理器執行時，例如用戶打開了一個程序，此時才有了進程，需要操作系統為其分配物理內存中的空間，創建頁表和堆棧等，這時候一個靜態的程序就變為了動態的進程，這個進程可能是一個，也可能是多個，這取決于程序本身，當然進程是有生命期的，一旦用戶關閉了這個程序，進程也就不存在了，它所占據的物理內存也會被釋放掉。

一個進程的頁表指定了它能夠在物理內存中訪問的地址空間，這個頁表當然也是位于內存中的，在一個進程進行狀態保存的時候，其實并不需要保存整個的頁表，只需要將這個頁表對應的PTR進行保存即可。因為每個進程都擁有全部的虛擬存儲器空間，因此不同的進程肯定會存在相同的虛擬地址，操作系統需要負責將這些不同的進程分配到物理內存中不同的地方，并將這些映射(mapping)信息更新到頁表中(使用store指令就可以完成這個任務)，這樣不同的進程使用的物理內存就不會產生沖突了。

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

可以采用很多方法來減少一個進程的頁表對于存儲空間的需求，最常用的方法是多級頁表(Hierarchical Page Table)，這種方法可以減少頁表對于物理存儲空間的占用，而且非常容易使用硬件實現，與之對應的，本節所講述的頁表就稱為單級頁表(Single Page Table)，也被稱為線性頁表(Linear Page Table)。

2.2 多級頁表

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

圖5 兩級頁表

這樣，要得到一個虛擬地址對應的數據，首先需要訪問第一級頁表，得到這個虛擬地址所屬的第二級頁表的基地址，然后再去第二級頁表中才可以得到這個虛擬地址對應的物理地址，這時候就可以在物理內存中取出相應的數據。

舉例來說，對于一個32位虛擬地址、頁大小為4KB的系統來說，如果采用線性頁表，則頁表的表項個數是220，將其分為1024(210)等份，每個等份就是一個第二級頁表，共有1024個第二級頁表，對應著第一級頁表的1024個表項。也就是說，第一級頁表需要10位地址進行尋址。每個二級頁表中，表項的個數是220/210=210個，也需要10位地址才能尋址第二級頁表，如圖6所示過程的示意圖。

在圖6中，一個頁表中的表項簡稱為PTE(Page Table Entry)，當操作系統創建一個進程時，就在物理內存中為這個進程找到一塊連續的4KB空間(4Bx210=4KB)，存放這個進程的第一級頁表，并且將第一級頁表在物理內存中的起始地址放到PTR寄存器中。通常這個寄存器都是處理器中的一個特殊寄存器，例如ARM中的TTB寄存器，x86中的CR3寄存器等。隨著這個進程的執行，操作系統會逐步在物理內存中創建第二級頁表，每次創建一個第二級頁表，操作系統就要將它的起始地址放到第一級頁表對應的表項中，如表1所示為一個進程送出的虛擬地址和第一級頁表、第二級頁表的對應關系。

圖6 使用兩級頁表進行地址轉換的一個例子

表1 虛擬地址和第一級頁表、第二級頁表的關系

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

當虛擬地址的p1部分不發生變化，只是p2部分的變化范圍在0x000-0x3FF之內時，此時不需要創建新的第二級頁表。每當虛擬地址中的p2部分發生變化，就表示要使用一個新的頁，操作系統將這個新的頁從下級存儲器中(如硬盤)取出來并放到物理內存中，然后將這個頁在物理內存中的起始地址填充到第二級頁表對應的PTE中(由虛擬地址的p2部分指定)。至于虛擬地址的頁內偏移(即Offset)部分，只是用來在一個頁的內部找到對應的數據，它不會影響第一級和第二級頁表的創建。

總體來看，當處理器開始執行一個程序時，就會把第一級頁表放到物理內存中，直到整個程序被關閉為止，因此第一級頁表所占用的4KB存儲空間是不可避免的，而第二級頁表是否在物理內存當中，則是根據一個程序當中虛擬地址的值來決定，操作系統會逐個地創建第二級頁表。事實上，伴隨著一個頁表被放入到物理內存中，必然會有第二級頁表中的一個PTE被建立，這個PTE會被寫入該頁在物理內存中的起始地址，如果這個頁對應的第二級頁表還不存在，那么就需要操作系統建立一個新的第二級頁表。

多級頁表有個優點就是容易擴展，當處理器的位數增加時，可以通過增加級數的方式來減少頁表對于物理內存的占用。如圖7所示。

圖7 使用多級頁表進行地址轉換

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

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

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

圖8 Page In和Page Out

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

2.3?Page Fault

如果一個進程中的虛擬地址在訪問頁表時，發現對應的PTE中，有效位(valid)為0，這就表示這個虛擬地址所屬的頁還沒有被放到物理內存中，因此在頁表中就沒有存儲這個頁的映射關系，這時候就說發生了Page Fault，需要從下級存儲器(例如硬盤)將這個頁取出來，放到物理內存中，并將這個頁在物理內存中的起始地址寫到頁表中。Page Fault是異常(exception)的一種，通常它的處理過程不是由硬件完成的，而是由軟件完成的，確切的說，是由操作系統完成的，因為操作系統也是軟件。

在有Page Fault時，處理器會跳轉到這個異常處理程序的入口地址，異常處理程序會根據某種替換算法，從物理內存中找到一個空閑的地方，將需要的頁從硬盤中搬移進來，并將這個新的對應關系寫到頁表中相應的PTE內。

需要注意的是，直接使用虛擬地址并不能知道一個頁位于硬盤的哪個位置，也需要一個機制來記錄一個進程的每個頁位于硬盤中的位置。

通常，操作系統會在硬盤中為一個進程的所有頁開辟一塊空間，這就是之前說過的swap空間，在這個空間中存儲一個進程所有的頁，操作系統在開辟swap空間的同時，還會使用一個表格來記錄每個頁在硬盤中存儲的位置，這個表格的結構其實和頁表是一樣的，它可以單獨存在，從理論上來講也可以和頁表合并在一起，如圖9所示。

圖9 同一個頁表中記錄了所有的內容

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

雖然圖9中，映射到物理內存的頁表和映射到硬盤的頁表可以放到一起，但在實際當中，物理上它們是分開放置的，因為不管一個頁是不是在物理內存中，操作系統都必須記錄一個進程的所有頁在硬盤中的位置，因此需要單獨地使用一個表格來記錄它。

物理內存相當于是硬盤的Cache，因為對一個程序來說，它的所有內容其實都存在于硬盤中，只有最近被使用的一部分內容存在物理內存中，這樣符合Cache的特征。因為一個程序的某些內容既存在于硬盤中，也存在于物理內存中，當物理內存中某個地址的內容被改變時(例如執行一條store指令，改變了程序中的某個變量)，對于這個地址來說，在硬盤中的存儲的內容就過時了，這種情況再Cache中也出現過，有兩種處理方法。

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

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

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

既然在虛擬存儲器的系統中采用了寫回的方式，當發生Page Fault并且物理內存已經沒有空間時，操作系統需要從其中找到一個頁進行替換，如果這個頁的某些內容被修改過，那么在覆蓋這個頁之前，需要先將它的內容寫回到硬盤中，然后才能進行覆蓋。

為了支持這個功能，需要記錄每個頁是否在物理內存中被修改過，通常是在頁表的每個PTE中增加一個臟(dirty)的狀態位，當一個頁的某個地址被寫入時，這個臟的狀態位會被置為1。

當操作系統需要將一個頁進行替換之前，會首先去頁表中檢查它對應的PTE臟狀態位，如果為1，則需要先將這個頁的內容寫回到硬盤中；如果為0，則表示這個頁從來沒有被修改過，那么就可以直接將其覆蓋了，因為在硬盤中還保存著這個頁的內容。

從一個時間點來看物理內存，會存在很多的頁處于臟的狀態，這些頁都被寫入了新的內容，當然，一旦這些臟的頁被寫回到硬盤中，它們在物理內存中也就不再是臟的狀態了。

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

這種方式是近似的LRU算法，被大多數操作系統所使用，由于使用了硬件來實現“使用位”，所以操作系統的任務量被大大地減輕了。

總結來說，為了處理Page Fault，處理器在硬件上需要提供的支持有如下幾種：

在發現Page Fault時，能夠產生對應類型的異常，并且能夠跳轉到它的異常處理程序的入口地址；

當要寫物理內存時，例如執行了store指令，需要硬件將頁表中對應PTE的臟狀態位置為1；

當訪問物理內存時，例如執行了store指令，需要硬件將頁表中對應PTE的“使用位”置為1，表示這個頁最近被訪問過。

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

因此，本節現在為止，頁表中每個PTE的內容如圖10所示。

圖10 頁表中包括的內容

三 程序保護

在現代處理器運行的環境中，存在著操作系統和許多的用戶進程，操作系統和用戶對于存儲空間需要有不同的訪問權限，因此可以在頁表上來實現這個功能，因為要訪問存儲器的內容必須要經過頁表，所以在頁表中對各個頁規定不同的訪問權限是很自然的事。

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

在Arm處理器中，采用了兩級頁表的方法，第二級頁表的每個PTE中都有一個AP部分，在Arm v7架構中，AP部分直接決定了每個頁的訪問權限，如表2所示。

表2?Arm中每個頁的權限管理

在Arm v7架構中，規定處理器可以工作在User模式和Privileged模式，在Privileged模式下，可以訪問處理器內部所有的資源，因此操作系統會運行在這種模式下，而普通的用戶程序則是運行在User模式下。在表2中，AP[2:0]位于PTE中，通過它，第二級頁表可以控制每個頁的訪問權限，這樣可以使一個頁對于不同的進程有著不同的訪問權限。

既然在頁表中規定了每個頁的訪問權限，那么一旦發現當前的訪問不符合規定，例如一個頁不允許用戶進程訪問，但是當前的用戶進程卻要讀取這個頁的某個地址，這樣就發生了非法訪問，會產生給異常(exception)來通知處理器，使處理器跳轉到異常處理程序中，這個處理程序一般是操作系統的一部分，由操作系統決定如何處理這種非法的訪問，例如操作系統可以終止當前的用戶進程，以防止惡意的程序對系統造成的破壞，圖11為地址轉換的過程中加入了權限檢查的過程，注意此時在PTE中多了用來進行權限控制的AP部分。

圖11 加入程序保護之后的地址轉換

當然如果采用了兩級頁表的結構，那么圖11只給出了第二級頁表的工作過程，事實上在第一級頁表中葉可以進行權限控制，而且可以控制更大的地址范圍。

舉例來說，在前文講述的頁大小為4KB的系統中，第一級頁表中每個PTE都可以映射一個完整的第二級頁表，也就是4KBx1024=4MB的地址范圍。

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

如果存在D-Cache的系統中，處理器送出的虛擬地址經過頁表轉換為物理地址之后，其實并不會直接去訪問物理內存，而是先訪問D-Cache。

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

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

到本小結為止，總結起來，在頁表中的每個PTE都包括如下的內容：

PFN，表示虛擬地址對應的物理地址的頁號； ?

Valid，表示對應的頁當前是否在物理內存中；

Dirty，表示對應頁中的內容是否被修改過；

Use，表示對應頁中的內容是否最近被訪問過；

AP，訪問權限控制，表示操作系統和用戶程序對當前這個頁的訪問權限；

Cacheable，表示對應的頁是否允許被緩存。 ?

四 加入TLB和Cache

4.1 TLB的設計

4.1.1 概述

對兩級頁表來說，需要訪問兩次物理內存才可以得到虛擬地址對應的物理地址，而物理內存的運行速度相對于處理器本身來說，有幾十倍的差距，因此整體下來速度很慢的。此時可以借鑒Cache的設計理念，使用一個速度比較快的緩存，將頁表中最近使用的PTE緩存下來，因為它們在以后還可能繼續使用，尤其對于取指令來說，考慮到程序本身的串行性，會順序地從一個頁內取指令，此時將PTE緩存起來是大有益處的，能夠加快一個頁內4KB內容的地址轉換速度。

由于歷史原因，緩存PTE的部件一般不稱為Cache，而是稱之為TLB(Translation Lookaside buffer)，在TLB中存儲了頁表中最近被使用過的PTE，從本質上來講，TLB就是頁表的Cache。但是TLB又不同于一般的cache，它只有時間相關性(Temporal Locality)，也就是說，現在訪問的頁，很有可能在以后繼續被訪問，至于空間相關性(Temporal Locality)，TLB并沒有明顯的規律，因為在一個頁內有很多情況，都可能使程序跳轉到其他不相鄰的頁中取指令或數據，也就是說，雖然當前在訪問一個頁，但未必會訪問它相鄰的頁，正因為如此，Cache設計中很多的優化方法，例如預取(prefetching)，是沒有辦法應用于TLB中的。

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

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

(1) 在頁表中找到的PTE是有效的，即這個虛擬地址所屬的頁存在于物理內存中，那么就可以直接從頁表中找到對應的物理地址，使用它來尋址物理內存從而得到需要的數據，同時將頁表中的這個PTE寫回到TLB中，供以后使用；

(2) 在頁表中找到的PTE是無效的，即這個虛擬地址所屬的頁不在物理內存中，造成這種現象的原因很多，例如這個頁在以前沒有被使用過，或者這個頁已經被交換到了硬盤中等，此時就應該產生Page Fault類型的異常，通知操作系統來處理這個情況，操作系統需要從硬盤中將相應的頁搬移到物理內存中，將它在物理內存中的首地址放到頁表內對應的PTE中，并將這個PTE的內容寫到TLB中。

圖12 TLB內容

在圖12中，因為TLB采用了全相連的方式，所以相比頁表多了一個Tag的項，它保存了虛擬地址的VPN，用來對TLB進行匹配查找，TLB中其它的項完全來自于頁表，每當發生TLB缺失時，將PTE從頁表中搬移到TLB內。

4.1.2 TLB缺失

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

(1) 虛擬地址對應的頁不在物理內存中，所以頁表也沒有對應的PTE，自然TLB中也不可能有的；

(2) 虛擬地址對應的頁在物理內存中，所以頁表中有對應的PTE，但這個PTE還沒有放到TLB中，這種情況也經常發生，畢竟TLB的內容遠小于頁表；

(3) 虛擬地址對應的頁在物理內存中，所以頁表中有對應的PTE，這個PTE也曾存在于TLB中，但后來被替換出去了，現在這個也又重新使用了，此時這個PTE就存在于頁表中，但不在TLB內。

解決TLB缺失的本質就是要從頁表中找到對應的映射關系，并將其寫回到TLB內，這個過程稱為Page Table Walk，可以使用硬件狀態機來完成這個事情，也可以使用軟件來做這個事情，各有優缺點，各自工作流程如下：

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

對于超標量處理器，對異常處理時，會將流水線中所有的指令抹掉，這樣會產生一些性能上缺失，但可以實現靈活的TLB替換算法，MIPS和Alpha處理器一般采用這種方法處理TLB缺失。為了防止在處理TLB缺失的異常處理程序再次發生TLB缺失，一般將這段異常處理程序放到一個不需要進行地址轉換的預取，這樣就可以直接使用物理地址來取指令和數據，避免再次發生TLB缺失的情況。軟件處理TLB缺失的過程如圖13所示。

圖13 軟件處理TLB miss的流程

(2) 硬件實現Page Table Walk，硬件實現一般由內存管理單元(MMU)完成，當發現TLB缺失時，MMU自動使用當前的虛擬地址去尋址物理內存中的頁表，前面說過，多級頁表的最大優點就是容易使用硬件進行查找，只需要使用一個狀態機逐級進行查找就可以，如果從頁表中找到的PTE是有效的，那么將它寫回到TLB中，這個過程全部由硬件自動完成的。

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

對于組相連或全相連結構的TLB，當一個新的PTE被寫到TLB中時，如果當前TLB中沒有空閑的位置了，那么就要考慮將其中的一個表項(entry)進行替換。理論上說，Cache中使用的替換方法在TLB里也可以，例如最少使用算法(LRU)，但是實際上對于TLB來說，隨機替換(Random)算法可以是一種比較合適的方法，通常可以采用時鐘算法(Clock Algorithm)來實現近似的隨機。

4.1.3 TLB的寫入

當一個頁從硬盤搬移到物理內存之后，操作系統需要知道這個頁中的內容在物理內存中是否被改變過。如果沒有被改變過，當這個頁需要被替換時可以直接進行覆蓋，因為總能從硬盤中找到這個頁的備份；如果已經被修改過了，需要先將它從物理內存中寫回到硬盤，因此需要在頁表中，對每個被修改的頁加以標記，稱為臟狀態位(dirty)。當物理內存中的一個頁要被替換時，需要首先檢查它在頁表中對應PTE的臟狀態位，如果它是1，那么就需要先將這個頁寫回到硬盤中，然后才能將其覆蓋。

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

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

雖然對于TLB和D-Cache都是Cache，但在操作系統對物理內存進行頁表替換時，所采取的的方法措施有點不同的，TLB中存在的頁表在物理內存中不會替換，D-Cache中存在數據所對應地址的頁表在物理內存中仍然會被替換，所以此時也需要將D-Cache的內容clean掉，切記兩者的不同之處。

4.1.4 對TLB進行控制

如果由于某些原因導致一個頁的映射關系在頁表中不存在了，那么它在TLB中也不應該存在，而操作系統在一些情況下，會把某些頁的映射關系從頁表中抹掉，例如：

(1) 當一個進程結束時，這個進程的指令(code)、數據(data)和堆棧(stack)所占據的頁表就需要變為無效，這樣也就釋放了這個進程所占據的物理內存空間。

但是，此時在I-TLB中可能存在這個進程的程序(code)對應的PTE，在D-TLB中可能還存在著這個進程的數據和堆棧的PTE，此時就需要將I-TLB和D-TLB中和這個進程相關的所有內容置為無效，如果沒有使用ASID，最簡單的做法就是將I-TLB和D-TLB中的全部內容都置為無效，這樣保證新的進程可以使用一個干凈的TLB；如果實現了ASID，那么只將這個進程對應的內容在TLB中置為無效就可以的；

(2) 當一個進程占用的物理內存過大時，操作系統可能會將這個進程中的一部分不經常使用頁寫回到硬盤中，這些頁在頁表中對應的映射關系也應該置為無效，此時當然也需要將I-TLB和D-TLB中對應的內容置為無效，但是，一般操作系統會盡量避免將存在于TLB中的頁置為無效，因為這些頁在以后很可能會被繼續使用。

因此，抽象出來，對TLB的管理需要包括的內容有如下幾點：

能夠將I-TLB和D-TLB的所有表項(entry)置為無效；

能夠將I-TLB和D-TLB中某個ASID對應的所有表項置為無效；

能夠將I-TLB和D-TLB中某個VPN對應的表項置為無效；

不同的處理器有著不同的方法來對TLB進行管理，本節以Arm為例進行說明。在Arm處理器中，使用系統控制協處理器(Arm稱之為CP15)中的寄存器對TLB進行控制，因此處理器只需要使用訪問協處理器的指令(MCR和MRC)來向CP15中對應的寄存器寫入相應的值，就可以對TLB進行操作。CP15中提供了如下的控制寄存器(以I-TLB和D-TLB分開的架構為例)。

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

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

①?如果TLB中一個表項的Global位無效，則需要ASID也相等；

②?如果TLB中一個表項的Global位有效，則不需要進行ASID比較。這個控制寄存器如圖14所示。

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

b. 將TLB中ASID匹配的所有表項置為無效的控制寄存器，但是TLB中那些Global位有效的表項不會受影響，這個控制寄存器如圖15所示。

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

c. 將TLB中所有未鎖定(unlocked)狀態的表項置為無效，那些鎖定(locked)狀態的表項則不會受到影響。為了加快處理器中某些關鍵程序的執行時間，可以將TLB中的某些表項設為鎖定狀態，這些內容將不會被替換掉，這樣保證了快速的地址轉換。

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

(3) 為了便于對TLB的內容進行控制和觀察，還需要能夠將TLB中的內容進行讀出和寫入，如圖16所示。

圖16 讀取TLB和寫入TLB

由于TLB中一個表項的內容大于32位，所有使用兩個寄存器來對應一個表項，如圖16中的data0和data1寄存器，在Arm的Cortex A8處理器中，這兩個寄存器位于協處理器CP15中。當讀取TLB時，被讀取的表項內容會放到這兩個寄存器中；而在寫TLB時，這兩個寄存器中的內容會寫到TLB中，當然，要完成這個過程，還需要給出尋址TLB的地址，例如一個表項個數為32的TLB，需要5位的地址來尋址，這個地址放在指令中指定的一個通用寄存器中。一般在調試處理器的時候，才會使用圖15所示的功能。

總結來說，在Arm處理器中對TLB的控制是通過協處理器來實現的，因此只需要使用訪問協處理器的指令(MCR和MRC)就可以了，其實不僅是對于TLB，在Arm處理器中對于存儲器的管理，例如Cache和BTB等部件，都是通過協處理器來實現的，這種方式雖然比較靈活，但不容易使用。

4.2 Cache的設計

4.2.1 Cache的設計

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

圖17 Physical Cache

圖18 Virtual Cache

?