臺灣博碩士論文加值系統

本篇論文中，我們將針對Java RMI提出一個新的分散式自動記憶體管理機制。分散式自動記憶體管理機制是用來判斷分散式環境的遠端物件是否可以釋放其佔用的記憶體，那些不會再被客戶端所引用的遠端物件將會被回收。在分散式環境之中，記憶體管理機制遠比傳統在一台主機上的記憶體管理複雜，因為它需要來自其他節點的資訊，也因此將造成更多的訊息傳遞。

我們的演算法根據計數參照的方式，將重點放在演算法使用的記憶體空間及連線次數。用於分散式系統的計數參照當中，以最簡單的方式達到分散是計數參照的 DRC 對於每個參考需要三次的連線；而權重計數參照(WRC)則以增加記憶體的方式來減少連線次數。

最後，在我們的實驗當中使用了 OpenJDK 的 RMI 來完成我們的分散式記憶體管理機制。我們的演算法將比 DRC 的連線次數較少；且在大部分的情況之下，可以比 WRC 擁有更少的記憶體使用以及連線次數。我們的演算法可以在不增加過多的記憶體的狀態之下有效的減少連線次數。根據實驗結果，與 DRC 演算法比較，我們減少 35.08% 至 57.09% 的 GC 時間消耗，平均為44.90%；和 WRC 比較，我們則減少了 22.47% 至 51.39% 的 GC 時間消耗，平均則是35.32%。

In this thesis, a new approach of distributed garbage collection(DGC) for Java Remote Method Invocation(RMI) is presented, called Surrogate Reference Counting(SRC). DGC is a mechanism that handles the remote objects used in the distributed environment. It reclaims the memory used by the
remote objects that are no longer referenced by any client. The garbage collection for a distributed system is more complicated than a local one. It needs information from other nodes, causing it to require more messages passing.

Our algorithm is based on reference counting, we focus on the memory space and network connection. A straightforward extension of reference counting to distributed systems requires communication overhead of three times the number of reference copies. Weighted reference counting reduces the cost of commnuications but increases the cost of memory space. In our experiments on the RMI package of OpenJDK, our new garbage collector requires less communications than distributed reference counting, and in most case it costs less memory space than weighted reference counting in the distributed systems. Our approach effectively reduces the number of connection without sacrificing too much memory space. When compared with DRC, our algorithm reduced the GC time in a range between 35.08% and 57.09%, averaging at 44.90%. When compared with WRC, our algorithm reduced the GC time in a range between 22.47% and 51.39%, with an average of 35.32%.

1 Introduction
1.1 Motivation
1.2 Thesis Organization
2 Background and Related Work
2.1 Java RMI
2.2 An Overview of Garbage Collection
2.3 Birrell’s Reference Listing Algorithm
2.4 Distributed Reference Counting
2.5 Weighted Reference Counting
2.6 Cyclic Issue
3 A New Garbage Collection Algorithm for Java RMI
3.1 Notation Define
3.2 Surrogate Reference Counting
3.3 An Example
3.4 Correctness
3.5 Compare
4 Implementation and Experiments
4.1 Implementation
4.2 Experiments
4.3 Result Analysis
5 Conclusion

S. Ahuja and R. Quintao. Performance evaluation of java rmi: A distributed object architecture for internet based applications. In Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS ’00, pages 565–569, Washington, DC, USA, 2000.
S. Abdullahi and G. Ringwood. Garbage collecting the internet: a survey of distributed garbage collection. ACM Comput. Surv., 30(3):330–373, 1998.
D. Bailey, D. Barszcz, J. Barton, D. Browning, R. Carter, L. Dagum, R. Fatoohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon, V. Venkatakrishnan, and S. Weeratunga. The nas parallel benchmarks. Technical Report RNR-94-007, NASA Ames Research Center, Moffett Field, CA, March 1994.
D. Bacon, P. Cheng, and V. Rajan. A unified theory of garbage collection. In Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, andapplications, OOPSLA ’04, pages 50–68, New York, NY, USA, 2004.
A. Birrell, D. Evers, G. Nelson, W. T. Robert, S. Owicki, and E. Wobber. Distributed garbage collection for network objects. 1993.
D. Bevan. Distributed garbage collection using reference counting. In Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, pages 176–187, London, UK, UK, 1987.
A. Buss and L. Jackson. Distributed simulation modeling: a comparison of hla, corba, and rmi. In Proceedings of the 30th conference on Winter simulation, WSC ’98, pages 819–826, Los Alamitos, CA, USA, 1998.
A. Birrell and B. Nelson. Implementing remote procedure calls. ACM Trans. Comput. Syst., 2:39–59, 1984.
A. Birrell, G. Nelson, S. Owicki, and E. Wobber. Network objects. In Proceedings of the fourteenth ACM symposium on Operating systems principles, SOSP ’93, pages 217–230, New York, NY, USA, 1993.
D. Brownbridge. Cyclic reference counting for combinator machines. In Proc. of a conference on Functional programming languages and computer architecture, pages 273–288, New York, NY, USA, 1985.
T. Christopher. Reference count garbage collection. Software: Practice and Experience, 14(6):503–507, 1984.
M. Frumkin and R. Wijngaart. Nas grid benchmarks: A tool for grid space exploration. Cluster Computing, 5(3):247–255, 2002.
W. Grosso. Java RMI. Sebastopol, CA, USA, 1st edition, 2001.
Y. Ichisugi and A. Yonezawa. Distributed garbage collection using group reference counting. In Department of Information Science, University of Tokyo, 1990.
M. Juric, B. Kezmah, M. Hericko, I. Rozman, and I. Vezocnik. Java rmi, rmi tunneling and web services comparison and performance analysis. SIGPLAN Not., 39(5):58–65, 2004.
R. Jones and R. Lins. Garbage collection: algorithms for automatic dynamic memory management. New York, NY, USA, 1996.
R. Lins. Cyclic reference vounting with lazy mark-scan. Information Processing Letters, 44:215–220, 1992.
R. Lins. Efficient cyclic weighted reference counting. In Proceedings of the 14th Symposium on Computer Architecture and High Performance Computing, SBAC-PAD ’02, pages 61–, Washington, DC, USA, 2002.
C. Lermen and D. Maurer. A protocol for distributed reference counting. In Proceedings of the 1986 ACM conference on LISP and functional programming, LFP ’86, pages 343–350, New York, NY, USA, 1986.
J. McBeth. Letters to the editor: on the reference counter method. Commun. ACM, 6:575–, 1963.
L. Moreau, P. Dickman, and R. Jones. Birrell’s distributed reference listing revisited. ACM Trans. Program. Lang. Syst., 27(6):1344–1395, 2005.
A. D. Martinez, R. Wachenchauzer, and R. Lins. Cycle reference counting with local mark-scan. Inf. Process. Lett., 34(1):31–35, 1990.
D. Plainfoss’e and M. Shapiro. A survey of distributed garbage collection techniques. In Proceedings of the International Workshop on Memory Management, IWMM ’95, pages 211–249, London, UK, UK, 1995.
Java RMI Specification. http://download.java.net/jdk7/archive/b123/docs/platform/rmi/spec/rmiTOC.html.
S. Vestal. Garbage collection: an exercise in distributed, faulttolerant programming. PhD thesis, Seattle, WA, USA, 1987.
L. Veiga and P. Ferreira. Complete distributed garbage collection: an experience with rotor. IEE Proceedings - Software, 150(5):283–290, 2003.
J. Waldo. Remote procedure calls and java remote method invocation. IEEE Concurrency, 6(3):5–7, July 1998.
R. Wijngaart and M. Frumkin. Nas grid benchmarks version 1.0. Technical Report NAS-02-005, NASA Ames Research Center, Moffett Field, CA, July 2002.
A. Wollrath, R. Riggs, J. Waldo, and Sun Microsystems Inc. A distributed object model for the java system, 1996.
P. Watson and I. Watson. An efficient garbage collection scheme for parallel computer architectures. pages 432–443. Springer-Verlag, 1987.
A. Wollrath, J. Waldo, and R. Riggs. Java-centric distributed computing. IEEE Micro, 17(3):44–53, 1997.