CONTENT BEYOND SYLLABUS - V
Storage Management
Classification of storage
In languages like C or Java, the storage used by a program generally comes in three categories.
Static storage. This refers to variablesgenerally given names by declarations whose lifetime by definition
encompasses the entire programs execution.
Local storage. Variablesalso usually named in declarationswhose lifetimes end after the execution of
some function or block.
Dynamic storage. Variables (generally anonymous) whose lifetime begins with the evaluation of a specific
statement or expression and ends either at an explicit deallocation statement or at program termination.
For example, in Java, static variables are introduced by as static fields in classes. C and C++ also allow for
static variables in functions and outside classes and functions (at the outer level where they are in e ect
static fields in a giant anonymous class). For example,
int rand(void)
/* C code */
{
static int lastValue = 42; extern int randomStatistics;
...
}
Here, there is a single variable lastValue and a single variable randomStatistics that retain their last values
from call to call. It is true that only the function rand is allowed to access lastValue by name, but that is an
1
independent question . Local variables in Java and C are simply non-static, non-external variables or
parameters declared in a function. They disappear upon exit from the function, which is why the following
piece of code, beloved of C beginners, is almost certainly incorrect.
int* newIntPointer(int N) /* C code */
/* Return a pointer to an integer initially containing N. */
{
int X = N; return &X;
}
In C, one can have pointers to simple containers: &X creates a pointer to the con-tainer X, and int* denotes
the type pointer-to-int. The variable X o cially dis-appears immediately after the return. Practically speaking,
this means that the compiler is allowed to re-use the storage location that was used to contain X at any
subsequent time (which will probably be the very next call to any function).
Finally, dynamic variables in Java and C++ are the anonymous objects the programmer creates using
new, or in C using calloc or malloc. In C and C++, any deallocation that takes place must be explicit (by use of
the free function or delete operator, respectively). Languages like Java and Lisp have no explicit free
operation, and instead deallocate storage at some point where the storage is no longer needed. Well discuss
how later in this chapter
Just to show that hybridization is possible, some C implementations support a function called alloca. This
takes the same argument as malloc and returns a pointer to storage. But the lifetime of the storage ends
when the function that called alloca exits (one may not free storage allocated by alloca). The storage is there-
fore sort of locally dynamic. It is useful for functions that create local linked lists (for example) or arrays
whose sizes are not known at compilation. Alas, due to the peculiar runtime memory layouts used by some
machines and C implementations, it is not a standard function.
DYNAMIC STORAGE ALLOCATION WITH EXPLICIT
Stack
Unallocated
Heap
Static
storage
Address 0
Executable
code
An example of run-time storage layout: the Unix C library strategy.
the area containing instructions and constants for the program (which is called the text segment). Local
storage resides in the run-time stack, which grows down toward the static storage area. The area in between
is available for the program to request and use as it will. The standard C library uses the beginning of this
area for dynamic storage, growing the portion it uses for this purpose toward the stack. By an unfortunate and
confusing convention, the dynamic storage area is known as the heap, although it has nothing in common
with the data structure we have used for priority queues.
Garbage collection
Copying garbage collection shares one problem with mark-and-sweep: long-lived objects are repeatedly
traversed, even though they tend not to change very quickly after they are allocated and initialized. Also, in
typical programs written for lan-guages like Lisp, objects that become garbage often tend to do so early in
their lifetimes. This suggests that it would be nice to restrict garbage collection to young (recently-allocated)
objects, ignoring ones that have remain reachable for a certain period of time. With some care, this can be
done; the result is known as generational garbage collection.
The idea is to divide objects into generations, each in a separate area of memory. Objects are initially
born into the youngest generation. When the to-space for this generation fills up, it is garbage collected
using copying, but pointers into older generations (whose objects were allocated before those in the youngest
generation) are mostly ignored (i.e., not traversed). Objects that survive one or more of these collections of
the youngest generation (details vary from system to system) are tenuredthat is, copied into the to-space
for the next-older generation. Because objects tend to die young, this older generation fills up much more
slowly than the youngest. It is also made to be much larger than the youngest generation, so that the need to
perform garbage collection for the older generations is relatively uncommon.
Roots
B
5
from:
to:
A B
C
D
42 D G F A
E
7 G D
A B*
C
D
42 B G F A
E*
7 G E
A B*
C
D*
42 B G F A D
E*
7 G E
G*
C G E
B
E
D G D
G*
C G E
(a)
Roots
B
5
from:
(b)
E
to:
B
D
G
C
E
G D
Roots
B
5
from:
to:
(c)
G
7
Roots
B
5
from:
to:
(d)
A B*
C
D*
42 B G F A D
B
E
D G D
E*
7 G E
G
7 G
