[ explain roots ]
 [ explain transitive closure def'n of garbage ]
 [ note alternative def'n of what is garbage: denotaitonal,
   distributed's semi-garbage, dijstra's tricolored nodes,
 [ java's: reachable, unfinalized, finalizable, finalized; motivation:
   Just before destruction a Java object gets its finalize method called,
   and during this time the object is again (briefly) strongly referenced
   through this pointer ]
 [ note terminology: referencing object --> referent ]
 [ note weak references; also Java's weak arrays;
   also Java's hierarchy strong, soft, weak references, (also, no references) ]

Five Kinds:

1. power cycle (don't bother)
  
- circa late 80's early 90's:  symbolics, lisp machines

- first JDK VM didn't have working garbage collector (usenet threads re:
finalize never called)

2. reference counting

 [ draw diagrams - show how object get created, show how garbage is
 formed when unlinking pointers, show recursive discovery of garbage,
 then show another example with cycle ]


3. mark and sweep

[ draw picture - some nodse gabage, some not, w/ 4-5 areas cicles.
 later to show VM pages ]

PHASE 1: (psuedocode) Mark

recusive alg.

[ mention there is another iterative variant that uses pointer reversing in
place to ensure constant space overhead ]

PHASE 2: (psuedocode) Sweep

for i in [0..n]
  if unmarked -> add to freelist
  [] marked -> unmark
  fi


[ big-Oh analysis do both time and space ]

summary what's wrong: always linear time, poor response-time
performance, poor locality of reference

More Garbage Collection


[ quiz 11 ]
4. stop and copy

5. generation scavenging


generation scavenging
Data Types and GC


ADT (paraphrale of Guttag et al.'s definition)
- finite set of operations
- possibly infinite set of operations
- operations completely characterize the type

[ more data type info from textbook ]

GC
1. power cycle (i.e., don't bother)
2. reference counts (but cycles)
3. mark and sweep (historical, not used, but distributed GC modeled on m-s)
4. stop and copy (easy to implement, locality of reference, fragmentation, 
compaction)
5. generation scavenging