在垃圾收集系統中，參考計數法無法回收環狀垃圾結構，需另外搭配環狀偵測器使用。本論文針對Lin-Hou所提之輕量級環狀垃圾偵測演算法(Lightweight Cyclic Reference Counting Algorithm, LW-CRC)進行一系列改良。LW-CRC兼具高效率及實用性，但無法回收特定的環狀垃圾，本研究在盡量不影響其效率的前提下，設法改善無法完全回收環狀垃圾的情形。此外，本論文也提出一個以Strongly-Connected Component(SCC)為基礎之環狀垃圾偵測演算法(SCC-CRC)，該演算法具有良好之效能且不會有無法回收環狀垃圾的情形。
　　這兩系列演算法的概念是基於減少物件圖形追蹤的次數，相較於目前普遍使用的三色追蹤法，時間複雜度可從O(2n)~O(3n)改善至O(n)~O(2n)。
　　本研究已實作於Jikes RVM(Research Java Virtual Machine)，並以SPECjvm 98效能評估程式來進行實驗量測，測試結果依測試程式及記憶體設定的不同，但整體而言，本研究所提出的演算法確實能比傳統方法有更出色的效能表現。

In garbage collection systems, reference counting technique can not reclaim cyclic garbage. It is often complemented by a cycle detector. In this thesis, we first try to improve the LW-CRC (Lightweight Cyclic Reference Counting) algorithm proposed by Lin-Hou. The original LW-CRC algorithm is a practical approach. However, there exist few cases that can not be properly handled in theory. The algorithms proposed herein relieve such a problem without affecting the practicality, where more cyclic garbage can be collected. In addition, we develop a new cycle collection algorithm based on finding strongly connected components (SCC), denoted SCC-CRC. It is a complete algorithm and it has good performance.
The main idea of the proposed algorithms is to reduce the number of traces over objects. Compare with the tri-color algorithm, a well-known cycle collection algorithm, our algorithms reduce the time complexity from O(2n) ~ O(3n) to O(n) ~ O(2n).
We implemented the algorithms on Jikes RVM (Research Java Virtual Machine), and used SPECjvm 98 as the benchmark programs. The experimental results demonstrate that the proposed algorithms are more practical and efficient, compared to the tri-color algorithm.

[1] Bowen Alpern, C. R. Attanasio, Anthony Cocchi, Derek Lieber, Stephen Smith, Ton Ngo, John J. Barton, Susan Flynn Hummel, Janice C. Sheperd, Mark Mergen, “Implementing jalapeño in Java”, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pp.314-324, 1999.
[2] David F. Bacon and V. T. Rajan, “Concurrent cycle collection in reference counted systems.”, In Proceedings of 15th European Conference on Object-Oriented Programming, pp.207-235, 2001.
[3] Stephen M. Blackburn, Perry Cheng, Kathryn S. McKinley, “Oil and water? High performance garbage collection in Java with MMTk.”, In International Conference on Software Engineering, pp.137-146, 2004.
[4] Stephen M. Blackburn, Kathryn S. McKinley, “Ulterior reference counting: Fast garbage collection without a long wait. In ACM Conference on Object-Oriented Programming Systems”, Languages, and Applications, Anaheim, pp.244-358, 2003.
[5] George E. Collins., “A method for overlapping and erasure of lists. “, Communications of the. ACM, vol.3, issue12, pp.655-657, 1960.
[6] L. Peter Deutsch, Daniel G. Bobrow, “An efficient incremental automatic garbage collector.”, Communications of the ACM, vol.19, issue9, pp.522-526, 1976.
[7] Yossi Levanoni and Erez Petrank, “A scalable reference counting garbage collector.”, Technical Report CS-0967, Technion Israel Institute of Technology, Haifa, Israel, 1999.
[8] Yossi Levanoni and Erez Petrank, “An on-the-fly reference counting garbage collector for Java.”, In ACM Conference Proceedings on Object-Oriented Programming Systems, Languages, and Applications, pp.367-380, 2001.
[9] Henry Lieberman, Carl Hewitt, “A real-time garbage collector based on the lifetimes of objects”, Communications of the ACM, vol.26, issue 6, pp.419-429, 1983.
[10]Chin-Yang Lin and Ting-Wei Hou, “A Lightweight Cyclic Reference Counting Algorithm”, Lecture Notes in Computer Science, vol.3947, pp.346-359, 2006.
[11] Rafael Dueire Lins, “An efficient algorithm for cyclic reference counting.”, Information Processing Letters, vol.83, pp.145-150, 2002.
[12] Rafael Dueire Lins, “Generational cyclic reference counting.”, Information Processing Letters, vol.46, pp.19-20, 1993.
[13] Rafel D. Lins, “Cyclic Reference counting with lazy mark-scan,” Information Processing Letters, Vol. 44, issue 4, pp.215-220, December 1992.
[14] A. D. Martínez, R. Wachenchauzer, R. D. Lins, “Cyclic reference counting with local mark-scan.”, Information Processing Letters, vol.34, issue 1, pp.31-35, 1990.
[15] John McCarthy, “Recursive functions of symbolic expressions and their computation by machine.” Communications of the. ACM, vol.3, pp.184-195, 1960.
[16] Marvin Minsky, “A LISP garbage collector algorithm using serial secondary storage.”, Technical Report Memo 58 (rev.), Project MAC, MIT, Cambridge, MA, 1963.
[17] Standard Performance Evaluation Corporation. SPECjvm98.
[18] Robert E. Tarjan, “Depth-first search and linear graph algorithms”, SIAM J. of Computing, vol 1, pp.146-160, 1972.