【操作系統(tǒng)】內(nèi)存管理概述

內(nèi)存管理硬件結(jié)構(gòu)

常見的內(nèi)存分配函數(shù)有malloc，mmap等，但大家有沒有想過，這些函數(shù)在內(nèi)核中是怎么實(shí)現(xiàn)的？換句話說，Linux內(nèi)核的內(nèi)存管理是怎么實(shí)現(xiàn)的？

內(nèi)存管理的目的是管理系統(tǒng)中的內(nèi)存，俗稱內(nèi)存橋，換成專業(yè)屬于叫DDR。我們有必要先了解下計(jì)算機(jī)對內(nèi)存管理的硬件結(jié)構(gòu)。我們先看下關(guān)于地址的一些概念。

早期內(nèi)存的使用方法

在計(jì)算機(jī)早期的發(fā)展階段，要運(yùn)行一個(gè)程序，要把計(jì)算機(jī)程序，全部裝載在內(nèi)存中，程序訪問的內(nèi)存地址就是實(shí)際的物理地址。所以，當(dāng)運(yùn)行多個(gè)程序時(shí)，必須保證運(yùn)行程序的使用的總的內(nèi)存量要小于總的內(nèi)存大小。那這種方式存在什么問題呢？

一個(gè)問題是進(jìn)程地址空間不合理，任意的進(jìn)程可以隨意修改其他進(jìn)程的地址數(shù)據(jù)；二是內(nèi)存使用效率很低，內(nèi)存緊張時(shí)需要把整個(gè)進(jìn)程交換到交換分區(qū)中，導(dǎo)致程序的使用效率很低。

分段

為了解決這兩個(gè)問題，當(dāng)時(shí)的人們提出了分段的機(jī)制。它的核心思想是建立一個(gè) 虛擬地址空間，將一個(gè)程序分成代碼段，數(shù)據(jù)段，堆棧段什么的，每個(gè)段各自管理不同的數(shù)據(jù)。在虛擬地址空間和物理地址空間之間做映射，實(shí)現(xiàn)進(jìn)程的隔離。

分頁

在分段機(jī)制中，程序也是全部裝載在內(nèi)存中的，效率也很低。這個(gè)時(shí)候就提出了分頁機(jī)制：分頁這個(gè)技術(shù)仍然是一種虛擬地址空間到物理地址空間映射的機(jī)制。但是，粒度更加的小了。單位不是整個(gè)程序，而是某個(gè)“頁”，一段虛擬地址空間組成的某一頁映射到一段物理地址空間組成的某一頁。

程序在運(yùn)行的時(shí)候，需要哪個(gè)頁面，我再把相關(guān)頁面交換進(jìn)來。經(jīng)常不用的頁面會(huì)交換到swap分區(qū)。分頁機(jī)制也是按需分配，這是操作系統(tǒng)的核心思想。

邏輯地址，線性地址（intel架構(gòu)）

邏輯地址和線性地址是intel架構(gòu)的概念，邏輯地址是程序產(chǎn)生的和段相關(guān)的那個(gè)部分，線性地址是邏輯地址轉(zhuǎn)換為物理地址的一個(gè)中間層。

在分段的方式中，邏輯地址是段的偏移地址，再加上基地址就是線性地址了。如果是做arm架構(gòu)的，可以不用關(guān)注這部分。

虛擬地址

簡單的說就是可以尋址的一片空間。如果這個(gè)空間是虛擬的，我們就叫做虛擬地址空間；如果這個(gè)空間是真實(shí)存在的，我們就叫做物理地址空間。虛擬地址空間是可以任意的大的，因?yàn)槭翘摂M的。而物理地址空間是真實(shí)存在的，所以是有限的

物理地址

物理地址是CPU通過外部總線直接訪問的外部內(nèi)存地址。如果系統(tǒng)啟動(dòng)了分頁機(jī)制，系統(tǒng)啟動(dòng)后必須通過查頁表的方式去獲取物理地址。

如果沒有啟動(dòng)分頁機(jī)制，系統(tǒng)啟動(dòng)后就通過直接變?yōu)榱宋锢淼刂贰?/p>

結(jié)構(gòu)圖

在啟動(dòng)MMU后，CPU訪問的是虛擬地址，虛擬地址經(jīng)過MMU后轉(zhuǎn)換為物理地址，這種轉(zhuǎn)換通過查詢存儲(chǔ)在主存儲(chǔ)器的頁表完成。頻繁訪問主存儲(chǔ)器比較耗時(shí)，因此引入了TLB的概念。

TLB緩存了上一次虛擬地址到物理地址的轉(zhuǎn)換，TLB不存儲(chǔ)具體的數(shù)據(jù)，存儲(chǔ)的是頁表的表項(xiàng)。如果能在TLB中找到本次訪問的頁表項(xiàng)，就不需要再訪問主存了。我們把這個(gè)過程叫做TLB命中。如果沒有找到頁表項(xiàng)，這個(gè)時(shí)候只能去查詢頁表，我們叫做TLB Miss。如何查詢頁表的后面我們會(huì)詳細(xì)介紹。

假設(shè)，現(xiàn)在虛擬地址已經(jīng)轉(zhuǎn)換為了物理地址。這個(gè)時(shí)候就會(huì)去找一級(jí)緩存?？匆患?jí)緩存有沒有需要的數(shù)據(jù)。我們這里采用的是物理索引（PI），物理標(biāo)簽（PT）的方式?，F(xiàn)在的大部分cache都采用組相聯(lián)的方式，訪問cache地址會(huì)被分為偏移域，索引域，標(biāo)記域三部分。如果一級(jí)緩存沒有相應(yīng)的數(shù)據(jù)，就要訪問二級(jí)緩存了，如果二級(jí)緩存沒有數(shù)據(jù)，就要訪問主存儲(chǔ)器了。

還有一種情況，當(dāng)系統(tǒng)物理內(nèi)存短缺的時(shí)候，Linux內(nèi)核中，有頁面回收的機(jī)制，會(huì)把不常用的頁面交換到swap分區(qū)中，這個(gè)動(dòng)作叫做swap。這張圖就從硬件結(jié)構(gòu)的角度解釋了內(nèi)存管理的基本構(gòu)成。

虛擬地址到物理地址的轉(zhuǎn)換

虛擬地址的32個(gè)bit位可以分為3個(gè)域，最高12bit位20~31位稱為L1索引，叫做PGD，頁面目錄。中間的8個(gè)bit位叫做L2索引，在Linux內(nèi)核中叫做PT，頁表。最低的12位叫做頁索引。

在ARM處理器中，TTBRx寄存器存放著頁表基地址，我們這里的一級(jí)頁表有4096個(gè)頁表項(xiàng)。每個(gè)表項(xiàng)中存放著二級(jí)表項(xiàng)的基地址。我們可以通過虛擬地址的L1索引訪問一級(jí)頁表，訪問一級(jí)頁表相當(dāng)于數(shù)組訪問。

二級(jí)頁表通常是動(dòng)態(tài)分配的，可以通過虛擬地址的中間8bit位L2索引訪問二級(jí)頁表，在L2索引中存放著最終物理地址的高20bit位，然后和虛擬地址的低12bit位就組成了最終的物理地址。以上就是虛擬地址轉(zhuǎn)換為物理地址的過程。

MMU訪問頁表是硬件實(shí)現(xiàn)的，但頁表的創(chuàng)建和填充需要Linux內(nèi)核來填充。通常，一級(jí)頁表和二級(jí)頁表存放在主存儲(chǔ)器中。

內(nèi)存管理總覽

系統(tǒng)調(diào)用

Linux內(nèi)核把用戶空間分為兩部分：用戶空間和內(nèi)核空間。用戶進(jìn)程運(yùn)行在用戶空間，如果需要內(nèi)存的話通過C庫提供的malloc，mmap，mlock，madvice，mremap函數(shù)。C庫的這些函數(shù)最終都會(huì)調(diào)用到內(nèi)核的sys_xxx接口分配內(nèi)存空間。如malloc函數(shù)是依賴內(nèi)核的sys_brk接口分配內(nèi)存空間的。mmap對應(yīng)接口為sys_mmap。

我們以malloc函數(shù)為例，假設(shè)現(xiàn)在用戶態(tài)的內(nèi)存短缺，就會(huì)通過sys_brk調(diào)用去堆上分配內(nèi)存。在用戶空間分配的是虛擬內(nèi)存，因此，在堆上分配的也是虛擬內(nèi)存。

vm_area_struct

Linux內(nèi)核把這些地址稱為進(jìn)程地址空間。內(nèi)核使用struct vm_area_struct 來管理這些進(jìn)程地址空間。VMA主要管理內(nèi)存的創(chuàng)建，插入，刪除，合并等操作。

由于每個(gè)不同質(zhì)的虛擬內(nèi)存區(qū)域功能和內(nèi)部機(jī)制都不同，因此一個(gè)進(jìn)程使用多個(gè)vm_area_struct結(jié)構(gòu)來分別表示不同類型的虛擬內(nèi)存區(qū)域。各個(gè)vm_area_struct結(jié)構(gòu)使用鏈表或者樹形結(jié)構(gòu)鏈接，方便進(jìn)程快速訪問，如下圖所示：

vm_area_struct結(jié)構(gòu)中包含區(qū)域起始和終止地址以及其他相關(guān)信息，同時(shí)也包含一個(gè)vm_ops指針，其內(nèi)部可引出所有針對這個(gè)區(qū)域可以使用的系統(tǒng)調(diào)用函數(shù)。這樣，進(jìn)程對某一虛擬內(nèi)存區(qū)域的任何操作需要用要的信息，都可以從vm_area_struct中獲得。mmap函數(shù)就是要?jiǎng)?chuàng)建一個(gè)新的vm_area_struct結(jié)構(gòu)，并將其與文件的物理磁盤地址相連。

缺頁中斷

缺頁中斷是實(shí)現(xiàn)了按需分配的思想。站在用戶角度，缺頁中斷后可分配的頁面有匿名頁面和page cache。匿名頁面指的是沒有關(guān)聯(lián)任何文件的頁面，比如進(jìn)程通過mlock從堆上分配的內(nèi)存。page cache是關(guān)聯(lián)了具體緩存的頁面。比如在看視頻時(shí)的緩存就是page cache。匿名頁面和page cache的產(chǎn)生需要頁面分配器完成。

伙伴系統(tǒng)

頁面分配器是以頁框?yàn)閱挝坏?。典型的頁面分配器就是伙伴系統(tǒng)。伙伴系統(tǒng)是一個(gè)結(jié)合了2的方冪個(gè)分配器和空閑緩沖區(qū)合并計(jì)技術(shù)的內(nèi)存分配方案, 其基本思想很簡單。

內(nèi)存被分成含有很多頁面的大塊, 每一塊都是2個(gè)頁面大小的方冪。如果找不到想要的塊, 一個(gè)大塊會(huì)被分成兩部分, 這兩部分彼此就成為伙伴。其中一半被用來分配，而另一半則空閑。這些塊在以后分配的過程中會(huì)繼續(xù)被二分直至產(chǎn)生一個(gè)所需大小的塊。當(dāng)一個(gè)塊被最終釋放時(shí)， 其伙伴將被檢測出來，如果伙伴也空閑則合并兩者。

雖然伙伴算法實(shí)現(xiàn)不復(fù)雜，但頁面分配器是內(nèi)核實(shí)現(xiàn)最復(fù)雜的系統(tǒng)之一。如果內(nèi)存充足時(shí)，你需要多少內(nèi)存，頁面分配器會(huì)給你分配多少。但如果內(nèi)存緊張時(shí)，頁面分配器會(huì)做很多嘗試，比如開啟異步模式的頁面回收，memory compaction（內(nèi)存規(guī)整）。如果經(jīng)過嘗試后內(nèi)存仍然不夠，這個(gè)時(shí)候會(huì)拿出重型武器oom kill會(huì)殺死一些進(jìn)程。

slab分配器

剛剛我們講的都是以頁為單位分配的內(nèi)存。但有時(shí)候我們需要幾個(gè)字節(jié)的內(nèi)存怎么辦。這個(gè)時(shí)候就需要slab分配器。slab可以管理特定大小的內(nèi)存，對于固定大小的內(nèi)存就不需要VMA去管理了。頁面分配器是中央財(cái)政，slab是地方財(cái)政。如果地方需要種棵樹就不要?jiǎng)跓┲醒胴?cái)政了。

頁面回收

頁面回收實(shí)現(xiàn)了頁面換出的理念。當(dāng)系統(tǒng)內(nèi)存短缺的時(shí)候，系統(tǒng)需要換出一部分內(nèi)存。這部分內(nèi)存通常是page cache 或者匿名頁面。內(nèi)核里面有個(gè)swap守護(hù)線程，當(dāng)系統(tǒng)內(nèi)存低于某個(gè)水位時(shí)，會(huì)被喚醒去掃描LRU（最近最少使用）鏈表，一般匿名頁面和page cache會(huì)添加到鏈表中。實(shí)際上，在內(nèi)核中又將LRU鏈表做了細(xì)分，又細(xì)分為活躍鏈表，不活躍鏈表，匿名頁面鏈表，page cache鏈表。

內(nèi)核相對比較喜歡回收page cache，干凈的page cache 直接合并就好了。對于臟的page cache需要寫回磁盤的一個(gè)動(dòng)作。對于匿名頁面是不能直接合并的，匿名頁面一般都是進(jìn)程的私有數(shù)據(jù)。一般這些匿名頁面數(shù)據(jù)需要回收時(shí)會(huì)swap out 到swap分區(qū)騰出空間，當(dāng)這些進(jìn)程再次需要這些數(shù)據(jù)時(shí)，才會(huì)從swap分區(qū)swap in。頁面回收我們會(huì)在后面詳細(xì)講解。

如果分配好了頁面，這個(gè)時(shí)候就要涉及到頁表的管理了。頁表分為內(nèi)核頁表和進(jìn)程頁表。內(nèi)核提供了很多和內(nèi)核頁表相關(guān)的函數(shù)，后續(xù)我們再分析。

再往下分析就是硬件層，比如MMU，TLB，cache，物理內(nèi)存等，對于這部分我們不做深入分析。

反向映射

當(dāng)進(jìn)程分配內(nèi)存并發(fā)生寫操作時(shí)，會(huì)分配虛擬地址并產(chǎn)生缺頁,進(jìn)而分配物理內(nèi)存并建立虛擬地址到物理地址的映射關(guān)系， 這個(gè)叫正向映射。

反過來， 通過物理頁面找到映射它的所有虛擬頁面叫反向映射（reverse-mapping, RMAP），它可以從page數(shù)據(jù)結(jié)構(gòu)中找到映射這個(gè)page的虛擬地址空間，也就是我們講過的VMA這個(gè)東西，ramp系統(tǒng)是為頁面回收服務(wù)的，如果要回收一個(gè)匿名頁面或者page cache的時(shí)候， 需要把映射這個(gè)頁面的用戶PTE斷開映射關(guān)系才可以去回收。

KSM

KSM，Kernel Samepage Merging，最早是用來優(yōu)化KVM虛擬機(jī)來發(fā)明的一種機(jī)制?，F(xiàn)在用來合并內(nèi)容相同的匿名頁面。

huge page

huge page，通常用來分配2M或者1G大小的頁，目前在服務(wù)器系統(tǒng)中用的比較多。使用huge page可以減少TLB miss的次數(shù)，假如現(xiàn)在需要2M的頁面，一個(gè)page是4K，最壞的情況下需要TLB miss 5次，如果使用2M的頁面，只需要TLB miss 1次。每次TLB miss 對系統(tǒng)的損耗很大。

頁遷移

頁遷移，內(nèi)核中有些頁面是可以遷移的，比如匿名頁面。頁遷移在內(nèi)核很多模塊都被廣泛使用，比如memory compaction（內(nèi)存規(guī)整）。

內(nèi)存規(guī)整

memory compaction，內(nèi)存規(guī)整模塊是為了緩解內(nèi)存碎片化的，系統(tǒng)運(yùn)行的時(shí)間越長，就越容易產(chǎn)生內(nèi)存碎片，系統(tǒng)此時(shí)想分配連續(xù)的大塊內(nèi)存就變得越來越難。

大塊連續(xù)的內(nèi)存一般是內(nèi)核所請求的，因?yàn)閷τ谟脩艨臻g來講，大塊缺頁內(nèi)存都是通過缺頁中斷一塊一塊來分配的。

內(nèi)存規(guī)整的實(shí)現(xiàn)原理也不復(fù)雜，在一個(gè)zoom中有兩個(gè)掃描器，分別從頭到尾和從尾到頭掃描，一個(gè)去查找zoom中有那些頁面可以遷移的，另外一個(gè)去掃描有那些空閑的頁，兩個(gè)掃描器在zoom中相遇的時(shí)候，掃描就停止了。這個(gè)時(shí)候內(nèi)存規(guī)整模塊就知道zoom中有那些頁面可以遷移到空閑頁面。經(jīng)過這么一折騰，就可以騰出一個(gè)大的連續(xù)的物理空間了。

OOM

在經(jīng)過內(nèi)存規(guī)整，頁面遷移等操作后，如果系統(tǒng)還不能分配出系統(tǒng)需要的頁面，Linux就要使用最后一招了，殺敵一千，自損八百，OOM killer會(huì)找一些占用內(nèi)存比較多的進(jìn)程殺掉來釋放內(nèi)存。

之所以會(huì)發(fā)生這種情況，是因?yàn)長inux內(nèi)核在給某個(gè)進(jìn)程分配內(nèi)存時(shí)，會(huì)比進(jìn)程申請的內(nèi)存多分配一些。這是為了保證進(jìn)程在真正使用的時(shí)候有足夠的內(nèi)存，因?yàn)檫M(jìn)程在申請內(nèi)存后并不一定立即使用，當(dāng)真正使用的時(shí)候，可能部分內(nèi)存已經(jīng)被回收了。

比如 當(dāng)一個(gè)進(jìn)程申請2G內(nèi)存時(shí)，內(nèi)核可能會(huì)分配2.5G的內(nèi)存給它.通常這不會(huì)導(dǎo)致什么問題。然而一旦系統(tǒng)內(nèi)大量的進(jìn)程在使用內(nèi)存時(shí)，就會(huì)出現(xiàn)內(nèi)存供不應(yīng)求，很快就會(huì)導(dǎo)致內(nèi)存耗盡。這時(shí)就會(huì)觸發(fā)這個(gè)oom killer，它會(huì)選擇性的殺掉某個(gè)進(jìn)程以保證系統(tǒng)能夠正常運(yùn)行。

內(nèi)存管理的一些數(shù)據(jù)結(jié)構(gòu)

線性映射

我們以32位系統(tǒng)為例，我們知道進(jìn)程最大的地址訪問空間是4G，0~3GB是用戶空間，3 ~ 4GB是內(nèi)核空間。

如果物理空間是大于1GB，內(nèi)核空間如何訪問大于1GB的空間呢？站在內(nèi)核的角度，低地址段是線性映射，高地址段是高端映射。

那線性映射和高端映射是如何劃分的呢？不同的體系結(jié)構(gòu)有不同的劃分方法。在ARM32中是線性映射大小為760M。線性映射就是直接把物理地址空間映射到3G ~ 4G的地址空間，這段映射關(guān)系就變得比較簡單了，內(nèi)核訪問時(shí)直接使用虛擬地址減去偏移量（page offset）就得到物理地址了。

如果要訪問高端內(nèi)存就麻煩一點(diǎn)，1G的物理內(nèi)存空間有限，不能把所有地址都映射到線性地址空間。如果要訪問高端內(nèi)存就要通過動(dòng)態(tài)映射的方式訪問了。

struct page

struct page數(shù)據(jù)結(jié)構(gòu)是用來抽象物理頁面的。這個(gè)數(shù)據(jù)結(jié)構(gòu)很重要，很多內(nèi)核代碼都是圍繞這個(gè)struct page 展開的。

此外還有個(gè)很重要的mem_map[]數(shù)組，是用來存放每一個(gè)struct page數(shù)據(jù)結(jié)構(gòu)的。通過數(shù)組，我們可以很方便的通過page找到頁幀號(hào)，頁幀號(hào)全稱叫page frame number ，pfm。

zone

除了page結(jié)構(gòu)，還有個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)叫zone。前面講到了物理內(nèi)存劃分為兩部分，線性映射和高端內(nèi)存。zone也是根據(jù)這個(gè)來劃分的。線性映射部分叫zone normal，高端內(nèi)存區(qū)域叫zone high。

頁面分配器和頁面回收都是基于zone來管理的。zone 也是一個(gè)很重要的管理物理內(nèi)存的數(shù)據(jù)結(jié)構(gòu)。

進(jìn)程角度看內(nèi)存管理

看完物理內(nèi)存的管理結(jié)構(gòu)，接下來從進(jìn)程的角度看下虛擬內(nèi)存是怎么管理的。

用戶空間有3G的大小，這3GB的大小也做了劃分，0 ~ 1GB 屬于代碼段，數(shù)據(jù)段，堆空間。1G ~ 3G 屬于mmap空間。

每個(gè)進(jìn)程都有一個(gè)管理進(jìn)程的數(shù)據(jù)結(jié)構(gòu)，操作系統(tǒng)中叫做PCB，進(jìn)程控制塊，linux內(nèi)核中就用task_struct描述進(jìn)程控制塊，task_struct內(nèi)容非常多，后面我們會(huì)詳細(xì)講解，今天我們只關(guān)注mm成員。

mm成員會(huì)指向mm_struct描述進(jìn)程管理的內(nèi)存資源，我們這里只關(guān)注mmap，pgd。mmap指向該進(jìn)程的VMA的鏈表。我們知道進(jìn)程地址空間使用VMA來管理，VMA是離散的，所以內(nèi)核使用兩種方式來管理VMA：鏈表和紅黑樹。

pgd指向進(jìn)程所在的頁表，這里指的是進(jìn)程的頁表，進(jìn)程的一級(jí)頁表在fork的時(shí)候創(chuàng)建，進(jìn)程的二級(jí)頁表在實(shí)際使用的時(shí)候動(dòng)態(tài)創(chuàng)建，

以上這張圖就從進(jìn)程的角度講述了內(nèi)存管理的概貌。