Linux 內存分配算法

內存管理算法——對討厭自己管理內存的人來說是天賜的禮物

1、內存碎片

1） 基本原理

產生原因：內存分配較小，并且分配的這些小的內存生存周期又較長，反復申請后將產生內存碎片的出現

優點：提高分配速度，便于內存管理，防止內存泄露

缺點：大量的內存碎片會使系統緩慢，內存使用率低，浪費大

2） 如何避免內存碎片

少用動態內存分配的函數（盡量使用棧空間）

分配內存和釋放的內存盡量在同一個函數中

盡量一次性申請較大的內存，而不要反復申請小內存

盡可能申請大塊的 2 的指數冪大小的內存空間

外部碎片避免——伙伴系統算法

內部碎片避免——slab 算法

自己進行內存管理工作，設計內存池

2、伙伴系統算法——組織結構

1） 概念

為內核提供了一種用于分配一組連續的頁而建立的一種高效的分配策略，并有效的解決了外碎片問題

分配的內存區是以頁框為基本單位的

2） 外部碎片

外部碎片指的是還沒有被分配出去（不屬于任何進程），但由于太小了無法分配給申請內存空間的新進程的內存空閑區域3） 組織結構

把所有的空閑頁分組為 11 個塊鏈表，每個塊鏈表分別包含大小為 1，2，4，8，16，32，64，128，256，512 和 1024 個連續頁框的頁塊。最大可以申請 1024 個連續頁，對應 4MB 大小的連續內存

3、伙伴系統算法——申請和回收

1） 申請算法

申請 2^i 個頁塊存儲空間，如果 2^i 對應的塊鏈表有空閑頁塊，則分配給應用

如果沒有空閑頁塊，則查找 2^（i 1） 對應的塊鏈表是否有空閑頁塊，如果有，則分配 2^i 塊鏈表節點給應用，另外 2^i 塊鏈表節點插入到 2^i 對應的塊鏈表中

如果 2^（i 1） 塊鏈表中沒有空閑頁塊，則重復步驟 2，直到找到有空閑頁塊的塊鏈表

如果仍然沒有，則返回內存分配失敗

2） 回收算法

釋放 2^i 個頁塊存儲空間，查找 2^i 個頁塊對應的塊鏈表，是否有與其物理地址是連續的頁塊，如果沒有，則無需合并

如果有，則合并成 2^（i 1）的頁塊，以此類推，繼續查找下一級塊鏈接，直到不能合并為止

3） 條件

兩個塊具有相同的大小

它們的物理地址是連續的

頁塊大小相同

4、如何分配 4M 以上內存？

1） 為何限制大塊內存分配

分配的內存越大， 失敗的可能性越大

大塊內存使用場景少

2） 內核中獲取 4M 以上大內存的方法

修改 MAX_ORDER， 重新編譯內核

內核啟動選型傳遞“mem=”參數， 如“mem=80M，預留部分內存；然后通過

request_mem_region 和 ioremap_nocache 將預留的內存映射到模塊中。需要修改內核啟動參數， 無需重新編譯內核。 但這種方法不支持 x86 架構， 只支持 ARM， PowerPC 等非 x86 架構

在 start_kernel 中 mem_init 函數之前調用 alloc_boot_mem 函數預分配大塊內存， 需要重新編譯內核

vmalloc 函數，內核代碼使用它來分配在虛擬內存中連續但在物理內存中不一定連續的內存

5、伙伴系統——反碎片機制

1） 不可移動頁

這些頁在內存中有固定的位置，不能夠移動，也不可回收

內核代碼段，數據段，內核 kmalloc（） 出來的內存，內核線程占用的內存等

2） 可回收頁

這些頁不能移動，但可以刪除。內核在回收頁占據了太多的內存時或者內存短缺時進行頁面回收3） 可移動頁

這些頁可以任意移動，用戶空間應用程序使用的頁都屬于該類別。它們是通過頁表映射的

當它們移動到新的位置，頁表項也會相應的更新

6、slab 算法——基本原理

1） 基本概念

Linux 所使用的 slab 分配器的基礎是 Jeff Bonwick 為 SunOS 操作系統首次引入的一種算法

它的基本思想是將內核中經常使用的對象放到高速緩存中，并且由系統保持為初始的可利用狀態。比如進程描述符，內核中會頻繁對此數據進行申請和釋放

2） 內部碎片

已經被分配出去的的內存空間大于請求所需的內存空間3） 基本目標

減少伙伴算法在分配小塊連續內存時所產生的內部碎片

將頻繁使用的對象緩存起來，減少分配、初始化和釋放對象的時間開銷

通過著色技術調整對象以更好的使用硬件高速緩存

7、slab 分配器的結構

由于對象是從 slab 中分配和釋放的，因此單個 slab 可以在 slab 列表之間進行移動

slabs_empty 列表中的 slab 是進行回收（reaping）的主要備選對象

slab 還支持通用對象的初始化，從而避免了為同一目而對一個對象重復進行初始化

8、slab 高速緩存

1） 普通高速緩存

slab 分配器所提供的小塊連續內存的分配是通過通用高速緩存實現的

通用高速緩存所提供的對象具有幾何分布的大小，范圍為 32 到 131072 字節。

內核中提供了 kmalloc（） 和 kfree（） 兩個接口分別進行內存的申請和釋放

2） 專用高速緩存

內核為專用高速緩存的申請和釋放提供了一套完整的接口，根據所傳入的參數為具體的對象分配 slab 緩存

kmem_cache_create（） 用于對一個指定的對象創建高速緩存。它從 cache_cache 普通高速緩存中為新的專有緩存分配一個高速緩存描述符，并把這個描述符插入到高速緩存描述符形成的 cache_chain 鏈表中

kmem_cache_alloc（） 在其參數所指定的高速緩存中分配一個 slab。相反， kmem_cache_free（） 在其參數所指定的高速緩存中釋放一個 slab

9、內核態內存池

1） 基本原理

先申請分配一定數量的、大小相等（一般情況下） 的內存塊留作備用

當有新的內存需求時，就從內存池中分出一部分內存塊，若內存塊不夠再繼續申請新的內存

這樣做的一個顯著優點是盡量避免了內存碎片，使得內存分配效率得到提升

2） 內核 API

mempool_create 創建內存池對象

mempool_alloc 分配函數獲得該對象

mempool_free 釋放一個對象

mempool_destroy 銷毀內存池

10、用戶態內存池

1） C++ 實例

11、DMA 內存

1） 什么是 DMA

直接內存訪問是一種硬件機制，它允許外圍設備和主內存之間直接傳輸它們的 I/O 數據，而不需要系統處理器的參與2） DMA 控制器的功能

能向 CPU 發出系統保持（HOLD）信號，提出總線接管請求

當 CPU 發出允許接管信號后，負責對總線的控制，進入 DMA 方式

能對存儲器尋址及能修改地址指針，實現對內存的讀寫操作

能決定本次 DMA 傳送的字節數，判斷 DMA 傳送是否結束

發出 DMA 結束信號，使 CPU 恢復正常工作狀態

2） DMA 信號

DREQ：DMA 請求信號。是外設向 DMA 控制器提出要求，DMA 操作的申請信號

DACK：DMA 響應信號。是 DMA 控制器向提出 DMA 請求的外設表示已收到請求和正進行處理的信號

HRQ：DMA 控制器向 CPU 發出的信號，要求接管總線的請求信號。

HLDA：CPU 向 DMA 控制器發出的信號，允許接管總線的應答信號：

責編AJX