Cheneys Algorithmus - Cheney's algorithm

Cheneys Algorithmus , der erstmals 1970 in einem ACM- Papier von CJ Cheney beschrieben wurde, ist eine Stop-and-Copy- Methode zum Verfolgen von Garbage Collection in Computersoftwaresystemen. Bei diesem Schema wird der Heap in zwei gleiche Hälften geteilt, von denen jeweils nur eine verwendet wird. Garbage Collection wird durchgeführt, indem Live-Objekte von einem Semispace (dem From-Space) in den anderen (dem To-Space) kopiert werden, der dann zum neuen Heap wird. Der gesamte alte Haufen wird dann in einem Stück verworfen. Es ist eine Verbesserung gegenüber der vorherigen Stopp- und Kopiertechnik.

Cheneys Algorithmus fordert Elemente wie folgt zurück:

• Objektreferenzen auf dem Stack. Objektreferenzen auf dem Stack werden geprüft. Für jede Objektreferenz, die auf ein Objekt im From-Space zeigt, wird eine der beiden folgenden Aktionen ausgeführt:
  • Wenn das Objekt noch nicht in den To-Space verschoben wurde, erfolgt dies durch Erstellen einer identischen Kopie im To-Space und anschließendes Ersetzen der From-Space-Version durch einen Weiterleitungszeiger auf die To-Space-Kopie. Aktualisieren Sie dann die Objektreferenz, um auf die neue Version in to-space zu verweisen.
  • Wenn das Objekt bereits in den To-Space verschoben wurde, aktualisieren Sie einfach die Referenz vom Weiterleitungszeiger im From-Space.
• Objekte im Zu-Raum. Der Garbage Collector untersucht alle Objektreferenzen in den Objekten, die in den to-space migriert wurden , und führt eine der beiden oben genannten Aktionen für die referenzierten Objekte aus.

Nachdem alle to-Space-Referenzen untersucht und aktualisiert wurden, ist die Garbage Collection abgeschlossen.

Der Algorithmus benötigt keinen Stack und nur zwei Zeiger außerhalb des From-Space und To-Space: einen Zeiger auf den Anfang des freien Speicherplatzes im To-Space und einen Zeiger auf das nächste zu untersuchende Wort im To-Space . Aus diesem Grund wird es manchmal als "Zwei-Finger"-Sammler bezeichnet - es braucht nur "zwei Finger", die in den Raum zeigen, um seinen Zustand zu verfolgen. Die Daten zwischen den beiden Fingern stellen die verbleibende Arbeit dar.

Der Weiterleitungszeiger (manchmal auch als "gebrochenes Herz" bezeichnet) wird nur während des Garbage-Collection-Prozesses verwendet; Wenn eine Referenz auf ein Objekt gefunden wird, das sich bereits im To-Space befindet (also einen Weiterleitungszeiger im From-Space hat), kann die Referenz schnell aktualisiert werden, indem einfach ihr Zeiger aktualisiert wird, damit er mit dem Weiterleitungszeiger übereinstimmt.

Da die Strategie darin besteht, alle Live-Referenzen und dann alle Referenzen in referenzierten Objekten auszuschöpfen, wird dies als ein Garbage-Collection-Schema für die Breiten-zuerst- Listenkopie bezeichnet.

Beispielalgorithmus

initialize() =
    tospace   = N/2
    fromspace = 0
    allocPtr  = fromspace
    scanPtr   = whatever -- only used during collection

allocate(n) =
    If allocPtr + n > fromspace + tospace
        collect()
    EndIf
    If allocPtr + n > fromspace + tospace
        fail “insufficient memory”
    EndIf
    o = allocPtr
    allocPtr = allocPtr + n
    return o

collect() =
    swap(fromspace, tospace)
    allocPtr = tospace
    scanPtr  = tospace

    -- scan every root you've got
    ForEach root in the stack -- or elsewhere
        root = copy(root)
    EndForEach
    
    -- scan objects in the to-space (including objects added by this loop)
    While scanPtr < allocPtr
        ForEach reference r from o (pointed to by scanPtr)
            r = copy(r)
        EndForEach
        scanPtr = scanPtr  + o.size() -- points to the next object in the to-space, if any
    EndWhile

copy(o) =
    If o has no forwarding address
        o' = allocPtr
        allocPtr = allocPtr + size(o)
        copy the contents of o to o'
        forwarding-address(o) = o'
    EndIf
    return forwarding-address(o)

Halbraum

Cheney basierte seine Arbeit auf dem Semispace Garbage Collector, der ein Jahr zuvor von RR Fenichel und JC Yochelson veröffentlicht wurde.

Äquivalenz zur dreifarbigen Abstraktion

Cheneys Algorithmus ist ein Beispiel für einen Garbage Collector mit dreifarbiger Markierung . Das erste Mitglied der grauen Menge ist der Stapel selbst. Objekte, auf die auf dem Stapel verwiesen wird, werden in den to-space kopiert, der Mitglieder der schwarzen und grauen Sätze enthält.

Der Algorithmus verschiebt alle weißen Objekte (äquivalent zu Objekten im From-Space ohne Weiterleitungszeiger) in die graue Menge, indem er sie in den To-Space kopiert. Objekte, die sich zwischen dem Scan-Zeiger und dem Freiraum-Zeiger auf dem Zu-Raum-Bereich befinden, sind Mitglieder des noch zu scannenden Grausatzes. Objekte unterhalb des Abtastzeigers gehören zum Schwarzsatz. Objekte werden in den Schwarzsatz verschoben, indem einfach der Scan-Zeiger darüber bewegt wird.

Wenn der Abtastzeiger den Freiraumzeiger erreicht, ist die Graumenge leer und der Algorithmus endet.

Verweise

• Cheney, CJ (November 1970). „Ein nichtrekursiver Listenkomprimierungsalgorithmus“. Mitteilungen des ACM . 13 (11): 677–678. doi : 10.1145/362790.362798 . S2CID  36538112 .
• Fenichel, RR; Yochelson, Jerome C. (1969). „Ein LISP-Garbage-Collector für Computersysteme mit virtuellem Speicher“. Mitteilungen des ACM . 12 (11): 611-612. doi : 10.1145/363269.363280 . S2CID  36616954 .
• Byers, Rick (2007). "Müllsammelalgorithmen" (PDF) . Garbage Collection-Algorithmen . 12 (11): 3-4.
• Tutorium an der University of Maryland, College Park