內(nèi)存管理：程序是如何被優(yōu)雅的裝載到內(nèi)存中

點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)

粉絲福利：小編會(huì)從今天留言的小伙伴中隨機(jī)抽贈(zèng)送8.88元現(xiàn)金紅包。娛樂抽獎(jiǎng)，大家隨緣積極參與啦，給生活一點(diǎn)小幸運(yùn)~感謝大家的支持

內(nèi)存作為計(jì)算機(jī)中一項(xiàng)比較重要的資源，它的主要作用就是解決CPU和磁盤之間速度的鴻溝，但是由于內(nèi)存條是需要插入到主板上的，因此對(duì)于一臺(tái)計(jì)算機(jī)來說，由于物理限制，它的內(nèi)存不可能無限大的。我們知道我們寫的代碼最終是要從磁盤被加載到內(nèi)存中的，然后再被CPU執(zhí)行，不知道你有沒有想過，為什么一些大型游戲大到10幾G，卻可以在只有8G內(nèi)存的電腦上運(yùn)行？甚至在玩游戲期間，我們還可以聊微信、聽音樂...，這么多進(jìn)程看著同時(shí)在運(yùn)行，它們?cè)趦?nèi)存中是如何被管理的？帶著這些疑問我們來看看計(jì)算系統(tǒng)內(nèi)存管理那些事。

內(nèi)存的交換技術(shù)

如果我們的內(nèi)存可以無限大，那么我們擔(dān)憂的問題就不會(huì)存在，但是實(shí)際情況是往往我們的機(jī)器上會(huì)同時(shí)運(yùn)行多個(gè)進(jìn)程，這些進(jìn)程小到需要幾十兆內(nèi)存，大到可能需要上百兆內(nèi)存，當(dāng)許許多多這些進(jìn)程想要同時(shí)加載到內(nèi)存的時(shí)候是不可能的，但是從我們用戶的角度來看，似乎這些進(jìn)程確實(shí)都在運(yùn)行呀，這是怎么回事？

這就引入要說的交換技術(shù)了，從字面的意思來看，我想你應(yīng)該猜到了，它會(huì)把某個(gè)內(nèi)存中的進(jìn)程交換出去。當(dāng)我們的進(jìn)程空閑的時(shí)候，其他的進(jìn)程又需要被運(yùn)行，然而很不幸，此時(shí)沒有足夠的內(nèi)存空間了，這時(shí)候怎么辦呢？似乎剛剛那個(gè)空閑的進(jìn)程有種占著茅坑不拉屎的感覺，于是可以把這個(gè)空閑的進(jìn)程從內(nèi)存中交換到磁盤上去，這時(shí)候就會(huì)空出多余的空間來讓這個(gè)新的進(jìn)程運(yùn)行，當(dāng)這個(gè)換出去的空閑進(jìn)程又需要被運(yùn)行的時(shí)候，那么它就會(huì)被再次交換進(jìn)內(nèi)存中。通過這種技術(shù)，可以讓有限的內(nèi)存空間運(yùn)行更多的進(jìn)程，進(jìn)程之間不停來回交換，看著好像都可以運(yùn)行。如圖所示，一開始進(jìn)程A被換入內(nèi)存中，所幸還剩余的內(nèi)存空間比較多，然后進(jìn)程B也被換入內(nèi)存中，但是剩余的空間比較少了，這時(shí)候進(jìn)程C想要被換入到內(nèi)存中，但是發(fā)現(xiàn)空間不夠了，這時(shí)候會(huì)把已經(jīng)運(yùn)行一段時(shí)間的進(jìn)程A換到磁盤中去，然后調(diào)入進(jìn)程C。

內(nèi)存碎片

通過這種交換技術(shù)，交替的換入和換出進(jìn)程可以達(dá)到小內(nèi)存可以運(yùn)行更多的進(jìn)程，但是這似乎也產(chǎn)生了一些問題，不知道你發(fā)現(xiàn)了沒有，在進(jìn)程C換入進(jìn)來之后，在進(jìn)程B和進(jìn)程C之間有段較小的內(nèi)存空間，并且進(jìn)程B之上也有段較小的內(nèi)存空間，說實(shí)話，這些小空間可能永遠(yuǎn)沒法裝載對(duì)應(yīng)大小的程序，那么它們就浪費(fèi)了，在某些情況下，可能會(huì)產(chǎn)生更多這種內(nèi)存碎片。

如果想要節(jié)約內(nèi)存，那么就得用到內(nèi)存緊湊的技術(shù)了，即把所有的進(jìn)程都向下移動(dòng)，這樣所有的碎片就會(huì)連接在一起變成一段更大的連續(xù)內(nèi)存空間了。但是這個(gè)移動(dòng)的開銷基本和當(dāng)前內(nèi)存中的活躍進(jìn)程成正比，據(jù)統(tǒng)計(jì)，一臺(tái)16G內(nèi)存的計(jì)算機(jī)可以每8ns復(fù)制8個(gè)字節(jié)，它緊湊全部的內(nèi)存大概需要16s，所以通常不會(huì)進(jìn)行緊湊這個(gè)操作，因?yàn)樗馁M(fèi)的CPU時(shí)間還是比較大的。

動(dòng)態(tài)增長(zhǎng)

其實(shí)上面說的進(jìn)程裝載算是比較理想的了，正常來說，一個(gè)進(jìn)程被創(chuàng)建或者被換入的時(shí)候，它占用多大的空間就分配多大的內(nèi)存，但是如果我們的進(jìn)程需要的空間是動(dòng)態(tài)增長(zhǎng)的，那就麻煩了，比如我們的程序在運(yùn)行期間的for循環(huán)可能會(huì)利用到某個(gè)臨時(shí)變量來存放目標(biāo)數(shù)據(jù)（例如以下變量a，隨著程序的運(yùn)行是會(huì)越來越大的）：

var?a?[]int64
for?i:=?0;i?<=?1000000;i++{
??if?i%2?==?0{
???a?=?append(a,i)?//a是不斷增大的
??}
}

當(dāng)需要增長(zhǎng)的時(shí)候：

1. 如果進(jìn)程的鄰居是空閑區(qū)那還好，可以把該空閑區(qū)分配給進(jìn)程
2. 如果進(jìn)程的鄰居是另一個(gè)進(jìn)程，那么解決的辦法只能把增長(zhǎng)的進(jìn)程移動(dòng)到一個(gè)更大的空閑內(nèi)存中，但是萬一沒有更大的內(nèi)存空間，那么就要觸發(fā)換出，把一個(gè)或者多個(gè)進(jìn)程換出去來提供更多的內(nèi)存空間，很明顯這個(gè)開銷不小。

為了解決進(jìn)程空間動(dòng)態(tài)增長(zhǎng)的問題，我們可以提前多給一些空間，比如進(jìn)程本身需要10M，我們多給2M，這樣如果進(jìn)程發(fā)生增長(zhǎng)的時(shí)候，可以利用這2M空間，當(dāng)然前提是這2M空間夠用，如果不夠用還是得觸發(fā)同樣的移動(dòng)、換出邏輯。

空閑的內(nèi)存如何管理

前面我們說到內(nèi)存的交換技術(shù)，交換技術(shù)的目的是騰出空閑內(nèi)存來，那么我們是如何知道一塊內(nèi)存是被使用了，還是空閑的？因此需要一套機(jī)制來區(qū)分出空閑內(nèi)存和已使用內(nèi)存，一般操作系統(tǒng)對(duì)內(nèi)存管理的方式有兩種：位圖法和鏈表法。

位圖法

先說位圖法，沒錯(cuò)，位圖法采用比特位的方式來管理我們的內(nèi)存，每塊內(nèi)存都有位置，我們用一個(gè)比特位來表示：

1. 如果某塊內(nèi)存被使用了，那么比特位為1
2. 如果某塊內(nèi)存是空閑的，那么比特位為0

這里的某塊內(nèi)存具體是多大得看操作系統(tǒng)是如何管理的，它可能是一個(gè)字節(jié)、幾個(gè)字節(jié)甚至幾千個(gè)字節(jié)，但是這些不是重點(diǎn)，重點(diǎn)是我們要知道內(nèi)存被這樣分割了。

位圖法的優(yōu)點(diǎn)就是清晰明確，某個(gè)內(nèi)存塊的狀態(tài)可以通過位圖快速的知道，因?yàn)樗臅r(shí)間復(fù)雜度是O(1)，當(dāng)然它的缺點(diǎn)也很明顯，就是需要占用太多的空間，尤其是管理的內(nèi)存塊越小的時(shí)候。更糟糕的是，進(jìn)程分配的空間不一定是內(nèi)存塊的整數(shù)倍，那么最后一個(gè)內(nèi)存塊中一定是有浪費(fèi)的。

如圖，進(jìn)程A和進(jìn)程B都占用的最后一個(gè)內(nèi)存塊的一部分，那么對(duì)于最后一個(gè)內(nèi)存塊，它的另一部分一定是浪費(fèi)的。

鏈表法

相比位圖法，鏈表法對(duì)空間的利用更加合理，我相信你應(yīng)該已經(jīng)猜到了，鏈表法簡(jiǎn)單理解就是把使用的和空閑的內(nèi)存用鏈表的方式連接起來，那么對(duì)于每個(gè)鏈表的元素節(jié)點(diǎn)來說，他應(yīng)該具備以下特點(diǎn)：

1. 應(yīng)該知道每個(gè)節(jié)點(diǎn)是空閑的還是被使用的
2. 每個(gè)節(jié)點(diǎn)都應(yīng)該知道當(dāng)前節(jié)點(diǎn)的內(nèi)存的開始地址和結(jié)束地址

針對(duì)這些特點(diǎn)，最終內(nèi)存對(duì)應(yīng)的鏈表節(jié)點(diǎn)大概是這樣的：

p代表這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的內(nèi)存空間是被使用的，H代表這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的內(nèi)存空間是空閑的，start代表這塊內(nèi)存空間的開始地址，length代表的是這塊內(nèi)存的長(zhǎng)度，最后還有指向鄰居節(jié)點(diǎn)的pre和next指針。

因此對(duì)于一個(gè)進(jìn)程來說，它與鄰居的組合有四種：

1. 它的前后節(jié)點(diǎn)都不是空閑的
2. 它的前一個(gè)節(jié)點(diǎn)是空閑的，它的后一個(gè)節(jié)點(diǎn)也不是空閑的
3. 它的前一個(gè)節(jié)點(diǎn)不是空閑的，它的后一個(gè)節(jié)點(diǎn)是空閑的
4. 它的前后節(jié)點(diǎn)都是空閑的

當(dāng)一個(gè)內(nèi)存節(jié)點(diǎn)被換出或者說進(jìn)程結(jié)束后，那么它對(duì)應(yīng)的內(nèi)存就是空閑的，此時(shí)如果它的鄰居也是空閑的，就會(huì)發(fā)生合并，即兩塊空閑的內(nèi)存塊合并成一個(gè)大的空閑內(nèi)存塊。

ok，通過鏈表的方式把我們的內(nèi)存給管理起來了，接下來就是當(dāng)創(chuàng)建一個(gè)進(jìn)程或者從磁盤換入一個(gè)進(jìn)程的時(shí)候，如何從鏈表中找到一塊合適的內(nèi)存空間？

首次適應(yīng)算法

其實(shí)想要找到空閑內(nèi)存空間最簡(jiǎn)單的辦法就是順著鏈表找到第一個(gè)滿足需要內(nèi)存大小的節(jié)點(diǎn)，如果找到的第一個(gè)空閑內(nèi)存塊和我們需要的內(nèi)存空間是一樣大小的，那么就直接利用，但是這太理想了，現(xiàn)實(shí)情況大部分可能是找到的第一個(gè)目標(biāo)內(nèi)存塊要比我們的需要的內(nèi)存空間要大一些，這時(shí)候呢，會(huì)把這個(gè)空閑內(nèi)存空間分成兩塊，一塊正好使用，一塊繼續(xù)充當(dāng)空閑內(nèi)存塊。

一個(gè)需要3M內(nèi)存的進(jìn)程，會(huì)把4M的空間拆分成3M和1M。

下次適配算法

和首次適應(yīng)算法很相似，在找到目標(biāo)內(nèi)存塊后，會(huì)記錄下位置，這樣下次需要再次查找內(nèi)存塊的時(shí)候，會(huì)從這個(gè)位置開始找，而不用從鏈表的頭節(jié)點(diǎn)開始尋找，這個(gè)算法存在的問題就是，如果標(biāo)記的位置之前有合適的內(nèi)存塊，那么就會(huì)被跳過。

一個(gè)需要2M內(nèi)存的進(jìn)程，在5這個(gè)位置找到了合適的空間，下次如果需要這1M的內(nèi)存會(huì)從5這個(gè)位置開始，然后會(huì)在7這個(gè)位置找到合適的空間，但是會(huì)跳過1這個(gè)位置。

最佳適配算法

相比首次適應(yīng)算法，最佳適配算法的區(qū)別就是：不是找到第一個(gè)合適的內(nèi)存塊就停止，而是會(huì)繼續(xù)向后找，并且每次都可能要檢索到鏈表的尾部，因?yàn)樗业阶詈线m那個(gè)內(nèi)存塊，什么是最合適的內(nèi)存塊呢？如果剛好大小一致，則一定是最合適的，如果沒有大小一致的，那么能容得下進(jìn)程的那個(gè)最小的內(nèi)存塊就是最合適的，可以看出最佳適配算法的平均檢索時(shí)間相對(duì)是要慢的，同時(shí)可能會(huì)造成很多小的碎片。

假設(shè)現(xiàn)在進(jìn)程需要2M的內(nèi)存，那么最佳適配算法會(huì)在檢索到3號(hào)位置（3M）后，繼續(xù)向后檢索，最終會(huì)選擇5號(hào)位置的空閑內(nèi)存塊。

最差適配算法

我們知道最佳適配算法中最佳的意思是找到一個(gè)最貼近真實(shí)大小的空閑內(nèi)存塊，但是這會(huì)造成很多細(xì)小的碎片，這些細(xì)小的碎片一般情況下，如果沒有進(jìn)行內(nèi)存緊湊，那么大概率是浪費(fèi)的，為了避免這種情況，就出現(xiàn)了這個(gè)最差適配算法，這個(gè)算法它和最佳適配算法是反著來的，它每次嘗試分配最大的可用空閑區(qū)，因?yàn)檫@樣的話，理論上剩余的空閑區(qū)也是比較大的，內(nèi)存碎片不會(huì)那么小，還能得到重復(fù)利用。

一個(gè)需要1.5M的進(jìn)程，在最差適配算法情況下，不會(huì)選擇3號(hào)（2M）內(nèi)存空閑塊，而是會(huì)選擇更大的5號(hào)（3M）內(nèi)存空閑塊。

快速適配算法

上面的幾種算法都有一個(gè)共同的特點(diǎn)：空閑內(nèi)存塊和已使用內(nèi)存塊是共用的一個(gè)鏈表，這會(huì)有什么問題呢？正常來說，我要查找一個(gè)空閑塊，我并不需要檢索已經(jīng)被使用的內(nèi)存塊，所以如果能把已使用的和未使用的分開，然后用兩個(gè)鏈表分別維護(hù)，那么上面的算法無論哪種，速度都將得到提升，并且節(jié)點(diǎn)也不需要P和M來標(biāo)記狀態(tài)了。但是分開也有缺點(diǎn)，如果進(jìn)程終止或者被換出，那么對(duì)應(yīng)的內(nèi)存塊需要從已使用的鏈表中刪掉然后加入到未使用的鏈表中，這個(gè)開銷是要稍微大點(diǎn)的。當(dāng)然對(duì)于未使用的鏈表如果是排序的，那么首次適應(yīng)算法和最佳適應(yīng)算法是一樣快的。

快速適配算法就是利用了這個(gè)特點(diǎn)，這個(gè)算法會(huì)為那些常用大小的空閑塊維護(hù)單獨(dú)的鏈表，比如有4K的空閑鏈表、8K的空閑鏈表...，如果要分配一個(gè)7K的內(nèi)存空間，那么既可以選擇兩個(gè)4K的，也可以選擇一個(gè)8K的。

它的優(yōu)點(diǎn)很明顯，在查找一個(gè)指定大小的空閑區(qū)會(huì)很快速，但是一個(gè)進(jìn)程終止或被換出時(shí)，會(huì)尋找它的相鄰塊查看是否可以合并，這個(gè)過程相對(duì)較慢，如果不合并的話，那么同樣也會(huì)產(chǎn)生很多的小空閑區(qū)，它們可能無法被利用，造成浪費(fèi)。

虛擬內(nèi)存：小內(nèi)存運(yùn)行大程序

可能你看到小內(nèi)存運(yùn)行大程序比較詫異，因?yàn)樯厦娌皇钦f到了嗎？只要把空閑的進(jìn)程換出去，把需要運(yùn)行的進(jìn)程再換進(jìn)來不就行了嗎？?jī)?nèi)存交換技術(shù)似乎解決了，這里需要注意的是，首先內(nèi)存交換技術(shù)在空間不夠的情況下需要把進(jìn)程換出到磁盤上，然后從磁盤上換入新進(jìn)程，看到磁盤你可能明白了，很慢。其次，你發(fā)現(xiàn)沒，換入換出的是整個(gè)進(jìn)程，我們知道進(jìn)程也是由一塊一塊代碼組成的，也就是許許多多的機(jī)器指令，對(duì)于內(nèi)存交換技術(shù)來說，一個(gè)進(jìn)程下的所有指令要么全部進(jìn)內(nèi)存，要么全部不進(jìn)內(nèi)存。看到這里你可能覺得這不是正常嗎？好的，別急，我們接著往下看。

后來出現(xiàn)了更牛逼的技術(shù)：虛擬內(nèi)存。它的基本思想就是，每個(gè)程序擁有自己的地址空間，尤其注意后面的自己的地址空間，然后這個(gè)空間可以被分割成多個(gè)塊，每一個(gè)塊我們稱之為頁（page）或者叫頁面，對(duì)于這些頁來說，它們的地址是連續(xù)的，同時(shí)它們的地址是虛擬的，并不是真正的物理內(nèi)存地址，那怎么辦？程序運(yùn)行需要讀到真正的物理內(nèi)存地址，別跟我玩虛的，這就需要一套映射機(jī)制，然后MMU出現(xiàn)了，MMU全稱叫做：Memory Managment Unit，即內(nèi)存管理單元，正常來說，CPU讀某個(gè)內(nèi)存地址數(shù)據(jù)的時(shí)候，會(huì)把對(duì)應(yīng)的地址發(fā)到內(nèi)存總線上，但是在虛擬內(nèi)存的情況下，直接發(fā)到內(nèi)存總線上肯定是找不到對(duì)應(yīng)的內(nèi)存地址的，這時(shí)候CPU會(huì)把虛擬地址告訴MMU，讓MMU幫我們找到對(duì)應(yīng)的內(nèi)存地址，沒錯(cuò)，MMU就是一個(gè)地址轉(zhuǎn)換的中轉(zhuǎn)站。

程序地址分頁的好處是：

1. 對(duì)于程序來說，不需要像內(nèi)存交換那樣把所有的指令都加載到內(nèi)存中才能運(yùn)行，可以單獨(dú)運(yùn)行某一頁的指令
2. 當(dāng)進(jìn)程的某一頁不在內(nèi)存中的時(shí)候，CPU會(huì)在這個(gè)頁加載到內(nèi)存的過程中去執(zhí)行其他的進(jìn)程。

當(dāng)然虛擬內(nèi)存會(huì)分頁，那么對(duì)應(yīng)的物理內(nèi)存其實(shí)也會(huì)分頁，只不過物理內(nèi)存對(duì)應(yīng)的單元我們叫頁框。頁面和頁框通常是一樣大的。我們來看個(gè)例子，假設(shè)此時(shí)頁面和頁框的大小都是4K，那么對(duì)于64K的虛擬地址空間可以得到64/4=16個(gè)虛擬頁面，而對(duì)于32K的物理地址空間可以得到32/4=8個(gè)頁框，很明顯此時(shí)的頁框是不夠的，總有些虛擬頁面找不到對(duì)應(yīng)的頁框。

我們先來看看虛擬地址為20500對(duì)應(yīng)物理地址如何被找到的：

1. 首先虛擬地址20500對(duì)應(yīng)5號(hào)頁面（20480-24575）
2. 5號(hào)頁面的起始地址20480向后查找20個(gè)字節(jié)，就是虛擬地址的位置
3. 5號(hào)頁面對(duì)應(yīng)3號(hào)物理頁框
4. 3號(hào)物理頁框的起始地址是12288，12288+20=12308，即12308就是我們實(shí)際的目標(biāo)物理地址。

但是對(duì)于虛擬地址而言，圖中還有紅色的區(qū)域，上面我們也說到了，總有些虛擬地址沒有對(duì)應(yīng)的頁框，也就是這部分虛擬地址是沒有對(duì)應(yīng)的物理地址，當(dāng)程序訪問到一個(gè)未被映射的虛擬地址（紅色區(qū)域）的時(shí)候，那么就會(huì)發(fā)生缺頁中斷，然后操作系統(tǒng)會(huì)找到一個(gè)最近很少使用的頁框把它的內(nèi)容換到磁盤上去，再把剛剛發(fā)生缺頁中斷的頁面從磁盤讀到剛剛回收的頁框中去，最后修改虛擬地址到頁框的映射，然后重啟引起中斷的指令。

最后可以發(fā)現(xiàn)分頁機(jī)制使我們的程序更加細(xì)膩了，運(yùn)行的粒度是頁而不是整個(gè)進(jìn)程，大大提高了效率。

頁表

上面說到虛擬內(nèi)存到物理內(nèi)存有個(gè)映射，這個(gè)映射我們知道是MMU做的，但是它是如何實(shí)現(xiàn)的？最簡(jiǎn)單的辦法就是需要有一張類似hash表的結(jié)構(gòu)來查看，比如頁面1對(duì)應(yīng)的頁框是10，那么就記錄成hash[1]=10，但是這僅僅是定位到了頁框，具體的位置還沒定位到，也就是類似偏移量的數(shù)據(jù)沒有。不猜了，我們直接來看看MMU是如何做到的，以一個(gè)16位的虛擬地址，并且頁面和頁框都是4K的情況來說，MMU會(huì)把前4位當(dāng)作是索引，也就是定位到頁框的序號(hào)，后12位作為偏移量，這里為什么是12位，很巧妙，因?yàn)?^12=4K，正好給每個(gè)頁框里的數(shù)據(jù)上了個(gè)標(biāo)號(hào)。因此我們只需要根據(jù)前4位找到對(duì)應(yīng)的頁框即可，然后偏移量就是后12位。找頁框就是去我們即將要說的頁表里去找，頁表除了有頁面對(duì)應(yīng)的頁框后，還有個(gè)標(biāo)志位來表示對(duì)應(yīng)的頁面是否有映射到對(duì)應(yīng)的頁框，缺頁中斷就是根據(jù)這個(gè)標(biāo)志位來的。

可以看出頁表非常關(guān)鍵，不僅僅要知道頁框、以及是否缺頁，其實(shí)頁表還有保護(hù)位、修改位、訪問位和高速緩存禁止位。

• 保護(hù)位：指的是一個(gè)頁允許什么類型的訪問，常見的是用三個(gè)比特位分別表示讀、寫、執(zhí)行。
• 修改位：有時(shí)候也稱為臟位，由硬件自動(dòng)設(shè)置，當(dāng)一個(gè)頁被修改后，也就是和磁盤的數(shù)據(jù)不一致了，那么這個(gè)位就會(huì)被標(biāo)記為1，下次在頁框置換的時(shí)候，需要把臟頁刷回磁盤，如果這個(gè)頁的標(biāo)記為0，說明沒有被修改，那么不需要刷回磁盤，直接把數(shù)據(jù)丟棄就行了。
• 訪問位：當(dāng)一個(gè)頁面不論是發(fā)生讀還是發(fā)生寫，該頁面的訪問位都會(huì)設(shè)置成1，表示正在被訪問，它的作用就是在發(fā)生缺頁中斷時(shí)，根據(jù)這個(gè)標(biāo)志位優(yōu)先在那些沒有被訪問的頁面中選擇淘汰其中的一個(gè)或者多個(gè)頁框。
• 高速緩存禁止位：對(duì)于那些映射到設(shè)備寄存器而不是常規(guī)內(nèi)存的頁面而言，這個(gè)特性很重要，加入操作系統(tǒng)正在緊張的循環(huán)等待某個(gè)IO設(shè)備對(duì)它剛發(fā)出的指令做出響應(yīng)，保證這個(gè)設(shè)備讀的不是被高速緩存的副本非常重要。

TLB快表加速訪問

通過頁表我們可以很好的實(shí)現(xiàn)虛擬地址到物理地址的轉(zhuǎn)換，然而現(xiàn)代計(jì)算機(jī)至少是32位的虛擬地址，以4K為一頁來說，那么對(duì)于32位的虛擬地址，它的頁表項(xiàng)就有2^20=1048576個(gè)，無論是頁表本身的大小還是檢索速度，這個(gè)數(shù)字其實(shí)算是有點(diǎn)大了。如果是64位虛擬的地址，按照這種方式的話，頁表項(xiàng)將大到超乎想象，更何況最重要的是每個(gè)進(jìn)程都會(huì)有一個(gè)這樣的頁表。

我們知道如果每次都要在龐大的頁表里面檢索頁框的話，效率一定不是很高。而且計(jì)算機(jī)的設(shè)計(jì)者們觀察到這樣一種現(xiàn)象：大多數(shù)程序總是對(duì)少量的頁進(jìn)行多次訪問，如果能為這些經(jīng)常被訪問的頁單獨(dú)建立一個(gè)查詢頁表，那么速度就會(huì)大大提升，這就是快表，快表只會(huì)包含少量的頁表項(xiàng)，通常不會(huì)超過256個(gè)，當(dāng)我們要查找一個(gè)虛擬地址的時(shí)候。首先會(huì)在快表中查找，如果能找到那么就可以直接返回對(duì)應(yīng)的頁框，如果找不到才會(huì)去頁表中查找，然后從快表中淘汰一個(gè)表項(xiàng)，用新找到的頁替代它。

總體來說，TLB類似一個(gè)體積更小的頁表緩存，它存放的都是最近被訪問的頁，而不是所有的頁。

多級(jí)頁表

TLB雖然一定程度上可以解決轉(zhuǎn)換速度的問題，但是沒有解決頁表本身占用太大空間的問題。其實(shí)我們可以想想，大部分程序會(huì)使用到所有的頁面嗎？其實(shí)不會(huì)。一個(gè)進(jìn)程在內(nèi)存中的地址空間一般分為程序段、數(shù)據(jù)段和堆棧段，堆棧段在內(nèi)存的結(jié)構(gòu)上是從高地址向低地址增長(zhǎng)的，其他兩個(gè)是從低地址向高地址增長(zhǎng)的。

可以發(fā)現(xiàn)中間部分是空的，也就是這部分地址是用不到的，那我們完全不需要把中間沒有被使用的內(nèi)存地址也引入頁表呀，這就是多級(jí)頁表的思想。以32位地址為例，后12位是偏移量，前20位可以拆成兩個(gè)10位，我們暫且叫做頂級(jí)頁表和二級(jí)頁表，每10位可以表示2^10=1024個(gè)表項(xiàng)，因此它的結(jié)構(gòu)大致如下：

對(duì)于頂級(jí)頁表來說，中間灰色的部分就是沒有被使用的內(nèi)存空間。頂級(jí)頁表就像我們身份證號(hào)前面幾個(gè)數(shù)字，可以定位到我們是哪個(gè)城市或者縣的，二級(jí)頁表就像身份證中間的數(shù)字，可以定位到我們是哪個(gè)街道或者哪個(gè)村的，最后的偏移量就像我們的門牌號(hào)和姓名，通過這樣的分段可以大大減少空間，我們來看個(gè)簡(jiǎn)單的例子：

如果我們不拆出頂級(jí)頁表和二級(jí)頁表，那么所需要的頁表項(xiàng)就是2^20個(gè)，如果我們拆分，那么就是1個(gè)頂級(jí)頁表+2^10個(gè)二級(jí)頁表，兩者的存儲(chǔ)差距明顯可以看出拆分后更加節(jié)省空間，這就是多級(jí)頁表的好處。

當(dāng)然我們的二級(jí)也可以拆成三級(jí)、四級(jí)甚至更多級(jí)，級(jí)數(shù)越多靈活性越大，但是級(jí)數(shù)越多，檢索越慢，這一點(diǎn)是需要注意的。