探秘嵌入式操作系統(tǒng)中的內(nèi)存管理算法

本文主要介紹內(nèi)存的基本概念以及操作系統(tǒng)的內(nèi)存管理算法。

1 內(nèi)存的基本概念

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

2 ROM&RAM&Flash

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

3 兩類內(nèi)存管理方式

內(nèi)存管理模塊管理系統(tǒng)的內(nèi)存資源，它是操作系統(tǒng)的核心模塊之一。主要包括內(nèi)存的初始化、分配以及釋放。 從分配內(nèi)存是否連續(xù)，可以分為兩大類。

連續(xù)內(nèi)存管理

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

非連續(xù)內(nèi)存管理

將進程分散到多個不連續(xù)的內(nèi)存空間中，可以減少內(nèi)存碎片，內(nèi)存使用率更高。如果分配的基本單位是頁，則稱為分頁內(nèi)存管理；如果基本單位是段，則稱為分段內(nèi)存管理。 當前的操作系統(tǒng)，普遍采用非連續(xù)內(nèi)存管理方式。不過因為分配粒度較大，對于內(nèi)存較小的嵌入式系統(tǒng)，一般采用連續(xù)內(nèi)存管理。本文主要對嵌入式系統(tǒng)中常用的連續(xù)內(nèi)存管理的分區(qū)式內(nèi)存管理進行介紹。

4 分區(qū)式內(nèi)存管理 分區(qū)式內(nèi)存管理分為固定分區(qū)和動態(tài)分區(qū)。

固定分區(qū) 事先就把內(nèi)存劃分為若干個固定大小的區(qū)域。分區(qū)大小既可以相等也可以不等。固定分區(qū)易于實現(xiàn)，但是會造成分區(qū)內(nèi)碎片浪費，而且分區(qū)總數(shù)固定，限制了可以并發(fā)執(zhí)行的進程數(shù)量。

動態(tài)分區(qū)

根據(jù)進程的實際需要，動態(tài)地給進程分配所需內(nèi)存。

5 動態(tài)分區(qū)內(nèi)存管理 運作機制

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

數(shù)據(jù)結(jié)構(gòu)

空閑鏈表法有多種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，這里介紹一種較為簡單的數(shù)據(jù)結(jié)構(gòu)。每個空閑分區(qū)的數(shù)據(jù)結(jié)構(gòu)中包含分區(qū)的大小，以及指向前一個分區(qū)和后一個分區(qū)的指針，這樣就能將各個空閑分區(qū)鏈接成一個雙向鏈表。

內(nèi)存分配算法

First Fit（首次適應(yīng)算法）

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

Next Fit（循環(huán)首次適應(yīng)算法）

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

Best Fit（最佳適應(yīng)算法）

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

Worst Fit（最壞適應(yīng)算法）

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

Two LevelSegregated Fit（TLSF）

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

圖中，第一層鏈表將空閑內(nèi)存塊的大小根據(jù)2的冪進行分類。第二層鏈表是具體的每一類空閑內(nèi)存塊按照一定的范圍進行線性分段。比如25這一類，以23即8分為4個內(nèi)存區(qū)間【25，25+8），【25+8，25+16），【25+16，25+24），【25+24，25+32）；216這一類，以214分為4個小區(qū)間【216，216+214），【216+214，216+2*214），【216+2*214，216+3*214），【216+3*214，216+4*214）。同時為了快速檢索到空閑塊，每一層鏈表都有一個bitmap用于標記對應(yīng)的鏈表中是否有空閑塊，比如第一層bitmap后3位010，表示25這一類內(nèi)存區(qū)間有空閑塊。對應(yīng)的第二層bitmap為0100表示【25+16，25+24）這個區(qū)間有空閑塊，即下面的52Byte。

Buddysystems（伙伴算法）

Segregated Fit算法的變種，具有更好的內(nèi)存拆分和回收合并效率?；锇樗惴ㄓ泻芏喾N類，比如BinaryBuddies，F(xiàn)ibonacci Buddies等。Binary Buddies是最簡單也是最流行的一種，將所有空閑分區(qū)根據(jù)分區(qū)的大小進行分類，每一類都是具有相同大小的空閑分區(qū)的集合，使用一個空閑雙向鏈表表示。BinaryBuddies中所有的內(nèi)存分區(qū)都是2的冪次方。 因為無論是已分配的或是空閑的分區(qū)，其大小均為 2 的冪次方，即使進程申請的內(nèi)存小于分配給它的內(nèi)存塊，多余的內(nèi)存也不會再拆分出來給其他進程使用，這樣就容易造成內(nèi)部碎片。 當進程申請一塊大小為n的內(nèi)存時的分配步驟為： 1、計算一個i值，使得2i-1

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

審核編輯：黃飛

?