Linux操作系統(tǒng)知識(shí)講解：走進(jìn)Linux 內(nèi)存分配算法

Linux 內(nèi)存分配算法

內(nèi)存管理算法——對(duì)討厭自己管理內(nèi)存的人來說是天賜的禮物

1、內(nèi)存碎片

1） 基本原理

產(chǎn)生原因：內(nèi)存分配較小，并且分配的這些小的內(nèi)存生存周期又較長(zhǎng)，反復(fù)申請(qǐng)后將產(chǎn)生內(nèi)存碎片的出現(xiàn)

優(yōu)點(diǎn)：提高分配速度，便于內(nèi)存管理，防止內(nèi)存泄露

缺點(diǎn)：大量的內(nèi)存碎片會(huì)使系統(tǒng)緩慢，內(nèi)存使用率低，浪費(fèi)大

2） 如何避免內(nèi)存碎片

少用動(dòng)態(tài)內(nèi)存分配的函數(shù)（盡量使用?？臻g）

分配內(nèi)存和釋放的內(nèi)存盡量在同一個(gè)函數(shù)中

盡量一次性申請(qǐng)較大的內(nèi)存，而不要反復(fù)申請(qǐng)小內(nèi)存

盡可能申請(qǐng)大塊的 2 的指數(shù)冪大小的內(nèi)存空間

外部碎片避免——伙伴系統(tǒng)算法

內(nèi)部碎片避免——slab 算法

自己進(jìn)行內(nèi)存管理工作，設(shè)計(jì)內(nèi)存池

2、伙伴系統(tǒng)算法——組織結(jié)構(gòu)

1） 概念

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

分配的內(nèi)存區(qū)是以頁框?yàn)榛締挝坏?/p>

2） 外部碎片

外部碎片指的是還沒有被分配出去（不屬于任何進(jìn)程），但由于太小了無法分配給申請(qǐng)內(nèi)存空間的新進(jìn)程的內(nèi)存空閑區(qū)域3） 組織結(jié)構(gòu)

把所有的空閑頁分組為 11 個(gè)塊鏈表，每個(gè)塊鏈表分別包含大小為 1，2，4，8，16，32，64，128，256，512 和 1024 個(gè)連續(xù)頁框的頁塊。最大可以申請(qǐng) 1024 個(gè)連續(xù)頁，對(duì)應(yīng) 4MB 大小的連續(xù)內(nèi)存

3、伙伴系統(tǒng)算法——申請(qǐng)和回收

1） 申請(qǐng)算法

申請(qǐng) 2^i 個(gè)頁塊存儲(chǔ)空間，如果 2^i 對(duì)應(yīng)的塊鏈表有空閑頁塊，則分配給應(yīng)用

如果沒有空閑頁塊，則查找 2^（i 1） 對(duì)應(yīng)的塊鏈表是否有空閑頁塊，如果有，則分配 2^i 塊鏈表節(jié)點(diǎn)給應(yīng)用，另外 2^i 塊鏈表節(jié)點(diǎn)插入到 2^i 對(duì)應(yīng)的塊鏈表中

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

如果仍然沒有，則返回內(nèi)存分配失敗

2） 回收算法

釋放 2^i 個(gè)頁塊存儲(chǔ)空間，查找 2^i 個(gè)頁塊對(duì)應(yīng)的塊鏈表，是否有與其物理地址是連續(xù)的頁塊，如果沒有，則無需合并

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

3） 條件

兩個(gè)塊具有相同的大小

它們的物理地址是連續(xù)的

頁塊大小相同

4、如何分配 4M 以上內(nèi)存？

1） 為何限制大塊內(nèi)存分配

分配的內(nèi)存越大， 失敗的可能性越大

大塊內(nèi)存使用場(chǎng)景少

2） 內(nèi)核中獲取 4M 以上大內(nèi)存的方法

修改 MAX_ORDER， 重新編譯內(nèi)核

內(nèi)核啟動(dòng)選型傳遞“mem=”參數(shù)， 如“mem=80M，預(yù)留部分內(nèi)存；然后通過

request_mem_region 和 ioremap_nocache 將預(yù)留的內(nèi)存映射到模塊中。需要修改內(nèi)核啟動(dòng)參數(shù)， 無需重新編譯內(nèi)核。 但這種方法不支持 x86 架構(gòu)， 只支持 ARM， PowerPC 等非 x86 架構(gòu)

在 start_kernel 中 mem_init 函數(shù)之前調(diào)用 alloc_boot_mem 函數(shù)預(yù)分配大塊內(nèi)存， 需要重新編譯內(nèi)核

vmalloc 函數(shù)，內(nèi)核代碼使用它來分配在虛擬內(nèi)存中連續(xù)但在物理內(nèi)存中不一定連續(xù)的內(nèi)存

5、伙伴系統(tǒng)——反碎片機(jī)制

1） 不可移動(dòng)頁

這些頁在內(nèi)存中有固定的位置，不能夠移動(dòng)，也不可回收

內(nèi)核代碼段，數(shù)據(jù)段，內(nèi)核 kmalloc（） 出來的內(nèi)存，內(nèi)核線程占用的內(nèi)存等

2） 可回收頁

這些頁不能移動(dòng)，但可以刪除。內(nèi)核在回收頁占據(jù)了太多的內(nèi)存時(shí)或者內(nèi)存短缺時(shí)進(jìn)行頁面回收3） 可移動(dòng)頁

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

當(dāng)它們移動(dòng)到新的位置，頁表項(xiàng)也會(huì)相應(yīng)的更新

6、slab 算法——基本原理

1） 基本概念

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

它的基本思想是將內(nèi)核中經(jīng)常使用的對(duì)象放到高速緩存中，并且由系統(tǒng)保持為初始的可利用狀態(tài)。比如進(jìn)程描述符，內(nèi)核中會(huì)頻繁對(duì)此數(shù)據(jù)進(jìn)行申請(qǐng)和釋放

2） 內(nèi)部碎片

已經(jīng)被分配出去的的內(nèi)存空間大于請(qǐng)求所需的內(nèi)存空間3） 基本目標(biāo)

減少伙伴算法在分配小塊連續(xù)內(nèi)存時(shí)所產(chǎn)生的內(nèi)部碎片

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

通過著色技術(shù)調(diào)整對(duì)象以更好的使用硬件高速緩存

7、slab 分配器的結(jié)構(gòu)

由于對(duì)象是從 slab 中分配和釋放的，因此單個(gè) slab 可以在 slab 列表之間進(jìn)行移動(dòng)

slabs_empty 列表中的 slab 是進(jìn)行回收（reaping）的主要備選對(duì)象

slab 還支持通用對(duì)象的初始化，從而避免了為同一目而對(duì)一個(gè)對(duì)象重復(fù)進(jìn)行初始化

8、slab 高速緩存

1） 普通高速緩存

slab 分配器所提供的小塊連續(xù)內(nèi)存的分配是通過通用高速緩存實(shí)現(xiàn)的

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

內(nèi)核中提供了 kmalloc（） 和 kfree（） 兩個(gè)接口分別進(jìn)行內(nèi)存的申請(qǐng)和釋放

2） 專用高速緩存

內(nèi)核為專用高速緩存的申請(qǐng)和釋放提供了一套完整的接口，根據(jù)所傳入的參數(shù)為具體的對(duì)象分配 slab 緩存

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

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

9、內(nèi)核態(tài)內(nèi)存池

1） 基本原理

先申請(qǐng)分配一定數(shù)量的、大小相等（一般情況下） 的內(nèi)存塊留作備用

當(dāng)有新的內(nèi)存需求時(shí)，就從內(nèi)存池中分出一部分內(nèi)存塊，若內(nèi)存塊不夠再繼續(xù)申請(qǐng)新的內(nèi)存

這樣做的一個(gè)顯著優(yōu)點(diǎn)是盡量避免了內(nèi)存碎片，使得內(nèi)存分配效率得到提升

2） 內(nèi)核 API

mempool_create 創(chuàng)建內(nèi)存池對(duì)象

mempool_alloc 分配函數(shù)獲得該對(duì)象

mempool_free 釋放一個(gè)對(duì)象

mempool_destroy 銷毀內(nèi)存池

10、用戶態(tài)內(nèi)存池

1） C++ 實(shí)例

11、DMA 內(nèi)存

1） 什么是 DMA

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

能向 CPU 發(fā)出系統(tǒng)保持（HOLD）信號(hào)，提出總線接管請(qǐng)求

當(dāng) CPU 發(fā)出允許接管信號(hào)后，負(fù)責(zé)對(duì)總線的控制，進(jìn)入 DMA 方式

能對(duì)存儲(chǔ)器尋址及能修改地址指針，實(shí)現(xiàn)對(duì)內(nèi)存的讀寫操作

能決定本次 DMA 傳送的字節(jié)數(shù)，判斷 DMA 傳送是否結(jié)束

發(fā)出 DMA 結(jié)束信號(hào)，使 CPU 恢復(fù)正常工作狀態(tài)

2） DMA 信號(hào)

DREQ：DMA 請(qǐng)求信號(hào)。是外設(shè)向 DMA 控制器提出要求，DMA 操作的申請(qǐng)信號(hào)

DACK：DMA 響應(yīng)信號(hào)。是 DMA 控制器向提出 DMA 請(qǐng)求的外設(shè)表示已收到請(qǐng)求和正進(jìn)行處理的信號(hào)

HRQ：DMA 控制器向 CPU 發(fā)出的信號(hào)，要求接管總線的請(qǐng)求信號(hào)。

HLDA：CPU 向 DMA 控制器發(fā)出的信號(hào)，允許接管總線的應(yīng)答信號(hào)：

責(zé)編AJX