1 前言內存管理是Linux內核中非常重要的部分，今天和大家一起學習一下。

當我們要學習一個新知識點時，比較好的過程是先理解出現這個技術點的 背景原因，同期其他解決方案，新技術點解決了什么問題以及它存在哪些不足和改進之處，這樣整個學習過程是 閉環 的，個人覺得這是個很好的學習思路。

凡事都是相通的，計算機學科的一些問題在現實生活中都可以找到原型，所以我覺得計算機科學家大部分都是善于觀察生活并總結歸納的。人類社會就是一臺復雜的機器，其中充滿了機制和規則，所以有時候跳進代碼海洋不如先回到生活之中，尋找原型再探究代碼，可能理解會更深刻。

2 為什么需要管理內存老子的著名觀點是無為而治，簡單說就是不過多干預而充分依靠自覺就可以有條不紊地運作，理想是美好的，現實是殘酷的。

在linux系統中如果以一種原始簡單的方式管理內存是存在一些問題的，我們來看幾個場景。

2.1 內存管理的問題

進程空間隔離問題

假如現在有ABC三個進程運行在linux的內存空間，設定os給進程A分配的地址空間是0-20M 進程B地址空間30-80M，進程C地址空間90-120M，如圖：

在某些時候程序空間的訪問可能出現問題，比如進程A訪問了屬于進程B的空間，進程B訪問了屬于進程C的空間，甚至修改了空間的值，這樣就會造成混亂和錯誤，所以實際中是不允許這種情況發生的。

內存效率和內存不足問題

機器的內存是有限資源，而進程數量是無法確定的，如果在某些時候已經啟動的進程占據了所有內存空間，此時就無法啟動新進程了，因為沒有新內存可分配了，但是我們觀察到已經啟動的進程有時候是在睡大覺，也就是給了內存也不用，這樣效率確實是有點低，所以我們需要一個管理員把不用的內存倒騰出來，另外連續內存實在是很珍貴，很多時候我們沒法有效及時地分配連續內存，因此虛擬化和離散化可能會有效提高內存的使用率。

程序定位調試和編譯運行問題

由于程序運行時的位置時不確定的，我們在定位問題、調試代碼、編譯執行時都會存在很多問題，我們希望每個進程有一致且完整的地址空間，同樣的起始位置放置了堆、棧以及代碼段等，從而簡化編譯和執行過程中的 linker 鏈接器、loader 加載器的使用。

2.2 虛擬地址空間

為了解決上述的一些問題，linux系統引入了虛擬空間的概念，虛擬化的出現和硬件有密不可分的聯系，可以說是軟硬件組合的結果，虛擬地址空間就是在程序和物理空間所增加的中間層，這也是內存管理的重點。

磁盤 disk 作為一種大容量的存儲也作為“內存”的一部分參與程序的運行，內存管理系統會將不常用非活躍內存進行頁面換出，可以認為內存是磁盤的緩存，內存中保留了活躍的數據，從而間接擴展了有限的物理內存空間，這部分空間稱為虛擬內存是相對于物理內存而言的。

3.段頁管理機制本文并不深入地將分段管理內存和分頁管理內存，因為將這些細節的優秀文章很多，感興趣的使用搜索引擎一鍵即達。

段頁機制也不是一蹴而就的，經歷了單純物理分段、單純分頁、單純邏輯分段等階段，最終演進出來了分段和分頁結合的內存管理方式，段頁結合獲得了分段和分頁的優勢也避免了單一模式的弊端，是一種比較好的管理模式。

本文對于段頁管理機制只想通俗地說明一些概念，段頁管理機制是分段式管理和分頁式管理的組合，段式管理是邏輯上的管理方式，分頁管理是偏物理上的管理方式。

計算機里面的一些技術和實現都可以在現實生活中找到縮影，所謂藝術和科技源自生活大概就是這個意思吧。

舉個栗子：

在進行居民戶籍管理時都會有區縣市的概念，但是實際上并沒有這種實體，都是邏輯上的，增加了這些行政單位之后可以讓地址管理更加直接。

對于我們居民來說唯一的實體就是自己的房子住所，這是物理上的單位，是真實存在的，這也是最基本的單位。

對比linux段頁時管理來說，段是邏輯上的單位相當于區縣市的概念，頁是物理上的單位相當于小區/房屋的概念，這樣就方便很多。

多級頁表也很好理解，總的物理內存假如有4GB，頁大小為4KB，那么就總共有2^20個頁，數量還是非常大的，這樣編號來建立索引尋址比較不方便，所以引入多級頁表，來減少存儲便于管理。

段頁機制加持下的邏輯地址和物理地址的映射關系簡圖，也就是虛擬地址到物理地址的對應關系：

內存管理單元（ MMU Memory Management Unit ）是硬件層組件，主要提供將虛擬地址映射為物理地址。

MMU 的工作流程：CPU 生成邏輯地址交給分段單元，分段單元進行處理將邏輯地址轉換為線性地址，再線性地址交給分頁單元，分頁單元根據頁表映射轉換內存物理地址，其中可能出現缺頁中斷。

缺頁中斷（ Page Fault ）是只當軟件試圖訪問一個虛擬地址時，經過段頁轉換為物理地址之后，此時發現該頁并沒有在內存中，這時 cpu 就會報出中斷，再進行相關虛擬內存的調入工作或者分配工作，如果出現異常也可能直接中斷。

4.物理內存和內存碎片前面說的段頁管理機制算是虛擬空間的部分，然而linux內存管理的另外一個重要部分就是物理內存的管理了，也就是如何分配和回收物理內存，這就涉及到一些內存分配算法和分配器。

4.1 物理內存分配器

分配器和分配算法就像公司財務，內存就像公司資金，如何把資金合理使用是財務的本職工作，如何把物理內存合理使用是分配器的分內之事。

4.2 內存碎片分類和機理

如果我們不知道內存碎片是什么，試想一下我們常說的碎片化的時間，也就是那些雖然空閑但是沒有被利用的時間，其實內存也是如此。

無論是時間還是內存被碎片化之后都無法被有效利用，因此合理管理減少碎片對我們來說是至關重要的，這也是物理內存分配算法和分配器的研究重點。

按照碎片的位置和產生原因，內存碎片分為外部碎片和內部碎片，我們看下這兩種碎片的直觀展示：

從圖中可以知道，外部碎片是進程與進程間未分配的內存空間，外部碎片的出現和進程頻繁的分配和釋放內存有直接關系，這個很好理解，模擬一下分配不同空間的進程不同時間釋放就可以看到外部碎片的產生了。

內部碎片主要因為分配器粒度問題以及一些地址限制導致實際分配的內存大于所需內存，這樣在進程內部就會出現內存空洞。

雖然虛擬地址讓進程使用的內存在物理內存上是離散的，但是很多時候進程需要一定量連續物理內存，如果大量碎片存在，就會造成無法啟動進程的問題，如圖Process7需要一塊連續的物理內存卻無法被分配：

5. 伙伴系統算法基本原理5.1 一些準備知識

物理頁框

linux將物理內存按照頁來劃分，內存頁的大小在不同的軟硬件中可能不一樣，linux內核設置為4KB，有的內核可能更大也可能更小，當時不同的大小在實際中都是有考量的，就像面包一樣有大有小，并不是整齊劃一的。

頁框記錄結構

在內核中為了建立對物理內存頁page的使用情況的監控，會有struct page這樣的數據結構來記錄頁的位置地址/使用情況等，相當于內核對內存頁管理的一本賬目。

延時分配和實時分配

linux系統有內核態和用戶態之分，內核態申請內存就立刻滿足并且認為這個請求一定是合理的。然而用戶態申請內存的請求，總是盡量延后分配物理內存，所以用戶態進程是先獲得一個虛擬內存區，在運行時通過缺頁異常獲得一塊真正的物理內存，我們執行 malloc 時獲取的只是虛擬內存而已，并不是真實的物理內存，也是這個原因造成的。

5.2 伙伴系統簡介

第一次聽到這個算法名稱就很好奇為什么叫伙伴系統？讓我們來一起揭秘。

伙伴系統要解決什么問題

伙伴系統算法是解決外部碎片的有力工具，簡單來說它針對頻繁請求和釋放不同大小的一組連續頁框的場景，建立一套管理機制來高效的分配和回收資源，降低外部碎片。

解決外部碎片的思路

第一種思路：把已經存在的外部碎片通過新的技術把這些非連續的空閑內存映射到連續的線性空間，其實相當于沒有去降低外部碎片的產生而是治理型方案，但是這種方案在真實需要連續物理內存時是無效的。

第二種思路：把這些小的空閑的不連續內存記錄在案，如果有新的分配需求就從中搜索合適的將空閑內存分配出去，這樣就避免了在新的區域進行分配內存，有種變廢為寶的感覺，其實這樣場景也很熟悉當你想吃一包餅干時，你媽媽肯定會說先把之前剩下一半沒吃完的吃掉，不要先開新的了。

基于一些其他方面的考量，linux內核選擇了第二種思路來解決外部碎片。

伙伴內存塊的定義

在伙伴系統中把大小相同且物理地址連續的兩塊內存區域稱為伙伴，連續地址的要求其實是比較苛刻了，但是這也是算法的關鍵，因為這樣的兩塊內存區域可以合并成一塊更大的區域。

伙伴系統的核心思想

伙伴系統將不同大小的連續物理頁框進行管理，在申請時從最接近的頁框大小進行分配，剩余的進行新的拆解，并將有伙伴關系的內存會進行合并成為大的頁框。

5.3 伙伴系統的基本過程

伙伴系統維護了 n=0~10 共 11 個塊鏈表，每個塊鏈表分別包含了大小為 2^n 個連續的物理頁。當 n=10 時即 1024 個 4KB 頁對應 4MB 大小的連續物理內存塊，這里的 n稱為 order，在伙伴系統中 order為0～10，也就是最小的是 4KB，最大的內存塊是4MB，這些相同大小的物理塊組成雙向鏈表進行管理，如圖展示了 order=0 和 order=2 的兩個雙向鏈表的情況：

申請內存過程：假設請求一個頁框塊，伙伴系統算法先在 order=0 的鏈表中檢查是否有空閑塊可分配。如果沒有則查找下一個更大的塊，在 order=1 的鏈表中找一個空閑塊，鏈表中存在就把2個頁框拆分，1個頁框分配出去1 個頁框加入到 order=0的鏈表中。如果 order=1 的鏈表中仍未找到空閑塊，就繼續向更大的order搜索，如果找到進行拆分處理，如果最終至 order=10 的鏈表也沒有空閑塊，則算法報錯。

合并內存過程：合并內存的過程是伙伴算法中伙伴塊的體現，算法把兩個塊具有相同大小 A且它們物理地址連續的內存合并為一個大小為 2A 的單獨塊。伙伴算法是自底向上迭代合并的，其實這個過程和 leveldb 中 sst 的合并過程很相似，區別在于伙伴算法要求內存塊是連續的，這個過程也體現了伙伴系統對于大塊內存的友好。

5.4 伙伴系統的優勢和不足

伙伴系統算法較好地解決了外部碎片問題，并且對于大內存塊的分配比較友好小粒度的內存可能造成內部碎片，但是伙伴系統對于伙伴塊的定義很苛刻，并且在合并伙伴塊的過程涉及較多的鏈表操作，對于一些頻繁的申請可能剛合并就會被拆分掉，這就做了無用功，所以伙伴系統還是存在一些問題的。

6. Slab分配器從伙伴系統的介紹可以知道其分配的最小單位是 4KB 的頁框，這對于一些頻繁申請的小到幾十字節的內存來說還是十分浪費的，所以我們需要更細粒度的分配器，這就是slab分配器。

slab分配器并不是和伙伴系統分立的，而是建立在伙伴系統之上，可以看作是伙伴系統的二級分銷商，更加靠近用戶側，但是slab分配器因為更靠近使用方，因此在結構實現上比伙伴系統更加復雜，本文只能簡單概括。

個人感覺slab分配器的亮點包括：最小粒度為對象和內存惰性歸還。

Linux 所使用的 slab 分配器的基礎是 Jeff Bonwick 為 SunOS 操作系統首次引入的一種算法。Jeff 的分配器是圍繞對象緩存進行的。在內核中，會為有限的對象集（例如文件描述符和其他常見結構）分配大量內存。Jeff 發現對內核中普通對象進行初始化所需的時間超過了對其進行分配和釋放所需的時間。因此他的結論是不應該將內存釋放回一個全局的內存池，而是將內存保持為針對特定初始化的狀態。

from 《linux slab 分配器剖析》

slab采用對象作為最小單位的理論基礎就在于初始化一個結構的時間可能超過了分配和釋放的時間。

slab分配器可以看作是一種內存預分配機制，就像超市會把常用的物品放到大家更容易找到的位置，事先把這些對象準備好申請時就可以立刻分配出去了。

slabs_full：鏈表中slab已經完全分配出去

slabs_partial：鏈表中的slab部分已經被分配出去了

slabs_empty： 鏈表中的slab都是空閑的 也就是可以被回收

對象是從 slab 中進行分配和釋放的，每個kmem_cache的slab列表是存在狀態遷移的，但是被回收的部分slab并不會立刻歸還給伙伴系統，并且在分配時會優先分配最近被釋放的對象，目的是利用cpu緩存的局部性原理，可以看出來slab分配器的細節做的很足，但是為了實現這一套復雜的邏輯，就要維護多個隊列會比伙伴系統更復雜。