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)
