Szemétgyűjtés

A számítógép-programozásban a szemétgyűjtés (angolul garbage collection) egy formája a biztonságos memóriakezelésnek. A szemétgyűjtő (angolul garbage collector vagy röviden GC) megkísérli eltávolítani a memóriából azokat az objektumokat, amelyeket az alkalmazás már nem használ. A szemétgyűjtés feltalálása John McCarthy nevéhez fűződik,Lisp és a GC aki a Lisp programozási nyelv egyik megalkotója. Gyakran állítják szembe a hagyományos, manuális memóriakezeléssel, ahol a programozó szabja meg az egyes objektumok élettartamát. A gyakorlat azt mutatja, hogy mindkét megoldásnak megvannak az előnyei és hátrányai (illetve léteznek más módszerek is, pl.: region inferenceRegion Inference).

Alapok A szemétgyűjtés alapelve: Meghatározni mely objektumok nincsenek már használatban Felszabadítani az általuk elfoglalt memóriát Azáltal, hogy a fejlesztőknek nem kell törődniük a memória helyes kezelésével, több időt fordíthatnak az alkalmazásfejlesztésre, és a futásidejű hibák száma is csökken, így stabilabb lesz a program. Elkerülhetőek azok a hibák, amelyek az esetlegesen rosszul kezelt memóriából adódnak (felszabadított objektumra való hivatkozás, lefoglalatlan memóriára való hivatkozás, stb.). Napjainkban sok programnyelvnek része a szemétgyűjtő (C#, Java, scriptnyelvek), és vannak programnyelvek, amelyeket manuális memóriakezelésre terveztek, de van GC-t alkalmazó implementációjuk (pl.: C, C++). Néhány nyelv - mint a Modula-3 - lehetővé teszi a kettő egyidejű alkalmazását (más-más halmot (heap) használva).

Előnyök

Megszabadítja a programozót a memóriamenedzseléstől, így kiküszöböl néhány gyakori hibát: Dangling ("lógó") pointer-ek: a mutatott memóriahely már felszabadult, de még van rá hivatkozás Többszörös felszabadítás: a már felszabadított memóriát ismét felszabadítja a program Memóriaszivárgás (memory leak): a már nem használt memória lefoglalva marad, anélkül, hogy felszabadulna Utóbbinál megkülönböztetünk fizikai és logikai memóriaszivárgást. Fizikainak nevezzük, ha a lefoglalt memória törlésre került, de nem szabadult fel. Logikai szivárgásról beszélünk, ha a területre van élő hivatkozás, de azt nem használjuk. Ebben az esetben a GC sem tehet semmit.

Hátrányok Lassú, folyamatosan figyelni kell az objektumokat, ez számításigényes feladat. Nem determinisztikus. Minden objektum törlődni fog, de nem tudni mikor.

Nyomkövetés alapú szemétgyűjtés A legelterjedtebb szemétgyűjtő módszer. Először meghatározza, mely objektumok elérhetőek, majd törli a megmaradtakat.

Egy objektum elérhetősége Egy elérhető objektumot úgy definiálhatunk, mint egy program futása közben létrejött változót, amelyet elérhetünk közvetlenül, vagy egy másik objektumon keresztül. Ezen a módon kétféle objektumot különböztetünk meg: Objektumok, amelyekről feltételezhetjük, hogy elérhetőek. Tipikusan azok az elemek tartoznak ide, amelyekre a call stack hivatkozik (azaz minden lokális változó és paraméter egy függvényben), illetve minden globális változó. Minden olyan objektum, amelyre egy másik, szintén elérhető objektum hivatkozik (formálisan az elérhetőség egy tranzitív lezárt). Ez a megközelítés nem optimális, mivel azután, hogy egy objektumra nincs többé szükség, még sok idő telhet el, mire kikerül az adott hatókörből.

Különbséget teszünk szintaktikai szemét (amikor a program nem fér hozzá az objektumhoz) és szemantikai szemét (azok, amiket többé nem használ a program) között:

var x = new Thing(); var y = new OtherThing(); x = new SomeThing(); //Thing() soha nem lesz hozzáférhető -> szintaktikai szemét

if(x.CheckSomething()) { x.DoSomething(y); }

return; //y szemantikai szemét lehet az x.CheckSomething() eredményétől függően

Könnyen bizonyítható, hogy a szemantikus szemét azonosítása csak részlegesen eldönthető: ha egy program létrehoz egy objektumot, amit tetszőleges program esetén csak annak befejezésekor használ, akkor a szemétgyűjtőnek a megállási problémát kellene megoldania. Bár kutatások folynak heurisztikus módszerek kifejlesztésére, amellyel a szemantikus szemét is kiszűrhető, a gyakorlatban a szemétgyűjtők inkább a szintaktikus szemétre koncentrálnak.

Alapvető algoritmusok A nyomkövetés alapú szemétgyűjtő nevét a munkamódszeréről kapta, mivel folyamatosan figyeli a program által használt memóriát, kutatva a szemét után. A gyűjtő ciklikusan működik, mindig akkor „kapcsol be”, amikor a program erőforrásszűkében van. Az eredetileg használt eljárás egy naiv jelöld meg és söpörd ki (mark-and-sweep) metódus alapján kiválasztja a felesleges elemeket. Ezzel a módszerrel a program futása során többször is végigmegy a felhasznált memórián.

Ebben a metódusban minden egyes objektum kap egy jelzést (flag) (tipikusan egy bit hosszúságú), amelyet csakis a szemétgyűjtő használ. Ez a flag mindig törölt állapotban van, kivéve a gyűjtő ciklusa alatt. A GC először kitakarítja a valószínűleg elérhető elemek (root set – a call stack és a lokális elemek) listáját, és minden használatban lévő objektumot megjelöl. Minden olyan elem, amelyre van hivatkozás a root set-ből szintén jelölést kap. Végül ismét végignézi az összes elemet: ha az objektum flagje alapállapotban van, akkor törlésre kerül, ellenkező esetben visszaáll az eredeti helyzetbe, hogy felkészüljön a következő ciklusra.

Ennek a módszernek rengeteg hátránya van, a legnagyobb, hogy a gyűjtő ciklusa alatt minden más folyamat várakozik, ez pedig az alkalmazás időszakos „lefagyását” okozhatja, lehetetlenné téve a valós idejű és időkritikus folyamatok végrehajtását. A GC legalább kétszer végignézi a memóriát az alkalmazás futása során, ez problémát okozhat a virtuális memóriát használó rendszereken.

A fenti hibák miatt a legtöbb modern nyomkövető szemétgyűjtő a háromszínű jelölés (tri-colour marking) egy változatát implementálja, amely a következőképpen működik:

Létrehozza a kezdeti fehér, szürke és fekete listákat. A fehérek az ún. halálraítélt elemek (condemned set), amelyek azok az objektumok, amiket törölni fog. A feketével jelölt elemekről „olcsón” bebizonyítható, hogy nem hivatkoznak a fehér lista egyetlen objektumára sem. A maradék szürkével jelölt elemek vagy hivatkoznak a fehérekre vagy nem. A következő lépésben kiválaszt egy elemet a szürke listából és feketével jelöli úgy, hogy minden objektumot amire az elem a fehér listában hivatkozik szürkére fest. Addig ismétli az előző műveletet, amíg a szürke lista üres nem lesz. Azok az elemek amelyek végül a fehér listában maradnak törlődnek.

Az algoritmus felállít egy fontos szabályt:

Egyetlen fekete elem sem hivatkozik fehér elemre.

Ez biztosítja, hogy minden fehérrel jelölt elem biztonságosan törölhető, ha a szürke lista kiürül.

A módszernek van egy nagy előnye: az alkalmazás futásával párhuzamosan működik, anélkül, hogy jelentős időre megakasztaná azt. Ahogy az objektumok allokálódnak, egyben jelölést is kapnak, ez pedig elkerülhetővé teszi a komplett memória átvizsgálását a gyűjtés alatt. Azáltal, hogy a szemétgyűjtő folyamatosan tisztában van az objektumok számával, mindig a megfelelő időben kezdheti meg a működését, nem pedig akkor, ha az alkalmazás erőforrásszűkében van.

Implementációs stratégiák A háromszínű algoritmus megvalósításának több alternatívája lehet, amelyek más-más módon befolyásolhatják a hatékony működést.

Mozgatás vagy helybenhagyás Miután meghatározta mely objektumokat kell felszabadítania az algoritmus minden más elemet az eredeti helyén hagy, vagy néhány (esetleg az összes) elemet új memóriaterületre másol, majd szükség szerint aktualizálja a hivatkozásokat.

Első ránézésre a mozgató stratégia "drága" és nem túl hatékony, de vannak jótékony hatásai a szemétgyűjtésre és a program futására egyaránt:

A mozgatás után már nincs szükség további műveletekre, újra felhasználhatóvá válik a felszabadított memória. A helybenhagyó módszernek valamilyen módon meg kell jelölnie az ismét felhasználhatóvá tett területeket. A mozgatás után az új objektumok létrehozása gyorsabb lesz, mivel az elemek egy összefüggő szabad memóriaterületen foglalnak helyet, az új elemek helyét egyszerűen az aktuális memóriára mutató pointer növelésével meghatározhatjuk. A helybenhagyó módszernek először töredezettségmentesítenie kell a területet, megfelelő méretű üres memóriahelyet létrehozva. Az egymásra gyakran hivatkozó objektumok a mozgatás után valószínűleg közelebb kerülnek egymáshoz a memóriában (lehet, hogy ugyanazon a memórialapon helyezkednek el), ami nagymértékben gyorsítja az alkalmazást.

A mozgató stratégia hátránya, hogy az objektumokhoz csak a szemétgyűjtő által létrehozott hivatkozásokon férünk hozzá és nem alkalmazhatóak a pointerműveletek, mert ha az objektumok más helyre kerülnek a rá hivatkozó mutató a semmire mutat. A natív kóddal való kompatibilitás miatt a szemétgyűjtőnek át kell másolnia a memória tartalmát egy a gyűjtő fennhatóságán kívüli területre. Alternatív megoldás lehet, ha az objektumot lerögzítjük (pinning), engedélyezve a natív pointereknek a direkt hozzáférést (és a pointereken végzett műveleteket.)Copying and Pinning

Másolás, mark-and-sweep, mark-and-don't-sweep A szemétgyűjtő módszerek tovább finomíthatók, azt vizsgálva, ahogy a három típus (fehér, szürke, fekete) elemei viselkednek az egyes esetekben.

A legegyszerűbb megoldás a kettős-űr -t (semi-space, two-space vagy stop-and-copy) használó algoritmus.Semi-space A memória két részre oszlik. Kezdetben az objektumok az első részben allokálódnak, majd amikor az megtelik meghívódik a szemétgyűjtő és az elérhető elemeket a másik rekeszbe másolja. Ekkor a szerepek megcserélődnek, a következő alkalommal a második rekeszből az elsőbe helyezi át az objektumokat, és így tovább. A módszer előnye, hogy nagyon egyszerűen működik (a három lista a másolás folyamata alatt jön létre), hátránya pedig, hogy egyszerre csak a memória fele van használatban (bár ez kiküszöbölhető a virtuális memóriát használó környezetekben, a GC gondos megírásával). A C. J. Cheney, R. R. Fenichel és J. C. Yochelson által elkészített algoritmusC. J. Cheney: A Nonrecursive List Compacting Algorithm (1970) ennek a módszernek a tökéletesítése. A mark-and-sweep elven működő gyűjtő egy vagy két bitet tart fenn amellyel jelöli, hogy az adott objektum fehér vagy fekete. A szürke elemek vagy egy különálló listában szerepelnek vagy egy újabb bitet kapnak. Ahogy a hivatkozások fája felépül, úgy kapják meg a megfelelő jelölést az objektumok (ez az ún. megjelölő (marking) ciklus). Végül a törölhető elemek „kisöprődnek” (sweep ciklus). Ennek a stratégiának megvan az az előnye, hogyha a hivatkozás nélküli elemek kiválasztódtak, azután a másoló és helybenhagyó módszereket egyaránt lehet használni, akár futásidőben kiválasztva a memória állapotától függően. Hátránya, hogy az objektumok mérete a hozzáadott bitek miatt megnőhet. A mark-and-don't-sweep stratégia hasonlít a társához, szintén egy plusz bit jelzi, hogy fehér vagy fekete objektumról van szó. A szürke elemek is ugyanúgy elkülönülnek. Két különbség van a két módszer között: Az első az, hogy minden elérhető elem mindig fekete. Amint létrejön a memóriában egy objektum automatikusan fekete jelzést kap, és ez így is marad, még akkor is, ha nincs rá érvényes hivatkozás. A fehér szín a szabad memóriát jelöli. A második, hogy a jelzőbit jelentése megváltozhat. Legyen például 0=fekete és 1=fehér. Ha a memóriafoglalás sikertelen, az azt jelzi, hogy a fehér lista üres, minden elem fekete. Ekkor a jelzőbit értéke invertálódik (1=fekete, 0=fehér). Ekkor minden elem fehér lesz. Most a gyűjtő kiválogatja az elérhető objektumokat (a szürke lista felhasználásával) és ismét feketével jelöli meg őket. Ekkor az érvénytelen objektumok fehérek lesznek és szabadon felhasználható az általuk elfoglalt memória. Nincs szükség a kisöprő fázisra.

Generációs szemétgyűjtő