Transcript PPT

Implications of
Substitution
Fall 2005 OOPD
John Anthony
Topics






Memory Allocation Strategies
The Java Memory Allocation Model
A Java Stack and Heap Example
Memory Allocation and Inheritance
An Example in C++ Using the Stack
Reference Assignment Strategies
Memory Allocation
Generally broken down into two strategies
(although variance does exist).
Static (Stack-based) Allocation

Static allocation means allocation of memory before
the program starts and retention until the end.

Compiler determines the exact size of the data
structure based on the software text.

Memory allocation and release is determined at
procedure entry and exit.

This means that the size of the program and its
“data” are determined before execution.
Dynamic (Heap-based) Allocation

Dynamic allocation means allocation of memory during
program execution.

Compiler cannot determine the exact size of the data
structure based on the software text.

Memory allocation and release is not determined at
procedure entry and exit.

Memory release either handled by programmer or
system (garbage collection).
Java (Thread) Execution State
Execution state of a Java thread has several runtime data areas:
Java stack
succession of frames representing method calls
Object heap
Objects used by a thread
Method area
Classes used by a thread
The Java Stack

A new frame for each
method execution

A frame includes local
variables of the
associated method and
operand stack that
contains partial results
(operands)

A frame also contains
registers such as the
program counter
Stack, Heap, and Method Area
Class
Reference
Object
Reference
Class Pool
Stack
Object heap

The heap associated with a thread contains all the objects used by
the thread (objects accessible from the thread’s Java stack)

The Class Pool associated with a thread contains the classes used
by the thread.
Stack – A Closer Look
Java Code
Stack
> int x;
> x = 5;
> double min = 0.5;
> boolean done = false;
Fernando Pereira University of Pennsylvania
Stack & Heap – A Closer Look
Java Code
Stack and Heap
> int x = 99;
> Counter c1;
> c1
null
> c1 = new Counter();
> c1
Counter@2f996f
> c1.incrementCount();
> Counter c2 = new Counter();
> c2
Counter@4a0ac5
Fernando Pereira University of Pennsylvania
Value of a Reference Variable


The value of are reference variable is either null or a “heap
address”
Example:








> Counter c1;
> c1
null
> c1 = new Counter();
> c1
Counter@e05ad6
e05ad6 is a hexadecimal (base 16) number
We don’t have to (and can’t) deal with these hex numbers directly
Fernando Pereira University of Pennsylvania
“Has a” Relationship


We’ll look at an example where an object A has an instance variable which is an
object whose type is B. (A “has a” B.)
We will create a DormRoom object, and a Freshman object whose room is that
DormRoom
What code should we write?
What will the stack and the heap will look like?
DormRoom Code and UML
public class DormRoom{
private int num;
private String bldgName;
public DormRoom(int n, String b){
num = n;
bldgName = b;
}
public String getLocation(){
return num + " " + bldgName;
}
}
> DormRoom room = new DormRoom(208, "Hill");
> room.getLocation()
"208 Hill"
A DormRoom on the Heap
> DormRoom room = new DormRoom(208, "Hill");
> room.getLocation()
"208 Hill"
Freshman Code and UML
public class Freshman{
private String name;
private DormRoom room;
public Freshman(String n, DormRoom r){
name = n;
room = r;
}
public String getName(){ return name;}
public DormRoom getRoom(){ return room;}
}
> DormRoom room = new DormRoom(208, "Hill");
> Freshman f = new Freshman("jo", room);
> f.getName()
"jo"
> f.getRoom().getLocation()
"208 Hill"
A Freshman on the Heap :)
> DormRoom room = new DormRoom(208, "Hill");
> Freshman f = new Freshman("jo", room);
> f.getName()
"jo"
> f.getRoom().getLocation()
"208 Hill"
Memory Allocation and Inheritance

If Stack Allocation is a more efficient memory
allocation and reclamation strategy, then why use
the heap?

Let’s look at one challenge as seen through the
eyes of C++ and polymorphism.
Consider the following….
class Window {
public:
virtual void oops();
private:
int height;
int width;
};
class TextWindow : public Window {
public:
virtual void oops();
private:
char * contents;
int cursorLocation;
};
If we create a new Window
(Window win;), how much
space on the Stack should be
allocated?
Three Choices

Allocate enough memory for the base class only.
(C++)

Allocate the maximum memory needed for any
legal value (base or subclass).

Allocate enough space to only hold a pointer.
(Smalltalk, Java)
Minimum Static Space Allocation


C++ uses this approach.
What happens when we execute the following
code:
Window win;
Window *tWinPtr;
.
.
.
tWinPtr = new TextWindow
.
.
.
Win = *tWinPtr
Slicing
height
height
width
width
…
…
contents
void Window::oops() {
cout << “Window oops”” << endl;
}
Void Window::oops() {
cout << “TextWindow oops”” << cursorLocation << endl;
}
cursorLocation
…
Rules for Member Function Binding
in C++

Variables declared as references or pointers, the binding
of the function name to the function body is based on
the dynamic class (as you’d perhaps expect).

With variables that are not pointers (i.e. declared on the
stack), the binding of the function name to the
function body is based on the static class.
Example
Window win;
TextWindow *tWinPtr, *tWin;
.
.
.
tWinPtr= new Textwindow;
win = * tWinPtr;
tWin = tWinPtr;
Win.oops();
tWin.oops();
Maximum Static space Allocation

Eliminates slicing problem by allocating the maximum
amount of memory necessary.

In order to do this, the entire program needs to be
scanned.

What about dynamic class loading….?

No major OO language takes this approach due to
restriction of “program scan”.
Dynamic Memory Allocation

The value is stored in a separate data area called the Heap.

Fixed size pointers are stored on the Stack and point to the heap.

Space on the heap is allocated when the object is created via the
“new” keyword (for Java).

What happens when after executing an assignment statement?
Pointer Assignment
Counter c1 = new Counter();
Counter c2 = new Counter();
c2 = c1;
0
Counter
0
Counter
c2
c1
Stack
Heap
Copy Assignment
Counter c1 = new Counter();
Counter c2 = new Counter();
c2 = c1;
0
Counter
0
Counter
0
Copied as a result of
assignment
Counter
c2
c1
Stack
Heap
A Hybrid Approach
Counter c1 = new Counter();
Counter c2 = new Counter();
c2 = c1;
0
Counter
0
Counter
Copied as a result of
modification (not
assignment)
Counter
c2
c1
Stack
0
Heap