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

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

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

ROM RAM Flash

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

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

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

從分配內(nèi)存是否連續(xù)，可以分為兩大類(lèi)。

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

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

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

將進(jìn)程分散到多個(gè)不連續(xù)的內(nèi)存空間中，可以減少內(nèi)存碎片，內(nèi)存使用率更高。如果分配的基本單位是頁(yè)，則稱(chēng)為分頁(yè)內(nèi)存管理;如果基本單位是段，則稱(chēng)為分段內(nèi)存管理。

當(dāng)前的操作系統(tǒng)，普遍采用非連續(xù)內(nèi)存管理方式。不過(guò)因?yàn)榉峙淞６容^大，對(duì)于內(nèi)存較小的嵌入式系統(tǒng)，一般采用連續(xù)內(nèi)存管理。本文主要對(duì)嵌入式系統(tǒng)中常用的連續(xù)內(nèi)存管理的分區(qū)式內(nèi)存管理進(jìn)行介紹。

分區(qū)式內(nèi)存管理

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

固定分區(qū)：

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

動(dòng)態(tài)分區(qū)：

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

動(dòng)態(tài)分區(qū)式內(nèi)存管理

1運(yùn)作機(jī)制動(dòng)態(tài)分區(qū)管理一般采用空閑鏈表法，即基于一個(gè)雙向鏈表來(lái)保存空閑分區(qū)。對(duì)于初始狀態(tài)，整個(gè)內(nèi)存塊都會(huì)被作為一個(gè)大的空閑分區(qū)加入到空閑鏈表中。當(dāng)進(jìn)程申請(qǐng)內(nèi)存時(shí)，將會(huì)從這個(gè)空閑鏈表中找到一個(gè)大小滿(mǎn)足要求的空閑分區(qū)。如果分區(qū)大于所需內(nèi)存，則從該分區(qū)中拆分出需求大小的內(nèi)存交給進(jìn)程，并將此拆分出的內(nèi)存從空閑鏈表中移除，剩下的內(nèi)存仍然是一個(gè)掛在空閑鏈表中的空閑分區(qū)。2數(shù)據(jù)結(jié)構(gòu)

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

3內(nèi)存分配算法

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

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

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

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

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

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

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

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

Two LevelSegregated Fit (TLSF)

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

圖中，第一層鏈表將空閑內(nèi)存塊的大小根據(jù)2的冪進(jìn)行分類(lèi)。第二層鏈表是具體的每一類(lèi)空閑內(nèi)存塊按照一定的范圍進(jìn)行線(xiàn)性分段。

比如25這一類(lèi)，以23即8分為4個(gè)內(nèi)存區(qū)間

【25，25+8)，

【25+8，25+16)，

【25+16，25+24)，

【25+24，25+32);

216這一類(lèi)，以214分為4個(gè)小區(qū)間

【216，216+214)，

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

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

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

同時(shí)為了快速檢索到空閑塊，每一層鏈表都有一個(gè)bitmap用于標(biāo)記對(duì)應(yīng)的鏈表中是否有空閑塊，比如第一層bitmap后3位010，表示25這一類(lèi)內(nèi)存區(qū)間有空閑塊。對(duì)應(yīng)的第二層bitmap為0100表示【25+16，25+24)這個(gè)區(qū)間有空閑塊，即下面的52Byte。

Buddysystems(伙伴算法)

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

因?yàn)闊o(wú)論是已分配的或是空閑的分區(qū)，其大小均為 2 的冪次方，即使進(jìn)程申請(qǐng)的內(nèi)存小于分配給它的內(nèi)存塊，多余的內(nèi)存也不會(huì)再拆分出來(lái)給其他進(jìn)程使用，這樣就容易造成內(nèi)部碎片。

當(dāng)進(jìn)程申請(qǐng)一塊大小為n的內(nèi)存時(shí)的分配步驟為：

計(jì)算一個(gè)i值，使得2i-1

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

如果找到空閑塊，則分配給進(jìn)程。

如果2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i+1的空閑鏈表中查找。

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

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

如果2i+2的空閑分區(qū)也找不到，則繼續(xù)查找2i+3，以此類(lèi)推。

在內(nèi)存回收時(shí)，如果待回收的內(nèi)存塊與空閑鏈表中的一塊內(nèi)存互為伙伴，則將它們合并為一塊更大的內(nèi)存塊，如果合并后的內(nèi)存塊在空閑鏈表中還有伙伴，則繼續(xù)合并到不能合并為止，并將合并后的內(nèi)存塊掛到對(duì)應(yīng)的空閑鏈表中。

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

內(nèi)存算法優(yōu)點(diǎn)缺點(diǎn)

First Fit高地址空間大空閑塊被保留低地址空間被不斷拆分，造成碎片;每次都從第一個(gè)空閑分區(qū)開(kāi)始查找，增加了查找時(shí)的系統(tǒng)開(kāi)銷(xiāo)

Next Fit空閑分區(qū)分布比較均勻，算法開(kāi)銷(xiāo)小缺乏大內(nèi)存空閑塊

Best Fit用最小內(nèi)存滿(mǎn)足要求，保留大內(nèi)存空閑塊每次分配后所拆分出來(lái)的剩余空閑內(nèi)存總是最小的，造成許多小碎片，算法開(kāi)銷(xiāo)大

Worst Fit每次分配后所拆分出來(lái)的剩余空閑內(nèi)存仍較大，減少小碎片產(chǎn)生缺乏大內(nèi)存空閑塊，算法開(kāi)銷(xiāo)大

TLSF查找效率高，時(shí)間復(fù)雜度小，碎片問(wèn)題表現(xiàn)良好內(nèi)存回收時(shí)算法復(fù)雜，系統(tǒng)開(kāi)銷(xiāo)大

Buddy systems內(nèi)部碎片比較嚴(yán)重外部碎片較少

審核編輯：湯梓紅