A Cheney-algoritmus, amelyet először C. J. Cheney írt le az ACM szaklapjában 1970-ben, a számítógépes rendszerekben a szemétgyűjtés nyomon követésére alkalmazott, úgynevezett stop and copy módszer. Ebben a rendszerben a halom (heap) két egyenlő részre van osztva, amelyek közül egyidejűleg csak az egyik van használatban. A szemétgyűjtés során az objektumok átmásolódnak az egyik féltérből (az ún. from térből) a másikba (az ún. to térbe), amely azután az új halommá válik. A régi halom ezután egy az egyben megsemmisül. Az előző stop and copy technikához viszonyítva ez az algoritmus mindenképpen fejlődést jelentett.
Cheney algoritmusa az alábbiakat követeli meg:
Miután megtörtént az összes to térbeli hivatkozás vizsgálata és frissítése, a szemétgyűjtés befejeződött.
Az algoritmusnak nincs szüksége veremre, csupán két mutatóra a from és a to tereken kívül: egy mutató szükséges a to tér szabad területének elejére, valamint egy másik mutató kell a to térben következő megvizsgálandó parancshoz. Ezért néha „kétujjú” szemétgyűjtőnek hívják - csak „két ujjra” van szüksége, amikkel a to térbe mutatva nyomon tudja követni az állapotát. A „két ujj” közötti adatok mutatják a még hátralévő feladatokat.
Az előre irányuló mutatót (amelyet néha „megtört szívnek” neveznek) csak a szemétszedés folyamata során használjuk; amikor egy a to térben már jelen lévő objektumhoz hivatkozás található (ezáltal rendelkezvén egy előre irányuló mutatóval a from térben), a hivatkozás gyorsan frissíthető, mégpedig úgy, hogy egyszerűen frissítjük a mutatót, úgy, hogy az megegyezzen az előre irányuló mutatóval.
Mivel a stratégia először az összes élő, majd az összes további referencia kihasználása a hivatkozott objektumokban, széltében listamásoló szemétgyűjtő sémának nevezik.
inicializálás() = tospace = N/2 fromspace = 0 allocPtr = fromspace scanPtr = bármi -- csak a gyűjtés során használt
allokál (n) =
Ha allocPtr + n > fromspace+ N/2
gyűjt ()
Ha vége
Ha allocPtr + n > fromspace+ N/2
hiba “nem elegendő memória”
Ha vége
o = allocPtr
allocPtr = allocPtr + n
return o
gyűjt() =
csere(fromspace, tospace)
allocPtr = fromspace
scanPtr = fromspace
-- minden gyökér vizsgálata
ForEach gyökér in verem -- vagy máshol
gyökér = másol(root)
ForEach vége
-- a halomban lévő objektumok vizsgálata (beleértve az ebben a ciklusban hozzáadottakat is)
Amíg scanPtr < allocPtr
ForEach reference r from o (scanPtr által mutatott)
r = másol(r)
ForEach vége
scanPtr = scanPtr + o.size() -- ha van még a halomban objektum, arra mutat
Amíg vége
másol(o) =
Ha o-nak nincs továbbítási címe
o' = allocPtr
allocPtr = allocPtr + méret(o)
másold o tartalmát o'-ba
továbbítási cím(o) = o'
Ha vége
return továbbítási cím(o)
Cheney munkáját az ún. kettős tér szemétgyűjtő elvére alapozta, amelyet egy évvel korábban R. R. Fenichel és J. C. Yochelson publikált.
Cheney algoritmusa tulajdonképpen az ún. háromszínű jelölő szemétgyűjtő példája. A szürke halmaz első tagja maga a verem. Az algoritmus veremben hivatkozott objektumokat a fekete és a szürke halmaz tagjait tartalmazó to térbe másolja.
Az algoritmus bármelyik fehér objektumot (amelyik egyenértékű a from térben lévő előre irányuló mutatóval nem rendelkező objektummal) a szürke halmazba mozgatja, azáltal, hogy a to térbe másolja őket. Azok az objektumok, amelyek a to térben a szkennelési mutató és az üres terület mutatója között vannak, a szürke halmaz szkennelésre váró tagjai. A szkennelési mutató alatti objektumok a fekete halmazhoz tartoznak. Az objektumok úgy kerülnek a fekete halmazba, hogy egyszerűen átmozgatják a szkennelési mutatót felettük.
Amikor a szkennelési mutató odaér a szabad terület mutatójához, a szürke halmaz üres lesz, és az algoritmus véget ér.
Ez a szócikk részben vagy egészben a Cheney's algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.