虛擬內(nèi)存
1.1. 為什么要使用虛擬內(nèi)存技術
1.2. 理論前提
1.3. 虛擬內(nèi)存實現(xiàn)
1.4. 頁機制
1.5. MMU
1.6. 物理內(nèi)存映射
進程的內(nèi)存分布
2.1. 內(nèi)核態(tài)
2.2. 用戶態(tài)
進程內(nèi)存管理
3.1. 物理內(nèi)存管理
3.2. node蝌诡、zone桩砰、page
3.3. 伙伴算法
3.4. slab

Linux 內(nèi)存管理

虛擬內(nèi)存

眾所周知逗抑，Linux采用虛擬內(nèi)存管理技術嘀略，每個進程都有獨立的進程地址空間。這是Linux內(nèi)存管理的基礎，所以我們先講解一下虛擬內(nèi)存技術。虛擬內(nèi)存技術是基于交換技術（swap）的章鲤，只不過交換的是頁或者段。

為什么要使用虛擬內(nèi)存技術

或者說使用虛擬技術的好處：

擴大內(nèi)存（主要催生虛擬內(nèi)存原因）
安全性提高（不直接訪問物理內(nèi)存）
易于開發(fā)（每個進程擁有獨立的用戶空間）

舉一個栗子來說明：

如果我們直接使用物理內(nèi)存咆贬，CPU需要某一個值的時候败徊，直接去物理內(nèi)存中取就可以了，簡單直接掏缎。

但是我們需要知道物理地址的值皱蹦，每次程序開始執(zhí)行，也就是執(zhí)行程序從磁盤被load到物理內(nèi)存中之后眷蜈，我們必須告訴CPU沪哺，程序是從哪一個地址開始執(zhí)行的(即PC寄存器的值)；

還有一個致命的缺點是：程序使用的內(nèi)存會被物理內(nèi)存所限制酌儒，比如我們的機器上只有512M內(nèi)存辜妓，那我們的程序就不能使用需占1G內(nèi)存的程序了，這點或許是催生虛擬內(nèi)存產(chǎn)生的最主要原因忌怎。

理論前提

我們知道想要裝下超過物理內(nèi)存大小的程序籍滴，那么我們可以選擇增加內(nèi)存條（硬擴充），同時也可以通過軟件進行擴充（軟擴充）榴啸，其中交換技術（包括虛擬內(nèi)存技術）就屬于軟擴充孽惰。

虛擬內(nèi)存技術就是只裝入程序的一部分，就開始運行整個程序鸥印。那么這樣內(nèi)存壓力就會變小勋功，能夠運行大內(nèi)存需求的軟件腥例。

那么這么做可以嗎？當然可以酝润，當時提出一個理論來支撐：程序局部性原理。

在一段時間內(nèi)璃弄，整個程序的執(zhí)行僅限于程序中的某一部分要销。相應地，執(zhí)行所訪問的存儲空間也局限于某個內(nèi)存區(qū)域夏块。局部性原理又表現(xiàn)為：時間局部性和空間局部性疏咐。

時間局部性是指如果程序中的某條指令一旦執(zhí)行，則不久之后該指令可能再次被執(zhí)行脐供；如果某數(shù)據(jù)被訪問浑塞，則不久之后該數(shù)據(jù)可能再次被訪問≌海空間局部性是指一旦程序訪問了某個存儲單元酌壕，則不久之后。其附近的存儲單元也將被訪問歇由。

虛擬內(nèi)存實現(xiàn)

實現(xiàn)原理：

當進程要求運行的時卵牍，不是將他的全部信息裝入內(nèi)存，而是將其一部分先裝入內(nèi)存沦泌，另一部分暫時留在外存糊昙，進程在運行過程中，要使用信息不在內(nèi)存時谢谦，發(fā)生中斷释牺，由操作系統(tǒng)將他們調(diào)如內(nèi)存，以保證進程的正常運行回挽。

但是呢没咙，從進程角度來說，會認為它擁有連續(xù)可用的內(nèi)存（一個連續(xù)完整的地址空間）厅各，而實際上镜撩，它通常是被分隔成多個物理內(nèi)存碎片，還有部分暫時存儲在外部磁盤存儲器上队塘，在需要時進行數(shù)據(jù)交換袁梗。

而這一部分外部磁盤存儲（輔存）就叫做交換分區(qū)。交換分區(qū)的主要功能是當全部的 RAM 被占用并且需要更多內(nèi)存時憔古，用磁盤空間代替 RAM 內(nèi)存遮怜。

內(nèi)核使用一個內(nèi)存管理程序來檢測最近沒有使用的內(nèi)存塊（內(nèi)存頁）。內(nèi)存管理程序?qū)⑦@些相對不經(jīng)常使用的內(nèi)存頁交換到硬盤上專門指定用于“分頁”或交換的特殊分區(qū)鸿市。那些換出到硬盤的內(nèi)存頁面被內(nèi)核的內(nèi)存管理代碼跟蹤锯梁，如果需要即碗，可以被分頁回 RAM。

總結一下陌凳，虛擬內(nèi)存實現(xiàn)可以總結為三步：

先加載進程的一部分數(shù)據(jù)
需要不在內(nèi)存的數(shù)據(jù)剥懒，發(fā)生中斷（缺頁中斷/缺段中斷）
將數(shù)據(jù)調(diào)入內(nèi)存

我們知道，根據(jù)存儲管理可以分為分頁式存儲合敦、段式存儲初橘、段頁式存儲3種。Linux 采用的是段頁式存儲充岛，但是保檐，大多數(shù)文章為什么都沒有提及段式存儲相關，為什么呢崔梗？

因為在Linux內(nèi)部的地址的映射過程為邏輯地址–>線性地址–>物理地址夜只，邏輯地址經(jīng)段機制轉(zhuǎn)化成線性地址；線性地址又經(jīng)過頁機制轉(zhuǎn)化為物理地址蒜魄。簡單的講就是扔亥，在虛擬內(nèi)存管理的時候，實質(zhì)上的管理的是一段一段的（邏輯段）权悟，這一段一段的內(nèi)存組和起來就是我們常規(guī)理解的線形地址砸王，而在這一段一段的虛擬內(nèi)存再使用頁機制轉(zhuǎn)化到物理內(nèi)存上。

我們要知道峦阁，頁是信息的物理單位谦铃，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭榔昔，提高內(nèi)存的利用率驹闰。段則是信息的邏輯單位，它含有一組其意義相對完整的信息撒会。分段的目的是為了能更好地滿足用戶的需要嘹朗。這也是段和頁的區(qū)別。

Linux上的段機制和頁機制下面會分開講解诵肛。段機制是Linux在組織虛擬出來的虛擬內(nèi)存屹培，而頁機制則是在實現(xiàn)虛擬內(nèi)存。

頁機制

虛擬內(nèi)存空間中的地址叫做“虛擬地址”怔檩；而實際物理內(nèi)存空間中的地址叫做“實際物理地址”或“物理地址”褪秀。

盡管處理器的最小可尋址單位通常為字或字節(jié)，但是Linux中內(nèi)存管理單元(MMU薛训，把虛擬地址轉(zhuǎn)換為物理地址的硬件設備)是以頁為單位處理媒吗。我們把虛擬出來的內(nèi)存分成等大的內(nèi)存塊，叫做頁（虛擬內(nèi)存空間的順序劃分）乙埃，把物理內(nèi)存分成同等大小的內(nèi)存塊闸英，叫做頁框（對物理內(nèi)存按順序等大小的劃分）锯岖。

我們知道，缺頁中斷過后操作系統(tǒng)會將對應的頁調(diào)入內(nèi)存甫何，那么常規(guī)操作系統(tǒng)是怎么實現(xiàn)這個邏輯的呢出吹？

首先檢測是否有空閑的頁框，如果有辙喂，那么將從交換分區(qū)調(diào)入的頁裝配到空閑頁框中（swap in）趋箩。如果沒有空閑頁框，那系統(tǒng)按預定的置換策略（頁面置換算法）自動選擇一個或一些在內(nèi)存的頁面加派，如果這個或者這些頁面為dirty，那么就將其換到（swap out）交換分區(qū)跳芳，空出頁框了芍锦，就可以安置所需的頁（swap in）。

值得說明的是飞盆，交換分區(qū)的數(shù)據(jù)來源于從物理內(nèi)存中淘汰出來的頁面娄琉，同時當缺頁中斷的時候，就是將交換分區(qū)中的頁面調(diào)入物理內(nèi)存中吓歇。

但是孽水，在頁面置換算法上，Linux 并沒有采取這一種常規(guī)做法城看，Linux有一個守護進程kswapd女气，比較每個內(nèi)存區(qū)域的高低水位來檢測是否有足夠的空閑頁面來使用。每次運行時测柠，僅有一個確定數(shù)量的頁面被回收炼鞠。這個閾值是受限的，以控制I/O壓力轰胁。每次執(zhí)行回收谒主，先回收容易的，再處理難的赃阀■希回收的頁面會加入到空閑鏈表中。

Linux采用的頁面置換算法是一種改進地LRU算法--最近最少使用（LRU）頁面的衰老算法榛斯，維護兩組標記：活動/非活動和是否被引用观游。第一輪掃描清除引用位，如果第二輪運行確定被引用肖抱，就提升到一個不太可能回收的狀態(tài)备典，否則將該頁面移動到一個更可能被回收的狀態(tài)。

處于非活動列表的頁面意述，自從上次檢查未被引用過提佣，因而是移除的最佳選擇吮蛹。被引用但不活躍的頁面同樣會被考慮回收，是因為一些頁面是守護進程訪問的拌屏，可能很長時間不再使用潮针。

狀態(tài)轉(zhuǎn)換如下：

頁框置換算法中考慮的頁面狀態(tài)

另外，內(nèi)存管理還有一個守護進程pdflush倚喂，會定期醒來每篷，寫回臟頁面；或者可用內(nèi)存下降到一定水平后被內(nèi)核喚醒端圈。

MMU

經(jīng)過前面講解焦读，對于一個進程（程序）來說，看到的就是一大塊連續(xù)的線形地址了舱权。但是想要探究更為具體的實現(xiàn)矗晃，那就要介紹MMU了。

內(nèi)存管理單元（Memory Management Unit）簡稱MMU宴倍，MMU位于處理器內(nèi)核和連接高速緩存以及物理存儲器的總線之間张症。當處理器內(nèi)核取指令或者存取數(shù)據(jù)的時候，都會提供一個有效地址(effective address)鸵贬，或者稱為邏輯地址俗他、虛擬地址，MMU會將邏輯地址映射為物理地址阔逼。

這對于多進程系統(tǒng)非常重要兆衅。例如，在32位Linux里嗜浮，進程A在地址0x08048000映射了可執(zhí)行文件涯保，進程B同樣在地址0x08048000映射了可執(zhí)行文件，如果A進程讀地址0x08048000周伦，讀到的是A的可執(zhí)行文件映射到RAM的內(nèi)容夕春，而進程B讀取地址0x08048000時，則讀到的是B的可執(zhí)行文件映射到RAM的內(nèi)容专挪。意思就是說及志，兩個進程雖然虛擬地址是一樣的，但是他們的對應的真實數(shù)據(jù)頁可能是不一樣的寨腔。

要將虛擬地址轉(zhuǎn)換成物理地址速侈，可以通過建立一張映射表完成。頁幀（Page Frame）是指物理內(nèi)存中的一頁內(nèi)存迫卢，MMU虛實地址映射就是尋找物理頁幀的過程倚搬。

MMU軟件配置的核心是頁表（Page Table），它描述MMU的映射規(guī)則乾蛤，即虛擬內(nèi)存哪(幾)個頁映射到物理內(nèi)存哪(幾)個頁幀每界。頁表由一條條代表映射規(guī)則的記錄組成捅僵，每一條稱為一個頁表條目（Page Table Entry），整個頁表保存在片外內(nèi)存眨层，MMU通過查找頁表確定一個虛擬地址應該映射到什么物理地址庙楚，以及是否有權限映射。

既然所有發(fā)往內(nèi)存的地址信號都要經(jīng)過MMU處理趴樱，那么MMU就可以以很小的代價承擔更大的責任馒闷，比如內(nèi)存保護。可以在PTE條目中預留出幾個比特叁征，用于設置訪問權限的屬性纳账，如禁止訪問、可讀捺疼、可寫和可執(zhí)行等塞祈。設好后，CPU訪問一個虛擬地址時帅涂，MMU找到頁表中對應PTE，把指令的權限需求與該PTE中的限定條件做比對尤蛮，若符合要求就把虛擬地址轉(zhuǎn)換成物理地址媳友，否則不允許訪問，并產(chǎn)生異常产捞。

物理內(nèi)存映射

我們知道Linux MMU處理單位為頁醇锚，一個32bits虛擬地址，每頁大小4k坯临，可以劃分為2^20個內(nèi)存頁焊唬，如果物理頁幀隨意映射，頁表的空間占用就是(2^20)*sizeof(PTE)*進程數(shù)（每個進程都要有自己的頁表）看靠，PTE一般占4字節(jié)赶促，即每進程4M，這對空間占用和MMU查詢速度都很不利挟炬。

實際應用中不需要每次都按最小粒度的頁來映射鸥滨，很多時候可以映射更大的內(nèi)存塊。因此最好采用變化的映射粒度谤祖，既靈活又可以減小頁表空間婿滓。Linux 采用的就是三級頁表。隨著64位CPU粥喜，比如X86_64凸主，出現(xiàn)四級頁表頁開始誕生，原理相同额湘，這里看一下Linux的三級頁表卿吐。

頁全局目錄 (Page Global Directory旁舰，即PGD) ：全局字典，指向中間頁目錄但两。
頁中間目錄( Page Middle Directory鬓梅，即PMD) ：中間字典，也可以理解為二級目錄谨湘，指向PTE中的表項绽快。
頁表 (Page Table，即PTE)：頁表(PTE)紧阔，指向物理頁面坊罢。
偏移量(Page Offset)：即頁內(nèi)偏移。

線性地址擅耽、頁表和頁表項線性地址不管系統(tǒng)采用多少級分頁模型活孩，線性地址本質(zhì)上都是索引+偏移量的形式.

進程的內(nèi)存分布

以32位的計算機為例，一共可以虛擬出4G（2^32）的虛擬內(nèi)存乖仇，每個進程都有各自獨立的進程地址空間憾儒，意思就是每一個進程都有4G的線性虛擬地址空間。4G進程地址空間被劃分兩部分乃沙，內(nèi)核空間和用戶空間起趾。用戶空間從0到3G，內(nèi)核空間從3G到4G警儒；但是內(nèi)核空間是由內(nèi)核負責映射训裆，不會跟著進程變化；內(nèi)核空間地址有自己對應的頁表蜀铲，用戶進程各自有不同的頁表边琉。可以理解為每個普通進程都有自己的用戶空間，但是內(nèi)核空間被所有普通進程所共享（每個進程虛擬空間的3G~4G部分是相同的）记劝。

另外变姨，用戶態(tài)進程只能訪問0-3G，但是內(nèi)核態(tài)進程既可以訪問0-3G厌丑，也可以訪問3G-4G地址空間钳恕。

那內(nèi)核態(tài)到底是什么呢？運行在內(nèi)核態(tài)的進程相比于用戶態(tài)的進程擁有更高的權限蹄衷，用戶態(tài)的進程能夠訪問的資源受到了極大的控制忧额，而運行在內(nèi)核態(tài)的進程可以“為所欲為”，它能夠控制計算機的硬件資源愧口，例如協(xié)調(diào)CPU資源睦番，分配內(nèi)存資源，并且提供穩(wěn)定的環(huán)境供應用程序運行。

下面來看看進程在虛擬內(nèi)存中的分布情況

內(nèi)核態(tài)

固定映射區(qū)（Fixing Mapping Region）：該區(qū)域和4G的頂端只有4k的隔離帶托嚣，其每個地址項都服務于特定的用途巩检，如ACPI_BASE等。

永久內(nèi)存映射區(qū)（PKMap Region）：該區(qū)域可訪問高端內(nèi)存示启。訪問方法是使用alloc_page(_GFP_HIGHMEM)分配高端內(nèi)存頁或者使用kmap函數(shù)將分配到的高端內(nèi)存映射到該區(qū)域兢哭。

動態(tài)內(nèi)存映射區(qū)（Vmalloc Region）：該區(qū)域由內(nèi)核函數(shù)vmalloc來分配，特點是：線性空間連續(xù)夫嗓，但是對應的物理空間不一定連續(xù)迟螺。vmalloc分配的線性地址所對應的物理頁可能處于低端內(nèi)存，也可能處于高端內(nèi)存舍咖。

直接映射區(qū)（Direct Memory Region）：線性空間中從3G開始最大896M的區(qū)間矩父，為直接內(nèi)存映射區(qū)，該區(qū)域的線性地址和物理地址存在線性轉(zhuǎn)換關系：線性地址=3G+物理地址排霉。

用戶態(tài)

棧：棧是用戶存放程序臨時創(chuàng)建的局部變量窍株，也就是說我們函數(shù)括弧“{}”中定義的變量（但不包括static聲明的變量，static意味著在數(shù)據(jù)段中存放變量）攻柠。除此以外球订，在函數(shù)被調(diào)用時，其參數(shù)也會被壓入發(fā)起調(diào)用的進程棧中瑰钮，并且待到調(diào)用結束后冒滩，函數(shù)的返回值也會被存放回棧中。

mmap 內(nèi)存映射區(qū)：用于文件映射（包括動態(tài)庫）和匿名映射飞涂。常見的就是使用 mmap 分配的虛擬內(nèi)存區(qū)域。

堆：堆是用于存放進程運行中被動態(tài)分配的內(nèi)存段祈搜，它的大小并不固定较店，可動態(tài)擴張或縮減。當進程調(diào)用malloc等函數(shù)分配內(nèi)存時容燕，新分配的內(nèi)存就被動態(tài)添加到堆上（堆被擴張）梁呈；當利用free等函數(shù)釋放內(nèi)存時，被釋放的內(nèi)存從堆中被剔除（堆被縮減）蘸秘。

BSS段：BSS段包含了未初始化的全局變量官卡，在內(nèi)存中bss段全部置零。

數(shù)據(jù)段：數(shù)據(jù)段用來存放已初始化的全局變量醋虏，換句話說就是存放程序靜態(tài)分配的變量和全局變量寻咒。

代碼段：代碼段是用來存放可執(zhí)行文件的操作指令，也就是說是它是可執(zhí)行程序在內(nèi)存中的鏡像颈嚼。代碼段需要防止在運行時被非法修改毛秘，所以是不可寫的。

用一張圖總結一下：

進程內(nèi)存管理

進程內(nèi)存管理的對象是進程線性地址空間上的內(nèi)存鏡像，這些內(nèi)存鏡像其實就是進程使用的虛擬內(nèi)存區(qū)域（virtual memory areas叫挟，即VMA）艰匙。

Linux內(nèi)核通過一個被稱為進程描述符的task_struct 結構體來管理進程，這個結構體包含了一個進程所需的所有信息抹恳。mm_struct中的pgd為頁表员凝，就是前面講的一級頁表。task_struct中有一個結構體被稱為內(nèi)存描述符的mm_struct奋献，描述了一個進程的整個虛擬地址空間健霹。每個進程正是因為都有自己的mm_struct，才使得每個進程都有自己獨立的虛擬的地址空間

每一段已經(jīng)分配的虛擬內(nèi)存區(qū)域都會以一個vm_area_struct結構體表示秽荞，而組織這些結構一共有兩種形式：其中mm_struct->mm_rb是所有vm_area_struct組成的紅黑樹骤公，而mm_struct->mmap是所有vm_area_struct組成的鏈表，vma這個數(shù)據(jù)結構被雙重管理主要是為了加速查找速度（空間換時間）扬跋。

mm_struct中的mmap指針指向的vm_area_struct鏈表的每一個節(jié)點就代表進程的一個虛擬地址空間阶捆，即一個VMA。一個VMA最終可能對應ELF可執(zhí)行程序的數(shù)據(jù)段钦听、代碼段洒试、堆、棧朴上、或者動態(tài)鏈接庫的某個部分垒棋。

在這條鏈表上進行這樣表示，我們就可以將其理解為最開始所說的邏輯分段了痪宰。

物理內(nèi)存管理

通過mm_struct結構體完成了對虛擬內(nèi)存的管理叼架，那么物理內(nèi)存是如何管理和分配的呢？

經(jīng)過前面介紹衣撬，我們知道Linux以頁為單位進行分配乖订，隨之而來的就會有兩個問題：

如何解決頁外碎片問題
如何解決頁內(nèi)碎片問題

Linux 采用 buddy 系統(tǒng)（伙伴系統(tǒng)）來解決頁外碎片，采用 slab 分配器來解決頁內(nèi)碎片具练。同時 Linux 采用
了 Node乍构，Zone 和 page三級結構來描述物理內(nèi)存的。buddy 系統(tǒng)是建立在這三級結構之上的扛点。
slab 同時又在 buddy 系統(tǒng)之上管理著物理頁之內(nèi)的內(nèi)存請求（小內(nèi)存分配）哥遮。

node、zone陵究、page

在介紹管理物理內(nèi)存之前我們要先了解一下什么是 UMA 和 NUMA眠饮。

在多核系統(tǒng)中，如果物理內(nèi)存對所有CPU來說沒有區(qū)別铜邮，每個CPU訪問內(nèi)存的方式也一樣君仆，則這種體系結構被稱為Uniform Memory Access(UMA)。

如果物理內(nèi)存是分布式的，由多個cell組成（比如每個核有自己的本地內(nèi)存）返咱，那么CPU在訪問靠近它的本地內(nèi)存的時候就比較快钥庇，訪問其他CPU的內(nèi)存或者全局內(nèi)存的時候就比較慢，這種體系結構被稱為Non-Uniform Memory Access(NUMA)咖摹。

Linux適用于各種不同的體系結構, 而不同體系結構在內(nèi)存管理方面的差別很大评姨，因此linux內(nèi)核需要用一種體系結構無關的方式來表示內(nèi)存。因此linux內(nèi)核把物理內(nèi)存按照CPU節(jié)點劃分為不同的node, 每個node作為某個cpu結點的本地內(nèi)存, 而作為其他CPU節(jié)點的遠程內(nèi)存, 而UMA結構下, 則任務系統(tǒng)中只存在一個內(nèi)存node, 這樣對于UMA結構來說, 內(nèi)核把內(nèi)存當成只有一個內(nèi)存node節(jié)點的偽NUMA萤晴。

內(nèi)存節(jié)點的數(shù)據(jù)結構為pg_data_t, 也就是struct pglist_data吐句，而Linux會將所有 pg_data_t 使用雙向鏈表組織起來。

內(nèi)存管理區(qū)(zone)店读，zone由struct zone_struct 數(shù)據(jù)結構來描述嗦枢。zone的類型由zone_t表示，主要有ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM 這三種類型屯断。

分區(qū)	功能
ZONE_DMA	可以用于DMA操作的頁
ZONE_NORMAL	正常的文虏、規(guī)則映射的頁
ZONE_HIGHMEM	高內(nèi)存地址的頁，并不永久性映射

內(nèi)存區(qū)域的確切邊界和布局是和硬件體系結構相關的。例如，在x86硬件上点晴，一些設備只能在最低的16MB地址空間進行DMA操作，因此ZONE_DMA就在0-16M范圍內(nèi)丸相，在決定分區(qū)的時候，先分配 ZONE_DMA 和 ZONE_HIGHMEM彼棍，剩下的就屬于 ZONE_NORMAL灭忠。ZONE_DMA大小是硬件決定的，和ZONE_NORMAL屬于低端內(nèi)存座硕，ZONE_HIGHMEM屬于高端內(nèi)存弛作。

節(jié)點、區(qū)域和頁框之間的關系如下圖：

上圖中的zone_mem_map是一個頁框的數(shù)組坎吻，它記錄了一個內(nèi)存分區(qū)的所有頁框的使用情況缆蝉。

用圖總結下：

image

伙伴算法

內(nèi)核子系統(tǒng)中有一個分區(qū)頁框分配器,用于處理對連續(xù)頁框組的內(nèi)存分配請求宇葱。其中名為管理區(qū)分配器部分接受動態(tài)內(nèi)存分配與釋放請求瘦真。

image.png

在每個內(nèi)存管理區(qū)（Zone）內(nèi)，頁框由伙伴系統(tǒng)來分配黍瞧。為了達到更好的系統(tǒng)性能诸尽，一小部分頁框保留在高速緩存中用于快速滿足對單個頁框的分配請求。

在 i386 體系結構中印颤，整個物理內(nèi)存被分為4k大小的頁框您机，我們知道經(jīng)過頁機制我們可以不必要求有大塊連續(xù)物理內(nèi)存，我們可以通過頁機制東拼西湊出一塊內(nèi)存，雖然物理內(nèi)存不連續(xù)际看，但是通過頁機制咸产，在虛擬內(nèi)存上就可以虛擬出一塊連續(xù)的虛擬內(nèi)存。但是仲闽，我們會更傾向于分配連續(xù)的物理內(nèi)存（頁框）脑溢，因為分配連續(xù)內(nèi)存時，頁表不需要更改赖欣，因此能降低TLB的刷新率（頻繁刷新會在很大程度上降低訪問速度）屑彻。有興趣的建議了解快表的機制。

那么為了能夠分配連續(xù)的物理內(nèi)存顶吮，就需要解決頁外碎片（外部碎片）的問題社牲，在Linux中采用伙伴算法來解決。

Buddy 算法將所有的空閑物理頁分成 10 組悴了，每組分別包含大小 1搏恤，2，4让禀，8挑社，16，32巡揍，64痛阻，
128，256腮敌，512 個連續(xù)物理頁阱当。每一組用鏈表組織起來。

image.png

分配：

對于一個 2^{order} 個連續(xù)頁框大小的內(nèi)存申請糜工，伙伴系統(tǒng)首先查看 zone->free_area[order] 中是否有空閑的塊弊添。如果找到，則直接分配給請求對象捌木。
如果沒有油坝，查找 zone->free_area[order+1] 是否有空閑塊，如果有: 則摘下一塊刨裆，并且分成兩等分澈圈，分配一份給請求對象，另一份插入到 zone->free_area[order] 中帆啃。
如果沒有瞬女，則依次往更大連續(xù)物理內(nèi)存分組尋找，直到滿足需求努潘。

回收：
回收算法根據(jù)提供的塊大小诽偷，將塊放到大小對應的鏈表中坤学。如果放入過程中發(fā)現(xiàn)有空閑伙伴塊，則合并伙伴报慕，形成更大的塊放到對應鏈表中深浮。

是否為伙伴塊需要滿足的條件：

兩個塊大小相同；
兩個塊地址連續(xù)眠冈；
兩個塊必須是同一個大塊中分離出來的略号；

slab

通過頁機制能夠非常方便的分配到物理內(nèi)存，但是通過伙伴算法分配的物理內(nèi)存也產(chǎn)生了頁內(nèi)碎片（內(nèi)部碎片）洋闽。但是內(nèi)核使用的很多都是小對象玄柠，可能就幾十字節(jié)，但是分配一個頁框也是4K诫舅，這種分配造成的浪費非常大羽利。比如存放文件描述符、進程描述符刊懈、虛擬內(nèi)存區(qū)域描述符等行為所需的內(nèi)存都不足一頁这弧。

Linux為了解決這種問題呢，在內(nèi)核實現(xiàn)了slab分配器虚汛，主要針對內(nèi)核中經(jīng)常分配并釋放的對象匾浪。核心思想就是存儲池的運用。

slab會把對象池化卷哩，相同的對象放到一個存儲池里蛋辈，每個對象池都是一個 kmem_cache 結構的引用（稱為一個 cache）。所有的對象池使用鏈表組織起來将谊，即cache_chain冷溶。

image

而每一個對象池（kmem_cache）存在3種slab：

slabs_full：完全分配的slab
slabs_partial：部分分配的slab
slabs_empty：空slab,或者沒有對象被分配

每一個slab就是一個或者多個連續(xù)的物理框（通常只有一個），他們是從伙伴系統(tǒng)中申請過來的物理內(nèi)存尊浓，被劃成很多小塊逞频，用于快速分配給對應的小對象。其中栋齿， slabs_empty 列表中的 slab 是進行回收（reaping）的主要備選對象苗胀。正是通過此過程，slab 所使用的內(nèi)存被返回給操作系統(tǒng)供其他用戶使用瓦堵。

每一個slab是不斷移動的基协。當一個 slab 中的所有對象都被使用完時，就從 slabs_partial 列表中移動到 slabs_full 列表中谷丸。當一個 slab 完全被分配并且有對象被釋放后堡掏，就從 slabs_full 列表中移動到 slabs_partial 列表中应结。當所有對象都被釋放之后刨疼，就從 slabs_partial 列表移動到 slabs_empty 列表中泉唁。

image

每當要申請這樣一個對象時，slab分配器就從一個slab列表中分配一個這樣大小的單元出去揩慕，而當要釋放時亭畜，將其重新保存在該列表中，而不是直接返回給伙伴系統(tǒng)迎卤。slab 分配器還可以支持硬件緩存對齊和著色拴鸵，這允許不同緩存中的對象占用相同的緩存行，從而提高緩存的利用率并獲得更好的性能蜗搔。

最后劲藐，用一張經(jīng)典的圖總結一下：