[發(fā)明專利]內(nèi)存管理方法和設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 201680086965.4
• 申請(qǐng)日: 2016-09-28
• 公開（公告）號(hào): CN109690498B
• 公開（公告）日: 2020-12-25
• 發(fā)明（設(shè)計(jì)）人: 亞歷山大·亞歷山德羅維奇·西馬克;彼得·謝爾蓋耶維奇·克林諾夫;張學(xué)倉
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02
• 代理公司: 廣州三環(huán)專利商標(biāo)代理有限公司 44202
• 代理人: 熊永強(qiáng);李稷芳

本發(fā)明提供一種內(nèi)存管理方法和內(nèi)存管理設(shè)備，用于使用多個(gè)獨(dú)立的空閑鏈表來執(zhí)行內(nèi)存分配和/或內(nèi)存解分配，所述多個(gè)獨(dú)立的空閑鏈表提供多個(gè)內(nèi)存塊的信息，其中，所述內(nèi)存分配和/或內(nèi)存解分配根據(jù)內(nèi)存塊的狀態(tài)執(zhí)行，并且所述內(nèi)存塊的狀態(tài)包括：使用狀態(tài)，指示處于使用狀態(tài)的內(nèi)存塊正在被使用并且不可用于分配；鏈接狀態(tài)，指示處于鏈接狀態(tài)的內(nèi)存塊未被使用，且在多個(gè)獨(dú)立的空閑鏈表的一個(gè)空閑鏈表中被鏈接，并且可用于分配；空閑狀態(tài)，指示處于空閑狀態(tài)的內(nèi)存塊未被使用，并且在所述多個(gè)獨(dú)立的空閑鏈表的任何一個(gè)空閑鏈表內(nèi)都未被鏈接，并且不可用于分配。

技術(shù)領(lǐng)域

本發(fā)明提供一種內(nèi)存管理方法和設(shè)備，用于使用多個(gè)獨(dú)立的空閑鏈表來執(zhí)行內(nèi)存分配和/或內(nèi)存解分配。此外，本發(fā)明涉及對(duì)應(yīng)排列的計(jì)算機(jī)程序產(chǎn)品和對(duì)應(yīng)排列的計(jì)算機(jī)可讀介質(zhì)。

背景技術(shù)

內(nèi)存管理在所有計(jì)算系統(tǒng)和設(shè)備中都必不可少。在計(jì)算系統(tǒng)或設(shè)備上執(zhí)行計(jì)算以及在計(jì)算系統(tǒng)或設(shè)備中處理數(shù)據(jù)時(shí)都需要內(nèi)存資源。內(nèi)存資源管理通常由內(nèi)存分配器實(shí)現(xiàn)。典型的內(nèi)存分配器是一個(gè)單獨(dú)的內(nèi)存記帳工具，其具有高效的接口來分配和解分配大小符合要求的內(nèi)存塊。在計(jì)算系統(tǒng)或設(shè)備中，請(qǐng)求內(nèi)存分配器提供一定大小的塊，從而執(zhí)行一個(gè)或多個(gè)進(jìn)程和/或?qū)?shù)據(jù)存儲(chǔ)在計(jì)算系統(tǒng)或設(shè)備中。內(nèi)存分配器評(píng)估該請(qǐng)求，檢查是否有足夠的內(nèi)存來滿足請(qǐng)求，準(zhǔn)備已經(jīng)定位好的塊并返回塊地址來響應(yīng)該請(qǐng)求。稍后，通知內(nèi)存分配器不再使用某一內(nèi)存塊。為響應(yīng)此信息，內(nèi)存分配器回收該塊并可選地執(zhí)行其他操作，例如合并。所有內(nèi)存分配器的共同問題是內(nèi)存細(xì)分(例如，參見Wilson,P.R.、Johnstone,M.S.、Neely,M.、Boles,D.(1995)“動(dòng)態(tài)存儲(chǔ)分配：調(diào)查和關(guān)鍵回顧”。內(nèi)存管理：國際研討會(huì)，Iwmm'95，英國金洛斯，1995年9月27至29日：會(huì)議錄)，也即，有多個(gè)小塊可用時(shí)，但顯然無法滿足提供單個(gè)更大塊的內(nèi)存請(qǐng)求。為了避免細(xì)分，內(nèi)存分配器執(zhí)行相鄰塊的歸并，也稱為合并。一般認(rèn)為合并是低效的，而且有相當(dāng)大的開銷。許多內(nèi)存分配器的合并方案顯著不同，這些合并模式都明確地旨在更高效地執(zhí)行合并(例如，參見US2003/0084263A1、US7,610,468B2、US5,742,793A)。

人們對(duì)于不同的內(nèi)存分配器已經(jīng)有了數(shù)十年的了解。盡管它們的特性不同，但其中很多都具有一些共同的特性，例如，都有塊邊界標(biāo)記，以支持合并；同時(shí)有鏈接字段，以組成空閑塊的鏈表。一些內(nèi)存分配器也使用查找表，區(qū)別地對(duì)待小目標(biāo)，從不進(jìn)行拆分或合并，甚至使用特殊的數(shù)據(jù)結(jié)構(gòu)和算法，如快速列表和延遲合并以實(shí)現(xiàn)更好的性能(例如，參見Wilson,P.R.、Johnstone,M.S.、Neely,M.、Boles,D.(1995)“動(dòng)態(tài)存儲(chǔ)分配：調(diào)查和關(guān)鍵回顧”。內(nèi)存管理：國際研討會(huì)，Iwmm'95，英國金洛斯，1995年9月27至29日：會(huì)議錄)。

這類中的最簡單的內(nèi)存分配器使用空閑鏈表的數(shù)組，每個(gè)鏈表只保留特定大小的空閑塊。空閑塊變得邏輯獨(dú)立，但并非因其大小的物理上獨(dú)立，因而顯著降低查找成本。此方案的更高級(jí)變形方案中，使用邊界標(biāo)記和雙鏈表以支持一般拆分和合并。簡單的設(shè)計(jì)選擇是對(duì)于嘗試與其相鄰塊合并的塊進(jìn)行回收，并且一進(jìn)行解分配就立即合并，但也可以使用延遲機(jī)制。

已知要實(shí)現(xiàn)立即合并，會(huì)造成每個(gè)小塊一進(jìn)行解分配時(shí)就重復(fù)執(zhí)行合并，并且一進(jìn)行由此產(chǎn)生的分配就很快重復(fù)地拆分合并的塊。延遲合并解決了這個(gè)問題，僅在某些情況下進(jìn)行合并，并一次運(yùn)行多個(gè)塊。這種方法仍然遇到了一些困難，因?yàn)閴K必須先定位并且合并也意味著從塊的空閑鏈表中抽取塊，這導(dǎo)致鏈接塊的內(nèi)存更新。在最壞的情況下，這些都是非本地內(nèi)存更新。作為替代解決方案，稱為快速列表的緩存數(shù)據(jù)結(jié)構(gòu)可用于新回收的塊。將最近釋放的塊放入其中，各個(gè)塊之間不建立鏈接，因此造就相當(dāng)寬松的合并機(jī)會(huì)。然而，這必然會(huì)增加最終設(shè)計(jì)和實(shí)現(xiàn)內(nèi)存分配器的復(fù)雜性。

針對(duì)上面提到的概念，有兩種已知的示例性實(shí)現(xiàn)方式，在下文中更詳細(xì)地進(jìn)行介紹。