Document

RUN-TIME STORAGE
c
Chuen-Liang Chen
Department of Computer Science
and Information Engineering
National Taiwan University
Taipei, TAIWAN
Chuen-Liang Chen, NTUCS&IE / ‹#›
Program layout (1/2)
 typical program layout
heap space
stack space
static data
literal pool
program code for
library and
separately compiled
modules
highest address
have to check collision
dynamic


static
c
added by linker/loader
each block can be
allocated to a
“segment” under
segmented memory
system
operand stack is
required for some
computer; Its size can
be determined at
compile-time
static data
literal pool
program code
reserved locations
read only
read only
eg. used by O.S
lowest address
Chuen-Liang Chen, NTUCS&IE / ‹#›
Program layout (2/2)
 for load-and-go compiler
highest address
static data
and
literal pool
heap space
c
generated iteratively
stack space
program code
library modules
reserved locations
lowest address
Chuen-Liang Chen, NTUCS&IE / ‹#›
Static allocation
 space is allocated in fixed location for the life-time of a program
 applicable only when the number and size of data objects is known at
compile-time
 suitable for
c

global variables

literals (or put them on a separate “literal pool” )

the only choice for early language (e.g. without recursion)
 preferable to address a data object as (DataArea, Offset) and binding
DataArea at link-time
Chuen-Liang Chen, NTUCS&IE / ‹#›
Heap allocation
 space is allocated and freed at any time and in any order
 suitable for dynamic memory allocation/deallocation
 allocation -- in demand
 best-fit
 first-fit
 circular-first-fit
 QUIZ: comparison
 deallocation
c
 no deallocation
(work for implementations with a large virtual memory)
 explicit deallocation
 implicit deallocation
– single reference
– reference count
– mark-and-sweep garbage collection [ + compaction]
 QUIZ: comparison
 free-space representation -- bit map, linked list
Chuen-Liang Chen, NTUCS&IE / ‹#›
Stack allocation (1/2)
 suitable for recursive call
 activation record (AR) -- data space required for a call
 push / pop, when “call” / “return”
 example -space for e
determined at
space
for
d
procedure p(a:integer) is
run-time
pointer to e
b: real;
c: array (1..10) of real;
pointer to d
d,e : array (1..N) of integer;
c dope vector
begin
determined at
c
b := c(a) * 2.51;
compile-time
b
end;
a
control
information
register
Offset = 0
– 2.51 is stored in literal pool
– dope vector -- fixed size descriptor for dynamic array;
containing size and bounds of array (determined at run-time)
Chuen-Liang Chen, NTUCS&IE / ‹#›
Stack allocation (2/2)
 when too many recursive calls
 too many AR
 too many registers

c
solutions: display registers & static and dynamic chains
 QUIZ: coroutine?
 QUIZ: variable declaration within block?
Chuen-Liang Chen, NTUCS&IE / ‹#›
Display registers (1/2)
 observation (by scoping rules) --at most one active scope for one static
nesting level at any time
 example -program
runtime
active scopes (display) of
stack
P1 R1 Q1 Q2 S1 S2 R2 P2 P3 Q3 R3
P()
2
R3: c
int a
2
Q3: b, S
Q()
1 1 1
P3: a, Q,
int b
cR
1
P2: a, Q, R
S()
2
R2: c
int d
3
S2: d
P;a,Q,R;b,S;d
3
S1: d
P;a,Q,R;b,S
2 2 2
Q2: b, S
R()
2
Q1: b, S
int c
2
R1: c
P;a,Q,R;c
1 1 1 1 1 1 1
P1: a, Q, R
P;a,Q,R
Chuen-Liang Chen, NTUCS&IE / ‹#›
Display registers (2/2)
 strategy -- allocating one display register for one static nesting level


c
have to be modified when routine call / return
QUIZ: detailed implementation
Chuen-Liang Chen, NTUCS&IE / ‹#›
Static and dynamic chains
 using one register only; point to uppermost AR
 static chain -- alternative implementation of a display
 dynamic chain -- list of AR entry on run-time stack, to restore activation
register
runtime
active scopes (display) of
stack
P1 R1 Q1 Q2 S1 S2 R2 P2 P3 Q3 R3
 example -2
R3: c
2
Q3: b, S
activation
1 1 1
register
P3: a, Q, R
c
1
P2: a, Q, R
2
R2: c
3
S2: d
3
S1: d
2 2 2
Q2: b, S
2
Q1: b, S
2
R1: c
1 1 1 1 1 1 1
P1: a, Q, R
dynamic
static
chain
chain
Chuen-Liang Chen, NTUCS&IE / ‹#›
Advanced features
 formal procedure
c
 QUIZ: how?
Chuen-Liang Chen, NTUCS&IE / ‹#›