當(dāng)在用戶模式下運(yùn)行進(jìn)程請(qǐng)求額外內(nèi)存時(shí)，從內(nèi)核維護(hù)的空閑頁幀列表上分配頁面。這個(gè)列表通常使用頁面置換算法來填充，如前所述，它很可能包含散布在物理內(nèi)存中的空閑頁面。也要記住，如果用戶進(jìn)程請(qǐng)求單個(gè)字節(jié)內(nèi)存，那么就會(huì)導(dǎo)致內(nèi)部碎片，因?yàn)檫M(jìn)程會(huì)得到整個(gè)幀。
用于分配內(nèi)核內(nèi)存的空閑內(nèi)存池通常不同于用于普通用戶模式進(jìn)程的列表。這有兩個(gè)主要原因：

內(nèi)核需要為不同大小的數(shù)據(jù)結(jié)構(gòu)請(qǐng)求內(nèi)存，其中有的小于一頁。因此，內(nèi)核應(yīng)保守地使用內(nèi)存，并努力最小化碎片浪費(fèi)。這一點(diǎn)非常重要，因?yàn)樵S多操作系統(tǒng)的內(nèi)核代碼或數(shù)據(jù)不受調(diào)頁系統(tǒng)的控制。

用戶模式進(jìn)程分配的頁面不必位于連續(xù)物理內(nèi)存。然而，有的硬件設(shè)備與物理內(nèi)存直接交互，即無法享有虛擬內(nèi)存接口帶來的便利，因而可能要求內(nèi)存常駐在連續(xù)物理內(nèi)存中。

下面討論兩個(gè)策略，以便管理用于內(nèi)核進(jìn)程的空閑內(nèi)存：“伙伴系統(tǒng)”和 slab 分配。

伙伴系統(tǒng)

伙伴系統(tǒng)從物理連續(xù)的大小固定的段上進(jìn)行分配。從這個(gè)段上分配內(nèi)存，采用 2 的冪分配器來滿足請(qǐng)求分配單元的大小為 2 的冪(4KB、 8KB、16KB 等)。請(qǐng)求單元的大小如不適當(dāng)，就圓整到下一個(gè)更大的 2 的冪。例如，如果請(qǐng)求大小為 11KB，則按 16KB 的段來請(qǐng)求。
讓我們考慮一個(gè)簡(jiǎn)單例子。假設(shè)內(nèi)存段的大小最初為 256KB，內(nèi)核請(qǐng)求 21KB 的內(nèi)存。最初，這個(gè)段分為兩個(gè)伙伴，稱為 AL 和 AR，每個(gè)的大小都為 128KB；這兩個(gè)伙伴之一進(jìn)一步分成兩個(gè) 64KB 的伙伴，即 BL 和 BR。然而，從 21KB 開始的下一個(gè)大的 2 的冪是 32KB，因此 BL 或 BR 再次劃分為兩個(gè) 32KB 的伙伴 CL 和 CR。因此，其中一個(gè) 32KB 的段可用于滿足 21KB 請(qǐng)求。這種方案如下圖所示，其中 CL 段是分配給 21KB 請(qǐng)求的。

伙伴系統(tǒng)分配

伙伴系統(tǒng)的一個(gè)優(yōu)點(diǎn)是：通過稱為合并的技術(shù)，可以將相鄰伙伴快速組合以形成更大分段。例如，在圖 1 中，當(dāng)內(nèi)核釋放已被分配的 CL 時(shí)，系統(tǒng)可以將 CL 和 CR 合并成 64KB 的段。段 BL 繼而可以與伙伴 BR 合并，以形成 128KB 段。最終，可以得到原來的 256KB 段。
伙伴系統(tǒng)的明顯缺點(diǎn)是：由于圓整到下一個(gè) 2 的冪，很可能造成分配段內(nèi)的碎片。例如，33KB 的內(nèi)存請(qǐng)求只能使用 64KB 段來滿足。事實(shí)上，我們不能保證因內(nèi)部碎片而浪費(fèi)的單元一定少于 50%。

slab分配

分配內(nèi)核內(nèi)存的第二種策略稱為slab分配。每個(gè)slab由一個(gè)或多個(gè)物理連續(xù)的頁面組成，每個(gè)cache由一個(gè)或多個(gè)slab組成，每個(gè)內(nèi)核數(shù)據(jù)結(jié)構(gòu)都有一個(gè)cache。
例如，用于表示進(jìn)程描述符、文件對(duì)象、信號(hào)量等的數(shù)據(jù)結(jié)構(gòu)都有各自單獨(dú)的cache。每個(gè)cache 含有內(nèi)核數(shù)據(jù)結(jié)構(gòu)的對(duì)象實(shí)例(稱為object)。例如，信號(hào)量cache有信號(hào)量對(duì)象，進(jìn)程描述符cache有進(jìn)程描述符對(duì)象，等等。

slab 分配

上圖顯示了slab、cache及object 三者之間的關(guān)系。該圖顯示了2個(gè)大小為3KB 的內(nèi)核對(duì)象和3個(gè)大小為7KB的對(duì)象，它們位于各自的cache中。slab分配算法采用 cache來存儲(chǔ)內(nèi)核對(duì)象。在創(chuàng)建 cache 時(shí)，若干起初標(biāo)記為free的對(duì)象被分配到 cache。cache內(nèi)的對(duì)象數(shù)量取決于相關(guān)slab的大小。例如，12KB slab(由3個(gè)連續(xù)的4KB頁面組成)可以存儲(chǔ)6個(gè)2KB對(duì)象。最初，cache內(nèi)的所有對(duì)象都標(biāo)記為空閑。當(dāng)需要內(nèi)核數(shù)據(jù)結(jié)構(gòu)的新對(duì)象時(shí)，分配器可以從cache上分配任何空閑對(duì)象以便滿足請(qǐng)求。從cache上分配的對(duì)象標(biāo)記為used(使用)。
讓我們考慮一個(gè)場(chǎng)景，這里內(nèi)核為表示進(jìn)程描述符的對(duì)象從slab分配器請(qǐng)求內(nèi)存。在 Linux 系統(tǒng)中，進(jìn)程描述符屬于 struct task_struct 類型，它需要大約1.7KB的內(nèi)存。當(dāng)Linux內(nèi)核創(chuàng)建一個(gè)新任務(wù)時(shí)，它從cache中請(qǐng)求 struct task_struct對(duì)象的必要內(nèi)存。cache 利用已經(jīng)在slab中分配的并且標(biāo)記為 free (空閑)的 struct task_struct對(duì)象來滿足請(qǐng)求。
在Linux中，slab可以處于三種可能狀態(tài)之一：

滿的：slab的所有對(duì)象標(biāo)記為使用。

空的：slab上的所有對(duì)象標(biāo)記為空閑。

部分：slab上的對(duì)象有的標(biāo)記為使用，有的標(biāo)記為空閑。

slab分配器首先嘗試在部分為空的slab中用空閑對(duì)象來滿足請(qǐng)求。如果不存在，則從空的slab 中分配空閑對(duì)象。如果沒有空的slab可用，則從連續(xù)物理頁面分配新的slab，并將其分配給cache；從這個(gè)slab上，再分配對(duì)象內(nèi)存。slab分配器提供兩個(gè)主要優(yōu)點(diǎn)：

沒有因碎片而引起內(nèi)存浪費(fèi)。碎片不是問題，因?yàn)槊總€(gè)內(nèi)核數(shù)據(jù)結(jié)構(gòu)都有關(guān)聯(lián)的cache，每個(gè) cache都由一個(gè)或多個(gè)slab組成，而slab按所表示對(duì)象的大小來分塊。因此，當(dāng)內(nèi)核請(qǐng)求對(duì)象內(nèi)存時(shí)，slab 分配器可以返回剛好表示對(duì)象的所需內(nèi)存。

可以快速滿足內(nèi)存請(qǐng)求。因此，當(dāng)對(duì)象頻繁地被分配和釋放時(shí)，如來自內(nèi)核請(qǐng)求的情況，slab 分配方案在管理內(nèi)存時(shí)特別有效。分配和釋放內(nèi)存的動(dòng)作可能是一個(gè)耗時(shí)過程。然而，由于對(duì)象已預(yù)先創(chuàng)建，因此可以從cache 中快速分配。再者，當(dāng)內(nèi)核用完對(duì)象并釋放它時(shí)，它被標(biāo)記為空閑并返回到cache，從而立即可用于后續(xù)的內(nèi)核請(qǐng)求。

slab 分配器首先出現(xiàn)在 Solaris 2.4 內(nèi)核中。由于通用性質(zhì)，Solaris 現(xiàn)在也將這種分配器用于某些用戶模式的內(nèi)存請(qǐng)求。最初，Linux使用的是伙伴系統(tǒng)；然而，從版本2.2開始，Linux 內(nèi)核采用 slab 分配器。
現(xiàn)在，最近發(fā)布的 Linux 也包括另外兩個(gè)內(nèi)核內(nèi)存分配器，SLOB和SLUB分配器(Linux 將 slab 實(shí)現(xiàn)稱為SLAB)。
簡(jiǎn)單塊列表(SLOB)分配器用于有限內(nèi)存的系統(tǒng)，例如嵌入式系統(tǒng)。SLOB工作采用3個(gè)對(duì)象列表：小(用于小于 256 字節(jié)的對(duì)象)、中(用于小于1024字節(jié)的對(duì)象)和大(用于小于頁面大小的對(duì)象)。內(nèi)存請(qǐng)求采用首先適應(yīng)策略，從適當(dāng)大小的列表上分配對(duì)象。
從版本2.6.24開始，SLUB分配器取代SLAB，成為Linux內(nèi)核的默認(rèn)分配器。SLUB通過減少SLAB 分配器所需的大量開銷，來解決slab分配的性能問題，一個(gè)改變是，在SLAB分配下每個(gè)slab 存儲(chǔ)的元數(shù)據(jù)，移到Linux內(nèi)核用于每個(gè)頁面的結(jié)構(gòu) page。此外，對(duì)于SLAB分配器，每個(gè)CPU都有隊(duì)列以維護(hù)每個(gè)cache內(nèi)的對(duì)象，SLUB會(huì)刪除這些隊(duì)列。
對(duì)于具有大量處理器的系統(tǒng)，分配給這些隊(duì)列的內(nèi)存量是很重要的。因此，隨著系統(tǒng)處理器數(shù)量的增加，SLUB性能也更好。

總結(jié)

以上是生活随笔為你收集整理的操作系统内存分配算法_操作系统基础45-伙伴系统和slab内存分配的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。