第一章 計(jì)算機(jī)系統(tǒng)漫游
編譯系統(tǒng)
hello.c的文件中，每個(gè)字符都對(duì)應(yīng)一個(gè)ASCII碼，整個(gè)文件只有ASCII字符抖剿，這種文件為文本文件，其他都稱為二進(jìn)制文件识窿。
Unix系統(tǒng)上斩郎，編譯器通過(guò)預(yù)處理、編譯喻频、匯編缩宜、鏈接四個(gè)操作，將hello.c文本文件翻譯成hello可執(zhí)行文件（二進(jìn)制文件）。
預(yù)處理：將文件中#include包含的.h頭文本內(nèi)容插入到原文本中锻煌，獲得一個(gè)新的文本文件妓布，后綴為i；
編譯：將文本文件hello.i翻譯為文本文件hello.s宋梧，即匯編語(yǔ)言下的文件匣沼，如：
main:
mov $8,%rsp
call puts
ret
匯編：將文本文件hello.s翻譯為機(jī)器語(yǔ)言指令hello.o，被稱為可重定位目標(biāo)程序.
鏈接：若hello中調(diào)用了printf()函數(shù)捂龄，此函數(shù)位于printf.o的目標(biāo)文件中释涛，鏈接器將這兩個(gè)文件合并，生成一個(gè)新的hello可執(zhí)行文件倦沧，從而可以被加載到內(nèi)存中執(zhí)行
硬件組成
CPU：處理器不斷讀取PC指向的指令
PC:程序計(jì)數(shù)器
ALU：算術(shù)/邏輯單元唇撬，可能執(zhí)行的操作如下：
-加載：從主存復(fù)制字節(jié)到寄存器
-存儲(chǔ)：從寄存器復(fù)制字節(jié)到主存
-操作：將兩個(gè)寄存器的復(fù)制到ALU，計(jì)算結(jié)果存放在新寄存器中
-跳轉(zhuǎn)：
I/O總線：將適配器展融、主存窖认、CPU等連接起來(lái)
主存：臨時(shí)存儲(chǔ)設(shè)備，由一組動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器（DRAM）組成愈污，存放程序和程序處理的數(shù)據(jù)
高速緩存
CPU中的寄存器是主存讀取速度的近100倍耀态，為提高數(shù)據(jù)傳輸速度，基于數(shù)據(jù)的局部性原理暂雹，CPU中存在一個(gè)高速緩沖存儲(chǔ)器首装，一般包括L1、L2杭跪、L3三級(jí)仙逻，由靜態(tài)隨機(jī)存取存儲(chǔ)器（SRAM）組成。
按照如下順序涧尿，后一級(jí)為前一級(jí)的高速緩存：
寄存器 -> L1 -> L2 -> L3 -> 主存（DRAM） -> 本地二級(jí)存儲(chǔ)（磁盤） -> 遠(yuǎn)程二級(jí)存儲(chǔ)（分布式文件系統(tǒng)）
操作系統(tǒng)
操作系統(tǒng)處于應(yīng)用軟件與硬件之間系奉，作用：
-防止應(yīng)用軟件失控，對(duì)硬件造成破壞
-通過(guò)簡(jiǎn)單一致的方式使應(yīng)用軟件能夠操作硬件
操作系統(tǒng)通過(guò)進(jìn)程姑廉、虛擬內(nèi)存缺亮、文件這幾個(gè)抽象概念實(shí)現(xiàn)上述功能，抽象的內(nèi)容如下：
進(jìn)程：對(duì)執(zhí)行程序的一種抽象
-并發(fā)：兩個(gè)任務(wù)在同一個(gè)cpu上同時(shí)交錯(cuò)運(yùn)行
-并行：兩個(gè)任務(wù)在兩個(gè)cpu上分別同時(shí)運(yùn)行
虛擬內(nèi)存：為每個(gè)進(jìn)程提供獨(dú)占內(nèi)存地址的假象
文件：
第二章 信息的表示和處理
整數(shù)只能表示相對(duì)較小的一個(gè)范圍桥言，但是是精確的萌踱；分?jǐn)?shù)范圍較大，但是不精確号阿。
邏輯右移：左端補(bǔ)k個(gè)0并鸵；
算術(shù)右移：左端補(bǔ)k個(gè)最高有效位的值；
C語(yǔ)言中幾乎所有編譯器都對(duì)有符號(hào)數(shù)做算術(shù)右移扔涧，對(duì)無(wú)符號(hào)數(shù)做邏輯右移园担；java中>>為算術(shù)右移届谈，>>>為邏輯右移
整數(shù)表示
整數(shù)分有符號(hào)數(shù)和無(wú)符號(hào)數(shù)，對(duì)于位數(shù)表示【x[n-1],x[n-2]...,x[0]】,
無(wú)符號(hào)數(shù)結(jié)果為:
有符號(hào)數(shù)（即補(bǔ)碼表示）結(jié)果為：
可以看出有符號(hào)數(shù)第一位為1時(shí)弯汰，表示負(fù)數(shù)艰山，為0時(shí)表示正數(shù)
將k位的補(bǔ)碼x轉(zhuǎn)換為同一個(gè)位數(shù)表示下的無(wú)符號(hào)數(shù)（即強(qiáng)制轉(zhuǎn)換），
x>0時(shí)T2U(X) = x咏闪；
x<0時(shí)T2U(X) = x + 2^k程剥；
同理，將k位的無(wú)符號(hào)數(shù)x轉(zhuǎn)換為同一個(gè)位數(shù)表示下的補(bǔ)碼（即強(qiáng)制轉(zhuǎn)換）汤踏，
x>TMax時(shí)U2T(X) = x - 2^k；
x<=TMax時(shí)U2T(X) = x舔腾；
整數(shù)運(yùn)算
k位無(wú)符號(hào)數(shù)加法：
x+y<=UMax時(shí)溪胶，x+y -> x+y;
x+y>UMax時(shí)，x+y -> x+y-2^k;
c語(yǔ)言中不會(huì)對(duì)無(wú)符號(hào)數(shù)的加法移除拋異常稳诚，因此需要注意檢測(cè)計(jì)算結(jié)果是否發(fā)生溢出哗脖。
當(dāng)且僅當(dāng)s=x+y<x或者s=x+y<y時(shí)發(fā)生了溢出。
k位有符號(hào)數(shù)加法：
x+y<TMin時(shí)扳还，x+y -> x+y+2^k;
TMin<=x+y<=TMax時(shí)才避，x+y -> x+y;
x+y>TMax時(shí)，x+y -> x+y-2^k;
c語(yǔ)言中不會(huì)對(duì)有符號(hào)數(shù)的加法移除拋異常氨距，因此需要注意檢測(cè)計(jì)算結(jié)果是否發(fā)生溢出桑逝。
當(dāng)且僅當(dāng)x>0,y>0,x+y<0時(shí)，或者x<0,y<0,x+y>0時(shí),計(jì)算發(fā)生溢出俏让，分別為正溢出和負(fù)溢出楞遏。
注意：有符號(hào)數(shù)與無(wú)符號(hào)數(shù)的加法運(yùn)算是同樣的位級(jí)表示，因此可以把有符號(hào)數(shù)看作無(wú)符號(hào)數(shù)做計(jì)算首昔，最后將計(jì)算結(jié)果轉(zhuǎn)換為有符號(hào)數(shù)寡喝。
k位無(wú)符號(hào)數(shù)乘法
對(duì)于k位的無(wú)符號(hào)數(shù)x,y，相乘的結(jié)果可能需要截?cái)嗟絢位勒奇，即：
xy -> (xy) mod 2^k
k位有符號(hào)數(shù)乘法
對(duì)于k位的有符號(hào)數(shù)x,y预鬓，與無(wú)符號(hào)數(shù)相同，相乘的結(jié)果可能需要截?cái)嗟絢位赊颠，即：
xy -> (xy) mod 2^k
注意：有符號(hào)數(shù)與無(wú)符號(hào)數(shù)的乘法運(yùn)算是同樣的位級(jí)表示格二，因此可以把有符號(hào)數(shù)轉(zhuǎn)換為無(wú)符號(hào)數(shù)之后做計(jì)算，最后將計(jì)算結(jié)果轉(zhuǎn)換為有符號(hào)數(shù)巨税。
乘以常數(shù)
編譯器會(huì)通過(guò)移位和加法運(yùn)算代替乘法蟋定，如x15 = x8 + x4 + x2 + x*1,相當(dāng)于一次左移三位操作、一次左移兩位操作草添、一次左移一位操作和三次加法操作驶兜。
由于無(wú)符號(hào)數(shù)和有符號(hào)數(shù)的加法和位移運(yùn)算是位級(jí)相同的，所以都可以通過(guò)這種方式進(jìn)行計(jì)算。
小數(shù)表示
定點(diǎn)表示法：
對(duì)于二進(jìn)制表示下的m+n+1位的小數(shù)：
如 123351.231抄淑，表示結(jié)果為：12^5 + 22^4 + 32^3 + 32^2 + 52^1 + 12^0 + 12^0 + 22^(-1) + 32^(-2) + 12^(-3)屠凶。
浮點(diǎn)表示法：
頂點(diǎn)表示法不能有效表達(dá)比較大的數(shù)字，如5*2100是101后面接100個(gè)0肆资，因此矗愧，IEEE浮點(diǎn)標(biāo)準(zhǔn)決定用V=(-1)s * M * 2^E 來(lái)表示一個(gè)小數(shù)：
s：符號(hào)位，決定是正數(shù)（s=1）還是負(fù)數(shù)（s=0）
M：尾數(shù)郑原，是一個(gè)二進(jìn)制小數(shù)唉韭，由n位的小數(shù)字段frac進(jìn)行編碼
E：階碼，對(duì)浮點(diǎn)數(shù)加權(quán)犯犁，由k位的階碼字段exp進(jìn)行編碼
根據(jù)階碼的值属愤，可以分為如下三種情況：
情況1：規(guī)格化的值
此時(shí)，exp的位不全為0酸役，也不全為1住诸。
E = e - bias，e為exp表示的無(wú)符號(hào)數(shù)涣澡，bias為常量2^(k-1) - 1贱呐，表示偏置值。
M = 1 + f, f為frac作為二進(jìn)制小數(shù)部分入桂、且整數(shù)部分為0所組成的值奄薇。因?yàn)榭偸强梢哉{(diào)整階碼，使得M在(1事格，2]之間惕艳，第一位總是為1，所以可以省略表示驹愚，這種表示法稱為隱含的以1開頭的值
情況2：非規(guī)格化的值
此時(shí)远搪，exp的位全為0。
E = 1 - bias逢捺，bias為常量2^(k-1) - 1谁鳍，表示偏置值。
M = f, f為frac作為二進(jìn)制小數(shù)部分劫瞳、且整數(shù)部分為0所組成的值倘潜，不包含隱含的以1開頭的值。
非規(guī)格化的值可以表示0和非常接近0的值志于。
情況3：特殊值
此時(shí)涮因，exp的位全為1。
小數(shù)域全為0時(shí)伺绽，表示無(wú)窮养泡；否則表示NaN(not a number)嗜湃，即錯(cuò)誤值。
8位浮點(diǎn)數(shù)的浮點(diǎn)格式與數(shù)值表示示例如下圖：
可以看到最小規(guī)格化數(shù)8/512與最大非規(guī)格化數(shù)7/512之間是平滑過(guò)渡的.
舍入
對(duì)于一個(gè)數(shù)澜掩，如1.50购披，無(wú)法準(zhǔn)確用二進(jìn)制小數(shù)進(jìn)行表示，因此需要進(jìn)行舍入肩榕，舍入方法有以下幾種：向上舍入刚陡、向下舍入、向零舍入株汉、向偶數(shù)舍入筐乳。
如把1.5進(jìn)行舍入，結(jié)果如下：
第六章 存儲(chǔ)器層次結(jié)構(gòu)
儲(chǔ)存技術(shù)
隨機(jī)訪問(wèn)存儲(chǔ)器（Random-Access Memery, RAM）
靜態(tài)隨機(jī)存儲(chǔ)器（SRAM）：多用于高速緩存存儲(chǔ)器
動(dòng)態(tài)隨機(jī)存儲(chǔ)器（DRAM）：多用于主存
SRAM和DRAM都是易失性（斷電后會(huì)丟失信息）乔妈，SRAM性能優(yōu)于DRAM哥童。
磁盤存儲(chǔ)
磁盤是大數(shù)據(jù)的機(jī)械存儲(chǔ)設(shè)備，但是讀寫比DRAM慢了100萬(wàn)倍褒翰。磁盤構(gòu)造如下：
磁盤的讀寫速度主要包括三個(gè)部分：
尋道時(shí)間：移動(dòng)傳動(dòng)臂到磁道所需的時(shí)間
旋轉(zhuǎn)時(shí)間：盤片旋轉(zhuǎn)所需的時(shí)間
傳送時(shí)間：讀取內(nèi)容的時(shí)間，時(shí)間相對(duì)來(lái)說(shuō)很短匀泊。
磁盤控制器維護(hù)著邏輯塊號(hào)和實(shí)際（物理）磁盤扇區(qū)之間的映射關(guān)系优训，操作系統(tǒng)需要讀取數(shù)據(jù)時(shí)，只需要對(duì)邏輯塊號(hào)進(jìn)行操作各聘。
固態(tài)硬盤（Solid State Disk, SSD）
固態(tài)磁盤是大數(shù)據(jù)的電子存儲(chǔ)設(shè)備揣非，整體基于閃存，是一種非易失性的大數(shù)據(jù)存儲(chǔ)設(shè)備躲因。閃存由數(shù)據(jù)塊組成早敬，數(shù)據(jù)塊由數(shù)據(jù)頁(yè)組成，數(shù)據(jù)是以頁(yè)為單位進(jìn)行讀寫的大脉，只有一個(gè)頁(yè)被整個(gè)擦除后搞监，才會(huì)重新對(duì)這一頁(yè)進(jìn)行寫入。內(nèi)部是通過(guò)半導(dǎo)體存儲(chǔ)數(shù)據(jù)的镰矿，讀的速度快于寫的速度琐驴，而且都比旋轉(zhuǎn)磁盤快很多，但是閃存經(jīng)過(guò)反復(fù)寫后會(huì)磨損秤标，因此SSD更易磨損绝淡。
局部性原理
一個(gè)編寫良好的程序具有良好的局部性，即苍姜，更傾向于引用臨近于其最近引用過(guò)的數(shù)據(jù)項(xiàng)牢酵。局部性通常具有時(shí)間局部性和空間局部性這兩種形式：良好的時(shí)間局部性，指被引用過(guò)一次的存儲(chǔ)器位置在不遠(yuǎn)的將來(lái)可能被再次引用衙猪；良好的空間局部性馍乙，指如果一個(gè)存儲(chǔ)器位置被引用了一次布近，那么在不遠(yuǎn)的將來(lái)，程序很可能引用附近的一個(gè)存儲(chǔ)器位置潘拨。
上圖中吊输，代碼局部性的排序?yàn)椋篵 > c > d
存儲(chǔ)器層次結(jié)構(gòu)
上一級(jí)的存儲(chǔ)器以下一級(jí)的存儲(chǔ)器作為緩存，數(shù)據(jù)以塊為單位進(jìn)行緩存铁追，兩層之間的數(shù)據(jù)單位保持不變季蚂，但各層級(jí)之間不一致，如L0與L1之間的塊大小為1個(gè)字琅束，但L1與L2之間為幾十個(gè)字節(jié)扭屁。因?yàn)榈讓拥脑L問(wèn)時(shí)間較長(zhǎng)，為了彌補(bǔ)這些訪問(wèn)時(shí)間涩禀，因此傳送的數(shù)據(jù)塊比較大料滥。
緩存命中
程序需要k+1層的數(shù)據(jù)，獲取數(shù)據(jù)時(shí)在k層就成功獲得了艾船，那么這種情況稱為緩存命中葵腹。
緩存不命中
程序需要k+1層的數(shù)據(jù)，獲取數(shù)據(jù)時(shí)在k層失敗屿岂，k+1層才能獲取到践宴，那么這種情況稱為緩存不命中。此時(shí)會(huì)往k層中記錄這個(gè)塊的數(shù)據(jù)爷怀，當(dāng)k層中的數(shù)據(jù)塊滿了的時(shí)候阻肩，會(huì)驅(qū)逐一個(gè)塊并將這個(gè)新的塊寫入，決定替換哪個(gè)塊的方法被稱為犧牲策略运授。
（查詢緩存的具體方法參見原書）
第七章 鏈接
鏈接是將各種代碼和數(shù)據(jù)片段收集并組合成一個(gè)單一文件的過(guò)程烤惊，這個(gè)文件可被加載到內(nèi)存中并執(zhí)行。鏈接可執(zhí)行于編譯時(shí)吁朦，即原代碼被翻譯為機(jī)器代碼時(shí)柒室；也可以執(zhí)行于加載時(shí)，即被加載器加載到內(nèi)存中的時(shí)候逗宜；也可以執(zhí)行于運(yùn)行時(shí)伦泥。
鏈接器
鏈接是通過(guò)鏈接器進(jìn)行的，鏈接器將多個(gè)可重定位執(zhí)行文件組合為一個(gè)可執(zhí)行文件锦溪。
鏈接器的目標(biāo)文件分為三類：
可重定位目標(biāo)文件：包含二進(jìn)制代碼和目標(biāo)數(shù)據(jù)不脯，可以與其他可重定位目標(biāo)文件合并，生成可執(zhí)行目標(biāo)文件
可執(zhí)行目標(biāo)文件：包含二進(jìn)制代碼和目標(biāo)數(shù)據(jù)刻诊，可以直接復(fù)制到內(nèi)存中被執(zhí)行
共享目標(biāo)文件：特殊的可重定位目標(biāo)文件防楷，可以在運(yùn)行時(shí)被動(dòng)態(tài)加載到內(nèi)存中并進(jìn)行鏈接
鏈接器對(duì)目標(biāo)文件的解析主要包括下面兩個(gè)部分：
符號(hào)解析：目標(biāo)文件會(huì)定義自己的符號(hào)和引用外部的符號(hào)，符號(hào)指函數(shù)则涯、全局變量或者靜態(tài)變量复局。符號(hào)解析的作用是指將目標(biāo)文件的定義和引用關(guān)聯(lián)起來(lái)冲簿。
重定位：可重定位文件的起始地址為0，連接器把每個(gè)符號(hào)與其實(shí)際內(nèi)存地址進(jìn)行關(guān)聯(lián)亿昏，從而重定位這些節(jié)峦剔，進(jìn)而修改對(duì)這些符號(hào)的引用，使得他們指向?qū)嶋H位置角钩。
可重定位目標(biāo)文件
以.c文件對(duì)應(yīng)的.ELF文件為例：
其中每個(gè)方塊均稱為節(jié)吝沫，部分節(jié)的含義如下：
.text：已編譯程序的機(jī)器代碼
.dodata：只讀數(shù)據(jù)，如printf中的語(yǔ)句串
.data：已初始化的全局C變量（局部C變量保存在棧中递礼，不出現(xiàn)在.data或者.bss中）
.bss：未初始化的全局C變量
.symtab：符號(hào)表惨险，存放被定義和引用的函數(shù)和全局變量的信息
.rel.text：當(dāng)鏈接器把這個(gè)目標(biāo)文件和其他可執(zhí)行文件結(jié)合時(shí)，.text節(jié)中的很多位置都需要修改脊髓。一般來(lái)說(shuō)辫愉，任何調(diào)用外部函數(shù)或者引用全局變量的指令都需要修改，而調(diào)用本地函數(shù)的指令則不需要修改
.rel.data：被模塊定義或引用的任何全局變量的信息
符號(hào)解析
每個(gè)可重定位目標(biāo)文件m都有一個(gè)符號(hào)表（.symtab）将硝，包含文件m定義和引用的符號(hào)信息恭朗，具體分為三類：
-由m定義并由其他模塊引用的全局符號(hào)，對(duì)應(yīng)于非靜態(tài)的C函數(shù)和全局變量
-由其他模塊定義并由m引用的全局符號(hào)依疼，對(duì)應(yīng)于其他模塊中定義的非靜態(tài)的C函數(shù)和全局變量
-只被m定義和引用的局部符號(hào)冀墨，對(duì)應(yīng)于static屬性的C函數(shù)和全局變量
多重定義的全局符號(hào)
函數(shù)和已初始化的全局符號(hào)是強(qiáng)符號(hào)，未初始化的全局變量是弱符號(hào)涛贯，對(duì)于多重定義的全局符號(hào)，鏈接器的處理原則為：
-不允許多個(gè)強(qiáng)符號(hào)存在
-一個(gè)強(qiáng)符號(hào)與其他弱符號(hào)同名蔚出，使用強(qiáng)符號(hào)
-多個(gè)弱符號(hào)同名弟翘，任選一個(gè)弱符號(hào)
與靜態(tài)庫(kù)鏈接
對(duì)于一組可以被共同使用的標(biāo)準(zhǔn)函數(shù)目標(biāo)文件，需要采用一種方式將其與開發(fā)的可重定位目標(biāo)文件鏈接起來(lái)骄酗，鏈接方法有哪些呢稀余？
方法一：讓編譯器辨認(rèn)出標(biāo)準(zhǔn)函數(shù)，并直接生成相應(yīng)的代碼趋翻。但是這樣會(huì)顯著提高編譯器的復(fù)雜性睛琳，且每次增加新函數(shù)時(shí)都需要更新編譯器版本
方法二：將所有標(biāo)準(zhǔn)函數(shù)放到一個(gè)可重定位目標(biāo)文件中。但是這樣每個(gè)可執(zhí)行文件都會(huì)包括整個(gè)標(biāo)準(zhǔn)函數(shù)的目標(biāo)文件踏烙，這是對(duì)磁盤空間的巨大浪費(fèi)师骗，且每次增加新的函數(shù)時(shí)都需要重新編譯整個(gè)文件
方法三：靜態(tài)庫(kù)。相關(guān)的函數(shù)被編譯為單獨(dú)的目標(biāo)文件讨惩，再封裝到一個(gè)文件庫(kù)中辟癌，鏈接時(shí)，鏈接器只復(fù)制被用到的目標(biāo)模塊荐捻。（注：實(shí)際引用方法可參照原書）
重定位
符號(hào)解析完成后黍少，代碼中的每個(gè)符號(hào)和函數(shù)的引用和定義就都聯(lián)系起來(lái)了寡夹，接下來(lái)可以通過(guò)重定位，對(duì)模塊進(jìn)行合并厂置，并為每個(gè)符號(hào)分配運(yùn)行時(shí)地址菩掏。
匯編器生成一個(gè)目標(biāo)模塊時(shí)，它并不知道數(shù)據(jù)和代碼最終會(huì)被放到內(nèi)存的什么位置昵济，所以它會(huì)生成一個(gè)重定位條目智绸，告訴鏈接器目標(biāo)文件合并時(shí)將如何修改這個(gè)引用。代碼的重定位條目放在.rel.text中砸紊，已初始化數(shù)據(jù)的重定位條目在.rel.data中传于。（實(shí)際重定位的方案可 參照原書）
動(dòng)態(tài)鏈接庫(kù)
使用靜態(tài)鏈接庫(kù)時(shí)，開發(fā)人員需要了解到庫(kù)的更新情況醉顽，并顯式得進(jìn)行重新鏈接沼溜；另外，對(duì)于printf這種比較常用的函數(shù)游添，多個(gè)文件都會(huì)存在拷貝系草，這是對(duì)內(nèi)存資源的極大浪費(fèi)。共享庫(kù)是用來(lái)解決這些問(wèn)題的新產(chǎn)物唆涝。
共享庫(kù)是在程序執(zhí)行的時(shí)候動(dòng)態(tài)完成加載過(guò)程的找都，而不是像靜態(tài)庫(kù)一樣，在創(chuàng)建可執(zhí)行文件時(shí)靜態(tài)完成加載的廊酣，流程圖如下：
每個(gè)庫(kù)只有一個(gè).so文件能耻，所有引用該庫(kù)的可執(zhí)行目標(biāo)文件共享這個(gè)庫(kù)，另外亡驰，共享庫(kù)的.text節(jié)可以被不同的運(yùn)行中的進(jìn)行共享晓猛。
c語(yǔ)言中有一個(gè)接口，允許程序在運(yùn)行時(shí)動(dòng)態(tài)加載和鏈接共享鏈接庫(kù)：
Java中有一個(gè)調(diào)用規(guī)則：java本地方法（JNI）凡辱，允許Java程序調(diào)用本地的c和c++程序戒职，其基本思想是將本地C函數(shù)（如foo）編譯到一個(gè)共享庫(kù)中（foo.so），當(dāng)一個(gè)正在運(yùn)行時(shí)的Java試圖調(diào)用foo函數(shù)時(shí)透乾，解釋器利用dlopen或者類似的接口動(dòng)態(tài)加載foo.so洪燥，再調(diào)用foo。
第九章 虛擬內(nèi)存
計(jì)算機(jī)的主存是由M個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組乳乌，每個(gè)字節(jié)有一個(gè)唯一的物理地址捧韵，最直接的訪問(wèn)方式是直接使用物理地址進(jìn)行訪問(wèn)。
現(xiàn)代處理器使用了一種虛擬尋址的方式汉操。CPU通過(guò)生成虛擬地址訪問(wèn)主存纫版，這個(gè)地址被送到主存之前會(huì)先通過(guò)cpu中的內(nèi)存管理單元（memory management unit,MMU），進(jìn)行查詢主存中的查詢表來(lái)動(dòng)態(tài)翻譯地址客情，查詢表的內(nèi)容由操作系統(tǒng)進(jìn)行管理其弊。
地址空間
地址空間是一個(gè)非負(fù)整數(shù)地址的有序集合癞己，如{0，1梭伐，2痹雅，3，4糊识，...}绩社，一個(gè)包含N=2^n個(gè)地址的空間叫做n位地址空間，表示為{0赂苗，1愉耙，2，3拌滋，4朴沿，...，N -1}败砂，現(xiàn)代系統(tǒng)通常支持32位或者64位虛擬地址空間赌渣。
一個(gè)系統(tǒng)還存在一個(gè)物理地址空間，對(duì)應(yīng)于物理內(nèi)存中的M個(gè)字節(jié)昌犹，{0坚芜，1墨技，2钞楼，...，M-1}圆凰。
需要認(rèn)識(shí)到的是铸敏，每個(gè)數(shù)據(jù)對(duì)象都需要允許存在多個(gè)獨(dú)立的地址缚忧，其中每個(gè)地址都選自一個(gè)不同的地址空間，這就是虛擬內(nèi)存的基本思想搞坝。
虛擬內(nèi)存被組織為一個(gè)存放在磁盤上的N個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組，每個(gè)字節(jié)都有一個(gè)唯一的虛擬地址魁袜，作為到數(shù)組的索引桩撮。磁盤上的數(shù)組被緩存到主存中。類似于存儲(chǔ)器結(jié)構(gòu)中的緩存峰弹，磁盤（較低層）的數(shù)據(jù)被分割成塊店量，作為磁盤和主存（較高層）之間的傳輸單元，VM系統(tǒng)中鞠呈，虛擬內(nèi)存被分割為虛擬頁(yè)融师，物理內(nèi)存被分割為物理頁(yè)，兩種頁(yè)的大小相等蚁吝。
虛擬頁(yè)面的集合分為三個(gè)不相交的子集：
未分配的：VM系統(tǒng)還為分配（或創(chuàng)建）的頁(yè)旱爆，沒有數(shù)據(jù)與它們關(guān)聯(lián)舀射，不占用任何磁盤空間
未緩存的：未緩存在主存中的已分配頁(yè)
緩存的：已緩存在主存中的已分配頁(yè)
示例如下：
我們使用DRAM緩存表示主存中緩存的虛擬頁(yè)。
頁(yè)表：
頁(yè)表存放在主存中怀伦，操作系統(tǒng)通過(guò)MMU中的地址翻譯硬件和頁(yè)表脆烟，將虛擬頁(yè)的地址映射到物理頁(yè)，每次地址翻譯硬件將一個(gè)虛擬地址轉(zhuǎn)換為一個(gè)物理地址時(shí)房待，都會(huì)讀取頁(yè)表邢羔。
頁(yè)表是一個(gè)頁(yè)表?xiàng)l目（Page Table Entry）PTE的數(shù)組，可假定為由一個(gè)有效位和一個(gè)n位地址字段組成桑孩。
頁(yè)表查詢時(shí)命中示例如下：
當(dāng)VM根據(jù)虛擬地址需要讀取PTE2時(shí)拜鹤，查詢頁(yè)表得到有效位為1，表明對(duì)應(yīng)虛擬頁(yè)在內(nèi)存中已被緩存流椒，并將從內(nèi)存中讀取
頁(yè)表查詢時(shí)缺頁(yè)示例如下：
VM查詢頁(yè)表發(fā)現(xiàn)有效位為0敏簿，內(nèi)存中未緩存對(duì)應(yīng)的物理頁(yè)，將觸發(fā)一個(gè)缺頁(yè)異常镣隶。缺頁(yè)異常處理程序會(huì)選擇一個(gè)犧牲頁(yè)极谊，如下圖中的物理地址PP3，其中已經(jīng)緩存的虛擬頁(yè)VP4將被替換為新的虛擬頁(yè)VP3
接下來(lái)安岂，內(nèi)核會(huì)更新PTE3轻猖，并返回，重新啟動(dòng)導(dǎo)致缺頁(yè)的命令域那，這是VP3已經(jīng)緩存在主存中了咙边，因此將能夠從頁(yè)表中查詢到虛擬頁(yè)的數(shù)據(jù)。
需要注意的是次员，由于局部性的存在败许，程序趨向于在一個(gè)較小的活動(dòng)頁(yè)面集合上工作，這個(gè)集合稱為工作集淑蔚。初始開銷時(shí)市殷，工作集的頁(yè)面被調(diào)度到內(nèi)存中，接下來(lái)對(duì)虛擬內(nèi)存的大多數(shù)查詢將命中頁(yè)表中的PTE條目刹衫，從而能夠直接從內(nèi)存中獲取到數(shù)據(jù)頁(yè)醋寝。
操作系統(tǒng)為每一個(gè)進(jìn)程維護(hù)了一個(gè)頁(yè)表，多個(gè)虛擬頁(yè)面可以映射到同一個(gè)共享物理頁(yè)面上带迟。
按需頁(yè)面調(diào)度和獨(dú)立的虛擬地址空間的結(jié)合音羞，對(duì)系統(tǒng)中內(nèi)存的使用和管理具有深遠(yuǎn)的影響。
簡(jiǎn)化鏈接：獨(dú)立的地址空間允許每個(gè)進(jìn)程的內(nèi)存映像使用相同的基本格式仓犬，對(duì)于64位地址空間嗅绰，代碼總是從虛擬地址的0x400000開始，數(shù)據(jù)段跟在代碼段之后，中間存在一大段對(duì)齊空白窘面，棧占據(jù)用戶進(jìn)程地址空間的最高部分并向下生長(zhǎng)翠语。這種一致性極大簡(jiǎn)化了鏈接器的設(shè)計(jì)和實(shí)現(xiàn)。
簡(jiǎn)化加載：為將目標(biāo)文件中的.data和.text節(jié)加載到一個(gè)新創(chuàng)建的進(jìn)程中民镜，加載器為代碼和數(shù)據(jù)段分配虛擬頁(yè)啡专，將虛擬頁(yè)標(biāo)記為無(wú)效（即未緩存的）。加載器不會(huì)從磁盤復(fù)制數(shù)據(jù)到內(nèi)存制圈，每個(gè)頁(yè)被初次引用時(shí)们童，VM會(huì)自動(dòng)調(diào)入數(shù)據(jù)頁(yè)。
實(shí)際加載時(shí)鲸鹦，每次CPU產(chǎn)生一個(gè)虛擬地址慧库，MMU就必需查閱一次頁(yè)表中的PTE，即從CPU的訪問(wèn)時(shí)間（一個(gè)周期）減慢到主存的訪問(wèn)時(shí)間（幾百個(gè)周期）馋嗜，因此齐板，在查詢頁(yè)表之前，MMU中維護(hù)了一個(gè)小的PTE的緩存葛菇，稱為翻譯后備緩沖器（TLB）甘磨。TLB是一個(gè)小的虛擬尋址的緩存，每一行都保存著一個(gè)由單個(gè)PTE組成的塊眯停，如下圖济舆，VPN是用來(lái)查詢PTE的索引信息，VPO是偏移值莺债。
因此滋觉，實(shí)際查詢流程如下：
1.CPU產(chǎn)生一個(gè)虛擬地址
2+3.MMU從TLB中取出相應(yīng)的PTE
4.MMU將虛擬地址翻譯成物理地址，并發(fā)送到高速緩存/主存
5.高速緩存/主存返回?cái)?shù)據(jù)字到CPU
整個(gè)翻譯過(guò)程都在MMU中齐邦，速度很快椎侠。
不命中時(shí)，MMU必需從L1緩存中獲取PTE措拇。
（注：地址翻譯練習(xí)過(guò)程參照原書9.6）
linux虛擬內(nèi)存系統(tǒng)
linux為每個(gè)進(jìn)程維護(hù)了一個(gè)單獨(dú)的虛擬地址空間
其中我纪，最上方區(qū)域，即內(nèi)核虛擬內(nèi)存中與進(jìn)程相關(guān)的數(shù)據(jù)結(jié)構(gòu)如下：
這個(gè)數(shù)據(jù)結(jié)構(gòu)每個(gè)進(jìn)程都不相同丐吓，其中的pgd指向第一級(jí)頁(yè)表浅悉，vm_area_struct中具體包括以下字段：
vm_start:指向區(qū)域的起始處
vm_end:指向區(qū)域的結(jié)束處
vm_prot:指向區(qū)域包含所有頁(yè)的讀寫權(quán)限
vm_flags:指向區(qū)域是共享的還是私有的
vm_next:指向下一個(gè)區(qū)域
MMU翻譯虛擬地址時(shí)，會(huì)根據(jù)這個(gè)結(jié)構(gòu)觸發(fā)缺頁(yè)異常處理汰蜘，翻譯的地址可能有下面著三種情況：
內(nèi)存映射
linux將一個(gè)虛擬內(nèi)存區(qū)域與磁盤上的一個(gè)對(duì)象關(guān)聯(lián)起來(lái)仇冯，以初始化這個(gè)虛擬內(nèi)存區(qū)域的內(nèi)容之宿，這個(gè)過(guò)程稱為內(nèi)存映射族操。虛擬內(nèi)存
區(qū)域可以映射到兩種類型：
1.linux文件系統(tǒng)中的普通文件，如可執(zhí)行文件
2.匿名文件，匿名文件是由內(nèi)核創(chuàng)建出來(lái)的（如調(diào)用fork()函數(shù)時(shí)）色难，磁盤和內(nèi)存之間沒有數(shù)據(jù)傳送泼舱。
再看共享對(duì)象
一個(gè)對(duì)象被映射到虛擬內(nèi)存的一個(gè)區(qū)域時(shí)，這個(gè)對(duì)象可以作為共享對(duì)象枷莉，也可以作為私有對(duì)象娇昙。
如果一個(gè)進(jìn)程將一個(gè)共享對(duì)象映射到他的虛擬內(nèi)存中，進(jìn)程對(duì)這個(gè)共享對(duì)象的任何寫操作笤妙，對(duì)其他將此對(duì)象映射為共享對(duì)象的進(jìn)程冒掌，都是可見的。
而對(duì)于私有對(duì)象蹲盘，進(jìn)程的寫操作不會(huì)修改磁盤中的對(duì)象股毫。私有對(duì)象采用了寫時(shí)復(fù)制的技術(shù)，進(jìn)程不做寫操作時(shí)召衔，多個(gè)進(jìn)程就可以共享物理內(nèi)存中對(duì)象的同一個(gè)副本铃诬，但當(dāng)一個(gè)進(jìn)程試圖進(jìn)行寫操作時(shí)，會(huì)觸發(fā)一個(gè)保護(hù)故障苍凛，被寫的那個(gè)頁(yè)會(huì)在內(nèi)存中被復(fù)制趣席，生成一個(gè)副本，同時(shí)醇蝴，這個(gè)進(jìn)程的頁(yè)表會(huì)被更新宣肚。
再看fork函數(shù)
我們知道fork()函數(shù)會(huì)創(chuàng)建一個(gè)帶有自己獨(dú)立虛擬地址空間的新進(jìn)程，兩個(gè)進(jìn)程的虛擬內(nèi)存在最初是相同的哑蔫，當(dāng)任意一個(gè)進(jìn)程進(jìn)行了寫操作時(shí)钉寝，通過(guò)寫時(shí)復(fù)制的機(jī)制，將會(huì)創(chuàng)建一個(gè)新的頁(yè)面出來(lái)闸迷。
再看execve函數(shù)
execve函數(shù)通過(guò)內(nèi)存映射和虛擬內(nèi)存進(jìn)行加載和執(zhí)行程序嵌纲，如加載a.out函數(shù)分以下幾步：
刪除已存在的用戶區(qū)域
映射私有區(qū)域：為新程序的代碼、數(shù)據(jù)腥沽、.bss逮走、和棧創(chuàng)建新的區(qū)域結(jié)構(gòu)，這些區(qū)域都是私有的今阳、寫時(shí)復(fù)制的
映射共享區(qū)域：如標(biāo)準(zhǔn)C庫(kù)libc.so
設(shè)置程序計(jì)數(shù)器
mmap可以用來(lái)在進(jìn)程的虛擬內(nèi)存中創(chuàng)建新的虛擬內(nèi)存區(qū)域师溅，并將磁盤文件映射過(guò)來(lái)
