Allocation strategy is an important factor in efficient utilization of memory for objects, defining their scope and lives using either static, stack, or heap allocations.
Stack Allocation
- Stack is a linear data structure that satisfies last-in, first-out (UFO) policy for its allocation and deallocation.
- This makes only last element of the stack accessible at any time.
- Implementing stack data structure requires use of Stack Base (SB) that points to first entry of stack, and a Top of Stack (TOS) pointer to point to last entry allocated to stack.
Stack Allocation for Activation Records
- The stack allocation is based on the principles of control stack in which entries are Activation Records (ARs) of some procedure.
- ARs are pushed and popped on each call (activations) and return (the end of procedure), respectively.
- On each activation request, the memory is allocated on the TOS and pointer is incremented by the size of allocation.
- On execution of return from the procedure, AR is deallocated and TOS is decremented by the same size.
- Figure shows the AR on stack during procedure call.
Heap Allocation
- Heaps are a kind of non-linear data structure that permits allocation and deallocation of entities in any (random) order as needed.
- Heap data structure returns a pointer to allocated and deallocated area in heap for an allocation request.
- Hence, an allocated entity must maintain a pointer to the memory area allocated to it.
- Space allocation strategy using heaps is optimized for performance by maintaining list of free areas and implementing policies such as first-fit and best-fit for new object allocation.