Garbage collection

Garbage collection (zkratka GC, v původním významu „odvoz odpadu“) je způsob automatické správy paměti. Funguje tak, že speciální algoritmus (garbage collector) vyhledává a uvolňuje úseky paměti, které již program nebo proces nepoužívá. Za autora garbage collection metody je považován John McCarthy, jenž metodu vyvinul kolem r. 1960 pro řešení problémů v Lispu.

Garbage collection šetří čas při vývoji. Automatická správa paměti osvobozuje programátora od uvolňování objektů, které již dále nejsou zapotřebí, což ho většinou stojí nezanedbatelné úsilí. Garbage collection také pomáhá předcházet některým typům běhových chyb, které se často vyskytují při ruční správě paměti (dangling pointer, memory leak).

Hledání objektů, které nebudou v budoucnu použity, se většinou provádí jednoduchým a poměrně rychlým způsobem, ne nějakou sofistikovanou analýzou kódu. Zjišťuje se, které objekty jsou z kořene programu nedostupné, tj. nevede na ně žádný živý ukazatel (odkaz, reference).

Algoritmus počítání referencí

Vůbec první^[zdroj?] algoritmus pro garbage collection je znám jako „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 odkazuje na svého potomka a ten odkazuje zpátky na rodiče. Tyto dva objekty nebudou mít nikdy čítač roven nule, i když jsou z kořene programu nedosažitelné. 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 počítání referencí v dnešní době jako univerzální garbage collector nepoužívá.

Sledovací algoritmy

Sledovací (tracing) algoritmy tzv. „zastaví svět“ (v tomto smyslu tedy běh programu) a začnou vyhledávat objekty. Začínají v kořenu programu a pokračují po referencích, dokud neprozkoumají všechny dosažitelné objekty.

Algoritmy, založené na tomto principu, se používají pro implementaci garbage collectorů v dnešních programovacích jazycích téměř výlučně. Jako první byla tato metoda použita v jazyce Lisp v roce 1960, kde ji využíval algoritmus nazvaný mark and sweep.

Algoritmus mark and sweep

Algoritmus mark and sweep 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 během garbage collection je pozastaven běh programu. To znamená, že se programy pravidelně „zmrazí“; tato metoda se tedy nehodí pro aplikace běžící v reálném čase.

Jednoduchá implementace mark and sweep, která nechává živé objekty na místě, trpí fragmentací uvolněné paměti. Proto je součástí této implementace GC obvykle defragmentování paměti.

Kopírovací algoritmus

Kopírovací 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 se nekopírují. Při dalším prohození aktivní a neaktivní části jsou zastaralá data jednoduše přepsána.

Nevýhodou tohoto algoritmu je jeho velká paměťová náročnost (potřebuje dvojnásobný prostor pro objekty). Další nevýhodou je potřeba kopírovat objekty, které přežijí úklid. Oproti tomu algoritmus nemá vůbec žádnou práci s objekty, které úklid nepřežijí. Vhodný je tedy v případě, kdy má být velká část objektů smazána, což se u nově vzniklých objektů často stává. Při běhu algoritmu je při kopírování objektů do druhé části haldy paměť automaticky defragmentována.

V praxi bývá tento algoritmus používán pro nově vzniklé objekty a je kombinován s dalšími algoritmy, což eliminuje jeho nevýhody.

Generační algoritmus

Při použití garbage collection 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 (nejkratší intervaly obvykle budou platit 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

Garbage collector se obvykle implementuje jako část běhového prostředí (programovacího) jazyka, nebo jako přídavná knihovna, podporovaná překladačem, hardwarem, operačním systémem nebo jejich kombinací.

Zřejmě nejznámějším jazykem, který používá garbage collection, je jazyk Java – ten ve verzi JDK 1.5 používá hned č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 and 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 and sweep pro stanovení živosti a uvolnění objektů.

Starší programovací jazyky, jako C a Pascal, používají explicitní spravování paměti. Funkcionální programovací jazyky jako ML, Haskell a APL mají automatickou správu paměti s garbage collection. Dynamicky typované jazyky jako Ruby také používají garbage collection. Objektově orientované programovací jazyky, mezi něž patří Java, Smalltalk či ECMAScript, mají integrované garbage collectory.

Nevýhody garbage collection

Garbage collector potřebuje ke své práci procesorový čas, aby mohl rozhodovat o tom, jestli je objekt v paměti „mrtvý“, nebo „živý“.
Některé garbage collectory mohou způsobit i dosti znatelné pauzy, což je vážný problém pro systémy běžící v reálném čase.
O stavu objektů musí mít garbage collector uloženou informaci. Tyto informace vyžadují určitou paměť navíc.
Některé jazyky s garbage collectorem neumožňují programátorovi znovupoužití paměti, i když ví, že paměť už nebude použita. To vede k nárůstu alokace paměti.

Externí odkazy

Obrázky, zvuky či videa k tématu Garbage collector na Wikimedia Commons
Miniseriál o garbage collectorech (česky)
Garbage collector v .NET (anglicky)
Visualizing Garbage Collection Algorithms (anglicky)