Stack storage:
Names local to a procedure are allocated space on a stack. The stack supports the normal call/ return policy for procedures.
Heap storage:
Data that may outlive the call to the procedure that created it is usually allocated on a “heap” of reusable storage. The heap is an area of virtual memory that allows objects or other data elements to obtain storage when they are created and to return that storage when they are invalidated.
To support heap management, “garbage collector” enables the run time system to detect useless data elements and reuse their storage, even if the programmer does not return their space explicitly.
Automatic garbage collection is an essential feature of many modern languages, despite it being a difficult operation to do efficiently; it may not even be possible for some languages.
Stack Allocation of Space
Almost all compilers for languages that use procedures, functions, or methods as units of user-defined actions manage at least part of their runtime 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.
This arrangement not only allows space to be shared by procedure calls whose durations do not overlap in time, but it allows us to compile code for a procedure in such a way that the relative addresses of its nonlocal variables are always the same, regardless of the sequence of procedure calls.
Activation Trees
- Stack allocation would not be feasible if procedure calls, or activations of procedures, did not nest in time.
- We can represent the activations of procedures during the running of an entire program by a tree, called an activation tree.
- Each node corresponds to one activation, and the root is the activation of the “main” procedure that initiates the execution of the program.
- At a node for activation of procedure p, the children correspond to activations of procedures called by this activation of p.
- We show these activations in the order that they are called, from left to right.
- Note: one child must finish before the activation to its right can begin.
Activation Records
- Procedure calls and returns are managed by a runtime stack called control stack.
- Each live activation has an activation record (also called a frame) on the control stack, with the root of the activation tree at the bottom, and the entire sequence of activation records on the stack corresponding to the path in the activation tree to the activation where control currently resides.
- The later activation has its record at the top of the stack.
Heap Management
- Heap is a portion of the store that is used for data that lives indefinitely, or until the program explicitly deletes it.
- Local variables typically become inaccessible when their procedures end.
- Many languages enable us to create objects or other data whose existence is not tied to the procedure activation that creates them.
- Both C++ and Java give the programmer new to create objects that may be passed – or pointers to them may be passed – from procedure to procedure, so they continue to exist long after the procedure that created them is gone.
- Such objects are stored on a heap.
- The memory manager is a subsystem that allocates and deallocates space within the heap;
- It serves as an interface between application programs and the operating system.
- For languages like C or C++ that deallocate chunks of storage manually (e.g., by using free or delete).
- The memory manager is also responsible for implementing deallocation.
- Garbage collection is the process of finding spaces within the heap that are no longer used by the program and can therefore be reallocated to house other data items.
- For languages like Java, it is the garbage collector that deallocates memory.
- When it is required, the garbage collector is an important subsystem of the memory manager