存儲(chǔ)器 - 內(nèi)存：程序的虛擬內(nèi)存是如何映射到物理內(nèi)存

計(jì)算機(jī)組成原理目錄：https://www.cnblogs.com/binarylei/p/12585607.html

程序運(yùn)行時(shí),，指令和數(shù)據(jù)都需要先加載到內(nèi)存里面,，才會(huì)被 CPU 拿去執(zhí)行。那程序中的虛擬地址最終是如何映射到內(nèi)存中的物理地址呢,？從簡(jiǎn)單頁(yè)表,，到多級(jí)頁(yè)表,，再到 TLB，都解決了那些問(wèn)題,？

1. 簡(jiǎn)單頁(yè)表：類(lèi)似數(shù)組,，時(shí)間復(fù)雜度為 O(1)。但空間復(fù)雜度為數(shù)組的長(zhǎng)度,，即頁(yè)的個(gè)數(shù),。32 位的內(nèi)存地址為 4MB（= 2^20 * 4byte）。
2. 多級(jí)頁(yè)表：類(lèi)似 B+ 樹(shù),，時(shí)間復(fù)雜度為 O(n),，如 4 級(jí)頁(yè)表就需要查詢(xún) 4 次。但程序只需要存儲(chǔ)正在使用的虛擬頁(yè)的映射關(guān)系,，空間復(fù)雜度大大降低,。
3. TLB：使用緩存保存之前虛擬頁(yè)的映射關(guān)系。因?yàn)橹噶詈蛿?shù)據(jù)往往都是連續(xù)的,，存在空間局部性和時(shí)間局部性,。也就是說(shuō)，連續(xù)執(zhí)行的多個(gè)指令和數(shù)據(jù)往往在同一個(gè)虛擬頁(yè)中,，沒(méi)必要每次都從內(nèi)存中讀取頁(yè)表來(lái)解析虛擬地址,。

1. 虛擬地址和物理地址

另外，學(xué)習(xí)本節(jié)時(shí)可以將下面兩個(gè)知識(shí)點(diǎn)對(duì)比學(xué)習(xí),。

1. 內(nèi)存地址映射：虛擬地址是如何映射到物理地址,？
2. 高速緩存映射：內(nèi)存地址是如何映射到 CPU Cache？

程序在編譯時(shí)不可能知道裝載后的物理內(nèi)存地址,，實(shí)際上,，程序編譯生成的地址都是虛擬地址。在我們?nèi)粘Ｊ褂玫?Linux 或者 Windows 操作系統(tǒng)下,，程序并不能直接訪(fǎng)問(wèn)物理內(nèi)存,。為了解決這個(gè)問(wèn)題，當(dāng)程序裝載后,，會(huì)通過(guò)虛擬地址映射到真實(shí)的物理地址,。

內(nèi)存被分成固定大小的頁(yè)(Page)，然后再通過(guò)虛擬內(nèi)存地址(Virtual Address) 到物理內(nèi)存地址(Physical Address) 的地址轉(zhuǎn)換(Address Translation),，才能訪(fǎng)問(wèn)實(shí)際存放數(shù)據(jù)的物理內(nèi)存位置,。而我們的程序看到的內(nèi)存地址，都是虛擬內(nèi)存地址,。

這些虛擬內(nèi)存地址究竟是怎么轉(zhuǎn)換成物理內(nèi)存地址的呢,？這一講里，我們就來(lái)看一看,。

2. 簡(jiǎn)單頁(yè)表

頁(yè)表(Page Table)：想要把虛擬內(nèi)存地址,，映射到物理內(nèi)存地址,，最直觀的辦法，就是來(lái)建一張映射表,。這個(gè)映射表,，能夠?qū)崿F(xiàn)虛擬內(nèi)存里面的頁(yè)，到物理內(nèi)存里面的頁(yè)的映射,。這個(gè)映射表,，在計(jì)算機(jī)里面，就叫作頁(yè)表,。

頁(yè)表地址轉(zhuǎn)換,，把一個(gè)內(nèi)存地址分成頁(yè)號(hào)(Directory) 和偏移量(Offset) 兩個(gè)部分。以一個(gè) 32 位的內(nèi)存地址,，頁(yè)的大小 4KB 為例,，內(nèi)存地址的 20 位的高位表示頁(yè)號(hào)，12 位（2¹² = 4KB）的低位表示偏移量,。

總結(jié)： 對(duì)于一個(gè)內(nèi)存地址轉(zhuǎn)換,，其實(shí)就是這樣三個(gè)步驟：

1. 把虛擬內(nèi)存地址，切分成頁(yè)號(hào)和偏移量的組合,；
2. 從頁(yè)表里面,，查詢(xún)出虛擬頁(yè)號(hào)，對(duì)應(yīng)的物理頁(yè)號(hào),；
3. 直接拿物理頁(yè)號(hào),，加上前面的偏移量，就得到了物理內(nèi)存地址,。

下面我們先計(jì)算一下,，這樣一個(gè)頁(yè)表需要多大的空間嗎？我們還是以 32 位的內(nèi)存地址空間為例,，需要一個(gè)數(shù)組大小為 2²⁰ 的數(shù)組，同時(shí)存儲(chǔ)一個(gè)內(nèi)存地址需要 4byte 大小,，共需要內(nèi)存大小為 4MB（= 2²⁰ * 4 byte）,。根據(jù)虛擬頁(yè)號(hào)查找物理頁(yè)號(hào)公式如下：

很顯然，一個(gè)程序就需要 4MB,，我們的計(jì)算機(jī)上運(yùn)行上千個(gè)進(jìn)程是很正常的,，這樣一算下來(lái)，光存儲(chǔ)頁(yè)表的開(kāi)銷(xiāo)就有 4GB ??？你有沒(méi)有更好的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)頁(yè)面呢？

3. 多級(jí)頁(yè)表

很明顯,，大部分進(jìn)程所占用的內(nèi)存是有限的,，我們只需要保存那些用到的頁(yè)之間的映射關(guān)系就好了,。如果你對(duì)數(shù)據(jù)結(jié)構(gòu)比較熟悉，你可能要說(shuō)了,，那我們是不是應(yīng)該用哈希表（HashMap）這樣的數(shù)據(jù)結(jié)構(gòu)呢,？

很可惜你猜錯(cuò)了。在實(shí)踐中,，我們其實(shí)采用的是一種叫作多級(jí)頁(yè)表(Multi-Level Page Table) 的解決方案,。為什么我們不用哈希表而用多級(jí)頁(yè)表呢？別著急,，聽(tīng)我慢慢跟你講,。

3.1 進(jìn)程的內(nèi)存地址分配 - '兩頭實(shí)、中間空'

要知道為什么使用多級(jí)頁(yè)表而不是哈希表,，首先就要知道,，一個(gè)進(jìn)程的內(nèi)存地址空間是怎么分配的。在整個(gè)進(jìn)程的內(nèi)存地址空間,，通常是 '兩頭實(shí),、中間空'。在程序運(yùn)行的時(shí)候,，內(nèi)存地址從頂部往下,，不斷分配占用的棧的空間。而堆的空間,，內(nèi)存地址則是從底部往上,，是不斷分配占用的。

所以,，在一個(gè)實(shí)際的程序進(jìn)程里面,，虛擬內(nèi)存占用的地址空間，通常是兩段連續(xù)的空間,。而不是完全散落的隨機(jī)的內(nèi)存地址,。而多級(jí)頁(yè)表，就特別適合這樣的內(nèi)存地址分布,。

3.2 頁(yè)表樹(shù)

事實(shí)上,，多級(jí)頁(yè)表就像一個(gè)多叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，所以我們常常稱(chēng)它為頁(yè)表樹(shù)(Page Table Tree),。這種數(shù)據(jù)結(jié)構(gòu)其實(shí)和 B+ 樹(shù)類(lèi)似,，允許一個(gè)結(jié)點(diǎn)存儲(chǔ)多條記錄，并且非葉子結(jié)點(diǎn)只存儲(chǔ)索引,，只有葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù),。

使用多級(jí)頁(yè)表后，同樣的虛擬內(nèi)存地址，偏移量的部分和上面簡(jiǎn)單頁(yè)表一樣不變,，而原先的頁(yè)號(hào)部分需要拆分成多段,。我們還是以一個(gè) 32 位的內(nèi)存地址，頁(yè)的大小 4KB 為例,，其 20 個(gè)高位表示頁(yè)號(hào),，12 個(gè)低位表示偏移量。如果拆分成一個(gè) 4 級(jí)的多級(jí)頁(yè)表,，需要將前 20 個(gè)高位從高到低,，分成 4 級(jí)到 1 級(jí)這樣 4 個(gè)頁(yè)表索引。

說(shuō)明： 一個(gè)進(jìn)程會(huì)有一個(gè) 4 級(jí)頁(yè)表,，通過(guò)虛擬地址查找物理地址時(shí)：

1. 先通過(guò) 4 級(jí)頁(yè)表索引,，找到 4 級(jí)頁(yè)表里面對(duì)應(yīng)的條目（Entry）。這個(gè)條目里存放的是一張 3 級(jí)頁(yè)表所在的地址,。4 級(jí)頁(yè)面里面的每一個(gè)條目,，都對(duì)應(yīng)著一張 3 級(jí)頁(yè)表，所以我們可能有多張 3 級(jí)頁(yè)表,。
2. 再根據(jù) 3 級(jí)頁(yè)表索引,，在 3 級(jí)頁(yè)表中查找對(duì)應(yīng)的 2 級(jí)頁(yè)表地址。
3. 依次類(lèi)推,，直到 1 級(jí)頁(yè)表,。在最后一級(jí)頁(yè)表中，保存虛擬地址對(duì)應(yīng)的物理地址頁(yè)號(hào),。

多級(jí)頁(yè)表的結(jié)構(gòu)和 B+ 樹(shù)非常類(lèi)似,，允許一個(gè)結(jié)點(diǎn)存儲(chǔ)多條記錄，并且非葉子結(jié)點(diǎn)只存儲(chǔ)索引,，只有葉子結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù),。

3.3 復(fù)雜度分析

3.3.1 空間復(fù)雜度

如果 32 位的內(nèi)存地址（20 位頁(yè)號(hào) + 12 位偏移量）平均拆分成 4 級(jí)，每級(jí)都用 5 bit 表示,，那么每張頁(yè)表能存儲(chǔ) 2^5 = 32 條記錄,。

1. 滿(mǎn) 1 級(jí)頁(yè)表：一個(gè)滿(mǎn)頁(yè)大小 128 byte，可以映射 128 KB 內(nèi)存地址,。一個(gè)頁(yè)表共 32 條記錄,，每條記錄中存儲(chǔ)物理內(nèi)存對(duì)應(yīng)的頁(yè)號(hào)，需要 4 byte,，而對(duì)應(yīng)的一個(gè)頁(yè)的大小為 4KB。
2. 滿(mǎn) 2 級(jí)頁(yè)表：對(duì)應(yīng)的就是 32 個(gè) 1 級(jí)頁(yè)表,，也就是 4MB（= 32 * 128 KB）,。

那么，我們現(xiàn)在可以推算一下，一個(gè)進(jìn)程占用 8MB 的內(nèi)存空間需要多大的頁(yè)表空間,？8MB 分成了 2 個(gè) 4MB 的連續(xù)空間,，一共需要 2 個(gè)獨(dú)立的、填滿(mǎn)的 2 級(jí)索引表,，也就意味著 64 個(gè) 1 級(jí)索引表,，2 個(gè)獨(dú)立的 3 級(jí)索引表，1 個(gè) 4 級(jí)索引表,。一共需要 69 個(gè)索引表,，大概就是 9KB（= 69 * 128byte）。比起 4MB 來(lái)說(shuō),，只有差不多 1/500,。

3.3.2 時(shí)間復(fù)雜度

多級(jí)頁(yè)表雖然節(jié)約了我們的存儲(chǔ)空間，卻帶來(lái)了時(shí)間上的開(kāi)銷(xiāo),，所以多級(jí)頁(yè)表其實(shí)是一個(gè) '以時(shí)間換空間' 的策略,。原本我們進(jìn)行一次地址轉(zhuǎn)換，只需要訪(fǎng)問(wèn)一次內(nèi)存就能找到物理頁(yè)號(hào),，算出物理內(nèi)存地址,。但是，用了 4 級(jí)頁(yè)表,，我們就需要訪(fǎng)問(wèn) 4 次內(nèi)存,，才能找到物理頁(yè)號(hào)了。

4. 加速地址轉(zhuǎn)換：TLB

多級(jí)頁(yè)表以時(shí)間換空間的策略,，大節(jié)省了內(nèi)存開(kāi)銷(xiāo),。但使用 4 級(jí)頁(yè)表后，就需要訪(fǎng)問(wèn) 4 次內(nèi)存才能找到物理頁(yè)號(hào),。而虛擬地址和物理內(nèi)存地址之間的地址轉(zhuǎn)換,，是一個(gè)非常高頻的動(dòng)作，對(duì)它的性能要求非常高,，你有什么好的解決方案呢,？我們最先想到的可能就是加緩存，事實(shí)上,，CPU 也是這么做的,。

4.1 為什么可以使用緩存

程序所需要使用的指令，都順序存放在虛擬內(nèi)存里面,。我們執(zhí)行的指令,，也是一條條順序執(zhí)行下去的。也就是說(shuō),，對(duì)于指令地址和需要訪(fǎng)問(wèn)的數(shù)據(jù),，都存在空間局部性和時(shí)間局部性。

我們連續(xù)執(zhí)行了 5 條指令，因?yàn)閮?nèi)存地址都是連續(xù)的,，所以這 5 條指令通常都在同一個(gè)“虛擬頁(yè)”里,。我們可以把之前的內(nèi)存轉(zhuǎn)換地址緩存下來(lái)，使得不需要反復(fù)去訪(fǎng)問(wèn)內(nèi)存來(lái)進(jìn)行內(nèi)存地址轉(zhuǎn)換,。

4.2 TLB

地址變換高速緩沖(Translation-Lookaside Buffer，TLB)：是 CPU 中的一塊緩存芯片,，這塊緩存存放了之前已經(jīng)進(jìn)行過(guò)地址轉(zhuǎn)換的查詢(xún)結(jié)果,。有了 TLB ，當(dāng)同樣的虛擬地址需要進(jìn)行地址轉(zhuǎn)換的時(shí)候,，我們可以直接在 TLB 查詢(xún)結(jié)果,，而不需要多次訪(fǎng)問(wèn)內(nèi)存來(lái)完成一次轉(zhuǎn)換。

TLB 和我們前面講的 CPU 的高速緩存類(lèi)似,，可以分成指令的 TLB 和數(shù)據(jù)的 TLB,，也就是 ITLB 和 DTLB。同樣的,，我們也可以根據(jù)大小對(duì)它進(jìn)行分級(jí),，變成 L1、L2 這樣多層的 TLB,。另外,，和高速緩存一樣，同樣需要用臟標(biāo)記這樣的標(biāo)記位,，來(lái)實(shí)現(xiàn) '寫(xiě)回' 這樣緩存管理策略,。

為了性能，我們整個(gè)內(nèi)存轉(zhuǎn)換過(guò)程也要由硬件來(lái)執(zhí)行,。在CPU芯片里面,，我們封裝了內(nèi)存管理單元（MMU，Memory Management Unit）芯片,，用來(lái)完成地址轉(zhuǎn)換,。和TLB的訪(fǎng)問(wèn)和交互，都是由這個(gè) MMU 控制的,。

參考：

• 《計(jì)算機(jī)組成與設(shè)計(jì)：硬件 / 軟件接口》的第 5.7 章節(jié)：虛擬內(nèi)存,。
• 《What Every Programmer Should Know About Memory》的第 4 部分：Virtual Memory。

每天用心記錄一點(diǎn)點(diǎn),。內(nèi)容也許不重要,，但習(xí)慣很重要！