Comprehensive exam: 7 May 2008, 1:00 PM (366 West Village H)
Slides are now available.
Will Clinger wrote the following paragraph to explain the choice of committee:
Felix's thesis concerns the design and implementation of a generational garbage collector with provable worst-case bounds on several important aspects of performance combined with reasonable throughput on typical programs. All members of his committee are comfortable with algorithm design and analysis and with low-level systems implementation, including concurrency on shared-memory multiprocessors. Guy Steele, who was on the program committee for ISMM 2008, understands the industrial state of this art. Gene Cooperman and Olin Shivers understand garbage collection in general and systems implementation.
The thesis proposal: Regional Garbage Collection
The short version:Garbage collectors that occasionally pause to collect the entire heap work well enough for many applications, but that paradigm does not scale up because collection pauses that take time proportional to the total heap size can cause alarming or annoying delays, even if they occur rarely.
Real-time, incremental, and concurrent collectors eliminate such delays but introduce complex invariants to the memory management system. Maintenance of these invariants during execution reduces application throughput. Also, supporting these invariants increases the complexity of compilers, run-time infrastructure, and low-level libraries (e.g. client modules written in C and linked via a foreign function interface).
In non-real-time operating environments, real-time garbage collection is overkill. It would be better to preserve the throughput of generational collectors while eliminating the long delays associated with major collections. Implementors would also appreciate a system with hard bounds on pause times, but simpler than contemporary real-time memory managers.
Will Clinger (my thesis advisor) and I have designed, and I am implementing, a regional garbage collector that collects bounded subsets of the heap during every collection, thus disentangling the worst-case mutator pause time from the total heap size. The design isolates collection-related work not directly associated with moving objects; a separate processor core can perform such work without direct interaction with the mutator thread.
My thesis is: Our regional garbage collector achieves worst case bounds on mutator pause times and minimum mutator utilization, and if its concurrent tasks are run with sufficiently high priority, it provides competitive throughput while maintaining a worst case bound on overall memory usage.
Content last updated: 11 May 2008 (Presentation last updated: 28 July 2009)