本文轉(zhuǎn)載自微信公眾號「程序員cxuan」，作者cxuan。轉(zhuǎn)載本文請聯(lián)系程序員cxuan公眾號。

在計算機(jī)早期的時候，計算機(jī)是無法將大于內(nèi)存大小的應(yīng)用裝入內(nèi)存的，因為計算機(jī)讀寫應(yīng)用數(shù)據(jù)是直接通過總線來對內(nèi)存進(jìn)行直接操作，對于寫操作來說，計算機(jī)會直接將地址寫入內(nèi)存;對于讀操作來說，計算機(jī)會直接讀取內(nèi)存的數(shù)據(jù)。

但是隨著軟件的不斷膨脹和移動應(yīng)用的到來，一切慢慢變了。

我們想要手機(jī)既能夠運行微信，同時又能夠運行 QQ 音樂，還希望能夠聊微博、刷知乎以及看股票。如果我們的手機(jī)內(nèi)存只有 1G，那么顯然是無法滿足這些應(yīng)用的，因為微信的后臺程序都占用 1G 多內(nèi)存了。那么就會有人說，把內(nèi)存容量提高不就行了嗎?這句話看似沒錯，但是內(nèi)存的造價成本非常昂貴，而且內(nèi)存的容量是永遠(yuǎn)追不上應(yīng)用程序所占用的容量的，把所有應(yīng)用程序直接堆入內(nèi)存也只是飲鴆止渴，因為即使是多核線程持續(xù)不斷的進(jìn)行計算，也會存在性能瓶頸。

客戶都是難搞的，我們并不希望正在使用微信，而后臺卻運行一些其他沒有必要的應(yīng)用，比如說旅游軟件、郵箱等。所以站在用戶的角度上來說，線程切換到這些應(yīng)用上是完全沒有必要的。

基于上述這些考量，工程師們認(rèn)為一直擴(kuò)大內(nèi)存容量并不能解決根本問題。

就像是軟件架構(gòu)一樣，盲目追求高性能并不一定可取，需要同時兼顧 CAP 的各個原則。

后來，提出了一種虛擬內(nèi)存(virtual memory)思想，虛擬內(nèi)存是操作系統(tǒng)的一種抽象，虛擬內(nèi)存的主要思想是：每個程序都有自己的地址空間，程序間的地址空間彼此不可見，我們的程序首先要先運行在虛擬內(nèi)存中，虛擬內(nèi)存會分為多個塊，每個塊稱為一頁或者頁面(page)，每一頁有連續(xù)的地址范圍，這些頁會被映射到物理內(nèi)存，當(dāng)程序引用到一部分在物理內(nèi)存的地址空間時，會由硬件完成對應(yīng)的映射過程，當(dāng)程序引用到不在物理內(nèi)存的地址空間時，由操作系統(tǒng)負(fù)責(zé)將缺失(不在內(nèi)存)的部分裝入物理內(nèi)存并重新執(zhí)行。

虛擬內(nèi)存系統(tǒng)是一種管理和分配程序虛擬內(nèi)存的程序，在使用虛擬內(nèi)存的情況下，虛擬地址不會直接映射到物理內(nèi)存中，而是會直接輸送到內(nèi)存管理單元(Memory Management Unit，MMU)，由 MMU 將虛擬地址映射為物理內(nèi)存地址。執(zhí)行這個映射過程的技術(shù)就叫做分頁(paging)。

MMU 是一塊單獨的芯片，它可以獨立存在，不過現(xiàn)代 OS 都把它內(nèi)置在了 CPU 中。

但是，映射到物理內(nèi)存的哪個位置?映射的規(guī)則又是什么?

實際上，物理內(nèi)存的劃分其實和虛擬內(nèi)存是一樣的，在物理內(nèi)存中，也會被劃分為一個個的頁框(page frame)，頁框是內(nèi)存所劃分的存儲單元，與虛擬內(nèi)存中的頁所不同的是，頁框是主存中的物理屬性，而頁面只是一種虛擬的抽象表示。頁面和頁框的存儲大小通常是一樣的，一般是 4KB。

通過 MMU 的幫助，可以有效地將虛擬地址映射到物理內(nèi)存地址，這也就是說，頁面可以和頁框進(jìn)行合理的映射。但是這并沒有解決虛擬地址空間比物理內(nèi)存空間大的這個問題。當(dāng) CPU 進(jìn)行數(shù)據(jù)寫入時，MMU 會判斷數(shù)據(jù)寫入的頁面是否已經(jīng)映射到頁框中，如果沒有映射的話，CPU 會陷入(trap)到操作系統(tǒng)，這個陷入的過程稱為缺頁中斷或者叫做缺頁錯誤(page fault)。

之后，操作系統(tǒng)會找到一個空閑的頁框并將它的內(nèi)容寫入到頁框中(這個頁框其實是在磁盤中，因為操作系統(tǒng)不會一次性把所有的頁框都加載到內(nèi)存中，而是按需加入)，然后修改頁框和頁面的映射關(guān)系，再重新啟動 trap 陷入的指令。

上面說到，MMU 會判斷數(shù)據(jù)寫入的頁面是否已經(jīng)映射到了頁框中，這個是如何判斷的呢?

實際上，MMU 中有一個叫做頁表(page table)的結(jié)構(gòu)，這個頁表就記錄了頁面和頁框的映射關(guān)系，上面所聊到修改頁框和頁面的映射關(guān)系，實際上就是修改頁表中的一個在/不在位的數(shù)據(jù)項，關(guān)于頁表的結(jié)構(gòu)，我們后面回說。

下面來看一下頁面和頁框的映射關(guān)系圖。

根據(jù)頁面中的頁表索引可以找到對應(yīng)的頁表號，根據(jù)頁表中的頁框索引可以找到頁框號，這種映射關(guān)系就很類似計算機(jī)網(wǎng)絡(luò)中的路由表(記錄各個數(shù)據(jù)轉(zhuǎn)發(fā)路徑)。從數(shù)學(xué)的角度來講，可以把頁表看做是一個函數(shù)，它的參數(shù)是頁表索引(通常也叫做虛擬頁號)，結(jié)果是頁框號，通過這個函數(shù)可以將虛擬地址中的虛擬頁面轉(zhuǎn)換成頁框號，然后形成物理地址。

這里強(qiáng)調(diào)一點：如果在/不在位是 0 的話，說明該頁面和頁框沒有存在映射關(guān)系，此時就會直接引起操作系統(tǒng)陷入，由操作系統(tǒng)找到對應(yīng)的頁框執(zhí)行寫入，寫入完成后修改頁面和頁框的映射關(guān)系，然后回到引起陷入的位置繼續(xù)執(zhí)行。

上面提到了頁表是記錄頁面和頁框映射關(guān)系的一個結(jié)構(gòu)，下面我們就來聊一下頁表項的結(jié)構(gòu)。不同機(jī)器的頁表結(jié)構(gòu)是不一樣的，但是大多數(shù)頁表項都具有下面這個結(jié)構(gòu)。

對于頁表項這個結(jié)構(gòu)來說，最重要的就是頁框號，頁框號相當(dāng)于是頁表的身份證，這就跟我們的身份證一樣，所以非常重要。

• 在/不在位我們上面聊過了，這個位就是判斷頁面和頁框有沒有進(jìn)行映射的一項。
• 保護(hù)位指出在這個頁面上允許什么樣的類型訪問，是讀還是寫，一般讀是 1，寫是 0 ，這是一位的形式，不過還有另外一種形式，是三位，分別對應(yīng)讀、寫、執(zhí)行。
• 修改位 用于判斷這個頁面是否被修改過，在對頁面進(jìn)行寫入時會自動設(shè)置修改位，如果一個頁面已經(jīng)被修改過，那么必須將它寫回磁盤，我們可以認(rèn)為這個頁面是一個臟頁。
• 無論讀寫，都會設(shè)置訪問位，訪問位的意義用來讓操作系統(tǒng)淘汰頁面所用，沒有訪問過的頁面要比多次訪問的頁面更容易被淘汰，訪問位在頁面置換算法中非常有用。
• 緩存位用于判斷是否禁用高速緩存，有的時候 CPU 需要讀取最新的用戶輸入，而不是從高速緩存中讀取已有的數(shù)據(jù)。

聊完頁表之后，我們來回顧一下頁面到頁框的映射過程(上面有寫，這里不再闡述了)

思考過后，你會發(fā)現(xiàn)，頁面到頁框的映射過程比較繁瑣，又是檢索頁面、又是操作系統(tǒng)切換、又是內(nèi)存和磁盤的交互，想必這部分的性能容易出現(xiàn)問題，所以提升這部分的性能就成為了優(yōu)先級比較高的一個課題。

我們知道，這個映射過程主要是在 MMU 中完成的，所以能不能加快虛擬地址到物理地址的映射速度呢?，而且很多操作系統(tǒng)的虛擬地址空間往往很大，所以需要的頁表也會越來越大，那么如何處理日益劇增的頁表呢?

首先我們要聊一下的就是如何加快虛擬地址到物理地址的映射速度，加快映射速度有兩種方式，一種是使用硬件進(jìn)行加速，一種是使用軟件進(jìn)行加速。

經(jīng)過多年的研究表明，大多數(shù)程序會對少量的頁面進(jìn)行多次訪問，而不會對大量的頁面進(jìn)行多次訪問或者訪問次數(shù)大差不差，因此，只有極少數(shù)的頁表會被頻繁訪問，而大多數(shù)頁面卻照顧不到。由于這種局部性原理，使用硬件的方式是設(shè)置一個轉(zhuǎn)換檢測緩沖區(qū)(TLB)，它能夠直接將虛擬地址映射成為物理地址，而不必再訪問頁表。

TLB 又叫做快表或者相聯(lián)存儲器。

TLB 可以放在 CPU 和 CPU 緩存(CPU cache)之間，用于緩存虛擬地址，TLB 可以放在 CPU 和 內(nèi)存之間，用于緩存物理地址，但是一般緩存虛擬地址比較常見，由此可見，TLB 相當(dāng)于是又多加了一個緩存層。

虛擬頁面在 TLB 中

當(dāng)一個數(shù)據(jù)的虛擬地址交由 MMU 進(jìn)行轉(zhuǎn)換時，MMU 首先會將這個虛擬地址和 TLB 中緩存的虛擬地址進(jìn)行匹配，判斷虛擬地址所在的頁面是否被緩存，如果已經(jīng)緩存，就會訪問 TLB(這里有個前提就是判斷訪問位)將虛擬頁面對應(yīng)的頁框號取出，而不必再訪問頁表。

虛擬頁面不在 TLB 中

如果 MMU 沒有檢測到虛擬地址所在的頁面，就說明沒有查詢到匹配項，就會走頁表訪問，通過頁表查詢到物理地址后，會從 TLB 中淘汰一個頁面，用新找到的頁面進(jìn)行替換。

雖然內(nèi)置一個硬件 TLB 能夠加快虛擬地址到物理地址的映射速度，不過現(xiàn)代 os 大多數(shù)都是使用軟件 TLB 來實現(xiàn)這個加速過程的，使用軟件 TLB 就意味著不再使用硬件，轉(zhuǎn)而擁抱操作系統(tǒng)。

這也就是說，當(dāng)發(fā)生 TLB 失效時，不再是通過 MMU 到頁表中查詢，而是生成一個 TLB 失效并交給操作系統(tǒng)來解決。失效會有兩種發(fā)生的可能性：當(dāng)要訪問的頁面在內(nèi)存中時，這種失效叫做軟失效，軟失效比較好處理，找到該頁面然后直接更新 TLB 中對應(yīng)的項即可。當(dāng)要訪問的頁面不再內(nèi)存中時，這種失效叫做硬失效，硬失效涉及磁盤訪問，頁面調(diào)入，硬失效的處理時間往往是軟失效的幾百萬倍。

上述都是理想情況下的失效，但實際情況下會存在既不是軟失效也不是硬失效的情況。當(dāng)程序訪問一個非法地址時，根本不需要向 TLB 更新映射，此時 os 會直接報告段錯誤來終止程序，這種缺頁屬于程序錯誤;而軟失效通常稱為次要缺頁錯誤，硬失效稱為嚴(yán)重缺頁錯誤。

解決完第一個問題之后，我們再來看第二個問題，即如何處理日益劇增的頁表呢?

一般有兩種處理方式，使用多級頁表和倒排頁表。

第一種方案是使用多級頁表，下面是一個例子

32 位的虛擬地址被劃分為 10 位的 PT1 域，10 位的 PT2 域，還有 12 位的 Offset 域。因為偏移量是 12 位，所以頁面大小是 4 KB，共有 2^20 次方個頁面。

引入多級頁表的原因是避免把全部頁表一直保存在內(nèi)存中。不需要的頁表就不應(yīng)該保留。

多級頁表是一種分頁方案，它由兩個或多個層次的分頁表組成，也稱為分層分頁。級別1(level 1)頁面表的條目是指向級別 2(level 2) 頁面表的指針，級別2頁面表的條目是指向級別 3(level 3) 頁面表的指針，依此類推。最后一級頁表存儲的是實際的信息。

下面是一個二級頁表的工作過程

在最左邊是頂級頁表，它有 1024 個表項，對應(yīng)于 10 位的 PT1 域。當(dāng)一個虛擬地址被送到 MMU 時，MMU 首先提取 PT1 域并把該值作為訪問頂級頁表的索引。因為整個 4 GB (即 32 位)虛擬地址已經(jīng)按 4 KB 大小分塊，所以頂級頁表中的 1024 個表項的每一個都表示 4M 的塊地址范圍。

由索引頂級頁表得到的表項中含有二級頁表的地址或頁框號。頂級頁表的表項 0 指向程序正文的頁表，表項 1 指向含有數(shù)據(jù)的頁表，表項 1023 指向堆棧的頁表，其他的項(用陰影表示)表示沒有使用?，F(xiàn)在把 PT2 域作為訪問選定的二級頁表的索引，以便找到虛擬頁面的對應(yīng)頁框號。

針對分頁層級結(jié)構(gòu)中不斷增加的替代方法是使用倒排頁表(inverted page tables)。采用這種解決方案的有 PowerPC、UltraSPARC 和 Itanium。在這種設(shè)計中，實際內(nèi)存中的每個頁框?qū)?yīng)一個表項，而不是每個虛擬頁面對應(yīng)一個表項。

雖然倒排頁表節(jié)省了大量的空間，但是它也有自己的缺陷：那就是從虛擬地址到物理地址的轉(zhuǎn)換會變得很困難。當(dāng)進(jìn)程 n 訪問虛擬頁面 p 時，硬件不能再通過把 p 當(dāng)作指向頁表的一個索引來查找物理頁。而是必須搜索整個倒排表來查找某個表項。另外，搜索必須對每一個內(nèi)存訪問操作都執(zhí)行一次，而不是在發(fā)生缺頁中斷時執(zhí)行。

解決這一問題的方式是使用 TLB。當(dāng)發(fā)生 TLB 失效時，需要用軟件搜索整個倒排頁表。一個可行的方式是建立一個散列表，用虛擬地址來散列。當(dāng)前所有內(nèi)存中的具有相同散列值的虛擬頁面被鏈接在一起。如下圖所示

如果散列表中的槽數(shù)與機(jī)器中物理頁面數(shù)一樣多，那么散列表的沖突鏈的長度將會是 1 個表項的長度，這將會大大提高映射速度。一旦頁框被找到，新的(虛擬頁號，物理頁框號)就會被裝載到 TLB 中。

總結(jié)

這篇文章我從 MMU 這個知識點進(jìn)行切入，來為你展開了操作系統(tǒng)中的虛擬地址的概念，操作系統(tǒng)是如何處理日益增加的地址空間的，以及內(nèi)存管理面臨的挑戰(zhàn)，如何優(yōu)化等。