目錄

• 前言
• 分區式內存管理
• 動態分區內存管理
• 總結

本筆記參考黃工的https://mp.weixin.qq.com/s/k0W_LqI1zBAYC1GU1U2HQA

前言

內存管理模塊主要負責內存的初始化、分配以及釋放。
從分配內存是否連續可以分為兩大類：

• 1、連續內存管理
  為進程分配的內存空間是連續的，但這種分配方式容易形成內存碎片，降低內存利用率。連續內存管理主要分為單一連續內存管理和分區內存管理兩種。
• 2、非連續內存管理
  將進程分散到多個不連續的內存空間種，可以減少內存碎片，內存使用率更高。如果分配的基本單位是頁，則稱為分頁式內存管理；如果基本單位式段，則稱為分段式內存管理

目前的OS主要采用非連續內存管理。對于內存較小的嵌入式系統，一般采用連續內存管理。
這里詳細講解連續內存管理的分區式內存管理，當然了解相關原理后也可以用于自己構建相關內存池。

分區式內存管理

分區式內存管理分為固定分區和動態分區

• 固定分區
  事先就把內存劃分為若干個固定大小的區域。分區大小既可以相等也可以不等。固定分區易于實現，但是會造成分區內碎片浪費，而且分區總數固定，限制了可以并發執行的進程數
• 動態分區
  根據進程的實際需要，動態地給進程分配所需內存

動態分區內存管理

運作機制：
動態分區管理一般采用空閑鏈表法，即基于一個雙向鏈表來保存空閑分區。對于初始狀態，整個內存塊都會被作為一個大的空閑分區加入到空閑鏈表中。當進程申請內存時，將會從這個空閑鏈表種找到一個大小滿足要求地空閑分區。如果分區大于所需內存，則從該分區中拆分出需求大小地內存交給進程，并將此拆分出的內存從空閑鏈表中移除，剩下的內存仍然是一個掛在空閑鏈表上的空閑分區。
數據結構
空閑鏈表法有多種數據結構實現方式，這里介紹一種較為簡單的數據結構。每個空閑分區的數據結構中包含分區大小，以及指向前一個分區和后一個分區的指針，這樣就能將各個空閑分區鏈接成一個雙向鏈表。

內存分配算法

• First Fit（首次適應算法）
  First Fit要求空閑分區鏈表以地址從小到大順序鏈接。分配內存時，從鏈表的第一個空閑分區開始查找，將最先能夠滿足要求的空閑分區分配給進程。
• Next Fit（循環首次適應算法）
  該算法由FF算法演變而來。分配內存時，從上一次剛分配過的空閑分區的下一個開始查找，直到找到能滿足要求的空閑分區。查找時會采用循環查找的方式，即如果直到鏈表最后一個空閑分區都不滿足，則返回到第一個空閑分區開始查找
• Best Fit（最佳適應算法）
  從所有空閑分區中找到能滿足要求的、且大小最小的空閑分區。為了加快查找速度，BF算法會把所有空閑分區按其容量從小到大的順序鏈接起來，這樣第一次找到的滿足大小要求的內存必然是最小的空閑分區
  與此相反的有個Worst Fit最壞適應算法，它是找到大小最大的空閑分區，然后按照容量從大到小順序鏈接所有空閑分區塊
• Two LevelSegregated Fit（TLSF）
  使用兩層鏈表來管理空閑內存，將空閑分區大小進行分類
  每個類用一個空閑鏈表表示，其中空閑內存大小都在某個特定值或者范圍內。這樣存在多個空閑鏈表，所以又用一個索引鏈表來管理這些空閑鏈表，該表的每一項都對應一種空閑鏈表，并記錄該類空閑鏈表的表頭指針。
  
  第一層鏈表將空閑塊的大小根據2的冪次進行分類。
  第二層鏈表是具體的每一類空閑內存塊按照一定的范圍進行線性分段
  同時為了快速檢索到空閑塊，每一層鏈表都有一個bitmap用于標記對應的鏈表中是否有空閑塊。
  如第一層bitmap后三位010，表示2^5這一類內存區間有空閑塊。對應的第二層bitmap為0100表示【25+16，25+24）這個區間有空閑塊
• 伙伴算法
  該算法為TLSF算法的變種，具有更好的內存拆分和回收合并效率。
  伙伴算法有很多種類，比如BinaryBuddies、Fibonacci Buddies等。Binary Buddies是最簡單也是最流行的一種。
  將所有空閑分區根據分區的大小進行分類，每一類都是具有相同大小的空閑分區的集合，使用一個空閑雙向鏈表表示。BinaryBuddies中所有的內存分區都是2的冪次方。
  無論是已分配還是空閑的分區，其大小都是2的冪次方，即使進程申請的內存小于分配給它的內存塊，多余的內存也不會再拆分出來給其他進程使用，這樣就容易造成內部碎片。
  當進程申請一塊大小為n的內存時的分配步驟為：
  1、計算一個i值，使得2 ^ i-1< n ≤2 ^ i
  2、在空閑分區大小為2 ^ i 的空閑鏈表中查找
  3、如果找到空閑塊，則分配給進程
  4、如果2 ^ i的空閑分區已經耗盡，則在分區大小為2 ^ i+1的空閑鏈表中查找
  5、如果存在2 ^i+1 的空閑分區，則將此空閑塊分為相等的兩個分區 ，這兩個分區就是一對伙伴，其中一塊分配給進程，另一塊掛到分區大小為2 ^ i的空閑鏈表中
  6、如果2 ^ i+1 的空閑分區還是不存在，則繼續查找大小為2 ^ i+2 的空閑分區。如果找到，需要進行兩次拆分。第一次拆分為兩塊大小為2 ^ i+1的空閑分區，一塊掛到2 ^ i+1的空閑鏈表中，另一塊分區繼續拆分為兩塊大小為2 ^ i的空閑分區，一塊分配給進程，另一塊掛到大小為2 ^ i的空閑鏈表中
  7、如果2 ^ i+2的空閑分區也找不到，則繼續查找2 ^ i+3，依次類推
  在內存回收時，如果待回收的內存塊與空閑鏈表中的一塊內存互為伙伴，則將它們合并為一塊更大的內存塊。如果合并后的內存塊在空閑鏈表中還有伙伴，則繼續合并到不能合并為止，并將合并后的內存塊掛到對應的空閑鏈表中，
  

總結