概述

我們都知道一個(gè)進(jìn)程是與其他進(jìn)程共享CPU和內(nèi)存資源的。正因如此，操作系統(tǒng)需要有一套完善的內(nèi)存管理機(jī)制才能防止進(jìn)程之間內(nèi)存泄漏的問題。

為了更加有效地管理內(nèi)存并減少出錯(cuò)，現(xiàn)代操作系統(tǒng)提供了一種對(duì)主存的抽象概念，即是虛擬內(nèi)存（Virtual Memory）。 虛擬內(nèi)存為每個(gè)進(jìn)程提供了一個(gè)一致的、私有的地址空間，它讓每個(gè)進(jìn)程產(chǎn)生了一種自己在獨(dú)享主存的錯(cuò)覺（每個(gè)進(jìn)程擁有一片連續(xù)完整的內(nèi)存空間） 。

理解不深刻的人會(huì)認(rèn)為虛擬內(nèi)存只是“使用硬盤空間來擴(kuò)展內(nèi)存“的技術(shù)，這是不對(duì)的。 虛擬內(nèi)存的重要意義是它定義了一個(gè)連續(xù)的虛擬地址空間 ，使得程序的編寫難度降低。并且， 把內(nèi)存擴(kuò)展到硬盤空間只是使用虛擬內(nèi)存的必然結(jié)果，虛擬內(nèi)存空間會(huì)存在硬盤中，并且會(huì)被內(nèi)存緩存（按需），有的操作系統(tǒng)還會(huì)在內(nèi)存不夠的情況下，將某一進(jìn)程的內(nèi)存全部放入硬盤空間中，并在切換到該進(jìn)程時(shí)再從硬盤讀取 （這也是為什么Windows會(huì)經(jīng)常假死的原因...）。

虛擬內(nèi)存主要提供了如下三個(gè)重要的能力：

• 它把主存看作為一個(gè)存儲(chǔ)在硬盤上的虛擬地址空間的高速緩存，并且只在主存中緩存活動(dòng)區(qū)域（按需緩存）。
• 它為每個(gè)進(jìn)程提供了一個(gè)一致的地址空間，從而降低了程序員對(duì)內(nèi)存管理的復(fù)雜性。
• 它還保護(hù)了每個(gè)進(jìn)程的地址空間不會(huì)被其他進(jìn)程破壞。

介紹了虛擬內(nèi)存的基本概念之后，接下來的內(nèi)容將會(huì)從虛擬內(nèi)存在硬件中如何運(yùn)作逐漸過渡到虛擬內(nèi)存在操作系統(tǒng)（Linux）中的實(shí)現(xiàn)。

CPU尋址

內(nèi)存通常被組織為一個(gè)由M個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組，每個(gè)字節(jié)都有一個(gè)唯一的物理地址（Physical Address PA），作為到數(shù)組的索引。CPU訪問內(nèi)存最簡單直接的方法就是使用物理地址，這種尋址方式被稱為物理尋址。

現(xiàn)代處理器使用的是一種稱為虛擬尋址（Virtual Addressing）的尋址方式。使用虛擬尋址，CPU需要將虛擬地址翻譯成物理地址，這樣才能訪問到真實(shí)的物理內(nèi)存。

虛擬尋址

虛擬尋址需要硬件與操作系統(tǒng)之間互相合作。CPU中含有一個(gè)被稱為內(nèi)存管理單元（Memory Management Unit, MMU）的硬件，它的功能是將虛擬地址轉(zhuǎn)換為物理地址。MMU需要借助存放在內(nèi)存中的頁表來動(dòng)態(tài)翻譯虛擬地址，該頁表由操作系統(tǒng)管理。

頁表

虛擬內(nèi)存空間被組織為一個(gè)存放在硬盤上的M個(gè)連續(xù)的字節(jié)大小的單元組成的數(shù)組，每個(gè)字節(jié)都有一個(gè)唯一的虛擬地址，作為到數(shù)組的索引（這點(diǎn)其實(shí)與物理內(nèi)存是一樣的）。

操作系統(tǒng)通過將虛擬內(nèi)存分割為大小固定的塊來作為硬盤和內(nèi)存之間的傳輸單位，這個(gè)塊被稱為虛擬頁（Virtual Page, VP），每個(gè)虛擬頁的大小為 P=2^p字節(jié)。物理內(nèi)存也會(huì)按照這種方法分割為物理頁（Physical Page, PP），大小也為P字節(jié)。

CPU在獲得虛擬地址之后，需要通過MMU將虛擬地址翻譯為物理地址。而在翻譯的過程中還需要借助頁表，所謂頁表就是一個(gè)存放在物理內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，它記錄了虛擬頁與物理頁的映射關(guān)系。

頁表是一個(gè)元素為頁表?xiàng)l目（Page Table Entry, PTE）的集合，每個(gè)虛擬頁在頁表中一個(gè)固定偏移量的位置上都有一個(gè)PTE 。下面是PTE僅含有一個(gè)有效位標(biāo)記的頁表結(jié)構(gòu)，該有效位代表這個(gè)虛擬頁是否被緩存在物理內(nèi)存中。

虛擬頁VP 0、VP 4、VP 6、VP 7被緩存在物理內(nèi)存中，虛擬頁VP 2和VP 5被分配在頁表中，但并沒有緩存在物理內(nèi)存，虛擬頁VP 1和VP 3還沒有被分配。

在進(jìn)行動(dòng)態(tài)內(nèi)存分配時(shí)，例如malloc()函數(shù)或者其他高級(jí)語言中的new關(guān)鍵字，操作系統(tǒng)會(huì)在硬盤中創(chuàng)建或申請(qǐng)一段虛擬內(nèi)存空間，并更新到頁表（分配一個(gè)PTE，使該P(yáng)TE指向硬盤上這個(gè)新創(chuàng)建的虛擬頁）。

由于CPU每次進(jìn)行地址翻譯的時(shí)候都需要經(jīng)過PTE，所以如果想控制內(nèi)存系統(tǒng)的訪問，可以在PTE上添加一些額外的許可位（例如讀寫權(quán)限、內(nèi)核權(quán)限等） ，這樣只要有指令違反了這些許可條件，CPU就會(huì)觸發(fā)一個(gè)一般保護(hù)故障，將控制權(quán)傳遞給內(nèi)核中的異常處理程序。一般這種異常被稱為“段錯(cuò)誤（Segmentation Fault）”。

頁命中

頁命中

如上圖所示，MMU根據(jù)虛擬地址在頁表中尋址到了PTE 4，該P(yáng)TE的有效位為1，代表該虛擬頁已經(jīng)被緩存在物理內(nèi)存中了，最終MMU得到了PTE中的物理內(nèi)存地址（指向PP 1）。

缺頁

缺頁

如上圖所示，MMU根據(jù)虛擬地址在頁表中尋址到了PTE 2，該P(yáng)TE的有效位為0，代表該虛擬頁并沒有被緩存在物理內(nèi)存中。虛擬頁沒有被緩存在物理內(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é)果是頁命中，并得到物理地址。

這種在硬盤和內(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)存跟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í)間局部性與空間局部性。

多級(jí)頁表

我們目前為止討論的只是單頁表，但在實(shí)際的環(huán)境中虛擬空間地址都是很大的（一個(gè)32位系統(tǒng)的地址空間有2^32 = 4GB，更別說64位系統(tǒng)了）。在這種情況下，使用一個(gè)單頁表明顯是效率低下的。

常用方法是使用層次結(jié)構(gòu)的頁表 。假設(shè)我們的環(huán)境為一個(gè)32位的虛擬地址空間，它有如下形式：

• 虛擬地址空間被分為4KB的頁，每個(gè)PTE都是4字節(jié)。
• 內(nèi)存的前2K個(gè)頁面分配給了代碼和數(shù)據(jù)。
• 之后的6K個(gè)頁面還未被分配。
• 再接下來的1023個(gè)頁面也未分配，其后的1個(gè)頁面分配給了用戶棧。

下圖是為該虛擬地址空間構(gòu)造的二級(jí)頁表層次結(jié)構(gòu)（真實(shí)情況中多為四級(jí)或更多），一級(jí)頁表（1024個(gè)PTE正好覆蓋4GB的虛擬地址空間，同時(shí)每個(gè)PTE只有4字節(jié)，這樣一級(jí)頁表與二級(jí)頁表的大小也正好與一個(gè)頁面的大小一致都為4KB）的每個(gè)PTE負(fù)責(zé)映射虛擬地址空間中一個(gè)4MB的片（chunk），每一片都由1024個(gè)連續(xù)的頁面組成。二級(jí)頁表中的每個(gè)PTE負(fù)責(zé)映射一個(gè)4KB的虛擬內(nèi)存頁面。

這個(gè)結(jié)構(gòu)看起來很像是一個(gè)B-Tree，這種層次結(jié)構(gòu)有效的減緩了內(nèi)存要求：

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

地址翻譯的過程

從形式上來說，地址翻譯是一個(gè)N元素的虛擬地址空間中的元素和一個(gè)M元素的物理地址空間中元素之間的映射。

下圖為MMU利用頁表進(jìn)行尋址的過程：

頁表基址寄存器（PTBR）指向當(dāng)前頁表。一個(gè)n位的虛擬地址包含兩個(gè)部分，一個(gè)p位的虛擬頁面偏移量（Virtual Page Offset, VPO）和一個(gè)（n - p）位的虛擬頁號(hào)（Virtual Page Number, VPN）。

MMU根據(jù)VPN來選擇對(duì)應(yīng)的PTE ，例如VPN 0代表PTE 0、VPN 1代表PTE 1....因?yàn)槲锢眄撆c虛擬頁的大小是一致的，所以物理頁面偏移量（Physical Page Offset, PPO）與VPO是相同的。那么之后 只要將PTE中的物理頁號(hào)（Physical Page Number, PPN）與虛擬地址中的VPO串聯(lián)起來，就能得到相應(yīng)的物理地址 。

多級(jí)頁表的地址翻譯也是如此，只不過因?yàn)橛卸鄠€(gè)層次，所以VPN需要分成多段。假設(shè)有一個(gè)k級(jí)頁表，虛擬地址會(huì)被分割成k個(gè)VPN和1個(gè)VPO，每個(gè) VPN i都是一個(gè)到第i級(jí)頁表的索引 。為了構(gòu)造物理地址，MMU需要訪問k個(gè)PTE才能拿到對(duì)應(yīng)的PPN。

TLB

頁表是被緩存在內(nèi)存中的，盡管內(nèi)存的速度相對(duì)于硬盤來說已經(jīng)非常快了，但與CPU還是有所差距。為了防止每次地址翻譯操作都需要去訪問內(nèi)存，CPU使用了高速緩存與TLB來緩存PTE。

在最糟糕的情況下（不包括缺頁），MMU需要訪問內(nèi)存取得相應(yīng)的PTE，這個(gè)代價(jià)大約為幾十到幾百個(gè)周期，如果PTE湊巧緩存在L1高速緩存中（如果L1沒有還會(huì)從L2中查找，不過我們忽略多級(jí)緩沖區(qū)的細(xì)節(jié)），那么性能開銷就會(huì)下降到1個(gè)或2個(gè)周期。然而，許多系統(tǒng)甚至需要消除即使這樣微小的開銷，TLB由此而生。

TLB（Translation Lookaside Buffer, TLB）被稱為翻譯后備緩沖器或翻譯旁路緩沖器，它是MMU中的一個(gè)緩沖區(qū)，其中每一行都保存著一個(gè)由單個(gè)PTE組成的塊。用于組選擇和行匹配的索引與標(biāo)記字段是從VPN中提取出來的，如果TLB中有****T = 2^t個(gè)組，那么TLB索引（TLBI）是由VPN的t個(gè)最低位組成的，而TLB標(biāo)記（TLBT）是由VPN中剩余的位組成的。

下圖為地址翻譯的流程（TLB命中的情況下）：

• 第一步，CPU將一個(gè)虛擬地址交給MMU進(jìn)行地址翻譯。
• 第二步和第三步，MMU通過TLB取得相應(yīng)的PTE。
• 第四步，MMU通過PTE翻譯出物理地址并將它發(fā)送給高速緩存/內(nèi)存。
• 第五步，高速緩存返回?cái)?shù)據(jù)到CPU（如果緩存命中的話，否則還需要訪問內(nèi)存）。

當(dāng)TLB未命中時(shí)，MMU必須從高速緩存/內(nèi)存中取出相應(yīng)的PTE，并將新取得的PTE存放到TLB（如果TLB已滿會(huì)覆蓋一個(gè)已經(jīng)存在的PTE）。

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

Linux為每個(gè)進(jìn)程維護(hù)了一個(gè)單獨(dú)的虛擬地址空間 。虛擬地址空間分為內(nèi)核空間與用戶空間，用戶空間包括代碼、數(shù)據(jù)、堆、共享庫以及棧，內(nèi)核空間包括內(nèi)核中的代碼和數(shù)據(jù)結(jié)構(gòu)，內(nèi)核空間的某些區(qū)域被映射到所有進(jìn)程共享的物理頁面。

Linux也將一組連續(xù)的虛擬頁面（大小等于內(nèi)存總量）映射到相應(yīng)的一組連續(xù)的物理頁面，這種做法為內(nèi)核提供了一種便利的方法來訪問物理內(nèi)存中任何特定的位置。

Linux將虛擬內(nèi)存組織成一些區(qū)域（也稱為段）的集合，區(qū)域的概念允許虛擬地址空間有間隙。一個(gè)區(qū)域就是已經(jīng)存在著的已分配的虛擬內(nèi)存的連續(xù)片（chunk） 。

例如，代碼段、數(shù)據(jù)段、堆、共享庫段，以及用戶棧都屬于不同的區(qū)域，每個(gè)存在的虛擬頁都保存在某個(gè)區(qū)域中，而不屬于任何區(qū)域的虛擬頁是不存在的，也不能被進(jìn)程所引用。

內(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ù)器等）。

• mm_struct：描述了虛擬內(nèi)存的當(dāng)前狀態(tài)。pgd指向一級(jí)頁表的基址（當(dāng)內(nèi)核運(yùn)行這個(gè)進(jìn)程時(shí)，pgd會(huì)被存放在CR3控制寄存器，也就是頁表基址寄存器中），mmap指向一個(gè)vm_area_structs的鏈表，其中每個(gè)vm_area_structs都描述了當(dāng)前虛擬地址空間的一個(gè)區(qū)域。
• vm_starts：指向這個(gè)區(qū)域的起始處。
• vm_end：指向這個(gè)區(qū)域的結(jié)束處。
• vm_prot：描述這個(gè)區(qū)域內(nèi)包含的所有頁的讀寫許可權(quán)限。
• vm_flags：描述這個(gè)區(qū)域內(nèi)的頁面是與其他進(jìn)程共享的，還是這個(gè)進(jìn)程私有的以及一些其他信息。
• vm_next：指向鏈表的下一個(gè)區(qū)域結(jié)構(gòu)。

內(nèi)存映射

Linux通過將一個(gè)虛擬內(nèi)存區(qū)域與一個(gè)硬盤上的文件關(guān)聯(lián)起來，以初始化這個(gè)虛擬內(nèi)存區(qū)域的內(nèi)容，這個(gè)過程稱為內(nèi)存映射（memory mapping）。

這種將虛擬內(nèi)存系統(tǒng)集成到文件系統(tǒng)的方法可以簡單而高效地把程序和數(shù)據(jù)加載到內(nèi)存中。

一個(gè)區(qū)域可以映射到一個(gè)普通硬盤文件的連續(xù)部分，例如一個(gè)可執(zhí)行目標(biāo)文件。文件區(qū)（section）被分成頁大小的片，每一片包含一個(gè)虛擬頁的初始內(nèi)容。 由于按需頁面調(diào)度的策略，這些虛擬頁面沒有實(shí)際交換進(jìn)入物理內(nèi)存，直到CPU引用的虛擬地址在該區(qū)域的范圍內(nèi) 。如果區(qū)域比文件區(qū)要大，那么就用零來填充這個(gè)區(qū)域的余下部分。

一個(gè)區(qū)域也可以映射到一個(gè)匿名文件，匿名文件是由內(nèi)核創(chuàng)建的，包含的全是二進(jìn)制零 。當(dāng)CPU第一次引用這樣一個(gè)區(qū)域內(nèi)的虛擬頁面時(shí)，內(nèi)核就在物理內(nèi)存中找到一個(gè)合適的犧牲頁面，如果該頁面被修改過，就先將它寫回到硬盤，之后用二進(jìn)制零覆蓋犧牲頁并更新頁表，將這個(gè)頁面標(biāo)記為已緩存在內(nèi)存中的。

簡單來說：普通文件映射就是將一個(gè)文件與一塊內(nèi)存建立起映射關(guān)系，對(duì)該文件進(jìn)行IO操作可以繞過內(nèi)核直接在用戶態(tài)完成（用戶態(tài)在該虛擬地址區(qū)域讀寫就相當(dāng)于讀寫這個(gè)文件）。匿名文件映射一般在用戶空間需要分配一段內(nèi)存來存放數(shù)據(jù)時(shí)，由內(nèi)核創(chuàng)建匿名文件并與內(nèi)存進(jìn)行映射，之后用戶態(tài)就可以通過操作這段虛擬地址來操作內(nèi)存了。匿名文件映射最熟悉的應(yīng)用場景就是動(dòng)態(tài)內(nèi)存分配（malloc()函數(shù)）。

Linux很多地方都采用了“懶加載”機(jī)制，自然也包括內(nèi)存映射。不管是普通文件映射還是匿名映射，Linux只會(huì)先劃分虛擬內(nèi)存地址。只有當(dāng)CPU第一次訪問該區(qū)域內(nèi)的虛擬地址時(shí)，才會(huì)真正的與物理內(nèi)存建立映射關(guān)系。

只要虛擬頁被初始化了，它就在一個(gè)由內(nèi)核維護(hù)的交換文件（swap file）之間換來換去。交換文件又稱為交換空間（swap space）或交換區(qū)域（swap area）。swap區(qū)域不止用于頁交換，在物理內(nèi)存不夠的情況下，還會(huì)將部分內(nèi)存數(shù)據(jù)交換到swap區(qū)域（使用硬盤來擴(kuò)展內(nèi)存）。

共享對(duì)象

虛擬內(nèi)存系統(tǒng)為每個(gè)進(jìn)程提供了私有的虛擬地址空間，這樣可以保證進(jìn)程之間不會(huì)發(fā)生錯(cuò)誤的讀寫。但多個(gè)進(jìn)程之間也含有相同的部分，例如每個(gè)C程序都使用到了C標(biāo)準(zhǔn)庫，如果每個(gè)進(jìn)程都在物理內(nèi)存中保持這些代碼的副本，那會(huì)造成很大的內(nèi)存資源浪費(fèi)。

內(nèi)存映射提供了共享對(duì)象的機(jī)制，來避免內(nèi)存資源的浪費(fèi)。一個(gè)對(duì)象被映射到虛擬內(nèi)存的一個(gè)區(qū)域，要么是作為共享對(duì)象，要么是作為私有對(duì)象的。

如果一個(gè)進(jìn)程將一個(gè)共享對(duì)象映射到它的虛擬地址空間的一個(gè)區(qū)域內(nèi)，那么這個(gè)進(jìn)程對(duì)這個(gè)區(qū)域的任何寫操作，對(duì)于那些也把這個(gè)共享對(duì)象映射到它們虛擬內(nèi)存的其他進(jìn)程而言，也是可見的。相對(duì)的，對(duì)一個(gè)映射到私有對(duì)象的區(qū)域的任何寫操作，對(duì)于其他進(jìn)程來說是不可見的。一個(gè)映射到共享對(duì)象的虛擬內(nèi)存區(qū)域叫做共享區(qū)域，類似的，也有私有區(qū)域。

為了節(jié)約內(nèi)存，私有對(duì)象開始的生命周期與共享對(duì)象基本上是一致的（在物理內(nèi)存中只保存私有對(duì)象的一份副本），并使用寫時(shí)復(fù)制的技術(shù)來應(yīng)對(duì)多個(gè)進(jìn)程的寫沖突。

只要沒有進(jìn)程試圖寫它自己的私有區(qū)域，那么多個(gè)進(jìn)程就可以繼續(xù)共享物理內(nèi)存中私有對(duì)象的一個(gè)單獨(dú)副本。然而，只要有一個(gè)進(jìn)程試圖對(duì)私有區(qū)域的某一頁面進(jìn)行寫操作，就會(huì)觸發(fā)一個(gè)保護(hù)異常。

在上圖中，進(jìn)程B試圖對(duì)私有區(qū)域的一個(gè)頁面進(jìn)行寫操作，該操作觸發(fā)了保護(hù)異常。異常處理程序會(huì)在物理內(nèi)存中創(chuàng)建這個(gè)頁面的一個(gè)新副本，并更新PTE指向這個(gè)新的副本，然后恢復(fù)這個(gè)頁的可寫權(quán)限。

還有一個(gè)典型的例子就是fork()函數(shù)，該函數(shù)用于創(chuàng)建子進(jìn)程。當(dāng)fork()函數(shù)被當(dāng)前進(jìn)程調(diào)用時(shí)，內(nèi)核會(huì)為新進(jìn)程創(chuàng)建各種必要的數(shù)據(jù)結(jié)構(gòu)，并分配給它一個(gè)唯一的PID。

為了給新進(jìn)程創(chuàng)建虛擬內(nèi)存，它復(fù)制了當(dāng)前進(jìn)程的mm_struct、vm_area_struct和頁表的原樣副本。并將兩個(gè)進(jìn)程的每個(gè)頁面都標(biāo)為只讀，兩個(gè)進(jìn)程中的每個(gè)區(qū)域都標(biāo)記為私有區(qū)域（寫時(shí)復(fù)制）。

這樣，父進(jìn)程和子進(jìn)程的虛擬內(nèi)存空間完全一致，只有當(dāng)這兩個(gè)進(jìn)程中的任一個(gè)進(jìn)行寫操作時(shí)，再使用寫時(shí)復(fù)制來保證每個(gè)進(jìn)程的虛擬地址空間私有的抽象概念。

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

雖然可以使用內(nèi)存映射（mmap()函數(shù)）來創(chuàng)建和刪除虛擬內(nèi)存區(qū)域來滿足運(yùn)行時(shí)動(dòng)態(tài)內(nèi)存分配的問題。然而，為了更好的移植性與便利性，還需要一個(gè)更高層面的抽象，也就是動(dòng)態(tài)內(nèi)存分配器（dynamic memory allocator）。

動(dòng)態(tài)內(nèi)存分配器維護(hù)著一個(gè)進(jìn)程的虛擬內(nèi)存區(qū)域，也就是我們所熟悉的“堆（heap）”，內(nèi)核中還維護(hù)著一個(gè)指向堆頂?shù)闹羔榖rk（break）。動(dòng)態(tài)內(nèi)存分配器將堆視為一個(gè)連續(xù)的虛擬內(nèi)存塊（chunk）的集合，每個(gè)塊有兩種狀態(tài)，已分配和空閑。已分配的塊顯式地保留為供應(yīng)用程序使用，空閑塊則可以用來進(jìn)行分配，它的空閑狀態(tài)直到它顯式地被應(yīng)用程序分配為止。已分配的塊要么被應(yīng)用程序顯式釋放，要么被垃圾回收器所釋放。

本文只講解動(dòng)態(tài)內(nèi)存分配的一些概念，關(guān)于動(dòng)態(tài)內(nèi)存分配器的實(shí)現(xiàn)已經(jīng)超出了本文的討論范圍。如果有對(duì)它感興趣的同學(xué)，可以去參考dlmalloc ^[1]^ 的源碼，它是由Doug Lea（就是寫Java并發(fā)包的那位）實(shí)現(xiàn)的一個(gè)設(shè)計(jì)巧妙的內(nèi)存分配器，而且源碼中的注釋十分多。

內(nèi)存碎片

造成堆的空間利用率很低的主要原因是一種被稱為碎片（fragmentation）的現(xiàn)象，當(dāng)雖然有未使用的內(nèi)存但這塊內(nèi)存并不能滿足分配請(qǐng)求時(shí)，就會(huì)產(chǎn)生碎片 。有以下兩種形式的碎片：

• 內(nèi)部碎片：在一個(gè)已分配塊比有效載荷大時(shí)發(fā)生。例如，程序請(qǐng)求一個(gè)5字（這里我們不糾結(jié)字的大小，假設(shè)一個(gè)字為4字節(jié)，堆的大小為16字并且要保證邊界雙字對(duì)齊）的塊，內(nèi)存分配器為了保證空閑塊是雙字邊界對(duì)齊的（具體實(shí)現(xiàn)中對(duì)齊的規(guī)定可能略有不同，但對(duì)齊是肯定會(huì)有的），只好分配一個(gè)6字的塊。在本例中，已分配塊為6字，有效載荷為5字，內(nèi)部碎片為已分配塊減去有效載荷，為1字。
• 外部碎片：當(dāng)空閑內(nèi)存合計(jì)起來足夠滿足一個(gè)分配請(qǐng)求，但是沒有一個(gè)單獨(dú)的空閑塊足夠大到可以來處理這個(gè)請(qǐng)求時(shí)發(fā)生。外部碎片難以量化且不可預(yù)測，所以分配器通常采用啟發(fā)式策略來試圖維持少量的大空閑塊，而不是維持大量的小空閑塊。分配器也會(huì)根據(jù)策略與分配請(qǐng)求的匹配來分割空閑塊與合并空閑塊（必須相鄰）。

空閑鏈表

分配器將堆組織為一個(gè)連續(xù)的已分配塊和空閑塊的序列，該序列被稱為空閑鏈表 。空閑鏈表分為隱式空閑鏈表與顯式空閑鏈表。

• 隱式空閑鏈表，是一個(gè)單向鏈表，并且每個(gè)空閑塊僅僅是通過頭部中的大小字段隱含地連接著的。
• 顯式空閑鏈表，即是將空閑塊組織為某種形式的顯式數(shù)據(jù)結(jié)構(gòu)（為了更加高效地合并與分割空閑塊）。例如，將堆組織為一個(gè)雙向空閑鏈表，在每個(gè)空閑塊中，都包含一個(gè)前驅(qū)節(jié)點(diǎn)的指針與后繼節(jié)點(diǎn)的指針。

查找一個(gè)空閑塊一般有如下幾種策略：

• 首次適配：從頭開始搜索空閑鏈表，選擇第一個(gè)遇見的合適的空閑塊。它的優(yōu)點(diǎn)在于趨向于將大的空閑塊保留在鏈表的后面，缺點(diǎn)是它趨向于在靠近鏈表前部處留下碎片。
• 下一次適配：每次從上一次查詢結(jié)束的地方開始進(jìn)行搜索，直到遇見合適的空閑塊。這種策略通常比首次適配效率高，但是內(nèi)存利用率則要低得多了。
• 最佳適配：檢查每個(gè)空閑塊，選擇適合所需請(qǐng)求大小的最小空閑塊。最佳適配的內(nèi)存利用率是三種策略中最高的，但它需要對(duì)堆進(jìn)行徹底的搜索。

對(duì)一個(gè)鏈表進(jìn)行查找操作的效率是線性的，為了減少分配請(qǐng)求對(duì)空閑塊匹配的時(shí)間，分配器通常采用分離存儲(chǔ)（segregated storage）的策略，即是維護(hù)多個(gè)空閑鏈表，其中每個(gè)鏈表的塊有大致相等的大小。

一種簡單的分離存儲(chǔ)策略：分配器維護(hù)一個(gè)空閑鏈表數(shù)組，然后將所有可能的塊分成一些等價(jià)類（也叫做大小類（size class）），每個(gè)大小類代表一個(gè)空閑鏈表，并且每個(gè)大小類的空閑鏈表包含大小相等的塊，每個(gè)塊的大小就是這個(gè)大小類中最大元素的大小（例如，某個(gè)大小類的范圍定義為（17~32），那么這個(gè)空閑鏈表全由大小為32的塊組成）。

當(dāng)有一個(gè)分配請(qǐng)求時(shí)，我們檢查相應(yīng)的空閑鏈表。如果鏈表非空，那么就分配其中第一塊的全部。如果鏈表為空，分配器就向操作系統(tǒng)請(qǐng)求一個(gè)固定大小的額外內(nèi)存片，將這個(gè)片分成大小相等的塊，然后將這些塊鏈接起來形成新的空閑鏈表。

要釋放一個(gè)塊，分配器只需要簡單地將這個(gè)塊插入到相應(yīng)的空閑鏈表的頭部。

垃圾回收

在編寫C程序時(shí)，一般只能顯式地分配與釋放堆中的內(nèi)存（malloc()與free()），程序員不僅需要分配內(nèi)存，還需要負(fù)責(zé)內(nèi)存的釋放。

許多現(xiàn)代編程語言都內(nèi)置了自動(dòng)內(nèi)存管理機(jī)制（通過引入自動(dòng)內(nèi)存管理庫也可以讓C/C++實(shí)現(xiàn)自動(dòng)內(nèi)存管理），所謂自動(dòng)內(nèi)存管理，就是自動(dòng)判斷不再需要的堆內(nèi)存（被稱為垃圾內(nèi)存），然后自動(dòng)釋放這些垃圾內(nèi)存。

自動(dòng)內(nèi)存管理的實(shí)現(xiàn)是垃圾收集器（garbage collector），它是一種動(dòng)態(tài)內(nèi)存分配器，它會(huì)自動(dòng)釋放應(yīng)用程序不再需要的已分配塊。

垃圾收集器一般采用以下兩種（之一）的策略來判斷一塊堆內(nèi)存是否為垃圾內(nèi)存：

• 引用計(jì)數(shù)器：在數(shù)據(jù)的物理空間中添加一個(gè)計(jì)數(shù)器，當(dāng)有其他數(shù)據(jù)與其相關(guān)時(shí)（引用），該計(jì)數(shù)器加一，反之則減一。通過定期檢查計(jì)數(shù)器的值，只要為0則認(rèn)為是垃圾內(nèi)存，可以釋放它所占用的已分配塊。使用引用計(jì)數(shù)器，實(shí)現(xiàn)簡單直接，但缺點(diǎn)也很明顯，它無法回收循環(huán)引用的兩個(gè)對(duì)象（假設(shè)有對(duì)象A與對(duì)象B，它們2個(gè)互相引用，但實(shí)際上對(duì)象A與對(duì)象B都已經(jīng)是沒用的對(duì)象了）。
• 可達(dá)性分析：垃圾收集器將堆內(nèi)存視為一張有向圖，然后選出一組根節(jié)點(diǎn)（例如，在Java中一般為類加載器、全局變量、運(yùn)行時(shí)常量池中的引用類型變量等），根節(jié)點(diǎn)必須是足夠“活躍“的對(duì)象。然后計(jì)算從根節(jié)點(diǎn)集合出發(fā)的可達(dá)路徑，只要從根節(jié)點(diǎn)出發(fā)不可達(dá)的節(jié)點(diǎn)，都視為垃圾內(nèi)存。

垃圾收集器進(jìn)行回收的算法有如下幾種：

• 標(biāo)記-清除：該算法分為標(biāo)記（mark）和清除（sweep）兩個(gè)階段。首先標(biāo)記出所有需要回收的對(duì)象，然后在標(biāo)記完成后統(tǒng)一回收所有被標(biāo)記的對(duì)象。標(biāo)記-清除算法實(shí)現(xiàn)簡單，但它的效率不高，而且會(huì)產(chǎn)生許多內(nèi)存碎片。
• 標(biāo)記-整理：標(biāo)記-整理與標(biāo)記-清除算法基本一致，只不過后續(xù)步驟不是直接對(duì)可回收對(duì)象進(jìn)行清理，而是讓所有存活的對(duì)象都向一端移動(dòng)，然后直接清理掉邊界以外的內(nèi)存。
• 復(fù)制： 將程序所擁有的內(nèi)存空間劃分為大小相等的兩塊，每次都只使用其中的一塊。當(dāng)這一塊的內(nèi)存用完了，就把還存活著的對(duì)象復(fù)制到另一塊內(nèi)存上，然后將已使用過的內(nèi)存空間進(jìn)行清理 。這種方法不必考慮內(nèi)存碎片問題，但內(nèi)存利用率很低。這個(gè)比例不是絕對(duì)的，像HotSpot虛擬機(jī)為了避免浪費(fèi)，將內(nèi)存劃分為Eden空間與兩個(gè)Survivor空間，每次都只使用Eden和其中一個(gè)Survivor。當(dāng)回收時(shí)，將Eden和Survivor中還存活著的對(duì)象一次性地復(fù)制到另外一個(gè)Survivor空間上，然后清理掉Eden和剛才使用過的Survivor空間。HotSpot虛擬機(jī)默認(rèn)的Eden和Survivor的大小比例為8：1，只有10%的內(nèi)存空間會(huì)被閑置浪費(fèi)。
• 分代： 分代算法根據(jù)對(duì)象的存活周期的不同將內(nèi)存劃分為多塊，這樣就可以對(duì)不同的年代采用不同的回收算法 。一般分為新生代與老年代，新生代存放的是存活率較低的對(duì)象，可以采用復(fù)制算法；老年代存放的是存活率較高的對(duì)象，如果使用復(fù)制算法，那么內(nèi)存空間會(huì)不夠用，所以必須使用標(biāo)記-清除或標(biāo)記-整理算法。

總結(jié)

虛擬內(nèi)存是對(duì)內(nèi)存的一個(gè)抽象。支持虛擬內(nèi)存的CPU需要通過虛擬尋址的方式來引用內(nèi)存中的數(shù)據(jù)。

CPU加載一個(gè)虛擬地址，然后發(fā)送給MMU進(jìn)行地址翻譯。地址翻譯需要硬件與操作系統(tǒng)之間緊密合作，MMU借助頁表來獲得物理地址。

• 首先，MMU先將虛擬地址發(fā)送給TLB以獲得PTE（根據(jù)VPN尋址）。
• 如果恰好TLB中緩存了該P(yáng)TE，那么就返回給MMU，否則MMU需要從高速緩存/內(nèi)存中獲得PTE，然后更新緩存到TLB。
• MMU獲得了PTE，就可以從PTE中獲得對(duì)應(yīng)的PPN，然后結(jié)合VPO構(gòu)造出物理地址。
• 如果在PTE中發(fā)現(xiàn)該虛擬頁沒有緩存在內(nèi)存，那么會(huì)觸發(fā)一個(gè)缺頁異常。缺頁異常處理程序會(huì)把虛擬頁緩存進(jìn)物理內(nèi)存，并更新PTE。異常處理程序返回后，CPU會(huì)重新加載這個(gè)虛擬地址，并進(jìn)行翻譯。

虛擬內(nèi)存系統(tǒng)簡化了內(nèi)存管理、鏈接、加載、代碼和數(shù)據(jù)的共享以及訪問權(quán)限的保護(hù)：

• 簡化鏈接，獨(dú)立的地址空間允許每個(gè)進(jìn)程的內(nèi)存映像使用相同的基本格式，而不管代碼和數(shù)據(jù)實(shí)際存放在物理內(nèi)存的何處。
• 簡化加載，虛擬內(nèi)存使向內(nèi)存中加載可執(zhí)行文件和共享對(duì)象文件變得更加容易。
• 簡化共享，獨(dú)立的地址空間為操作系統(tǒng)提供了一個(gè)管理用戶進(jìn)程和內(nèi)核之間共享的一致機(jī)制。
• 訪問權(quán)限保護(hù)，每個(gè)虛擬地址都要經(jīng)過查詢PTE的過程，在PTE中設(shè)定訪問權(quán)限的標(biāo)記位從而簡化內(nèi)存的權(quán)限保護(hù)。

操作系統(tǒng)通過將虛擬內(nèi)存與文件系統(tǒng)結(jié)合的方式，來初始化虛擬內(nèi)存區(qū)域，這個(gè)過程稱為內(nèi)存映射。應(yīng)用程序顯式分配內(nèi)存的區(qū)域叫做堆，通過動(dòng)態(tài)內(nèi)存分配器來直接操作堆內(nèi)存。