Garbage collection

Garbage collector 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í.

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í sami 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 prů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.

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ší.

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 zlomek 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ámně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.

Externí odkazy

• Úvod do problematiky garbage collectorů (anglicky)
• Popis algoritmu Mark & Sweep (anglicky)
• Garbage collector v .NET (anglicky)
• Popis práce garbage collectorů (anglicky)