slab管理演算法內存碎片

1. 夥伴演算法和slab演算法

內存碎片太小和管理內存碎片的效率問題

原因：分配內存時，不能將相鄰內存合並

解決辦法：

如果申請的內存大小為n，則向上取整為2的冪次數，定位到響應組，到組中(鏈表上)找空閑塊分配出去；若沒有空閑塊，則到上一組找，直到找到為止，並將剩餘的內存放到下面適當的組中。

用完內存需要歸還，根據實際內存塊大小向上取整為2的冪次數，歸入鏈表。

註：夥伴演算法使用點陣圖標記內存塊的使用情況

slab以內存池為思想，解決內部碎片問題，專門解決小內存問題。

2. linux 內存管理（buddy 和 slab）

Linux 在拿到一大塊內存後（譬如是64MB內存），先將其看作是好多個連續排列的 4MB 內存。
那麼如果程序請求1MB的內存，那麼內存分配操作邏輯如下：

這個演算法就是所謂的 binary buddy 分配演算法。
在 Linux 中，這個二分法最小分割到 4096 位元組，也就是一個頁的大小。
因此總共有 11 種大小，分別為 4KB，8KB，……4MB。
其中 4KB 為 order 0，4MB 為 order 10.
我們稱其 max order 為 12，有些資料會提到這個概念。

以上這些信息可以在 /proc/buddyinfo 上查看，其格式大概是這樣：

buddy 在上面這種情況下，有些被分為小塊內存，那麼就會存在內存碎片的問題。
/proc/pagetypeinfo

以上 buddy 管理的是不小於4K 的內存分配，slab 則是管理小於4KB 的內存對象。

3. 外碎片與內碎片

內部碎片
是處於操作系統分配的用於裝載某一進程的內存區域內部的存儲塊。佔有這些區域或頁面的進程並不使用這個存儲塊。而在進程佔有這塊存儲塊時，系統無法利用它。直到進程釋放它，或進程結束時，系統才有可能利用這個存儲塊。
外部碎片
外部碎片指的是還沒有被分配出去（不屬於任何進程），但由於太小了無法分配給申請內存空間的新進程的內存空閑區域。
外部碎片是處於任何兩個已分配區域或頁面之間的空閑存儲塊。這些存儲塊的總和可以滿足當前申請的長度要求，但是由於它們的地址不連續或其他原因，使得系統無法滿足當前申請。

內部碎片的產生 ：因為所有的內存分配必須起始於可被 4、8 或 16 整除（視處理器體系結構而定）的地址或者因為MMU的分頁機制的限制，決定內存分配演算法僅能把預定大小的內存塊分配給客戶。假設當某個客戶請求一個 43 位元組的內存塊時，因為沒有適合大小的內存，所以它可能會獲得 44位元組、48位元組等稍大一點的位元組，因此由所需大小四捨五入而產生的多餘空間就叫內部碎片。

外部碎片的產生 ： 頻繁的分配與回收物理頁面會導致大量的、連續且小的頁面塊夾雜在已分配的頁面中間，就會產生外部碎片。假設有一塊一共有100個單位的連續空閑內存空間，范圍是0 _{99。如果你從中申請一塊內存，如10個單位，那麼申請出來的內存塊就為0} 9區間。這時候你繼續申請一塊內存，比如說5個單位大，第二塊得到的內存塊就應該為10 _{14區間。如果你把第一塊內存塊釋放，然後再申請一塊大於10個單位的內存塊，比如說20個單位。因為剛被釋放的內存塊不能滿足新的請求，所以只能從15開始分配出20個單位的內存塊。現在整個內存空間的狀態是0} 9空閑，10 _{14被佔用，15} 24被佔用，25 _{99空閑。其中0} 9就是一個內存碎片了。如果10 _{14一直被佔用，而以後申請的空間都大於10個單位，那麼0} 9就永遠用不上了，變成外部碎片。
 
夥伴演算法(buddy)用來解決外碎片
slab演算法用來解決內碎片

4. linux中使用了什麼內存管理方法,為什麼

「事實勝於雄辯」，我們用一個小例子（原形取自《User-Level Memory Management》）來展示上面所講的各種內存區的差別與位置。

進程的地址空間對應的描述結構是「內存描述符結構」,它表示進程的全部地址空間，——包含了和進程地址空間有關的全部信息，其中當然包含進程的內存區域。

進程內存的分配與回收

創建進程fork()、程序載入execve()、映射文件mmap()、動態內存分配malloc()/brk()等進程相關操作都需要分配內存給進程。不過這時進程申請和獲得的還不是實際內存，而是虛擬內存，准確的說是「內存區域」。進程對內存區域的分配最終都會歸結到do_mmap（）函數上來（brk調用被單獨以系統調用實現，不用do_mmap()），

內核使用do_mmap()函數創建一個新的線性地址區間。但是說該函數創建了一個新VMA並不非常准確，因為如果創建的地址區間和一個已經存在的地址區間相鄰，並且它們具有相同的訪問許可權的話，那麼兩個區間將合並為一個。如果不能合並，那麼就確實需要創建一個新的VMA了。但無論哪種情況，do_mmap()函數都會將一個地址區間加入到進程的地址空間中－－無論是擴展已存在的內存區域還是創建一個新的區域。

同樣，釋放一個內存區域應使用函數do_ummap()，它會銷毀對應的內存區域。

如何由虛變實！

從上面已經看到進程所能直接操作的地址都為虛擬地址。當進程需要內存時，從內核獲得的僅僅是虛擬的內存區域，而不是實際的物理地址，進程並沒有獲得物理內存（物理頁面——頁的概念請大家參考硬體基礎一章），獲得的僅僅是對一個新的線性地址區間的使用權。實際的物理內存只有當進程真的去訪問新獲取的虛擬地址時，才會由「請求頁機制」產生「缺頁」異常，從而進入分配實際頁面的常式。

該異常是虛擬內存機制賴以存在的基本保證——它會告訴內核去真正為進程分配物理頁，並建立對應的頁表，這之後虛擬地址才實實在在地映射到了系統的物理內存上。（當然，如果頁被換出到磁碟，也會產生缺頁異常，不過這時不用再建立頁表了）

這種請求頁機制把頁面的分配推遲到不能再推遲為止，並不急於把所有的事情都一次做完（這種思想有點像設計模式中的代理模式（proxy））。之所以能這么做是利用了內存訪問的「局部性原理」，請求頁帶來的好處是節約了空閑內存，提高了系統的吞吐率。要想更清楚地了解請求頁機制，可以看看《深入理解linux內核》一書。

這里我們需要說明在內存區域結構上的nopage操作。當訪問的進程虛擬內存並未真正分配頁面時，該操作便被調用來分配實際的物理頁，並為該頁建立頁表項。在最後的例子中我們會演示如何使用該方法。

系統物理內存管理

雖然應用程序操作的對象是映射到物理內存之上的虛擬內存，但是處理器直接操作的卻是物理內存。所以當應用程序訪問一個虛擬地址時，首先必須將虛擬地址轉化成物理地址，然後處理器才能解析地址訪問請求。地址的轉換工作需要通過查詢頁表才能完成，概括地講，地址轉換需要將虛擬地址分段，使每段虛地址都作為一個索引指向頁表，而頁表項則指向下一級別的頁表或者指向最終的物理頁面。

每個進程都有自己的頁表。進程描述符的pgd域指向的就是進程的頁全局目錄。下面我們借用《linux設備驅動程序》中的一幅圖大致看看進程地址空間到物理頁之間的轉換關系。

上面的過程說起來簡單，做起來難呀。因為在虛擬地址映射到頁之前必須先分配物理頁——也就是說必須先從內核中獲取空閑頁，並建立頁表。下面我們介紹一下內核管理物理內存的機制。

物理內存管理（頁管理）

Linux內核管理物理內存是通過分頁機制實現的，它將整個內存劃分成無數個4k（在i386體系結構中）大小的頁，從而分配和回收內存的基本單位便是內存頁了。利用分頁管理有助於靈活分配內存地址，因為分配時不必要求必須有大塊的連續內存[3]，系統可以東一頁、西一頁的湊出所需要的內存供進程使用。雖然如此，但是實際上系統使用內存時還是傾向於分配連續的內存塊，因為分配連續內存時，頁表不需要更改，因此能降低TLB的刷新率（頻繁刷新會在很大程度上降低訪問速度）。

鑒於上述需求，內核分配物理頁面時為了盡量減少不連續情況，採用了「夥伴」關系來管理空閑頁面。夥伴關系分配演算法大家應該不陌生——幾乎所有操作系統方面的書都會提到,我們不去詳細說它了，如果不明白可以參看有關資料。這里只需要大家明白Linux中空閑頁面的組織和管理利用了夥伴關系，因此空閑頁面分配時也需要遵循夥伴關系，最小單位只能是2的冪倍頁面大小。內核中分配空閑頁面的基本函數是get_free_page/get_free_pages，它們或是分配單頁或是分配指定的頁面（2、4、8…512頁）。

注意：get_free_page是在內核中分配內存，不同於malloc在用戶空間中分配，malloc利用堆動態分配，實際上是調用brk()系統調用，該調用的作用是擴大或縮小進程堆空間（它會修改進程的brk域）。如果現有的內存區域不夠容納堆空間，則會以頁面大小的倍數為單位，擴張或收縮對應的內存區域，但brk值並非以頁面大小為倍數修改，而是按實際請求修改。因此Malloc在用戶空間分配內存可以以位元組為單位分配,但內核在內部仍然會是以頁為單位分配的。

另外,需要提及的是，物理頁在系統中由頁結構structpage描述，系統中所有的頁面都存儲在數組mem_map[]中，可以通過該數組找到系統中的每一頁（空閑或非空閑）。而其中的空閑頁面則可由上述提到的以夥伴關系組織的空閑頁鏈表（free_area[MAX_ORDER]）來索引。

內核內存使用

Slab

所謂尺有所長，寸有所短。以頁為最小單位分配內存對於內核管理系統中的物理內存來說的確比較方便，但內核自身最常使用的內存卻往往是很小（遠遠小於一頁）的內存塊——比如存放文件描述符、進程描述符、虛擬內存區域描述符等行為所需的內存都不足一頁。這些用來存放描述符的內存相比頁面而言，就好比是麵包屑與麵包。一個整頁中可以聚集多個這些小塊內存；而且這些小塊內存塊也和麵包屑一樣頻繁地生成/銷毀。

為了滿足內核對這種小內存塊的需要，Linux系統採用了一種被稱為slab分配器的技術。Slab分配器的實現相當復雜，但原理不難，其核心思想就是「存儲池[4]」的運用。內存片段（小塊內存）被看作對象，當被使用完後，並不直接釋放而是被緩存到「存儲池」里，留做下次使用，這無疑避免了頻繁創建與銷毀對象所帶來的額外負載。

Slab技術不但避免了內存內部分片（下文將解釋）帶來的不便（引入Slab分配器的主要目的是為了減少對夥伴系統分配演算法的調用次數——頻繁分配和回收必然會導致內存碎片——難以找到大塊連續的可用內存），而且可以很好地利用硬體緩存提高訪問速度。

Slab並非是脫離夥伴關系而獨立存在的一種內存分配方式，slab仍然是建立在頁面基礎之上，換句話說，Slab將頁面（來自於夥伴關系管理的空閑頁面鏈表）撕碎成眾多小內存塊以供分配，slab中的對象分配和銷毀使用kmem_cache_alloc與kmem_cache_free。

Kmalloc

Slab分配器不僅僅只用來存放內核專用的結構體，它還被用來處理內核對小塊內存的請求。當然鑒於Slab分配器的特點，一般來說內核程序中對小於一頁的小塊內存的請求才通過Slab分配器提供的介面Kmalloc來完成（雖然它可分配32到131072位元組的內存）。從內核內存分配的角度來講，kmalloc可被看成是get_free_page（s）的一個有效補充，內存分配粒度更靈活了。

有興趣的話，可以到/proc/slabinfo中找到內核執行現場使用的各種slab信息統計，其中你會看到系統中所有slab的使用信息。從信息中可以看到系統中除了專用結構體使用的slab外，還存在大量為Kmalloc而准備的Slab（其中有些為dma准備的）。

內核非連續內存分配（Vmalloc）

夥伴關系也好、slab技術也好，從內存管理理論角度而言目的基本是一致的，它們都是為了防止「分片」，不過分片又分為外部分片和內部分片之說，所謂內部分片是說系統為了滿足一小段內存區（連續）的需要，不得不分配了一大區域連續內存給它，從而造成了空間浪費；外部分片是指系統雖有足夠的內存，但卻是分散的碎片，無法滿足對大塊「連續內存」的需求。無論何種分片都是系統有效利用內存的障礙。slab分配器使得一個頁面內包含的眾多小塊內存可獨立被分配使用，避免了內部分片，節約了空閑內存。夥伴關系把內存塊按大小分組管理，一定程度上減輕了外部分片的危害，因為頁框分配不在盲目，而是按照大小依次有序進行，不過夥伴關系只是減輕了外部分片，但並未徹底消除。你自己比劃一下多次分配頁面後，空閑內存的剩餘情況吧。

所以避免外部分片的最終思路還是落到了如何利用不連續的內存塊組合成「看起來很大的內存塊」——這里的情況很類似於用戶空間分配虛擬內存，內存邏輯上連續，其實映射到並不一定連續的物理內存上。Linux內核借用了這個技術，允許內核程序在內核地址空間中分配虛擬地址，同樣也利用頁表（內核頁表）將虛擬地址映射到分散的內存頁上。以此完美地解決了內核內存使用中的外部分片問題。內核提供vmalloc函數分配內核虛擬內存，該函數不同於kmalloc，它可以分配較Kmalloc大得多的內存空間（可遠大於128K，但必須是頁大小的倍數），但相比Kmalloc來說,Vmalloc需要對內核虛擬地址進行重映射，必須更新內核頁表，因此分配效率上要低一些（用空間換時間）

與用戶進程相似,內核也有一個名為init_mm的mm_strcut結構來描述內核地址空間，其中頁表項pdg=swapper_pg_dir包含了系統內核空間（3G-4G）的映射關系。因此vmalloc分配內核虛擬地址必須更新內核頁表，而kmalloc或get_free_page由於分配的連續內存，所以不需要更新內核頁表。

vmalloc分配的內核虛擬內存與kmalloc/get_free_page分配的內核虛擬內存位於不同的區間，不會重疊。因為內核虛擬空間被分區管理，各司其職。進程空間地址分布從0到3G(其實是到PAGE_OFFSET,在0x86中它等於0xC0000000)，從3G到vmalloc_start這段地址是物理內存映射區域（該區域中包含了內核鏡像、物理頁面表mem_map等等）比如我使用的系統內存是64M(可以用free看到)，那麼(3G——3G+64M)這片內存就應該映射到物理內存，而vmalloc_start位置應在3G+64M附近（說"附近"因為是在物理內存映射區與vmalloc_start期間還會存在一個8M大小的gap來防止躍界）,vmalloc_end的位置接近4G(說"接近"是因為最後位置系統會保留一片128k大小的區域用於專用頁面映射，還有可能會有高端內存映射區，這些都是細節，這里我們不做糾纏)。

上圖是內存分布的模糊輪廓

由get_free_page或Kmalloc函數所分配的連續內存都陷於物理映射區域，所以它們返回的內核虛擬地址和實際物理地址僅僅是相差一個偏移量（PAGE_OFFSET），你可以很方便的將其轉化為物理內存地址，同時內核也提供了virt_to_phys（）函數將內核虛擬空間中的物理映射區地址轉化為物理地址。要知道，物理內存映射區中的地址與內核頁表是有序對應的，系統中的每個物理頁面都可以找到它對應的內核虛擬地址（在物理內存映射區中的）。

而vmalloc分配的地址則限於vmalloc_start與vmalloc_end之間。每一塊vmalloc分配的內核虛擬內存都對應一個vm_struct結構體（可別和vm_area_struct搞混，那可是進程虛擬內存區域的結構），不同的內核虛擬地址被4k大小的空閑區間隔，以防止越界——見下圖）。與進程虛擬地址的特性一樣，這些虛擬地址與物理內存沒有簡單的位移關系，必須通過內核頁表才可轉換為物理地址或物理頁。它們有可能尚未被映射，在發生缺頁時才真正分配物理頁面。

這里給出一個小程序幫助大家認清上面幾種分配函數所對應的區域。

#include<linux/mole.h>

#include<linux/slab.h>

#include<linux/vmalloc.h>

unsignedchar*pagemem;

unsignedchar*kmallocmem;

unsignedchar*vmallocmem;

intinit_mole(void)

{

pagemem = get_free_page(0);

printk("<1>pagemem=%s",pagemem);

kmallocmem = kmalloc(100,0);

printk("<1>kmallocmem=%s",kmallocmem);

vmallocmem = vmalloc(1000000);

printk("<1>vmallocmem=%s",vmallocmem);

}

voidcleanup_mole(void)

{

free_page(pagemem);

kfree(kmallocmem);

vfree(vmallocmem);

}

實例

內存映射(mmap)是Linux操作系統的一個很大特色，它可以將系統內存映射到一個文件（設備）上，以便可以通過訪問文件內容來達到訪問內存的目的。這樣做的最大好處是提高了內存訪問速度，並且可以利用文件系統的介面編程（設備在Linux中作為特殊文件處理）訪問內存，降低了開發難度。許多設備驅動程序便是利用內存映射功能將用戶空間的一段地址關聯到設備內存上，無論何時，只要內存在分配的地址范圍內進行讀寫，實際上就是對設備內存的訪問。同時對設備文件的訪問也等同於對內存區域的訪問，也就是說，通過文件操作介面可以訪問內存。Linux中的X伺服器就是一個利用內存映射達到直接高速訪問視頻卡內存的例子。

熟悉文件操作的朋友一定會知道file_operations結構中有mmap方法，在用戶執行mmap系統調用時，便會調用該方法來通過文件訪問內存——不過在調用文件系統mmap方法前，內核還需要處理分配內存區域（vma_struct）、建立頁表等工作。對於具體映射細節不作介紹了，需要強調的是,建立頁表可以採用remap_page_range方法一次建立起所有映射區的頁表，或利用vma_struct的nopage方法在缺頁時現場一頁一頁的建立頁表。第一種方法相比第二種方法簡單方便、速度快，但是靈活性不高。一次調用所有頁表便定型了，不適用於那些需要現場建立頁表的場合——比如映射區需要擴展或下面我們例子中的情況。

我們這里的實例希望利用內存映射，將系統內核中的一部分虛擬內存映射到用戶空間，以供應用程序讀取——你可利用它進行內核空間到用戶空間的大規模信息傳輸。因此我們將試圖寫一個虛擬字元設備驅動程序，通過它將系統內核空間映射到用戶空間——將內核虛擬內存映射到用戶虛擬地址。從上一節已經看到Linux內核空間中包含兩種虛擬地址：一種是物理和邏輯都連續的物理內存映射虛擬地址；另一種是邏輯連續但非物理連續的vmalloc分配的內存虛擬地址。我們的例子程序將演示把vmalloc分配的內核虛擬地址映射到用戶地址空間的全過程。

程序里主要應解決兩個問題：

第一是如何將vmalloc分配的內核虛擬內存正確地轉化成物理地址？

因為內存映射先要獲得被映射的物理地址，然後才能將其映射到要求的用戶虛擬地址上。我們已經看到內核物理內存映射區域中的地址可以被內核函數virt_to_phys轉換成實際的物理內存地址，但對於vmalloc分配的內核虛擬地址無法直接轉化成物理地址，所以我們必須對這部分虛擬內存格外「照顧」——先將其轉化成內核物理內存映射區域中的地址，然後在用virt_to_phys變為物理地址。

轉化工作需要進行如下步驟：

如下圖所示：

第二是當訪問vmalloc分配區時，如果發現虛擬內存尚未被映射到物理頁，則需要處理「缺頁異常」。因此需要我們實現內存區域中的nopaga操作，以能返回被映射的物理頁面指針，在我們的實例中就是返回上面過程中的內核物理內存映射區域中的地址。由於vmalloc分配的虛擬地址與物理地址的對應關系並非分配時就可確定，必須在缺頁現場建立頁表，因此這里不能使用remap_page_range方法，只能用vma的nopage方法一頁一頁的建立。

程序組成

map_driver.c，它是以模塊形式載入的虛擬字元驅動程序。該驅動負責將一定長的內核虛擬地址(vmalloc分配的)映射到設備文件上。其中主要的函數有——vaddress_to_kaddress（）負責對vmalloc分配的地址進行頁表解析,以找到對應的內核物理映射地址（kmalloc分配的地址）；map_nopage()負責在進程訪問一個當前並不存在的VMA頁時，尋找該地址對應的物理頁，並返回該頁的指針。

test.c它利用上述驅動模塊對應的設備文件在用戶空間讀取讀取內核內存。結果可以看到內核虛擬地址的內容（ok!），被顯示在了屏幕上。

執行步驟

編譯map_driver.c為map_driver.o模塊,具體參數見Makefile

載入模塊：insmodmap_driver.o

生成對應的設備文件

1在/proc/devices下找到map_driver對應的設備命和設備號：grepmapdrv/proc/devices

2建立設備文件mknodmapfilec 254 0（在我的系統里設備號為254）

利用maptest讀取mapfile文件，將取自內核的信息列印到屏幕上。

5. 簡述內存管理中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由一個或者多個連續的物理頁面組成。這些頁面種包含了已分配的緩存對象，也包含了空閑對象。

6. 怎樣設計一個內存池，減少內存碎片

一般工程里不推薦你寫，因為你費力寫一個出來99%可能性沒有內置的好，且內存出bug難調試
一定要設計的話，你也可以當個玩具寫寫玩玩：

1. 實現教科書上的內存分配器：
做一個鏈表指向空閑內存，分配就是取出一塊來，改寫鏈表，返回，釋放就是放回到鏈表裡面，並做好歸並。注意做好標記和保護，避免二次釋放，還可以花點力氣在如何查找最適合大小的內存快的搜索上，減少內存碎片，有空你了還可以把鏈表換成夥伴演算法，寫著玩嘛。

2. 實現固定內存分配器：
即實現一個 FreeList，每個 FreeList 用於分配固定大小的內存塊，比如用於分配 32位元組對象的固定內存分配器，之類的。每個固定內存分配器裡面有兩個鏈表，OpenList 用於存儲未分配的空閑對象，CloseList用於存儲已分配的內存對象，那麼所謂的分配就是從 OpenList 中取出一個對象放到 CloseList 里並且返回給用戶，釋放又是從 CloseList 移回到 OpenList。分配時如果不夠，那麼就需要增長 OpenList：申請一個大一點的內存塊，切割成比如 64 個相同大小的對象添加到 OpenList中。這個固定內存分配器回收的時候，統一把先前向系統申請的內存塊全部還給系統。

3. 實現 FreeList 池：
在你實現了 FreeList的基礎上，按照不同對象大小（8位元組，16位元組，32，64，128，256，512，1K。。。64K），構造十多個固定內存分配器，分配內存時根據內存大小查表，決定到底由哪個分配器負責，分配後要在頭部的 header 處（ptr[-sizeof(char*)]處）寫上 cookie，表示又哪個分配器分配的，這樣釋放時候你才能正確歸還。如果大於64K，則直接用系統的 malloc作為分配，如此以浪費內存為代價你得到了一個分配時間近似O（1）的內存分配器，差不多實現了一個 memcached 的 slab 內存管理器了，但是先別得意。此 slab 非彼 slab（sunos/solaris/linux kernel 的 slab）。這說白了還是一個弱智的 freelist 無法歸還內存給操作系統，某個 FreeList 如果高峰期佔用了大量內存即使後面不用，也無法支援到其他內存不夠的 FreeList，所以我們做的這個和 memcached 類似的分配器其實是比較殘缺的，你還需要往下繼續優化。

4. 實現正統的 slab （非memcached的偽 slab）代替 FreeList：
這時候你需要閱讀一下論文了，現代內存分配技術的基礎，如何管理 slab 上的對象，如何進行地址管理，如何管理不同 slab 的生命周期，如何將內存回收給系統。然後開始實現一個類似的東西，文章上傳統的 slab 的各種基礎概念雖然今天沒有改變，但是所用到的數據結構和控制方法其實已經有很多更好的方法了，你可以邊實現邊思考下，實在不行還可以參考 kernel 源碼嘛。但是有很多事情應用程序做不了，有很多實現你是不能照搬的，比如頁面提供器，可以提供連續線性地址的頁面，再比如說 kernel 本身記錄著每個頁面對應的 slab，你查找 slab 時，系統其實是根據線性地址移位得到頁面編號，然後查表得到的，而你應用程序不可能這么干，你還得做一些額外的體系來解決這些問題，還需要寫一些額外的 cookie 來做標記。做好內存收縮工作，內存不夠時先收縮所有分配器的 slab，再嘗試重新分配。再做好內存回收工作，多餘的內存，一段時間不使用可以還給操作系統。

5. 實現混合分配策略：
你實現了上面很多常見的演算法後，該具體閱讀各種內存分配器的代碼了，這些都是經過實踐檢驗的，比如 libc 的內存分配器，或者參考有自帶內存管理的各種開源項目，比如 python 源碼，做點實驗對比他們的優劣，然後根據分配對象的大小採用不同的分配策略，區別對待各種情況。試驗的差不多了就得引入多線程支持了，將你的鎖改小。注意很多系統層的線程安全策略你是沒法弄的，比如操作系統可以關中斷，短時間內禁止本cpu發生任務切換，這點應用程序就很麻煩了，還得用更小的鎖來代替。當鎖已經小到不能再小，也可以選擇引入 STM 來代替各種鏈表的鎖。

6. 實現 Per-CPU Cache：
現代內存分配器，在多核下的一個重要優化就是給多核增加 cache，為了進一步避免多線程鎖競爭，需要引入 Per-CPU Cache 了。分配內存先找到對應線程所在的cpu，從該cpu上對應的 cache 里分配，cache 不夠了就一次性從你底層的內存分配器里多分配幾個對象進來填充 cache，釋放時也是先放回 cache，cache裡面如果對象太多，就做一次收縮，把內存換個底層分配器，讓其他 cpu 的cache有機會利用。這樣針對很多短生命周期的頻繁的分配、釋放，其實都是在 cache 里完成的，沒有鎖競爭，同時cache分配邏輯簡單，速度更快。操作系統裡面的代碼經常是直接讀取當前的cpu是哪個，而應用層實現你可以用 thread local storage 來代替，目前這些東西在 crt的 malloc 里還暫時支持不到位（不排除未來版本會增加），可以更多參考 tc/jemalloc。

7. 實現地址著色:
現代內存分配器必須多考慮匯流排壓力，在很多機型上，如果內存訪問集中在某條 cache line相同的偏移上，會給匯流排帶來額外的負擔和壓力。比如你經常要分配一個 FILE 對象，而每個 FILE對象使用時會比較集中的訪問 int FILE::flag; 這個成員變數，如果你的頁面提供器提供的頁面地址是按照 4K對齊的，那麼很可能多個 FILE對象的 flag 成員所處的 cache line 偏移地址是相同的，大量訪問這些相同的偏移地址會給匯流排帶來很大負擔，這時候你需要給每個對象額外增加一些偏移，讓他們能夠均勻的分布在線性地址對應的cache line 偏移上，消減匯流排沖突的開銷。

8. 優化緩存競爭：
多核時代，很多單核時代的代碼都需要針對性的優化改寫，最基本的一條就是 cache 競爭，這是比前面鎖競爭更惡劣的情況：如果兩個cpu同時訪問相同的 cache-line 或者物理頁面，那麼 cpu 之間為了保證內存一致性會做很多的通信工作，比如那個cpu0需要用到這段內存，發現cpu1也在用，那麼需要通知cpu1，將cpu1 L1-L2緩存裡面的數據寫回該物理內存，並且釋放控制權，這時cpu0取得了控制權才能繼續操作，期間cpu0-cpu1之間的通信協議是比較復雜的，代價也是比較大的，cache競爭比鎖競爭惡劣不少。為了避免 cache 競爭，需要比先前Per-CPU cache 更徹底的 Per-CPU Page 機制來解決，直接讓不同的cpu使用不同的頁面進行二次分配，徹底避免 cache 競爭。具體應用層的做法也是利用線性地址來判斷所屬頁面（因為物理頁面映射到進程地址也是4k對齊的），同時繼續使用 thread local storage 或者用系統提供的 api 讀取當前屬於哪個 cpu 來實現。為了避免核太多每個核占據大量的頁面帶來的不必要的浪費，你可以參考下 Linux 最新的 slub 內存分配演算法，但是 slub 也有未盡之處，好幾個 linux 發行版在實踐中發現 slub 還是存在一些問題的（非bug，而是機制），所以大部分發行版默認都是關閉 slub 的，雖然，你還是可以借鑒測試一下。

9. 調試和折騰：
繼續參考各種現代內存分配器，取長補短，然後給你的分配器添加一些便於調試的機制，方便診斷各種問題。在你借鑒了很多開源項目，自己也做了一些所謂的優化，折騰了那麼久以後，你或許以為你的分配器可以同各種開源分配器一戰了，測試效果好像也挺好的，先別急，繼續觀察內存利用率，向操作系統申請/歸還內存的頻率等一系列容易被人忽視的指標是否相同。同時更換你的測試用例，看看更多的情況下，是否結果還和先前一樣？這些都差不多的時候，你發現沒有個一兩年的大規模持續使用，你很難發現一些潛在的隱患和bug，可能你覺得沒問題的代碼，跑了兩年後都會繼續報bug，這很正常，多點耐心，興許第三年以後就比較穩定了呢？

7. linux內核物理內存管理有哪些常用演算法 lru slab

採用夥伴演算法分配內存時，每次至少分配一個頁面。但當請求分配的內存大小為幾十個位元組或幾百個位元組時應該如何處理？如何在一個頁面中分配小的內存區，小內存區的分配所產生的內碎片又如何解決？
Linux2.0採用的解決辦法是建立了13個空閑區鏈表，它們的大小從32位元組到132056位元組。從Linux2.2開始，MM的開發者採用了一種叫做slab的分配模式，該模式早在1994年就被開發出來，用於Sun Microsystem Solaris 2.4操作系統中。Slab的提出主要是基於以下考慮：
· 內核對內存區的分配取決於所存放數據的類型。例如，當給用戶態進程分配頁面時，內核調用get_free_page()函數，並用0填充這個頁面。 而給內核的數據結構分配頁面時，事情沒有這么簡單，例如，要對數據結構所在的內存進行初始化、在不用時要收回它們所佔用的內存。因此，Slab中引入了對象這個概念，所謂對象就是存放一組數據結構的內存區，其方法就是構造或析構函數，構造函數用於初始化數據結構所在的內存區，而析構函數收回相應的內存區。但為了便於理解，你也可以把對象直接看作內核的數據結構。為了避免重復初始化對象，Slab分配模式並不丟棄已分配的對象，而是釋放但把它們依然保留在內存中。當以後又要請求分配同一對象時，就可以從內存獲取而不用進行初始化，這是在Solaris 中引入Slab的基本思想。
實際上，Linux中對Slab分配模式有所改進，它對內存區的處理並不需要進行初始化或回收。出於效率的考慮，Linux並不調用對象的構造或析構函數，而是把指向這兩個函數的指針都置為空。Linux中引入Slab的主要目的是為了減少對夥伴演算法的調用次數。
· 實際上，內核經常反復使用某一內存區。例如，只要內核創建一個新的進程，就要為該進程相關的數據結構（task_struct、打開文件對象等）分配內存區。當進程結束時，收回這些內存區。因為進程的創建和撤銷非常頻繁，因此，Linux的早期版本把大量的時間花費在反復分配或回收這些內存區上。從Linux2.2開始，把那些頻繁使用的頁面保存在高速緩存中並重新使用。
· 可以根據對內存區的使用頻率來對它分類。對於預期頻繁使用的內存區，可以創建一組特定大小的專用緩沖區進行處理，以避免內碎片的產生。對於較少使用的內存區，可以創建一組通用緩沖區（如Linux2.0中所使用的2的冪次方）來處理，即使這種處理模式產生碎片，也對整個系統的性能影響不大。
· 硬體高速緩存的使用，又為盡量減少對夥伴演算法的調用提供了另一個理由，因為對夥伴演算法的每次調用都會「弄臟」硬體高速緩存，因此，這就增加了對內存的平均訪問次數。
Slab分配模式把對象分組放進緩沖區（盡管英文中使用了Cache這個詞，但實際上指的是內存中的區域，而不是指硬體高速緩存）。因為緩沖區的組織和管理與硬體高速緩存的命中率密切相關，因此，Slab緩沖區並非由各個對象直接構成，而是由一連串的「大塊（Slab）」構成，而每個大塊中則包含了若干個同種類型的對象，這些對象或已被分配，或空閑，如圖6.12所示。一般而言，對象分兩種，一種是大對象，一種是小對象。所謂小對象，是指在一個頁面中可以容納下好幾個對象的那種。例如，一個inode結構大約佔300多個位元組，因此，一個頁面中可以容納8個以上的inode結構，因此，inode結構就為小對象。Linux內核中把小於512位元組的對象叫做小對象。

8. 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、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所屬隊列。