Sběr odpadků (počítačová věda) - Garbage collection (computer science)

Tento článek je o uvolňování paměti ve správě paměti. Sběr odpadků na jednotce SSD najdete v tématu uvolňování paměti (SSD) .
Pro jiná použití, viz Garbage collection (disambiguation) .
Ukládání a kopírování odpadků v architektuře Lisp : Paměť je rozdělena na pracovní a volnou paměť; nové objekty jsou přiděleny v prvním. Když je plný (zobrazeno), provede se sběr odpadu: Všechny datové struktury, které se stále používají, jsou lokalizovány pomocí sledování ukazatelů a zkopírovány do po sobě jdoucích míst ve volné paměti.
Poté se obsah pracovní paměti vyřadí ve prospěch komprimované kopie a vymění se role pracovní a volné paměti (znázorněno).

V informatice je garbage collection ( GC ) forma automatické správy paměti . Na garbage collector pokusy paměti recyklovaného prášku, který byl přidělen v rámci programu, ale již není odkazuje, nazývaný také odpadky . Sběr odpadků vynalezl americký počítačový vědec John McCarthy kolem roku 1959, aby zjednodušil ruční správu paměti v Lispu .

Odvoz odpadu zbavuje programátora od provedení manuální správu paměti , kde programátor určuje, jaké objekty navrátit a vrátit se do paměti systému, a když k tomu. Mezi další podobné techniky patří alokace zásobníku , odvození oblasti , vlastnictví paměti a kombinace více technik. Sběr odpadků může trvat značnou část celkového času zpracování v programu a v důsledku toho může mít významný vliv na výkon .

Prostředky jiné než paměti, jako jsou síťové sokety , databázové uchy , interakce s uživatelem oken , souborů a popisovačů zařízení, které nejsou obvykle řeší sběr odpadků. Metody pro správu takových prostředků, zejména destruktorů , mohou také stačit ke správě paměti, takže není potřeba GC. Některé systémy GC umožňují, aby takové další prostředky byly přidruženy k oblasti paměti, která při jejich shromažďování způsobí práci při regeneraci těchto prostředků.

Zásady

Základními principy shromažďování odpadků je najít datové objekty v programu, ke kterému v budoucnu nelze přistupovat, a znovu získat prostředky používané těmito objekty.

Mnoho programovacích jazyků vyžaduje sběr odpadků, buď jako součást jazykové specifikace (například Java , C# , D , Go a většina skriptovacích jazyků ), nebo efektivně pro praktickou implementaci (například formální jazyky jako lambda kalkul ); Tyto jsou prý odpadky shromažďují jazyky . Jiné jazyky byly navrženy pro použití s ​​manuální správou paměti, ale mají k dispozici implementace sbírané odpadky (například C a C ++ ). Některé jazyky, jako Ada , Modula-3 a C ++/CLI , umožňují souběžné shromažďování odpadků a ruční správu paměti ve stejné aplikaci pomocí samostatných hromad pro shromažďované a ručně spravované objekty; ostatní, jako D , se shromažďují odpadky, ale umožňují uživateli ručně odstraňovat objekty a také zcela deaktivovat sběr odpadků, když je vyžadována rychlost.

Zatímco integrace sbírání odpadků do kompilátoru jazyka a runtime systému umožňuje mnohem širší výběr metod, existují post-hoc systémy GC, jako je například automatické počítání referencí (ARC), včetně těch, které nevyžadují rekompilaci. ( Post-hoc GC je někdy rozlišováno jako sběr odpadků .) Sběrač odpadků bude téměř vždy úzce integrován s alokátorem paměti .

Výhody

Garbage collection osvobozuje programátora od ručního uvolňování paměti. Tím se odstraní nebo sníží některé kategorie chyb :

  • Houpající ukazovátka , které se vyskytují, když kus paměti je uvolněna, zatímco stále existují odkazy na něj, a jeden z těchto ukazatelů je dereferenced . Do té doby může být paměť přeřazena k jinému použití s ​​nepředvídatelnými výsledky.
  • Dvojité chyby , ke kterým dochází, když se program pokusí uvolnit oblast paměti, která již byla uvolněna a možná již byla znovu přidělena.
  • Určité druhy nevracení paměti , kdy program nedokáže uvolnit paměť obsazenou objekty, které se staly nedostupnými , což může vést k vyčerpání paměti.

Nevýhody

Sběr odpadků spotřebovává výpočetní prostředky při rozhodování o tom, kterou paměť uvolnit, přestože programátor tyto informace již možná znal. Trest za pohodlí neoznačení životnosti objektu ručně ve zdrojovém kódu je režie , což může vést ke snížení nebo nerovnoměrnému výkonu. Recenzovaný dokument z roku 2005 dospěl k závěru, že GC potřebuje pětkrát více paměti, aby kompenzoval tuto režii a aby fungoval stejně rychle jako stejný program pomocí idealizované explicitní správy paměti, vložením anotací pomocí věštec implementovaného shromažďováním stop z programů spustit pod profilerem. Programátoři, jako je Jon Harrop, však tvrdí, že taková základní linie je nerealistická, protože programátoři zřídka píší optimální explicitní kód pro správu paměti. Interakce s efekty hierarchie paměti může tuto režii učinit nesnesitelnou za okolností, které je těžké předvídat nebo odhalit v rutinním testování. Dopad na výkon také společnost Apple uvedla jako důvod, proč nepřijala sběr odpadků v systému iOS, přestože jde o nejžádanější funkci.

Okamžik, kdy se odpadky skutečně shromažďují, může být nepředvídatelný, což má za následek, že stánky (pauzy na posun/uvolnění paměti) jsou roztroušeny po celé relaci. Nepředvídatelné překážky mohou být nepřijatelné v prostředích v reálném čase , při zpracování transakcí nebo v interaktivních programech. Inkrementální, souběžné a sběrači odpadků v reálném čase řeší tyto problémy s různými kompromisy.

Strategie

Trasování

Hlavní článek: Trasování smetí

Tracing garbage collection je nejběžnějším typem garbage collection, a to natolik, že „garbage collection“ často odkazuje na tracing garbage collection, spíše než jiné metody, jako je počítání odkazů . Celková strategie spočívá v určení, které objekty by měly být odpadky shromážděné sledováním, které objekty jsou dosažitelné řetězcem odkazů z určitých kořenových objektů, a zvážením zbytku jako odpadků a jejich shromažďováním. Při implementaci se však používá velké množství algoritmů s velmi rozdílnou složitostí a výkonnostními charakteristikami.

Počítání referencí

Hlavní článek: Počítání referencí

Sbírání odpadků při počítání odkazů je místo, kde má každý objekt počet odkazů na něj. Odpadky se identifikují tak, že mají referenční počet nula. Počet odkazů na objekt se zvýší, když se vytvoří odkaz na něj, a sníží se, když je odkaz zničen. Když počet dosáhne nuly, paměť objektu se obnoví.

Stejně jako u ruční správy paměti a na rozdíl od sledování uvolňování paměti, počítání odkazů zaručuje, že jsou objekty zničeny, jakmile je zničena jejich poslední reference, a obvykle přistupuje pouze k paměti, která je buď v mezipaměti CPU , v objektech, které mají být uvolněny, nebo přímo ukazuje na těmi, a proto nemá obvykle významné negativní vedlejší účinky na mezipaměť CPU a provoz virtuální paměti .

Počítání referencí má řadu nevýhod; toto lze obecně vyřešit nebo zmírnit sofistikovanějšími algoritmy:

Cykly
Pokud se dva nebo více objektů na sebe odkazují, mohou vytvořit cyklus, ve kterém ani jeden nebude shromažďován, protože jejich vzájemné reference nikdy nedovolí, aby se jejich počet referencí stal nulovým. Některé systémy pro sběr odpadků využívající počítání odkazů (jako ten v CPythonu ) používají k řešení tohoto problému specifické algoritmy pro detekci cyklu. Další strategií je použít slabé reference pro „backpointery“, které vytvářejí cykly. Při počítání referencí je slabá reference podobná slabé referenci v rámci trasovacího garbage collectoru. Jedná se o speciální referenční objekt, jehož existence nezvyšuje počet referencí referenčního objektu. Kromě toho je slabá reference bezpečná v tom, že když se referenční objekt stane odpadkem, jakýkoli slabý odkaz na něj zanikne , než aby mu bylo dovoleno zůstat visící, což znamená, že se změní na předvídatelnou hodnotu, jako je například nulová reference.
Prostor nad hlavou (počet referencí)
Počítání referencí vyžaduje, aby byl každému objektu přidělen prostor pro uložení jeho počtu odkazů. Počet může být uložen vedle paměti objektu nebo v boční tabulce někde jinde, ale v každém případě každý jeden objekt počítaný referencí vyžaduje pro svůj počet odkazů další úložiště. K tomuto úkolu se běžně používá paměťový prostor o velikosti bez znaménka, což znamená, že pro každý objekt musí být přiděleno 32 nebo 64 bitů úložiště počtu odkazů. V některých systémech může být možné tuto režii zmírnit pomocí označeného ukazatele k uložení počtu referencí do nevyužitých oblastí paměti objektu. Architektura často ve skutečnosti neumožňuje programům přístup k celému rozsahu adres paměti, které by mohly být uloženy ve své velikosti nativního ukazatele; určitý počet vysokých bitů v adrese je buď ignorován, nebo musí být nulový. Pokud má objekt spolehlivě ukazatel na určitém místě, lze počet odkazů uložit do nepoužitých bitů ukazatele. Například každý objekt v Objective-C má na začátku své paměti ukazatel na svou třídu ; na architektuře ARM64 pomocí iOS 7 se k uložení referenčního počtu objektů použije 19 nepoužitých bitů tohoto ukazatele třídy.
Rychlostní režie (přírůstek/úbytek)
V naivních implementacích každé přiřazení odkazu a každý odkaz spadající mimo rozsah často vyžadují úpravy jednoho nebo více čítačů referencí. V běžném případě, kdy je reference zkopírována z proměnné vnějšího rozsahu do proměnné vnitřního rozsahu, takže životnost vnitřní proměnné je ohraničena životností vnější, lze přírůstek odkazu eliminovat. Vnější proměnná „vlastní“ referenci. V programovacím jazyce C ++ je tato technika snadno implementována a demonstrována pomocí constodkazů. Počítání referencí v C ++ se obvykle implementuje pomocí „ chytrých ukazatelů “, jejichž konstruktory, destruktory a operátory přiřazení spravují reference. Chytrý ukazatel lze předat odkazem na funkci, čímž se vyhnete nutnosti zkopírovat a zkonstruovat nový inteligentní ukazatel (což by zvýšilo počet odkazů při vstupu do funkce a snížilo jej při ukončení). Místo toho funkce obdrží odkaz na inteligentní ukazatel, který je vyroben levně. Metoda počítání referencí Deutsch-Bobrow využívá skutečnost, že většina aktualizací počtu odkazů je ve skutečnosti generována referencemi uloženými v místních proměnných. Ignoruje tyto odkazy, pouze počítá odkazy v haldě, ale než bude možné odstranit objekt s nulovým počtem odkazů, musí systém ověřit skenováním zásobníku a zaregistruje, že na něj stále neexistuje žádný jiný odkaz. Další podstatné snížení režie u aktualizací čítačů lze dosáhnout sdružováním aktualizací, které zavedli Levanoni a Petrank . Zvažte ukazatel, který se v daném intervalu provádění několikrát aktualizuje. Nejprve ukazuje na objekt O1, pak na objekt O2a tak dále, dokud na konci intervalu neukáže na nějaký objekt On. Algoritmus počítání referencí by obvykle provést rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Většina těchto aktualizací je ale nadbytečná. Aby byl počet referencí na konci intervalu správně vyhodnocen, stačí provést rc(O1)--a rc(On)++. Levanoni a Petrank změřili odstranění více než 99% aktualizací čítačů v typických benchmarcích Java.
Vyžaduje atomicitu
Při použití ve vícevláknovém prostředí může být nutné, aby tyto úpravy (přírůstek a úbytek) byly atomovými operacemi, jako je například srovnávání a výměna , přinejmenším pro všechny objekty, které jsou sdíleny nebo potenciálně sdíleny mezi více vlákny. Atomové operace jsou drahé na multiprocesoru a ještě dražší, pokud musí být emulovány softwarovými algoritmy. Tomuto problému je možné se vyhnout přidáním počtů referenčních hodnot za vlákno nebo za CPU a přistupováním ke globálnímu počtu referencí pouze tehdy, když se počet místních referencí stane nebo již není nulový (nebo alternativně pomocí binárního stromu referenčních počtů nebo dokonce vzdání se deterministické destrukce výměnou za to, že vůbec nemáme globální počet referencí), ale to zvyšuje režii paměti, a proto bývá užitečné pouze ve zvláštních případech (používá se například při počítání referencí modulů jádra Linuxu ). Aktualizační sloučení od Levanoniho a Petranka lze použít k odstranění všech atomových operací z bariéry proti zápisu. Čítače se v průběhu provádění programu nikdy neaktualizují pomocí podprocesů programu. Upravuje je pouze kolektor, který se spouští jako jediné další vlákno bez synchronizace. Tuto metodu lze použít jako mechanismus stop-the-world pro paralelní programy a také s kolektorem souběžného počítání referencí.
Ne v reálném čase
Naivní implementace počítání referencí obecně neposkytují chování v reálném čase, protože jakékoli přiřazení ukazatele může potenciálně způsobit rekurzivní uvolnění řady objektů ohraničených pouze celkovou alokovanou velikostí paměti, zatímco vlákno nemůže vykonávat jinou práci. Tomuto problému je možné se vyhnout delegováním uvolňování nereferenčních objektů na jiná vlákna za cenu dodatečné režie.

Úniková analýza

Hlavní článek: Úniková analýza

Analýza únik je v době kompilace technika, která může konvertovat haldy přidělení na zásobníku přidělení , čímž se sníží množství sběru odpadků je třeba udělat. Tato analýza určuje, zda je objekt přidělený uvnitř funkce přístupný mimo něj. Pokud se zjistí, že místní alokace funkcí je přístupná jiné funkci nebo vláknu, říká se, že alokace „uniká“ a nelze ji provést v zásobníku. V opačném případě může být objekt přidělen přímo v zásobníku a uvolněn, když se funkce vrátí, čímž se obejde halda a související náklady na správu paměti.

Dostupnost

Obecně lze říci, že programovací jazyky vyšší úrovně mají jako standardní funkci sběru odpadků pravděpodobněji. V některých jazycích, které nemají vestavěnou popelářskou sbírku, ji lze přidat prostřednictvím knihovny, jako u Boehm garbage collector pro C a C ++.

Většina funkčních programovacích jazyků , jako ML , Haskell a APL , má vestavěnou sběr odpadků. Lisp je zvláště pozoruhodný, protože je prvním funkčním programovacím jazykem a prvním jazykem, který zavádí sběr odpadků.

Jiné dynamické jazyky, jako Ruby a Julia (ale ne Perl  5 nebo PHP před verzí 5.3, které oba používají počítání referencí), JavaScript a ECMAScript také obvykle používají GC. Objektově orientované programování jazyky, jako je Smalltalk a Javu obvykle poskytují integrovaný garbage collection. Významnými výjimkami jsou C ++ a Delphi , které mají destruktory .

ZÁKLADNÍ

BASIC a Logo často používaly sběr odpadků pro datové typy s proměnnou délkou, jako jsou řetězce a seznamy, aby nezatěžovaly programátory detaily správy paměti. Na Altair 8800 by programy s mnoha řetězcovými proměnnými a malým řetězcovým prostorem mohly způsobit dlouhé pauzy kvůli shromažďování odpadků. Podobně algoritmus shromažďování odpadků interpretů Applesoft BASIC opakovaně prohledává popisovače řetězců s řetězcem s nejvyšší adresou, aby jej zhutnil směrem k vysoké paměti, což má za následek výkon a pozastaví se od několika sekund do několika minut. Náhradní popelář pro Applesoft BASIC od Randy Wigginton identifikuje skupinu řetězců v každém průchodu hromadou, což dramaticky zkracuje čas sběru. BASIC.System, vydaný s ProDOS v roce 1983, poskytuje mnohonásobně rychlejší okenní popelář pro BASIC.

Cíl-C

Zatímco Objective-C tradičně neměl sběr odpadků, s vydáním OS X 10.5 v roce 2007 Apple představil sběr odpadu pro Objective-C  2.0 pomocí interně vyvinutého runtime kolektoru. Nicméně, s vydáním 2012 OS X 10.8 , garbage collection byl zastaralý ve prospěch LLVM ‚s automatickým referenčním čítačem (ARC), která byla zavedena s OS X 10.7 . Kromě toho, od května 2015 Apple dokonce zakazuje používání smetí pro nové aplikace OS X v App Store . U systému iOS nebylo uvolňování paměti nikdy zavedeno kvůli problémům s odezvou aplikace a výkonem; místo toho iOS používá ARC.

Omezené prostředí

Sběr odpadků se na vestavěných systémech nebo systémech v reálném čase používá jen zřídka, protože je obvyklá potřeba velmi přísné kontroly nad využíváním omezených zdrojů. Byly však vyvinuty popelářské koše kompatibilní s mnoha omezenými prostředími. Microsoft .NET Micro Framework , .NET nanoFramework a Java Platform, Micro Edition jsou integrované softwarové platformy, které, stejně jako jejich větší bratranci, zahrnují sběr odpadků.

Jáva

Popelářské koše dostupné v JDK Java zahrnují:

Čas kompilace

Sbírání odpadků v době kompilace je forma statické analýzy, která umožňuje opětovné použití a regeneraci paměti na základě invariantů známých během kompilace.

Tato forma sběru odpadků byl zkoumán v programovacím jazyce Mercury , a to vidělo větší využití se zavedením LLVM ‚s automatickým referenčním čítačem (ARC) do Apple ekosystému (iOS a OS X) v roce 2011.

Systémy v reálném čase

Byly vyvinuty přírůstkové, souběžné a sběrače odpadků v reálném čase, jako je Bakerův algoritmus nebo Liebermanův algoritmus.

V Bakerově algoritmu se alokace provádí buď v polovině jedné oblasti paměti. Když se naplní na polovinu, provede se sběr odpadu, který přesune živé objekty do druhé poloviny a zbývající objekty se implicitně uvolní. Spuštěný program (dále jen „mutátor“) musí zkontrolovat, zda je jakýkoli objekt, na který odkazuje, ve správné polovině, a pokud jej nepřesunete, zatímco úkol na pozadí vyhledá všechny objekty.

Generační schémata shromažďování odpadků jsou založena na empirickém pozorování, že většina předmětů umírá mladá. V generačním uvolňování paměti jsou uchovávány dvě nebo více alokačních oblastí (generací), které jsou uchovávány odděleně na základě věku objektu. Nové objekty se vytvářejí v „mladé“ generaci, která se pravidelně shromažďuje, a když je generace plná, objekty, na které se stále odkazuje ze starších oblastí, se zkopírují do další nejstarší generace. Občas se provede úplné skenování.

Některé počítačové architektury vyšší úrovně jazyka obsahují hardwarovou podporu pro sběr odpadků v reálném čase.

Většina implementací sběračů odpadků v reálném čase používá trasování . Při použití s ​​operačním systémem v reálném čase takovéto smetáky v reálném čase splňují tvrdá omezení v reálném čase.

Viz také

Reference

Další čtení

externí odkazy