當(dāng)前位置:首頁 > 嵌入式 > 嵌入式教程
[導(dǎo)讀]動(dòng)態(tài)內(nèi)存管理在面向嵌入式實(shí)時(shí)系統(tǒng)中的研究

動(dòng)態(tài)內(nèi)存管理的基本任務(wù)就是有效地對(duì)動(dòng)態(tài)內(nèi)存進(jìn)行分配、回收,并同時(shí)保證系統(tǒng)的快速性、可靠性和穩(wěn)定性。當(dāng)系統(tǒng)請(qǐng)求分配內(nèi)存時(shí),系統(tǒng)需要從所有空閑塊中找到一個(gè)合適的空閑塊進(jìn)行分配;當(dāng)用戶不再使用而將某塊內(nèi)存釋放時(shí),系統(tǒng)需要回收這一內(nèi)存塊,以備在新的請(qǐng)求產(chǎn)生時(shí)重新進(jìn)行分配。為此,系統(tǒng)需要建立一個(gè)與內(nèi)存當(dāng)前使用情況相對(duì)應(yīng)的內(nèi)存描述,用來記錄所有與內(nèi)存分配、回收相關(guān)的信息。而如何記錄這些信息并進(jìn)行分配與回收,便成為各種算法的最根本區(qū)別。

  1  嵌入式系統(tǒng)中內(nèi)存管理技術(shù)的特點(diǎn)

  實(shí)時(shí)系統(tǒng)分為硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)。硬實(shí)時(shí)系統(tǒng)是指系統(tǒng)中各任務(wù)不僅要執(zhí)行無誤而且要做到準(zhǔn)時(shí);軟實(shí)時(shí)系統(tǒng)是指系統(tǒng)中各任務(wù)運(yùn)行的越快越好,并不要求限定某一任務(wù)必須在多長時(shí)間內(nèi)完成??梢钥闯鰟?dòng)態(tài)內(nèi)存分配是絕對(duì)不能用于硬實(shí)時(shí)系統(tǒng)的,因?yàn)閯?dòng)態(tài)分配具有時(shí)間不確定性(分配時(shí)間與內(nèi)存塊數(shù)量有關(guān)),而且動(dòng)態(tài)分配可能產(chǎn)生分配不成功的情況。所以對(duì)于硬實(shí)時(shí)系統(tǒng),只能采用靜態(tài)內(nèi)存分配方式。靜態(tài)分配是指在編譯或鏈接時(shí)將程序所需的內(nèi)存空間分配好,這樣不會(huì)出現(xiàn)分配失敗的情況。

  1.1 靜態(tài)分配與動(dòng)態(tài)分配

  靜態(tài)分配為系統(tǒng)提供了最好的可靠性與實(shí)時(shí)性。對(duì)于那些對(duì)實(shí)時(shí)性和可靠性要求極高的需求,就只能采用靜態(tài)分配方式。但采用靜態(tài)分配就必然會(huì)使系統(tǒng)失去靈活性。因此必須在設(shè)計(jì)階段考慮所有可能的情況,并對(duì)所有的需求做出相應(yīng)的空間分配。一旦出現(xiàn)沒有考慮到的情況,系統(tǒng)就無法處理。此外靜態(tài)分配方式也必然導(dǎo)致很大的浪費(fèi),因?yàn)楸仨毎凑兆顗那闆r進(jìn)行最大的配置,而在實(shí)際運(yùn)行中可能只用到其中的一小部分。

  動(dòng)態(tài)分配為系統(tǒng)提供了很大的靈活性,而且在內(nèi)存的利用率和系統(tǒng)功能擴(kuò)展等方面也都明顯地優(yōu)于靜態(tài)分配。

  大多數(shù)系統(tǒng)采用靜態(tài)分配和動(dòng)態(tài)分配相結(jié)合的方式。由于嵌入式系統(tǒng)本身各個(gè)任務(wù)的可靠性、實(shí)時(shí)性要求不盡相同,通常會(huì)有一部分任務(wù)對(duì)可靠性與實(shí)時(shí)性沒有特別嚴(yán)格的要求。這些任務(wù)對(duì)一定的延時(shí)與失敗是可以接受的。因此對(duì)于這樣的一部分任務(wù),就可以采用動(dòng)態(tài)分配方式來滿足它們部分或全部的內(nèi)存需求。而對(duì)于那些有嚴(yán)格時(shí)限要求的任務(wù),為了保證任務(wù)的可靠性和實(shí)時(shí)性,就應(yīng)采用靜態(tài)分配方式。

  1.2 動(dòng)態(tài)分配的技術(shù)要求

 ?。?)快速性:由于嵌入式系統(tǒng)對(duì)實(shí)時(shí)性要求較高,所以內(nèi)存分配過程要盡可能地快。在嵌入式系統(tǒng)中,由于還不能采用通用操作系統(tǒng)中復(fù)雜而完善的內(nèi)存分配策略,所以一般都采用簡單、快速的內(nèi)存分配方案。

 ?。?)可靠性:由于嵌入式系統(tǒng)對(duì)可靠性的要求較高,所以內(nèi)存分配過程也要具備高可靠性。但由于各個(gè)嵌入式系統(tǒng)之間對(duì)可靠性的要求不盡相同,對(duì)內(nèi)存分配的可靠性要求也就各不相同。通常,可靠性要求極高的系統(tǒng)不采用動(dòng)態(tài)分配。

 ?。?)高效性:由于在嵌入式系統(tǒng)中內(nèi)存資源都相對(duì)有限,所以為了保證程序的正常運(yùn)行,內(nèi)存管理系統(tǒng)要盡可能高效地使用內(nèi)存,減少不必要的浪費(fèi)。

  2  伙伴系統(tǒng)

  2.1 伙伴系統(tǒng)原理

  伙伴(buddy)系統(tǒng)的基本原理就是按照2的冪次方大小對(duì)內(nèi)存進(jìn)行分配,以此得到很高的分配速度和回收速度。例如:對(duì)于10KB的空間請(qǐng)求,伙伴系統(tǒng)會(huì)分配16KB的空間來滿足。因?yàn)閮?nèi)存空閑塊大小均為2的冪次方,所以需要16KB,這是滿足10KB的最小空間;同樣對(duì)于70KB的空間請(qǐng)求,伙伴系統(tǒng)會(huì)分配128KB的空間來滿足。

  2.2 伙伴系統(tǒng)存在的問題

  伙伴系統(tǒng)比那些按大小而不按塊的整數(shù)倍地址分配的算法有更多的優(yōu)點(diǎn)。其優(yōu)點(diǎn)為當(dāng)一個(gè)大小為2的K次冪的塊被釋放后,存儲(chǔ)管理只需要搜索2的K次冪字節(jié)大小的塊以判定是否需要合并。那些允許內(nèi)存塊以任意形式分割的策略需要搜索所有的空閑塊表。相比之下,伙伴系統(tǒng)更快。

  但是對(duì)于內(nèi)存利用率來說,伙伴系統(tǒng)是極其低效的。問題出自所有的內(nèi)存請(qǐng)求都必須以2的冪次方大小的空間來滿足,一個(gè)35KB的請(qǐng)求需要分配64KB的空間,其余的29KB被浪費(fèi)了。在極端情況下內(nèi)存資源有近50%被浪費(fèi)。

  3  連續(xù)的內(nèi)存分配

  3.1 問題提出

  伙伴系統(tǒng)的內(nèi)存管理方式對(duì)空間的使用存在極大的浪費(fèi)。在某些情況下還會(huì)由于資源的浪費(fèi),導(dǎo)致后繼的內(nèi)存請(qǐng)求得不到滿足,進(jìn)而嚴(yán)重地影響程序的正常功能。

  試考慮:系統(tǒng)共有1MB內(nèi)存空間可用,采用伙伴系統(tǒng)進(jìn)行管理。有如下請(qǐng)求:請(qǐng)求A,300KB;請(qǐng)求B,300KB;請(qǐng)求C,50KB.結(jié)果如表1所示。

  由表1中可以看出:伙伴系統(tǒng)對(duì)空間的浪費(fèi)是極其嚴(yán)重的,即使在物理內(nèi)存充足(1MB)的情況下,也會(huì)產(chǎn)生請(qǐng)求(650KB)無法滿足的情況。

  由于在嵌入式系統(tǒng)中,一般都沒有虛擬內(nèi)存的支持,所以當(dāng)內(nèi)存請(qǐng)求無法得到滿足時(shí),將嚴(yán)重影響程序的正常功能。因此為了保證程序的正常功能,就要提高內(nèi)存的利用率,盡可能地滿足程序的內(nèi)存請(qǐng)求。所以在對(duì)伙伴系統(tǒng)進(jìn)行分析的基礎(chǔ)上,提出了連續(xù)的內(nèi)存分配方式。

3.2 連續(xù)的內(nèi)存分配原理

  從上例不難看出,只要采用連續(xù)的內(nèi)存分配方式(即分配與請(qǐng)求大小相等的空間來滿足請(qǐng)求),便不難使請(qǐng)求C得到滿足,而且還會(huì)有很大的剩余空間繼續(xù)用來滿足其他的內(nèi)存請(qǐng)求。結(jié)果如表2所示。

  連續(xù)的內(nèi)存分配方式明顯不同于其他以塊為單位進(jìn)行分配的內(nèi)存管理方法。它采用連續(xù)分配的方式,按照請(qǐng)求空間的實(shí)際大小來進(jìn)行空間分配。
[!--empirenews.page--]3.3 連續(xù)的內(nèi)存分配實(shí)現(xiàn)方法

 

  為了提高內(nèi)存空間的利用率,采用按請(qǐng)求的實(shí)際大小來分配空間,而不是按塊的整數(shù)倍大小來分配空間。

  基本方法就是將所有獨(dú)立塊(空閑塊和使用塊)按物理地址的先后順序組織成一個(gè)雙鏈表,每個(gè)塊中存放塊本身的一些獨(dú)立信息。分配空間時(shí),需要查找整個(gè)鏈表以找到最優(yōu)適配的空閑塊,之后再將此空閑塊分裂成二塊,一塊用來滿足請(qǐng)求,另一塊則作為空閑塊插入鏈表??臻g釋放時(shí),只需根據(jù)鏈表便可以方便地找到與其相鄰的物理塊,在空間合并處理完成之后再將新的塊插入鏈表。

  但事實(shí)上,由于在分配過程中只需要在空閑塊中查找最優(yōu)適配塊,所以可以采用一個(gè)單獨(dú)的鏈表將所有的空閑塊鏈接起來,這樣可以極大地加快空間分配時(shí)空閑塊的查找速度。

  另外,從對(duì)伙伴系統(tǒng)的分析可知,將所有的內(nèi)存空閑區(qū)保留在一個(gè)或多個(gè)按空閑區(qū)大小排序的鏈表中將使內(nèi)存分配很快。所以借鑒伙伴系統(tǒng)的實(shí)現(xiàn)方式,可以將單個(gè)的空閑分區(qū)鏈組織成多個(gè)鏈表間有序的空閑分區(qū)鏈。在動(dòng)態(tài)內(nèi)存操作頻繁的情況下,這將會(huì)提高系統(tǒng)內(nèi)存分配的效率。

  由于以上的方式容易產(chǎn)生許多小的不能繼續(xù)使用的空閑區(qū),所以在進(jìn)行空間分配時(shí),如果分配所得的空閑區(qū)小于某一特定值,則不再進(jìn)行空間分配,而是將整個(gè)空間作為請(qǐng)求結(jié)果返回。

  綜上所述,可以將內(nèi)存塊組織成二個(gè)雙鏈表,即空閑塊鏈表和物理塊鏈表。

 ?。?)空閑塊鏈表:將所有的空閑塊按鏈表間有序的方式組織成多個(gè)獨(dú)立的空閑鏈表??臻g分配時(shí),根據(jù)空間的大小選擇相應(yīng)的鏈表進(jìn)行查找。若查找成功,則在空間分配處理完成之后,將已分配空間返回給請(qǐng)求;若查找失敗,則在更大空間的鏈表中繼續(xù)查找;若直到全部鏈表查找完成仍未找到合適的空閑塊,則認(rèn)為此次分配操作失敗。

 ?。?)物理塊鏈表:將所有獨(dú)立塊(空閑塊和使用塊)組織成一個(gè)雙鏈表,鏈表中各節(jié)點(diǎn)之間是按照物理地址的先后順序鏈接的,每個(gè)塊中存放塊本身的一些獨(dú)立信息??臻g釋放時(shí),可以不需查找,而直接根據(jù)這一鏈表找到與釋放塊相鄰的塊。再根據(jù)相鄰塊中的相關(guān)信息就可以方便地進(jìn)行內(nèi)存塊的合并操作。

  具體實(shí)現(xiàn)時(shí),可以將這二個(gè)鏈表的控制信息與用戶空間獨(dú)立存放,避免控制信息被意外地破壞。也可以利用物理塊本身來存放這些控制信息,得到更好的空間利用率和更好的靈活性。

  3.4 連續(xù)的內(nèi)存分配工作方式

  首先假定空間不再進(jìn)行分配的最小值為1KB,即當(dāng)空間分裂時(shí)所得的空閑區(qū)小于1KB時(shí),將不再進(jìn)行空間分配。

  分別保留大小為1KB、2KB、4KB、8KB字節(jié)等直到大于內(nèi)存總?cè)萘看笮〉逆湵怼@鐚?duì)于容量為1 024KB的內(nèi)存,有從1KB字節(jié)到2 048KB字節(jié)的12個(gè)鏈表。初始時(shí),所有內(nèi)存都是空閑的,2 048KB的鏈表包含一個(gè)1 024KB的空閑區(qū)(每個(gè)鏈表存放所有小于鏈表本身字節(jié)數(shù)、大于等于前一鏈表的字節(jié)數(shù)的內(nèi)存塊,2 048KB的鏈表存放所有小于2 048KB大于等于1 024KB的內(nèi)存塊)。其他的鏈表均為空,內(nèi)存最初的情況如圖1所示。為表示方便,圖中使用單鏈表來表示鏈接關(guān)系。實(shí)線表示物理塊鏈表指針,短劃線表示空閑塊鏈表指針,虛線表示空指針。對(duì)于物理塊鏈表,灰色塊表示已分配塊,白色塊表示空閑塊。

  當(dāng)有一個(gè)300KB的內(nèi)存請(qǐng)求(用A表示)產(chǎn)生時(shí),系統(tǒng)找到512KB鏈表的表頭。因?yàn)檫@個(gè)鏈表中可能包含滿足請(qǐng)求所需的最小空間。之后按照最佳適配(best fit)算法,在鏈表中搜尋是否有夠用的最小空閑區(qū)。此時(shí)512KB的鏈表為空,1 024KB的鏈表也為空,所以最終在2 048KB的鏈表中找到1 024KB可用空間。將此空間分割成大小分別為300KB和700KB的塊,700KB的塊(大于最小塊1KB)插入到1 024KB的鏈表中,300KB的塊則返回給請(qǐng)求A.

  接著,又有一個(gè)300KB(用B表示)和一個(gè)50KB(用C表示)的內(nèi)存請(qǐng)求。結(jié)果如圖2所示。

  現(xiàn)在塊B被釋放。此時(shí),根據(jù)物理塊鏈表,可以方便地找到與B鄰接的物理塊A和物理塊C.由于塊A和塊C都未被釋放,所以不需要進(jìn)行合并操作。因?yàn)閴KB的大小介于256KB和512KB之間,所以將塊B插入到512KB的空閑鏈表中,結(jié)果如圖3所示。

  接著,塊C被釋放。此時(shí)根據(jù)物理塊鏈表可知與塊C鄰接的為塊B和塊F,并且二塊都為空閑狀態(tài)。將塊B和塊F從512KB空閑塊鏈表中刪除,再將三塊合并成一個(gè)700KB的塊(用F表示)插入到1 024KB的空閑鏈表中,結(jié)果如圖4所示。

  最后當(dāng)塊A被釋放時(shí),塊A與塊F合并成1 024KB的塊,回到最初只有1 024KB空閑區(qū)的情況。

  4  結(jié)  論

  動(dòng)態(tài)內(nèi)存管理一直是計(jì)算機(jī)領(lǐng)域的一項(xiàng)重要技術(shù)。動(dòng)態(tài)內(nèi)存管理給用戶提供了比較大的自由度,用戶可以從系統(tǒng)分區(qū)中申請(qǐng)內(nèi)存塊,也可以從用戶內(nèi)存區(qū)申請(qǐng)內(nèi)存塊。這樣增加了系統(tǒng)的靈活性,同時(shí)也限制了大量碎片產(chǎn)生的可能(在不頻繁刪除建立系統(tǒng)內(nèi)存分區(qū)的前提下)。也增加了部分c 代碼的可移植性。
 

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉