第三章 虛擬內(nèi)存
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
3.1 簡明信息理論
比特是二進(jìn)制的數(shù)字抄谐，也是信息的單位。一個比特有兩種可能的情況蜓萄，寫為0或者1盗扇。如果是兩個比特鲜屏，那就有四種可能的組合风范，00抵屿、01、10和11丐重。通常腔召，如果你有b個比特，你就可以表示2 ** b個值之一扮惦。一個字節(jié)是8個比特臀蛛，所以它可以儲存256個值之一。
從其它方面來講崖蜜，假設(shè)你想要儲存字母表中的字母浊仆。字母共有26個，所以你需要多少個比特呢豫领？使用4個比特你可以表示16個值之一抡柿，這是不夠的。使用5個比特你可以表示32個值等恐，這對于所有字母是夠用的沙绝，同時還有一點(diǎn)點(diǎn)浪費(fèi)。
通常鼠锈，如果你想要表示N個值之一闪檬，你就需要求出最小的b使2 ** b >= N。在兩邊計(jì)算以2為底的對數(shù)购笆，就會得到b >= log(2, N)粗悯。
假設(shè)我投擲一枚硬幣并且告訴你結(jié)果，我就向你提供了1比特的信息同欠。如果我投擲六個面的篩子并告訴你結(jié)果样傍，我就向你提供了log(2, 6)比特的信息。并且通常铺遂，如果結(jié)果的概率是1/n衫哥，結(jié)果應(yīng)該包含log(2, N)比特的信息。
同樣襟锐，如果結(jié)果的概率為p撤逢，那么信息的內(nèi)容為-log(2, p)。這個數(shù)量叫做“自信息”（self-information）粮坞。它度量了結(jié)果有多么令人意外蚊荣，所以也叫作“驚異度”。如果你的賽馬只有十六分之一的幾率獲勝莫杈，并且它獲勝了互例，那么你就得到了4比特的信息（以及獎金）。但是如果它的獲勝幾率為75%筝闹，這條新聞只含有0.42個比特媳叨。
可以由直覺得出腥光，非預(yù)期的新聞會帶有大量信息；與之相反糊秆，如果你對一件事情很有自信武福，對它的驗(yàn)證只會得到少量的信息。
對于書中的一些話題扩然，我們只需要熟練于在比特?cái)?shù)量b和它們所編碼的值的數(shù)量N = 2 ** b之間進(jìn)行轉(zhuǎn)換艘儒。
3.2 內(nèi)存（Memory）和儲存器（Storage）
當(dāng)進(jìn)程處于運(yùn)行期間，它的多數(shù)數(shù)據(jù)都放在“主存”（內(nèi)存）之中夫偶，它通常是一些隨機(jī)儲存器（RAM）界睁。在當(dāng)前的大多數(shù)電腦上，主存非常易失兵拢，也就是說翻斟，當(dāng)電腦關(guān)閉時，主存的內(nèi)容就沒了说铃。一個典型的臺式電腦擁有2~8GiB的內(nèi)存访惜。GiB代表“gibibyte”，相當(dāng)于2 ** 30個字節(jié)腻扇。
如果進(jìn)程會讀寫文件债热，這些文件通常放在機(jī)械硬盤（HDD）或固態(tài)硬盤（SSD）里面。這些儲存器都是非易失的幼苛，所以他們可用于長時間儲存窒篱。當(dāng)前，一個典型的臺式電腦擁有500GB到2TB的HDD舶沿。GB代表“gigabyte”墙杯，相當(dāng)于10 ** 9個字節(jié)。TB代表“terabyte”括荡，相當(dāng)于10 ** 12個字節(jié)高镐。
你可能會注意到我使用二進(jìn)制單位GiB來描述主存大小，并使用十進(jìn)制單位GB和TB來描述HDD的大小畸冲。由于歷史和技術(shù)因素嫉髓，內(nèi)存以二進(jìn)制單位度量，并且硬盤以十進(jìn)制單位度量召夹。本書中我會小心區(qū)分二進(jìn)制和十進(jìn)制單位岩喷，但是你應(yīng)該注意到“gigabyte”以及GB縮寫通常在使用上非常模糊。
非正式的用法中监憎，“內(nèi)存”有時會用于HDD和SSD（特別是移動設(shè)備），以及RAM婶溯。然而鲸阔，這些設(shè)備的屬性大相徑庭偷霉，所以我們需要區(qū)分它們。我會使用“儲存器”來指代HDD和SSD褐筛。
3.3 地址空間
主存中的每個字節(jié)都由一個“物理地址”整數(shù)所指定，物理地址的集合叫做物理“地址空間”渔扎。它的范圍通常為0到N-1硫狞，其中N是主存的大小晃痴。在帶有1GiB主存的的系統(tǒng)上，最高的有效地址是2 ** 30 - 1倘核，十進(jìn)制表示為1,073,741,823，16進(jìn)制表示為0x03ff ffff（前綴0x表示十六進(jìn)制）紧唱。
然而，許多操作系統(tǒng)提供“虛擬內(nèi)存”漏益，也就是說程序永遠(yuǎn)不需要處理物理地址，也不需要知道有多少物理內(nèi)存是有效的绰疤。
作為代替铜犬，程序處理虛擬地址峦睡，它被編碼為從0到M-1，其中M是有效虛擬地址的大小榨了。虛擬地址空間的大小取決于所處的操作系統(tǒng)和硬件。
你一定聽過人們談?wù)?2位和64位系統(tǒng)龙屉。這些術(shù)語表明了寄存器的尺寸，也通常是虛擬地址的大小转捕。在32位系統(tǒng)上，虛擬地址是32位的五芝，也就是說虛擬地址空間為從0到0xffff ffff痘儡。這一地址空間的大小是2 ** 32個字節(jié)，或者4GiB枢步。
在64位系統(tǒng)上沉删，虛擬地址空間大小為2 ** 64個字節(jié)渐尿，或者4 * 1024 ** 6個字節(jié)。這是16個EiB矾瑰，大約比當(dāng)前的物理內(nèi)存大十億倍砖茸。虛擬內(nèi)存比物理內(nèi)存大很多，這看上去有些奇怪殴穴，但是我們很快就就會看到它如何工作凉夯。
當(dāng)一個程序讀寫內(nèi)存中的值時，它使用虛擬地址采幌。硬件在操作系統(tǒng)的幫助下劲够，在訪問主存之前將物理地址翻譯虛擬地址。翻譯過程在進(jìn)程層級上完成植榕，所以即使兩個進(jìn)程訪問相同的虛擬地址再沧，它們所映射的物理地址可能不同。
因此尊残，虛擬內(nèi)存是操作系統(tǒng)隔離進(jìn)程的一種重要途徑炒瘸。通常，一個進(jìn)程不能訪問其他進(jìn)程的數(shù)據(jù)寝衫，因?yàn)闆]有任何虛擬地址能映射到其他進(jìn)程分配的物理內(nèi)存顷扩。
3.4 內(nèi)存段
一個運(yùn)行中進(jìn)程的數(shù)據(jù)組織為4個段：
-
text段包含程序文本，即程序所組成的機(jī)器語言指令慰毅、 -
static段包含由編譯器所分配的變量隘截，包括全局變量，和使用static聲明的局部變量汹胃。 -
stack段包含運(yùn)行時棧婶芭，它由棧幀組成。每個棧幀包含函數(shù)參數(shù)着饥、本地變量以及其它犀农。 -
heap段包含運(yùn)行時分配的內(nèi)存塊，通常通過調(diào)用C標(biāo)準(zhǔn)庫函數(shù)malloc來分配宰掉。
這些段的組織方式部分取決于編譯器呵哨，部分取決于操作系統(tǒng)。不同的操作系統(tǒng)中細(xì)節(jié)可能不同轨奄，但是下面這些是共同的：
-
text段靠近內(nèi)存“底部”孟害，即接近0的地址。 -
static段通常剛好在text段上面挨务。 -
stack段靠近內(nèi)存頂部，即接近虛擬地址空間的最大地址果漾。在擴(kuò)張過程中谷誓，它向低地址的方向增長吨凑。 -
heap通常在static段的上面。在擴(kuò)張過程中糙臼，它向高地址的方向增長恩商。
為了搞清楚這些段在你操作系統(tǒng)上的布局，可以嘗試運(yùn)行這個程序揽乱，它就是這本書的倉庫中的aspace.c：
#include <stdio.h>
#include <stdlib.h>
int global;
int main ()
{
int local = 5;
void *p = malloc(128);
printf ("Address of main is %p\n", main);
printf ("Address of global is %p\n", &global);
printf ("Address of local is %p\n", &local);
printf ("Address of p is %p\n", p);
}
main是函數(shù)的名稱粟矿，當(dāng)它用作變量時，它指向main中第一條機(jī)器語言指令的地址撒犀，我們認(rèn)為它在text段內(nèi)掏秩。
global是一個全局變量，所以我們認(rèn)為它在static段內(nèi)映凳。local是一個局部變量杆煞，所以我們認(rèn)為它在棧上。
p持有malloc所返回的地址队询，它指向堆區(qū)所分配的空間构诚。malloc代表“內(nèi)存分配”（memory allocate）。
格式化占位符%p告訴printf把每個地址格式化為“指針”送膳，它是地址的另一個名字。
當(dāng)我運(yùn)行這個程序時叠聋，輸出就像下面這樣（我添加了空格使它更加易讀）：
Address of main is 0x 40057c
Address of global is 0x 60104c
Address of local is 0x7fffd26139c4
Address of p is 0x 1c3b010
正如預(yù)期的那樣，main的地址最低虏束，隨后是global和p厦章。local的地址會更大，它是12個十六進(jìn)制數(shù)字汗侵，每個十六進(jìn)制數(shù)字對應(yīng)4比特群发，所以它是48位的地址。這表明虛擬內(nèi)存的可用部分為2 ** 48個字節(jié)宫屠。
作為一個練習(xí)滑蚯，你需要在你的電腦上運(yùn)行這個程序，并將你的結(jié)果與我的結(jié)果比較坤次。添加對malloc的第二個調(diào)用來檢查你系統(tǒng)上的堆區(qū)是否向上增長（地址更高）斥赋。添加一個函數(shù)來打印出局部變量的地址，檢查棧是否向下增長滑绒。
3.5 靜態(tài)局部變量
棧上的局部變量有時稱為“自動變量”隘膘，因?yàn)樗鼈儺?dāng)函數(shù)創(chuàng)建時自動被分配，并且當(dāng)函數(shù)返回時自動被釋放纵势。
C語言中又另一種局部變量，叫做“靜態(tài)變量”软舌，它分配在在static段上牛曹。它在程序啟動時初始化，并且在函數(shù)調(diào)用之間保存它的值恋脚。
例如焰手，下面的函數(shù)跟蹤了它所調(diào)用的次數(shù)：
int times_called()
{
static int counter = 0;
counter++;
return counter;
}
static關(guān)鍵字表示counter是靜態(tài)局部變量书妻。它的初始化只發(fā)生一次躬拢，就是程序啟動的時候。
如果你將這個函數(shù)添加到aspace.c工猜，你可以確定counter和全局變量一起分配在static段上菱蔬，而不是在棧上。
3.6 地址翻譯
虛擬地址（VA）如何翻譯成物理地址（PA）魏身？基本的機(jī)制十分簡單蚪腐，但是簡單的實(shí)現(xiàn)方式十分耗時，并且占據(jù)大量空間家制。所以實(shí)際的實(shí)現(xiàn)會復(fù)雜一點(diǎn)泡一。
大多數(shù)處理器提供了內(nèi)存管理單元（MMU），位于CPU和主存之間诅病。MMU在VA和PA之間執(zhí)行快速的翻譯。
- 當(dāng)程序讀寫變量時蝇棉，CPU會得到VA芥永。
- MMU將VA分成兩部分，稱為頁碼和偏移板辽〖撸“頁”是一個內(nèi)存塊，頁的大小取決于操作系統(tǒng)和硬件邑跪，通常為1~4KiB呼猪。
- MMU在“頁表”里查找頁碼，然后獲取相應(yīng)的物理頁碼轴踱。之后它將物理頁碼和偏移組合得到PA谚赎。
- PA傳遞給主存，用于讀寫指定地址嘁傀。
作為一個例子视粮，假設(shè)VA為32位，物理內(nèi)存為1GiB笑撞，劃分為1KiB的頁面。
- 由于1GiB為
2 ** 30個字節(jié)茴肥，物理頁的數(shù)量為2 ** 20個荡灾，它們也稱為“幀”瞬铸。 - 虛擬地址空間的大小為
2 ** 32字節(jié)嗓节，這個例子中皆警，頁的大小為2 ** 10字節(jié)，所以共有2 ** 22個虛擬頁鸵隧。 - 偏移的大小取決于頁的大小意推。這個例子中頁的大小為
2 ** 10字節(jié)，所以需要10位來指定頁中的一個字節(jié)靡羡。 - 如果VA是32位俊性，而偏移是10位定页，剩余的22位構(gòu)成了虛擬頁碼绽诚。
- 由于共有
2 ** 20個物理頁，每個物理頁碼是20位卒落。加上10位的偏移蜂桶，PA的結(jié)果為30位。
到目前為止腰湾，看上去是是可行的疆股。但是讓我們考慮一下頁表應(yīng)該占多大。頁表最簡單的實(shí)現(xiàn)是一個數(shù)組附井，每個虛擬頁面是一個條目。每個條目都包含一個物理頁碼永毅，在例子中它是20位，加上每幀的一些額外的數(shù)據(jù)节猿，所以我們認(rèn)為每個條目占用3~4個字節(jié)漫雕。由于共有2 ** 22個虛擬頁，頁面共需要2 ** 24個字節(jié)太雨，或16MiB。
由于我們需要為每個進(jìn)程創(chuàng)建一個頁表囊扳，一個運(yùn)行256個進(jìn)程的系統(tǒng)就需要2 ** 32個字節(jié)兜看，或者4GiB，這還只是頁面的空間细移！這些就占用了全部32位虛擬地址。而在48或64位的虛擬地址上雪侥，這個數(shù)量更加荒謬精绎。
幸運(yùn)的是，并不需要這么大的空間旬牲，因?yàn)榇蠖鄶?shù)進(jìn)程不使用虛擬地址空間的每個小片段襟己。而且，如果一個進(jìn)程不使用某個虛擬頁面员咽，我們也不需要在頁表中為其分配條目贮预。
也就是說契讲，頁表是“稀疏”的捡偏，這暗示了最簡單的實(shí)現(xiàn)峡迷，即頁表?xiàng)l目的數(shù)組是個糟糕的想法。幸運(yùn)的是彤避，稀疏數(shù)組有一些不錯的實(shí)現(xiàn)方式夯辖。
一種選擇是多級頁表，它被多數(shù)操作系統(tǒng)例如Linux所采用圆米。另一種選擇是關(guān)聯(lián)表，其中每個條目包含虛擬頁碼和物理頁碼啄栓。在軟件上搜索關(guān)聯(lián)表會非常慢，但是硬件上我們可以并行搜索整個表昙楚，所以關(guān)聯(lián)數(shù)組經(jīng)常用于在MMU中表示頁表。
你可以在頁表的維基百科頁面閱讀更多關(guān)于這些實(shí)現(xiàn)的信息。你也可能會找到有趣的細(xì)節(jié)崎场。但是基本的想法就是頁表應(yīng)做成稀疏的遂蛀，所以我們需要為稀疏數(shù)組選擇一個好的實(shí)現(xiàn)方式。
我之前提到了操作系統(tǒng)可以中斷一個運(yùn)行中的進(jìn)程螃宙，保存它的狀態(tài)所坯，之后運(yùn)行其它進(jìn)程。這個機(jī)制叫做“上下文切換”芹助。由于每個進(jìn)程都有自己的頁表闲先，操作系統(tǒng)需要和MMU配合來保證每個進(jìn)程拿到了正確的頁表伺糠。在舊機(jī)器上斥季，MMU中的頁表信息在每次上下文切換時會被替換掉，開銷非常大舵揭。在新的系統(tǒng)中灶挟，MMU的每個頁表?xiàng)l目包含進(jìn)程ID，所以多個進(jìn)程的頁表可以同時儲存在MMU中箱叁。
