teaching machines

CS 330 Lecture 29 – Garbage Collection

April 16, 2012 by Chris Johnson. Filed under cs330, lectures, spring 2012.

Agenda

• how does polymorphism work?
• Jim Blinn’s terrible approach
• the elegant vtable approach
• garbage collection
• programmers don’t get explicit reclamation right
• OS does reclaim memory when program stops
• what happens when…
• … we don’t call free?
• … we call free twice?
• … we call free once but leave pointer untouched?
• some approaches:
• mark-and-sweep
• stop-and-copy
• reference counting
• a C++ counter pointer
• pair pointer with reference count
• maintain count on copy, assignment, destruction
• when count goes to 0, free it

TODO

• A brief introduction to Java’s former garbage collectors: http://www.ibm.com/developerworks/library/j-jtp10283/.
• Apple’s description of memory management: http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/MemoryMgmt.html.
• Weak references: http://weblogs.java.net/blog/2006/05/04/understanding-weak-references.
• Apple’s recommendations on circular referencing: http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmPractical.html#//apple_ref/doc/uid/TP40004447-1000810.

Mark-and-sweep

for each allocated block:
  mark unvisited

for each pointer on stack:
  mark block pointed to visited
  recurse on any pointers in block

for each allocated block:
  free if block unvisited

Code

…

Haiku