【操作系統】內存管理概述

內存管理硬件結構

常見的內存分配函數有 malloc，mmap 等，但大家有沒有想過，這些函數在內核中是怎麼實現的？換句話說，Linux 內核的內存管理是怎麼實現的？

內存管理的目的是管理系統中的內存，俗稱內存橋，換成專業屬於叫 DDR。我們有必要先了解下計算機對內存管理的硬件結構。我們先看下關於地址的一些概念。

早期內存的使用方法

在計算機早期的發展階段，要運行一個程序，要把計算機程序，全部裝載在內存中，程序訪問的內存地址就是實際的物理地址。所以，當運行多個程序時，必須保證運行程序的使用的總的內存量要小於總的內存大小。那這種方式存在什麼問題呢？

一個問題是進程地址空間不合理，任意的進程可以隨意修改其他進程的地址數據；二是內存使用效率很低，內存緊張時需要把整個進程交換到交換分區中，導致程序的使用效率很低。

分段

爲了解決這兩個問題，當時的人們提出了分段的機制。它的核心思想是建立一個虛擬地址空間，將一個程序分成代碼段，數據段，堆棧段什麼的，每個段各自管理不同的數據。在虛擬地址空間和物理地址空間之間做映射，實現進程的隔離。

分頁

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

程序在運行的時候，需要哪個頁面，我再把相關頁面交換進來。經常不用的頁面會交換到 swap 分區。分頁機制也是按需分配，這是操作系統的核心思想。

邏輯地址，線性地址（intel 架構）

邏輯地址和線性地址是 intel 架構的概念，邏輯地址是程序產生的和段相關的那個部分，線性地址是邏輯地址轉換爲物理地址的一箇中間層。

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

虛擬地址

簡單的說就是可以尋址的一片空間。如果這個空間是虛擬的，我們就叫做虛擬地址空間；如果這個空間是真實存在的，我們就叫做物理地址空間。虛擬地址空間是可以任意的大的，因爲是虛擬的。而物理地址空間是真實存在的，所以是有限的

物理地址

物理地址是 CPU 通過外部總線直接訪問的外部內存地址。如果系統啓動了分頁機制，系統啓動後必須通過查頁表的方式去獲取物理地址。

如果沒有啓動分頁機制，系統啓動後就通過直接變爲了物理地址。

結構圖

在啓動 MMU 後，CPU 訪問的是虛擬地址，虛擬地址經過 MMU 後轉換爲物理地址，這種轉換通過查詢存儲在主存儲器的頁表完成。頻繁訪問主存儲器比較耗時，因此引入了 TLB 的概念。

TLB 緩存了上一次虛擬地址到物理地址的轉換，TLB 不存儲具體的數據，存儲的是頁表的表項。如果能在 TLB 中找到本次訪問的頁表項，就不需要再訪問主存了。我們把這個過程叫做 TLB 命中。如果沒有找到頁表項，這個時候只能去查詢頁表，我們叫做 TLB Miss。如何查詢頁表的後面我們會詳細介紹。

假設，現在虛擬地址已經轉換爲了物理地址。這個時候就會去找一級緩存。看一級緩存有沒有需要的數據。我們這裏採用的是物理索引（PI），物理標籤（PT）的方式。現在的大部分 cache 都採用組相聯的方式，訪問 cache 地址會被分爲偏移域，索引域，標記域三部分。如果一級緩存沒有相應的數據，就要訪問二級緩存了，如果二級緩存沒有數據，就要訪問主存儲器了。

還有一種情況，當系統物理內存短缺的時候，Linux 內核中，有頁面回收的機制，會把不常用的頁面交換到 swap 分區中，這個動作叫做 swap。這張圖就從硬件結構的角度解釋了內存管理的基本構成。

虛擬地址到物理地址的轉換

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

在 ARM 處理器中，TTBRx 寄存器存放着頁表基地址，我們這裏的一級頁表有 4096 個頁表項。每個表項中存放着二級表項的基地址。我們可以通過虛擬地址的 L1 索引訪問一級頁表，訪問一級頁表相當於數組訪問。

二級頁表通常是動態分配的，可以通過虛擬地址的中間 8bit 位 L2 索引訪問二級頁表，在 L2 索引中存放着最終物理地址的高 20bit 位，然後和虛擬地址的低 12bit 位就組成了最終的物理地址。以上就是虛擬地址轉換爲物理地址的過程。

MMU 訪問頁表是硬件實現的，但頁表的創建和填充需要 Linux 內核來填充。通常，一級頁表和二級頁表存放在主存儲器中。

內存管理總覽

系統調用

Linux 內核把用戶空間分爲兩部分：用戶空間和內核空間。用戶進程運行在用戶空間，如果需要內存的話通過 C 庫提供的malloc，mmap，mlock，madvice，mremap函數。C 庫的這些函數最終都會調用到內核的sys_xxx接口分配內存空間。如malloc函數是依賴內核的sys_brk接口分配內存空間的。mmap 對應接口爲sys_mmap。

我們以malloc函數爲例，假設現在用戶態的內存短缺，就會通過sys_brk調用去堆上分配內存。在用戶空間分配的是虛擬內存，因此，在堆上分配的也是虛擬內存。

vm_area_struct

Linux 內核把這些地址稱爲進程地址空間。內核使用struct vm_area_struct 來管理這些進程地址空間。VMA主要管理內存的創建，插入，刪除，合併等操作。

由於每個不同質的虛擬內存區域功能和內部機制都不同，因此一個進程使用多個vm_area_struct結構來分別表示不同類型的虛擬內存區域。各個vm_area_struct結構使用鏈表或者樹形結構鏈接，方便進程快速訪問，如下圖所示：

vm_area_struct結構中包含區域起始和終止地址以及其他相關信息，同時也包含一個vm_ops指針，其內部可引出所有針對這個區域可以使用的系統調用函數。這樣，進程對某一虛擬內存區域的任何操作需要用要的信息，都可以從vm_area_struct中獲得。mmap函數就是要創建一個新的vm_area_struct結構，並將其與文件的物理磁盤地址相連。

缺頁中斷

缺頁中斷是實現了按需分配的思想。站在用戶角度，缺頁中斷後可分配的頁面有匿名頁面和page cache。匿名頁面指的是沒有關聯任何文件的頁面，比如進程通過mlock從堆上分配的內存。page cache是關聯了具體緩存的頁面。比如在看視頻時的緩存就是page cache。匿名頁面和page cache的產生需要頁面分配器完成。

夥伴系統

頁面分配器是以頁框爲單位的。典型的頁面分配器就是夥伴系統。夥伴系統是一個結合了 2 的方冪個分配器和空閒緩衝區合併計技術的內存分配方案, 其基本思想很簡單。

內存被分成含有很多頁面的大塊, 每一塊都是 2 個頁面大小的方冪。如果找不到想要的塊, 一個大塊會被分成兩部分, 這兩部分彼此就成爲夥伴。其中一半被用來分配，而另一半則空閒。這些塊在以後分配的過程中會繼續被二分直至產生一個所需大小的塊。當一個塊被最終釋放時，其夥伴將被檢測出來，如果夥伴也空閒則合併兩者。

雖然夥伴算法實現不復雜，但頁面分配器是內核實現最複雜的系統之一。如果內存充足時，你需要多少內存，頁面分配器會給你分配多少。但如果內存緊張時，頁面分配器會做很多嘗試，比如開啓異步模式的頁面回收，memory compaction（內存規整）。如果經過嘗試後內存仍然不夠，這個時候會拿出重型武器 oom kill 會殺死一些進程。

slab 分配器

剛剛我們講的都是以頁爲單位分配的內存。但有時候我們需要幾個字節的內存怎麼辦。這個時候就需要 slab 分配器。slab 可以管理特定大小的內存，對於固定大小的內存就不需要 VMA 去管理了。頁面分配器是中央財政，slab 是地方財政。如果地方需要種棵樹就不要勞煩中央財政了。

頁面回收

頁面回收實現了頁面換出的理念。當系統內存短缺的時候，系統需要換出一部分內存。這部分內存通常是 page cache 或者匿名頁面。內核裏面有個 swap 守護線程，當系統內存低於某個水位時，會被喚醒去掃描 LRU（最近最少使用）鏈表，一般匿名頁面和 page cache 會添加到鏈表中。實際上，在內核中又將 LRU 鏈表做了細分，又細分爲活躍鏈表，不活躍鏈表，匿名頁面鏈表，page cache 鏈表。

內核相對比較喜歡回收page cache，乾淨的page cache 直接合並就好了。對於髒的page cache需要寫回磁盤的一個動作。對於匿名頁面是不能直接合並的，匿名頁面一般都是進程的私有數據。一般這些匿名頁面數據需要回收時會 swap out 到 swap 分區騰出空間，當這些進程再次需要這些數據時，纔會從 swap 分區 swap in。頁面回收我們會在後面詳細講解。

如果分配好了頁面，這個時候就要涉及到頁表的管理了。頁表分爲內核頁表和進程頁表。內核提供了很多和內核頁表相關的函數，後續我們再分析。

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

反向映射

當進程分配內存併發生寫操作時，會分配虛擬地址併產生缺頁, 進而分配物理內存並建立虛擬地址到物理地址的映射關係，這個叫正向映射。

反過來，通過物理頁面找到映射它的所有虛擬頁面叫反向映射（reverse-mapping, RMAP），它可以從 page 數據結構中找到映射這個 page 的虛擬地址空間，也就是我們講過的 VMA 這個東西，ramp 系統是爲頁面回收服務的，如果要回收一個匿名頁面或者 page cache 的時候，需要把映射這個頁面的用戶 PTE 斷開映射關係纔可以去回收。

KSM

KSM，Kernel Samepage Merging，最早是用來優化 KVM 虛擬機來發明的一種機制。現在用來合併內容相同的匿名頁面。

huge page

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

頁遷移

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

內存規整

memory compaction，內存規整模塊是爲了緩解內存碎片化的，系統運行的時間越長，就越容易產生內存碎片，系統此時想分配連續的大塊內存就變得越來越難。

大塊連續的內存一般是內核所請求的，因爲對於用戶空間來講，大塊缺頁內存都是通過缺頁中斷一塊一塊來分配的。

內存規整的實現原理也不復雜，在一個 zoom 中有兩個掃描器，分別從頭到尾和從尾到頭掃描，一個去查找 zoom 中有那些頁面可以遷移的，另外一個去掃描有那些空閒的頁，兩個掃描器在 zoom 中相遇的時候，掃描就停止了。這個時候內存規整模塊就知道 zoom 中有那些頁面可以遷移到空閒頁面。經過這麼一折騰，就可以騰出一個大的連續的物理空間了。

OOM

在經過內存規整，頁面遷移等操作後，如果系統還不能分配出系統需要的頁面，Linux 就要使用最後一招了，殺敵一千，自損八百，OOM killer 會找一些佔用內存比較多的進程殺掉來釋放內存。

之所以會發生這種情況，是因爲 Linux 內核在給某個進程分配內存時，會比進程申請的內存多分配一些。這是爲了保證進程在真正使用的時候有足夠的內存，因爲進程在申請內存後並不一定立即使用，當真正使用的時候，可能部分內存已經被回收了。

比如當一個進程申請 2G 內存時，內核可能會分配 2.5G 的內存給它. 通常這不會導致什麼問題。然而一旦系統內大量的進程在使用內存時，就會出現內存供不應求，很快就會導致內存耗盡。這時就會觸發這個 oom killer，它會選擇性的殺掉某個進程以保證系統能夠正常運行。

內存管理的一些數據結構

線性映射

我們以 32 位系統爲例，我們知道進程最大的地址訪問空間是 4G，0~3GB 是用戶空間，3 ~ 4GB 是內核空間。

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

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

如果要訪問高端內存就麻煩一點，1G 的物理內存空間有限，不能把所有地址都映射到線性地址空間。如果要訪問高端內存就要通過動態映射的方式訪問了。

struct page

struct page數據結構是用來抽象物理頁面的。這個數據結構很重要，很多內核代碼都是圍繞這個struct page 展開的。

此外還有個很重要的mem_map[]數組，是用來存放每一個struct page數據結構的。通過數組，我們可以很方便的通過 page 找到頁幀號，頁幀號全稱叫page frame number ，pfm。

zone

除了 page 結構，還有個很重要的數據結構叫 zone。前面講到了物理內存劃分爲兩部分，線性映射和高端內存。zone 也是根據這個來劃分的。線性映射部分叫 zone normal，高端內存區域叫 zone high。

頁面分配器和頁面回收都是基於 zone 來管理的。zone 也是一個很重要的管理物理內存的數據結構。

進程角度看內存管理

看完物理內存的管理結構，接下來從進程的角度看下虛擬內存是怎麼管理的。

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

每個進程都有一個管理進程的數據結構，操作系統中叫做 PCB，進程控制塊，linux 內核中就用task_struct描述進程控制塊，task_struct內容非常多，後面我們會詳細講解，今天我們只關注 mm 成員。

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

pgd 指向進程所在的頁表，這裏指的是進程的頁表，進程的一級頁表在 fork 的時候創建，進程的二級頁表在實際使用的時候動態創建，

以上這張圖就從進程的角度講述了內存管理的概貌。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/G9TVl5noQJ7mODSvc6Dr6Q