(3.238.96.184) 您好!臺灣時間:2021/05/12 23:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:鄭賀元
研究生(外文):Ho-yuan Cheng
論文名稱:引用計數垃圾收集機制之研究
論文名稱(外文):A Study of Reference Counting Garbage Collectors
指導教授:陳維美
指導教授(外文):Wei-mei Chen
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電子工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:44
中文關鍵詞:引用計數垃圾收集爪哇虛擬機器
外文關鍵詞:reference countinggarbage collectionJava virtual machineJikes RVM
相關次數:
  • 被引用被引用:0
  • 點閱點閱:199
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
垃圾收集(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%.
Abstract I
中文摘要 II
章節目錄 III
圖序列表 VI
表序列表 VIII
第一章、緒論 1
1.1 研究動機與目的 1
1.2 論文架構 2
第二章、垃圾收集技術背景知識與傳統的演算法 3
2.1 背景知識 3
2.1.1 計算圖形 3
2.1.2 垃圾 4
2.1.3 空懸參照 5
2.2 傳統演算法 8
2.2.1 引用計數法 8
2.2.2 標記—掃除法 8
2.2.3 物件複製法 9
2.2.4 環狀引用計數法 10
2.2.4.1 Bobrow技術 10
2.2.4.2 弱指標演算法 10
2.2.4.3 部分標記—掃除演算法 11
第三章、環狀結構偵測器與分類模型 12
3.1 環狀偵測器相關技術 12
3.1.1 Martinez區域標記—掃描法 12
3.1.2 Lins延遲標記—掃描法 14
3.1.3 Bacon演算法 17
3.2 新環狀結構分類模型 19
第四章、多引用計數演算法 22
4.1 多引用計數法的基本概念 22
4.2 實際操作多引用計數演算法 22
第五章、實驗方法與模擬結果 26
5.1 實驗方法 26
5.1.1 Jikes RVM 26
5.1.2 實作細節 27
5.1.3 實驗平台 28
5.1.4 Benchmarks 28
5.2 模擬結果與分析 28
5.2.1 環狀結構分類模型的分析 28
5.2.2 環狀偵測器處理過的物件個數 31
5.2.3 環狀偵測器處理過的參照個數 35
5.2.4 環狀偵測器花費的時間 38
第六章、結論 40
參考文獻 41
[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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔