Cheney-algoritmus

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:

• Objektumhivatkozások a veremben. Ellenőrizzük a veremben található objektumhivatkozásokat. A következő két művelet egyikét kell elvégezni minden olyan objektumreferencia esetén, amely egy a from térben lévő objektumra mutat:
  • Ha az objektumot még nem helyezték át a to térbe, akkor ezt úgy kell megtenni, hogy egy vele megegyező másolatot kell készíteni a to térben, majd a from térből érkező verziót lecserélni egy előre irányuló mutatóra a to térben lévő másolatra. Ezután frissíteni kell az objektumhivatkozást, hogy az az új verzióra hivatkozzon a to térben.
  • Ha az objektumot már áthelyezték a to térbe, egyszerűen frissíteni kell a from térben lévő előre irányuló mutató hivatkozását.
• Objektumok a to térben. A szemétgyűjtő megvizsgálja az összes objektumhivatkozást a to térbe áttelepített objektumokban, és elvégzi a fenti két művelet egyikét a hivatkozott objektumokon.

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.

Példaalgoritmus

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)

Kettős tér

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.

A háromszínű absztrakcióval való egyenértékűség

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.

Irodalom

• Cheney (1970. november 1.). „A Nonrecursive List Compacting Algorithm”. Communications of the ACM 13 (11), 677–678. o. DOI:10.1145/362790.362798. 
• Fenichel (1969). „A LISP garbage-collector for virtual-memory computer systems”. Communications of the ACM 12 (11), 611–612. o. DOI:10.1145/363269.363280. 
• Byers (2007). „Garbage Collection Algorithms”. Garbage Collection Algorithms 12 (11), 3–4. o. 
• Oktatóanyag, Maryland Egyetem, College Park

Fordítás

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.