2020-03-08 21:41:30 linux內核

夥伴系統

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分配器並不丟棄已分配的對象，而是釋放並把它們保存在內存中。當以後又要請求新的對象時，就可以從內存直接獲取而不用重複初始化。