Linux是如何避免記憶體碎片的？

在網上看到這個面試題，參考答案是這樣的：

1. 夥伴算法，用于管理實體記憶體，避免記憶體碎片;
2. 高速緩存Slab層用于管理核心配置設定記憶體，避免碎片。

故繼而去深入了解了一波，做了一個粗略的整理：

記憶體碎片問題

• 頻繁地請求和釋放不同大小的記憶體，必然導緻記憶體碎片問題的産生，結果就是當再次要求配置設定連續的記憶體時，即使整體記憶體是足夠的，也無法滿足連續記憶體的需求。該問題也稱之為外碎片(external fragmentation)。
• 解決方案：

• 避免外碎片的方法有兩種:

  1、利用分頁單元把一組非連續的空閑頁框映射到連續的線性位址

  2、開發一種适當的技術來記錄現存的空閑的連續頁框塊的情況，以盡量避免為滿足對小塊的請求而分割大的空閑快

• 第一種方案的意思是，我們使用位址轉換技術，把非連續的實體位址轉換成連續的線性位址。
• 第二種方案的意思是，開發一種特有的配置設定技術來記錄下來空閑記憶體的情況，進而解決記憶體碎片問題。
• Linux采用了第二種方案，因為在某些情況下，系統的确需要連續的實體位址（DMA處理器可以直接通路總線）。

這裡先對Linux記憶體管理做一個簡單介紹

• linux kernel 通過把整個實體記憶體劃分成以一個個page進行管理，管理器就是夥伴系統，它的最小配置設定單元就是page。但是對于小于page的記憶體配置設定，如果直接配置設定一個page，是一個很大的浪費。linux kernel 通過slab來實作對小于page大小的記憶體配置設定。slab把page按2的m次幂進行劃分一個個位元組塊，當kmalloc申請記憶體時，通過slab管理器傳回需要滿足申請大小的最小空閑記憶體塊。
• slub主要是針對slab的對象管理資料的優化版本，相比于slab，slub提供更小的管理成本開銷。而且slub對多核系統的支援也更加友好。細節這裡就不展開講。
• 是以kernel的記憶體管理是個2層分層系統，從下往上依次為：
• 第一層為全部實體記憶體：其管理器為夥伴系統，最小管理機關為page；
• 第二層為slab page：其管理器為slab/slub，最小管理機關為2的m次幂的位元組塊；

夥伴系統(buddy system)

• Linux采用著名的夥伴系統(buddy system)算法來解決外碎片問題。把所有的空閑頁框分組為11個塊連結清單，每個連結清單分别包含大小為1,2,4,8,16,32,64,128,256,512,1024個連續的頁框，對1024個頁框的最大請求對應着4MB大小的連續RAM（每頁大小為4KB），每個塊的第一個頁框的實體位址是該塊大小的整數倍，例如，大小為16個頁框的塊，其起始位址是16*2^12的倍數。

  我們通過一個例子來說明夥伴算法的工作原理，假設現在要請求一個256個頁框的塊（1MB），算法步驟如下：

  • 在256個頁框的連結清單中檢查是否有一個空閑快，如果沒有，查找下一個更大的塊，如果有，請求滿足。

  • 在512個頁框的連結清單中檢查是否有一個空閑塊，如果有，把512個頁框的空閑塊分為兩份，第一份用于滿足請求，第二份連結到256個頁框的連結清單中。如果沒有空閑塊，繼續尋找下一個更大的塊。

  下圖比較形象地描述了該過程。

  

  頁的請求

  以上過程的逆過程，就是頁框塊的釋放過程，也是該算法名字的由來，核心試圖把大小為B的一對空閑夥伴塊合并為一個2B的單獨塊，滿足以下條件的兩個塊稱之為夥伴：

  • 兩個塊具有相同的大小

  • 他們的實體位址是連續的

  第一塊的第一個頁框的實體位址是2 * B * 2^12

  該算法是遞歸的，如果它成功合并了B，就會試圖去合并2B，以再次試圖形成更大的塊。

高速緩存Slab層

• slab是Linux作業系統的一種記憶體配置設定機制。其工作是針對一些經常配置設定并釋放的對象，如程序描述符等，這些對象的大小一般比較小，如果直接采用夥伴系統來進行配置設定和釋放，不僅會造成大量的記憶體碎片，而且處理速度也太慢。
• 而slab配置設定器是基于對象進行管理的，相同類型的對象歸為一類(如程序描述符就是一類)，每當要申請這樣一個對象，slab配置設定器就從一個slab清單中配置設定一個這樣大小的單元出去，而當要釋放時，将其重新儲存在該清單中，而不是直接傳回給夥伴系統，進而避免這些内碎片。slab配置設定器并不丢棄已配置設定的對象，而是釋放并把它們儲存在記憶體中。當以後又要請求新的對象時，就可以從記憶體直接擷取而不用重複初始化。
• 對象高速緩存的組織如右下圖所示，高速緩存的記憶體區被劃分為多個slab，每個slab由一個或多個連續的頁框組成，這些頁框中既包含已配置設定的對象，也包含空閑的對象。
• 在cache和object中加入slab配置設定器，是在時間和空間上的折中方案。

  

• 另外為了解決多核和NUMA架構下效率問題，slab管理器kmem_cache又把slab page對象分為2層結構，從下往上依次為：
• 第一層為NUMA node下cpu共享page：管理器為kmem_cache_node，管理node下的slab對象，解決NUMA架構的記憶體通路效率問題。當本層的空閑page不足時，從夥伴系統申請空閑page；
• 第二層為per-cpu專屬page：管理器為kmem_cache_cpu，管理cpu專屬的slab對象，解決多核競争問題。當本層的空閑page不足時，從第一層申請空閑page；

  

slab配置設定算法

• slab配置設定算法采用cache 存儲核心對象。當建立cache 時，起初包括若幹标記為空閑的對象。對象的數量與slab的大小有關。開始，所有對象都标記為空閑。當需要核心資料結構的對象時，可以直接從cache 上直接擷取，并将對象初始化為使用。
• 下面考慮核心如何将slab配置設定給表示程序描述符的對象。在Linux系統中，程序描述符的類型是struct task_struct ，其大小約為1.7KB。當Linux 核心建立新任務時，它會從cache 中獲得struct task_struct 對象所需要的記憶體。Cache 上會有已配置設定好的并标記為空閑的struct task_struct 對象來滿足請求。

• Linux 的slab 可有三種狀态：

  滿的：slab 中的所有對象被标記為使用。

  空的：slab 中的所有對象被标記為空閑。

  部分：slab 中的對象有的被标記為使用，有的被标記為空閑。

• slab 配置設定器首先從部分空閑的slab 進行配置設定。如沒有，則從空的slab 進行配置設定。如沒有，則從實體連續頁上配置設定新的slab，并把它賦給一個cache ，然後再從新slab 配置設定空間。

資料整理自：

[1] https://baike.baidu.com/item/slab

[2] http://www.cnblogs.com/wahaha02/p/6616957.html

[3] https://www.jianshu.com/p/c4ef33bde4f5