摘要 |
A garbage collector treats a dynamically allocated heap as divided into a young generation and an old generation, to which it applies different collection policies. To keep track of where a mutator has made reference modifications in the old generation between collection intervals, the collector divides the old generation into "cards" and maintains a "card table" that contains an entry for each card. Initially, each entry's value is clean, and, when the collector scans the old generation for references to young-generation objects, it skips cards whose entries are clean. When the mutator modifies a reference in a card, it gives the card's card-table entry a dirty value. If a thread scanning a card during a given collection interval finds that no references to young-generation objects that remain in the young generation through the end of that collection interval, it sets the card's card-table entry to a clean value. On the other hand, if the collector finds that the card contains such a reference, it gives the entry a youngergen value selected from a plurality of youngergen values at the beginning of the interval as the "current" youngergen value. When a thread finds a referred-to object in the young generation, it sometimes "promotes" the object to a card in the old generation, arranges for any references it contains to be processed, and sometimes sets the card's entry to the current youngergen value. The collector executes the card-table processing in a plurality of threads, and the youngergen value chosen for a given collection interval differs from the one that was chosen for the previous collection interval. As a result, a thread is able to distinguish between a card in which a reference to the younger generation remained at the end of the previous interval and one identified by some other thread during the current interval as referring to a young-generation object. In that way, the thread is able to avoid unnecessary scanning.
|