博碩士論文查詢聯邦系統首頁 聯絡信箱 關於我們 加入我們

本論文已被瀏覽 45 次, [ 造訪詳細資料與全文 ] 33 次,[ 回到前頁查詢結果 ] [ 重新搜尋 ]

參考計數式記憶體管理系統之高效率環狀垃圾回收法

Efficient Cyclic Garbage Reclamation Approach for Reference Counted Memory Management Systems

作者:林錦陽
畢業學校:國立成功大學
出版單位:國立成功大學
核准日期:2009-11-17
類型:Electronic Thesis or Dissertation
權限:Copyright information available at source archive--National Cheng Kung University....

中文摘要

無法有效回收環狀垃圾(cyclic garbage)是參考計數式垃圾回收演算法(reference counting)的主要缺點。在支援參考計數之記憶體管理系統上,此問題有兩種普遍解法:(1) 整合基於追蹤法的全域型回收器(global tracing collector); (2) 採用基於追蹤法的區域型回收器(local tracing collector)。由於後者通常只需面對局部的物件而非整個堆積區(Heap)的物件,因此擴充性佳; 加上現今堆積區的空間普遍增加的趨勢,區域型回收器的優勢將逐漸明顯。
目前基於區域型回收器的相關研究幾乎都採用傳統的追蹤機制(稱為trial deletion),由於此機制的運作一般需要追蹤(存取)物件三次,導致了許多額外的運算負擔; 儘管許多相關研究著眼於減少需要分析的物件數目來改善效能,卻鮮少有研究訴諸於回收環狀垃圾的演算法本身。
此研究提出一個適用於參考計數式記憶體管理系統之高效率環狀垃圾回收法,這包含一個新穎的環狀垃圾回收演算法,該演算法能以更簡單有效的方式來處理環狀垃圾(在此稱為輕量級演算法); 而關鍵在於此演算法降低了追蹤物件的次數。相較於傳統偵測環狀垃圾的方法,此方法只需追蹤物件一次,偵測環狀垃圾的複雜度因而從3O(n)降至O(n)。
此研究更針對如何增加該輕量級演算法的效率與實用性,提出兩個改善方法:(1) 透過演算程序與資料結構的改進,解決原演算法的最壞情況(worst case),進而降低運算負擔; (2) 利用基於經驗式(heuristic)的混合演算法來解決輕量級演算法一個理論上的缺點,進而改善了整體效能。此外,相關的演算法虛擬碼以及其證明都被詳細陳述於此論文中。
為驗證在此所提之方法,此論文包括了一系列基於Jike虛擬機器 (Jikes Research Virtual Machine)以及SPECjvm98效能評估程式的實驗; 所有結果皆與另一個高效能的環狀垃圾回收器進行比較。根據實驗的結果,新提出之方法可改善約6–7%的整體程式執行時間,而且確實可有效解決真實應用程式的環狀垃圾問題。

英文摘要

The inability to collect cyclic garbage is generally considered the major weakness of reference counting. Reference counted systems handle this problem by incorporating either a global tracing collector or a local tracing collector that considers only the cycle candidates (i.e. objects that may contain cyclic garbage). Particularly, the latter has become a preferred one as it has better scalability and locality (i.e., there is no need to scan the entire heap).
Most of the local tracing collectors so far are based on a classical tracing scheme, called trial deletion. This scheme essentially requires three traversals over objects and thus may incur more tracing overhead and lower the potential for further developments. Lots of works have focused on improving the tracing cost by reducing the scope of cycle candidates, but few studies resort to the cycle collection procedure itself.
This research presents an efficient cyclic garbage reclamation approach for reference counted memory management systems. It includes a novel cycle collection algorithm, which is a local tracing algorithm but deals with the cycle problem in a simpler and more efficient way. The key is to minimize the number of traces over the cycle candidates; it can detect garbage cycles in a single traversal over objects, thereby significantly reducing the complexity from 3O(n) to O(n).
In addition, two further enhancements of the proposed algorithm are presented. The first introduces a data structure to increase the efficiency, solving the worst case of the proposed algorithm. The second is a heuristic-based hybrid approach for enhancing the practicability of the proposed algorithm. It not only addresses a theoretical problem of the algorithm, but also significantly improves the overall efficiency. Moreover, the pseudo-code of the algorithms and the correctness proofs are described in detail.
To evaluate the effectiveness of all of these methods, a set of experiments are conducted based on Jikes Research Virtual Machine and SPECjvm98 benchmarks. The results show that this approach can cope with the cycle problem for large programs and attain better application performance on average around 6 7% faster, when compared to a modern state-of-the-art cycle collector based on the trial deletion.


口試委員 - 謝錫堃

口試委員 - 陳祈男

口試委員 - 蔡尚榮

口試委員 - 楊武

口試委員 - 曾黎明

指導教授 - 侯廷偉


 

計畫贊助者: