Memory Management: Garbage Collection Algorithm



Abstract

The paper presents a brief survey about the Garbage collection algorithms. This paper aims at discussing the most commonly used garbage collection algorithm Mark-Sweep and its variations. The Processes, Benefits and draw backs of these algorithms are briefly explained while Potential challenges and advancement that may be required for future have also been suggested in order to make the algorithm more reliable, efficient and more precise.

Introduction to Garbage Collection1

The Mark Sweep Garbage Collection1

Variations of Garbage collection Algorithm2

Semi - Space Algorithm2

Compacting algorithm4

Generational algorithm4

Advantages of Garbage Collection5

Disadvantages of Garbage Collection5

Future challenges and considerations6

Conclusion7

References8

Memory Management: Garbage Collection Algorithm

Introduction to Garbage Collection

The process of Garbage collection is meant to reclaim the unused data in storage (Cohen. J, 1981). Garbage collection consists of following two phases. First the storage is identified to reclaim; this is called marking and done by tracing the list of cells that can be immediately accessible through the links. Each cell is marked so it can be traced. Second phase is to integrate the reclaimed storage in the area of the memory in order to make it accessible for the user. This phase has two sub divisions. The incorporation of storage into list which is free, the cells have pointers to link and the compaction into already used data cells into an end area of memory, the other end (Cohen, Nicolau, 1983).

The Mark Sweep Garbage Collection

The most basic algorithm of garbage collection is known as Mark-Sweep which is the earliest algorithm (McCarthy, 1960). The most garbage collection algorithms that are used today are variation of Mark-Sweep. In the Mark-sweep garbage collection, the program requests for memory and if the memory is not free, it stops to perform garbage collection. The time taken by the Mark Sweep algorithm takes to operate is linear to the heap size. This doesn't give idea about overhead imposed on the given program, because whenever an allocation process fails it has to be invoked, thus the parameters on which the overhead is dependant on the size of the heap and the amount of memory which become unreachable in the last Garbage Collection. The time of overhead and pause is higher in Mark sweep algorithm while comparing practically to other algorithms. The algorithm frees the unused memory but it also fragments easily (Collins, 1960).

Variations of Garbage collection Algorithm

There variations on the GC algorithms in order to maximize the metrics according to achieve a pattern for the typical allocation. The algorithm dependents on the pattern used by program for the allocations Therefore, without considering the context in which the algorithm is used it can not be compared in a precise way. Practically, GC algorithms can be compared by general specification of statements of benefits that are imprecise and in specific benchmark scenarios the behavior's precise measurements. Important points while comparing GC algorithms are

The time to reclaim memory is minimized.

The wasted memory is minimized at all times.

Perform a collection the amount of memory used is to be ...