Run-time Systems

As discussed at the beginning of the course, few programs run stand-alone, a supporting environment is needed. An integral part of a run-time system is how memory is allocated and deallocated both for language implementation structures (implict allocation) and for user program structures (explicit allocation). Allocation class depends on scope and extent of variable referring to location/structure:

scope:

local, global, lexical, dynamic

extent:

dynamic, indefinite

Dynamic Typing

Need to be able to distinguish between types at run-time. Three techniques:

boxed:

Obvious first choice, store type (integer, class) in fixed position in evry structure. Lisp, Spitbol, Basic, PASCAL (variant records). Disadvantage is that type checking now requires an indirection operation (conflicts with cache assumptions on most machines) and small objects (characters, integers) that can be stored in a single word (usually) must now be heap allocated.

tagged:

Use unused bits in the address of an object-tends to be architecture dependednt, although can still be relatively portable. Saves indirecting to check type and is also more economical on heap consumption (although it is arguable how important this is).

address ranges:

multiple homogenous heaps (Franz Lisp). Allocate fixed types in such pages (eg. cons cells, vectors and floats (64 bit)). Doesn't accomodate extensible systems (where new classes can be defined). Have to use a page of escape class (or some such technique).

Static Allocation

Allocated once, in a fixed location-for example: C static and FORTRAN COMMON blocks (mention EQUIVALENCE).

Automatic Allocation

Allocated and deallocated at particular times and in a particular order (LIFO). Don't know how many recursions and don't know how much space-only when. Activation record or frame: arguments + locals + temporaries. Compilations stores information about position (offset) into AR. Need to access several ARs to deal with nested lexical scope: either use indirection (static chain pointer) or display (hardware solution). Display registers (d0...di) point directly to enclosing lexical block i steps away just as fp points to current frame (d0). Adds to complexity of function call and return since these regsiters must be handled explicitly (mention B6500). Note: do not need an AR per block (since blocks can be merged at compile time), only per procedure.

Heap Allocation

Allocated at will and deallocated at unpredictable times. Three policies:

1. no deallocation or let programmer handle it entirely
2. explicit deallocation-for example C, PASCAL-but when to free is programmer's decision (easy to get it wrong).
3. implicit deallocation or garbage collection, when it can be proven that structure can no longer be accessed by the normal action of the program.

Need heap allocation because:

1. long-term or variable sized user data structures-for example: lists nodes.
2. procedure/function values (closures): copy AR (and static chain) into heap or allocate in heap initially. Static analysis can determine (conservatively) when to do which.

Two kinds of garbage collection: intrusive, real-time. Two phases, each with two techniques:

Identifying what to recover  Making storage available for re-use
----------------------------------------------------------------
reference counts             free-list
tracing and marking          compaction

Reference Counting

Practical implementations always use free-lists for making storage available for re-use. Explain. Pros: immediate return, simple implementation, fragmentation. Cons: overhead on all primitive operations (assignment, head, tail), cannot handle circlar structures.

Mark And Sweep

Can either use free-list or compaction for sweep phase. Explain. Backpointer traversal. Pros: physical memory utilisation, circular structures. Cons: amount of work and VM hit.

Stop And Copy

Compaction is implicit in the copy phase. Explain. Pros: circular structures, compaction for free, live structure only (VM performance: good in TO space, but bad in FROM because of the access patterns-depends on use of depth-first or breadth first copying). Cons: uses twice amount of actual memory.

Summary

This is far from exahustive coverage of GC-there are probably as many GC algorithms as there are implementations-and there are several important variants of the above that we do not have time to discuss. Do not conclude that reference couting is the only way to do real-time GC. Do not choose between mark/scan and stop/copy now. Choose technique to suit situation and read the literature. This is still something of a black art.