Storage Allocation Strategies

STORAGE ALLOCATION STRATEGIES

The different storage allocation strategies are :

1. Static allocation - lays out storage for all data objects at compile time

2. Stack allocation - manages the run-time storage as a stack.

3. Heap allocation - allocates and deallocates storage as needed at run time from a data area known as heap.

STATIC ALLOCATION

In static allocation, names are bound to storage as the program is compiled, so there is no need for a run-time support package. Since the bindings do not change at run-time, everytime a procedure is activated, its names are bound to the same storage locations. Therefore values of local names are retained across activations of a procedure.

That is, when control returns to a procedure the values of the locals are the same as they were when control left the last time. From the type of a name, the compiler decides the amount of storage for the name and decides where the activation records go. At compile time, we can fill in the addresses at which the target code can find the data it operates on.

STACK ALLOCATION OF SPACE

All compilers for languages that use procedures, functions or methods as units of user-defined actions manage at least part of their run-time memory as a stack. Each time a procedure is called , space for its local variables is pushed onto a stack, and when the procedure terminates, that space is popped off the stack.

Calling sequences:

Procedures called are implemented in what is called as calling sequence, which consists of code that allocates an activation record on the stack and enters information into its fields. A return sequence is similar to code to restore the state of machine so the calling procedure can continue its execution after the call. The code in calling sequence is often divided between the calling procedure (caller) and the procedure it calls (callee).

When designing calling sequences and the layout of activation records, the following principles are helpful:

Ø     Values communicated between caller and callee are generally placed at the beginning of the callee’s activation record, so they are as close as possible to the caller’s activation record.

Fixed length items are generally placed in the middle. Such i the control link, the accesslink, and the machine status fields

Items whose size may not be known early enough are placed at the end of the activation

record. The most common example is dynamically sized array, where the value of one of

the callee’s parameters determines the length of the array.

We must locate the top-of-stack pointer judiciously. A common approach is to have it pointto the end of fixed-length fields in the activation record. Fixed-length data can then be accessed by fixed offsets, known to the intermediate-code generator, relative to the top-of-stack pointer.

The calling sequence and its division between caller and callee are as follows:

Ø     The caller evaluates the actual parameters.

Ø     The caller stores a return address and the old value of top_sp into the callee’s activation record. The caller then increments the top_sp to the respective positions.

Ø     The callee saves the register values and other status information.

Ø     The callee initializes its local data and begins execution.

A suitable, corresponding return sequence is:

Ø     The callee places the return value next to the parameters.

Ø     Using the information in the machine-status field, the callee restores top_sp and other registers, and then branches to the return address that the caller placed in the status field.

Ø     Although top_sp has been decremented, the caller knows where the return value is, relative to the current value of top_sp; the caller therefore may use that value.

Variable length data on stack:

The run-time memory management system must deal frequently with the allocation of space for objects, the sizes of which are not known at the compile time, but which are local to a procedure and thus may be allocated on the stack. The reason to prefer placing objects on the stack is that we avoid the expense of garbage collecting their space. The same scheme works for objects of any type if they are local to the procedure called and have a size that depends on the parameters of the call.

HEAP ALLOCATION

Stack allocation strategy cannot be used if either of the following is possible :

1.   The values of local names must be retained when an activation ends.

2.   A called activation outlives the caller.

Heap allocation parcels out pieces of contiguous storage, as needed for activation records or other objects. Pieces may be deallocated in any order, so over the time the heap will consist of alternate areas that are free and in use.

Fig. 2.10 Records for live activations need not be adjacent in heap

•   The record for an activation of procedure r is retained when the activation ends.

•   Therefore, the record for the new activation q(1 , 9) cannot follow that for s physically.

•    If the retained activation record for r is deallocated, there will be free space in the heap between the activation records for s and q.