Concurrent Garbage Collection in O_2

We describe a concurrent garbage collector (GC) for object-oriented databases. Our GC uses a new synchronization mechanism (mechanism that allows the GC to operate concurrently with ordinary users of the database), called GC-consistent cuts. A GC-consistent cut is a set of virtual copies of database pages. The copies are taken at times such that an object may appear as garbage in the cut only if it is garbage in the system. Our GC examines the copies, instead of the real database, in order to determine which objects are garbage. GC-consistent cuts are easy to implement by already-existing code that implements consistent read-only transactions. Our GC scales up. Unlike other scalable GCs, it does not require the user to explicitely partition the database into looselyconnected subsets, and does not introduce code that must run all the time, hereby avoiding to slow down the system while the GC is not running. 1 Introduction Automatic garbage collection is widely recognized as a fundam..