垃圾收集(garbage collection)裡的引用計數法(reference counting)，在種種情況下顯 示，是很適合用在即時系統(real-time system)的一種垃圾收集技術。但是，引用計數法所需要的環狀結構偵測(cycle detection)步驟會增加很多掃描(scanning)程式計算圖形
(computation graph)的負擔(overhead)。這種特性降低了垃圾收集的效率也增加了垃圾收集所需要的暫停時間(pause time)。我們的研究指出，可以利用Java 語言是一種強制型別語言(strongly- typed language)的特性，來降低環狀結構偵測的負擔。
此篇研究裡，我們提出兩種方法以增進引用計數演算法的效能：第一，為了能夠善加利用使用者程式其中的語意(semantic)，我們提出了一個全新的連通性模型(connectivity model) ，用以表現出程式裡物件的行為(behavior)，並且分析了SPECjvm98與DaCapo benchmarks， 將這兩種benchmarks的連通性模型一併予以分析。第二，為了減少掃描程式計算圖形的負擔，我們利用Java是強制型別語言的特性，改進了現有的引用計數演算法，使效率更好。
我們分析了修改前後的演算法，監測它們對垃圾收集程式的影響程度。實驗結果顯示，使用我們改進過後的方法，需經過環狀結構偵測器的物件數目大幅減少， 大約平均可以減少39.0%。

Reference counting strategy is, in many respects, a natural choice for real-time garbage collection, but the cycle detection phase which is required to ensure the correctness for reference counting algorithm can introduce heavy scanning overheads. This degrades the efficiency and inflates the pause times required for garbage collection. Our work has shown that the strongly-typed reference features in Java language can be utilized to reduce these overheads effectively.
In this thesis, we present two approaches to improve the efficiency of reference counting algorithm. First, in order to make better use of the semantics of a given program, we introduce a novel connectivity model to predict the objects behaviors in a program and make an analysis for the percentage of different connectivity types in SPECjvm98 benchmarks. Second, in order to reduce the scanning overheads, we present an enhancement for current cyclic reference counting algorithm, by utilizing strongly-typed reference features of Java language.
We analyze the efficiency of these two methods, and demonstrate their potential impact on garbage collection. Our results show that when applying our improvements, the number of objects scanned during cycle collection phase, can be reduced by an average of 39.0%.

[1] B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P. Cheng, J. D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. Shepherd, S. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalape?no virtual machine, IBM System Journal, 39(1), pages 211–238, Feb. 2000.
[2] B. Alpern, C. R. Attanasio, A. Cocchi, D. Lieber, S. Smith, T. Ngo, J. J. Barton, S. F. Hummel, J. C. Sheperd, and M. Mergen, Imple-menting Jalape?no in Java, in Proceedings of the 1999 ACM SIG-PLAN Conference on Object-Oriented Programming Systems, Lan-guages & Applications, OOPSLA ’99, Denver, Colorado, November 1-5, 1999, volume 34(10) of ACM SIGPLAN Notices, pages 314–324, Oct. 1999.
[3] S. Ashwin, P. Roy, S. Seshadri, A. Silberschatz, and S. Sudarshan, Garbage collection in object oriented databases using transactional cyclic reference counting, in VLDB'97, Proceedings of 23rd Inter-national Conference on Very Large Data Bases, pages 366-375, 1997.
[4] T. H. Axford, Reference counting of cyclic graphs for functional programs, Computer Journal, 33(5), pages 466-470, 1990.
[5] D. F. Bacon, C.R. Attanasio, H. B. Lee, V. T. Rajan, and S. Smith, Java without the coffee breaks: a nonintrusive multiprocessor gar-bage collector, in Proceedings of the SIGPLAN Conference on Pro-gramming Language Design and Implementation, Snowbird, Utah, volume 36(5), pages 92-103, June 2001,.
[6] D. F. Bacon and V. T. Rajan, Concurrent cycle collection in refer-ence counted systems, in Proceedings of 15th European Conference on Object-Oriented Programming, ECOOP 2001, Budapest, Hungary, pages 207-235, June 2001.
[7] S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovi’c, T. VanDrunen, D. von Dincklage, and B. Wiedermann, The DaCapo benchmarks: Java benchmarking devel-opment and analysis, in Conference on Object-Oriented Program-ming, Systems, Languages, and Applications, pages 169-190, 2006.
[8] S. Blackburn, K. McKinley, Ulterior reference counting: fast gar-bage collection without a long wait, in Conference on Ob-ject-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2003, 38(11), pages 344-358, 2003.
[9] D. G. Bobrow, Managing re-entrant structures using reference counts, ACM Transactions on Programming Languages and Systems, 2(3), pages 269-273, July 1980.
[10] H. J. Boehm, Re: reference counting (was re: searching method for incremental garbage collection), USENET, November 1994.
[11] H. Boehm, The space cost of lazy reference counting, in Proceed-ings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL, Venice, Italy, pages 210-219, Jan. 2004.
[12] D. R. Brownbridge, Cyclic reference rounting for combinator ma-chines, in Proceeding of Functional Programming Languages and Computer Architecture, pages 273-288, Sept. 1985.
[13] T. W. Christopher, Reference counting garbage collection. Soft-ware Practice and Experience 14(6), pages 503-507, June 1984.
[14] G. E. Collins, A method for overlapping and erasure of lists, Communication of the ACM, 3(12), pages 655-657, Dec. 1960.
[15] F. Dehne, R. D. Lins, Distributed cyclic reference counting, Can-ada-France Conference on Parallel and Distributed Computing, pages 95-100, 1994.
[16] J. DeTreville, Experience with concurrent garbage collectors for Modula-2+, technical report 64, DEC Systems Research Center, Palo Alto, CA, Aug. 1990.
[17] L. P. Deutsch, D. G. Bobrow, An efficient incremental automatic garbage collector, Communications of the ACM, 19(9), pages 522-526, Sept. 1976.
[18] R. R. Fenichel and J. C. Yochelson, A Lisp garbage collector for virtual memory computer systems. Communications of the ACM, 12(11), pages 611-612, Nov. 1969.
[19] A. Georges, D. Buytaert, L. Eeckhout, Statistically rigorous java performance evaluation, in Proceedings of the 2007 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages & Applications, OOPSLA ’07, volume 42(10) of ACM SIGPLAN Notices, pages 57-76, Oct. 2007.
[20] A. Goldberg and D. Robson, Samlltalk-80:The Language and its Implementation, Addison-Wesley, 1983.
[21] R. E. Jones and R. D. Lins, Cyclic weighted reference counting without delay, in PARLE'93 Parallel Architectures and Languages Europe, A. Bode, M. Reeve, and G. Wolf, Eds., vol. 694 of Lecture Notes in Computer Science, Springer-Verlag, pages 712-715, June 1993.
[22] Y. Levanoni and E. Petrank, A scalable reference-counting garbage collector, Technical report CS0967, Technion, Israel Institute of Technology, Nov. 1999.
[23] Y. Levanoni and E. Petrank, On-the-fly reference counting garbage collector for Java, in Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA’01, pages 367-380, 2001.
[24] R. D. Lins, Cyclic reference counting with lazy mark-scan, Infor-mation Processing Letters, 44(4), pages 215-220, 1992.
[25] R. D. Lins, An efficient algorithm for cyclic reference counting, Information Processing Letters, 83(3), pages 145-150, 2002.
[26] R. D. Lins, An efficient multi-processor architecture for parallel cyclic reference counting, volume 2565 / 2003 Title: High Per-formance Computing for Computational Science - VECPAR 2002: 5th International Conference, Porto, Portugal, June 26-28, 2002.
[27] U. Maheshwari, B. Liskov, Collecting distributed garbage cycles by back tracing, in Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, Santa Barbara, California, United States, pages 239-248, 1997.
[28] A. D. Martinez, R. Wachenchauzer, and R. D. Lins, Cyclic refer-ence counting with local mark-scan, Information Processing Let-ters, 34, 1, pages 31-35, 1990.
[29] H. McBeth, On the reference counter method, Communications of the ACM, 6(9), pages 575, Sept. 1963.
[30] J. McCarthy, Recursive functions of symbolic expressions and their computation by machine, Communication of the ACM, 3, pages 184-195, 1960.
[31] L. Moreau, Hierarchical distributed reference counting, in Inter-national Symposium on Memory Management, ISMM 1998, pages 57-67, 1998.
[32] H. Paz and E. Petrank, Using prefetching to improve refer-ence-counting garbage collectors, Lecture Notes in Computer Sci-ence, LNCS volume 4420, pages 48-63, 2007.
[33] 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.
[34] D. Plainfosse, M. Shapiro, A survey of distributed garbage collec-tion techniques, Memory Management: International Workshop, IWMM'95, pages 211-247, 1995.
[35] H. Rodrigues and R. E. Jones, A cyclic distributed garbage col-lector for network objects, in Tenth International Workshop on Distributed Algorithms WDAG'96, number 1151 in Lecture Notes in Computer Science, Bologna, pages 123-140, Oct. 1996.
[36] J. D. Salkild, Implementation and analysis of two reference counting algorithms, Master's thesis, University College, London, 1987.
[37] R. Shaham, K. Kordner, and S. Sagiv, Automatic removal of array memory leaks in Java, in Compiler Construction (CC), Lecture Notes in Computer Science, LNCS 1781, Springer Verlag, pages 50-66, 2000.
[38] Standard Performance Evaluation Corporation. SPECjvm98 Docu-mentation, release 1.03 edition, Mar. 1999.
[39] D. A. Turner, A new implementation technique for applicative lan-guages, Software Practice and Experience, 9, 1979.
[40] J. Weizenbaum, Symmetric list processor, Communications of the ACM, 6(9), pages 524-536, Sept. 1963.