Which algorithms are using Garbage collector in Java. How Garbage Collector algorithm works
Garbage collector algorithm
Another technique is Tracing. The runtime system will try to find all objects accessible through refrence chains running from certain root objects and assume that all other objects unreachable through those reference chains are garbage. This is the most commonly used algorithm since unlike refrence counting explained by ~ swim ~ , it eliminates the need to allocate additional memory to store refrence counts. It is also unsusceptible to refrence cycles which occur when unneeded objects contain refrences to each other preventing the reference count from falling to zero to allow garbage collection.
Memory is allocated to Java programs by the JVM (java virtual machine). The JVM runs garbage collection at unspecified intervals automatically, to keep available memory at acceptable level. The GC frees up memory by removing unused variables and obsolete objects from the memory. All this happens in the background without any explicit instruction or control from the developer.
Garbage collection works on Mark and Sweep algorithm. In Mark phase it detects all the unreachable objects and Sweep phase it reclaim the heap space used by the garbage objects and make the space available again to the program. There are many garbage collection algorithms which run in the background. One of them is mark and sweep. Mark and Sweep AlgorithmAny garbage collection algorithm must perform 2 basic operations. One, it should be able to detect all the unreachable objects and secondly, it must reclaim the heap space used by the garbage objects and make the space available again to the program.The above operations are performed by Mark and Sweep Algorithm in Two phases: Mark phase Sweep phase Mark Phase When an object is created, its mark bit is set to 0(false). In the Mark phase, we set the marked bit for all the reachable objects (or the objects which a user can refer to) to 1(true). Now to perform this operation we simply need to do a graph traversal, a depth first search approach would work for us. Here we can consider every object as a node and then all the nodes (objects) that are reachable from this node (object) are visited and it goes on till we have visited all the reachable nodes. Root is a variable that refer to an object and is directly accessible by local variable. We will assume that we have one root only. We can access the mark bit for an object by: markedBit(obj). Algorithm -Mark phase: Mark(root) If markedBit(root) = false then markedBit(root) = true For each v referenced by root Mark(v) Note: If we have more than one root, then we simply have to call Mark() for all the root variables.
Sweep Phase As the name suggests it “sweeps” the unreachable objects i.e. it clears the heap memory for all the unreachable objects. All those objects whose marked value is set to false are cleared from the heap memory, for all other objects (reachable objects) the marked bit is set to true. Now the mark value for all the reachable objects is set to false, since we will run the algorithm (if required) and again we will go through the mark phase to mark all the reachable objects. Algorithm – Sweep Phase Sweep() For each object p in heap If markedBit(p) = true then markedBit(p) = false else heap.release(p) The mark-and-sweep algorithm is called a tracing garbage collector because it traces out the entire collection of objects that are directly or indirectly accessible by the program. The very short version though is that Garbage collectors determine which memory to retain and which to reclaim, using reachability through chains of pointers. _Garbage collector uses many algorithms but the most commonly used algorithm is mark and sweep. Garbage collection has two components: locating “live” objects and moving them so that there are no gaps. Locating live objects can be done by having each handle (pointer to the object) include a reference count. A non-zero reference count means that the object is still live. Alternatively, a depth first search algorithm can be used to locate live objects. There are also two basic methods of moving an object. One is called “mark and sweep” where all the live objects are located and their addresses sorted so that when they are moved, one object doesn’t inadvertently overwrite another
The other method is called “copying” garbage collection where a new block of memory is allocated for the objects and each live object is copied into the new area. This method is faster since each live object can be moved immediately without reference to any other object. However, it is wasteful of memory. The JVM tends to use a combination of both methods. Objects tend to have either a short life or a long life. New objects are placed in a “young generation” of memory where copying collection is employed. As the young generation fills up, “surviving” objects get placed into the “old generation” where mark and sweep is employed (infrequently).