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 / ‹#›