成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	賴俊安 Lai, Chun-An
論文名稱：	輕量級環狀偵測器之設計與實作：應用於參考計數式之垃圾收集系統 Design and Implementation of a Lightweight Cycle Detector for Reference Counting Garbage Collection Systems
指導教授：	侯廷偉 Hou, Ting-Wei
學位類別：	碩士 Master
系所名稱：	工學院 - 工程科學系 Department of Engineering Science
論文出版年：	2004
畢業學年度：	92
語文別：	中文
論文頁數：	66
中文關鍵詞：	垃圾收集、參考計數、環狀偵測器
外文關鍵詞：	Jikes RVM
相關次數：	點閱：39 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　本論文針對參考計數法無法回收環狀結構的問題，發展一環狀偵測器，能夠比目前Lins演算法更具有效率。
　　本研究提出一個新穎的環狀偵測器，將目前環狀偵測器的時間複雜度，由O(2n)~O(3n)，下降至O(n)，雖然只有少量的垃圾環狀結構無法回收，但是卻有相當好的效率，因此本研究提出的演算法稱為輕量級環狀偵測器。
　　我們將輕量級演算法實作於IBM的Jikes RVM(Research Java Virtual Machine)，並且使用SPEC的效能測試程式，進行環狀偵測器的效能評估，與Bacon的演算法相較，輕量級演算法確實有相當高的效率，時間成本可以降低1/2到1/3，例如SPECJVM98有36%至57%的效能提升，而SPECjbb2000有56%至57%的效能提升。

　　In this thesis, we focus on a major disadvantage of reference counting technique — the inability to reclaim cyclic data structures. We have developed a novel cycle detector whose time complexity is O(n). Compared to cycle detectors based on Lins’ approach that need O(2n)~O(3n), ours is more efficient. We call it a “Lightweight Cycle Detector”.
　　For performance evaluation, we implemented the algorithm on a well-known Java execution environment, IBM Jikes RVM (Research Java Virtual machine), and used SPECjvm98 as the benchmark programs.
　　The measurements show that the Lightweight algorithm is indeed much more efficient than Bacon’s algorithm, a modern cycle detector based on Lins’ approach. The experiments also show that most of the garbage cycles generated by benchmark programs are collected successfully.

中文摘要........................................................................I
Abstract.......................................................................II
誌謝..........................................................................III
章節目錄.......................................................................IV
圖目錄.........................................................................VI
表目錄.......................................................................VIII
演算法列表.....................................................................IX
第一章	緒論.................................................................1
1 研究動機與背景..............................................................1
2 研究目的....................................................................2
3 章節概要....................................................................3
第二章	Java虛擬機器垃圾收集技術.............................................4
1 參考計數法..................................................................4
2 標誌-清除法.................................................................5
3 物件複製法..................................................................5
4 世代收集法..................................................................6
5 環狀偵測器相關工作..........................................................7
5.1 Bobrow技術................................................................7
5.2 Brownbridge強弱指標演算法.................................................7
5.3 標記—掃描法..............................................................8
5.4 Martinez區域標記—掃描法..................................................8
5.5 Lins延遲追蹤演算法........................................................8
5.6 Bacon演算法...............................................................9
5.7 Hou-Lin SCC-based演算法...................................................9
6 環狀偵測器演算法的採用.....................................................10
第三章	環狀偵測器設計......................................................11
1 環狀偵測器相關技術.........................................................11
1.1  Bacon環狀偵測器演算法...................................................11
1.2  非環狀結構的資料型態....................................................17
2 輕量級環狀偵測器...........................................................18
2.1 設計理念.................................................................18
2.2 術語與定義...............................................................18
2.3 資料結構.................................................................19
2.4 輕量級環狀偵測器演算法...................................................20
2-5 輕量級環狀偵測器虛擬碼與說明.............................................26
2.6 輕量級演算法的物件狀態...................................................29
3 複雜度分析.................................................................31
4 安全性與完整性.............................................................31
4.1 輕量級環狀偵測器安全性證明...............................................31
4.2 輕量級環狀偵測器完整性探討...............................................32
第四章	輕量級環狀偵測器實作與效能評估......................................34
1 Jikes RVM..................................................................34
1.1 Jikes RVM簡介............................................................34
2 實作環境...................................................................34
3 實作探討...................................................................35
4 效能測試程式...............................................................36
5測試平台....................................................................36
6 實驗參數設定...............................................................37
7 實驗結果...................................................................37
8 本章小結...................................................................58
第五章	結論與未來工作......................................................60
1 結論.......................................................................60
2 未來工作...................................................................60
參考文獻.......................................................................62
自述...........................................................................66


                                    

[1]A. W. Appel, ”Simple generational garbage collection and fast allocation,” Software Practice and Experience, vol.19 no.2, p.171-183, February 1989.

[2]H. Azatchi and E. Petrank,” Integrating generations with advanced reference counting garbage collectors,” In International Conference on Compiler Construction, Warsaw, Poland, p.185-199, April 2003.

[3]David F. Bacon , and V. T. Rajan, “Concurrent Cycle Collection in Reference Counted Systems,” Proceedings of the 15th European Conference on Object-Oriented Programming, p.207-235, June 2001.

[4]David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , and Stephen Smith, “Java without the coffee breaks: a nonintrusive multiprocessor garbage collector,” Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, Snowbird, Utah, p.92-103, June 2001.

[5]S. M. Blackburn and K. S. McKinley,” Fast garbage collection without a long wait,” Technical Report TR-CS-02-06, Dept. of Computer Science, Austrailian National University, November 2002.

[6]Stephen M. Blackburn, and Kathryn S. McKinley,” Ulterior reference counting: fast garbage collection without a long wait,” Proceedings of the 18th ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, p.344 – 358, Anaheim, California, October 2003.

[7]David R. Brownbridge.” Cyclic reference counting for combinatory machines,” Functional Programming Languages and Computer Architecture, p.273-288, Nancy, France, September 1985.

[8]Daniel G. Bobrow, “Managing Reentrant Structures Using Reference Counts,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol.2 no.3, p.269-273, New York, July 1980.

[9]T.W. Christopher, “Reference count garbage collection”, Software Practice and Experience, vol.14 no.6, p. 503-507, 1984.

[10]Tamar Domani, Gal Goldshtein, Elliot K. Kolodner, Ethan Lewis, Erez Petrank, and Dafna Sheinwald, “Thread-Local Heap for Java,” Proceedings of the International Symposium On Memory Management (ISMM), p.76 – 87, Berlin, Germany, June 2002.

[11]John DeTreville,” Experience with concurrent garbage collectors for Modula-2+,” Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.

[12]Fabrice Le Fessant, “Detecting distributed cycles of garbage in large-scale systems,” Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.200-209, Newport, Rhode Island, August 2001.

[13]Ting-We Hou, and Chin-Yang Lin, “A single-trace cyclic reference counting algorithm,” submitted for Information Processing Letters.

[14]R.E. Jones, and R.D. Lins, Garbage Collection Algorithms for Dynamic Memory Management, John Wiley & Sons, New York, (1996).

[15]Brain Kennedy,” The features of object oriented abstract type hierarchy(OATH),” Proceedings of Isenix C++ Conference, p.41-50, Usenix Association, April 1990.

[16]R.D. Lins,“An efficient algorithm for cyclic reference counting,” Information Processing Letters, vol.83 no.3, p.145-150, August 2002 .

[17]R.D. Lins, “Cyclic Reference counting with lazy mark-scan,” Information Processing Letters, vol.44 no.4, p.215-220, December 1992.

[18]R.D. Lins, “Generational cyclic reference counting,” Information Processing Letters, vol.46 no.1, p.19-20, April 1993.

[19]Y. Levanoni and E. Petrank, “A Scalable Reference Counting Garbage Collector,” Dept. of Computer Science, Technion, November 1999.

[20]Y. Levanoni and E. Petrank, “An on-the-fly reference counting garbage collector for Java”, ACM Conference Proceedings on Object–Oriented Programming Systems, Languages, and Applications, p. 367–380, Tampa, Florida, October, 2001.

[21]A.D. Martinez, R. Wachenchauzer, and R.D. Lins, “Cyclic reference counting with local mark-scan,” Information Processing Letters, v.34 n.1, p.31-35, February 1990.

[22]John McCarthy, “Recursive functions of symbolic expressions and their computation by machine,” Communications of the ACM, vol.3, no.4, p.184-195, New York, April 1960.

[23]E. J. H. Pepels, M. C. J. D. van Eekelen, and M. J. Plasmeijer, “A cyclic reference counting algorithm and its proof,” Technical Report 88-10, Computing Science Department, University of Nijmegen, 1988.

[24]T. Printezis and D. Detlefs, “A generational mostly-concurrent garbage collector,” Proceedings of the International Symposium On Memory Management (ISMM), p.143 - 154 Minneapolis, Minnesota, October, 2000.

[25]Srinivas Ashwin, Prasan Roy, S. Seshadri, Abraham Silberschatz, and S. Sudarshan, “Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting,” Very Large Data Bases Journal Springer-Verlag(VLDB). vol.7, no.3, p.179-193, New York, August 1998.

[26]Standard Performance Evaluation Corporation, SPECjvm98 Documentation, release 1.03 edition, March 1999.

[27]Standard Performance Evaluation Corporation, SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.

[28]Standard Performance Evaluation Corporation, http://www.spec.org/.

[29]Jon D. Salkild, “Implementation and analysis of two reference counting algorithms,” Master’s thesis, University College, Londo, 1987.

[30]Umesh Maheshwari, and Barbara Liskov, “Collecting distributed garbage cycles by back tracing,” Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.239-248, Santa Barbara, California, August 1997.

[31]Stephen C. Vestal, Garbage collection: “An Exercise in Distributed, Fault-Tolerant Programming,” PhD thesis, University of Washington, Seattle, WA, 1987.

[32]X. Ye and J. Keane, “Collecting cyclic garbage in distributed systems,” Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks, p.227-231, December 1997.

校內：立即公開
校外：2004-08-03公開

簡易檢索 / 詳目顯示

相關論文