臺灣博碩士論文加值系統

In distributed systems, weighted reference counting algorithm (WRC) is more
efficient than other reference counting or reference listing algorithms since each
reference has to send a message to object only when it is deleted. WRC uses
weight for each reference and the weight has to be halved when a reference is
copied. Thus it eliminates synchronization in the case of reference duplication
and reference deletion. In other words, there is no race condition for messages
in WRC which the other algorithms have to consider. When a reference whose
weight is equal to one has to be copied, the weight cannot be a whole number
after copied, so another auxiliary object (named indirection cell) has to be
created between the reference and the original object. The undirected reference
has to send more messages and more time consuming to access the object.
The weight-based reference counting algorithm (RWT) tries to figure out the
undirected problem with much more extra space. It uses tables instead of a
single cell, but the access to an object is always directly. In this thesis, we
propose an algorithm of recycling weight for weighted reference counting. The
recycling weight approach (RW) does not completely eliminate the undirected
v
reference drawback. It simply reduces the cases of indirection cell would be
created. In our experiments, recycling weight approach reduces the required
space up to 55% fromWRC and up to 88% from RWT. Average space efficiency
of Recycling Weight approach is 32.60% and 55.94% over WRC and RWT
respectively.

Acknowledgements iii
List of Figures x
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Background and Related Work 4
2.1 Weighted Reference Counting Algorithm (WRC) . . . . . . . . 4
2.1.1 Weighted References . . . . . . . . . . . . . . . . . . . 5
2.1.2 Indirection cells . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Reference Weight-based Table Method (RWT) . . . . . . . . . 7
2.2.1 The Basic Method . . . . . . . . . . . . . . . . . . . . 8
2.2.2 The RWT Algorithm . . . . . . . . . . . . . . . . . . . 11
3 Recycling Weight Approach 14
viii
3.1 Reusable Weight . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Recycling Weight . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Duplicating Reference (Weight = 1) . . . . . . . . . . . . . . . 16
3.4 Reference Deletion . . . . . . . . . . . . . . . . . . . . . . . . 18
3.5 Determining Reusable Weight . . . . . . . . . . . . . . . . . . 18
3.6 Distributing Reusable Weight . . . . . . . . . . . . . . . . . . 20
3.7 Communications . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.8 Space Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Implementation and Experiments 24
4.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Result Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5 Conclusion 53

[1] D. Bailey, E. Barscz, J. Barton, D. Browning, R. Carter, L. Dagun, R. Fa-
toohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon,
V. Venkatakrishnan, and S. Weeratunga. The nas parallel benchmarks.
Technical report, NASA Ames Research Center, Moffett Field, CA, 1994.
[2] D. I. Bevan. Distributed garbage collection using reference counting.
PARLE Parallel Architectures and Languages Europe, 259:176–187, June
1987.
[3] A. Birrell, D. Evers, G. Nelson, S. Owicki, and E. Wobber. Distributed
garbage collection for network objects. Technical Report 116, DEC Sys-
tem Research Center, 130 Lytton Avenue Palo Alto CA 94301, December
1993.
[4] A. Birrell, G. Nelson, S. Owicki, and E. Wobber. Network objects. Tech-
nical Report 14, ACM Symposium on Operating Systems Principles, De-
cember 1993.
[5] G. E. Collins. A method for overlapping and erasure of lists. Communi-
cations of the ACM, 3(12):655–657, December 1960.
54
[6] H. Corporaal, T. Veldman, and A. J. van de Goor. An efficient, ref-
erence weight-based garbage collection method for distributed systems.
PARBASE-90: International Conference on Databases, Parallel Archi-
tectures, and Their Applications, pages 463–465, March 1990.
[7] R. F. Van der Wijngaart and Michael Frumkin. Nas grid benchmarks
version 1.0. Technical report, NASA Ames Research Center, July 2002.
[8] Michael Frumkin and R. F. Van der Wijngaart. Nas grid benchmarks: A
tool for grid space exploration. Technical report, NASA Ames Research
Center, January 2002.
[9] B. Goldberg. Generational reference counting: A reduced communication
distributed storage reclamation scheme. Technical report, PLDI, 1989.
[10] Java rmi specification. http://docs.oracle.com/javase/jp/8/platform/
rmi/spec/rmiTOC.html.
[11] Java se hotspot. http://www.oracle.com/technetwork/java/javase/
tech/index-jsp-136373.html.
[12] R. Jones and R. Lins. Garbage Collection Algorithms for Automatic Dy-
namic Memory Management. John Wiley Sons Ltd, 1996.
[13] C.-W. Lermen and D. Maurer. A protocol for distributed reference count-
ing. LFP, pages 343–350, 1986.
[14] J. McCarthy. Recursive functions of symbolic expressions and their com-
55
putation by machine. Communications of the ACM, 3:184–195, April
1960.
[15] Openjdk. http://openjdk.java.net/projects/jdk6/.
[16] J. M. Piquer. Indirect reference counting: A distributed garbage collec-
tion algorithm. In Aarts, editor, PARLE’91 Parallel Architectures and
Languages Europe, volume 505 of Lecture Notes in Computer Science.
Springer-Verlag, June 1991.
[17] D. Plainfoss and M. Shapiro. A survey of distributed garbage collection
techniques. Technical Report 211-249, In Proceedings of the International
Workshop on Memory Management, IWMM, 1995.
[18] Sun Microsystems. Memory Management in the Java Hotspot Virtual
Machine, April 2006.
[19] P.Watson and I.Watson. An efficient garbage collection shceme for paral-
lel computer architectures. PARLE Parallel Architectures and Languages
Europe, 259:432–443, June 1987.
[20] A. Wollrath, R. Riggs, and J. Waldo. A distributed object model for the
java system. In Proceedings of the USENIX 2nd Conference on Object-
Oriented Technologies and Systems, June 1996.