伙伴系統
Linux內核中采用了一種同時適用于32位和64位系統的記憶體分頁模型，對于32位系統來說，兩級頁表足夠用了，而在x86_64系統中，用到了四級頁表，四級頁表分別為：
- 頁全域目錄(Page Global Directory)
- 頁上級目錄(Page Upper Directory)
- 頁中間目錄(Page Middle Directory)
- 頁表(Page Table)
頁全域目錄包含若干頁上級目錄的地址，頁上級目錄又依次包含若干頁中間目錄的地址，而頁中間目錄又包含若干頁表的地址，每一個頁表項指向一個頁框，Linux中采用4KB大小的頁框作為標準的記憶體分配單元，
在實際應用中，經常需要分配一組連續的頁框，而頻繁地申請和釋放不同大小的連續頁框，必然導致在已分配頁框的記憶體塊中分散了許多小塊的空閑頁框，這樣，即使這些頁框是空閑的，其他需要分配連續頁框的應用也很難得到滿足，
為了避免出現這種情況，Linux內核中引入了伙伴系統演算法(buddy system)，把所有的空閑頁框分組為11個塊鏈表，每個塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁框塊，最大可以申請1024個連續頁框，對應4MB大小的連續記憶體，每個頁框塊的第一個頁框的物理地址是該塊大小的整數倍，
假設要申請一個256個頁框的塊，先從256個頁框的鏈表中查找空閑塊，如果沒有，就去512個頁框的鏈表中找，找到了則將頁框塊分為2個256個頁框的塊，一個分配給應用，另外一個移到256個頁框的鏈表中，如果512個頁框的鏈表中仍沒有空閑塊，繼續向1024個頁框的鏈表查找，如果仍然沒有，則回傳錯誤，
頁框塊在釋放時，會主動將兩個連續的頁框塊合并為一個較大的頁框塊，
Buddy演算法的優缺點：
1）盡管伙伴記憶體演算法在記憶體碎片問題上已經做的相當出色，但是該演算法中，一個很小的塊往往會阻礙一個大塊的合并，一個系統中，對記憶體塊的分配，大小是隨機的，一片記憶體中僅一個小的記憶體塊沒有釋放，旁邊兩個大的就不能合并，
2）演算法中有一定的浪費現象，伙伴演算法是按2的冪次方大小進行分配記憶體塊，當然這樣做是有原因的，即為了避免把大的記憶體塊拆的太碎，更重要的是使分配和釋放程序迅速，但是他也帶來了不利的一面，如果所需記憶體大小不是2的冪次方，就會有部分頁面浪費，有時還很嚴重，比如原來是1024個塊，申請了16個塊，再申請600個塊就申請不到了，因為已經被分割了，
3）另外拆分和合并涉及到 較多的鏈表和位圖操作，開銷還是比較大的，
Buddy（伙伴的定義）：
這里給出伙伴的概念，滿足以下三個條件的稱為伙伴：
1）兩個塊大小相同；
2）兩個塊地址連續；
3）兩個塊必須是同一個大塊中分離出來的；
Buddy演算法的分配原理：
假如系統需要4(22)個頁面大小的記憶體塊，該演算法就到free_area[2]中查找，如果鏈表中有空閑塊，就直接從中摘下并分配出去，如果沒有，演算法將順著陣列向上查找free_area[3],如果free_area[3]中有空閑塊，則將其從鏈表中摘下，分成等大小的兩部分，前四個頁面作為一個塊插入free_area[2]，后4個頁面分配出去，free_area[3]中也沒有，就再向上查找，如果free_area[4]中有，就將這16(2222)個頁面等分成兩份，前一半掛如free_area[3]的鏈表頭部，后一半的8個頁等分成兩等分，前一半掛free_area[2]的鏈表中，后一半分配出去，假如free_area[4]也沒有，則重復上面的程序，知道到達free_area陣列的最后，如果還沒有則放棄分配，
Buddy演算法的釋放原理：
記憶體的釋放是分配的逆程序，也可以看作是伙伴的合并程序，當釋放一個塊時，先在其對應的鏈表中考查是否有伙伴存在，如果沒有伙伴塊，就直接把要釋放的塊掛入鏈表頭；如果有，則從鏈表中摘下伙伴，合并成一個大塊，然后繼續考察合并后的塊在更大一級鏈表中是否有伙伴存在，直到不能合并或者已經合并到了最大的塊(222222222個頁面)，
slab機制
slab是Linux作業系統的一種記憶體分配機制，其作業是針對一些經常分配并釋放的物件，如行程描述符等，這些物件的大小一般比較小，如果直接采用伙伴系統來進行分配和釋放，不僅會造成大量的內碎片，而且處理速度也太慢，而slab分配器是基于物件進行管理的，相同型別的物件歸為一類(如行程描述符就是一類)，每當要申請這樣一個物件，slab分配器就從一個slab串列中分配一個這樣大小的單元出去，而當要釋放時，將其重新保存在該串列中，而不是直接回傳給伙伴系統，從而避免這些內碎片，slab分配器并不丟棄已分配的物件，而是釋放并把它們保存在記憶體中，當以后又要請求新的物件時，就可以從記憶體直接獲取而不用重復初始化，
Linux 的slab 可有三種狀態：
- 滿的：slab 中的所有物件被標記為使用，
- 空的：slab 中的所有物件被標記為空閑，
- 部分：slab 中的物件有的被標記為使用，有的被標記為空閑，
slab 分配器首先從部分空閑的slab 進行分配，如沒有，則從空的slab 進行分配，如沒有，則從物理連續頁上分配新的slab，并把它賦給一個cache ，然后再從新slab 分配空間，
與傳統的記憶體管理模式相比， slab 快取分配器提供了很多優點，
1、內核通常依賴于對小物件的分配，它們會在系統生命周期內進行無數次分配，
2、slab 快取分配器通過對類似大小的物件進行快取而提供這種功能，從而避免了常見的碎片問題，
3、slab 分配器還支持通用物件的初始化，從而避免了為同一目的而對一個物件重復進行初始化，
4、slab 分配器還可以支持硬體快取對齊和著色，這允許不同快取中的物件占用相同的快取行，從而提高快取的利用率并獲得更好的性能，
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/9808.html
標籤：嵌入式
上一篇：痞子衡嵌入式：恩智浦i.MX RTxxx系列MCU啟動那些事（6.1）- FlexSPI NOR連接方式大全(RT600)