Garbage collection (zkratkaGC, 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ánJohn McCarthy, jenž metodu vyvinul kolem r. 1960 pro řešení problémů vLispu.
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).
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 nebokoř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í (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íchprogramovacích jazycích téměř výlučně. Jako první byla tato metoda použita v jazyceLisp v roce 1960, kde ji využíval algoritmus nazvanýmark and sweep.
Algoritmusmark 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í proaplikace 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 obvykledefragmentování paměti.
Kopírovací algoritmus nejprve rozdělí prostor nahaldě 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.
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.
Garbage collector se obvykle implementuje jako částbě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 jazykJava – ten ve verziJDK 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 jazykyC aC++ se používá knihovnaBoehm garbage collector, která využívá metodu mark and sweep pro stanovení živosti a uvolnění objektů.
Starší programovací jazyky, jakoC aPascal, používají explicitní spravování paměti.Funkcionální programovací jazyky jakoML,Haskell aAPL mají automatickou správu paměti s garbage collection.Dynamicky typované jazyky jakoRuby také používají garbage collection.Objektově orientované programovací jazyky, mezi něž patříJava,Smalltalk čiECMAScript, mají integrované garbage collectory.
Obrázky, zvuky či videa k tématuGarbage collector na Wikimedia Commons
