一種基於用途編號的用戶程序內存分配及批量回收的方法及裝置製造方法
2023-06-19 19:04:26
一種基於用途編號的用戶程序內存分配及批量回收的方法及裝置製造方法
【專利摘要】本發明提供了一種基於用途編號的用戶程序內存分配及批量回收的方法及裝置，對於一類需要逐漸地進行內存分配，而同時釋放所有之前所分配空間的功能需求，提供一種更高效率的內存分配及回收方法，使得無論在內存分配過程中有多少次分配操作，都可以在釋放空間時一次完成，極大的改善了此類應用對系統資源的消耗，提高了內存分配方法的效率。
【專利說明】一種基於用途編號的用戶程序內存分配及批量回收的方法及裝置
【技術領域】
[0001]本發明涉及計算機作業系統中內存管理【技術領域】，尤其涉及在分布式計算中對細粒度任務進行離散的內存分配以及批量內存回收的方法及裝置。
【背景技術】
[0002]在計算機系統中，內存的分配和回收是一種核心功能，支持作業系統和應用程式動態的獲取和釋放系統內存資源，作業系統內核中的內存分配策略服務於所有內核中的功能，是一種通用的內存分配策略。
[0003]常見內存分配算法及優缺點如下:
[0004](I)首次適應算法。使用該算法進行內存分配時，從空閒分區鏈首開始查找，直至找到一個能滿足其大小要求的空閒分區為止。然後再按照作業的大小，從該分區中劃出一塊內存分配給請求者，餘下的空閒分區仍留在空閒分區鏈中。
[0005]該算法傾向於使用內存中低地址部分的空閒分區，在高地址部分的空閒分區很少被利用，從而保留了高地址部分的大空閒區。顯然為以後到達的大作業分配大的內存空間創造了條件。缺點在於低址部分不斷被劃分，留下許多難以利用、很小的空閒區，而每次查找又都從低址部分開始，這無疑會增加查找的開銷。
[0006](2)循環首次適應算法。該算法是由首次適應算法演變而成的。在為進程分配內存空間時，不再每次從鏈首開始查找，而是從上次找到的空閒分區開始查找，直至找到一個能滿足要求的空閒分區，並從中劃出一塊來分給作業。該算法能使空閒中的內存分區分布得更加均勻，但將會缺乏大的空閒分區。
[0007](3)最佳適應算法。該算法總是把既能滿足要求，又是最小的空閒分區分配給作業。
[0008]為了加速查找，該算法要求將所有的空閒區按其大小排序後，以遞增順序形成一個空白鏈。這樣每次找到的第一個滿足要求的空閒區，必然是最優的。孤立地看，該算法似乎是最優的，但事實上並不一定。因為每次分配後剩餘的空間一定是最小的，在存儲器中將留下許多難以利用的小空閒區。同時每次分配後必須重新排序，這也帶來了一定的開銷。
[0009](4)最差適應算法。最差適應算法中，該算法按大小遞減的順序形成空閒區鏈，分配時直接從空閒區鏈的第一個空閒分區中分配(不能滿足需要則不分配)。很顯然，如果第一個空閒分區不能滿足，那麼再沒有空閒分區能滿足需要。這種分配方法初看起來不太合理，但它也有很強的直觀吸引力:在大空閒區中放入程序後，剩下的空閒區常常也很大，於是還能裝下一個較大的新程序。
[0010]最壞適應算法與最佳適應算法的排序正好相反，它的隊列指針總是指向最大的空閒區，在進行分配時，總是從最大的空閒區開始查尋。
[0011]該算法克服了最佳適應算法留下的許多小的碎片的不足，但保留大的空閒區的可能性減小了，而且空閒區回收也和最佳適應算法一樣複雜。[0012]而內核中的不同功能對內存的需求各不相同,對內存空間的使用也存在不同的規律，使用一種通用的存儲管理方法會導致內存利用率降低、內存碎片逐漸嚴重。
[0013]對於內核中的一些模塊，其在申請內存的過程中是逐漸獲取的，不斷增加其持有的內存資源，而在這個模塊完成某項功能，將要釋放資源的時候，則希望在同一時刻釋放所有其持有的內存資源。現有的內存分配方法要求釋放的內存對應分配時的位置和大小，對於多次分配而獲得的較大內存空間，也需要逐個進行釋放。這就導致了內存釋放時出現大量集中的操作，帶來較大的開銷。
[0014]常見內存回收算法及優缺點如下:
[0015]引用計數算法的優點和缺陷同樣明顯。這一算法在執行垃圾收集任務時速度較快，但算法對程序中每一次內存分配和指針操作提出了額外的要求(增加或減少內存塊的引用計數)。更重要的是，引用計數算法無法正確釋放循環引用的內存塊。
[0016]標記-清除算法的執行過程分為「標記」和「清除」兩大階段。這種分步執行的思路奠定了現代垃圾收集算法的思想基礎。與引用計數算法不同的是，標記-清除算法不需要運行環境監測每一次內存分配和指針操作，而只要在「標記」階段中跟蹤每一個指針變量的指向。用類似思路實現的垃圾收集器也常被後人統稱為跟蹤收集器。伴隨著Lisp語言的成功，標記-清除算法也在大多數早期的Lisp運行環境中大放異彩。儘管最初版本的標記-清除算法在今天看來還存在效率不高(標記和清除是兩個相當耗時的過程)等諸多缺陷。
[0017]為了解決標記-清除算法在垃圾收集效率方面的缺陷，M.L.Minsky於1963年發表了著名的論文「一種使用雙存儲區的Lisp語言垃圾收集器(A LISP Garbage CollectorAlgorithm Using Serial Secondary Storage)」。]^.L.Minsky在該論文中描述的算法被人們稱為複製算法，它也被M.L.Minsky本人成功地引入到了 Lisp語言的一個實現版本中。
[0018]分區、複製的思路不僅大幅提高了垃圾收集的效率，而且也將原本繁紛複雜的內存分配算法變得前所未有地簡明和扼要。既然每次內存回收都是對整個半區的回收，內存分配時也就不用考慮內存碎片等複雜情況，只要移動堆頂指針，按順序分配內存就可以了。在垃圾收集技術中，複製算法提高效率的代價是人為地將可用內存縮小了一半。
[0019]標記-整理算法是標記-清除算法和複製算法的有機結合。標記-整理算法的總體執行效率高於標記-清除算法，又不像複製算法那樣需要犧牲一半的存儲空間，這是一種非常理想的方法。在許多現代的垃圾收集器中都使用了標記-整理算法或其改進版本。
【發明內容】
[0020]本發明的目的為提供一種基於用途編號的對於離散分配的內存空間進行批量回收的方法及裝置，提高了批量內存釋放時的效率，從而消除在集中釋放內存時帶來的較大開銷。
[0021]為解決上述技術問題，本發明提供了一種基於用途編號的對於離散分配的內存空間進行批量回收的方法及裝置，如圖1所示，所述方法包括:
[0022]內存分配接口。這一接口的調用者需要提供兩個參數。第一個參數是需要分配的內存空間的大小，以字節為單位。第二個參數是一個任意的數值，用於區分內存的用途，相同的數值表示所分配的內存用於相同的用途，並且將在使用結束後一起回收。這個數值被稱為「用途編號」
[0023]內存回收接口。這一接口的調用者需要提供一個參數。這個參數對應在內存分配時所提供的用途編號，調用內存回收接口表示把參數數值所對應的所有內存空間全部回收，供未來分配使用。
[0024]內存管理模塊。為每一個出現過的用途編號預留一個連續的內存空間，不同的用途編號對應不用的內存空間。一個用途之內的內存申請在自己所屬的空間之中申請內存。一個用途編號所對應的預留內存空間被稱為一個子內存池，相應地，一個子內存池服務於一個用途。內存管理結構如圖2所示。
【專利附圖】
【附圖說明】
[0025]圖1為內存分配裝置的結構圖。
[0026]圖2為內存管理模塊結構圖。
【具體實施方式】
[0027]對於一個子內存池，其中的存儲分配是順序的。一個空閒空間指針指向未分配內存段的開始。分配操作採用計算機的原子操作指令對空閒空間指針進行操作，返回當前空閒空間的地址，並向後移動所申請的大小，使其指向新的空閒空間的開始地址。
[0028]當子內存池的空間不足以分配新的元素時，管理模塊調用作業系統的底層內存管理功能，為子內存池擴容，即申請更多的空間，新申請的空間和子內存池是連續的，保證內存池中的地址空間總是連續的。
[0029]關閉子內存池表示不再繼續使用一個用途編號所對應的內存資源。關閉一個內存池的時候，整個內存池所佔用的內存空間被清除，交回作業系統管理。
[0030]一個子內存池中的存儲單元不能單獨回收。
[0031]回收子內存池表示將一個子內存池中的存儲空間全部重置，交還給內存管理模塊，但是這一子內存池還要繼續為後續的申請繼續服務，子內存池所包含的內存資源不會交還給作業系統。
[0032]在系統內存資源不足時，內存管理模塊會開始進行強制內存回收操作。強制內存回收操作步驟如下:
[0033]隨機選擇一個子內存池。檢查當前子內存池已經預留的內存空間。檢查當前子內存池已經分配的內存空間。如果已經分配的內存空間比已經預留的內存空間小，表示當前內存池並沒有完全被使用，可以對這個子內存池進行回收操作。
[0034]回收操作通過調用作業系統的內存管理函數將子內存池實際佔用的內存邊界調整到實際分配的大小，從而減小了實際佔用的內存大小。
[0035]如果當前系統的空閒內存能夠滿足要求，則完成強制內存回收操作。如果當前還不能獲得足夠的內存空間，則再次隨機選取一個子內存池進行上述的操作。如此迭代操作，直到回收了足夠的內存空間。如果已經遍歷了所有的子內存池，依然沒有獲得足夠的內存空間，則報告內存不足。
【權利要求】
1.內存分配接口。這一接口的調用者需要提供兩個參數。第一個參數是需要分配的內存空間的大小，以字節為單位。第二個參數是一個任意的數值，用於區分內存的用途，相同的數值表示所分配的內存用於相同的用途，並且將在使用結束後一起回收。這個數值被稱為「用途編號」。
2.內存回收接口。這一接口的調用者需要提供一個參數。這個參數對應在內存分配時所提供的用途編號，調用內存回收接口表示把參數數值所對應的所有內存空間全部回收，供未來分配使用。
3.內存管理模塊。為每一個出現過的用途編號預留一個連續的內存空間，不同的用途編號對應不用的內存空間。一個用途之內的內存申請在自己所屬的空間之中申請內存。一個用途編號所對應的預留內存空間被稱為一個子內存池，相應地，一個子內存池服務於一個用途。
4.對於一個子內存池，其中的存儲分配是順序的。一個空閒空間指針指向未分配內存段的開始。分配操作採用計算機的原子操作指令對空閒空間指針進行操作，返回當前空閒空間的地址，並向後移動所申請的大小，使其指向新的空閒空間的開始地址。
5.回收子內存池表示將一個子內存池中的存儲空間全部重置，交還給內存管理模塊，但是這一子內存池還要繼續為後續的申請繼續服務，子內存池所包含的內存資源不會交還給作業系統。
【文檔編號】G06F12/02GK103488577SQ201310430994
【公開日】2014年1月1日 申請日期:2013年9月22日 優先權日:2013年9月22日
【發明者】吳興博, 龍翔, 王雷 申請人:北京航空航天大學