Garbage collector

Z Multimediaexpo.cz

Garbage collector (GC) je obvykle část běhového prostředí (programovacího) jazyka, nebo přídavná knihovna, podporovaná kompilátorem, hardware, operačním systémem, nebo jakoukoli kombinací těchto tří. Má za úkol automaticky určit, která část paměti programu je už nepoužívaná, a připravit ji pro další znovupoužití.

Obsah

Vznik garbage collecting

Garbage collecting je označení pro metodu automatické správy paměti programu. Garbage collecting vymyslel roku 1959 John McCarthy pro řešení problému manuální správy paměti v Lispu. Je nejčastěji popisována opakem manuální správy paměti, která vyžaduje specifikovat program tak, aby bylo zřejmé, které objekty se mohou uvolnit a které se mají vrátit zpět do paměti.

Místa v paměti, které již programátor nepoužije se nazývají memory leaks a GC tyto místa hledá a odstraňuje je. Dalším problémem je tzv. „dangling pointer“. Je to vlastně ukazatel na prázdnou paměť, nebo paměť jež byla znova alokována jinde v programu a přepsána jinými daty.

Tyto chyby jsou jen těžko odhalitelné a špatná podmínka větinou způsobí nesprávné chování programu. Takže vyvarování se chyb způsobených správou paměti na haldě bylo jistě jedním z důvodů vzniku automatické správy.

Základní princip garbage collecting

  1. Vyhledají se v programu takové datové objekty, které nebudou v budoucnu použity
  2. Vrácení zdrojů, kde se vyskytovaly nalezené objekty

Uvolňování paměti garbage collecting osvobozuje prográmatora od uvolňování objektů, které již dále nejsou zapotřebí, což ho většinou stojí značné úsilí. Je to vlastně pomůcka pro stabilnější program, protože zabraňuje některým třídám provozních chyb. Například zabraňuje chybám ukazatelů, které ukazují na již nepoužívaný objekt, nebo který je již zrušen a tato paměť se dále k ničemu nevyužívá.

Mnohé jazyky vyžadují garbage collectory už ve specifikaci jazyka (Java, C#), nebo až v praktické realizaci(Garbage collected jazyky). Další jazyky jako C,C++ jsou určeny pro manuální správu paměti, garbage collector je ale možno ručně napsat. Verze garbage collectoru v Delphi pracuje s dynamickými poli, dlouhými řetězci(long string) a rozhraními.

Algoritmus počítání referencí

Vůbec první algoritmus pro garbage collector se jmenoval počítání referencí (reference counting). Funguje následovně: Ke každému objektu je přiřazen čítač referencí. Když je objekt vytvořen, jeho čítači je nastavena hodnota 1. V okamžiku, kdy si nějaký jiný objekt nebo kořen programu (kořeny jsou hledány v programových registrech, v lokálních proměnných uložených v zásobnících jednotlivých vláken a ve statických proměnných) uloží referenci na tento objekt, hodnota čítače je zvětšena o 1. Ve chvíli, kdy je reference mimo rozsah platnosti (např. po opuštění funkce, která si referenci uložila), nebo když je referenci přiřazena nová hodnota, čítač je snížen o 1. Jestliže je hodnota čítače některého objektu nulová, může být tento objekt uvolněn z paměti. Když je uvolňován z paměti, všem objektům, na něž má objekt referenci, se sníží hodnota o 1 - tedy uvolnění jednoho objektu může vést k uvolnění dalších objektů. Nevýhoda této metody spočívá ve faktu, že neumí detekovat cykly. Cyklus nastává v okamžiku, kdy dva a více objektů ukazují samy na sebe, například když rodičovská třída ukazuje na svého potomka a ten má referenci zpátky na rodiče. Tyto dva objekty nebudou mít nikdy čítač roven nule, ačkoli jsou nedosažitelné z kořene programu. Další nevýhoda spočívá v režii, která je nutná pro zvyšování a snižování čítačů u každého objektu. Kvůli těmto nedostatkům se reference counting v dnešní době nepoužívá jako univerzální garbage collector.

Sledovací (tracing) algoritmy

Sledovací algoritmy tzv. zastaví svět (v tomto smyslu tedy běh programu) a začnou vyhledávat objekty. Začínají v kořenové množině programu a pokračují po referencích, dokud neprozkoumají všechny dosažitelné objekty. Algoritmy, založené na tomto principu, se používají téměř výlučně pro implementaci garbage collectorů v dnešních programovacích jazycích. Jako první byla tato metoda použita v jazyce Lisp v roce 1960, kde ji využíval algoritmus nazvaný Mark & Sweep.

Mark & Sweep

Algoritmus nejdříve nastaví všem objektům, které jsou v paměti, speciální příznak navštíven na hodnotu ne. Poté projde všechny objekty, ke kterým se lze dostat. Těm, které takto navštívil, nastaví příznak na hodnotu ano. V okamžiku, kdy se už nemůže dostat k žádnému dalšímu objektu, znamená to, že všechny objekty s příznakem navštíven majícím hodnotu ne jsou odpad - a mohou být tedy uvolněny z paměti.

Tato metoda má několik nevýhod. Největší je, že při garbage collectionu je přerušen běh programu. To znamená,že se programy pravidelně zmrazí, takže je nemožné pracovat s aplikacemi používající reálný čas.

Kopírovací (copying) collector

Tento algoritmus nejprve rozdělí prostor na haldě na dvě části, kdy jedna je aktivní a s druhou se nepracuje. Vždy můžeme alokovat objekty v celkové velikosti, která je poloviční velikost haldy. Pokud se při alokaci nevejdeme do místa na části haldy, je potřeba provést úklid. Ten spočívá v prohození aktivní a neaktivní části. Do nově aktivní části se překopírují živé objekty ze staré, již neaktivní, části. Mrtvé objekty nekopírujeme, ale při dalším prohození aktvní a neaktivn části je jednoduše přepíšeme.

Kopírovací algoritmus probíhá zdlouhavě, protože se objekty musí přesouvat z částí haldy. Kvůli náročnosti celého přesunu tedy mohou být prodlevy ještě znatelnější než při použití mark & sweep. Výhodou je, že nenastává fragmentace jako u mark & sweep. Objekty jsou totiž udržovány na spodku právě používaného prostoru, proto stačí k jejich adresovaní mnohem menší rozptyl adres.

Generační algoritmus

Při použití garbage collectorů se dají empiricky vypozorovat dva důležité fakty. Tím prvním je, že mnoho objektů se stane odpadem krátce po svém vzniku. Tím druhým je skutečnost, že jen malé procento referencí ve „starších“ objektech ukazuje na objekty mladší.

U tracing collectoru, kde se využívá celá halda, musel collector při každé čistce procházet mezi objekty a všechny živé objekty buďto překopírovat do jiné části haldy, nebo je označit a dále projít celou haldu a uvolnit mrtvé. A právě z důvodu brzkého úmrtí většiny objektů je tato metoda velice neefektivní.

Generační garbage collector využívá těchto skutečností a rozděluje si paměť programu do několika částí, tzv. generací. Objekty jsou vytvářeny ve spodní (nejmladší) generaci a po splnění určité podmínky, obvykle stáří, jsou přeřazeny do starší generace. Pro každou generaci může být úklid prováděn v rozdílných časových intervalech (obvykle nejkratší intervaly budou pro nejmladší generaci) a dokonce pro rozdílné generace mohou být použity rozdílné algoritmy úklidu. V okamžiku, kdy se prostor pro spodní generaci zaplní, všechny dosažitelné objekty v nejmladší generaci jsou zkopírovány do starší generace. I tak bude množství kopírovaných objektů pouze zlomkem z celkového množství mladších objektů, jelikož většina z nich se již stala odpadem.

Použití v dnešních jazycích

Zřejmě nejznámějším jazykem, který používá garbage collector je jazyk Java - ten v dnešní době (JDK 1.5) používá rovnou čtyři druhy garbage collectorů, přičemž všechny jsou generační. Další známou platformou je .NET, který používá obdobu algoritmu Mark & Sweep.

Lze říci, že u vyšších jazyků je garbage collector napsán jako standardní funkce. Pro jazyky C a C++ se používá knihovna Boehm garbage collector, která využívá metodu mark & sweep pro stanovení živosti a uvolnění objektů.

Funkcionální programovací jazyky jako ML, Haskell a APL, mají automatické spravování paměti s garbage collection, v kontrastu se staršími programovacími jazyky jako je C a Pascal, které používají explicitní spravování paměti. Funkcionální programovací jazyky jsou náročnější na systémové prostředky.

Ostatní dynamické jazyky jako Ruby (kromě Perlu a PHP) také používají garbage collection. Objektově orientované programovací jazyky mezi něž patří Java, Smalltalk či ECMAScript mají integrované garbage collectory.

Nevýhody garbage collectingu

  • Garbage collector potřebuje ke své práci procesorový čas, aby mohl rozhodovat o tom, jestli je objekt v paměti mrtvý, nebo živý. O stavu objektů musí mít collector uloženou nějakou informaci. Tyto informace jsou další data, která ale nejsou nezbytná pro běh programu.
  • Některé garbage collectory mohou způsobit i dosti znatelné pauzy, což se jeví jako problém pro tzv. real-time systémy

Externí odkazy

Citováno z „http://www.multimediaexpo.cz/mmecz/index.php/Garbage_collector“