Garbage collector

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

Vznik garbage collecting[editovat | editovat zdroj]

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.

Garbage collector hledá místa v paměti, která již nemohou být dále používána, a uvolňuje je. Také pomáhá předcházet chybám, které mohou nastat při ruční správě paměti, např. tzv. „dangling pointer“. To je vlastně ukazatel na uvolněnou 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ětšinou 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[editovat | editovat zdroj]

  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 programátora 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á. Zavádějící: když ukazatel ukazuje na objekt, tak ten může být používán, GC ukazatel nezmění a objekt neodstraní a nepřijde na to, že ukazatel tam neměl ukazovat a že to je/byla chyba. 2. pokud se paměť k ničemu nevyužívá, tak je jedno jaká data tam jsou, a nevadí, pokud ta data jsou i platná a využívána. Problém je pokud se paměť znova začne využívat.

Hledání objektů, které nebudou v budoucnu použity, se děje většinou jednoduchým, bezpečným a poměrně rychlým způsobem, ne nějakou sofistikovanou analýzou kódu. Tento způsob zjišťuje, které objekty jsou nedostupné, tj. nevede na ně žádný živý ukazatel.

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. Mnohé jazyky GC ve specifikaci sice nemají, ale protože vy nemáte nekonečnou paměť a ony nemají nástroje pro uvolňování paměti, tak to vyjde nastejno a GC nakonec mají.

Algoritmus počítání referencí[editovat | editovat zdroj]

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, i když 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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.

Jednoduchá implementace Mark&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í (copying) collector[editovat | editovat zdroj]

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. 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ě, že velká část objektů má být 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 také používají garbage collection. Objektově orientované programovací jazyky, mezi něž patří Java, Smalltalk či ECMAScript, mají integrované garbage collectory.

Nevýhody garbage collectingu[editovat | editovat zdroj]

  • 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
  • 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.

Související články[editovat | editovat zdroj]

Memory leak: paměť, která už nebude použita programem, ale není uvolněna, např. protože je odkayována.

Externí odkazy[editovat | editovat zdroj]