第10章 虛擬存儲(chǔ)器 關(guān)鍵詞：虛擬存儲(chǔ)器，動(dòng)態(tài)存儲(chǔ)器分配，地址空間與多級(jí)頁(yè)表，空閑鏈表，伙伴系統(tǒng) 為了更加有效地管理存儲(chǔ)器并且少出錯(cuò)，現(xiàn)代系統(tǒng)提供了一種對(duì)主存的抽象概念，叫做虛擬存儲(chǔ)器（VM）。虛擬存儲(chǔ)器是硬件異常、硬件地址翻譯、主存、磁盤(pán)文件和內(nèi)核軟件的完美交互，它為每個(gè)進(jìn)程提供了一個(gè)大的、一致的、私有地址空間。通過(guò)一個(gè)很清晰的機(jī)制，虛擬存儲(chǔ)器提供了三個(gè)重要的能力：它將主存看成是一個(gè)存儲(chǔ)在磁盤(pán)上的地址空間的高速緩存，在主存中保存活動(dòng)區(qū)域，并根據(jù)需要在磁盤(pán)和主存之間來(lái)回傳送數(shù)據(jù)，通過(guò)這種方式，它高效地使用了主存；它為每個(gè)進(jìn)程提供了一致的地址空間，從而簡(jiǎn)化了存儲(chǔ)器管理；它保護(hù)了每個(gè)進(jìn)程的地址空間不被其它進(jìn)程破壞。 10.1 物理和虛擬地址 計(jì)算機(jī)系統(tǒng)的主存被組織成一個(gè)M個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組。每字節(jié)都有一個(gè)唯一的物理地址（physical address，PA）。第一個(gè)字節(jié)的地址為0，接下來(lái)的字節(jié)地址為1，再下一個(gè)為2，以此類(lèi)推。給定這種簡(jiǎn)單的結(jié)構(gòu)，CPU訪(fǎng)問(wèn)存儲(chǔ)器的最自然的方式就是使用物理地址。我們把這種方式稱(chēng)為物理尋址（physical addressing）。 早期的PC使用物理尋址，而且諸如數(shù)字信號(hào)處理器、嵌入式微控制器以及Cray超級(jí)計(jì)算機(jī)這樣的系統(tǒng)仍然繼續(xù)使用這種尋址方式及。然而，為通用設(shè)計(jì)的現(xiàn)代處理器使用的是虛擬尋址（virtual addressing）。 根據(jù)虛擬尋址，CPU通過(guò)生成一個(gè)虛擬地址（virtual address，VA）來(lái)訪(fǎng)問(wèn)主存，這個(gè)虛擬地址在被送到存儲(chǔ)器之前先轉(zhuǎn)換成適當(dāng)?shù)奈锢淼刂?。講一個(gè)虛擬地址轉(zhuǎn)換為物理地址的任務(wù)叫做地址翻譯（address translation）。就像異常處理一樣，地址翻譯需要CPU硬件和操作系統(tǒng)之間的緊密合作。CPU芯片叫做MMU（memory management unit，存儲(chǔ)器管理單元）的專(zhuān)用硬件，利用存放在主存中的查詢(xún)表來(lái)動(dòng)態(tài)翻譯虛擬地址，該表的內(nèi)容是由操作系統(tǒng)管理的。 10.2 地址空間 地址空間（address space）是一個(gè)非負(fù)整數(shù)地址的有序集合：{0，1，2……}。 如果地址空間中的整數(shù)是連續(xù)的，我們說(shuō)它是一個(gè)線(xiàn)性地址空間（linear address space）。為了簡(jiǎn)化討論，總是假設(shè)使用的是線(xiàn)性地址空間。在一個(gè)帶虛擬存儲(chǔ)器的系統(tǒng)中，CPU從一個(gè)有N=2^n個(gè)地址的空間中生成虛擬地址，這個(gè)地址空間被稱(chēng)為虛擬地址空間（virtual address space）:{0，1，2，……，N-1}。 一個(gè)地址空間的大小是由表示最大地址所需要的位數(shù)來(lái)描述的。例如，一個(gè)包含N=2^n個(gè)地址的虛擬地址空間就叫做一個(gè)n位地址空間。 一個(gè)系統(tǒng)還有一個(gè)物理地址空間（physical?address space），它與系統(tǒng)中物理存儲(chǔ)器的M個(gè)字節(jié)相對(duì)應(yīng)：{0，1，2，……，M-1}。 10.3 虛擬存儲(chǔ)器作為緩存的工具 1 虛擬存儲(chǔ)器基本概念 虛擬存儲(chǔ)器被組織為一個(gè)由存放在磁盤(pán)上的N個(gè)連續(xù)的N個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組。每字節(jié)都有一個(gè)唯一的虛擬地址，這個(gè)唯一的虛擬地址是作為到數(shù)組的縮印的。磁盤(pán)上數(shù)組的內(nèi)容被緩存在主存中。和存儲(chǔ)器層次結(jié)構(gòu)中的其它緩存一樣，磁盤(pán)（較低層）上的數(shù)據(jù)被分割成塊，這些塊作為磁盤(pán)和主存（較高層）之間的傳輸單元。VM系統(tǒng)通過(guò)將虛擬存儲(chǔ)器分割為稱(chēng)為虛擬也（virtual page，VP）的大小固定的塊，來(lái)處理這個(gè)問(wèn)題。每個(gè)虛擬頁(yè)的大小為P=2^p字節(jié)。類(lèi)似地，物理存儲(chǔ)器被分割為物理頁(yè)（physical page，PP），大小也為P字節(jié)（物理頁(yè)也被稱(chēng)為頁(yè)幀，page frame）。 在任何時(shí)刻，虛擬頁(yè)面的集合都分為三個(gè)不相交的子集： 未分配的：VM系統(tǒng)還未分配（或者創(chuàng)建）的頁(yè)。未分配的塊沒(méi)有任何數(shù)據(jù)和它們相關(guān)聯(lián)，因此也就不占用任何磁盤(pán)空間。 緩存的：當(dāng)前緩存在物理存儲(chǔ)器中的已分配頁(yè)。 未緩存的：沒(méi)有緩存在物理存儲(chǔ)器中的已分配頁(yè)。 2 DRAM高速緩存的組織結(jié)構(gòu) 在存儲(chǔ)器層次結(jié)構(gòu)中，DRAM緩存的位置對(duì)它的組織結(jié)構(gòu)有很大的影響?；叵胍幌拢篋RAM比SRAM要慢大約10倍，而磁盤(pán)要比DRAM慢大約100 000多倍。因此DRAM緩存中的不命中比起SRAM緩存中的不命中要昂貴的多，因?yàn)镈RAM緩存不命中要由磁盤(pán)來(lái)服務(wù)，而SRAM緩存不命中通常是由基于DRAM的主存來(lái)服務(wù)的。而且，從磁盤(pán)的一個(gè)山區(qū)讀取第一字節(jié)的時(shí)間開(kāi)銷(xiāo)比起讀這個(gè)扇區(qū)中后面的字節(jié)要慢大約100 000倍。歸根到底，DRAM緩存的組織結(jié)構(gòu)完全是由巨大的不命中開(kāi)銷(xiāo)驅(qū)動(dòng)的。 因?yàn)榇蟮牟幻刑幜P和訪(fǎng)問(wèn)第一字節(jié)的開(kāi)銷(xiāo)，虛擬頁(yè)趨向于很大，典型地是4-8KB。由于大的不命中處罰，DRAM緩存是全相聯(lián)的，也就是說(shuō)，任何虛擬頁(yè)都可以放置在任何的物理頁(yè)中。不命中時(shí)的替換策略也很重要，因?yàn)樘鎿Q錯(cuò)了虛擬頁(yè)的處罰也非常之高。因此，比起硬件對(duì)SRAM緩存，操作系統(tǒng)對(duì)DRAM緩存使用了更復(fù)雜精密的替換算法。最后，因?yàn)閷?duì)磁盤(pán)的訪(fǎng)問(wèn)時(shí)間很長(zhǎng)，DRAM緩存總是使用寫(xiě)回（write-back），而不是直寫(xiě)（write-through）。 3 頁(yè)表 頁(yè)表將虛擬頁(yè)映射到物理頁(yè)。每次地址翻譯硬件將一個(gè)虛擬地址轉(zhuǎn)換為物理地址時(shí)，都會(huì)讀取頁(yè)表。操作系統(tǒng)負(fù)責(zé)維護(hù)也表的內(nèi)容，以及在次番禺DRAM之間來(lái)回傳送頁(yè)。 頁(yè)面中的話(huà)，就可以直接引用數(shù)據(jù)，如果發(fā)生了也不命中，即缺頁(yè)，就需要進(jìn)行頁(yè)面調(diào)度。常用的方法有按需頁(yè)面調(diào)度。 盡管在整個(gè)運(yùn)行過(guò)程中引用的不同頁(yè)面的綜述可能超出物理存儲(chǔ)器總的大小，但是局部性原則保證了在任意時(shí)刻，這些頁(yè)面將趨向于在一個(gè)較小的活動(dòng)頁(yè)面（active page）集合上工作，這個(gè)集合叫做工作集（working set）或者常駐集合（resident set）。在初始開(kāi)銷(xiāo)，也就是將工作頁(yè)面調(diào)度到存儲(chǔ)器中，之后，接下來(lái)對(duì)這個(gè)工作集的引用將導(dǎo)致命中，而不會(huì)產(chǎn)生額外的磁盤(pán)流量。 只要我們的程序有良好的局部性，虛擬存儲(chǔ)器系統(tǒng)就能工作的相當(dāng)好。但是，當(dāng)然不是所有的程序都能展現(xiàn)良好的時(shí)間局部性。如果工作集的大小超過(guò)了物理存儲(chǔ)器的大小，那么程序?qū)a(chǎn)生一種不幸的狀態(tài)，叫做顛簸（thrashing）。這時(shí)頁(yè)面將不斷換進(jìn)換出。 10.4 虛擬存儲(chǔ)器作為存儲(chǔ)器管理工具 虛擬地址是一個(gè)有用的機(jī)制，因?yàn)樗蟠蠛?jiǎn)化了存儲(chǔ)器管理，并提供了一種簡(jiǎn)單自然的保護(hù)存儲(chǔ)器的方法。 多個(gè)虛擬頁(yè)面可以映射到同一個(gè)共享的物理頁(yè)面上。 虛擬存儲(chǔ)器作用： 簡(jiǎn)化鏈接：獨(dú)立的地址空間允許每個(gè)進(jìn)程為它的存儲(chǔ)器映像使用相同的基本格式，而不管代碼和數(shù)據(jù)實(shí)際存放在物理存儲(chǔ)器的何處。 簡(jiǎn)化共享：獨(dú)立地址空間為操作系統(tǒng)提供了一個(gè)管理用戶(hù)進(jìn)程和操作系統(tǒng)自身之間共享的一致機(jī)制。一般而言，每個(gè)進(jìn)程都有自己私有的代碼、數(shù)據(jù)、堆以及棧區(qū)域，是不和其它進(jìn)程共享的。在這種情況下，操作系統(tǒng)創(chuàng)建頁(yè)表，將相應(yīng)的虛擬頁(yè)映射到不同的物理頁(yè)面。操作系統(tǒng)通過(guò)將不同進(jìn)程中的適當(dāng)?shù)奶摂M頁(yè)面映射到相同的物理頁(yè)面，從而安排多個(gè)進(jìn)程共享這部分代碼的一個(gè)拷貝。 簡(jiǎn)化存儲(chǔ)器分配：虛擬存儲(chǔ)器為用戶(hù)進(jìn)程提供一個(gè)簡(jiǎn)單的分配額外存儲(chǔ)器的機(jī)制。 簡(jiǎn)化加載：虛擬存儲(chǔ)器也使加載可執(zhí)行文件和已共享目標(biāo)文件到存儲(chǔ)器中變得容易。映射一個(gè)連續(xù)虛擬頁(yè)面的集合到任意一個(gè)文件中的任意一個(gè)位置的概念叫做存儲(chǔ)器映射（memory mapping）。 10.5 地址翻譯 PTE：頁(yè)表?xiàng)l目 多級(jí)頁(yè)表：第一，如果一級(jí)頁(yè)表中的一個(gè)PTE是空的，那么相應(yīng)的二級(jí)頁(yè)表就不會(huì)存在。這表現(xiàn)出一種巨大的潛在節(jié)約，因?yàn)閷?duì)于一個(gè)典型的程序，4GB的虛擬地址空間的大部分都會(huì)是未分配的。第二，只有一級(jí)頁(yè)表才需要總是在主存中。虛擬存儲(chǔ)器系統(tǒng)可以在需要時(shí)創(chuàng)建，并頁(yè)面調(diào)入或調(diào)出二級(jí)頁(yè)表，這就減少了主存的壓力。只有最經(jīng)常使用的二級(jí)頁(yè)表才需要緩存在主存中。 10.6 動(dòng)態(tài)存儲(chǔ)器分配 1 動(dòng)態(tài)存儲(chǔ)器分配 一個(gè)動(dòng)態(tài)存儲(chǔ)器分配器維護(hù)者一個(gè)進(jìn)程的虛擬存儲(chǔ)器區(qū)域，稱(chēng)為堆（heap）。在大多數(shù)的Unix系統(tǒng)中，堆是一個(gè)請(qǐng)求二進(jìn)制零的區(qū)域，它緊接在未初始化的bss區(qū)域后開(kāi)始，并向上生長(zhǎng)（向更高的地址）。對(duì)于每個(gè)進(jìn)程，內(nèi)核維護(hù)者一個(gè)變量brk（讀作“break”），它指向棧的頂部。 分配器將堆視為一組不同大小的塊（block）的集合來(lái)維護(hù)。每個(gè)塊就是一個(gè)連續(xù)的虛擬存儲(chǔ)器組塊（chunk），要么是已分配的，要么是空閑的。已分配塊顯式地保留為供應(yīng)用使用?？臻e塊保持空閑，知道它顯式地被應(yīng)用所分配。一個(gè)已分配的塊保持已分配狀態(tài)，直到它被釋放，這種釋放要么是應(yīng)用顯式執(zhí)行的，要么是存儲(chǔ)器分配器自身隱式執(zhí)行的。 2 分配器有兩種基本風(fēng)格 顯式分配器：要求應(yīng)用顯式地釋放任何已分配的塊。例如，C標(biāo)準(zhǔn)庫(kù)提供一種叫做malloc程序包的顯式分配器。C程序通過(guò)調(diào)用malloc分配一個(gè)塊，并通過(guò)調(diào)用free函數(shù)來(lái)釋放一個(gè)塊，C++中的new和delete操作符與C中的malloc和free相當(dāng)。 隱式分配器：在另一個(gè)方面，要求分配器檢測(cè)何時(shí)一個(gè)已分配塊不再被程序使用，然后就釋放這個(gè)塊。隱式分配器也叫做垃圾收集器（garbage collector），而自動(dòng)釋放未使用的已分配的塊的過(guò)程就做垃圾收集（garbage collection）。諸如，Lisp、ML以及Java之類(lèi)的高級(jí)語(yǔ)言就依靠垃圾收集來(lái)釋放已分配的塊。 使用動(dòng)態(tài)存儲(chǔ)器分配的重要原因是它們經(jīng)常到程序?qū)嶋H運(yùn)行時(shí)，才知道某些數(shù)據(jù)結(jié)構(gòu)的大小。 造成對(duì)利用率很低的主要原因是一種稱(chēng)為碎片（fragmentation）的現(xiàn)象，當(dāng)雖然有未使用的存儲(chǔ)器但不能用來(lái)滿(mǎn)足分配請(qǐng)求是，就發(fā)生這種現(xiàn)象。包括：內(nèi)部碎片（internal fragmentation）和外部碎片（external fragmentation）。 內(nèi)部碎片的量化是簡(jiǎn)單明了的，它就是已分配塊和它們的有效載荷之差的和。因此在任意時(shí)刻，內(nèi)部碎片的數(shù)量只取決于請(qǐng)求的模式和分配器的實(shí)現(xiàn)方式。 外部碎片是當(dāng)空閑存儲(chǔ)器合計(jì)起來(lái)足夠滿(mǎn)足一個(gè)分配請(qǐng)求，但是沒(méi)有一個(gè)單獨(dú)的空閑塊足夠大可以處理這個(gè)請(qǐng)求時(shí)發(fā)生的。因?yàn)橥獠克槠y以量化和不可能預(yù)測(cè)的，所以分配器典型地采用啟發(fā)式策略來(lái)試圖維持少量的大空閑塊，而不是維持大量的小空閑塊。 隱式空閑鏈表，空閑塊是通過(guò)頭部中的大小字段隱含地連接著的。分配器可以通過(guò)遍歷堆中所有的塊，從而間接地遍歷整個(gè)空閑塊的集合。 隱式空閑鏈表的優(yōu)點(diǎn)是簡(jiǎn)單。顯著的缺點(diǎn)是任何操作的開(kāi)銷(xiāo)，例如放置分配的塊，要求空閑鏈表的搜索與堆中已分配塊和空閑塊的總數(shù)呈線(xiàn)性關(guān)系。 很重要的一點(diǎn)就是意識(shí)到系統(tǒng)對(duì)齊要求和分配器對(duì)塊格式的選擇對(duì)分配器上的最小塊大小有強(qiáng)制的要求。沒(méi)有已分配塊或者空閑塊可以比這個(gè)最小值還小。 3 放置分配的塊（分配策略） 當(dāng)一個(gè)應(yīng)用請(qǐng)求一個(gè)k字節(jié)的塊時(shí)，分配器搜索空閑鏈表，查找一個(gè)足夠大、可以防止所請(qǐng)求塊的空閑塊。分配器執(zhí)行者中搜索的方式是由配置策略（placement policy）所確定的。一些常見(jiàn)的策略是首次適配（first fit）、下一次適配（next fit）和最佳適配（best fit）。 首次適配：從頭開(kāi)始搜索空閑鏈表，選擇第一個(gè)合適的空閑塊。下一次適配和首次適配很相似，只不過(guò)不是從鏈表的起始處開(kāi)始每次搜索，而是從上一次查詢(xún)結(jié)束的地方開(kāi)始。最佳適配器檢查每個(gè)空閑塊，選擇匹配所需請(qǐng)求大小的最小空閑塊。 首次匹配的一個(gè)優(yōu)點(diǎn)是它趨于將大的空閑塊保留在表的后面。缺點(diǎn)是它區(qū)域在靠近鏈表起始處留下空閑塊的“碎片”，這就增加了對(duì)較大塊的搜索時(shí)間。最佳適配比首次適配和下一次適配的利用率要高一些。然而在簡(jiǎn)單空閑鏈表組織結(jié)構(gòu)中，比如隱式空閑鏈表中，使用最佳匹配的缺點(diǎn)是它對(duì)堆進(jìn)行徹底的搜索。在后面會(huì)有更加精細(xì)負(fù)載的分離式空閑鏈表組織，它實(shí)現(xiàn)了最佳適配策略，而不需要進(jìn)行徹底的堆搜索。 4 合并空閑塊 假碎片（fault fragmentation）：當(dāng)分配器釋放一個(gè)分配塊時(shí)，可能有其它空閑塊與這個(gè)新釋放的空閑塊相鄰。這些鄰接的空閑塊可能引起一種現(xiàn)象，叫做假碎片，這里有許多可用的空閑快被分割成為小的，無(wú)法使用的空閑塊。 立即合并（immediate coalescing）：每次一個(gè)塊被釋放，就合并所有相鄰塊。這種方式有可能會(huì)產(chǎn)生一種形式的抖動(dòng)，塊會(huì)反復(fù)地合并，然后馬上分割。反復(fù)地分配和釋放一個(gè)塊將產(chǎn)生大量不必要的分割和合并。所以快速的分配器通常會(huì)選擇某種形式的推遲合并。 延遲合并（deferred coalescing）：等到某個(gè)稍晚的時(shí)候再合并。如，可以在直到某個(gè)請(qǐng)求失敗后，然后掃描整個(gè)堆，合并所有的空閑塊。 5 隱式空閑鏈表 給定一個(gè)到頭部的隱式空閑鏈表，唯一的選擇將是搜索整個(gè)鏈表，記住前面的位置，直到我們達(dá)到當(dāng)前塊。使用隱式空閑鏈表，這意味著每次調(diào)用free的時(shí)間都與堆的大小成線(xiàn)性關(guān)系。即使使用更復(fù)雜精細(xì)的空閑鏈表組織，搜索時(shí)間也不會(huì)是常數(shù)。 Knuth提出了一種聰明而通用的技術(shù)，叫做邊界標(biāo)記（boundary tag），允許在常數(shù)時(shí)間內(nèi)進(jìn)行對(duì)前面塊的合并。這種思想，是在每個(gè)塊的結(jié)尾處添加一個(gè)腳部（footer邊界標(biāo)記），其中部步就是頭部的一個(gè)副本。如果每個(gè)塊包括這樣一個(gè)腳部，那么分配器就可以通過(guò)檢查前面一個(gè)塊的腳部，判斷前面一個(gè)塊的起始位置和狀態(tài)，需要注意的是，前面一個(gè)塊的腳部總是位于當(dāng)前塊起始位置的前一個(gè)字的距離處。 邊界標(biāo)記的概念是簡(jiǎn)單優(yōu)雅的，它對(duì)許多不同類(lèi)型的分配器和空閑鏈表組織都是通用的。然而，它也存在一個(gè)潛在的缺陷，要求每個(gè)塊都保持一個(gè)頭部和一個(gè)腳部，在應(yīng)用程序操作許多個(gè)小塊時(shí)，會(huì)產(chǎn)生顯著的存儲(chǔ)器開(kāi)銷(xiāo)。幸運(yùn)的是，有一種非常聰明的邊界標(biāo)記的優(yōu)化方法，能夠使得在已分配塊中不再需要腳部。回想一下，當(dāng)我們?cè)噲D在存儲(chǔ)器中合并當(dāng)前塊以及前面的塊和后面的塊時(shí)，只有在前面的塊時(shí)空閑時(shí)，才會(huì)需要用到它的腳部。如果我們把前面塊的已分配/空閑位存放在當(dāng)前塊中多出來(lái)的低位中，那么已分配的塊就不需要腳部了，這樣我們就可以將這個(gè)多出來(lái)的空間用作有效載荷了。 6 顯式空閑鏈表 因?yàn)閴K分配與堆塊的總數(shù)呈線(xiàn)性關(guān)系，所以對(duì)于通用的分配器，隱式空閑鏈表是不適合的（盡管對(duì)于堆塊數(shù)量預(yù)先知道是很小的特殊的分配器來(lái)說(shuō)，它是比較好的）. 一種更好的方法是將空閑塊組織為某種形式的數(shù)據(jù)結(jié)構(gòu)。根據(jù)定義，程序是不需要一個(gè)空閑塊的主體，所以實(shí)現(xiàn)這個(gè)數(shù)據(jù)結(jié)構(gòu)的指針可以村販子啊這些空閑塊的主題里面。例如，堆可以組織成一個(gè)雙向空閑鏈表，在每個(gè)空閑塊中，都包含一個(gè)pred（祖先）和succ（后繼）指針。 使用雙向鏈表而不是隱式空閑鏈表，使首次適配的分配時(shí)間從塊綜述的線(xiàn)性時(shí)間減少到了空閑塊數(shù)量的線(xiàn)性時(shí)間。不過(guò)，釋放一個(gè)塊的時(shí)間可以是線(xiàn)性的，也可能是個(gè)常數(shù)，這取決于我們?cè)诳臻e鏈表中對(duì)塊排序所選擇的策略。 一種方法是用后進(jìn)先出（LIFO）的順序維護(hù)鏈表，將新釋放的塊放置在鏈表的開(kāi)始處。使用LIFO的順序和首次適配的放置策略，分配器會(huì)最先檢查最近使用的塊。在這種情況下，釋放一個(gè)塊，可以在常數(shù)時(shí)間內(nèi)完成。如果使用了邊界標(biāo)記，那么合并也可以在常數(shù)時(shí)間內(nèi)完成。 另一種方法是按照地址順序來(lái)維護(hù)鏈表，其中鏈表中每個(gè)塊的地址都小于它祖先的地址。在這種情況下，釋放一個(gè)塊需要線(xiàn)性時(shí)間的搜索，來(lái)定位合適的祖先。平衡點(diǎn)在于，按照地址排序的首次適配比LIFO排序的首次適配有更高的存儲(chǔ)器利用率，接近最佳適配的利用率。 一般而言，顯式鏈表的缺點(diǎn)是空閑塊必須足夠大，以包含所需要的指針，以及頭部和可能的腳部，這就導(dǎo)致了更大的最小塊大小，也潛在地提高了內(nèi)部碎片的程度。 7 分離的空閑鏈表 一個(gè)單項(xiàng)的空閑鏈表的分配器需要與空閑塊數(shù)量成線(xiàn)性關(guān)系的時(shí)間來(lái)分配塊。一種流行的減少分配時(shí)間的方法，通常稱(chēng)為分離存儲(chǔ)（segregated storage），維護(hù)多個(gè)空閑鏈表，其中每個(gè)鏈表中的塊有大致相等的大小。 主要有兩種：簡(jiǎn)單分離存儲(chǔ)（simple segregated storage）和分離適配（segregated fit） 簡(jiǎn)單分離存儲(chǔ)（simple segregated storage）：使用簡(jiǎn)單分離存儲(chǔ)，每個(gè)大小類(lèi)的空閑鏈表包含大小相等的塊，每個(gè)塊的大小就是這個(gè)大小類(lèi)中最大元素的大小。其優(yōu)點(diǎn)是分配和釋放都很簡(jiǎn)單，缺點(diǎn)是容易造成內(nèi)部和外部碎片。因?yàn)榭臻e塊是不會(huì)被分割的，所以可能會(huì)造成內(nèi)部碎片。更糟的是，某些引用模式會(huì)引起極多的外部碎片，因?yàn)槭遣粫?huì)合并空閑塊的。 分離適配（segregated fit）：分配器維護(hù)一個(gè)空閑鏈表的數(shù)組。每個(gè)空閑鏈表是和一個(gè)大小類(lèi)相關(guān)聯(lián)的，并且被組織成某種類(lèi)型的顯式或隱式鏈表。每個(gè)鏈表包含潛在的大小不同的塊，這些快的大小是大小類(lèi)的成員。下面一種簡(jiǎn)單的版本是：為了分配一個(gè)塊，我們必須確定請(qǐng)求類(lèi)的大小，并且對(duì)適當(dāng)?shù)目臻e鏈表做首次適配，查找合適的塊。如果找到一個(gè)，我們（可選地）分割它，并將剩余的部分插入到適當(dāng)?shù)目臻e鏈表中。如果找不到，我們就搜索下一個(gè)更大的大小類(lèi)的空閑鏈表。如此重復(fù)，直到找到一個(gè)合適的塊。如果沒(méi)有空閑鏈表中有合適的塊，那么就向操作系統(tǒng)請(qǐng)求額外的對(duì)存儲(chǔ)器，從這個(gè)新的對(duì)存儲(chǔ)器中分配出一個(gè)塊，將剩余的部分放置在最大的大小類(lèi)中。要釋放一個(gè)塊，我們執(zhí)行合并，并將結(jié)果方知道相應(yīng)的空閑鏈表中。這種方法既快速，對(duì)存儲(chǔ)器的使用也很有效率。搜索時(shí)間減少了，因?yàn)樗阉鞅幌拗圃诙训哪硞€(gè)部分，而不是整個(gè)堆。存儲(chǔ)器利用了得到了改善，因?yàn)橛幸粋€(gè)有趣的事實(shí)：對(duì)分離空閑鏈表的簡(jiǎn)單的首次適配搜索相當(dāng)于整個(gè)堆的最佳適配搜索。 8?伙伴系統(tǒng) 伙伴系統(tǒng)（buddy system）是分離適配的一種特例，其中每個(gè)大小類(lèi)都是2的冪。基本的死里是假設(shè)一個(gè)對(duì)的大小是2^m個(gè)字。我們?yōu)槊總€(gè)塊大小2^k維護(hù)一個(gè)分離空閑鏈表，其中 ? ? ? ? ?0=<k<=m。請(qǐng)求塊大小向上舍入到最接近2的冪。最開(kāi)始時(shí)，只有一個(gè)大小為2^m個(gè)字的空閑塊。 伙伴系統(tǒng)分配器的主要優(yōu)點(diǎn)是它的快速搜索和快速合并。主要缺點(diǎn)是要求塊的大小為2的冪可能導(dǎo)致顯著的內(nèi)部碎片。因此伙伴系統(tǒng)分配器不適合通用目的的工作服在。然而，對(duì)于某些與應(yīng)用相關(guān)的工作負(fù)載，其中塊大小預(yù)先知道是2的冪，伙伴系統(tǒng)分配器就很有吸引力了。 10.7 垃圾收集 Mark&Sweep垃圾收集器由標(biāo)記（mark）階段和清除（sweep）階段組成。標(biāo)記階段標(biāo)記處根節(jié)點(diǎn)的所有可達(dá)的和已分配的后繼，而后面的清除階段釋放每個(gè)未被標(biāo)記的已分配塊。 想了解更多，請(qǐng)看后面的參考書(shū)籍。 10.8 C語(yǔ)言中常見(jiàn)的與存儲(chǔ)器有關(guān)的錯(cuò)誤 1 間接引用壞指針 在晉城的虛擬地址空間中有較大的洞，沒(méi)有映射到任何有意義的數(shù)據(jù)。如果我們?cè)噲D間接引用一個(gè)指向這些洞的指針，那么操作系統(tǒng)就會(huì)以段異常終止這個(gè)程序。而且，虛擬存儲(chǔ)的某些區(qū)域是只讀的。試圖寫(xiě)這些區(qū)域?qū)⒃斐梢员Ｗo(hù)異常終止這個(gè)程序。 間接引用壞指針的一個(gè)常見(jiàn)示例的經(jīng)典是scanf錯(cuò)誤。做正確的事情的方法是傳遞給scanf一個(gè)格式串和變量的地址： scanf（“%d”,&val） 而C程序員初學(xué)者，則很容易傳遞val的內(nèi)容，如 scanf（“%d”,val） 在這種情況下，scanf將把val的內(nèi)容解釋為一個(gè)地址，并試圖講一個(gè)字寫(xiě)到這個(gè)位置。在最好的情況下，程序立即以異常終止。最為糟糕的情況下，val的內(nèi)容對(duì)應(yīng)于虛擬存儲(chǔ)器的某個(gè)合法的讀/寫(xiě)區(qū)域，于是我們就覆蓋了存儲(chǔ)器，這通常會(huì)造成災(zāi)難性的、令人困惑的后果。 2 讀未初始化的存儲(chǔ)器 雖然.bbs存儲(chǔ)器位置（諸如未初始化的全局C變量）總是被加載器初始化為零，但是對(duì)于對(duì)存儲(chǔ)器卻并不是這樣的。 3 允許棧緩沖區(qū)溢出 如果一個(gè)程序不檢查輸入串的大小就寫(xiě)入棧中的目標(biāo)緩沖區(qū)，那么這個(gè)程序就會(huì)有緩沖區(qū)溢出錯(cuò)誤（buffer overflow bug）。 4 假設(shè)指針和他們指向的對(duì)象是相同大小的 5 造成錯(cuò)位錯(cuò)誤 錯(cuò)位（off-by-one）錯(cuò)誤是另一種常見(jiàn)的覆蓋性錯(cuò)誤發(fā)生的原因： 6 引用指針，而不是它所指向的對(duì)象 如果我們不太注意C操作符的優(yōu)先級(jí)和結(jié)合性，我們就會(huì)錯(cuò)誤地操作指針，而不是期望操作指針?biāo)赶虻膶?duì)象。 7 誤解指針運(yùn)算 忘記了指針的算術(shù)操作是以他們指向的對(duì)象的大小為單位來(lái)進(jìn)行的。 8 引用不存在的變量 不理解棧的規(guī)則，有時(shí)會(huì)引用不在合法的本地變量。 9 引用空閑堆塊中的數(shù)據(jù) 一個(gè)相似的錯(cuò)誤是引用已經(jīng)被釋放了的堆塊中的數(shù)據(jù)。 10 引起存儲(chǔ)器泄露 10.9 虛擬存儲(chǔ)器的幾個(gè)關(guān)鍵概念 一個(gè)關(guān)鍵的經(jīng)驗(yàn)教訓(xùn)是，即使虛擬存儲(chǔ)器是由系統(tǒng)自動(dòng)提供，它也是一種有限的存儲(chǔ)器資源，應(yīng)用程序必須精明地管理它。正如我們從對(duì)動(dòng)態(tài)存儲(chǔ)分配器的研究種學(xué)到的那樣，管理虛擬存儲(chǔ)器資源可能包括一些微妙的時(shí)間和空間的平衡。另一個(gè)關(guān)鍵的經(jīng)驗(yàn)教訓(xùn)是，在C程序中很容易犯與存儲(chǔ)器有關(guān)的錯(cuò)誤。壞的指針值，釋放已經(jīng)空閑了的塊、不恰當(dāng)?shù)膹?qiáng)制類(lèi)型轉(zhuǎn)換和只恨運(yùn)算，以及覆蓋堆結(jié)構(gòu)，這些只是可能給我們帶來(lái)麻煩的許多方式中的一小部分。實(shí)際上，與存儲(chǔ)器有關(guān)的錯(cuò)誤很討厭，這是導(dǎo)致Java產(chǎn)生的一個(gè)重要原因，Java取消了取變量地址的能力，完全控制了動(dòng)態(tài)存儲(chǔ)分配器，從而嚴(yán)格控制了對(duì)虛擬存儲(chǔ)器的訪(fǎng)問(wèn)。 10.10 小結(jié) 虛擬存儲(chǔ)器是對(duì)主存的一個(gè)抽象。支持虛擬存儲(chǔ)器的處理器通過(guò)使用一種叫做虛擬殉職的間接形式來(lái)引用主存。處理器產(chǎn)生一個(gè)虛擬地址，在被發(fā)送到主存之前，這個(gè)地址被翻譯成一個(gè)物理地址。從虛擬地址空間到物理地址空間的地址翻譯要求硬件和軟件緊密合作。專(zhuān)門(mén)的硬件通過(guò)使用頁(yè)表來(lái)翻譯虛擬地址，而頁(yè)表的內(nèi)容是由操作系統(tǒng)提供的。 虛擬存儲(chǔ)器提供三個(gè)重要的功能：第一，它在主存中自動(dòng)緩存最近使用的存放磁盤(pán)上的虛擬地址空間的內(nèi)容。虛擬存儲(chǔ)器緩存中的塊叫做頁(yè)。對(duì)磁盤(pán)上頁(yè)的引用會(huì)觸發(fā)缺頁(yè)，缺頁(yè)將控制轉(zhuǎn)移到操作系統(tǒng)中的一個(gè)缺頁(yè)處理程序。缺頁(yè)處理程序?qū)㈨?yè)面從磁盤(pán)拷貝到主存緩存，如果必要，將寫(xiě)回被驅(qū)逐的頁(yè)。第二，虛擬存儲(chǔ)器簡(jiǎn)化了存儲(chǔ)器管理，進(jìn)而又簡(jiǎn)化了鏈接、在進(jìn)程間共享數(shù)據(jù)、進(jìn)程的存儲(chǔ)器分配，以及程序加載。最后虛擬存儲(chǔ)器通過(guò)在每條頁(yè)表?xiàng)l目中加入保護(hù)位，從而簡(jiǎn)化了存儲(chǔ)器保護(hù)。 地址翻譯的過(guò)程將虛擬存儲(chǔ)器組塊（chunk）和磁盤(pán)上的文件塊關(guān)聯(lián)起來(lái)，來(lái)初始化虛擬存儲(chǔ)器組塊，這個(gè)郭晨剛成為存儲(chǔ)器映射。存儲(chǔ)器映射為共享數(shù)據(jù)、創(chuàng)建新的進(jìn)程以及加載程序，提供了一種高效的機(jī)制。應(yīng)用可以使用mmap函數(shù)來(lái)手工的創(chuàng)建和刪除虛擬地址空間的區(qū)域，然而，大多數(shù)程序依賴(lài)于動(dòng)態(tài)存儲(chǔ)分配器，例如malloc，它管理虛擬地址空間區(qū)域內(nèi)一個(gè)稱(chēng)為堆的區(qū)域。動(dòng)態(tài)存儲(chǔ)器分配器是一個(gè)有系統(tǒng)級(jí)感覺(jué)的應(yīng)用程序，它直接操作存儲(chǔ)器，而無(wú)需類(lèi)型系統(tǒng)的很多幫助。分配器有兩種類(lèi)型：顯式分配器要求應(yīng)用顯式地釋放它們的存儲(chǔ)器塊；隱式分配器（垃圾收集器）自動(dòng)釋放任何無(wú)用的和不可達(dá)的塊。 對(duì)于C程序員來(lái)說(shuō)，管理和使用虛擬地址儲(chǔ)存器是一件困難和容易出錯(cuò)的任務(wù)。常見(jiàn)的錯(cuò)誤示例包括：間接引用壞指針、讀取未初始化的存儲(chǔ)器，允許棧緩沖區(qū)溢出，假設(shè)指針和它們指向的對(duì)象大小相同，引用指針而不是它所指向的對(duì)象，誤解指針運(yùn)算，引用不存在的變量，以及引起存儲(chǔ)器泄露等問(wèn)題。[1]
PS：對(duì)于10.8部分，C語(yǔ)言中常見(jiàn)的錯(cuò)誤這一方面還需要看更加專(zhuān)業(yè)的書(shū)，本參考是也只是泛泛而談，還需要結(jié)合其它書(shū)籍來(lái)參考，如《C和指針》[2]《C陷阱與缺陷》[3]。如后面參考文獻(xiàn)所示。 參考文獻(xiàn) 布賴(lài)恩特, O'Hallaron D, et al. 深入理解計(jì)算機(jī)系統(tǒng)[M]. 中國(guó)電力出版社, 2004. Bryant R, David Richard O H, David Richard O H. Computer systems: a programmer's perspective[M]. Upper Saddle River: Prentice Hall, 2003. Reek K A. Pointers on C[M]. Addison-Wesley Longman Publishing Co., Inc., 1997. Koenig A. C traps and pitfalls[M]. Pearson Education India, 1988.