Garbage Collection Without Paging
Brief Intro
Collecting the heap may induce paging, and garbage collection also disrupts information about the reference history tracked by the virual memory manager.
This paper introduces bookmarking colledction (BC), a garbage collection algorithm that virtually eliminates garbage collector-induced paging. It records summary information ("bookmarks") about outgoing pointers from pages that have been evicted to disk. Once a page is evicted from memory, BC does not touch it unless the application itself makes it resident. Bookmarking necessarily sacrifices some connectivity information and could thus prevent garbage from being reclaimed.
The bookmarking collector relies on some additional operating systems support, which consists of a modest extension to the Linux virtual memory manager.
Overview
Three design goals:
low space consumption: by mark-sweep collection
high throughput: by using a nursery generation to manage short-lived obejcts
the elimination of GC-induced page faults: organizes the heap into groups of pages and reacts to signals from the virtual memory manager whenever pages are scheduled for eviction to disk or made resident in main memory
BC avoid paing caused by processing objects on evicted pages. It scans pages prior to eviction and remenbers outgoing pointers by bookmarking targetd objects.
When BC is notified of an impending eviction and cannot shrink the heap or discard an empty page, BC ensures that only appropriate pages are evicted. BC scans each object on the victim page, bookmarks the targets of any references, and increments counters in the target superpages' headers. After processing all of the objects, BC informs the virtual memory manager that the page can be evicted.
Q: Bookmarked means the object is referenced by another object from other pages?
Bookmarking Collection
The bookmarking collector is a generational collector with a bump pointer nursery, a compacting mature space, and a page-based large object space. BC divides the mature space into superpages, page-aligned groups of four contiguous pages (16K). BC manages mature objects using segregated size classes: objects of different sizes are allocated onto different superpages. Completed empty superpages can be reassigned to any size class. This size classes are designed to minimize both internal and external fragmentation.
Q: Is this segregated size idea similar to Memento?
BC performs mark-sweep garbage collection when the heap fills, for two reasons:
it provides good program throughput and short GC pauses
mark-sweep does not increase memory pressure by needing a copy reserve of pages
Remembered Sets
BC must remember pointers from the older to the younger generation. It normally stores these pointers in page-sized write buffers.
BC marks the card for the source object in the card table used during the marking phase of garbage collection. It begins each nursery collection by reviewing these cards and scanning only those objects whose cards are makred.
Compacting Collection
BC performs a two-pass compacting collection whenever a full garbage collection does not free enough pages to satisfy the current allocation request.
The first pass:
Every time it marks an object, it also increments a counter for the object's size class.
TODO
The second pass: TODO
Cooperation with the Virtual Memory Manager
Insights
Links
TO BE ADDED.
Last updated