[發明專利]用于持久和穩固的存儲設備分配的系統和方法

無效

• 申請號: 01104511.6
• 申請日: 2001-02-14
• 公開（公告）號: CN1309354A
• 公開（公告）日: 2001-08-22
• 發明（設計）人: 詹姆斯·R·H·查林杰;阿魯·K·利恩格爾
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F12/08
• 分類號: G06F12/08
• 代理公司: 中國國際貿易促進委員會專利商標事務所
• 代理人: 酆迅

本發明涉及計算機存儲方法和系統，更具體地涉及用于穩固動態存儲分配的方法和系統。

許多計算機需要動態地分配存儲器。操作系統使用動態存儲分配為執行程序而分配存儲器。動態存儲分配的另一個例子可以包括用于存儲網絡數據的網絡服務器。在很多情況下，在發出請求之前，所請求的存儲尺寸是不知道的。動態分配的存儲塊的生命周期也是不知道的。

已經花費了相當多的精力來開發主存儲器的有效動態存儲分配算法。但對盤上的有效動態存儲分配算法的開發所花費精力卻少得多。

有多種理由說明盤上的有效動態存儲分配的重要性。在很多情況下，主要的是具有能在時間上持久的即使在關機后也持久的數據。盤存儲器提供持久存儲。盤存儲器也提供容錯存儲；當系統垮臺以致主存儲器內容丟失之后，經常仍能保持存于盤上的信息。盤存儲器的另一個優點是有可能以比主存儲器更合理的價格提供更多的盤存儲器。因此它可用于存儲主存儲器內存放不下的信息。

參照圖1，最初適配系統分配找到的第一塊足夠大的能滿足存儲請求的存儲塊(的全部或一部分)。對于“7”的存儲請求，最初適配返回B1，因為這是遇到的能夠滿足請求的第一塊。最佳適配系統分配足夠大以能滿足存儲請求的最小存儲塊(的全部或一部分)。圖1中，由于“7”在塊B3(它的容量為8)中適配得最佳，因此返回B3。

參照圖2，在二進制伙伴系統中，塊尺寸為2的冪(例如4和4,8和8等)。許多動態存儲分配器(DSA)保持一個或多個空塊表。這類表稱為空表，例如空塊表。不同尺寸的塊有不同的空表。也存在用于分配其他尺寸的塊的伙伴系統。在1996年10月在Proceedings?of?IEEEFrontiers′96上刊登的Arun?Iyengar所著的名為“動態存儲分配算法的可改變規模性”的文章以及本說明書所附參考文獻中都很好地回顧了動態存儲分配的現有技術。

動態存儲分配器(DSA)能夠使用不同方法來匯并鄰近空塊。一個方案是使用立即匯并，其中在釋放塊時立即將該釋放塊與鄰近空塊匯并，如圖3所示。在圖3中，在每塊中都標明塊尺寸。正的尺寸值標明空塊，而負的尺寸值標明分配塊。

參照圖4，另一個方案包括延遲匯并。當使用延遲匯并時，在釋放后鄰近的空塊并不自動地合并。相反，到一定時候(例如當無法分配一個足夠大能滿足請求的塊時)，DSA將掃描存儲設備中的各塊以及如圖4中所示地將鄰近塊合并。

存儲碎塊是DSA浪費的存儲區。內部存儲碎塊是當使用大于所請求尺寸的空塊來滿足請求時(例如使用尺寸為32的塊來滿足對尺寸為25的塊的請求時)損失的存儲區。當空塊與分配塊交織時出現外部存儲碎塊。在這種情況下，即使有大于b字節的空間也無法滿足對b字節的分配請求，因為最大的連續空塊小于b字節。

以上引用的“動態存儲分配算法的可改變規模性”文章中所描述的多空表適配Ⅰ(MFLFⅠ)使用多個按照尺寸組織的空表。小塊的空表稱為快表。大塊的空表稱為雜項表。當保持單個雜項表時，MFLF?Ⅰ退化為稱為快適配的存儲分配系統。

參照圖5，其中顯示快適配技術。在此系統中，尺寸為16以下的塊放在快表中；可以改變快表數量以便針對不同請求分布將性能優化。在此例中，當2≤s≤16(2是最小塊尺寸)時，通過檢查尺寸為s的快表來分配尺寸為s的塊。如此表不空，則表中第一塊可用于滿足請求。注意到可能有對應于單元尺寸的倍數的塊尺寸的快表。例如，在圖2中，單元尺寸是1。如果單元尺寸是1000，則可以使用塊尺寸為1000、2000、3000、…、16000的快表(總共有16個快表)。MFLFⅠ使用延遲匯并。存儲區分為工作存儲區12和尾區14，如圖5中所示。工作存儲區12包括分配塊和空表中的塊。尾區14包括存儲區一端的未分配存儲區中的連續塊。最初，在分配任何塊之前，尾區包括所有可分配存儲區，及空表是空的。空表包括快表和雜項表，其中雜項表用于較大存儲塊。塊13包括一個尺寸(由塊13中的數目所標示)。當檢查一個或多個空表后發現無法滿足請求時，可從尾區14中分配從而滿足請求。尾區指針(tailptr.)標示尾區14的始端。當釋放已分配塊時即將它填放入空表。