Transcript Chapter 4

Ch 4. Memory Management
Timothy Budd
Oregon State University
Memory Management
 Java : background memory management
• Advantage: allowing programmer to concentrate on
more application specific details
• Disadvantage: programmer has little control over how
memory management is performed.
 C++ : explicit memory management
• Advantage:permitting much more efficient use of
memory
• Can bloat a program at run-time, or make a program
very inefficient
Common Errors in C++
 Using a value before it has been initialized.
 Allocating memory for a value, then not deleting it
once it is no longer being used.
 Using a value after it has been freed.
Memory Model
 C++ model is much closer to the actual machine
representation than is Java memory model.
 Permits an efficient implementation at the expense of
needing increased diligence on the part of the
programmer.
 Stack-resident - created automatically when a
procedure is entered or exited.
 Heap-resident - must be explicitly created using the
new operator.
Stack Resident Memory Values
 C++
• Both the stack and the heap are internal data structures
managed by a run-time system.
• Values on a stack are strongly tied to procedure entry
and exit.
• When a procedure begins execution, a new section of
the stack is created.
 Java
• only primitive values are truly stack resident.
• objects and arrays are always allocated on the heap.
Program Example: test()
void test () // Java
{
int i;
int a[ ] = new int [10];
anObject ao = new anObject();
…..
}
void test () // C++
{
int i,
int a[10];
anObject ao;
…..
}
Drawbacks Using Stack
 Lifetime of stack resident memory values is tied to
procedure entry & exit. Stack resident values cease to
exist when a procedure returns. An attempt to use
resident value after deletion will typically result in error
or at least erratic behavior.
 Size of stack resident memory values must be known at
compile time, which is when the structure of the
activation record is laid out.
Lifetime Errors
 Once a procedure returns from execution, any stack
resident values are deleted & no longer accessible.
 A reference to such a value will no longer be valid,
although it may even seem to work for awhile until some
other function or interrupt routine is called which
overwrites the previously used stack area)
Program Example: readALine()
Char * readALine ()
{
char buffer[1000]; // declare a buffer for the line gets(buffer);
gets(buffer);
// read the line return buffer;
return buffer;
// return text of line
}
String readALine (BufferedInput inp) throws IOException
{
// create a buffer for the line
String line = inp.readLine();
return line;
}
char * lineBuffer; // global declaration of pointer to buffer
void readALine ()
{
char buffer[1000];
gets(buffer);
lineBuffer = buffer;
}
// declare a buffer for the line
// read the line
// set pointer to reference buffer
Size Errors - Slicing Problem
 Most severe restrictions of stack-based memory
management: positions of values within the activation
record are determined at compile time.
 For primitive values & pointers this is a small concern.
 For arrays: the array bound must be known at compile
time.
 For objects: a limitation on the degree to which values
can be polymorphic.
Array Allocations
 Stack resident arrays must have a size that is known at
compile time.
 Often programmers avoid this problem by allocating an
array with a size that is purposely too large.
 Rule: Never assume that just because an array is big, it
will always be “big enough”
Program Example
char buffer[200];
// making array
global avoids deletion error
char * readALine ()
{
gets(buffer); // read the line
return buffer;
}
char * buffer;
int newSize; // newSize is given some
value
…. buffer = new ChartnewSize]; //
create an array of the given size
….
delete [ ] buffer; // delete buffier when
no longer Being used
class A {
public:
// constructor
A () : dataOne(2) { }
// identification method
virtual void whoAmI () { printf("class A");
}
private:
int dataOne;
};
class B : public A {
public:
// constructor
B () : dataTwo(4) { }
// identification method
virtual void whoAmI () { printf("class B");
}
private:
int dataTwo;
};
Slicing Problem
 Java: polymorphic - a variable declared as maintaining a
value of one class can be holding a value derived from a
child class.
 In both Java and C++, it is legal to assign a value derived
from class B to a variable declared as holding an instance
of class A.
A instanceOfA; // declare instances of
B instanceOfB; // class A and B
instanceOfA = instanceOfB;
instaceOfA.whoAmI();
Slicing Problem
 Rule: Static variables are never polymorphic.
 Note carefully that slicing does not occur with
references or with pointers:
A & referenceToA = instanceOfB;
referenceToA.whoAmI(); // will print class B
B * pointerToB = new B();
A * pointerToA = pointerToB();
pointerToA -> whoAmI(); // will print class B
 Slicing only occurs with objects that are stack resident :
C++ programs make the majority of their objects heap
resident.
Heap Resident Memory Values
 Heap resident values are created using the new operator.
 Memory for such values resides on the heap, or free
store, which is a separate part of memory from the
stack.
 Typically accessed through a pointer, which will often
reside on the stack.
 Java hides the use of this pointer value, don’t need be
concerned with it.
 In C++, pointer declaration is explicitly stated.
Heap Resident Memory Values
void test () // Java
{
A anA = new A ( );
…….
}
void test () // C++
{
A * anA = new A; // note pointer declaration
if (anA == 0) ...
// handle no memory situation
delete anA;
}
Recovery of Heap Based Memory
 Java incorporates garbage collection into its run-time
library: the garbage collection system monitors the use
of dynamically allocated variables, and will
automatically recover and reuse memory that is no
longer being accessed.
 In C++, leaves this task to the programmer: dynamically
allocated memory must be handed back to the heap
manager using the delete operator. The deletion is
performed by simply naming the pointer variable.
Common Error in C++
 Forgetting to allocate a heap-resident value, and using a
pointer as if it were referencing a legitimate value.
 Forgetting to hand unused memory back to the heap
manager.
 Attempting to use memory values after they have been
handed back to the heap manager.
 Invoking the delete statement on the same value more
than once, thereby passing the same memory value
back to the heap manager.
Match memory allocations and deletions
 Null pointer exception.
 Memory leak: an allocation of memory that is never
recovered - cause the memory requirements for the
program to increase over time. Eventually the heap
manager will be unable to service a request for further
memory, and the program will halt.
 Result of an over-zealous attempt to avoid the
second error.
 Inconsistent state by the heap manager.
 Rule: Always match memory allocations and
deletions
Simple Techniques to manage heap
 Hide the allocation and release of dynamic memory
values inside an object.
 Maintaining a reference count that indicates the number
of pointers to the value. When this count is decremented
to zero, the value can be recovered.
Encapsulating Memory Management
 String literals in C++ are very low level abstractions.
 A string literal in C++ is treated as an array of character
values, and the only permitted operations are those
common to all arrays.
 The String data type in Java is designed to provide a
higher level of abstraction.
 A version of this data structure is provided in the new
Standard Template Library.
Program Example: resize()
void String::resize(int size){
if (buffer == O);
// no previous
allocation
buffer = new char[1+ size];
else if (size > strlen(buffer)) {
class String {
Public:
String
() : buffer(0) { } // constructors
String
(const char * right) : buffer(0)
{ resize(strlen(right)); strcpy(buffer, right);
}
String
(const String & right) :
buffer(0)
{ resize(strlen(right.buffer)); strcpy(buffer,
right.buffer);
}
String () { delete [ ] buffer; } // destructor
void operator = (const String & right) //
assignment
{ resize(strlen(right.buffer));
strcpy(buffer, right.buffer); }
private:
void resize (int size);
char * buffer;
};
delete [ ] buffer; // recover old value
buffer = new char[1 + size];}
}
Destructor in C++
 Destructor: a preocedure that performs whatever
housekeeping is necessary before a variable is deleted.
 Destructor class is a non-argument procedure with a
name formed by prepending a tilde before the class
name.
 Can match all allocations and deletes, ensuring no
memory leaks will occur.
 delete operator is the function used to actually return
memory to the heap manger
finalize in Java
 A finalize method invoked when the value holding the method
is about to be recovered by the garbage collector.
 Cannot make assumptions concerning behavior based on the
execution of code in a finalize method.
Execution Tracer
 The class Trace takes as argument a string value. The
constructor prints a message using the strings and the
destructor prints a different message using the same
string:
 To trace the flow of function invocations, the
programmer simply creates a declaration for a dummy
variable of type Trace in each procedure to be traced
Program Example: class Trace
class Trace {
public:
Trace (string); // constructor and destructor
~ trace ();
private:
string name;
};
Trace: :Trace (string t) : name(t){
cout << "Entering " << name << end1;
}
Trace : : ~Trace (){
count << “Exiting “ << name << end1;
}
Program Example: procedures
void procedureOne (){
Trace dummy("Procedure One");
….
procedureTwo(); // proc one invokes proc two
}
void procedureTwo (){
Trace dummy("Procedure Two");
….
If (x < 5) {
Trace dumTrue("x test is true");
…..
}
else {
Trace dumFalse("x test is false");
…..
} …..
}
Auto_ptr Class
 There is an object that must dynamically allocate
another memory value in order to perform its intended
task
 But the lifetime of the dynamic value is tied to the
lifetime of the original object; it exists as long as the
original objects exists, and should be eliminated when
the original object ceases to exist.
 To simplify the management of memory, the standard
library implements a useful type named auto_ptr.
Reference Count
 Reference Count: the count of the number of pointers
to a dynamically allocated object.
 Ensure the count is accurate: whenever a new pointer is
added the count is incremented, and whenever a pointer
is removed the count is decremented.
Reference Count (Table)
“abc”
“xyz”
string a = “abc”
1
0
string b = “xyz”
1
0
string c;
1
1
c = a;
2
1
a = b;
1
2
g = b;
2
2
end of execution:
destructor for c
destructor for b
destructor for a
1
1
1
2
1
0
Statement