| dbo:abstract
|
- 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, úgy nevezett 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. (hu)
- 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, úgy nevezett 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. (hu)
|
