Memory management: Stack Model Vs. Heap Model

Objectives

Different Perspectives of Memory Services

• Hardware level: operations like READ and WRITE.
• Operating System level: sharing of the physical memory among different processes, allocating memory to processors, etc.
• Programming Language: how programming language constructs relate to memory operations at runtime and at compile time.

Background: Memory Technologies

• On-chip storage - registers and cache storage - very fast storage which generally reside on the same chip as the main processor
• Random Access Memory - a family of technologies used to implement the computer main memory the RAM.
• Persistent online storage - Hard disk or solid state disks using magnetic or electromagnetic technologies.
• Persistent offline storage - Tapes/DVD/CD are magnetic or optical offline storage technologies.

The following properties characterize the memory system of a computer:

1. Memory space: how much main memory the processor can address (maximum potential size)
2. Word size: words are the native units of data the CPU operates on. Usually, internal registers can store exactly one word, and writes/reads from main memory are at lease word-sized.

1. Width of the address bus: memory is viewed as an array of words. Each word has an index (0, 1, …, up to the size of the memory space). The index of a word in the main memory is called its address.
2. Width of the data bus: memory is read and written to/from registers in the processor and locations in main memory. Each such operation is performed on a single word at a time. The size of the word is determined by the number of physical connections (lines) between the processor and the memory system.

Hardware Perspective

1. Load the data from memory into internal processor registers.
2. Apply the operation on the registers and put the result in another register.
3. Write the result from the register into the relevant memory location.

• Read (Address), (Register): copy the content of the word stored at (Address) into the (Register) of the processor. Registers are referenced by their number (0, 1, … number of registers on the processor).
• Write (Register), (Address): copy the content of the (Register) to the memory cell at (Address).

The compiler generates the relevant code for the CPU to execute. The generated code in an abstract set of processor instructions would look like the following code; by convention, we write [var] to denote the address in memory in which a variable is stored.

;; Initialize the memory cells for i and j
WRITE $10, [i]		;; 10 is a constant value
WRITE $20, [j]		;; 20 is a constant value

;; Execute the sum
READ [i], R1		;; copy the content of i in register 1 (R1)
READ [j], R2		;; copy the content of j in register 2 (R2)
ADD R1, R2, R3		;; execute the operation: R1 + R2 and store the result in R3
WRITE R3,[i]		;; store the result in the memory location of i

Programming language perspective

We start with a discussion of how Java constructs relate to memory. We then compare the Java approach with the C++ approach and stress the differences.

Which explicit/implicit memory-related services we already used in Java?

• Object allocation - Object allocation using new
• Initialization - Constructor invocation or variable initialization
• Copying - Copying data from one variable to another

• Object deletion - done by the Garbage Collector
• Variable allocation - Local (primitive) variables allocation
• Variable deallocation - Local variable deallocation when leaving scope

Memory Access

1. A name
2. A type
3. A scope: the program region in which the name is recognized and refers to the same variable

1. A type
2. A position in memory which is the value address
3. A size - how much memory does the value requires in memory

• They are identical
• The type of the value is more specific in the inheritance hierarchy than the type of the variable.
• The type of the value implements the type of the variable (when the type of the variable is an interface).

Stack model vs. Heap model

Procedures

Stack

• The parameters passed to the procedure
• Local primitive variables declared in the procedure
• The return value - Where to return to when the procedure ends

public static void foo(int a, bool b){
        int var_a;
        int var_b;
        .
        .
        .
}

Each time the function is invoked, an appropriate activation frame will open on the stack, which will look something like this:

When an activation frame is created, the binding between local variables and their location on the stack is made. When a procedure terminates, its associated activation frame is popped from the stack, and (figuratively) discarded.

In Java, only the variables located on the top-most activation frame may be accessed (parameters and local variables). However, as we will see, this is not the case in C++ (and we are not referring to pointers!).

Stack Implementation

Heap

Before we go into the details of how usually heaps are implemented by an RTE, let us see where we have made use of the heap in Java. In Java, there is a clear distinction between what is saved on the stack and what is stored on the heap. In Java, all local variables of methods are stored on the stack and all Objects, are stored on the heap.

Consider the following code snippet:

We need to make a clear distinction between the Object which might be very big, with enough space to hold the entire state of Object, and the variable o which holds the location of the Object on the heap! More specifically, the section associated with o on the stack holds a reference (a number) to the starting location of the block of memory new allocated to hold the instance of the new Object().

This distinction between Objects and primitives in Java explains why primitives are always passed to functions by value and Objects always by reference.

Heap Implementation

Memory deallocation in Java

However, we have not mentioned how memory in Java is freed. What happens to an Object once we have no further use for it? e.g., we allocated an array inside some function, and then left the function without leaking the reference to the array outside of the scope of the function. Should the array be kept in memory indefinitely? No. This would exhaust our memory rapidly. We would like to reuse the memory used by the array, in a way to tell the RTE that the memory can be recycled. In Java, this is done automatically for us, by an active entity which is called the garbage collector.

Once in a while (or when the user asks by calling System.gc()), the garbage collector kicks into action, and recycles, or frees, all garbage Objects. An Object is considered garbage if it cannot be accessed from a variable on the stack. The algorithm of the garbage collector essentially works like this:

1. Compose a set of all Objects referenced from the stack and from registers.
2. For each Object in the set, add all Objects it references.
3. Repeat step (2) until the set remains unchanged (in essence, compute the transitive closure of the "a references b" relation).
4. Free all objects which are not in the set.

Stack and Heap in C++

Stack

We later discuss three important methods of objects in C++: The destructor, copy constructor and assignment operator.

Objects on the stack and pass by value

void doSomething(Foo foo2)
{
        foo2.changeMe(...);
}
Foo foo1;
doSomthing(foo1);

During runtime, the following takes place:

1. A place to hold class Foo is reserved on the stack and is binded with the variable foo1.
2. The default constructor is called
3. An activation frame for doSomthing is created, with enough space to hold the return address and an object of class Foo.
4. A new object of class Foo is instantiated on the stack, by using the copy constructor of class Foo and passing foo1 as the argument.
5. The method changeMe() of the object foo2 is called.
6. The destructor of foo2 is called.
7. The doSomething frame is poped from the stack and the program continues from the return address.

Now consider another example:

Foo doSomething(Foo foo2)
{
        foo2.changeMe(...);
        return foo2;
}
...
Foo foo1;
Foo foo3 = doSomething(foo1);

During runtime, the following takes place:

1. A place to hold class Foo is reserved on the stack and is binded with the variable foo1.
2. A place to hold class Foo is reserved on the stack and is binded with the variable foo3.
3. The default constructor is called for foo1
4. An activation frame for doSomthing is created, with enough space to hold the return address and an object of class Foo.
5. A new object of class Foo is instantiated on the stack, by using the copy constructor of class Foo and passing foo1 as the argument.
6. The method changeMe() of the object foo2,is called.
7. foo2 is copied by the copy constructor of class Foo to the location of foo3.
8. The destructor of foo2 is called.
9. The doSomething frame is poped from the stack and the program continues from the return address.

Heap

New and Delete Operators

Please notice that the returned value of new a_type(vars) is always of type a_type *, which is called a pointer to a_type (but more on pointers in the next lecture).

The memory is initialized using the constructor we requested (which must exists, otherwise our code will not compile).

In contrast to Java, memory allocated on the heap in C++ is never garbage collected, and it is the responsibility of the programmer to free the memory. For example, to free the memory we allocated earlier we will use the following code:

Each time we delete an object, its destructor is called.

Allocating and Deleting Arrays in C++

Foo *foo_array = new Foo[100];

Pay attention that the type returned by the new [] operator is, again, of type Foo *. Again, pointers, which we will discuss in the next lecture. But this is not the important point. The important point is that we have allocated a block of memory on the heap, large enough to hold 100 Foo objects. Each object is then initialized using the default constructor of class Foo (note that the default constructor of primitive numbers is 0, bool is false and pointers are 0).

But, how can we release the memory? by calling the delete[] operator!

delete[] foo_array;

Which, in turn, calls the destructor of each object in the array, and then frees the memory.

Note that new and new[] are not the same operators. Same holds for delete and delete[]. You must pay attention to call delete[] on memory allocated by new[] and delete for memory allocated by new.