Distributed Garbage Collection
A study and comparison of Mark-Sweep and Reference Counting

Tanmay Mogra Y7471 Shashwat Mishra Y7416

Table of Contents
History and Motivation 1 ------------------------------------------------

Work Completed Mark and Sweep ------------------------------------------------2 Basic Algorithm ------------------------------------------------2 Strengths and Weaknesses ------------------------------------------------2 Varations of Mark and Sweep -------------------------------------------------2 Reference Counting Basic Algorithm Strengths and Weaknesses 3 3 Mark and Sweep vs. Reference Counting Design/Implementation A Simulation of Reference Counting using JAVA's ----------------------------------------------Remote Method Invocation API Conclusion References -----------------------------------------------------------------------------------------------6 7 5 -----------------------------------------------4 Variations of Ref. Counting --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------3 3

History and Motivation
The problem statement requires one to study and compare the efficiency of two garbage collection algorithms, Mark and Sweep and Reference Counting, in the context of distributed object systems. It also involves the implementation of one of the two algorithms. Modern systems come with limited memory. Part of this memory is known as 'heap', which is dynamically allocated as and when needed. References are maintained to the locations in the heap. In such a scenario, it is possible for chunk of memory to become unreachable (when there is no reference to it). Such chunks which are not reachable, become garbage. Garbage collection refers to automatic memory management. This is in contrast to explicit (manual) heap management, which gives the responsibility of de-allocating memory occupied by objects to the application programmer . As modern software development involves large, complex artefacts of software, often developed by a large team of developers, no one person knows the implementation details of the entire system. It is thus very difficult for any developer to manage memory manually. Manual allocation and de-allocation is prone to errors that cause difficult-to-debug problems. This issue is made more prominent in distributed systems where there are many of threads of control, many processes interacting and often components developed by many different parties. Explicit management is out of the question in such situations. This calls for automatic memory management schemes. In distributed systems, garbage collection becomes more difficult because of the very concurrent nature of a distributed system. Since each node has one or more processes, there are very many mutators constantly changing the reference graph of objects in memory. For an object to be able to explicitly collect another object’s memory, it would have to know that the particular object was not going to be referred to by all the processes in the system. In context of the distributed garbage collection, the part which receives request from the application program and handles allocation of free cells of the heap memory is known as Allocator. The part which handles reclaimation of memory is known as the Collector. The application program itself is known as the Mutator because it changes the connectivity of the graph of the heap data structures by requesting creation/deletion of references. Some locations in the heap are known as root. A root is a location in the memory which is always accessible to the program. For example in a java program class variables can play the role of root. Any location in the memory is termed as reachable if it is reachable from root through one or more references. The heart of the problem lies in reclaiming the nonreachable memory. Classically, there are three broad algorithms for handling distributed garbage collection. Reference counting ( which works by maintaing a count of references to a particular object ), Mark and Sweep (which works in phases to reclaim memory) and Copy Collection (like Mark and Sweep with the advantage that it incorporates defragmentation into reclaimation).

Mark and Sweep
Basic Algorithm :Presented in [McCarthy, 1960] for the LISP language, this was the first algorithm for automatic heap management. Also known as tracing collector it works in two phases. All the objects have a mark-bit which is initially set to 0. Phases :1. Garbage Detection: This is done by tracing, starting at the root set and traversing the graph of pointer relationships using BFS or DFS. The mark-bits in the objects that are reached are set to 1. 2. Garbage Reclamation: Once all the live objects have been made distinguishable from the garbage, memory is swept. It is exhaustively examined (all cells) to find all the unmarked objects and reclaim them. All the marked objects have their mark bits reset, in readiness for the next phase. Strengths :The strengths of the mark-sweep algorithm have lead to its adoption in some systems. The functional language Miranda [Turner, 1985] is a notable example. Mark and Sweep has two major advantages 1. Cyclic data structures are handled naturally. This is because all objects are not examined from the point of view of other objects referring to them, but from the root set. If an island in the graph occurs, it will have no references directly or indirectly from the root set and thus will not be marked. 2. There is no overhead in pointer manipulation. We'll see that reference counting places a high overhead whenever a pointer is created, copied or destroyed. In the mark-sweep, because the algorithm does not update its view of liveness every time the mutator mutates the graph of references, this overhead does not occur. Weaknesses :1. Fragmentation – This is a common problem to several GC algorithms. Because the collector does not move the objects, hence when handling objects of varying size, this will lead to creation of holes in the memory. This in turn increases the task of the allocator which will have to find a sufficiently large hole for memory-allocation requests. However this problem can be handled in a variation of Mark-Sweep. [Cohen and Nicolau, 1983]. 2. Slow due to Stop/Start nature - There will be a substantial pause in mutator activity when the collector is working. [Foderaro and Fateman, 1981] showed that as memory sizes grew faster than processing speeds, some large Lisp programs were spending between 25—40% of their time marking and sweeping, and users were waiting 5 seconds in a minute . For highly interactive systems such as window managers and video games, as well as real time applications and safety critical systems, this collector would not be practical. If on the other hand, response time is not an important consideration, marksweep does offer better performance than incremental algorithms like reference counting [Jones and Lins, 1996]. Variation :- Mark and Compact Suggested by [Cohen and Nicolau, 1983], it handles the problem of fragmentation by doing more passes of the memory. After marking phase, it makes 3 more phases a – to compute new locations for live objects b – to update pointers that refer to live objects c – to move the objects

Reference Counting

Basic Algorithm :Reference counting, first presented in [Collins, 1960] is a method where each object determines its only liveness. Every object maintains a count of the number of references to it from all the other objects in the distributed setup. Each time a reference to the object is created, the object's count is incremented. When a reference to an object is deleted, the count is decremented. When the reference count reaches zero, the memory occupied by an object may be reclaimed. This is because the zero count indicates that no pointers to the object exist and the program can never reach this object. Before an object X is reclaimed, the counts of all the objects which are referenced from X are decremented. This is because a reference from a garbage object is not meaningful as it is inaccessible. Thus reclaiming one object may result to the transitive decrementing of reference counts and reclaiming many other objects. Strengths :The main advantage of reference counting is its incremental nature of operation. It is interleaved with the mutator's own execution. Every unit of mutator execution which involves operation on references (copying, deleting) includes some time spent on handling reference counts. But this time is bounded. Hence reference counting is real time. Weaknesses :1. Fragmentation – Like Mark-Sweep, Reference Counting does not move the live objects. Thereby creating holes in the heap memory. Unfortunately, in case of Reference Counting there are not variations which can handle the fragmentation issue. 2. Detection of Cycles – Basic Reference Counting fails to detect islands of objects which are interconnected to one another but are un-reachable from the root. However this can be handled by running a tracing algorithm (like Mark-Sweep) after some period of time to detect all isolated cycles [Knuth, 1973], [Wise, 1979], [Deutsch and Bobrow, 1976] . 3. Overhead – Although we said that the time spent on operations over references is bounded, the cost of proportionaliy is large. Changing of a reference link from object a to object b causes two reference counts to be adjusted. Further, one will have to check for liveness of one these objects after the operation. This leads to a lot of work. Variations :Weighted Reference Counting :- In weighted reference counting every reference has a weight attached to it. Also every object stores a fixed quantity known as its own weight. The following invariant is maintained, an object's weight is equal to the sum of the weights of the references to it. Weighted Reference Counting scores over Basic Reference Counting by improving over the no. Of messages involved in copying a reference. In basic reference counting, whenever a new reference (of c) is copied from a to b, b needs to notify (send a message) to c to let it know that it should increase its reference count. However in weighted reference counting this can be avoided, when passing reference of c to b, a can also pass half of the weight of its reference to c. Thereby maintaining the invariant. When a reference is deleted, the weighted reference sum is decremented by the weight of the reference. This is communicated to the object by sending it a message. When the object detects that the weighted reference sum has dropped to zero, it may be reclaimed.

Mark-Sweep vs Ref. Counting
In context of distributed systems, latency plays an important role. Unnecessary delays can hamper the performance of the system. Hence every effort should be made to minimize

such delays. Because of Start/Stop nature of Distributed Mark-Sweep, every time the collector is initiated, the entire system must suspend all other work till the collector reclaims some memory. This step has to be repeated every single time the collector is initiated. This will introduce long pauses in the execution of the mutator. Whereas in Distributed Ref. Counting, an object will be accounted for as soon as it turns into garbage. Because of realtime nature of garbage collection it does not impose delays on the mutator like MarkSweep does. Hence it seems that in a distributed environment, Reference Counting is better option than Mark-Sweep. However, it is interesting to note that the performance of Reference Counting depends on the depth of the garbage. Depth of the garbage means the complexity of the reference graph. If the setup is such that deeply nested data structures are often created in the reference graphs, then Mark-Sweep outruns Reference Counting. However, in distributed server-client computing most references direct from a client to the server, hence long chains of remote references are rarely created. [Friedman, 77] and [Stoye et al, 84] discovered that 70% to 80% of all objects are referenced only once. The average references per object lies between 1.25 – 1.45. This factor weighs in favor of Distributed Reference Counting. We thus see that Distributed Reference Counting's latency-tolerant real-time nature scores over Mark-Sweep's delays in memory reclamation, thereby making the former a preferred choice in scenarios such as distributed client-server models, where latency is an important issue. An important issue left un-addressed in the justification of Distr. Ref. Counting is of Fault Tolerance. Essentially, if a node A goes down, then it may leave orphans on some node B. Such orphans will maintain there reference counts > 0 and hence will not be garbage collected. There are two ways to handle this. 1. A crashed node on resuming will send out garbage collect messages to all such orphan nodes 2. The concept of Lease is introduced. Essentially every object has a timer associated with it. After the timer runs out, the local GC must collect the object as garbage. If a node wishes to use an object on another node, it must re-new the lease after every fixed period of time. Given the concept of lease, all orphan nodes are bound to be collected by the local GC in B after their lease runs out. Hence Distr. Ref. Counting can be made to handle faults in the system.

Simulation of Distributed Reference Counting
We present a simulation of Distributed Reference Counting implemented in JAVA using JAVA's Remote Method Invocation API.

JAVA RMI facilitates easy creation of objects for use in remote procedure calls. In our simulation, we present a client-server model, where clients maintain references to objects that reside on servers. The servers maintain these objects and may hold references to other servers. We start with a fixed reference graph which mutates with time and corresponding to every significant event in the system, we print messages to denote these events. We do not actually claim the object as garbage but we show messages for the same. Hence in essence it is a simulation. We plan to replace the textual-message corresponding to every event, with a GUI output to make the outcome more legible. We are still working on this stage. The basic model is outlined in a diagram as shown below.

The grey circles on the left denote the clients, and the blue circles on the right denote the servers. Every server maintains a single object. This object is referenced to by the clients and by other servers. A client object can refer to more than one objects on different servers (client 1). A server object can be referenced to by more than one clients (server1). Lastly, one or more servers may hold referance to other server(s) (2,3,4 hold reference to 5). In our simulation as references are created, links will be drawn between client-server or server-server. In the background the reference count will be updated. When an object no longer needs a reference to a remote object, a clean() call will be issued to that object. The link will be removed, and the object, if eligible to be reclaimed, will also be removed. We plan to use java.awt package to render the graphic simulation. All clients and servers will communicate with a central thread notifying it of any significant event. The central thread will responsible for rendering the simulation.

Conclusion
This project involves the study of a consequence of limited memory in computer systems. Limited memory calls for efficient memory management techniques. In large distributed setups a single entity is not aware of memory allocations in the entire setup. Hence manual memory management is infeasible. This thought suggests that efficient automatic memory management is necessary for a system. Unreachable locations on the memory need to be reclaimed. In a non-distributed system a memory location can be referenced to only by the

objects on that system alone. The garbage collector is able to easily determine which objects are still in use by literally looking at each object in a program, marking those which are still in use and removing the leftovers. But with distributed objects, any node in the system could be using your objects if you let them. The garbage collector can't very well look at every object on the entire Web to determine which are still in use. We study and analyse two garbage collection algorithms, Mark-Sweep and Reference Counting. We come to learn that in case of distributed client-server model where latency is an important criteria, Distr. Ref. Counting scores over Mark-Sweep by claiming garbage in real-time. Reference counting does suffer from some drawbacks such as Fault Tolerance,Cycle detection etc but we see that variations of Reference counting have been proposed that over come these pitfalls. However on a similar note, one very important conclusion that we come across is that neither Reference Counting nor Mark-Sweep address the issue of Fragmentation. Fragmentation causes formation of holes in heap increases the task of allocator which has to find a sufficiently large hole to accomodate each object. It is worth mentioning that a separate class of Garbage Collection Algorithms exist, known as Copying Collectors, which incorporate fragmentation into the program. Essentially these copying collectors divide the heap into two equal halves. Unlike other algorithms where garbage objects are reclaimed, this algorithm picks all the reachable objects and copies them into the other half. The role of each half is flipped after every such copying operation. Although there exist variation of Mark-Sweep (Mark-Compact) which address this issue, such variations are very costly since they require multiple passes over the entire memory space. This makes them even slower than basic Mark-Sweep which itself is slow to beginwith. In the implementation stage, opting to do a simulation was not a matter of choice, since any modern programming language which contains libraries for Remote Procedure Calls, comes preloaded with Distributed Garbage Collection algorithms. The JAVA RMI library comes pre-equipped with distributed reference counting. A remote object can implement the java.rmi.server.Unreferenced interface and get a notification via the unreferenced method when there are no longer any clients holding a live reference. However in our implementation we have not implemented the Unreferenced interface. We have encountered some problems in exporting multiple remote objects from a single server using java RMI. Although a client can connect to different objects lying in different nodes, there seems to be some problem with a single server exporting multiple distinct objects to its clients. When tried, all the clients seem to connect to only the first object that was exported. One can look into the above issues to make the basic model shown in the diagram earlier more generic.

References
[1] A Construction of Distributed Reference Counting [Mureau-Dupreat, 99] [2] Distributed Garbage Collection using Reference Counting [D I Bevan] [3] Global Mark and Sweep on Parallel Computers [Yamamoto-Taura, 98]