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, 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 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.)

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. 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 algoritmus (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ő

A tapasztalat azt mutatja, hogy a frissen létrehozott objektumok válnak a leggyorsabban elérhetetlenné (csecsemőhalálozás (infant mortality) vagy generációs hipotézis). Ez a szemétgyűjtő generációkra osztja az objektumokat (az objektumok létrehozása és a hivatkozó elemek alapján) és a ciklusa alatt az egyes generációkat teszi a fehér csoportba. A futtató rendszer „feljegyzéseket” készít az objektumokról, így nem szükséges a hivatkozásfa teljes átnézése. A memória felosztásra kerül az objektumok kora alapján. Amikor az adott memóriarész megtelik, azok az elemek, amelyekre létezik élő hivatkozás az öregebb régiókból, egy generációval feljebb kerülnek. Ez a módszer igen gyors, mivel egyszerre csak egy generációt kell „kitakarítani”.

A generációs gyűjtő heurisztikus alapon működik, ezért előfordulhat, hogy néhány felesleges objektum nem szabadul fel. Ez időnként szükségessé teszi a teljes memória átvizsgálását. A modern keret- vagy futtató rendszerek (mint a Java virtuális gép vagy a .NET Framework) valamilyen hibrid megoldást alkalmaznak, vagyis az alapértelmezett generációk átvizsgálásán felül végrehajtanak egy „mark-and-sweep” ciklust vagy a memória széttöredezettsége miatt egy másoló eljárást – amennyiben szükséges. A végrehajtott eljárások alapján megkülönböztetünk al- (minor) és fő- (major) gyűjtőciklust.

Megszakításos, növekvényes és konkurens modell

Attól függően, hogy a gyűjtő milyen hatással van az éppen futó alkalmazásra, háromféle megoldást különböztetünk meg:

• A megszakításos (stop-the-world) modell, teljes mértékben felfüggeszti a program futását, így garantálva azt, hogy nem jönnek létre új objektumok és nem válnak elérhetetlenné a régiek. Ennek a módszernek a nagy hátránya, hogy a ciklus alatt az alkalmazás nem csinál semmit.
• A növekvényes (incremental) modell párhuzamosan fut az alkalmazással. Ebben az esetben körültekintő tervezés szükséges, hogy a program ne zavarja meg a gyűjtőt és viszont. Például, ha egy új objektumot hozna létre, akkor vagy megvárja amíg a ciklus véget ér, vagy tájékoztatja a GC -t az új egyedről.
• A konkurens (concurrent) modell a párhuzamos rendszerek eszköze. Valós időben párhuzamosan fut az alkalmazással. A program helyességének érdekében összetett lock rendszer szükséges.

Óvatos, illetve pontos szemétgyűjtők

Az olyan programozási nyelveknél, ahol nincs beépített szemétgyűjtő, óvatos (conservative) gyűjtőt alkalmazunk. Ekkor a GC nem ismeri pontosan a memória felépítését és feltételezi minden olyan objektumról, amely pointernek „látszik”, hogy hivatkozás.

A beépített GC-vel rendelkező nyelveknél pontos (precise vagy exact) modellről beszélünk. Ekkor a gyűjtő természetesen ismeri a memória felépítését és felismeri a hivatkozásokat.

Teljesítmény

A nyomkövetés alapú szemétgyűjtő bizonyos overheaddel jár, ami rontja a futásidejű teljesítményt. Az általánosan használt stop-the-world típusú gyűjtő – amely határozatlan időre felfüggeszti a program végrehajtását – alkalmatlanná teszi a szemétgyűjtő használatát a számításigényes és valós idejű feladatok végrehajtásánál.

Sokkal nagyobb probléma, hogy a szemétgyűjtők elmozdíthatják az objektumokat az eredeti helyükről, így az összefüggő adatokat lassabban érheti el a program. A modern számítástechnika nagyban támaszkodik a gyorsítótárakra (caching), amelyek hatékony működése a kapcsolódó adatok elrendezésén alapszik. Vannak gyűjtők, amelyek jobban tudnak együttműködni a gyorsítótárral, mint mások (pl. a generációs és másoló módszereken alapuló gyűjtők). Egy rosszkor indított gyűjtőciklus jelentősen ronthatja a teljesítményt, ezért sok rendszer biztosít eszközöket a ciklusok késleltetésére, megállítására és szándékos elindítására is.

A gyakori memóriafoglalást/felszabadítást igénylő alkalmazások esetében a szemétgyűjtés és a manuális allokáció nagyjából egyforma hatásfokkal dolgozik. Többletterhelést jelent a manuális foglalóknál a szabad területeket nyilvántartó lista karbantartása és a best fit/first fit keresések, a gyűjtőnél pedig az elérhető objektumok felderítése, az elérhető objektumok másolása (mozgató gyűjtőnél) és a first fit/best fit keresések a nem mozgatóknál.

Referenciaszámlálás

A referenciaszámlálás az automatikus memóriakezelés egy formája. Minden objektum rendelkezik egy hozzáadott mezővel, amelynek értéke megadja az elemre való hivatkozások számát. Ez az érték eggyel növekszik egy új hivatkozás születésekor és eggyel csökken, ha a hivatkozás megszűnik. Ha eléri a nullát, az objektum által elfoglalt memória felszabadul.

Ennek a módszernek két nagy hibája van:

• Ha két vagy több elem egymásra hivatkozik, akkor kör keletkezhet, ezért sohasem kerülnek felszabadításra. Egyes referenciaszámlálás alapú szemétgyűjtők – mint a CPythonban implementált – rendelkezik ezt a hibát kivédeni szándékozott körfigyelő algoritmusokkal.
• A hivatkozások élettartama elején és végén szükség van a számlálók módosítására, s bár ennek kioptimalizálására vannak jól használható módszerek, többszálas környezetben ez lockokat igényelhet, amelyek költsége igen nagy is lehet.

Elérhetőség

A magas szintű programozási nyelvek egyre inkább alapértelmezés szerint támogatják a szemétgyűjtő használatát. A standard gyűjtővel nem rendelkező nyelvekhez gyakran elérhetőek a GC-t támogató környezetek, az azt megvalósító könyvtárak.

A funkcionális programozási nyelvek, mint az ML, a Haskell vagy az APL beépített gyűjtővel rendelkeznek. A funkcionális programozást bevezető Lisp elsőként használt szemétgyűjtőt.

A dinamikus nyelvek mint a Ruby szintén rendelkeznek szemétgyűjtővel (kivételt képeznek ez alól a PHP és Perl nyelvek, amelyek referenciaszámlálást használnak). Az objektumorientált nyelvek – Smalltalk, Java, ECMAScript – szintén használják (nevezetes kivétel a C++).

A korai, kezdőknek szánt programozási nyelvek – például BASIC és Logo – is használták ezt a technikát, levéve a programozással csak ismerkedők válláról a memóriamenedzsment terhét. A korai, lassú és kis központi memóriával rendelkező gépeken a szemétgyűjtés gyakran okozott véletlenszerű, megmagyarázhatatlan szüneteket a program végrehajtásában.

Korlátozott környezetek

A szemétgyűjtés ritkán alkalmazott beágyazott vagy valós idejű rendszerek esetében, mivel limitált lehetőségeket nyújt a szűkös erőforrások kezelésére. Mindazonáltal a Microsoft .NET Micro Framework és a Java Platform, Micro Edition ezekre a platformokon is elérhető, és nagyobb testvéreikhez hasonlóan támogatják a szemétgyűjtést.

További információk

• Memory menedzsment referencia
• Egy szemétgyűjtő a C/C++ nyelvekhez
• Richard Jones tanulmánya