Ⅰ 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、Slab）
由操作系統或系統管理員預先將內存劃分成若干個分區。在系統運行過程中，分區的邊界不再改變。分配時，找一個空閑且足夠大的分區。如沒有合適的分區：①讓申請者等待。②先換出某分區的內容，再將其分配出去。
為申請者分配指定的分區或任選一個分區。如果沒有空閑分區，可將一個分區的內容換出。可能需要重定位。
會出現內部碎片，無法滿足大內存的需求。
可減少內部碎片。減少對大內存需求的限制。
①固定分配：只分配某種尺寸的特定分區，如分區已被使用，申請者必須等待。
可能出現不公平等待：雖有更大尺寸的空閑分區，卻必須等待。
②最佳適應分配：分配能滿足需要的最小尺寸的空閑分區，只有當所有分區都已用完時，申請者才需要等待。靈活，但可能產生較大的內部碎片。
3、靜態分區：內存利用率低，產生內部碎片；尺寸和分區數量難以確定。
1、不預先確定分區的大小和數量，將分區工作推遲到實際分配內存時進行。 Lazy
初始情況下，把所有的空閑內存看成一個大分區。分配時，按申請的尺寸，找一塊足夠大的空閑內存分區，臨時從中劃出一塊構成新分區。新分區的尺寸與申請的大小相等，不會出現內部碎片。回收時，盡可能與鄰近的空閑分區合並。在內存緊缺時，可將某個選定的分區換出。
2、會產生外部碎片，如下圖（內部碎片是指 eg：要 1M，分了 8M，產生 7M 的碎片）：
移動內存中的進程，將碎片集中起來，重新構成大的內存塊。需要運行時的動態重定位，費時。
（1）緊縮方向：向一頭緊縮，向兩頭緊縮。
（2）緊縮時機：①在釋放分區時，如果不能與空閑分區合並，則立刻進行緊縮。
好處是不存在外部碎片，壞處是費時。
②在內存分配時，如果剩餘的空閑空間總量能滿足要求但沒有一個獨立的空閑塊能滿足要求，則進行緊縮。
好處是減少緊縮次數。Lazy。
①最先適應演算法（First fit）：從頭開始，在滿足要求的第一個空閑塊中分配。
分區集中在內存的前部，大內存留在後面，便於釋放後的合並。
②最佳適應演算法（Best fit）：遍歷空閑塊，在滿足要求的最小空閑塊中分配。
留下的碎片最小，基本無法再用，需要更頻繁地緊縮。
③下一個適應演算法（Next fit）：從上次分配的位置開始，在滿足要求的下一個空閑塊中分配。
對內存的使用較平均，不容易留下大的空閑塊。
④最差適應演算法（Worst Fit）：遍歷空閑塊，在滿足要求的最大空閑塊中分配。
留下的碎片較大，但不會剩餘大內存。
最先適應演算法較優，最佳適應演算法較差。
夥伴演算法：將動態分區的大小限定為 2^k 位元組，分割方式限定為平分，分區就會變得較為規整，分割與合並會更容易，可以減少一些外部碎片。平分後的兩塊互稱夥伴。
1、
分配時可能要多次平分，釋放時可能要多次合並。舉例：
記錄大小不同的空閑頁：
示意圖：
2、
夥伴演算法是靜態分區和動態分區法的折中，比靜態分區法靈活，不受分區尺寸及個數的限制；比動態分區法規范，不易出現外部碎片。會產生內部碎片，但比靜態分區的小。
linux、Windows、Ucore等都採用夥伴演算法管理物理內存。
一般情況下，將最小尺寸定為 2^12 位元組（1頁，4K=4096B），最大尺寸定為1024頁，11個隊列。
Linux、Windows、Ucore 等都將夥伴的最小尺寸限定為1頁。
ucore 用 page，在內存初始化函數 page_init 中為系統中的每個物理頁建立一個 page 結構。
頁塊（pageblock）是一組連續的物理頁。
5、
（1）判斷夥伴關系/尋找夥伴
最後兩行是指，B1和B2隻有第i位相反。
（2）判斷夥伴是否空閑：
ucore 用 free_area[ ]數組定義空閑頁塊隊列。
（3）確定夥伴是否在 order 隊列中：
7、
（1）解決內部碎片過大問題（eg：申請5頁，分配8頁，浪費3頁）：
ucore 在前部留下需要的頁數，釋放掉尾部各頁。每次釋放1頁，先劃分成頁塊，再逐個釋放。
（2） 解決切分與合並過於頻繁的問題：
用得較多的是單個頁。位於處理器Cache中頁稱為熱頁（hot page），其餘頁稱為冷頁（cold page）。處理器對熱頁的訪問速度要快於冷頁。
可建一個熱頁隊列（per_cpu_page），暫存剛釋放的單個物理頁，將合並工作向後推遲 Lazy。總是試圖從熱頁隊列中分配單個物理頁。分配與釋放都在熱頁隊列的隊頭進行。
（3）解決內存碎化(有足夠多的空閑頁，但是沒有大頁塊)問題：①將頁塊從一個物理位置移動到另一個物理位置，並保持移動前後邏輯地址不變（拷貝頁塊內容）；②邏輯內存管理器。
（4）滿足大內存的需求：
（5）物理內存空間都耗盡的情況：
在任何情況下，都應該預留一部分空閑的物理內存以備急需。定義兩條基準線low和high，當空閑內存量小於low時，應立刻開始回收物理內存，直到空閑內存量大於high。
（6）回收物理內存：
法一：啟動一個守護進程，專門用於回收物理內存。周期性啟動，也可被喚醒。
法二：申請者自己去回收內存。實際是由內存分配程序回收。回收的方法很多，如釋放緩沖區、頁面淘汰等。
1、
夥伴演算法最小分配內存為頁，對於更小的內存的管理 --> Slab 演算法
內和運行過程中經常使用小內存（小於1頁）eg：建立數據結構、緩沖區
內核對小內存的使用極為頻繁、種類繁多、時機和數量難以預估。所以難以預先分配，只能動態地創建和撤銷
2、
Slab 向夥伴演算法申請大頁塊（批發），將其劃分成小對象分配出去（零售）；將回收的小對象組合成大頁塊後還給夥伴演算法。
Slab 採用等尺寸靜態分區法，將頁塊預先劃分成一組大小相等的小塊，稱為內存對象。
具有相同屬性的多個Slab構成一個Cache，一個Cache管理一種類型（一類應該是指一個大小）的內存對象。當需要小內存時，從預建的Cache中申請內存對象，用完之後再將其還給Cache。當Cache中缺少對象時，追加新的Slab；當物理內存緊缺時，回收完全空閑的Slab。
Slab 演算法的管理結構：
① Cache 管理結構：管理Slab，包括Slab的創建和銷毀。
② Slab 管理結構：管理內存對象，包括小對象的分配與釋放。
（Cache結構和Slab結構合作，共同實現內存對象的管理）
3、
（1）描述各個內存對象的使用情況
可以用點陣圖標識空閑的內存對象。也可以將一個Slab中的空閑內存對象組織成隊列，並在slab結構中記錄隊列的隊頭。
早期的Linux在每個內存對象的尾部都加入一個指針，用該指針將空閑的內存對象串聯成一個真正的隊列。（對象變長、不規范，空間浪費）
改進：將指針集中在一個數組中，用數組內部的鏈表模擬內存對象隊列。
再改進：將數組中的指針換成對象序號，利用序號將空閑的內存對象串成隊列。序號數組是動態創建的。
序號數組可以位於 Slab 內部，也可以位於 Slab 外部
（2）一個Cache會管理多個Slab，可以將所有Slab放在一個隊列中。
Ucore為每個Cache准備了兩個slab結構隊列：全滿的和不滿的。Linux為每個Cache准備了三個slab結構隊列：部分滿的、完全滿的和完全空閑的。
Linux允許動態創建Cache，Ucore不許。Ucore預定了對象大小，分別是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。為每一種大小的對象預建了Cache。
（3）Slab是動態創建的，當Cache中沒有空閑的內存對象時，即為其創建一個新的Slab。
Slab所需要的內存來自夥伴演算法，大小是 2^page_order 個連續頁。
4、小對象的尺寸
如按處理器一級緩存中緩存行（Cache Line）的大小（16、32位元組）取齊，可使對象的開始位置都位於緩存行的邊界處。
在將頁塊劃分成內存對象的過程中，通常會剩餘一小部分空間，位於所有內存對象之外，稱為外部碎片。
Slab演算法選用碎片最小的實現方案。
5、
（1）對象分配 kmalloc
① 根據size確定一個Cache。
② 如果Cache的slabs_notfull為空，則為其創建一個新的Slab。
③ 選中slabs_notfull中第一個Slab，將隊頭的小對象分配出去，並調整隊列。
④ 對象的開始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;
（2）對象釋放 kfree
① 算出對象所在的頁號，找到它的 Page 結構。
② 根據 Page 找到所屬的 Cache 和 Slab。
③ 算出對象序號：objnr = (objp - slabp->s_mem) / cachep->objsize;
④將序號插入Slab的free隊列。
⑤整Slab所屬隊列。
Ⅱ 簡述內存管理中buddy演算法和slab機制的區別
1、Buddy演算法
linux對空閑內存空間管理採取buddy演算法，
Buddy演算法：
把內存中所有頁面按照2^n劃分，其中n=0~5，每個內存空間按1個頁面、2個頁面、4個頁面、8個頁面、16個頁面、32個頁面進行六次劃分。劃分後形成了大小不等的存儲塊，稱為頁面塊，簡稱頁塊，包含一個頁面的頁塊稱為1頁塊，包含2個頁面的稱為2頁塊，依次類推。
每種頁塊按前後順序兩兩結合成一對Buddy「夥伴」。系統按照Buddy關系把具有相同大小的空閑頁面塊組成頁塊組，即1頁塊組、2頁塊組……32頁塊組。 每個頁塊組用一個雙向循環鏈表進行管理，共有6個鏈表，分別為1、2、4、8、16、32頁塊鏈表。分別掛到free_area[] 數組上。
點陣圖數組
用於標記內存頁面使用情況，第0組每一位表示單個頁面使用情況，1表示使用，0表示空閑，第二組每一位表示比鄰的兩個頁面使用情況，一次類推。默認為10個數組，當一對Buddy的兩個頁面中有一個事空閑的，而另一個全部或部分被佔用時，該位置1.兩個頁面塊都是空閑，對應位置0.
內存分配和釋放過程
內存分配時，系統按照Buddy演算法，根據請求的頁面數在free_area[]對應的空閑頁塊組中搜索。 若請求頁面數不是2的整數次冪，則按照稍大於請求數的2的整數次冪的值搜索相應的頁面塊組。
當相應頁塊組中沒有可使用的空閑頁面塊時就查詢更大一些的頁塊組，在找到可用的頁塊後分配所需要的頁面。當某一空閑頁面被分配後，若仍有剩餘的空閑頁面，則根據剩餘頁面的大小把他們加入到相應頁面組中。
內存頁面釋放時，系統將其作為空閑頁面看待，檢查是否存在與這些頁面相鄰的其他空閑頁塊，若存在，則合為一個連續的空閑區按Buddy演算法重新分組。
2、Slab演算法
採用buddy演算法，解決了外碎片問題，這種方法適合大塊內存請求，不適合小內存區請求。如：幾十個或者幾百個位元組。Linux2.0採用傳統內存分區演算法，按幾何分布提供內存區大小，內存區以2的冪次方為單位。雖然減少了內碎片，但沒有顯著提高系統效率。
Linux2.4採用了slab分配器演算法，該演算法比傳統的分配器演算法有更好性能和內存利用率，最早在solaris2.4上使用。
Slab分配器思想
1）小對象的申請和釋放通過slab分配器來管理。
2）slab分配器有一組高速緩存，每個高速緩存保存同一種對象類型，如i節點緩存、PCB緩存等。
3）內核從它們各自的緩存種分配和釋放對象。
4）每種對象的緩存區由一連串slab構成，每個slab由一個或者多個連續的物理頁面組成。這些頁面種包含了已分配的緩存對象，也包含了空閑對象。