Linux記憶體管理，記憶體定址
linux記憶體管理
面向基礎底層的知識，深入學習linux記憶體分配，虛擬記憶體管理，作業系統等相關知識。基於linux核心2。6版本。
“咬定青山不放鬆，立根原在破巖中。千磨萬擊還堅韌，任爾東西南北風。” —— 鄭板橋 《竹石》
概述
首先介紹一下概況性的觀點，然後繼續深入實現，關於記憶體管理機制，有個比較通用的觀點，即為了高效的管理物件，通常會使用類似於
記憶體池
（物件池）的概念。例如：
在Python的記憶體管理機制上面，即用到了“大物件記憶體直接alloc， 小物件使用記憶體池分級進行管理”是一種比較複雜的記憶體管理機制
在Nginx中也使用了記憶體池的概念，即Nginx對每個TCP連線都分配了一個記憶體池，HTTP框架會對每一次HTTP請求再分配一次記憶體池，請求結束後銷燬整個記憶體池，並把曾經分配的記憶體一次性歸還給作業系統
記憶體管理的高效性：
減少了作業系統分配記憶體，回收記憶體的開銷
減少了記憶體碎片，提高了記憶體有效利用率
對於頻繁使用的資料結構，使用記憶體管理去快取
基礎的概念
BIOS（
Basic Input/Output System
）：中的一些資料一般在物理地址前1MB， 主要職責為計算機啟動引導時系統自檢，並載入作業系統啟動的載入程式
核心：通常啟動之後的物理地址是BIOS之後從
0x00100000
地址開始 （低地址）
MMU（
memory management unit
）：CPU的一個單獨模組，用來將虛擬地址轉換為實際物理地址的元件，MMU通常使用記憶體中的一個元件，通常稱為頁表（page table）或
PTE
（page table entry）來管理虛擬地址到實際物理地址的對映。（硬體層面）
PTE（
page table entry
）：頁表儲存著對映資訊，頁表實現了頁表置換演算法，用來儲存最常用的頁對映，即LRU（
least recently used
）演算法。當對映缺失時，則會向CPU傳送一個
Page Fault
即
缺頁中斷
， CPU則會在物理記憶體（RAM）中尋找一個空閒的頁， 並更新PTE。如果沒有可用的空閒頁，則CPU會選擇PTE頁表中的頁，置換到磁碟上並在PTE頁面設定標誌，這就是通常所說的頁面排程（
paging
），將記憶體頁換出到磁碟或者
swap
空間。（軟體層面，虛擬記憶體）
linux使用三級頁表完成虛擬地址到實際物理地址的轉換，為了加速這樣的轉換通常的體系結構層面使用了TLB來加速轉換
TLB（
Translation lookaside buffer
）： 是儲存虛擬地址到物理地址的一個快取，是MMU的一部分，儲存在CPU和CPU cache之間，有效的減少了透過轉換去獲取物理地址的次數。
架構
自上而下，介紹linux記憶體分配的整體架構
1。 記憶體分配架構
整體架構如下圖所示，結合圖示介紹幾個基本概念：
使用者記憶體空間
首先記憶體空間分為
使用者記憶體空間
和
核心記憶體空間
， 使用者記憶體空間也稱為程序的地址空間，即對於每個使用者程序可見。使用者記憶體空間由低地址到高地址依次為：
可執行檔案程式碼的記憶體對映， 程式碼段（
text section
）
可執行檔案的已初始化全域性變數的記憶體對映，資料段（
data section
）
可執行檔案未初始化的全域性變數，bbs段的零頁（
bbs segment
）
記憶體堆區（
heap
）
共享記憶體段，C庫，或一些動態連結庫，記憶體對映檔案mmap將核心中的記憶體對映到使用者程序空間，減少了核心態向用戶態copy的消耗
記憶體棧區（
stack
） 高地址 => 低地址
核心記憶體空間
核心不能像使用者空間那樣奢侈的使用記憶體，核心空間透過對記憶體化分不同的區域來管理記憶體，通常劃分的區域為
ZONE_DMA
，
ZONE_NORMAL
，
ZONE_HIGHEM
， 在每個區域中又透過
slab
層來管理記憶體。核心管理記憶體的最小單位是物理頁，通常在32位體系結構中支援
4kb
的物理頁，核心直接管理物理頁，核心管理的記憶體是不會出現換出的情況的。
下圖可以看到核心分配記憶體主要有兩組介面函式，
kmalloc kfree
，
vmalloc vfree
kmalloc： 返回一個指向記憶體塊的指標，所分配的記憶體在物理上連續的
vmalloc：所分配的記憶體在虛擬地址空間上是連續的，並不會保證在物理RAM上是連續的。在效能上，vmalloc為了將物理上不連續的頁轉換成虛擬地址上連續的頁，必須專門建立頁表項，這就會導致TLB的快取失效，影響效能。因此只有在少數情況下才會使用vmalloc，例如將模組動態載入到核心中。
核心在管理棧空間時，使用了4kb或8kb比較小的棧來管理，並使用獨立的中斷棧對每個程序提供中斷處理程式的棧，提供中斷處理的效率。
總而言之：整體架構上，對於使用者記憶體空間linux使用我們所熟知的
虛擬記憶體管理
的方式對記憶體進行管理，而對於核心使用Slab或者vmalloc的方式對記憶體進行管理。在此之上，liunx統一使用
Buddy System
提供了更加靈活的記憶體管理方式。
2。 Slab & Buddy allocator
Slab 和 Buddy 是linux核心中基礎的記憶體分配器，相輔相成，各自負責不同的職責。
Slab allocator
： 具有相同大小的記憶體集合，透過一次性申請較大的記憶體空間，並將其等分為大小相同的塊，來避免記憶體碎片。
Buddy system
夥伴系統：即分配的每個物件都帶有一個
buddy
夥伴，當物件被釋放時，夥伴系統會將其記憶體進行合併。當有小物件需要分配記憶體時，夥伴系統將會把大記憶體塊分割成小記憶體塊分配出去。夥伴系統
buddy system
對記憶體塊的切分合並的思想，主要為了記憶體分配和歸還的複用（re-use）。
總而言之：
Slab
：申請的大的記憶體塊會被劃分成相等大小的塊，以連結串列的形式儲存維護，不會對記憶體塊進行合併和分隔，對於頻繁固定大小記憶體的分配和釋放十分高效。slab會以快取記憶體組的形式管理諸如
task struct
，
inode struct
這些固定大小而又頻繁使用的資料結構。
Buddy
： 按需分配不同大小的記憶體，分配和歸還涉及記憶體塊的合併和分割
linux核心記憶體管理提供了靈活的夥伴記憶體管理系統
Buddy allocator system
，在此之上並提供了不同的Slab管理不同的結構，例如：
task_struct
，
inode_struct
等等。
3。 Buddy allocator演算法
Buddy allocator
或
Buddy system
是一種經典記憶體分配演算法， 分離適配（
segregated fit
）， 其主要思想是將記憶體按2的冪次劃分，並搜尋其記憶體空間找到最佳適配的記憶體。搜尋複雜度為O（logN）。其缺點是如果要分配66單位的大小，則需要劃分出128大小的塊。Buddy allocator在linux系統中主要是為了分配動態大小的物件而設計的，對於固定大小且分配頻率高的物件使用slab分配器。
4。 page&zone關係
Slab
Buddy
為linux核心管理記憶體的方式，在其底層對於每個物理頁使用快取記憶體組
zone
和物理頁
page
的方式進行管理。下圖即為：
對於linux核心中每個物理頁，都由一個
page struct
用來維護。
page struct
維護了當前頁的一些資訊。並使用
mem_map
對程序的每個虛擬頁到物理頁做對映管理。mem_map稱為頁描述符陣列。
虛擬記憶體管理
記憶體定址
虛擬記憶體的實現中使用了分頁（paging）技術， 其依賴於硬體MMU的實現。首先虛擬地址被送到MMU中，MMU將虛擬地址轉化成物理地址，再送到記憶體匯流排中，在主從中獲取實際物理地址，或者在具體的硬體裝置中獲取實際物理地址。然後對物理地址進行相關的操作（讀寫）
MMU是一種硬體電路實現，包含主要兩個部件：分段部件，分頁部件。
分段機制：將虛擬地址（邏輯地址）轉化成線性地址
分頁機制：將線性地址轉化成物理地址
基址暫存器（
Page Table Base Register
） PTBR + 虛擬頁偏移（
Virtual Page Offset
） VPO + 虛擬頁號（
Virtual Page Number
） VPN
頁表
頁表（
page table
）： 是虛擬記憶體實現的作業系統中儲存物理地址到虛擬地址轉化的資料結構。其工作原理如下圖所示：虛擬地址首先被傳送到MMU中檢視TLB快取，如果快取命中（TLB hit）則返回物理地址，否則（TLB miss） MMU或作業系統會在頁表（page table）中查詢是否存在（a page walk），如果命中則返回物理地址，並寫回TLB快取。
注：雖然頁表屬於作業系統層面，MMU屬於硬體CPU層面，但是頁表與MMU不是相互獨立的，頁表與MMU是
協同工作
，圖中TLB部分即為MMU部分，即MMU可以透過頁表來查詢對應的物理地址，頁表的設計遵循計算機架構手冊（x86-64）。因此作業系統開發者需要保證頁表設計的正確性。
頁錶轉化失敗（
Translation failures
）主要有如下幾個原因，並觸發缺頁中斷（
page fault
）
虛擬地址不合法，程序訪問了不屬於自己的地址空間，陣列越界。即常說的段錯誤
segmentation fault
並觸發相應的錯誤處理程式
虛擬地址沒有沒有對該記憶體區域可讀，可寫，可執行的許可權，則缺頁處理程式會觸發一個
保護異常
虛擬地址對應的頁不在主存中，這種情況即該頁被換出（
page out
）儲存到輔存（
secondary store
， disk， swap partition）中。然後會將在輔存中的頁重新載入到記憶體中（
page in
），重新載入會使用memory-mapped files機制，並修改相應的頁表。
當發生頁錶轉化失敗的情況後，作業系統會分情況進行如下操作：
物理記憶體不滿： 這種情況下會獲取物理頁（free），並更新頁表和TLB，繼續轉化虛擬地址操作
物理記憶體滿： 這種情況下作業系統會選擇一個或多個物理頁換出到輔存中，頁表需要將被換出頁標記為
之前在主存
的狀態，並標記在輔存中的位置。相應的TLB也需要將換出（paged-out）的物理頁移除，繼續轉化虛擬地址操作
在進行頁換出（
page out
）操作時，需要用到
頁置換演算法(page replacement algorithm)
頁表的大小在32位作業系統4kb頁大小需要僅僅
4MB
去儲存。因為虛擬地址空間為
2^32
，每個頁的大小為4KB，即
2^12
，32位的作業系統，可以支援頁的個數為
2^32/2^12=2^20
， 32位虛擬地址需要4bytes來表示，所有需要頁表大小為
2^20*4=4MB
。
頁面置換演算法
頁置換演算法的主要作用就是發生缺頁中斷 （在虛擬地址對應的頁不在主存中這一種情況）時，作業系統必須選擇一個頁面將其換出，以便為即將調入的頁面騰出空間。
常見的有LRU（Least recently used），LFU（Least frequently used），NRU（Not recently used）等等。
總結
透過學習記憶體管理，可以很好的瞭解到程式在執行時的行為，以及作業系統的一些行為，可以使開發者寫程式碼時，更加遊刃有餘。
Reference
《linux核心設計與實現》（推薦）
《現代作業系統》（推薦）
《深入理解計算機系統》（推薦）
Buddy allocator， Slab allocator
overview linux memory management-slabs
gorman linux kernel tutorial（推薦）
slab allocation wiki
虛擬記憶體
stackoverflow linux-page-table-management-and-mmu
stackoverflow slab vs buddy
cool shell夥伴記憶體分配
wiki page table（推薦）
wiki page replacement algorithm
