本文主要介紹內存的基本概念以及操作系統的內存管理算法。

內存的基本概念

內存是計算機系統中除了處理器以外最重要的資源，用于存儲當前正在執行的程序和數據。內存是相對于CPU來說的，CPU可以直接尋址的存儲空間叫做內存，CPU需要通過驅動才能訪問的叫做外存。

ROM RAM Flash

內存一般采用半導體存儲單元，分為只讀存儲器(ROM，Read Only Memory)、隨機存儲器(RAM，Random Access Memory)ROM一般只能讀取不能寫入，掉電后其中的數據也不會丟失。RAM既可以從中讀取也可以寫入，但是掉電后其中的數據會丟失。內存一般指的就是RAM。ROM在嵌入式系統中一般用于存儲BootLoader以及操作系統或者程序代碼或者直接當硬盤使用。近年來閃存(Flash)已經全面代替了ROM在嵌入式系統中的地位，它結合了ROM和RAM的長處，不僅具備電子可擦除可編程的特性，而且斷電也不會丟失數據，同時可以快速讀取數據。

兩類內存管理方式

內存管理模塊管理系統的內存資源，它是操作系統的核心模塊之一。主要包括內存的初始化、分配以及釋放。

從分配內存是否連續，可以分為兩大類。

連續內存管理：

為進程分配的內存空間是連續的，但這種分配方式容易形成內存碎片(碎片是難以利用的空閑內存，通常是小內存)，降低內存利用率。連續內存管理主要分為單一連續內存管理和分區式內存管理兩種。

非連續內存管理：

將進程分散到多個不連續的內存空間中，可以減少內存碎片，內存使用率更高。如果分配的基本單位是頁，則稱為分頁內存管理;如果基本單位是段，則稱為分段內存管理。

當前的操作系統，普遍采用非連續內存管理方式。不過因為分配粒度較大，對于內存較小的嵌入式系統，一般采用連續內存管理。本文主要對嵌入式系統中常用的連續內存管理的分區式內存管理進行介紹。

分區式內存管理

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

固定分區：

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

動態分區：

根據進程的實際需要，動態地給進程分配所需內存。

動態分區式內存管理

1運作機制動態分區管理一般采用空閑鏈表法，即基于一個雙向鏈表來保存空閑分區。對于初始狀態，整個內存塊都會被作為一個大的空閑分區加入到空閑鏈表中。當進程申請內存時，將會從這個空閑鏈表中找到一個大小滿足要求的空閑分區。如果分區大于所需內存，則從該分區中拆分出需求大小的內存交給進程，并將此拆分出的內存從空閑鏈表中移除，剩下的內存仍然是一個掛在空閑鏈表中的空閑分區。2數據結構

空閑鏈表法有多種數據結構實現，這里介紹一種較為簡單的數據結構。每個空閑分區的數據結構中包含分區的大小，以及指向前一個分區和后一個分區的指針，這樣就能將各個空閑分區鏈接成一個雙向鏈表。

3內存分配算法

First Fit (首次適應算法)

First Fit要求空閑分區鏈表以地址從小到大的順序連接。分配內存時，從鏈表的第一個空閑分區開始查找，將最先能夠滿足要求的空閑分區分配給進程。

Next Fit (循環首次適應算法)

Next Fit由First Fit算法演變而來。分配內存時，從上一次剛分配過的空閑分區的下一個開始查找，直至找到能滿足要求的空閑分區。查找時會采用循環查找的方式，即如果直到鏈表最后一個空閑分區都不能滿足要求，則返回到第一個空閑分區開始查找。

Best Fit (最佳適應算法)

從所有空閑分區中找出能滿足要求的、且大小最小的空閑分區。為了加快查找速度，Best Fit算法會把所有空閑分區按其容量從小到大的順序鏈接起來，這樣第一次找到的滿足大小要求的內存必然是最小的空閑分區。

Worst Fit (最壞適應算法)

從所有空閑分區中找出能滿足要求的、且大小最大的空閑分區。Worst Fit算法按其容量從大到小的順序鏈接所有空閑分區。

Two LevelSegregated Fit (TLSF)

使用兩層鏈表來管理空閑內存，將空閑分區大小進行分類，每一類用一個空閑鏈表表示，其中的空閑內存大小都在某個特定值或者某個范圍內。這樣存在多個空閑鏈表，所以又用一個索引鏈表來管理這些空閑鏈表，該表的每一項都對應一種空閑鏈表，并記錄該類空閑鏈表的表頭指針。

圖中，第一層鏈表將空閑內存塊的大小根據2的冪進行分類。第二層鏈表是具體的每一類空閑內存塊按照一定的范圍進行線性分段。

比如25這一類，以23即8分為4個內存區間

【25，25+8)，

【25+8，25+16)，

【25+16，25+24)，

【25+24，25+32);

216這一類，以214分為4個小區間

【216，216+214)，

【216+214，216+2*214)，

【216+2*214，216+3*214)，

【216+3*214，216+4*214)。

同時為了快速檢索到空閑塊，每一層鏈表都有一個bitmap用于標記對應的鏈表中是否有空閑塊，比如第一層bitmap后3位010，表示25這一類內存區間有空閑塊。對應的第二層bitmap為0100表示【25+16，25+24)這個區間有空閑塊，即下面的52Byte。

Buddysystems(伙伴算法)

Segregated Fit算法的變種，具有更好的內存拆分和回收合并效率?；锇樗惴ㄓ泻芏喾N類，比如BinaryBuddies，Fibonacci Buddies等。Binary Buddies是最簡單也是最流行的一種，將所有空閑分區根據分區的大小進行分類，每一類都是具有相同大小的空閑分區的集合，使用一個空閑雙向鏈表表示。BinaryBuddies中所有的內存分區都是2的冪次方。

因為無論是已分配的或是空閑的分區，其大小均為 2 的冪次方，即使進程申請的內存小于分配給它的內存塊，多余的內存也不會再拆分出來給其他進程使用，這樣就容易造成內部碎片。

當進程申請一塊大小為n的內存時的分配步驟為：

計算一個i值，使得2i-1

在空閑分區大小為2i的空閑鏈表中查找。

如果找到空閑塊，則分配給進程。

如果2i的空閑分區已經耗盡，則在分區大小為2i+1的空閑鏈表中查找。

如果存在2i+1的空閑分區，則將此空閑塊分為相等的兩個分區，這兩分區就是一對伙伴，其中一塊分配給進程，另一塊掛到分區大小為2i的空閑鏈表中。

如果2i+1的空閑分區還是不存在，則繼續查找大小為2i+2的空閑分區。如果找到，需要進行兩次拆分。第一次拆分為兩塊大小為2i+1的分區，一塊分區掛到大小為2i+1的空閑鏈表中，另一塊分區繼續拆分為兩塊大小為2i的空閑分區，一塊分配給進程，另一塊掛到大小為2i的空閑鏈表中。

如果2i+2的空閑分區也找不到，則繼續查找2i+3，以此類推。

在內存回收時，如果待回收的內存塊與空閑鏈表中的一塊內存互為伙伴，則將它們合并為一塊更大的內存塊，如果合并后的內存塊在空閑鏈表中還有伙伴，則繼續合并到不能合并為止，并將合并后的內存塊掛到對應的空閑鏈表中。

下面的表格對上面6種算法的優缺點進行了比較：

內存算法優點缺點

First Fit高地址空間大空閑塊被保留低地址空間被不斷拆分，造成碎片;每次都從第一個空閑分區開始查找，增加了查找時的系統開銷

Next Fit空閑分區分布比較均勻，算法開銷小缺乏大內存空閑塊

Best Fit用最小內存滿足要求，保留大內存空閑塊每次分配后所拆分出來的剩余空閑內存總是最小的，造成許多小碎片，算法開銷大

Worst Fit每次分配后所拆分出來的剩余空閑內存仍較大，減少小碎片產生缺乏大內存空閑塊，算法開銷大

TLSF查找效率高，時間復雜度小，碎片問題表現良好內存回收時算法復雜，系統開銷大

Buddy systems內部碎片比較嚴重外部碎片較少

審核編輯：湯梓紅