一個記憶體配置設定方法的好壞，一是展現在 配置設定的速度 上，其重要性在記憶體容量較大時會顯得尤其明顯，二是展現在對記憶體這種有限資源的 使用率 上。如果空閑記憶體被分割成了許多無法利用的小記憶體塊(也就是俗稱的記憶體碎片)，那麼即便系統中空閑記憶體的總量還很多，也可能無法滿足程式記憶體配置設定的需求。 本系列文章将由淺入深，介紹記憶體配置設定常見的幾種實作方式及其各自的應用場景。
空閑連結清單(free list)
将記憶體中所有的空閑記憶體塊通過連結清單的形式組織起來，就形成了最基礎的free list。記憶體配置設定時，掃描free list的各個空閑記憶體塊，從中找到一個大小滿足要求的記憶體塊，并将該記憶體塊從free list中移除。記憶體釋放時，釋放的記憶體塊被重新插入到free list中。 假設現在記憶體的使用情況是這樣的：
灰色部分代表已經被配置設定的記憶體塊，白色部分代表空閑的記憶體塊，大小分别是48位元組，16位元組和96位元組。 如果此時記憶體配置設定的申請是 12個位元組 ，那麼将有幾下三種政策可以選擇：
- First fit(最先适配)，就是從free list頭部開始掃描，直到遇到第一個滿足大小的空閑記憶體塊，這裡第一個48位元組的記憶體塊就可以滿足要求。這種方法的優點是相對快一些，尤其是滿足要求的空閑記憶體塊位于連結清單前部的時候，但是在控制碎片數量上不是最優的。
- Best fit(最佳适配)，就是周遊free list的所有空閑記憶體塊，從中找到和所申請的記憶體大小最接近的空閑記憶體塊，這裡第二個16位元組的記憶體塊是最接近12位元組的。
- Worst fit(最差适配)，也是周遊free list的所有空閑記憶體塊，如果找不到大小剛好比對的，就從最大的空閑記憶體塊中配置設定。初看起來很反直覺是不是？但假設接下來的記憶體申請是64個位元組，那隻有worst fit的這種方法才能滿足需求，是以其價值展現在：配置設定之後剩下的空閑記憶體塊很可能仍然足夠大。
以上讨論的是記憶體配置設定的情況，接下來看看記憶體釋放的操作是怎樣的。 假設從第80位元組到第100位元組中間的20位元組記憶體被釋放了，那麼它将和前面相鄰的空閑記憶體塊合并：
接下來從第100位元組到第112位元組中間的12位元組記憶體也被釋放了，那麼它将同時和前後相鄰的空閑記憶體塊合并：
不過，既然用到了連結清單，那就需要指針，而指針本身也是要占用記憶體空間的。而且在記憶體釋放時，要判斷被釋放的記憶體塊前後的記憶體塊是不是也是空閑的，這就需要每個記憶體塊有一個空閑狀态的标志位。 可以采用的一種方式是bitmap，假設以4個位元組為最小配置設定機關，那麼每4位元組需要一個bit，是以額外消耗的記憶體為1/32。
記憶體池(memory pool)
空閑連結清單的配置設定方式簡單，但配置設定效率不高，運作一段時間後容易産生大量的記憶體碎片，進而惡化了記憶體使用率。 如果能将一大塊記憶體分成多個小記憶體(稱為記憶體池)，不同的記憶體池又按照不同的「尺寸」分成大小相同的記憶體塊(比如分别按照32, 64, 128……位元組)，同一記憶體池中的空閑記憶體塊按照free list的方式連接配接。 每次配置設定的時候，選擇和申請的的記憶體在「尺寸」上最接近的記憶體池，比如申請60位元組的記憶體，就直接從單個記憶體塊大小為64位元組的記憶體池的free list上配置設定。
這樣減少了free list連結清單的長度，能夠縮短每次記憶體配置設定所需的線性搜尋的時間，特别适合對實時性要求比較高的系統(比如RTOS)。 但要想取得好的效果，需要結合系統實際的記憶體配置設定需求，對記憶體池的大小進行合理的劃分。比如一個系統常用的是256位元組以下的記憶體申請，那設定過多的256位元組以上的記憶體池，就會造成記憶體資源的閑置和浪費。 似乎不是很好把控到底怎樣劃分記憶體池最為合适？ 下文 将要介紹的Linux中的buddy配置設定系統，将基于普通的記憶體池進行優化，以更貼合大型作業系統對記憶體管理的需求。