Transcript ch7.n
Runtime Environments
Chapter 7
Support of Execution
Activation
Tree
Control Stack
Scope
Binding of Names
– Data object (values in storage)
– Environment (functions that map to stg)
– State (funct that maps a stg location to
the value held there)
Storage Allocation Strategies
Static
– Names are bound to storage at compile
time
Dynamic
– names are bound to storage at run
time
Comments Related to Static
C,
C++, Pascal, Algol, Ada
Data does not exist after the function
finishes.
Storage Organization
CODE
STATIC DATA
STACK
\/
/\
HEAP
Stack
Allocate
activation record
Locals get new storage
Enters information into its fields
Activation Record (Stack Frames)
Returned
value
Actual parameters
Optional control link
Optional access link
Saved machine status
Local data
Temporary data
Calling Sequence
Caller
evaluates arguments
Caller stores return address in
callee’s activation record
Caller stores stack top
Callee saves register values and
status information for caller
Return Sequence
Callee
restores state of machine
Callee places return value next to the
activation record of the caller
Restores top of stack pointer
Caller copies return value
Variable Length Data
Arrays
– Stored after the activation record
– The activation record does not have to
allocate space for the array
Comments Related to Dynamic
LISP, Smalltalk
When
static doesn’t work
– If data is referenced from an activation
record after the function finishes.
– In static memory allocation, this is
referred to as a dangling reference
Demonstrated
by the following program
– 2nd example may be a desirable
situation demonstrating inadequacy of
stack based environments.
Heap vs Stack Allocation
Stack
allocation cannot be used if
– Local names must be retained after
activation ends
– Activation outlives caller
Dangling Reference
int *dangle();
main(){
int *p;
p = dangle();
sub();
}
int *dangle(){
int i = 23;
return &i;
}
sub(){
int i,j,k;
}
printf("p = %d\n",*p);
printf("p = %d\n",*p);
Dangling Reference caused by
local function
typedef int (* proc) (void); /*ptr to proc,
proc defined */
proc g(int x)
/* g of type proc */
{ int f(void)
/* local function*/
{ return x; }
return f; }
/* returns f to c */
main()
{ proc c;
c = g(2);
printf(“%d\n”,c()); /* should print 2 */ }
Heap Management Strategies
free
list
first fit
best fit
worst fit
Garbage Collection
records
not reachable
reclaim to allow reuse
performed by runtime system
(support programs linked with the
compiled code)
Record Types
alive
– will be used in the future
not alive – will not be used in the
future
reachable – able to be accessed via
programs
Types of Algorithms
Mark-And-Sweep
Reference
Collection
Counts
Copying Collection
Generational Collection
Incremental Collection
Mark-And-Sweep Collection
Program
variables and heap records
form a directed graph
Roots are the variables
node n is reachable if
r -> … -> n
Depth first search marks reachable
nodes
Any node not marked is garbage
Cost of Garbage Collection
Depth
first search takes time
proportional to the number of
reachable nodes
Sweep phase takes time proportional
to the size of the heap
Maintaining Free Space
Create
a list of free space
Search for a space of size N might be
long
Maintain several free lists of differing
sizes
External fragmentation a problem
Internal fragmentation can also be a
problem
Reference Counts
Count
the number of pointers
pointing to each record
Store the reference count with each
record
If p addresses an alternate record,
decrement the old and increment the
new
If count reaches 0, free record
When to Decrement
Instead of decrementing the counts a
record references when the record is
placed on the free list, it is better to
do this when the record is removed
from the free list.
Why
Breaks
the recursive decrementing
work into shorter pieces
Compiler emits code to check
whether the count has reached 0,
but the recursive decrementing will
be done only in one place, in the
allocator
Problems with Reference Count
Cycles
of garbage cannot be
reclaimed
Incrementing the reference counts is
very expensive
Solutions-Cycles, Expensive
Require
the programmer to break
the cycle
Combine reference counting with
mark-sweep
No solution for it being expensive
Problems outweigh advantages, thus
rarely used
Copying Collection
Reachable
part is a directed graph
with records as nodes, pointers as
edges, and variables as roots
Copy the graph from “from-space” to
“to-space”
Delete all “from-space”qq
Access to Nonlocal Names
Lexical
scope without nested
procedures
– Allows nonlocals to be found via static
addresses
– Uses physical layout
– All storage locations known at compile
time
– Functions can be passed as parameters
Lexical Scope Example
main { /* main */
A.R. main
p();
…
} /* main */
A.R. p
p{
control link main
int n;
no access link
n = 1;
…
r(2);
A.R. r
fun q{
/* inside of p */
contol link p
n = 5; /*n non-local non-global*/ access link p
}
…
fun r(int n){ /* inside of p */
A.R. q
q();
control link r
}/* r */
access link p
}
…
Access Chaining Example
main{
A.R. main
p();
…
fun p{
A.R. p
int x;
ctl link main, acc main
q();
A.R. q
fun q{
ctl link p, acc link p
r();
A.R. r
fun r{ /* fun r */
ctl link q, acc link q
x = 2;
A.R. p
if ... then p();
ctl link r, acc link main
} /* fun r */
A.R. q
} /* fun q */
ctl link p, acc link p
} /* fun p */
A.R. r
} /* fun main */
ctl link q, acc link q
Passing Function Example
main{
q();
fun p (fun a) {
a();
} /* end p */
fun q {
int x;
x = 2;
p(r);
fun r{
printf( x );
} /* end r */
} /* end q */
} /* end main */
A.R. main
…
A.R. q
ctl link main, acc main
A.R. p
ctl link q, acc main
A.R. a
ctl link p, acc q
Dynamic Scope
lisp, apl, snobol, spitbol, scheme
main(){
float r;
r := .25;
show; small;
show; small;
}
fun show{
printf(r);
}
fun small{
fun r;
r := 0.125;
show;
}
What is printed?
Parameter Passing
Call
by
Call by
Call by
Call by
value
reference (address)
copy restore
name
Call by Value
Only
the value is passed
Storage is in the A.R. of called
function
Caller evaluates and places the value
in callee A.R.
Operations do not effect original
value
Call by Reference
Caller
passes pointer to callee
if a+b is passed, the address of a
temporary is used
Consider swap(i,a[i])
– Does indeed swap
– Addresses are bound at time of call
Call by Copy-Restore
Value
of argument is given to callee
Upon completion value is copied back
to caller
swap(i, a[i]) works correctly
Copy-Restore/Reference Example
int a = 1;
main() {
unsafe(a);
print(a);
}
fun unsafe( int x) {
x = 2;
a = 0;
}
Copy-Restore/Reference Example
Nested Functions
main() {
int a = 1;
unsafe(a);
print(a);
fun unsafe( int x) {
x = 2;
a = 0;
}
}
Call by Name
A
macro
Body of the function replaces the call
Local values are protected
swap(i, a[i]) does not work since i
will have changed value
Call by Name Example
#include <stdio.h>
int temp;
#define swap(x,y) { temp = x, x = y, y = temp; }
main(){
int i;
int a[5] ={1,2,3,4,5};
for(i = 0; i < 5; i++)
printf("a[%d]=%d ",i,a[i]);
i = 3;
swap(i,a[i]);
for(i = 0; i < 5; i++ )
printf("a[%d]=%d ",i,a[i]);
}
Prints a[0]=1 a[1]=2 a[2]=3 a[3]=4 a[4]=3
Dynamic Memory Object Oriented
langagues
Memory
is a cross between a
traditional record structures and an
activation record
Instance variables are fields of the
record (data members)
Structure differs from a traditional
record in how methods and inherited
features are accessed
How to implement objects?
Copy all the inherited features and
methods directly into the record structure
– Wasteful of space
Keep a complete description of the class
structure in memory. Inheritance
maintained by superclass pointers.
All method pointers kept as fields in the
class structure. (an inheritance graph)