Memory Allocation

From

Current revision as of 18:57, 9 April 2009

Before discussing the elementary data structures, we will talk about memory allocation. A data structure must have memory allocated to it if it is to store any data. There are two forms of memory allocation: static and dynamic.

Stack and Heap

The run-time environment for many languages sets up two areas of memory, usually called the stack and the heap. These areas are usually managed by code placed into an executable program by the compiler. The stack is the area for static allocation and the heap is the area for dynamic allocation.

Static Allocation

This means that memory is allocated at the time a program is compiled. Memory for static allocation is taken from an area called the stack. In some ways, static allocation is similar to the concept of fixed memory partitions. Just as fixed partitioning can suffer from internal fragmentation; we can have a similar problem with static allocation. Also static allocation has certain properties such as scope and lifetime.

Activation Record

When a method is called, there are some questions about memory usage. For example, when local variables are declared in a method, where does the memory come from? If parameters are passed to the method, how is this done? If the method returns a value, how does this get back to the calling method? The answer to these questions is usually found in a structure called an activation record.

Dynamic Allocation

This means that memory is allocated while a program is running. Memory for dynamic allocation is taken from an area usually called the heap. In many programming languages, a programmer must explicitly request dynamic memory to be allocated and explicitly release it when it is no longer needed. For example, both Java and C++ use the keyword new to request memory allocation, whereas the C programming language uses the function malloc(). Some languages, such as Java automatically try to clean up the heap. This situation is similar to variable memory allocation and external fragmentation. This process is called garbage collection. Other languages, such as C and C++ rely on a programmer to explicitly release dynamic memory that is no longer needed. This can be a source of memory leaks: both when a programmer forgets to release the memory and when the programmer “loses” the memory. This is similar to a child losing a balloon at the circus.