STORAGE ALLOCATION STRATEGIES
The various storage allocation strategies to allocate storage in different data areas of the memory are
- Static allocation
- Stack allocation
- Heap allocation
Static Allocation
In static memory allocation, program variables remain permanently allocated irrespective of their accessibility at any stage of the program’s execution. Names are bound to storage as the program is compiled; therefore, there is no need for ants time support package. As these bindings do not change at run time, every time a procedure is activated, its names are bound to the same storage locations. Due to this property, the values of local names are retained across various activations of a procedure. So, when control returns to a procedure, the values of the local variables remain the same as they were earlier when control left the procedure last time. For example, in
FORTRAN memory is permanently allocated to the program variables of all subprograms of programs, irrespective of whether a given subprogram is active at any given moment. The amount of storage required for a symbol is determined from its type as follows.
- An elementary data type like character, integer, or real can usually be stored in integral numbers of bytes.
- A contiguous block of bytes large enough to hold all its components is allocated, for an array or record.
In static allocation, it is possible to fill in the addresses at which the target code can find the data it operates on at the compile time. Also, we which information is to be saved when a procedure call occurs.
The limitations of the static memory allocation are
- For two subprograms that do not call each other i.e. they are mutually exclusive, memory remains bound by the program variables of both the subprograms.
- Memory remains bound by the program variables of those subprograms which may never be called.
- It doesn’t support recursive procedures.
- As there is no mechanism for storage allocation at run time, data structures cannot be created dynamically.
- The size of the data objects must be known during compilation.
Stack Allocation
For stack allocation storage is organized as a stack. An activation record is pushed when a procedure is entered during program execution. It is popped when the procedure ends. The storage freed by popping an activation record can be used to push another activation record when another block is entered. Thus, mutually exclusive blocks do not unnecessarily bind up memory space.
For each call of a procedure, the activation record contains storage for the local variables of that call. These values of locals are lost when an activation ends, as its activation record is popped off. The top of the stack may be stored in a register. This value can be incremented by the size of the activation record to allocate space for an activation record and can be decremented by the size of the activation record to deallocate the space.
The advantages of stack allocation are
- It supports recursion as memory is always allocated on block entry.
- It allows the creation of data structures dynamically.
- It allows an array declaration like A (1, J) since the actual allocation is made only at execution time. The dimension bounds need not be known at compile time with the condition that they must be evaluated before the dimensioned variables are brought into existence.
The only disadvantage of stack allocation is that memory addressing has to be effected through pointers and index registers which may be slower than static allocation especially in the case of array reference.
Heap Allocation
In the case of stack allocation, the local variables of a procedure or block are lost when activation ends. If we want to retain these values, we are required to use heap allocation. It allows the programmer explicit control over the allocation/deallocation of storage to the program variables. For example, PL/1 permits a list processing to be carried out easily in a non-list processing environment. Here, allocation to variables is performed from a large free area, and access to variables is implemented through pointers associated with each variable rather than through block descriptors. Whenever storage is de-allocated, it is not reclaimed for use immediately. Rather, garbage collection is done ‘whenever all such space is necessary to reclaim.
Heap allocation is required particularly in cases where allocation/deallocation is not necessarily carried out in a last-in-first-out manner and stack allocation scheme cannot be used. For example, in a multi-activity program, the programmer is allowed to create activities that are independent of one another. These activities may be executed concurrently in an asynchronous manner and the program blocks may be entered and exited in a non-LIFO order during the execution of these activities. So, we have to use heap allocation. Similar is the case of procedure valued parameters.
A heap allocation is a more general allocation strategy than a stack allocation. But the stack is efficient both in terms of space and execution as it does not require maintaining any links and any garbage collection activity.