計(jì)算機(jī)系統(tǒng)虛擬內(nèi)存分享

前言

該分享文檔芽死，是基于《深入理解理解計(jì)算機(jī)系統(tǒng)》第三版關(guān)于內(nèi)存方面的總結(jié)签舞。下述所有模型圖草穆，在原書中均有示例祈惶。
由于這里主要分享虛擬內(nèi)存雕旨，關(guān)于物理內(nèi)存部分，簡(jiǎn)單描述

分享的主要問題

1. 計(jì)算機(jī)物理內(nèi)存層次結(jié)構(gòu)
2. 什么是虛擬內(nèi)存
3. 虛擬內(nèi)存的實(shí)現(xiàn)
4. 程序內(nèi)虛擬內(nèi)存分配和釋放

物理內(nèi)存

常見的存儲(chǔ)技術(shù)

在計(jì)算機(jī)體系中捧请，CPU執(zhí)行指令奸腺，而存儲(chǔ)器為CPU存放指令和數(shù)據(jù)。
實(shí)際上血久，計(jì)算機(jī)的存儲(chǔ)器系統(tǒng)是一個(gè)具有不同容量突照、成本和訪問時(shí)間的存儲(chǔ)設(shè)備層次結(jié)構(gòu)。
層次越高的存儲(chǔ)越快氧吐，價(jià)格越高讹蘑。例如若程序需要的數(shù)據(jù)存儲(chǔ)在CPU寄存器中末盔，在指令的執(zhí)行周期內(nèi)，0個(gè)周期內(nèi)就可以訪問到他們座慰；如果存儲(chǔ)在高速緩存中陨舱，需要4~75個(gè)周期；如果在主存上版仔，需要上百個(gè)周期游盲；而如果存儲(chǔ)在磁盤上，需要大約幾千萬個(gè)周期蛮粮。

隨機(jī)訪問存儲(chǔ)器

隨訪訪問存儲(chǔ)器（Random-Access Memory,RAM）分為兩類：靜態(tài)和動(dòng)態(tài)的金拒。

1. 靜態(tài)RAM：不需要刷新電路就能保存數(shù)據(jù)名秀，所以具有靜止存取數(shù)據(jù)作用据沈，多以多用在Cache崖叫。SRAM用來作為高速緩存存儲(chǔ)器，可以用在CPU芯片上变泄。
2. 動(dòng)態(tài)RAM：DRAM只需要一個(gè)電容和一個(gè)晶體管令哟，廉價(jià)，但是由于對(duì)于干擾敏感妨蛹，需要不斷刷新屏富。DRAM用來作為主存以及圖形系統(tǒng)的幀緩沖區(qū)。

SRAM比DRAM更快蛙卤，但是也貴的多役听。因此類似 MAC，SRAM不會(huì)超過幾兆字節(jié)表窘，但是DRAM卻有幾千兆字節(jié)典予。

DRAM芯片封裝在內(nèi)存模塊（Memeory Module）中，它可以插到主板卡槽上乐严，通過將多個(gè)內(nèi)存模塊連接到內(nèi)存控制器瘤袖，就聚合成了主存。為了降低芯片上地址引腳數(shù)量昂验，DRAM被組織成二維矩陣捂敌，而不是線性數(shù)組。因此在發(fā)送數(shù)據(jù)時(shí)候既琴，必須拆分兩步占婉，先選中行，然后將行數(shù)據(jù)存入一個(gè)鎖存器甫恩，然后等列地址傳數(shù)逆济，然后再選中所需數(shù)據(jù)。

數(shù)據(jù)流通過總線（bus）的共享電子電路在處理器和DRAM主存之間來來回回，每次CPU和主存之間的數(shù)據(jù)傳輸都是通過一系列步驟（總線事物）來完成的奖慌。主存到CPU為讀事物抛虫，CPU到主存為寫事物。

非易失性存儲(chǔ)器

DRAM和SRAM在斷電后會(huì)丟失信息简僧，非易失性存儲(chǔ)器（nonvolatile memory）為即使關(guān)電后建椰，仍然保存著它們的信息。這些存儲(chǔ)器雖然現(xiàn)在既可讀岛马，也可寫棉姐，但是由于歷史原因，仍然被稱為ROM（Read-Only Memory,ROM）
常見的ROM啦逆，包含：

1. PROM（Programmable ROM）伞矩，可編程式ROM，只能被編程一次
2. 可擦寫式ROM（Erasable Programmable ROM蹦浦，EPROM），可以多次使用撞蜂，常見的為光存儲(chǔ)和電子可擦除（EEPROM）
3. 閃存（Flash）盲镶，基于EEPROM

磁盤存儲(chǔ)

磁盤廣為應(yīng)用是保存大量數(shù)據(jù)的存儲(chǔ)設(shè)備，數(shù)量用百G記蝌诡，但是磁盤上讀信息時(shí)間為毫秒級(jí)溉贿，比DRAM讀滿了10萬倍，比SRAM讀慢了100萬倍浦旱。

常見旋轉(zhuǎn)磁盤（disk）和固態(tài)硬盤（Solid State Disk宇色，SSD）。其中固態(tài)硬盤是基于閃存的存儲(chǔ)技術(shù)颁湖，SSD讀比寫要快宣蠕。

SSD速度位于DRAM和旋轉(zhuǎn)磁盤之間。

如下圖甥捺，存儲(chǔ)器層次結(jié)構(gòu)的中心思想是抢蚀，對(duì)于每個(gè)K層，位于K層的更快更小的存儲(chǔ)設(shè)備作為用于位于K+1層的更大更慢的設(shè)備中的數(shù)據(jù)對(duì)象的緩沖區(qū)域镰禾。

局部性

一個(gè)編寫良好的計(jì)算機(jī)程序常常具有良好的局部性（locality）皿曲。也就是，它們傾向于引用臨近于其他最近引用過得數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng)吴侦，或者最近引用過的數(shù)據(jù)項(xiàng)本身屋休。這種傾向性被稱為局部性原理。

在一個(gè)擁有良好時(shí)間局部性的程序中备韧，被引用過一次的內(nèi)存位置很可能在不遠(yuǎn)的將來再次被多次引用劫樟。在一個(gè)擁有空間局部性的程序中，程序大概率會(huì)在不遠(yuǎn)的將來引用附近的一個(gè)內(nèi)存位置。

局部性原理：指CPU訪問存儲(chǔ)器時(shí)候毅哗，無論是存取指令還是存取數(shù)據(jù)听怕，所訪問的存儲(chǔ)單元都趨于聚集在一個(gè)較小的連續(xù)空間中。通常包含三種不同類型的局部性原理：

1. 時(shí)間局部性：如果一個(gè)數(shù)據(jù)被訪問虑绵，那么這個(gè)數(shù)據(jù)可能還會(huì)被再次訪問尿瞭，例如循環(huán)中的變量。
2. 空間局部性：在未來（最近的）將會(huì)用到的信息與正在使用的信息在空間上是鄰近的（步長(zhǎng)）翅睛。
3. 工作集理論：進(jìn)程訪問時(shí)被頻繁訪問的頁面集合声搁，在同一時(shí)間內(nèi)不會(huì)馬上替換出去。

現(xiàn)代計(jì)算機(jī)系統(tǒng)的各個(gè)層次捕发，從硬件到操作系統(tǒng)疏旨，在到應(yīng)用程序，他們的設(shè)計(jì)都利用了局部性原理扎酷。在硬件層檐涝，局部性原理允許計(jì)算機(jī)設(shè)計(jì)者通過引入高速緩存存儲(chǔ)來保存最近被引用的指令和數(shù)據(jù)項(xiàng)。

在操作系統(tǒng)級(jí)法挨，局部性原理允許系統(tǒng)使用主存作為虛擬地址空間被引用塊的高速緩存谁榜。

虛擬內(nèi)存簡(jiǎn)介

在介紹虛擬內(nèi)存之前，我們先來看一張工作中常被問到的圖

在這張圖中凡纳，有我們?nèi)粘ｉ_發(fā)中窃植，經(jīng)常提到的堆棧，然而在上述的物理內(nèi)存中荐糜，并不存在這樣的概念巷怜。所謂的堆棧，其實(shí)是在虛擬內(nèi)存中抽象的一個(gè)概念暴氏。

虛擬內(nèi)存是強(qiáng)大的延塑，它給予應(yīng)用程序強(qiáng)大的能力，可以創(chuàng)建和釋放內(nèi)存片（chunk）答渔，進(jìn)程之間也可以通過內(nèi)存片映射共享內(nèi)存页畦。

同時(shí)虛擬內(nèi)存也是核心的，它遍布計(jì)算機(jī)系統(tǒng)所有層面研儒，在硬件異常豫缨、匯編器、鏈接器端朵、加載器好芭、共享對(duì)象、文件和進(jìn)程的設(shè)計(jì)中扮演著重要角色冲呢。

在計(jì)算機(jī)系統(tǒng)中舍败，每次程序引用一個(gè)變量、間接引用一個(gè)指針、或者調(diào)用malloc或free方法時(shí)候邻薯，都是在和虛擬內(nèi)存發(fā)生交互裙戏。

下面我們就正式介紹虛擬內(nèi)存。

虛擬內(nèi)存是什么

首先要強(qiáng)調(diào)下虛擬的概念厕诡，它是抽象的累榜，不是實(shí)際存在的。

一個(gè)系統(tǒng)中的進(jìn)程是與其他進(jìn)程共享CPU和主存資源的灵嫌。隨著對(duì)CPU需求的增長(zhǎng)壹罚，進(jìn)程以某種合理的平滑的方式慢了下來。但是如果太多的進(jìn)程需要太多的內(nèi)存寿羞，那么它們中的一些就根本無法運(yùn)行猖凛。當(dāng)一個(gè)程序中沒有空間可以用時(shí)，那就是它運(yùn)氣不好了绪穆。內(nèi)存還容易被破壞辨泳。如果某個(gè)進(jìn)程不小心寫了另一個(gè)進(jìn)程使用的內(nèi)存，它就可能以某種完全和程序邏輯無關(guān)的令人迷惑的方式失敗玖院。

虛擬內(nèi)存（VM）是硬件異常菠红、硬件地址翻譯、主存司恳、磁盤文件和內(nèi)核軟件完美交互途乃，是現(xiàn)代計(jì)算機(jī)為了更加有效管理內(nèi)存并減少出錯(cuò)绍傲，提供的一種對(duì)主存的抽象概念扔傅。

虛擬內(nèi)存的關(guān)鍵能力

虛擬內(nèi)存的關(guān)鍵能力：

1. 它將主存看成是一個(gè)存儲(chǔ)在磁盤上的地址空間的高速緩存，在主存中只保存活動(dòng)區(qū)域烫饼，并根據(jù)需要在磁盤和主存之間來回傳送數(shù)據(jù)猎塞，通過這種方式，高效的使用了主存杠纵。
2. 它為每個(gè)進(jìn)程提供了一致的地址空間荠耽，從而簡(jiǎn)化了內(nèi)存管理。
3. 它保護(hù)了每個(gè)進(jìn)程的地址空間不被其他進(jìn)程破壞比藻。

物理尋址

計(jì)算機(jī)系統(tǒng)的主存被組織成一個(gè)有M個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組铝量。每字節(jié)都有一個(gè)唯一的物理地址（PA）。第一個(gè)字節(jié)的物理地址為0银亲，接下來的字節(jié)地址為1究反，再下來為2敷钾，依次類推。給定這種簡(jiǎn)單的結(jié)構(gòu)，CPU訪問內(nèi)存的最自然的方式就是使用物理地址僵芹。我們把這種方式稱為物理尋址（physical addressing）荧库。

早期的PC使用的是物理地址，而且諸如數(shù)字信號(hào)處理器、嵌入式微控制器以及Cray超級(jí)計(jì)算機(jī)這樣的系統(tǒng)仍然還是繼續(xù)使用這種尋址方式践瓷。

虛擬尋址

使用虛擬地址，CPU通過生成一個(gè)虛擬地址（Virtual Address亡蓉，VA）來訪問主存晕翠，這個(gè)虛擬地址在被送到內(nèi)存之前先轉(zhuǎn)換成適當(dāng)?shù)奈锢淼刂贰⑦@個(gè)虛擬地址轉(zhuǎn)換成物理地址的任務(wù)叫做地址翻譯（address translation）寸宵。就像異常處理一樣崖面，地址翻譯需要CPU硬件和操作系統(tǒng)的緊密合作。CPU芯片上叫做內(nèi)存管理單元（MMU）的專有硬件梯影，利用存放主存中的查詢表來動(dòng)態(tài)的翻譯虛擬地址巫员，該表的內(nèi)容由操作系統(tǒng)來管理。

虛擬內(nèi)存映射

地址空間

地址空間是一個(gè)非負(fù)整數(shù)的有序集合{0甲棍，1简识，2，.......}感猛。如果地址空間中的整數(shù)是連續(xù)的七扰，那么我們說它是一個(gè)線性的連續(xù)地址空間。

在一個(gè)帶有虛擬內(nèi)存的系統(tǒng)中陪白，CPU從一個(gè)由N個(gè)地址的地址空間中生成虛擬地址颈走，這個(gè)地址空間稱為虛擬地址空間（virtual address space）。一個(gè)地址空間的大小是由表示最大地址所需要的位數(shù)來描敘的≡凼浚現(xiàn)代系統(tǒng)通常支持32位或者64位虛擬地址空間立由。

一個(gè)系統(tǒng)還有一個(gè)物理地址空間（physical address space），對(duì)應(yīng)于系統(tǒng)中物理內(nèi)存的M個(gè)字節(jié)序厉。地址空間的概念是十分重要的锐膜，因?yàn)樗宄貐^(qū)分了數(shù)據(jù)對(duì)象（字節(jié)）和它們地屬性（地址）。一旦認(rèn)識(shí)到了這種區(qū)別弛房，那么我們就可以將其推廣了道盏，允許每個(gè)數(shù)據(jù)對(duì)象有多個(gè)獨(dú)立地地址空間，其中每個(gè)地址都選自一個(gè)不同的地址空間文捶。這就是虛擬內(nèi)存的基本思想荷逞。主存中的每字節(jié)都有一個(gè)選自虛擬空間的虛擬地址和一個(gè)選自物理空間的物理地址。

虛擬內(nèi)存映射即為虛擬地址空間到物理地址空間的映射粹排。

MMU 的作用：

MMU 進(jìn)行虛擬地址轉(zhuǎn)換成為物理地址的過程是 MMU 工作的核心种远，另外它還包含訪問權(quán)限控制的作用

后續(xù)的一些概念

下面是和虛擬內(nèi)存相關(guān)的一些概念，先簡(jiǎn)單表述下恨搓，后續(xù)都會(huì)講到

1. 虛擬地址(virtual memory)：相對(duì)物理地址來說的概念院促，不真實(shí)存在的筏养。
2. 物理地址(physical address)：真實(shí)存在的，和物理內(nèi)存關(guān)聯(lián)的常拓。
3. 地址翻譯：將虛擬地址映射成物理地址的過程渐溶。
4. 頁(page)：
   
   通常將虛擬地址空間以512Byte ~ 8K，作為一個(gè)單位弄抬，稱為頁茎辐，并從0開始依次對(duì)每一個(gè)頁編號(hào)。這個(gè)大小通常被稱為頁面掂恕。
   
   將物理地址按照同樣的大小拖陆，作為一個(gè)單位，稱為框或者塊懊亡，也從0開始依次對(duì)每一個(gè)框編號(hào)依啰。
5. 頁表(page table)：
   
   管理虛擬內(nèi)存頁和物理內(nèi)存頁映射和緩存狀態(tài)的數(shù)據(jù)結(jié)構(gòu)。
   
   操作系統(tǒng)通過維護(hù)一張表店枣，這張表上記錄了每一對(duì)頁和框的映射關(guān)系
6. 頁表?xiàng)l目(page table entry PTE)：是構(gòu)成頁表的基本元素速警，是索引號(hào)為虛擬頁號(hào)、值為物理頁號(hào)的數(shù)組鸯两。
7. 虛擬頁(VP)：虛擬地址空間劃分為多個(gè)固定大小的虛擬頁闷旧。
8. 物理頁(PP)：物理地址空間劃分為多個(gè)固定大小的物理頁。
9. 頁表基地址寄存器（PTBR）：CPU有一個(gè)專門的頁表基地址寄存器钧唐，指向當(dāng)前頁表的基地址（物理框的起始基地址）忙灼。
10. 翻譯后備緩沖區(qū)（TLB）：一個(gè)用來緩存頁表?xiàng)l目PTE的硬件設(shè)備。
11. MMU(Memory Management Unit)：CPU中含有的硬件钝侠，將虛擬地址轉(zhuǎn)換為物理地址该园。

地址轉(zhuǎn)換的步驟描述

這里我們以頁面大小為4k為例

一個(gè)4G虛擬地址空間，將會(huì)產(chǎn)生1024*1024個(gè)頁机错，頁表的每一項(xiàng)存儲(chǔ)一個(gè)頁和一個(gè)框的映射爬范，所以父腕，至少需要1M個(gè)頁表?xiàng)l目弱匪。如果一個(gè)頁表?xiàng)l目大小為1Byte，則至少需要1M的空間璧亮，所以頁表被放在物理內(nèi)存中萧诫，由操作系統(tǒng)維護(hù)。

當(dāng)CPU要訪問一個(gè)虛擬地址空間對(duì)應(yīng)的物理內(nèi)存地址時(shí)枝嘶，先將具體的(虛擬地址A)/(頁面大小4K)帘饶，結(jié)果的商作為頁表號(hào)，結(jié)果的余作為業(yè)內(nèi)地址偏移群扶。

例如：

CPU訪問的虛擬地址：A

頁面：L

頁表號(hào)：(A/L)

頁內(nèi)偏移：(A%L)

CPU中有一個(gè)頁表寄存器及刻，里面存放著當(dāng)前進(jìn)程頁表的起始地址和頁表長(zhǎng)度镀裤。將上述計(jì)算的頁表號(hào)和頁表長(zhǎng)度進(jìn)行對(duì)比，確認(rèn)在頁表范圍內(nèi)缴饭，然后將頁表號(hào)和頁表項(xiàng)長(zhǎng)度相乘暑劝，得到目標(biāo)頁相對(duì)于頁表基地址的偏移量，最后加上頁表基地址偏移量就可以訪問到相對(duì)應(yīng)的框了颗搂，CPU拿到框的起始地址之后担猛，再把頁內(nèi)偏移地址加上，訪問到最終的目標(biāo)地址丢氢。

虛擬內(nèi)存的頁面調(diào)度

請(qǐng)求頁面調(diào)度即當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)傅联，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請(qǐng)求疚察，由 OS 將其所需頁面調(diào)入內(nèi)存蒸走。

概念上而言，虛擬內(nèi)存被組織為一個(gè)由存放在磁盤上的N個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組貌嫡。每字節(jié)都有一個(gè)唯一的虛擬地址载碌，作為到數(shù)組的索引。磁盤上數(shù)組的內(nèi)容被緩存到主存中衅枫。和存儲(chǔ)器層次結(jié)構(gòu)中其他緩存一樣嫁艇，磁盤（較低層）上的數(shù)據(jù)被分割為塊，這些塊作為磁盤和主存之間的傳輸單元弦撩。VM系統(tǒng)通過將虛擬內(nèi)存分割為稱為虛擬頁（Vitrual Page）的大小固定的塊來處理這個(gè)問題步咪。每個(gè)頁面大小為P字節(jié)。類似的益楼，物理內(nèi)存頁被分割為物理頁（Physical page,PP）,大小也為P字節(jié)（物理頁面也被稱為頁幀 Page frame）猾漫。

虛擬存儲(chǔ)器是由硬件和操作系統(tǒng)自動(dòng)實(shí)現(xiàn)存儲(chǔ)信息調(diào)度和管理的。它的工作過程包括6個(gè)步驟：

1. 中央處理器訪問主存的邏輯地址分解成組號(hào)a和組內(nèi)地址b感凤，并對(duì)組號(hào)a進(jìn)行地址變換悯周，即將邏輯組號(hào)a作為索引，查地址變換表陪竿，以確定該組信息是否存放在主存內(nèi)禽翼。
2. 如該組號(hào)已在主存內(nèi)，則轉(zhuǎn)而執(zhí)行步驟4族跛；如果該組號(hào)不在主存內(nèi)（缺頁）闰挡，則檢查主存中是否有空閑區(qū)，如果沒有礁哄，便將某個(gè)暫時(shí)不用的組調(diào)出送往輔存长酗，以便將這組信息調(diào)入主存。
3. 輔存讀出所要的組桐绒，并送到主存空閑區(qū)夺脾，然后將那個(gè)空閑的物理組號(hào)a和邏輯組號(hào)a登錄在地址變換表中之拨。
4. 從地址變換表讀出與邏輯組號(hào)a對(duì)應(yīng)的物理組號(hào)a。
5. 從物理組號(hào)a和組內(nèi)字節(jié)地址b得到物理地址咧叭。
6. 根據(jù)物理地址從主存中存取必要的信息敦锌。

在任何時(shí)刻，虛擬頁面的集合都分為三個(gè)不相交的子集：

1. 未分配：VM系統(tǒng)還未分配（或者創(chuàng)建）的頁佳簸。未分配的塊沒有任何數(shù)據(jù)和它們相關(guān)聯(lián)乙墙，因此也就不占用任何磁盤空間。
2. 緩存的：當(dāng)前已緩存在物理內(nèi)存中的已分配頁生均。
3. 未緩存的：未緩存在物理內(nèi)存中的已分配頁听想。

頁表

同任何緩存一樣，虛擬內(nèi)存系統(tǒng)必須由某種方法來判定一個(gè)虛擬頁是否緩存在DRAM中的某個(gè)地方马胧。如果是汉买，系統(tǒng)還必須確定這個(gè)虛擬頁存放在哪個(gè)物理頁面中。如果不命中佩脊，系統(tǒng)必須判斷這個(gè)虛擬頁面放在磁盤的哪個(gè)位置蛙粘，在物理內(nèi)存中選擇一個(gè)犧牲頁，并將虛擬頁從磁盤復(fù)制到DRAM中威彰，替換這個(gè)犧牲頁面出牧。

這些功能是軟硬件聯(lián)合提供的，包括操作系統(tǒng)歇盼、MMU（內(nèi)存管理單元）中的地址翻譯硬件和一個(gè)存放在物理內(nèi)存中叫作頁表（page table）的數(shù)據(jù)結(jié)構(gòu)舔痕，頁表將虛擬頁映射到物理頁面。每次地址翻譯硬件將一個(gè)虛擬地址轉(zhuǎn)換為物理地址時(shí)豹缀，都會(huì)讀取頁表伯复。操作系統(tǒng)負(fù)責(zé)維護(hù)頁表的內(nèi)容，以及在磁盤與DRAM之間來回傳送頁邢笙。

頁表就是一個(gè)頁表?xiàng)l目（Page Table Entry）的數(shù)組啸如。虛擬地址空間中的每個(gè)頁在頁表中都有一個(gè)固定的偏移量處都有一個(gè)PTE。為了我們的目的氮惯，我們假設(shè)每個(gè)PTE是由一個(gè)有效位（valid bit）和一個(gè)n位地址字段組成的叮雳。有效位表明了該虛擬頁面當(dāng)前是否被緩存在DRAM中。如果設(shè)置了有效位筐骇，那么地址字段就表示DRAM中相應(yīng)的物理頁的起始位置债鸡，這個(gè)物理頁中緩存了該虛擬頁亭珍。如果沒有設(shè)置有效位薇溃，那么這個(gè)空地址表示這個(gè)虛擬頁還未被分配蹬挺。否則，這個(gè)地址就會(huì)指向該虛擬頁在磁盤上的起始位置告唆。

在頁表?xiàng)l目中棺弊，通過有效位與磁盤地址可以產(chǎn)生不同的情況：

1. 有效位為1時(shí)候，標(biāo)識(shí)虛擬頁已經(jīng)緩存
2. 有效位為0時(shí)候擒悬，數(shù)值為 null 時(shí)候模她，表示未分配的頁
3. 有效位為0，數(shù)值不為 null 時(shí)候懂牧，表示已經(jīng)分配了虛擬頁侈净，但是還未緩存到具體的物理頁中（缺頁）

注意，這里的緩存是代表內(nèi)存中存有的數(shù)據(jù)僧凤。

頁命中

當(dāng)CPU 想要讀取一個(gè)頁表內(nèi)虛擬內(nèi)存的一個(gè)字時(shí)候畜侦，地址翻譯硬件會(huì)將虛擬地址作為一個(gè)索引來定位頁面（例如PTE2），地址翻譯硬件會(huì)將模擬地址作為一個(gè)索引來定位PTE2躯保，并從內(nèi)存中讀取它旋膳。

當(dāng)有效位為1時(shí)候，代表頁命中途事，那么地址翻譯硬件就知道VP2是緩存在內(nèi)存中的了验懊。所以它就可以直接使用PTE2表中的物理內(nèi)存地址（該地址指向PP 1中緩存頁的起始位置），構(gòu)造出這個(gè)字的物理地址尸变。

缺頁

擬頁沒有被緩存在物理內(nèi)存中（緩存未命中）被稱為缺頁义图。

當(dāng)CPU遇見缺頁時(shí)會(huì)觸發(fā)一個(gè)缺頁異常，缺頁異常將控制權(quán)轉(zhuǎn)向操作系統(tǒng)內(nèi)核召烂，然后調(diào)用內(nèi)核中的缺頁異常處理程序歌溉，該程序會(huì)選擇一個(gè)犧牲頁，如果犧牲頁已被修改過骑晶，內(nèi)核會(huì)先將它復(fù)制回硬盤（采用寫回機(jī)制而不是直寫也是為了盡量減少對(duì)硬盤的訪問次數(shù)）痛垛，然后再把該虛擬頁覆蓋到犧牲頁的位置，并且更新PTE桶蛔。

當(dāng)缺頁異常處理程序返回時(shí)匙头，它會(huì)重新啟動(dòng)導(dǎo)致缺頁的指令，該指令會(huì)把導(dǎo)致缺頁的虛擬地址重新發(fā)送給MMU仔雷。由于現(xiàn)在已經(jīng)成功處理了缺頁異常蹂析，所以最終結(jié)果是頁命中，并得到物理地址碟婆。

頁面調(diào)度

這種在硬盤和內(nèi)存之間傳送頁的行為稱為頁面調(diào)度（paging）：頁從硬盤換入內(nèi)存和從內(nèi)存換出到硬盤电抚。當(dāng)缺頁異常發(fā)生時(shí)，才將頁面換入到內(nèi)存的策略稱為按需頁面調(diào)度（demand paging）竖共，所有現(xiàn)代操作系統(tǒng)基本都使用的是按需頁面調(diào)度的策略蝙叛。

虛擬內(nèi)存調(diào)度分為三個(gè)方式：分段式、段式和段頁式 3種公给。

1. 頁式調(diào)度是將邏輯和物理地址空間都分為固定大小的頁借帘，主存按頁順序編號(hào)蜘渣，而每個(gè)獨(dú)立編址的程序空間都有自己的頁號(hào)順序，通過調(diào)度輔存中的程序各頁肺然，可以離散裝入主存中不同的頁面位置蔫缸，并可以根據(jù)表一一映射。
2. 段式調(diào)度是按程序的邏輯結(jié)構(gòu)劃分地址空間际起，段的長(zhǎng)度是隨意的拾碌，并且允許伸長(zhǎng)，它的優(yōu)點(diǎn)是消除了內(nèi)存零頭街望，易于實(shí)現(xiàn)存儲(chǔ)保護(hù)倦沧，便于程序動(dòng)態(tài)裝配；缺點(diǎn)是調(diào)入操作復(fù)雜它匕。
3. 將這兩種方法結(jié)合起來便構(gòu)成段頁式調(diào)度展融。在段頁式調(diào)度中把物理空間分成頁，程序按模塊分段豫柬，每個(gè)段再分成與物理空間頁同樣小的頁面告希。段頁式調(diào)度綜合了段式和頁式的優(yōu)點(diǎn)。其缺點(diǎn)是增加了硬件成本烧给，軟件也較復(fù)雜燕偶。大型通用計(jì)算機(jī)系統(tǒng)多數(shù)采用段頁式調(diào)度。

虛擬內(nèi)存的局部性

虛擬內(nèi)存跟CPU高速緩存（或其他使用緩存的技術(shù)）一樣依賴于局部性原則础嫡。雖然處理缺頁消耗的性能很多（畢竟還是要從硬盤中讀戎该础），而且程序在運(yùn)行過程中引用的不同虛擬頁的總數(shù)可能會(huì)超出物理內(nèi)存的大小榴鼎，但是局部性原則保證了在任意時(shí)刻伯诬，程序?qū)②呄蛴谠谝粋€(gè)較小的活動(dòng)頁面（active page）集合上工作，這個(gè)集合被稱為工作集（working set）巫财。根據(jù)空間局部性原則（一個(gè)被訪問過的內(nèi)存地址以及其周邊的內(nèi)存地址都會(huì)有很大幾率被再次訪問）與時(shí)間局部性原則（一個(gè)被訪問過的內(nèi)存地址在之后會(huì)有很大幾率被再次訪問）盗似，只要將工作集緩存在物理內(nèi)存中，接下來的地址翻譯請(qǐng)求很大幾率都在其中平项，從而減少了額外的硬盤流量赫舒。

如果一個(gè)程序沒有良好的局部性，將會(huì)使工作集的大小不斷膨脹闽瓢，直至超過物理內(nèi)存的大小接癌，這時(shí)程序會(huì)產(chǎn)生一種叫做抖動(dòng)（thrashing）的狀態(tài)，頁面會(huì)不斷地?fù)Q入換出扣讼，如此多次的讀寫硬盤開銷缺猛，性能自然會(huì)十分“恐怖”。所以，想要編寫出性能高效的程序枯夜，首先要保證程序的時(shí)間局部性與空間局部性弯汰。

虛擬內(nèi)存的內(nèi)存管理與保護(hù)

VM作為內(nèi)存管理工具

上述僅僅是一個(gè)單獨(dú)頁表艰山，將一個(gè)虛擬地址空間映射到物理地址空間湖雹。在實(shí)際上，操作系統(tǒng)為每個(gè)進(jìn)程提供了一個(gè)獨(dú)立的虛擬地址空間曙搬，大大簡(jiǎn)化了內(nèi)存管理摔吏。另外，多個(gè)虛擬頁面可以映射到同一個(gè)物理頁面上纵装。
操作系統(tǒng)通過將不同進(jìn)程中適當(dāng)?shù)奶摂M頁面映射到相同的物理頁面征讲，從而安排多個(gè)進(jìn)程共享這部分代碼的一個(gè)副本，而不是在每個(gè)進(jìn)程中都包含單獨(dú)的內(nèi)核和C標(biāo)準(zhǔn)庫的副本（例如 printf 函數(shù)）橡娄。

按需頁面調(diào)度和獨(dú)立的虛擬地址空間的結(jié)合诗箍，讓VM簡(jiǎn)化了鏈接和加載，代碼和數(shù)據(jù)共享挽唉，以及應(yīng)用程序的內(nèi)存分配滤祖。

1. 簡(jiǎn)化鏈接。獨(dú)立的地址空間允許每個(gè)進(jìn)程的內(nèi)存映像使用相同的基本格式瓶籽，而不管代碼和數(shù)據(jù)實(shí)際存放在物理內(nèi)存的何處匠童。
2. 簡(jiǎn)化加載。虛擬內(nèi)存使得容易向內(nèi)存中加載可執(zhí)行文件和共享對(duì)象文件塑顺。將一組連續(xù)的虛擬頁面映射到任意一個(gè)文件中的任意位置的表示法稱作內(nèi)存映射（memory mapping）汤求。Linux 提供了一個(gè) mmap 的系統(tǒng)調(diào)用，允許應(yīng)用程序自己做內(nèi)存映射严拒。
3. 簡(jiǎn)化共享扬绪。獨(dú)立地址空間為操作系統(tǒng)提供了一個(gè)管理用戶進(jìn)程和操作系統(tǒng)自身之間共享的一致機(jī)制。一般情況下裤唠，每個(gè)進(jìn)程都有自己私有的代碼勒奇、數(shù)據(jù)、堆棧巧骚。這些內(nèi)容不與其他進(jìn)程共享赊颠。在這種情況下，操作系統(tǒng)創(chuàng)建頁表劈彪，將相應(yīng)的虛擬頁映射到不連續(xù)的物理頁面竣蹦。
4. 簡(jiǎn)化內(nèi)存分配。虛擬內(nèi)存向用戶進(jìn)程提供一個(gè)簡(jiǎn)單的分配額外內(nèi)存的機(jī)制沧奴。當(dāng)一個(gè)用戶程序要求額外的堆空間時(shí)候痘括，操作系統(tǒng)分配 k 個(gè)適當(dāng)?shù)倪B續(xù)的虛擬內(nèi)存頁面，并且將他們映射到物理內(nèi)存的中的 k 個(gè)任意頁面，操作系統(tǒng)沒有必要分配 k 個(gè)連續(xù)的物理內(nèi)存頁面纲菌。

VM作為內(nèi)存保護(hù)工具

現(xiàn)代計(jì)算機(jī)系統(tǒng)為操作系統(tǒng)提供手段來控制對(duì)內(nèi)存系統(tǒng)的訪問挠日。

在上圖中，每個(gè) PTE 添加了三個(gè)控制位翰舌， SUP 位表示進(jìn)程是否必須運(yùn)行在超級(jí)用也就是內(nèi)核模式下才能訪問該頁嚣潜，WRITE 位控制頁面的寫訪問， EXRC 位控制頁面的執(zhí)行椅贱。如果有指令違反了這些控制條件懂算，那么 CPU 會(huì)觸發(fā)一個(gè)一般保護(hù)故障，將控制傳遞給內(nèi)核中的異常處理程序庇麦。

地址翻譯

上述已經(jīng)簡(jiǎn)單描述虛擬內(nèi)存映射计技，在計(jì)算機(jī)系統(tǒng)中，硬件還需要支持地址翻譯山橄，即 MMU 的相關(guān)工作原理垮媒。

地址翻譯，是一個(gè)N元素的虛擬地址空間（VAS）中的元素和一個(gè)M元素的物理地址空間（PAS）中元素之間的映射航棱。

計(jì)算機(jī)通過MMU硬件利用頁表來完成上述映射：

CPU中有一個(gè)控制寄存器睡雇，頁表基址寄存器（Page Table Base Register，PTBR）指向當(dāng)前頁表丧诺。n位虛擬地址包含兩個(gè)部分：一個(gè)P位的虛擬頁號(hào)偏移（Virtual Page Offset入桂，VPO）和一個(gè)（n-p）位的虛擬頁號(hào)（Virtual Page Number，VPN)

MMU用后者選擇適當(dāng)?shù)腜TE驳阎，再將物理頁號(hào)和虛擬地址中的VPO串聯(lián)起來得到物理地址抗愁。

因?yàn)槲锢砗吞摂M頁面都是P字節(jié)的，所以物理頁面偏移和VPO是相同的呵晚。

物理地址是由物理頁號(hào)和虛擬頁面偏移串聯(lián)起來得到的蜘腌。

1）頁面命中時(shí)，執(zhí)行的步驟（完全由硬件來處理）：

2）缺頁時(shí)饵隙，執(zhí)行的步驟（硬件和操作系統(tǒng)內(nèi)核協(xié)作完成）：

結(jié)合高速緩存和虛擬內(nèi)存

大多數(shù)系統(tǒng)使用物理尋址來訪問SRAM高速緩存撮珠。

高速緩存無需處理保護(hù)問題，因?yàn)樵L問權(quán)限的檢查是地址翻譯過程的一部分金矛。

利用TLB加速地址翻譯

如上圖芯急，PTE不命中 L1 高速緩存，需要在內(nèi)存中讀仁豢　（創(chuàng)建并更新）娶耍。每次CPU產(chǎn)生一個(gè)虛擬地址，MMU就必須查閱一個(gè)PTE饼酿，以便將虛擬地址翻譯為物理地址榕酒。在最糟糕情況下胚膊，這會(huì)要求內(nèi)存讀取一次數(shù)據(jù)，代價(jià)是幾十到幾百個(gè)周期想鹰。

為了消除這樣的開銷紊婉，許多系統(tǒng)在MMU包含了一個(gè)關(guān)于PTE的小緩存，稱為翻譯后備緩沖器（Translation Lookaside Buffer，TLB）。

TLB是一個(gè)小的，虛擬尋址的緩存，其中每一行都保存著一個(gè)由單個(gè)PTE組成的塊表箭。TLB通常有高度的相關(guān)聯(lián)度。如下圖所示隘马，用于組選擇和行匹配的索引和標(biāo)記字段是從虛擬地址中的虛擬號(hào)中提煉出來的逞姿。如果TLB有 T = 2^t 個(gè)組，那么 TLB 索引（TLBI）是有 VPN 的 t 個(gè)最低位組成的蝙云，而 TLB 標(biāo)記（TLBT）是由 VPN 中剩余的位組成的氓皱。

簡(jiǎn)單舉例：

當(dāng)cpu要訪問一個(gè)虛擬地址/線性地址時(shí)，CPU會(huì)首先根據(jù)虛擬地址的高20位（20是x86特定的勃刨，不同架構(gòu)有不同的值）在TLB中查找波材。如果是表中沒有相應(yīng)的表項(xiàng)，稱為TLB miss身隐，需要通過訪問慢速RAM中的頁表計(jì)算出相應(yīng)的物理地址廷区。同時(shí)，物理地址被存放在一個(gè)TLB表項(xiàng)中贾铝，以后對(duì)同一線性地址的訪問隙轻，直接從TLB表項(xiàng)中獲取物理地址即可，稱為TLB hit垢揩。

下述為TLB命中（通常情況）時(shí)候的步驟玖绿。由于所有地址翻譯步驟都在芯片MMU上，因此非常的快

1. CPU產(chǎn)生一個(gè)虛擬地址
2. MMU從TLB中取出相應(yīng)的PTE
3. MMU將這個(gè)虛擬地址翻譯成一個(gè)物理地址叁巨，并且將它發(fā)送到高速緩存/主存
4. 高速緩存/主存將所請(qǐng)求的數(shù)據(jù)字返回給CPU

當(dāng)TLB不命中時(shí)斑匪，MMU 必須從L1緩存中取出相應(yīng)的PTE，新取出的PTE存放在TLB中锋勺，可能會(huì)覆蓋一個(gè)已經(jīng)存在的條目蚀瘸。

TLB介于CPU與高速緩存/內(nèi)存之間，用于程序從邏輯地址訪問內(nèi)存地址的頁表緩存

多級(jí)頁表

虛擬地址空間以頁面為單位劃分庶橱。在物理內(nèi)存中對(duì)應(yīng)的單位稱為頁幀贮勃。頁面和頁幀的大小總是一樣的。

假設(shè)頁面的大小為4KB悬包，下面是一個(gè)頁表給出虛擬地址與物理內(nèi)存地址之間的映射關(guān)系

這樣的頁表衙猪，有兩個(gè)很主要的問題

1）頁表有可能非常大

2）地址映射必須非常快

這里重點(diǎn)討論第一個(gè)問題，第二個(gè)問題可以通過硬件去解決垫释。

第一個(gè)問題的產(chǎn)生是由于現(xiàn)代計(jì)算機(jī)使用的虛擬地址至少是32位的丝格。比如，當(dāng)頁面大小為4KB時(shí)棵譬，4字節(jié)的PTE显蝌，32位的地址空間將有100萬個(gè)頁面，4MB（4GB/4KB*4B）订咸，64位的地址空間則更多曼尊。虛擬地址空間中的100萬個(gè)頁面需要有100萬個(gè)表項(xiàng)的頁表。并且請(qǐng)記住脏嚷，每個(gè)進(jìn)程都需要有自己的頁表（因?yàn)槊總€(gè)進(jìn)程有自己的虛擬地址空間）骆撇。

顯然不可能每個(gè)進(jìn)程都將自己的頁表保存在內(nèi)存中。

為此父叙，用來壓縮頁表的常用方法是使用層次結(jié)構(gòu)的頁表（多級(jí)頁表）神郊，如下圖。

一級(jí)頁表中的每個(gè)PTE負(fù)責(zé)映射虛擬內(nèi)存地址空間中的一個(gè)4MB的片（chunk）趾唱，這里每一片都由1024個(gè)連續(xù)的頁面組成涌乳。

如果片i中的每個(gè)頁面都未分配，那么這一級(jí)的PTEi就為空

二級(jí)頁表中的每個(gè)PTE負(fù)責(zé)映射一個(gè)4KB的虛擬內(nèi)存頁面甜癞。

這種層次結(jié)構(gòu)有效的減緩了內(nèi)存要求：

1. 如果一個(gè)一級(jí)頁表的一個(gè)PTE是空的夕晓，那么相應(yīng)的二級(jí)頁表也不會(huì)存在。這代表一種巨大的潛在節(jié)約（對(duì)于一個(gè)普通的程序來說悠咱，虛擬地址空間的大部分都會(huì)是未分配的）蒸辆。
2. 只有一級(jí)頁表才總是需要緩存在內(nèi)存中的，這樣虛擬內(nèi)存系統(tǒng)就可以在需要時(shí)創(chuàng)建乔煞、頁面調(diào)入或調(diào)出二級(jí)頁表（只有經(jīng)常使用的二級(jí)頁表才會(huì)被緩存在內(nèi)存中）吁朦，這就減少了內(nèi)存的壓力。

Linux虛擬內(nèi)存系統(tǒng)

程序運(yùn)行時(shí)的虛擬內(nèi)存渡贾，準(zhǔn)確的表達(dá)是"虛擬內(nèi)存技術(shù)"逗宜。

上述的虛擬內(nèi)存系統(tǒng)，更多的是從硬件角度解析虛擬內(nèi)存空骚。一個(gè)虛擬內(nèi)存系統(tǒng)要求硬件和內(nèi)核之間的緊密協(xié)作纺讲。下面我們開始介紹 Linux 針對(duì)虛擬內(nèi)存的一些實(shí)現(xiàn)（內(nèi)核函數(shù)實(shí)現(xiàn)思路）。

Linux 為每個(gè)進(jìn)程維護(hù)了一個(gè)單獨(dú)的虛擬地址空間囤屹。

注：用戶只能訪問整個(gè)地址空間的下半部分熬甚，不能訪問內(nèi)核部分。同時(shí)用戶進(jìn)程也不能操作另一個(gè)進(jìn)程的地址空間（除非共享內(nèi)存）肋坚。

注2：IA-32 系統(tǒng)上地址范圍4GB乡括，內(nèi)核大概1GB肃廓。

內(nèi)核虛存內(nèi)包含內(nèi)核中的代碼和數(shù)據(jù)結(jié)構(gòu)。內(nèi)核虛擬內(nèi)存的某些區(qū)域被映射到所有進(jìn)程共享的物理頁面诲泌。例如盲赊，每個(gè)進(jìn)程共享內(nèi)核的代碼和全部數(shù)據(jù)結(jié)構(gòu)。

內(nèi)核虛擬內(nèi)存的其他區(qū)域包含每個(gè)進(jìn)程都不相同的數(shù)據(jù)敷扫。比如說哀蘑，頁表、內(nèi)核在進(jìn)程中上下文中執(zhí)行代碼時(shí)使用的棧葵第，以及記錄虛擬地址空間當(dāng)前組織的各種數(shù)據(jù)結(jié)構(gòu)绘迁。

內(nèi)核虛擬區(qū)域

Linux將虛擬內(nèi)存組織成一些區(qū)域（也叫做段）的集合。一個(gè)區(qū)域就是已經(jīng)存在著的（已分配的）虛擬內(nèi)存的連續(xù)片卒密，這些頁是以某種方式相關(guān)聯(lián)的缀台。

代碼段、數(shù)據(jù)段栅受、堆将硝、共享庫段和用戶區(qū)都是不同是區(qū)域恭朗。只要是存在的虛擬頁就保存在某個(gè)區(qū)域中屏镊。
區(qū)域的存在允許虛擬地址空間有間隙。內(nèi)核不記錄不存在的虛擬頁痰腮，由此節(jié)省空間而芥。
內(nèi)核為系統(tǒng)中的每個(gè)進(jìn)程維護(hù)一個(gè)單獨(dú)的任務(wù)結(jié)構(gòu)（源代碼中的task_struct）。任務(wù)結(jié)構(gòu)中的元素包含或者指向內(nèi)核運(yùn)行該進(jìn)程所需要的所有信息（例如膀值，PID棍丐、指向用戶棧的指針、可執(zhí)行目標(biāo)文件的名字以及程序計(jì)數(shù)器）沧踏。
下圖強(qiáng)調(diào)了記錄一個(gè)進(jìn)程中虛擬內(nèi)存區(qū)域的內(nèi)核數(shù)據(jù)結(jié)構(gòu)歌逢。

task_struct的mm指針指向了mm_struct，該結(jié)構(gòu)描述了虛擬內(nèi)存的當(dāng)前狀態(tài)翘狱。mm_struct的pgd指針指向該進(jìn)程的第一級(jí)頁表（頁全局目錄）的基址秘案。mmap指針指向了vm_area_struct（區(qū)域結(jié)構(gòu)）鏈表。每個(gè)每個(gè)vm_area_struct都描繪了虛擬地址空間的一個(gè)區(qū)域潦匈。當(dāng)內(nèi)核運(yùn)行這個(gè)進(jìn)程時(shí)阱高，它就將pgdf存放在CR3控制寄存器中。區(qū)域結(jié)構(gòu)包含以下幾個(gè)部分

1. vm_start：指向這個(gè)區(qū)域的起始處
2. vm_end：指向這個(gè)區(qū)域的結(jié)束處
3. vm_port：描述這個(gè)區(qū)域內(nèi)包含的所有頁的讀寫許可權(quán)限
4. vm_flags：描述這個(gè)區(qū)域內(nèi)的頁面是與其他進(jìn)程共享的茬缩，還是這個(gè)進(jìn)程私有的
5. vm_next：指向鏈表中下一個(gè)區(qū)域結(jié)構(gòu)

Linux缺頁異常處理

當(dāng)MMU翻譯一個(gè)虛擬地址時(shí)發(fā)生發(fā)生缺頁異常赤惊，該異常使控制轉(zhuǎn)移到內(nèi)核的缺頁處理程序，程序執(zhí)行如下步驟：

1. 缺頁處理程序搜索區(qū)域結(jié)構(gòu)的鏈表凰锡，將虛擬地址與每個(gè)區(qū)域結(jié)構(gòu)的vm_start和vm_end進(jìn)行比較未舟，由此判斷虛擬地址是否合法圈暗，即是否在某個(gè)區(qū)域結(jié)構(gòu)定義的區(qū)域內(nèi)。若不合法裕膀，則缺頁處理程序觸發(fā)段錯(cuò)誤厂置，終止進(jìn)程。
2. 判斷進(jìn)程是否有讀魂角、寫昵济、執(zhí)行這個(gè)區(qū)域內(nèi)頁面的權(quán)限，即內(nèi)存訪問是否合法野揪。若不合法访忿，則觸發(fā)一個(gè)保護(hù)異常，終止進(jìn)程斯稳。
3. 若是通過了上述兩步海铆，則說明該缺頁是對(duì)一個(gè)合法地址的合法操作導(dǎo)致的，由此則可以處理缺頁挣惰。選擇一個(gè)犧牲頁卧斟，如果犧牲頁被修改過，那么把它交換出去憎茂。換入新的頁面并更新頁表珍语。缺頁處理程序返回時(shí)，CPU重新啟動(dòng)引起缺頁的指令竖幔。（同去缺頁處理）

交換空間

從硬盤中劃分出的所謂的"虛擬內(nèi)存"板乙，準(zhǔn)確來說應(yīng)該叫做虛擬內(nèi)存的"后備存儲(chǔ)空間"

注意，從硬盤劃分出來的虛擬內(nèi)存和程序運(yùn)行時(shí)的虛擬內(nèi)存并不是一個(gè)概念拳氢。

從操作系統(tǒng)角度來看募逞，虛擬內(nèi)存即交換文件；

Linux系統(tǒng)實(shí)現(xiàn)虛擬內(nèi)存有兩種方法：交換分區(qū)（swap分區(qū)）和交換文件

1. 實(shí)際內(nèi)存
   
   實(shí)際內(nèi)存是指一個(gè)系統(tǒng)中實(shí)際存在的物理內(nèi)存馋评，稱為RAM放接。實(shí)際內(nèi)存是存儲(chǔ)臨時(shí)數(shù)據(jù)最快最有效的方式，因此必須盡可能地分配給應(yīng)用程序留特，現(xiàn)在的RAM的形式有多種：SIMM纠脾、DIMM、Rambus磕秤、DDR等乳乌，很多RAM都可以使用糾錯(cuò)機(jī)制（ECC）。
2. 交換空間swap
   
   交換空間是專門用于臨時(shí)存儲(chǔ)內(nèi)存的一塊磁盤空間（文件）市咆，通常在頁面調(diào)度和交換進(jìn)程數(shù)據(jù)時(shí)使用汉操，通常推薦交換空間的大小應(yīng)該是物理內(nèi)存的二到四倍。在 Mac OS 系統(tǒng)上蒙兰，可以查看 /private/var/vm/swapfile*磷瘤。
3. 交換分區(qū)
   
   采用交換分區(qū)的辦法其實(shí)就是新建一個(gè)分區(qū)芒篷，然后將該分區(qū)掛載作為交換空間，方法步驟與傳統(tǒng)的新建分區(qū)一樣采缚。只不過格式化分區(qū)和掛載分區(qū)分別采用mkswap和swapon命令针炉。在創(chuàng)建分區(qū)之前，我們常常要用過fdisk -l和df -Th命令來查看硬盤信息和掛載信息扳抽，來確定分區(qū)的大小篡帕。

內(nèi)存映射

虛擬內(nèi)存區(qū)域是和磁盤中的文件對(duì)應(yīng)。

Linux通過將一個(gè)虛擬內(nèi)存區(qū)域與一個(gè)磁盤上的對(duì)象關(guān)聯(lián)起來贸呢，以初始化這個(gè)虛擬內(nèi)存區(qū)域的內(nèi)容镰烧，這個(gè)過程稱為內(nèi)存映射(memory mapping)。

虛擬內(nèi)存區(qū)域可以映射到以下兩類對(duì)象：

1. Linux系統(tǒng)中的普通文件：文件區(qū)被分成頁大小的片楞陷，每一片包含一個(gè)虛擬頁面的初始內(nèi)容怔鳖。因?yàn)榘葱柽M(jìn)行頁面調(diào)度，因此這些虛擬頁沒有實(shí)際交換進(jìn)入物理內(nèi)存固蛾，直到CPU第一次引用頁面结执。
2. 匿名文件：由內(nèi)核創(chuàng)建，內(nèi)容全是二進(jìn)制零艾凯。CPU第一次引用這樣一個(gè)區(qū)域的虛擬內(nèi)存時(shí)献幔，內(nèi)核就在物理內(nèi)存中找一個(gè)合適的犧牲頁面，被修改過就換出來览芳，用二進(jìn)制零覆蓋犧牲頁面并更新頁表斜姥，將這個(gè)頁面標(biāo)記為留在內(nèi)存中。在磁盤和內(nèi)存間沒有實(shí)際的數(shù)據(jù)傳輸沧竟，因此映射到匿名文件中的頁叫做請(qǐng)求二進(jìn)制零的頁(demand-zero page)。

無論上述哪種情況缚忧，一旦一個(gè)虛擬頁面被初始化了，它就在一個(gè)由內(nèi)核維護(hù)的專門的交換文件(swap file)之間換來換去。交換文件也叫交換空間序六、交換區(qū)域跃须。注意該空間限制當(dāng)前運(yùn)行的進(jìn)程能夠分配的虛擬頁面的總數(shù)。

開發(fā)過程中的內(nèi)存映射

開發(fā)中只有虛擬空間的概念球榆，進(jìn)程看到的所有地址組成的空間朽肥，就是虛擬空間。虛擬空間是某個(gè)進(jìn)程對(duì)分配給它的所有物理地址（已經(jīng)分配的和將會(huì)分配的）的重新映射持钉。

mmap的作用衡招，在應(yīng)用這一層，是讓你把文件的某一段每强，當(dāng)作內(nèi)存一樣來訪問始腾。內(nèi)核和驅(qū)動(dòng)如何實(shí)現(xiàn)的州刽，性能高不高這些問題，這層語義上沒有承諾浪箭。我們可以基于功能決定怎么用它就好了穗椅。

mmap的工作原理，當(dāng)你發(fā)起這個(gè)調(diào)用的時(shí)候奶栖，它只是在你的虛擬空間中分配了一段空間匹表，連真實(shí)的物理地址都不會(huì)分配的，當(dāng)你訪問這段空間宣鄙，CPU陷入OS內(nèi)核執(zhí)行異常處理桑孩，然后異常處理會(huì)在這個(gè)時(shí)間分配物理內(nèi)存，并用文件的內(nèi)容填充這片內(nèi)存框冀，然后才返回你進(jìn)程的上下文流椒，這時(shí)你的程序才會(huì)感知到這片內(nèi)存里有數(shù)據(jù)

驅(qū)動(dòng)每次讀入多少頁面，頁面的分配算法等等明也，包括swap等等宣虾，就是上述的一些實(shí)現(xiàn)機(jī)制。

頁面調(diào)度和交換

在簡(jiǎn)單描述下其他一些概念：

Linux內(nèi)存管理：Linux系統(tǒng)通過2種方法進(jìn)行內(nèi)存管理温数，“調(diào)頁算法”绣硝，“交換技術(shù)”。

調(diào)頁算法是將內(nèi)存中最近不常使用的頁面換到磁盤上撑刺，把常使用的頁面（活動(dòng)頁面）保留在內(nèi)存中供進(jìn)程使用鹉胖。

交換技術(shù)是系統(tǒng)將整個(gè)進(jìn)程，而不是部分頁面够傍，全部換到磁盤上甫菠。正常情況下，系統(tǒng)會(huì)發(fā)生一些交換過程冕屯。

當(dāng)內(nèi)存嚴(yán)重不足時(shí)寂诱，系統(tǒng)會(huì)頻繁使用調(diào)頁和交換，這增加了磁盤I/O的負(fù)載安聘。進(jìn)一步降低了系統(tǒng)對(duì)作業(yè)的執(zhí)行速度痰洒，即系統(tǒng)I/O資源問題又會(huì)影響到內(nèi)存資源的分配。

1. 頁面調(diào)度
   
   頁面調(diào)度是指從磁盤向內(nèi)存?zhèn)鬏敂?shù)據(jù)浴韭，以及相反的過程丘喻，這個(gè)過程之所以被稱為頁面調(diào)度，是因?yàn)閁nix內(nèi)存被平均劃分成大小相等的頁面念颈；通常頁面大小為 4KB和8KB（在Solaris中可以用pagesize命令查看）泉粉。當(dāng)可執(zhí)行程序開始運(yùn)行時(shí)，它的映象會(huì)一頁一頁地從磁盤中換入舍肠，與此類似搀继，當(dāng)某些內(nèi) 存在一段時(shí)間內(nèi)空閑窘面，就可以把它們換出到交換空間中，這樣就可以把空閑的RAM交給其他需要它的程序使用叽躯。
2. 交換
   
   頁面調(diào)度通常容易和交換的概念混淆财边，頁面調(diào)度是指把一個(gè)進(jìn)程所占內(nèi)存的空閑部分傳輸?shù)酱疟P上，而交換是指當(dāng)系統(tǒng)中實(shí)際的內(nèi)存已不夠滿足新的分配需求時(shí)点骑，把整個(gè)進(jìn)程傳輸?shù)酱疟P上酣难，交換活動(dòng)通常意味著內(nèi)存不足。

共享對(duì)象

操作系統(tǒng)為每個(gè)進(jìn)程提供私有的虛擬地址空間黑滴，免受其他進(jìn)程讀寫的干擾憨募。但對(duì)于每個(gè)進(jìn)程都要訪問的相同的只讀代碼區(qū)域，如果每個(gè)進(jìn)程在物理內(nèi)存中保存一份副本袁辈，那就是極大的浪費(fèi)菜谣。因此還是希望進(jìn)程能夠共享某些對(duì)象。

一個(gè)對(duì)象可以被映射到虛擬內(nèi)存的一個(gè)區(qū)域晚缩，要么作為共享對(duì)象尾膊，要么作為私有對(duì)象。一個(gè)映射到共享對(duì)象的虛擬內(nèi)存區(qū)域叫做共享區(qū)域荞彼。類似的冈敛，也有私有區(qū)域。

若進(jìn)程將一個(gè)共享對(duì)象映射到虛擬內(nèi)存的一個(gè)區(qū)域鸣皂，則該進(jìn)程對(duì)這個(gè)區(qū)域的任何寫操作抓谴，對(duì)那些也把該共享對(duì)象映射到虛擬內(nèi)存的其他進(jìn)程而言是可見的。同時(shí)寞缝，對(duì)象的變化會(huì)反映到磁盤上的原始對(duì)象上癌压。

反之，進(jìn)程對(duì)映射到私有對(duì)象的區(qū)域所做的改變對(duì)其他進(jìn)程不可見第租，且進(jìn)程對(duì)該區(qū)域所做的任何寫操作也不會(huì)反應(yīng)在磁盤上的對(duì)象上措拇。

私有對(duì)象使用寫時(shí)復(fù)制（copy on write）的方式被映射到虛擬內(nèi)存中。在物理內(nèi)存中保存私有對(duì)象的一個(gè)副本慎宾。進(jìn)程共享私有對(duì)象的同一個(gè)物理副本，只要沒有進(jìn)程試圖寫私有區(qū)域浅悉，則進(jìn)程可繼續(xù)共享物理內(nèi)存中對(duì)象的一個(gè)單獨(dú)副本趟据。注意私有區(qū)域的頁表?xiàng)l目都被標(biāo)記為只讀，區(qū)域結(jié)構(gòu)被標(biāo)記為私有寫時(shí)復(fù)制术健。

如果一個(gè)進(jìn)程試圖寫私有區(qū)域的某個(gè)頁面汹碱，則會(huì)觸發(fā)一個(gè)保護(hù)故障，故障處理程序會(huì)在物理內(nèi)存中創(chuàng)建這個(gè)頁面的一共新副本荞估，更新頁表?xiàng)l目指向新副本咳促，之后恢復(fù)頁面的可寫權(quán)限稚新。故障處理程序返回后CPU重新執(zhí)行寫操作。

總結(jié)如下

內(nèi)存映射：將進(jìn)程中的一個(gè)虛擬內(nèi)存區(qū)域與一個(gè)磁盤上的對(duì)象關(guān)聯(lián)跪腹，使得二者存在映射關(guān)系褂删，當(dāng)然，也可以多個(gè)進(jìn)程映射到一個(gè)對(duì)象上面冲茸。如上圖所示屯阀，其中私有對(duì)象與共享對(duì)象的區(qū)別在于權(quán)限管理。

映射關(guān)系可以分為兩種：

1. 文件映射
   磁盤文件映射進(jìn)程的虛擬地址空間轴术，使用文件內(nèi)容初始化物理內(nèi)存难衰。
2. 匿名映射
   初始化全為0的內(nèi)存空間。

而對(duì)于映射關(guān)系是否共享又分為：

1. 私有映射(MAP_PRIVATE)
   多進(jìn)程間數(shù)據(jù)共享逗栽，修改不反應(yīng)到磁盤實(shí)際文件盖袭，是一個(gè)copy-on-write（寫時(shí)復(fù)制）的映射方式。
2. 共享映射(MAP_SHARED)
   多進(jìn)程間數(shù)據(jù)共享彼宠，修改反應(yīng)到磁盤實(shí)際文件中鳄虱。

虛擬內(nèi)存系統(tǒng)通過將虛擬內(nèi)存分割為稱作虛擬頁(Virtual Page，VP)大小固定的塊兵志，一般情況下醇蝴，每個(gè)虛擬頁的大小默認(rèn)是4096字節(jié)。同樣的想罕，物理內(nèi)存也被分割為物理頁(Physical Page悠栓，PP)，也為4096字節(jié)按价。

內(nèi)存映射和標(biāo)準(zhǔn)IO對(duì)比

而作為對(duì)比惭适，當(dāng)通過 標(biāo)準(zhǔn)IO 讀取一個(gè)文件時(shí)，步驟為：

1. 將 完整 的文件從磁盤拷貝到物理內(nèi)存（內(nèi)核空間）楼镐。
2. 將完整文件數(shù)據(jù)從 內(nèi)核空間 拷貝到 用戶空間 以供進(jìn)程訪問癞志。

內(nèi)存映射的使用

Fork函數(shù)

Fork系統(tǒng)調(diào)用用于創(chuàng)建一個(gè)新進(jìn)程，稱為子進(jìn)程框产，它與進(jìn)程（稱為系統(tǒng)調(diào)用fork的進(jìn)程）同時(shí)運(yùn)行凄杯，此進(jìn)程稱為父進(jìn)程。創(chuàng)建新的子進(jìn)程后秉宿，兩個(gè)進(jìn)程將執(zhí)行fork（）系統(tǒng)調(diào)用之后的下一條指令戒突。子進(jìn)程使用相同的pc（程序計(jì)數(shù)器），相同的CPU寄存器描睦，在父進(jìn)程中使用的相同打開文件膊存。

1. fork函數(shù)會(huì)在父進(jìn)程中創(chuàng)建子進(jìn)程，子進(jìn)程的堆，棧隔崎，數(shù)據(jù)段今艺，PC指針都是從父進(jìn)程中復(fù)制過來的，和父進(jìn)程是獨(dú)立的爵卒，但是內(nèi)容是一致的虚缎。代碼段子進(jìn)程和父進(jìn)程是共享的。
2. fork（）的返回值可能為-1,0技潘，和一個(gè)正數(shù)遥巴。-1表示fork（）調(diào)用失敗，0表示返回子進(jìn)程執(zhí)行結(jié)果享幽，正數(shù)表示返回父進(jìn)程結(jié)果（正數(shù)即為子進(jìn)程ID）铲掐。
3. 在fork的時(shí)候，緩存被復(fù)制到了子進(jìn)程空間值桩。

Linux下可以使用fork函數(shù)創(chuàng)建新的進(jìn)程摆霉，顯然創(chuàng)建的新進(jìn)程帶有自己獨(dú)立的虛擬地址空間。在當(dāng)前進(jìn)程調(diào)用fork函數(shù)時(shí)奔坟，內(nèi)核為新進(jìn)程創(chuàng)建各種數(shù)據(jù)結(jié)構(gòu)携栋，并為其分配唯一的進(jìn)程ID。為給新進(jìn)程創(chuàng)建虛擬內(nèi)存咳秉，創(chuàng)建當(dāng)前進(jìn)程的mm_struct婉支、區(qū)域結(jié)構(gòu)和頁表的副本。兩個(gè)進(jìn)程中的每個(gè)頁面都標(biāo)記為只讀澜建，兩個(gè)進(jìn)程中每個(gè)區(qū)域結(jié)構(gòu)都標(biāo)記為私有寫時(shí)復(fù)制向挖。

當(dāng) fork 在新進(jìn)程中返回時(shí)，新進(jìn)程現(xiàn)在的虛擬頁面剛好和調(diào)用 fork 時(shí)存在的虛擬內(nèi)存相同炕舵。當(dāng)這兩個(gè)進(jìn)程中某個(gè)進(jìn)行寫操作時(shí)何之，寫時(shí)復(fù)制就會(huì)創(chuàng)建新頁面，因此咽筋，也就為每個(gè)進(jìn)程保持了私有地址空間的抽象概念溶推。

execve函數(shù)

execve（執(zhí)行文件）在進(jìn)程中啟動(dòng)新的程序，在子進(jìn)程中調(diào)用exec函數(shù)啟動(dòng)新的程序奸攻。exec函數(shù)一共有六個(gè)蒜危，其中execve為內(nèi)核級(jí)系統(tǒng)調(diào)用，其他（execl睹耐，execle舰褪，execlp，execv疏橄，execvp）都是調(diào)用execve的庫函數(shù)。

假設(shè)運(yùn)行在當(dāng)前進(jìn)程中的程序執(zhí)行了如下的調(diào)用：

execve("a.out",NULL,NULL) ;

execve函數(shù)在當(dāng)前進(jìn)程中加載并運(yùn)行包含在可執(zhí)行目標(biāo)文件a.out中的程序，用a.out程序有效地替代了當(dāng)前程序捎迫。加載并運(yùn)行a.out需要以下幾個(gè)步驟：

1. 刪除已存在的用戶區(qū)域晃酒。刪除當(dāng)前進(jìn)程虛擬地址用戶部分中的已存在的區(qū)域結(jié)構(gòu)。
2. 映射私有區(qū)域窄绒。為新程序的文本贝次、數(shù)據(jù)、bss和棧區(qū)域創(chuàng)建新的區(qū)域結(jié)構(gòu)彰导。所有這些新的區(qū)域都是私有的蛔翅、寫時(shí)拷貝的。文本和數(shù)據(jù)區(qū)域被映射為a.out文件中的文本和數(shù)據(jù)區(qū)位谋。bss區(qū)域是請(qǐng)求二進(jìn)制零的山析，映射到匿名文件，其大小包含在a.out中掏父。棧和堆區(qū)域也是請(qǐng)求二進(jìn)制零的笋轨。
3. 映射共享區(qū)域。如果a.out程序與共享對(duì)象(或目標(biāo))鏈接赊淑，比如標(biāo)準(zhǔn)C庫libc.so爵政，那么這些對(duì)象都是動(dòng)態(tài)鏈接到這個(gè)程序的，然后再映射到用戶虛擬地址空間中的共享區(qū)域內(nèi)陶缺。
4. 設(shè)置程序計(jì)數(shù)器(PC)钾挟。execve做的最后一件事情就是設(shè)置當(dāng)前進(jìn)程上下文中的程序計(jì)數(shù)器慎王，使之指向文本區(qū)域的入口點(diǎn)嚷缭。
   下一次調(diào)度這個(gè)進(jìn)程時(shí)，它將從這個(gè)入口點(diǎn)開始執(zhí)行芦昔。Linux將根據(jù)需要換入代碼和數(shù)據(jù)頁面伶贰。

內(nèi)存映射實(shí)現(xiàn)

內(nèi)存映射的實(shí)現(xiàn)過程主要是通過 Linux 系統(tǒng)下的系統(tǒng)調(diào)用函數(shù) mmap蛛砰，取消映射則是通過 munmap 函數(shù)。

mmap 函數(shù)的作用相當(dāng)于：創(chuàng)建虛擬內(nèi)存區(qū)域+與共享對(duì)象建立映射關(guān)系黍衙。mmap在用戶空間映射調(diào)用系統(tǒng)中作用很大泥畅。

mmap將一個(gè)文件或者其它對(duì)象映射進(jìn)內(nèi)存。文件被映射到多個(gè)頁上琅翻，如果文件的大小不是所有頁的大小之和位仁，最后一個(gè)頁不被使用的空間將會(huì)清零。

該函數(shù)主要用途有三個(gè)：

1. 將一個(gè)普通文件映射到內(nèi)存中方椎，通常在需要對(duì)文件進(jìn)行頻繁讀寫時(shí)使用聂抢，這樣用內(nèi)存讀寫取代I/O讀寫，以獲得較高的性能棠众；
2. 將特殊文件進(jìn)行匿名內(nèi)存映射琳疏，可以為關(guān)聯(lián)進(jìn)程提供共享內(nèi)存空間有决；
3. 為無關(guān)聯(lián)的進(jìn)程提供共享內(nèi)存空間，一般也是將一個(gè)普通文件映射到內(nèi)存中空盼。

mmap 函數(shù)聲明

頭文件

<sys/mman.h>

函數(shù)原型

void* mmap(void* start,size_t length,int prot,int flags,int fd,off_t offset);
int munmap(void* start,size_t length);

在 mmap函數(shù)各個(gè)參數(shù)含義：

1. start: 期望的進(jìn)程虛擬內(nèi)存起始位置书幕，填 NULL 時(shí)由內(nèi)核來決定起始位置
2. length: 需要映射的對(duì)象字節(jié)大小
3. fd: 文件句柄
4. offset: 距離文件開始處的偏移量
5. prot: 映射對(duì)象的訪問權(quán)限，用于可指定是否可讀寫揽趾、執(zhí)行台汇。
6. flags: 映射對(duì)象的類型，例如指定是映射普通文件還是請(qǐng)求二進(jìn)制零篱瞎、映射共享對(duì)象還是私有的寫時(shí)復(fù)制對(duì)象等苟呐。

前4項(xiàng)地含義可通過下圖更直觀地了解：

后面2項(xiàng)的含義為，通過映射關(guān)系和是否組合俐筋。

總結(jié)起來有4種組合:

1. 私有文件映射
   多個(gè)進(jìn)程使用同樣的物理內(nèi)存頁進(jìn)行初始化牵素，但是各個(gè)進(jìn)程對(duì)內(nèi)存文件的修改不會(huì)共享，也不會(huì)反應(yīng)到物理文件中
2. 私有匿名映射
   mmap會(huì)創(chuàng)建一個(gè)新的映射校哎，各個(gè)進(jìn)程不共享两波，這種使用主要用于分配內(nèi)存(malloc分配大內(nèi)存會(huì)調(diào)用mmap)。
   例如開辟新進(jìn)程時(shí)闷哆，會(huì)為每個(gè)進(jìn)程分配虛擬的地址空間腰奋，這些虛擬地址映射的物理內(nèi)存空間各個(gè)進(jìn)程間讀的時(shí)候共享，寫的時(shí)候會(huì)copy-on-write抱怔。
3. 共享文件映射
   多個(gè)進(jìn)程通過虛擬內(nèi)存技術(shù)共享同樣的物理內(nèi)存空間劣坊，對(duì)內(nèi)存文件 的修改會(huì)反應(yīng)到實(shí)際物理文件中，他也是進(jìn)程間通信(IPC)的一種機(jī)制屈留。
4. 共享匿名映射
   這種機(jī)制在進(jìn)行fork的時(shí)候不會(huì)采用寫時(shí)復(fù)制局冰，父子進(jìn)程完全共享同樣的物理內(nèi)存頁，這也就實(shí)現(xiàn)了父子進(jìn)程通信(IPC).

這里值得注意的是灌危，mmap只是在虛擬內(nèi)存分配了地址空間康二，只有在第一次訪問虛擬內(nèi)存的時(shí)候才分配物理內(nèi)存。
在mmap之后勇蝙，并沒有在將文件內(nèi)容加載到物理頁上沫勿，只上在虛擬內(nèi)存中分配了地址空間。當(dāng)進(jìn)程在訪問這段地址時(shí)味混，通過查找頁表产雹，發(fā)現(xiàn)虛擬內(nèi)存對(duì)應(yīng)的頁沒有在物理內(nèi)存中緩存，則產(chǎn)生"缺頁"翁锡，由內(nèi)核的缺頁異常處理程序處理蔓挖，將文件對(duì)應(yīng)內(nèi)容，以頁為單位(4096)加載到物理內(nèi)存馆衔，注意是只加載缺頁瘟判，但也會(huì)受操作系統(tǒng)一些調(diào)度策略影響怨绣，加載的比所需的多。

mmap在write和read時(shí)會(huì)發(fā)生什么

write

1. 進(jìn)程(用戶態(tài))將需要寫入的數(shù)據(jù)直接copy到對(duì)應(yīng)的mmap地址(內(nèi)存copy)
2. 若mmap地址未對(duì)應(yīng)物理內(nèi)存荒适，則產(chǎn)生缺頁異常梨熙，由內(nèi)核處理
3. 若已對(duì)應(yīng)，則直接copy到對(duì)應(yīng)的物理內(nèi)存
4. 由操作系統(tǒng)調(diào)用刀诬，將臟頁回寫到磁盤（通常是異步的）

因?yàn)槲锢韮?nèi)存是有限的，mmap在寫入數(shù)據(jù)超過物理內(nèi)存時(shí)邪财，操作系統(tǒng)會(huì)進(jìn)行頁置換陕壹，根據(jù)淘汰算法，將需要淘汰的頁置換成所需的新頁树埠，所以mmap對(duì)應(yīng)的內(nèi)存是可以被淘汰的（若內(nèi)存頁是"臟"的糠馆，則操作系統(tǒng)會(huì)先將數(shù)據(jù)回寫磁盤再淘汰）。這樣怎憋，就算mmap的數(shù)據(jù)遠(yuǎn)大于物理內(nèi)存又碌，操作系統(tǒng)也能很好地處理，不會(huì)產(chǎn)生功能上的問題绊袋。

read

從圖中可以看出毕匀，mmap要比普通的read系統(tǒng)調(diào)用少了一次copy的過程。因?yàn)閞ead調(diào)用癌别，進(jìn)程是無法直接訪問kernel space的皂岔，所以在read系統(tǒng)調(diào)用返回前，內(nèi)核需要將數(shù)據(jù)從內(nèi)核復(fù)制到進(jìn)程指定的buffer展姐。但mmap之后躁垛，進(jìn)程可以直接訪問mmap的數(shù)據(jù)(page cache)

而在 iOS 開發(fā)中，當(dāng)我們需要的數(shù)據(jù)類型是 NSData 時(shí)圾笨，可以更簡(jiǎn)便地通過調(diào)用以下方法

@interface NSData (NSDataCreation)

+ (nullable instancetype)dataWithContentsOfFile:(NSString *)path options:(NSDataReadingOptions)readOptionsMask error:(NSError **)errorPtr;

系統(tǒng)動(dòng)態(tài)內(nèi)存分配

動(dòng)態(tài)內(nèi)存分配器維護(hù)一個(gè)進(jìn)程的虛擬內(nèi)存區(qū)域教馆，稱為堆。

對(duì)于每個(gè)進(jìn)程擂达，內(nèi)核維護(hù)著一個(gè)變量brk土铺，指向堆的頂部。

分配器將堆視為一組不同大小的塊的集合來維護(hù)谍婉，每個(gè)塊是一個(gè)連續(xù)的虛擬內(nèi)存片舒憾，要么是已分配的，要么是空閑的穗熬。

分配器有兩種基本風(fēng)格镀迂，兩種風(fēng)格都要求應(yīng)用顯式地分配塊，它們的不同之處在于由哪個(gè)實(shí)體來負(fù)責(zé)釋放已分配的塊唤蔗。

1. 顯式分配器要求應(yīng)用顯式地釋放任何已分配的塊探遵，比如C中的malloc和free窟赏，C++中的new和delete。
2. 隱式分配器要求分配器檢測(cè)一個(gè)已分配塊何時(shí)不再被程序所使用箱季，那么就釋放這個(gè)塊涯穷，隱式分配器也叫做垃圾收集器。

函數(shù)聲明

malloc函數(shù)

C標(biāo)準(zhǔn)庫提供了一個(gè)稱為malloc程序包的顯示分配器藏雏，程序通過調(diào)用malloc函數(shù)來從堆中分配塊拷况。

void *malloc(size_t size);

malloc函數(shù)返回一個(gè)指針，指向大小至少size字節(jié)的內(nèi)存塊掘殴，這個(gè)塊會(huì)為可能包含在這個(gè)塊內(nèi)的任何數(shù)據(jù)對(duì)象類型做對(duì)齊赚瘦。

如果malloc遇到問題（例如程序要求的內(nèi)存塊比可用的虛擬內(nèi)存還要大），那么它就返回NULL奏寨，并設(shè)置errno起意。malloc不初始化它返回的內(nèi)存。

動(dòng)態(tài)分配器病瞳，例如 malloc揽咕，可以通過 使用 mmap 和 munmap函數(shù)，顯示的分配和釋放堆套菜，或者還可以使用 sbrk函數(shù)：

sbrk函數(shù)

void *sbrk(intptr_t incr);

sbrk函數(shù)通過將內(nèi)核的brk指針增加incr來擴(kuò)展和收縮堆亲善。

如果成功，它就返回brk的舊值笼踩，否則它就返回-1逗爹，并將errno設(shè)置為ENOMEM

如果incr為零，那么sbrk就返回brk的當(dāng)前值

free函數(shù)

void free(void *ptr);

程序是通過free函數(shù)來釋放已經(jīng)分配的堆塊嚎于。

ptr參數(shù)必須指向一個(gè)從malloc掘而、calloc或者realloc獲得的已分配塊的起始位置。如果不是于购，那么free的行為就是未定義的袍睡。更糟糕的是，既然它什么都不返回肋僧，free就不會(huì)告訴應(yīng)用出現(xiàn)了錯(cuò)誤斑胜。

分配器需實(shí)現(xiàn)的規(guī)則和目標(biāo)

規(guī)則：

• 處理任意請(qǐng)求序列（不能假設(shè)所有的分配請(qǐng)求都有相匹配的釋放請(qǐng)求，例如請(qǐng)求順序是 1嫌吠，2止潘，3，4辫诅，5 而釋放順序?yàn)?3凭戴，2，4炕矮，5）
• 立即響應(yīng)請(qǐng)求（不允許分配器為了提高性能重新排列或者緩沖請(qǐng)求）
• 只使用堆（為了使分配器是可擴(kuò)展的么夫，任何非標(biāo)量數(shù)據(jù)結(jié)構(gòu)都必須保存在堆里）
• 對(duì)齊塊者冤，分配器必須對(duì)齊塊，使得他們可以保存任何類型的數(shù)據(jù)對(duì)象
• 不修改已分配的塊（分配器只能操作或者改變空閑塊档痪，一旦塊被分配就不允許修改或者移動(dòng)了）

目標(biāo)：

• 最大化吞吐率
• 最大化內(nèi)存利用率

碎片

造成堆利用率很低的主要原因是一種稱為碎片（fragmentation）的現(xiàn)象涉枫，當(dāng)雖然有未使用的內(nèi)存但是不能用來滿足分配請(qǐng)求的時(shí)候，就會(huì)發(fā)生這種現(xiàn)象腐螟。

具體的來講愿汰，碎片就是用來描述一個(gè)系統(tǒng)中所有不可用的空閑內(nèi)存；這些資源之所以仍然未被使用遭垛，是因?yàn)樨?fù)責(zé)分配內(nèi)存的分配器使這些內(nèi)存無法使用尼桶。碎片只會(huì)在虛擬內(nèi)存中產(chǎn)生。

碎片有兩種形式：

1. 內(nèi)部碎片：已分配塊比有效載荷大的時(shí)候發(fā)生的锯仪。
   
   例如 malloc 一個(gè) char （1 byte）的空間，則必須分配 4KB (Linux 通常頁面大小)趾盐，或者因?yàn)閷?duì)齊庶喜，請(qǐng)求1個(gè)字，分配了6個(gè)字救鲤。
2. 外部碎片：空閑內(nèi)存合計(jì)起來足夠滿足一個(gè)分配請(qǐng)求久窟，但沒有一個(gè)單獨(dú)的空閑塊足夠大可以來處理這個(gè)請(qǐng)求。
   
   例如 頻繁的申請(qǐng)和釋放內(nèi)存本缠，會(huì)導(dǎo)致許多不連續(xù)的可用小內(nèi)存存在在分配頁中斥扛。但申請(qǐng)一塊較大內(nèi)存（申請(qǐng)內(nèi)存是連續(xù)的），即使小內(nèi)存總和大于要申請(qǐng)的內(nèi)存丹锹，也不可用稀颁。

外部碎片比內(nèi)部碎片的量化要困難的多，外部碎片還不可能測(cè)量楣黍。因?yàn)樗粌H取決于以前請(qǐng)求的模式和分配器的實(shí)現(xiàn)方式匾灶，還取決于將來請(qǐng)求的模式。

實(shí)現(xiàn)中會(huì)遇到的問題

可以想象出的最簡(jiǎn)單的分配器會(huì)把堆組織成一個(gè)大的字節(jié)數(shù)組租漂，還有一個(gè)指針p阶女，初始指向這個(gè)數(shù)組的第一個(gè)字節(jié)。為了分配size個(gè)字節(jié)哩治，malloc將p的當(dāng)前值保存在棧里秃踩，將p增加size，并將p的舊值返回到調(diào)用函數(shù)业筏。free只是簡(jiǎn)單地返回到調(diào)用函數(shù)而不做任何事情憔杨。

這個(gè)簡(jiǎn)單的分配器是一種極端情況，因?yàn)槊總€(gè)malloc和free只執(zhí)行很少的指令驾孔，吞吐率會(huì)極好芍秆。然而惯疙，因?yàn)榉峙淦鲝牟恢貜?fù)使用任何塊，內(nèi)存利用率將極差妖啥。一個(gè)實(shí)際的分配器要在吞吐率和利用率之間把握好平衡要考慮以下問題：

空閑塊組織：如何記錄空閑塊霉颠？

• 放置：如何選擇一個(gè)合適的空閑塊來放置一個(gè)新分配的塊？
• 分割：在將一個(gè)新分配的塊放置到某個(gè)空閑塊之后荆虱，如何處理這個(gè)空閑塊中的剩余部分蒿偎？
• 合并：如何處理一個(gè)剛剛被釋放的塊？

隱式空閑鏈表

任何實(shí)際的分配器都需要一些數(shù)據(jù)結(jié)構(gòu)怀读，允許它來區(qū)別塊邊界诉位，以及區(qū)別已分配塊和空閑塊。大多數(shù)分配器將這些信息嵌入塊本身菜枷。如下圖所示

在這種情況中苍糠，一個(gè)塊是由一個(gè)字的頭部、有效載荷啤誊、以及可能的一些額外的填充組成的岳瞭。頭部編碼了這個(gè)塊的大小以及這個(gè)塊是分配的還是空閑的。如果有一個(gè)雙字的對(duì)齊約束條件蚊锹，塊大小就總是8的倍數(shù)瞳筏，塊大小的最低3位總是0。假設(shè)有一個(gè)已分配的塊（a=1）牡昆，大小為24（0x18）字節(jié)姚炕，頭部將是

0x00000018|0x1=0x00000019

類似地，一個(gè)空閑塊（a=0）丢烘，大小為40（0x28）字節(jié)柱宦，頭部將是

0x00000028|0x=0x00000028

在頭部后面就應(yīng)該是調(diào)用 malloc 時(shí)請(qǐng)求的有效核載，有效核載后面是一片不使用的填充塊铅协，大小是任意的(分配器策略或用于滿足對(duì)其要求)忍宋。
這樣我們就可以利用上述的頭部來將堆組織為一個(gè)連續(xù)已分配和空閑塊的序列

上述結(jié)構(gòu)被稱為隱式空閑鏈表偏陪，因?yàn)榭臻e塊是通過頭部的大小字段隱含的連接的。分配器可以通過遍歷堆中所有的塊，從而遍歷整個(gè)空閑塊集合鸡典。

隱式空閑鏈表俩滥，是因?yàn)榭臻e塊是通過頭部中的大小字段隱含地連接著的眠副。分配器可以通過遍歷堆中所有的塊肪康，從而間接地遍歷整個(gè)空閑塊的集合。

隱式空閑鏈表的優(yōu)點(diǎn)是簡(jiǎn)單姜贡。顯著的缺點(diǎn)是任何操作的開銷试吁，要求空閑鏈表的搜索與堆中已分配塊和空閑塊的總數(shù)呈線性關(guān)系。

系統(tǒng)對(duì)齊要求和分配器對(duì)塊格式的選擇會(huì)對(duì)分配器上的最小塊大小有強(qiáng)制的要求。沒有已分配塊或者空閑塊可以比這個(gè)最小值還小熄捍。

放置已分配的塊

分配器搜索空閑鏈表烛恤，查找一個(gè)足夠大可以放置所請(qǐng)求塊的空閑塊。分配器執(zhí)行這種搜索的方式是由放直策咯 (placement policy) 確定的余耽。一些常見的策略是首次適配 (first fit)缚柏、下一次適配 (next fit) 和最佳適配 (best fit)。

• 首次適配從頭開始搜索空閑鏈表碟贾，選擇第一個(gè)合適的空閑塊币喧。
• 下一次適配和首次適配很相似，是從上一次查詢結(jié)束的地方開始袱耽。
• 最佳適配檢查每個(gè)空閑塊杀餐，選擇適合所需請(qǐng)求大小的最小空閑塊。

首次適配的優(yōu)點(diǎn)是它往往將大的空閑塊保留在鏈表的后面朱巨。

缺點(diǎn)是它往在靠近鏈表起始處留下小空閑塊的"碎片飛這就增加了對(duì)較大塊的搜索時(shí)間史翘。

下一次適配比首次適配運(yùn)行起來明顯要快一些，尤其是當(dāng)鏈表的前面布滿了許多小的碎片時(shí)冀续。

下一次適配的存儲(chǔ)器利用率要比首次適配低得多恶座。

最佳適配比首次適配和下一次適配的存儲(chǔ)器利用率都要高一些。

然而沥阳，在簡(jiǎn)單空閑鏈表組織結(jié)構(gòu)中,使用最佳適配的缺點(diǎn)是它要求對(duì)堆進(jìn)行徹底的搜索。

分割空閑塊

一旦分配器找到一個(gè)匹配的空閑塊自点，它就必須做另一個(gè)策略決定桐罕，那就是分配這個(gè)空閑塊中多少空間。

一個(gè)選擇是用整個(gè)空閑塊桂敛。簡(jiǎn)單而快捷功炮，但是主要的缺點(diǎn)就是它會(huì)造成內(nèi)部碎片。如果放置策略趨向于產(chǎn)生好的匹配术唬，那么額外的內(nèi)部碎片也是可以接受的薪伏。

如果匹配不太好，那么分配器通常會(huì)選擇將這個(gè)空閑塊分割為兩部分粗仓。第一部分變成分配塊嫁怀，而剩下的變成一個(gè)新的空閑塊。

獲取額外的堆存儲(chǔ)器

如果分配器不能為請(qǐng)求塊找到合適的空閑塊借浊，一個(gè)選擇是通過合并那些在存儲(chǔ)器中物理上相鄰的空閑塊來創(chuàng)建一些更大的空閑塊塘淑。如果這樣還是不能生成一個(gè)足夠大的塊，或者如果空閑塊已經(jīng)最大程度地合并了蚂斤，那么分配器就會(huì)通過調(diào)用 sbrk 函數(shù)存捺，向內(nèi)核請(qǐng)求額外的堆存儲(chǔ)器。

合并空閑塊

當(dāng)分配器釋放一個(gè)已分配塊時(shí)曙蒸，可能有其他空閑塊與這個(gè)新釋放的空閑塊相鄰捌治。這些鄰接的空閑塊可能引起一種現(xiàn)象岗钩，叫做假碎片(fault fragmentation)，就是有許多可用的空閑塊被切割 成小的肖油、無法使用的空閑塊兼吓。

為了解決假碎片問題，任何實(shí)際的分配器都必須合并相鄰的空閑塊构韵，這個(gè)過程稱為合并 ( coalescing)周蹭。

分配器可以選擇立即合并 (immediate coalescing)，也就是在每次一個(gè)塊被釋放時(shí)疲恢，就合并所有的相鄰塊凶朗。或者它也可 以選擇推遲合并 (deferred coalescing)显拳，也就是等到某個(gè)稍晚的時(shí)候再合并空閑塊棚愤。

立即合并很簡(jiǎn)單明了，可以在常數(shù)時(shí)間內(nèi)執(zhí)行完成杂数，但是對(duì)于某些請(qǐng)求模式宛畦，這種方式會(huì)產(chǎn)生一種形式的抖動(dòng)，塊會(huì)反復(fù)地合并揍移，然后馬上分割次和。

如何合并空閑塊

試想如下場(chǎng)景：假設(shè)我們要釋放的chunk為P，它緊鄰的前一個(gè)chunk為FD那伐，緊鄰的后一個(gè)chunk為BK踏施，且BK與FD都為free chunk。將P于BK合并在一起是很容易的罕邀，因?yàn)榭梢酝ㄟ^P的size字段輕松定位到BK的開始位置畅形，進(jìn)而獲取BK的size等等，但是將P于FD合并卻很難诉探，我們必須從頭遍歷整個(gè)堆日熬，找到FD，然后加以合并肾胯，這就意味著每次進(jìn)行chunk釋放操作消耗的時(shí)間與堆的大小成線性關(guān)系竖席。為了解決這個(gè)問題，Knuth提出了一種聰明而通用的技術(shù)——邊界標(biāo)記阳液。

Knuth在每個(gè)塊的最后添加了一個(gè)腳部(Footer)怕敬，它就是該塊頭部(header)的一個(gè)副本，我們稱之為邊界標(biāo)記：

顯然每個(gè)塊的腳部都在其相鄰的下一個(gè)塊的頭部的前4個(gè)字節(jié)處帘皿。通過這個(gè)腳部东跪，堆內(nèi)存管理器就可以很容易地得到前一個(gè)塊的起始位置和分配狀態(tài)，進(jìn)而加以合并了。

但是虽填，邊界標(biāo)記同時(shí)帶來了一個(gè)問題：它要求每個(gè)塊都包含一個(gè)頭部和腳部丁恭，如果應(yīng)用程序頻繁地進(jìn)行小內(nèi)存的申請(qǐng)和釋放操作的話(比如1，2個(gè)字節(jié))斋日，就會(huì)造成很大的性能損耗牲览。

同時(shí)，考慮到只有在對(duì)釋放塊進(jìn)行合并的時(shí)候才需要腳部恶守，也就是說對(duì)于分配塊而言它并不需要腳部第献，因此我們可以對(duì)這個(gè)腳部加以優(yōu)化——將前一個(gè)塊的已分配/空閑標(biāo)記位存儲(chǔ)在當(dāng)前塊的size字段的第1，或2比特位上兔港，這樣如果我們通過當(dāng)前塊的size字段知道了前一個(gè)塊為釋放塊庸毫，那么就可得出結(jié)論：當(dāng)前塊地址之前的4個(gè)字節(jié)為前一個(gè)釋放塊的腳部，我們可以通過該腳部獲取前一個(gè)塊的起始位置衫樊；如果當(dāng)前塊的size字段的標(biāo)記位表明前一個(gè)塊是于分配塊的話飒赃，那么就可得出另一個(gè)結(jié)論：前一個(gè)塊沒有腳部，即當(dāng)前塊地址之前的4個(gè)字節(jié)為前一個(gè)于分配塊的payload或padding的最后部分科侈。新的塊格式圖如下：

邊界標(biāo)記的概念是簡(jiǎn)單優(yōu)雅的载佳，它對(duì)許多不同類型的分配器和空閑鏈表組織都是通用的，也存在一個(gè)潛在的缺陷臀栈。它要求每個(gè)塊都保持一個(gè)頭部和一個(gè)腳部蔫慧，在應(yīng)用程序操作許多個(gè)小塊時(shí)，會(huì)產(chǎn)生顯著的存儲(chǔ)器開銷权薯。

顯式空閑鏈表

顯式空閑鏈表藕漱，是在隱式空閑鏈表上做的優(yōu)化

在隱式空閑鏈表中，由于塊的分配與堆塊的總數(shù)呈線性關(guān)系崭闲，所以對(duì)于通用分配器來說，隱式空閑鏈表是不合適的威蕉。

如果我們將空閑塊組織為某種顯示的數(shù)據(jù)結(jié)構(gòu)刁俭，由于程序不需要一個(gè)空閑塊的主題，所以我們將數(shù)據(jù)結(jié)構(gòu)的指針存放在空閑塊的主體里面韧涨，我們將堆組織為一個(gè)雙向空閑鏈表牍戚，在每個(gè)空閑塊中都包含一個(gè) pred 前驅(qū)和 succ 后繼指針。

使用雙向鏈表后虑粥，使得首次適配的分配時(shí)間從塊總數(shù)的線性時(shí)間減少到空閑塊數(shù)量的線性時(shí)間如孝。不過釋放一個(gè)塊的時(shí)間可以是線性的，也可以是常數(shù)的娩贷。

釋放時(shí)間取決于放置策略

• 后進(jìn)先出
  用 LIFO 的順序維護(hù)鏈表第晰，將新釋放的塊放置在鏈表的開始處，釋放和合并可以在常數(shù)時(shí)間內(nèi)完成。如果使用了邊界標(biāo)記茁瘦，合并也可以在常數(shù)時(shí)間內(nèi)品抽。
• 按地址放置
  按照地址順序來維護(hù)鏈表，其中立案表內(nèi)每個(gè)塊的地址都小于它的后繼的地址甜熔。此時(shí)圆恤，釋放一個(gè)塊需要線性時(shí)間的搜索來定位合適的前驅(qū)。

按照地址順序排序的首次適配比LIFO排序的首次適配具有更高的內(nèi)存利用率腔稀，接近最佳適配的利用率（因?yàn)榭瞻椎刂废嘟?/p>

分離的空閑鏈表

在顯示空閑鏈表中盆昙，一個(gè)使用單向空閑塊鏈表的分配器需要與空閑塊數(shù)量呈線性關(guān)系的時(shí)間來分配塊。

為了解決這個(gè)問題焊虏，一種流行的減少分配時(shí)間的方法淡喜，通常稱為分離存儲(chǔ)（segregated storage），就是維護(hù)多個(gè)空閑鏈表炕淮，其中每個(gè)鏈表有大致相等的大小拆火。

例如，我們可以根據(jù)2的冪來劃分大小
~
{1}涂圆，{2}们镜，{3}，{3润歉，4}模狭，{5 ~ 8}，...踩衩，{1024}嚼鹉，{1024 ~ 2048}，{2049 ~ 4096}驱富，{4096 ~ ∞}

分配器維護(hù)著一個(gè)空閑鏈表數(shù)組 锚赤，每個(gè)大小類一個(gè)空閑鏈表，按照大小的升序排列褐鸥。當(dāng)分配器需要一個(gè)大小為 n 的塊時(shí)线脚，他就搜索相應(yīng)的空閑鏈表，如不能找到則搜索下一個(gè)鏈表叫榕，以此類推浑侥。

簡(jiǎn)單的分離存儲(chǔ)：

每個(gè)大小類的空閑鏈表包含大小相等的塊，每個(gè)塊的大小就是這個(gè)大小類中最大元素的大小晰绎。

為了分配給一個(gè)給定大小的塊寓落，我們檢查相應(yīng)的空閑鏈表，如果鏈表為空荞下，我們簡(jiǎn)單地分配其中第一塊的全部伶选。此時(shí)空閑塊是不會(huì)分割以滿足分配請(qǐng)求的史飞。如果鏈表為空，分配器就向操作系統(tǒng)申請(qǐng)一個(gè)固定大小的額外存儲(chǔ)器片考蕾，將這個(gè)片分成大小相等的塊祸憋，并將這些塊鏈接起來形成新的空閑鏈表。釋放時(shí)肖卧，只需要簡(jiǎn)單的將這個(gè)塊插入到相應(yīng)的空閑鏈表前部蚯窥。

這樣的話，分配和釋放都可以在常數(shù)時(shí)間內(nèi)完成塞帐。由于我們不進(jìn)行分割拦赠，那么也就沒有合并，所以我們就不需要一個(gè)已分配/空閑標(biāo)記葵姥，已分配塊也就不需要頭部荷鼠，因?yàn)闆]有合并，同樣也不需要腳部榔幸。

缺點(diǎn) ：容易造成外部碎片和內(nèi)部碎片允乐，因?yàn)榭臻e塊是不會(huì)分割的，所以可能會(huì)造成內(nèi)部碎片削咆。更糟糕的是牍疏，因?yàn)椴粫?huì)合并塊，所以某些引用模式會(huì)造成極多的碎片拨齐。

分離適配方法：

為了改進(jìn)上述的缺點(diǎn)鳞陨，我們可以先找到合適的塊，分割（可選的）并使用瞻惋，同時(shí)將剩余的塊插入到適當(dāng)?shù)目臻e鏈表中厦滤。如果找不到，則繼續(xù)搜索下一個(gè)更大的類的空閑鏈表歼狼。

分離適配方法是一種常見的選擇掏导，C標(biāo)準(zhǔn)庫提供的GNU malloc 包就是采用的這種方法。因?yàn)檫@種方法即快速羽峰，對(duì)內(nèi)存的使用也很有效率碘菜。搜索時(shí)間減少了，因?yàn)樗阉鞅幌拗圃诙训哪硞€(gè)部分限寞，而不是整個(gè)堆。

伙伴系統(tǒng)——分離適配的特例

伙伴系統(tǒng)是分離適配的一種特例仰坦，其中每個(gè)大小類都是2的冪履植。基本思路是假設(shè)一個(gè)堆的大小為 2的m次方 個(gè)字悄晃，我們?yōu)槊總€(gè)塊大小 2的k次方 維護(hù)一個(gè)分離空閑鏈表玫霎，其中 0 ≤ k ≤ m凿滤。請(qǐng)求塊大小向上舍入到最接近的2的冪。

這樣庶近，給定地址和塊的大小翁脆，很容易計(jì)算出它的伙伴的地址，也就是說：一個(gè)塊的地址和它的伙伴的地址只有一位不同鼻种。

伙伴系統(tǒng)分配器的主要優(yōu)點(diǎn)是快速搜索和快速合并反番，主要缺點(diǎn)是要求快為2的冪可能導(dǎo)致顯著的內(nèi)存碎片。因此叉钥，伙伴系統(tǒng)分配器不適合通用目的的工作負(fù)載（適用某些特定應(yīng)用）罢缸。

垃圾回收

垃圾收集器將內(nèi)存視為一張可達(dá)圖(reachability graph)。該圖的節(jié)點(diǎn)被分成一組根節(jié)點(diǎn)(root node)和一組堆節(jié)點(diǎn)(heap node)投队。每個(gè)堆節(jié)點(diǎn)對(duì)應(yīng)于堆中的一個(gè)已分配塊枫疆。有向邊(p->q)表示塊p中的某個(gè)指針指向塊q中的某個(gè)位置。根節(jié)點(diǎn)對(duì)應(yīng)于這樣一種不在堆中的位置敷鸦，它們包含指向堆中的指針息楔。

垃圾收集器的角色就是維護(hù)可達(dá)圖的某種表示，并通過釋放不可達(dá)節(jié)點(diǎn)且將他們返回給空閑鏈表扒披，來定期回收它們值依。

Java這類語言可以維護(hù)精確地可達(dá)圖的表示，因此垃圾回收可以回收所有垃圾谎碍；而C++和C這樣的語言的收集器通常不能維護(hù)精確的可達(dá)圖表示鳞滨，叫做保守的垃圾收集器。

Mark & Sweep 垃圾收集器

Mark & Sweep 垃圾收集器由標(biāo)記(mark)階段和清除(sweep)階段組成蟆淀，標(biāo)記階段標(biāo)記處根節(jié)點(diǎn)的所有可達(dá)的和已分配的后繼拯啦。后繼是指根節(jié)點(diǎn)可達(dá)的節(jié)點(diǎn)指向的下一個(gè)已分配內(nèi)存塊。而后面的清除階段釋放每個(gè)未被標(biāo)記的已分配塊熔任。塊頭部中空閑的低位中的一位通常用來表示這個(gè)塊是否被標(biāo)記了褒链。

每次對(duì)mark函數(shù)的調(diào)用都標(biāo)記某個(gè)根節(jié)點(diǎn)的所有未標(biāo)記并且可達(dá)的后繼節(jié)點(diǎn)。在標(biāo)記階段的末尾疑苔，任何未標(biāo)記的已分配塊都被認(rèn)定為是不可達(dá)的甫匹，是垃圾，可以在清除階段回收惦费。

清除階段基于sweep函數(shù)的調(diào)用實(shí)現(xiàn)兵迅，sweep函數(shù)在堆中每個(gè)塊上反復(fù)循環(huán)，釋放它所遇到的所有未標(biāo)記的已分配塊薪贫，也就是垃圾恍箭。

void mark(ptr p)
{
    if ((b = isPtr(p)) == NULL)
    {
        return ;
    }
    if (blockMarked(b))
    {
        return ;
    }
    markBlock(b);
    len = length(b);
    for(i = 0; i < len; i++)
        mark(b[i]);          // 標(biāo)記后繼節(jié)點(diǎn)
    return ;
}
void sweep(ptr b, ptr end)
{
    while(b < end)
    {
        if (blockMarked(b))
            unmarkBlock(b);
        else if (blockAllocated(b))
            free(b);
        b = nextBlock(b);
    }
    return ;
}

C程序的保守Mark & Sweep

這里主要說明一下為什么C中的mark和sweep是保守的，也就是不能精確的維護(hù)一個(gè)可達(dá)圖的表示瞧省。

C語言的isPtr函數(shù)的實(shí)現(xiàn)是一個(gè)挑戰(zhàn)扯夭，原因如下：

C不會(huì)用任何類型信息來標(biāo)記內(nèi)存位置鳍贾。因此，對(duì)isPtr沒有一種明顯的方式來判斷它的輸入p是不是一個(gè)指針交洗。
即使我們知道p是一個(gè)指針骑科，對(duì)isPtr也沒有明顯的方式來判斷ps是否指向一個(gè)已分配塊的有效載荷中的某個(gè)位置。
對(duì)最后一個(gè)問題的解決辦法是构拳，將已分配塊集合維護(hù)成一顆平衡二叉樹概疆，這棵樹保持著這樣一個(gè)屬性：左子樹都是較小地址的塊盏混，右子樹都是較大地址的塊冰啃。isPtr函數(shù)用樹來執(zhí)行對(duì)已分配塊的二分查找绩脆。在每一步中，它依賴于塊頭部中的大小字段來判斷p是否落在這個(gè)塊的范圍之內(nèi)暇藏。

C語言中的Mark & sweep收集器必須是保守的蜜笤，其根本原因是C語言不會(huì)用類型信息來標(biāo)記內(nèi)存位置。因此盐碱，像int或float這樣的標(biāo)量可以偽裝成指針把兔。對(duì)收集器而言，由于缺少類型信息瓮顽，因此不能推斷出這個(gè)數(shù)據(jù)實(shí)際上是int而不是指針县好。因此，分配器必須保守地將塊b標(biāo)記為可達(dá)暖混，盡管事實(shí)上它可能是不可達(dá)的缕贡。

C語言常見內(nèi)存錯(cuò)誤

未初始化的本地指針

int sum(int a[], int n)
{
    int *p;
    int sum = 0;
    for (int i = 0; i < n; i++)
    sum += *p++;
}

假設(shè)您聲明了一個(gè)本地指針但是忘記初始化它。由于變量的內(nèi)存在堆棧上拣播，并且堆椓肋洌可能充滿了之前的活動(dòng)記錄所丟棄的數(shù)據(jù)，所以指針可以有任何值：

未初始化的局部變量

int i;
double d;
scanf("%d %g", i, d); // wrong!!!
// here is the correct call:
scanf("%d %g", &i, &d);
scanf()不指定所有參數(shù)的類型贮配，而形參在預(yù)編譯的時(shí)候需要告訴系統(tǒng)要預(yù)留出多少的內(nèi)存空間谍倦，所以這里的參數(shù)不可以是未初始化的局部變量。

內(nèi)存溢出問題

#define array_size 100
int *a = (int *) malloc(sizeof(int *) * array_size);
for (int i = 0; i <= array_size; i++)
    a[i] = NULL;

這是一個(gè)顯然的錯(cuò)誤泪勒，但卻是我們經(jīng)常會(huì)不小心犯昼蛀，應(yīng)該把for循環(huán)中的小于等于改成小于。

超出所分配的內(nèi)存

#define array_size 100
int *a = (int *) malloc(array_size);
a[99] = 0; // this overwrites memory beyond the block

分配太少的內(nèi)存會(huì)導(dǎo)致之后的賦值覆蓋掉之前的內(nèi)存圆存。
應(yīng)該改為int a=(int)malloc(array_size*sizeof(int))

忘記給\0分配空間

有時(shí)叼旋，程序員忘記字符串是由\0結(jié)束的÷僬蓿考慮下面的函數(shù)夫植，該函數(shù)將字符串傳輸?shù)蕉眩?/p>

char *heapify_string(char *s){
    int len = strlen(s);

    char *new_s = (char *) malloc(len);
    strcpy(new_s, s);
    return new_s;
}

在這個(gè)例子中，程序沒有為字符串分配足夠的空間怕轿。malloc中的參數(shù)應(yīng)該為len+1偷崩，為終止的零字節(jié)留下空間。如果malloc分配的是8字節(jié)的倍數(shù)撞羽，當(dāng)len是8字節(jié)的倍數(shù)的時(shí)候heapify_string這個(gè)函數(shù)將會(huì)失敳薄（除非內(nèi)存大小不是舍入到更大的內(nèi)存大小）

另外诀紊，當(dāng)兩個(gè)字符串連接時(shí)谒出，結(jié)果字符串也有可能占用太多空間：

char q[] = “do not overflow”;
char r[] = ” memory”;
char s[16];
strcpy(s, q);
strcat(s, r);

需要22+1個(gè)字符，但只分配了16邻奠，所以寫操作會(huì)超出所分配的內(nèi)存（要知道strcat函數(shù)并不會(huì)為結(jié)果分配額外的內(nèi)存）

在運(yùn)行時(shí)堆棧上構(gòu)建指針并將指針返回給調(diào)用方

int *ptr_to_zero(){
    int i = 0;
    return &i;
}

盡管這個(gè)函數(shù)返回一個(gè)指向0值整數(shù)的指針笤喳，但是這個(gè)整數(shù)是在一個(gè)活動(dòng)記錄中。而這個(gè)函數(shù)返回時(shí)這個(gè)活動(dòng)記錄就會(huì)被立刻刪除碌宴，那么指針引用的內(nèi)存的值可以變成任意值杀狡，這還要取決于其他函數(shù)的調(diào)用情況。

運(yùn)算順序和優(yōu)先級(jí)導(dǎo)致的問題

// decrement a if a is greater than zero:
void dec_positive(int *a){
    *a--; // decrement the integer
    if (*a < 0) *a = 0; // make sure a is positive
}

函數(shù)里的第一行代碼本來想減少a的值贰镣，但是事實(shí)上減少的是指向a的指針呜象，錯(cuò)誤原因是–的優(yōu)先級(jí)雖然和一樣高，但是執(zhí)行順序是從右向左執(zhí)行的碑隆。當(dāng)不確定運(yùn)算優(yōu)先級(jí)時(shí)需要使用括號(hào)恭陡，之前的代碼改為(a)–即可。

意外地釋放相同的指針兩次

void my_write(x){
    ... use x ...
    free(x);
}
int *x = (int *) malloc(sizeof(int*) * N);
...
my_read(x);
...
my_write(x);
free(x); //oops, x is freed in my_write()!

引用已被釋放的內(nèi)存塊

一旦一個(gè)塊被釋放上煤，如果塊占用的內(nèi)存被另一個(gè)塊重用休玩，它的數(shù)據(jù)隨時(shí)可能被堆分配程序和應(yīng)用程序改變。因此劫狠，使用一個(gè)被釋放指針會(huì)導(dǎo)致不好的事情發(fā)生拴疤。您可能在塊被修改的地方讀取到垃圾，如果寫入塊嘉熊，則可能破壞程序已經(jīng)分配好的堆或數(shù)據(jù)遥赚。下面是一個(gè)引用已釋放指針的程序的示例：

void my_write(x){
    ... use x ...
    free(x);
}
int *x = (int *) malloc(sizeof(int*) * N);
...
my_read(x);
...
my_write(x);
...
my_read(x); // oops, x was freed by my write!
...
my_write(x);

避免這種錯(cuò)誤的一種方法是在釋放指針時(shí)替換帶有null的指針。然而阐肤，如果指針有多個(gè)副本凫佛，這并不能解決問題。事實(shí)上這是一個(gè)常見的錯(cuò)誤發(fā)生方式：程序員完成了一個(gè)引用并釋放了塊孕惜，忘記了還有其他引用可能被使用愧薛。

內(nèi)存泄漏

內(nèi)存泄漏形象的比喻是”操作系統(tǒng)可提供給所有進(jìn)程的存儲(chǔ)空間正在被某個(gè)進(jìn)程榨干”，最終結(jié)果是程序運(yùn)行時(shí)間越長(zhǎng)衫画，占用存儲(chǔ)空間越來越多毫炉，最終用盡全部存儲(chǔ)空間，整個(gè)系統(tǒng)崩潰削罩。

void my_function(char *msg){
    // allocate space for a string
    char *full_msg = (char *) malloc(strlen(msg) + 100);
    strcpy(full_msg, "The following error was encountered: ");
    strcat(full_msg, msg);
    if (!display(full_msg)) return;
    ...
    free(full_msg);   
}

在這個(gè)例子中瞄勾，被分配的內(nèi)存在函數(shù)最后一行被釋放费奸，但如果在display那里發(fā)生了錯(cuò)誤，這個(gè)函數(shù)就會(huì)提前返回而沒有釋放內(nèi)存进陡。異常愿阐、錯(cuò)誤、各種形式的拋出和捕獲通常都會(huì)與內(nèi)存泄漏有關(guān)趾疚。

忘記釋放數(shù)據(jù)結(jié)構(gòu)的各個(gè)部分導(dǎo)致內(nèi)存泄漏

typedef struct  {
    char *name;
    int age;
    char *address;
    int phone;
} Person;
void my_function(){
    Person *p = (Person *) malloc(sizeof(Person));
    p->name = (char *) malloc(M);
    ...
    p->address = (char *) malloc(N);
    ...
    free(p); // what about name and address?
}

在這個(gè)例子中缨历，一個(gè)person結(jié)構(gòu)體被分配和釋放。但是作為這個(gè)結(jié)構(gòu)體的一部分糙麦，name和address被分配了卻沒有被釋放辛孵。