Cheneys algoritm

Cheneys algoritm , som först beskrevs i en ACM -tidning från 1970 av CJ Cheney, är en stopp- och kopieringsmetod för att spåra sophämtning i datorprogram. I det här schemat högen uppdelad i två lika stora halvor, av vilka endast en används vid en viss tidpunkt. Sophämtning utförs genom att kopiera levande objekt från ett semispace (från-rymden) till det andra (to-space), som sedan blir den nya högen. Hela den gamla högen kasseras sedan i ett stycke. Det är en förbättring jämfört med den tidigare stoppa-och-kopiera-tekniken.

Cheneys algoritm tar tillbaka föremål enligt följande:

• Objektreferenser på stacken. Objektreferenser på stacken kontrolleras. En av de två följande åtgärderna vidtas för varje objektreferens som pekar på ett objekt i från-rymden:
  • Om objektet ännu inte har flyttats till to-space, görs detta genom att skapa en identisk kopia i to-space, och sedan ersätta from-space-versionen med en vidarebefordran till to-space-kopian. Uppdatera sedan objektreferensen för att hänvisa till den nya versionen i to-space.
  • Om objektet redan har flyttats till to-space, uppdatera helt enkelt referensen från vidarebefordranpekaren i from-space.
• Objekt i to-space. Skräpsamlaren undersöker alla objektreferenser i objekten som har migrerats till to-space , och utför en av ovanstående två åtgärder på de refererade objekten.

När alla referenser till rymden har granskats och uppdaterats är sophämtningen klar.

Algoritmen behöver ingen stack och bara två pekare utanför från-utrymmet och till-utrymmet: en pekare till början av ledigt utrymme i till-utrymmet, och en pekare till nästa ord i till-utrymmet som behöver undersökas . Data mellan de två pekarna representerar arbete som återstår för den att utföra (dessa objekt är gråa i trefärgsterminologin, se senare).

Vidarebefordranspekaren (ibland kallad ett "brutet hjärta") används endast under sophämtningsprocessen; när en referens till ett objekt som redan finns i to-space (därmed en vidarekopplingspekare i from-space) hittas, kan referensen uppdateras snabbt genom att helt enkelt uppdatera dess pekare så att den matchar vidarebefordrande pekare.

Eftersom strategin är att uttömma alla livereferenser, och sedan alla referenser i refererade objekt, är detta känt som ett schema för att kopiera skräpinsamlingar med bredd först .

Exempel på algoritm

 initialize() = tospace = N/2 fromspace = 0 allocPtr = fromspace scanPtr = whatever -- används endast under samling 

 allocate(n) = If allocPtr + n > fromspace + tospace collect() EndIf If allocPtr + n > fromspace + tospace misslyckas “otillräckligt minne” EndIf o = allocPtr allocPtr = allocPtr + n return o 

 collect() = swap(fromspace, tospace) allocPtr = fromspace scanPtr = fromspace -- skanna varje rot du har ForEach rot i stacken -- eller någon annanstans rot = copy(root) EndForEach -- skanna objekt i to-utrymmet (inklusive objekt som lagts till av denna loop) Medan scanPtr < allocPtr ForEach referens r från o (pekas på av scanPtr) r = copy(r) EndForEach scanPtr = scanPtr + o .size() -- pekar på nästa objekt i to-utrymmet, om något EndWhile 

 copy(o) = Om o inte har någon vidarebefordranadress o' = allocPtr allocPtr = allocPtr + size(o) kopiera innehållet i o till o ' forwarding-address(o) = o' EndIf returnera forwarding-address(o) 

Semispace

Cheney baserade sitt arbete på semispace garbage collector, som publicerades ett år tidigare av RR Fenichel och JC Yochelson.

Motsvarighet till trefärgad abstraktion

Cheneys algoritm är ett exempel på en sopsamlare med tre färger . Den första medlemmen i det grå setet är själva stacken. Objekt som refereras till i stacken kopieras till to-space, som innehåller medlemmar av de svarta och grå uppsättningarna.

Algoritmen flyttar alla vita objekt (motsvarande objekt i från-utrymmet utan vidarebefordran av pekare) till den grå uppsättningen genom att kopiera dem till till-utrymmet. Objekt som befinner sig mellan skanningspekaren och ledigt utrymmespekaren på to-space-området är medlemmar av den grå uppsättningen som fortfarande ska skannas. Objekt under skanningspekaren tillhör den svarta uppsättningen. Objekt flyttas till den svarta uppsättningen genom att helt enkelt flytta skanningspekaren över dem.

När skanningspekaren når pekaren för ledigt utrymme är den grå uppsättningen tom och algoritmen slutar.

•   Cheney, CJ (november 1970). "En icke-rekursiv listkomprimeringsalgoritm". Kommunikation från ACM . 13 (11): 677–678. doi : 10.1145/362790.362798 . S2CID 36538112 .
•   Fenichel, RR; Yochelson, Jerome C. (1969). "En LISP-sopsamlare för datorsystem med virtuellt minne". Kommunikation från ACM . 12 (11): 611–612. doi : 10.1145/363269.363280 . S2CID 36616954 .
• Byers, Rick (2007). "Algorithms för sophämtning" (PDF) . Algoritmer för sophämtning . 12 (11): 3–4.

externa länkar

• på YouTube - Android använder en variant av semi-space garbage collector.