The techniques needed to implement dynamic storage allocation depend on how storage is deallocated. If deallocation is implicit, then the run-time support package is responsible for determining when a storage block is no longer needed. There is less a compiler has to do if deallocation is done explicitly by the programmer.
There are two types of deallocation :
1.Explicit Deallocation
2.Implicit Deallocation
– It is explicit when the program asks for a block to be
freed,
– It is implicit when the memory manager automatically
tries to free unused blocks when it does not have
enough free memory to satisfy an allocation request.
1.Explicit Deallocation :
Explicit memory deallocation presents several problems:
1. Memory can be freed too early, which leads to
dangling pointers — and then to data corruption,
crashes, security issues, etc.
2. Memory can be freed too late — or never — which leads
to space leaks.
Due to these problems, most modern programming languages are designed to provide implicit deallocation, also called automatic memory management — or garbage collection, even though garbage collection refers to a specific kind of automatic memory management.
2.Implicit Deallocation :
Implicit memory deallocation is based on the following conservative assumption:
If a block of memory is reachable, then it will be used again in the future, and therefore it cannot be freed. Only unreachable memory blocks can be freed. Since this assumption is conservative, it is possible to have memory leaks even with implicit memory deallocation. This happens whenever a reference to a memory block is kept, but the block is not accessed anymore.
However, implicit deallocation completely eliminates dangling pointers.
Garbage collection (GC) :
Garbage collection (GC) is a common name for a set of
techniques that automatically reclaim objects that are not
reachable anymore.
We will examine several garbage collection techniques:
1. Reference Counting,
2. Mark & Sweep garbage collection, and
3. Copying garbage collection.
All these techniques have concepts in common, which we
introduce now.
1.Reference counting :
The idea of reference counting is simple:
Every object carries a count of the number of pointers that reference it. When this count reaches zero, the object is guaranteed to be unreachable and can be deallocated. Reference counting requires collaboration from the compiler and/or programmer to make sure that reference counts are properly maintained!
Pros and cons :
Reference counting is relatively easy to implement, even as a library. It reclaims memory immediately. However, it has an important impact on space consumption, and speed of execution: every object must contain a counter, and every pointer write must update it.
2.Mark & Sweep
Mark & sweep garbage collection is a GC technique that proceeds in two successive phases:
1. in the marking phase, the reachability graph is
traversed and reachable objects are marked,
2. in the sweeping phase, all allocated objects are
examined, and unmarked ones are freed.
GC is triggered by a lack of memory, and must complete before the program can be resumed. This is necessary to ensure that the reachability graph is not modified by the program while the GC traverses it.
3.Copying GC :
The idea of copying garbage collection is to split the heap in two semi-spaces of equal size: the from-space and the tospace. Memory is allocated in from-space, while to-space is left empty.
When from-space is full, all reachable objects in from-space are copied to to-space, and pointers to them are updated accordingly.
Finally, the role of the two spaces is exchanged, and the program resumed.
Allocation in a copying GC :
In a copying GC, memory is allocated linearly in from-space. There is no free list to maintain, and no search to perform in order to find a free block. All that is required is a pointer to the border between the allocated and free area of fromspace. Allocation in a copying GC is therefore very fast — as fast as stack allocation. Before copying an object, a check must be made to see whether it has already been copied. If this is the case, it must not be copied again.
