操作系統(tǒng)的內(nèi)存管理算法
本文主要介紹內(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)才能訪問(wèn)的叫做外存。
二、ROM&RAM&Flash
內(nèi)存一般采用半導(dǎo)體存儲(chǔ)單元，分為只讀存儲(chǔ)器（ROM，Read Only Memory）、隨機(jī)存儲(chǔ)器（RAM，Random Access Memory）ROM一般只能讀取不能寫入，掉電后其中的數(shù)據(jù)也不會(huì)丟失。RAM既可以從中讀取也可以寫入，但是掉電后其中的數(shù)據(jù)會(huì)丟失。內(nèi)存一般指的就是RAM。
ROM在嵌入式系統(tǒng)中一般用于存儲(chǔ)BootLoader以及操作系統(tǒng)或者程序代碼或者直接當(dāng)硬盤使用。近年來(lái)閃存（Flash）已經(jīng)全面代替了ROM在嵌入式系統(tǒng)中的地位，它結(jié)合了ROM和RAM的長(zhǎng)處，不僅具備電子可擦除可編程的特性，而且斷電也不會(huì)丟失數(shù)據(jù)，同時(shí)可以快速讀取數(shù)據(jù)。
從分配內(nèi)存是否連續(xù)，可以分為兩大類。
連續(xù)內(nèi)存管理
非連續(xù)內(nèi)存管理
將進(jìn)程分散到多個(gè)不連續(xù)的內(nèi)存空間中，可以減少內(nèi)存碎片，內(nèi)存使用率更高。如果分配的基本單位是頁(yè)，則稱為分頁(yè)內(nèi)存管理；如果基本單位是段，則稱為分段內(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)存劃分為若干個(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ū)管理一般采用空閑鏈表法，即基于一個(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è)大小滿足要求的空閑分區(qū)。如果分區(qū)大于所需內(nèi)存，則從該分區(qū)中拆分出需求大小的內(nèi)存交給進(jìn)程，并將此拆分出的內(nèi)存從空閑鏈表中移除，剩下的內(nèi)存仍然是一個(gè)掛在空閑鏈表中的空閑分區(qū)。
空閑鏈表法有多種數(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è)雙向鏈表。
First Fit（首次適應(yīng)算法）
First Fit要求空閑分區(qū)鏈表以地址從小到大的順序鏈接。分配內(nèi)存時(shí)，從鏈表的第一個(gè)空閑分區(qū)開始查找，將最先能夠滿足要求的空閑分區(qū)分配給進(jìn)程。
Next Fit（循環(huán)首次適應(yīng)算法）
Best Fit（最佳適應(yīng)算法）
Worst Fit（最壞適應(yīng)算法）
Two LevelSegregated Fit（TLSF）
-
Buddysystems（伙伴算法）
1、計(jì)算一個(gè)i值，使得2i-1<n≤2i
2、在空閑分區(qū)大小為2i的空閑鏈表中查找
3、如果找到空閑塊，則分配給進(jìn)程
4、如果2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i+1的空閑鏈表中查找
6、如果2i+1的空閑分區(qū)還是不存在，則繼續(xù)查找大小為2i+2的空閑分區(qū)。如果找到，需要進(jìn)行兩次拆分。第一次拆分為兩塊大小為2i+1的分區(qū)，一塊分區(qū)掛到大小為2i+1的空閑鏈表中，另一塊分區(qū)繼續(xù)拆分為兩塊大小為2i的空閑分區(qū)，一塊分配給進(jìn)程，另一塊掛到大小為2i的空閑鏈表中
7、如果2i+2的空閑分區(qū)也找不到，則繼續(xù)查找2i+3，以此類推
| 內(nèi)存算法 |
優(yōu)點(diǎn) |
缺點(diǎn) |
| First Fit | 高地址空間大空閑塊被保留 | 低地址空間被不斷拆分，造成碎片；每次都從第一個(gè)空閑分區(qū)開始查找，增加了查找時(shí)的系統(tǒng)開銷 |
| Next Fit | 空閑分區(qū)分布比較均勻，算法開銷小 | 缺乏大內(nèi)存空閑塊 |
| Best Fit | 用最小內(nèi)存滿足要求，保留大內(nèi)存空閑塊 | 每次分配后所拆分出來(lái)的剩余空閑內(nèi)存總是最小的，造成許多小碎片，算法開銷大 |
| Worst Fit | 每次分配后所拆分出來(lái)的剩余空閑內(nèi)存仍較大，減少小碎片產(chǎn)生 | 缺乏大內(nèi)存空閑塊，算法開銷大 |
| TLSF | 查找效率高，時(shí)間復(fù)雜度小，碎片問(wèn)題表現(xiàn)良好 | 內(nèi)存回收時(shí)算法復(fù)雜，系統(tǒng)開銷大 |
| Buddy systems | 內(nèi)部碎片比較嚴(yán)重 | 外部碎片較少 |
免責(zé)聲明：本文轉(zhuǎn)自LiteOS物聯(lián)網(wǎng)操作系統(tǒng)，版權(quán)歸原作者所有。如涉及作品版權(quán)問(wèn)題，請(qǐng)與我聯(lián)系刪除。
ST-LINK Utility查看內(nèi)核運(yùn)行狀態(tài)
C語(yǔ)言中幾種特殊標(biāo)準(zhǔn)定義和用法
C語(yǔ)言 volatile 關(guān)鍵字在編譯優(yōu)化過(guò)程中有何作用
長(zhǎng)按前往圖中包含的公眾號(hào)關(guān)注
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
