漫游計(jì)算機(jī)系統(tǒng)之虛擬存儲(chǔ)器

漫游計(jì)算機(jī)系統(tǒng)之虛擬存儲(chǔ)器

1. 背景

一個(gè)典型的計(jì)算機(jī)系統(tǒng)如下圖所示：

直接讓應(yīng)用使用硬件可能會(huì)導(dǎo)致濫用，并且應(yīng)用需要處理復(fù)雜的硬件細(xì)節(jié)，容易出錯(cuò)。所以我們引入了操作系統(tǒng)來管理硬件資源，如下圖所示：

操作系統(tǒng)為了讓應(yīng)用能更好更簡(jiǎn)單地使用硬件資源，對(duì)硬件資源做了進(jìn)一步抽象，如下圖所示：

2. 虛擬存儲(chǔ)器

虛擬存儲(chǔ)器把進(jìn)程訪問的存儲(chǔ)設(shè)備抽象成一個(gè)巨大的字節(jié)數(shù)組，并對(duì)每個(gè)字節(jié)做唯一的地址編碼。它提供了三個(gè)重要的功能：

1. 將主存看做存儲(chǔ)在磁盤上的地址空間的高速緩存，從而提高了主存使用效率。
2. 為每個(gè)進(jìn)程提供一致的地址空間，簡(jiǎn)化存儲(chǔ)器管理。
3. 保護(hù)每個(gè)進(jìn)程的地址空間不被其他進(jìn)程破壞。

虛擬存儲(chǔ)器在幕后自動(dòng)地工作，無需應(yīng)用程序員干涉，既然如此，為什么我們還需要去理解它呢？我想理解它可以帶來以下幾點(diǎn)好處：

1. 虛擬存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的核心。它涉及計(jì)算機(jī)系統(tǒng)的所有層面（硬件異常、匯編器、鏈接器、加載器、共享對(duì)象、文件、進(jìn)程），理解它將幫助我們更好地理解計(jì)算機(jī)系統(tǒng)是怎么工作的。
2. 虛擬存儲(chǔ)器的功能非常強(qiáng)大。它賦予應(yīng)用程序強(qiáng)大的功能，比如加載一個(gè)文件到存儲(chǔ)器中，不需要任何顯示拷貝。
3. 虛擬存儲(chǔ)器非常危險(xiǎn)。對(duì)于編寫像c/c++程序，一個(gè)錯(cuò)誤指針就可以讓程序立即崩潰。理解它可以讓我們更好地避免錯(cuò)誤；或者當(dāng)錯(cuò)誤發(fā)生時(shí)，更好地定位問題所在。

3. 虛擬尋址

進(jìn)程看到是虛擬地址，但是信息是存在物理內(nèi)存上的，那么系統(tǒng)是如何用虛擬地址來獲取對(duì)應(yīng)物理內(nèi)存的字節(jié)信息的呢？簡(jiǎn)單來說，可以分為三步：

1. CPU會(huì)把虛擬地址發(fā)送到MMU（Memory Management Unit）
2. MMU把虛擬地址翻譯為物理地址后傳送給主存
3. 主存把物理地址對(duì)應(yīng)的字節(jié)傳送給CPU

具體過程如下圖：

3.1. 頁表

MMU是如何把虛擬地址翻譯為物理地址的呢？
OS會(huì)把物理內(nèi)存、虛擬內(nèi)存分為同樣大小的塊（linux默認(rèn)為4k），并稱之為頁。同時(shí)為每個(gè)進(jìn)程分配頁表，頁表是一個(gè)頁表?xiàng)l目（PTE）數(shù)組，其中每個(gè)PTE記錄了虛擬頁與物理頁的映射關(guān)系。

一個(gè)虛擬地址可以分為兩部分：虛擬頁號(hào)×××和虛擬頁偏移量VPO。由于虛擬頁與物理頁是同樣大小，因此虛擬頁偏移量就是物理頁偏移量；虛擬頁號(hào)是頁表中PTE的索引，對(duì)應(yīng)的PTE中存儲(chǔ)著物理頁號(hào)和有效位（表示頁面是否有對(duì)應(yīng)物理頁），這樣MMU通過查詢PTE就可以找到虛擬頁對(duì)應(yīng)的物理頁，再加上虛擬頁偏移量就可以得到物理地址，如下圖：

3.2. 多級(jí)頁表

如果每個(gè)進(jìn)程只有一個(gè)頁表（假設(shè)物理頁大小為4k），那么對(duì)于32位系統(tǒng)，需要占用4M內(nèi)存（每個(gè)PTE是4字節(jié)）；對(duì)于64位系統(tǒng)（實(shí)際只用了48位用來尋址），則需要256G內(nèi)存，實(shí)在是太大了。為了解決這個(gè)問題，我們用多級(jí)頁表，如下圖：

在多級(jí)頁表中，所有級(jí)別的頁表大小是一樣的，我們以linux的4級(jí)頁表為例，則最少要4個(gè)頁表，假設(shè)一個(gè)頁表4k，總共16k；隨著進(jìn)程消耗內(nèi)存的增長(zhǎng)，第k級(jí)頁表數(shù)目隨之線性增長(zhǎng)，由于其他級(jí)別的頁表數(shù)目遠(yuǎn)遠(yuǎn)小于k級(jí)頁表，因此總頁表消耗內(nèi)存頁頁接近于線性增長(zhǎng)。由于進(jìn)程實(shí)際占用內(nèi)存大小遠(yuǎn)小于256T，因此頁表消耗內(nèi)存遠(yuǎn)小于一級(jí)頁表。

4. 進(jìn)程內(nèi)存布局

從上述小結(jié)，我們知道每個(gè)進(jìn)程都有一個(gè)獨(dú)立的虛擬存儲(chǔ)器空間，那么其布局是否有規(guī)律呢？我們以linux下的64位進(jìn)程舉例，見下圖：

linux將用戶虛擬存儲(chǔ)器組織成一些段的集合。一個(gè)段就是已分配的虛擬存儲(chǔ)器的連續(xù)片。只有存在于段的虛擬存儲(chǔ)器頁是可以被進(jìn)程訪問的。

#include <stdlib.h>

int main()
{
    char *p = (char*)malloc(1);
    while(1);
    return 0;
}

編譯上述代碼并運(yùn)行，通過top獲取此進(jìn)程PID后，我們可以打開/proc/PID/maps文件查看進(jìn)程的內(nèi)存布局：

00400000-00401000 r-xp 00000000 fd:01 723899                             /home/wld/test/a.out
00600000-00601000 r--p 00000000 fd:01 723899                             /home/wld/test/a.out
00601000-00602000 rw-p 00001000 fd:01 723899                             /home/wld/test/a.out
0148c000-014ad000 rw-p 00000000 00:00 0                                  [heap]
7fb917267000-7fb917425000 r-xp 00000000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb917425000-7fb917625000 ---p 001be000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb917625000-7fb917629000 r--p 001be000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb917629000-7fb91762b000 rw-p 001c2000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb91762b000-7fb917630000 rw-p 00000000 00:00 0
7fb917630000-7fb917653000 r-xp 00000000 fd:01 1731443                    /lib/x86_64-linux-gnu/ld-2.19.so
7fb917835000-7fb917838000 rw-p 00000000 00:00 0
7fb917850000-7fb917852000 rw-p 00000000 00:00 0
7fb917852000-7fb917853000 r--p 00022000 fd:01 1731443                    /lib/x86_64-linux-gnu/ld-2.19.so
7fb917853000-7fb917854000 rw-p 00023000 fd:01 1731443                    /lib/x86_64-linux-gnu/ld-2.19.so
7fb917854000-7fb917855000 rw-p 00000000 00:00 0
7ffe8b3e1000-7ffe8b402000 rw-p 00000000 00:00 0                          [stack]
7ffe8b449000-7ffe8b44b000 r--p 00000000 00:00 0                          [vvar]
7ffe8b44b000-7ffe8b44d000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

上面每一行表示一個(gè)段，每個(gè)段的有6列，各列含義如下：

1. 此段虛擬地址空間起始地址-結(jié)束地址。
2. 此段虛擬地址空間的屬性。每種屬性用一個(gè)字段表示，r表示可讀，w表示可寫，x表示可執(zhí)行，p和s共用一個(gè)字段，互斥關(guān)系，p表示私有段，s表示共享段，如果沒有相應(yīng)權(quán)限，則用’-’代替。
3. 對(duì)有名映射，表示此段虛擬存儲(chǔ)器起始地址在文件中以頁為單位的偏移。對(duì)匿名映射，它等于0或者vm_start/PAGE_SIZE。
4. 映射文件所屬設(shè)備號(hào)。對(duì)匿名映射來說，因?yàn)闆]有文件在磁盤上，所以沒有設(shè)備號(hào)，始終為00:00。對(duì)有名映射來說，是映射的文件所在設(shè)備的設(shè)備號(hào)
5. 映射文件所屬節(jié)點(diǎn)號(hào)。對(duì)匿名映射來說，因?yàn)闆]有文件在磁盤上，所以沒有節(jié)點(diǎn)號(hào)，始終為00:00。對(duì)有名映射來說，是映射的文件的節(jié)點(diǎn)號(hào)
6. 對(duì)有名來說，是映射的文件名。對(duì)匿名映射來說，是此段虛擬存儲(chǔ)器在進(jìn)程中的角色。[stack]表示在進(jìn)程中作為棧使用，[heap]表示堆。其余情況則無顯示

5. 缺頁異常處理

假如MMU在嘗試翻譯某個(gè)虛擬地址A時(shí)，沒有對(duì)應(yīng)的物理地址，則會(huì)觸發(fā)了一個(gè)缺頁異常。這個(gè)異常會(huì)導(dǎo)致控制轉(zhuǎn)移到內(nèi)核的缺頁異常處理程序，處理程序隨后執(zhí)行如下步驟：

1. 虛擬地址是合法的嗎？即虛擬地址是否在已分配的段的地址范圍內(nèi)。如果找不到就會(huì)觸發(fā)段錯(cuò)誤。
2. 試圖進(jìn)行的虛擬地址訪問是合法的嗎？即權(quán)限是否符合所在段的權(quán)限。如果沒有權(quán)限就會(huì)觸發(fā)保護(hù)異常。
3. 分配物理頁，更新頁表。缺頁處理程序返回時(shí)，CPU會(huì)重新執(zhí)行引起缺頁的指令。

通過執(zhí)行以下兩種的任意一種命令可查看某個(gè)進(jìn)程的缺頁中斷信息
ps -o majflt,minflt -C program_name
ps -o majflt,minflt -p pid
majflt和minor這兩個(gè)數(shù)值表示一個(gè)進(jìn)程自啟動(dòng)以來所發(fā)生的缺頁中斷的次數(shù)。
其中majflt與minflt的不同是，majflt表示需要讀寫磁盤，可能是內(nèi)存對(duì)應(yīng)頁面在磁盤中需要load到物理內(nèi)存中，也可能是此時(shí)物理內(nèi)存不足，需要淘汰部分物理頁面至磁盤中。

6. 內(nèi)存映射

linux通過將虛擬內(nèi)地段與一個(gè)磁盤上的文件關(guān)聯(lián)起來，以初始化這個(gè)虛擬存儲(chǔ)器段的內(nèi)容，這個(gè)過程稱之為內(nèi)存映射（memory mapping）。內(nèi)存映射有兩種：

1. 有名文件映射：一個(gè)段可以映射到一個(gè)普通磁盤文件的連續(xù)部分，例如一個(gè)可執(zhí)行文件。
2. 匿名文件映射：一個(gè)段也可以映射到一個(gè)匿名文件，匿名文件由內(nèi)核創(chuàng)建，包含的是全二進(jìn)制零。

###6.1 共享對(duì)象
內(nèi)存映射可以讓我們簡(jiǎn)單高效地把程序和數(shù)據(jù)加載到虛擬存儲(chǔ)器空間中。在實(shí)際中，許多進(jìn)程會(huì)映射同一個(gè)文件到內(nèi)存中，比如glic動(dòng)態(tài)庫，如果物理內(nèi)存中存在多份，那就是極端的浪費(fèi)。我們可以通過共享對(duì)象技術(shù)來消除浪費(fèi)。

對(duì)于私有對(duì)象，我們可以用寫時(shí)拷貝技術(shù)來共享物理內(nèi)存頁。

6.2 思考題

1. 能否通過動(dòng)態(tài)庫的全局變量在進(jìn)程間傳遞信息？
2. 進(jìn)程A使用動(dòng)態(tài)庫S，更新S版本，再啟動(dòng)使用S的進(jìn)程B后，進(jìn)程A是否還能正常訪問S的函數(shù)？

7. 動(dòng)態(tài)內(nèi)存分配

類unix操作系統(tǒng)下的動(dòng)態(tài)內(nèi)存分配器有很多，比如ptmalloc（linux默認(rèn)），tcmalloc（google出品），jemalloc（FreeBSD、NetBSD和firefox默認(rèn)）。這三種分配器的詳細(xì)介紹可以參考http://www.360doc.com/content/13/0915/09/8363527_314549128.shtml。
本文以ptmalloc為例介紹動(dòng)態(tài)內(nèi)存分配。在linux下os提供兩種動(dòng)態(tài)內(nèi)存分配brk和mmap。ptmalloc對(duì)于申請(qǐng)內(nèi)存小于128k的采用brk方式，大于128k的采用mmap方式。

7.1. mmap

對(duì)于大內(nèi)存，malloc會(huì)直接調(diào)用系統(tǒng)函數(shù)mmap分配內(nèi)存，以物理頁為最小單位做對(duì)齊。free會(huì)直接調(diào)用系統(tǒng)函數(shù)munmap釋放內(nèi)存。

7.2. brk

進(jìn)程有一個(gè)指針指向堆的頂部的地址，通過系統(tǒng)函數(shù)brk可以改變這個(gè)指針的位置，從而改變堆的大?。ǘ芽梢詳U(kuò)大也可以收縮）。當(dāng)已有的堆不能分配內(nèi)存時(shí)，brk會(huì)擴(kuò)大堆來分配動(dòng)態(tài)內(nèi)存。當(dāng)頂部的內(nèi)存被釋放，切釋放內(nèi)存大于128k，brk就會(huì)收縮堆，如下圖：

從上面的堆分配釋放方式，我們知道實(shí)際上很多小內(nèi)存申請(qǐng)后是不會(huì)馬上釋放給OS，為了將這些內(nèi)存重復(fù)利用，內(nèi)存分配器需要由一個(gè)算法，下面介紹下ptmalloc是如何處理的。

7.3. ptmalloc

ptmalloc通過chunk的數(shù)據(jù)結(jié)構(gòu)來組織每個(gè)內(nèi)存單元。當(dāng)我們使用malloc分配得到一塊內(nèi)存的時(shí)候，這塊內(nèi)存就會(huì)通過chunk的形式被記錄到glibc上并且管理起來。你可以把它想象成自己寫內(nèi)存池的時(shí)候的一個(gè)內(nèi)存數(shù)據(jù)結(jié)構(gòu)。chunk的結(jié)構(gòu)可以分為使用中的chunk和空閑的chunk。使用中的chunk和空閑的chunk數(shù)據(jù)結(jié)構(gòu)基本項(xiàng)同，但是會(huì)有一些設(shè)計(jì)上的小技巧，巧妙的節(jié)省了內(nèi)存。
使用中的chunk：

1. chunk指針指向chunk開始的地址；mem指針指向用戶內(nèi)存塊開始的地址。
2. p=0時(shí)，表示前一個(gè)chunk為空閑，prev_size才有效
3. p=1時(shí)，表示前一個(gè)chunk正在使用，prev_size無效 p主要用于內(nèi)存塊的合并操作
4. ptmalloc 分配的第一個(gè)塊總是將p設(shè)為1, 以防止程序引用到不存在的區(qū)域
5. M=1 為mmap映射區(qū)域分配；M=0為heap區(qū)域分配
6. A=1 為非主分區(qū)分配；A=0 為主分區(qū)分配

空閑的chunk結(jié)構(gòu)會(huì)復(fù)用User data來保存雙向鏈表指針。

ptmalloc一共維護(hù)了128bin。每個(gè)bins都維護(hù)了大小相近的雙向鏈表的chunk。
通過上圖這個(gè)bins的列表就能看出，當(dāng)用戶調(diào)用malloc的時(shí)候，能很快找到用戶需要分配的內(nèi)存大小是否在維護(hù)的bin上，如果在某一個(gè)bin上，就可以通過雙向鏈表去查找合適的chunk內(nèi)存塊給用戶使用。

1. fast bins。fast bins是bins的高速緩沖區(qū)，大約有10個(gè)定長(zhǎng)隊(duì)列。當(dāng)用戶釋放一塊不大于max_fast（默認(rèn)值64）的chunk（一般小內(nèi)存）的時(shí)候，會(huì)默認(rèn)會(huì)被放到fast bins上。當(dāng)用戶下次需要申請(qǐng)內(nèi)存的時(shí)候首先會(huì)到fast bins上尋找是否有合適的chunk，然后才會(huì)到bins上空閑的chunk。ptmalloc會(huì)遍歷fast bin，看是否有合適的chunk需要合并到bins上。
2. unsorted bin。是bins的一個(gè)緩沖區(qū)。當(dāng)用戶釋放的內(nèi)存大于max_fast或者fast bins合并后的chunk都會(huì)進(jìn)入unsorted bin上。當(dāng)用戶malloc的時(shí)候，先會(huì)到unsorted bin上查找是否有合適的bin，如果沒有合適的bin，ptmalloc會(huì)將unsorted bin上的chunk放入bins上，然后到bins上查找合適的空閑chunk。
3. small bins和large bins。small bins和large bins是真正用來放置chunk雙向鏈表的。每個(gè)bin之間相差8個(gè)字節(jié)，并且通過上面的這個(gè)列表，可以快速定位到合適大小的空閑chunk。前64個(gè)為small bins，定長(zhǎng)；后64個(gè)為large bins，非定長(zhǎng)。
4. Top chunk。并不是所有的chunk都會(huì)被放到bins上。top chunk相當(dāng)于分配區(qū)的頂部空閑內(nèi)存，當(dāng)bins上都不能滿足內(nèi)存分配要求的時(shí)候，就會(huì)來top chunk上分配。
5. mmaped chunk。當(dāng)分配的內(nèi)存非常大（大于分配閥值，默認(rèn)128K）的時(shí)候，需要被mmap映射，則會(huì)放到mmaped chunk上，當(dāng)釋放mmaped chunk上的內(nèi)存的時(shí)候會(huì)直接交還給操作系統(tǒng)。

7.3.1. 內(nèi)存分配malloc流程

1. 獲取分配區(qū)的鎖，防止多線程沖突。
2. 計(jì)算出需要分配的內(nèi)存的chunk實(shí)際大小。
3. 判斷chunk的大小，如果小于max_fast（64b），則取fast bins上去查詢是否有適合的chunk，如果有則分配結(jié)束。
4. chunk大小是否小于512B，如果是，則從small bins上去查找chunk，如果有合適的，則分配結(jié)束。
5. 繼續(xù)從 unsorted bins上查找。如果unsorted bins上只有一個(gè)chunk并且大于待分配的chunk，則進(jìn)行切割，并且剩余的chunk繼續(xù)扔回unsorted bins；如果unsorted bins上有大小和待分配chunk相等的，則返回，并從unsorted bins刪除；如果unsorted bins中的某一chunk大小 屬于small bins的范圍，則放入small bins的頭部；如果unsorted bins中的某一chunk大小 屬于large bins的范圍，則找到合適的位置放入。
6. 從large bins中查找，找到鏈表頭后，反向遍歷此鏈表，直到找到第一個(gè)大小 大于待分配的chunk，然后進(jìn)行切割，如果有余下的，則放入unsorted bin中去，分配則結(jié)束。
7. 如果搜索fast bins和bins都沒有找到合適的chunk，那么就需要操作top chunk來進(jìn)行分配了（top chunk相當(dāng)于分配區(qū)的剩余內(nèi)存空間）。判斷top chunk大小是否滿足所需chunk的大小，如果是，則從top chunk中分出一塊來。
8. 如果top chunk也不能滿足需求，則需要擴(kuò)大top chunk。主分區(qū)上，如果分配的內(nèi)存小于分配閥值（默認(rèn)128k），則直接使用brk()分配一塊內(nèi)存；如果分配的內(nèi)存大于分配閥值，則需要mmap來分配；非主分區(qū)上，則直接使用mmap來分配一塊內(nèi)存。通過mmap分配的內(nèi)存，就會(huì)放入mmap chunk上，mmap chunk上的內(nèi)存會(huì)直接回收給操作系統(tǒng)。

7.3.2. 內(nèi)存釋放free流程

1. 獲取分配區(qū)的鎖，保證線程安全。
2. 如果free的是空指針，則返回，什么都不做。
3. 判斷當(dāng)前chunk是否是mmap映射區(qū)域映射的內(nèi)存，如果是，則直接munmap()釋放這塊內(nèi)存。前面的已使用chunk的數(shù)據(jù)結(jié)構(gòu)中，我們可以看到有M來標(biāo)識(shí)是否是mmap映射的內(nèi)存。
4. 判斷chunk是否與top chunk相鄰，如果相鄰，則直接和top chunk合并（和top chunk相鄰相當(dāng)于和分配區(qū)中的空閑內(nèi)存塊相鄰）。轉(zhuǎn)到步驟8
5. 如果chunk的大小大于max_fast（64b），則放入unsorted bin，并且檢查是否有合并，有合并情況并且和top chunk相鄰，則轉(zhuǎn)到步驟8；沒有合并情況則free。
6. 如果chunk的大小小于 max_fast（64b），則直接放入fast bin，fast bin并沒有改變chunk的狀態(tài)。沒有合并情況，則free；有合并情況，轉(zhuǎn)到步驟7
7. 在fast bin，如果當(dāng)前chunk的下一個(gè)chunk也是空閑的，則將這兩個(gè)chunk合并，放入unsorted bin上面。合并后的大小如果大于64KB，會(huì)觸發(fā)進(jìn)行fast bins的合并操作，fast bins中的chunk將被遍歷，并與相鄰的空閑chunk進(jìn)行合并，合并后的chunk會(huì)被放到unsorted bin中，fast bin會(huì)變?yōu)榭?。合并后的chunk和topchunk相鄰，則會(huì)合并到topchunk中。轉(zhuǎn)到步驟8
8. 判斷top chunk的大小是否大于mmap收縮閾值（默認(rèn)為128KB），如果是的話，對(duì)于主分配區(qū)，則會(huì)試圖歸還top chunk中的一部分給操作系統(tǒng)。free結(jié)束。

7.4. 內(nèi)存碎片

造成堆利用率低的主要原因是碎片，當(dāng)雖然有未使用的內(nèi)存但不能用來滿足分配請(qǐng)求時(shí)，就會(huì)發(fā)生這種現(xiàn)象。有兩種形式的碎片：

1. 內(nèi)部碎片：已分配塊比有效載荷大。往往在實(shí)現(xiàn)內(nèi)存池或者自己管理內(nèi)存時(shí)會(huì)存在內(nèi)部碎片。
2. 外部碎片：空閑內(nèi)存合起來可以滿足分配要求，但是沒有一個(gè)單獨(dú)的空閑塊足夠大可以滿足分配請(qǐng)求。目前一些好的第三方分配器，如tcmalloc、jemalloc可以很好地解決外部碎片問題。

7.5. 思考題

####提問1：請(qǐng)問下面代碼運(yùn)行后，OS會(huì)立即分配1G物理內(nèi)存嗎？

#include <cstdlib>

int main()
{
    char *p = (char*)malloc(1024*1024*1024);
    while(1);
    return 0;
}

###提問2：請(qǐng)問下面代碼運(yùn)行后，OS會(huì)分配多少物理內(nèi)存？

#include <cstdlib>
#include <cstring>

int main()
{
    const size_t MAX_LEN = 1024*1024*1024;
    char *p = (char*)malloc(MAX_LEN);
    memset(p, 0, MAX_LEN/2);
    while(1);
    return 0;
}