Garbage collection [ 1] v programování je formou automatické správy paměti . Speciální proces , nazývaný garbage collector , periodicky uvolňuje paměť tím , že z ní odstraňuje objekty , které se staly nepotřebnými .
Automatické shromažďování odpadků zlepšuje zabezpečení přístupu do paměti .
Garbage collection poprvé použil John McCarthy v roce 1959 v programovacím prostředí ve funkcionálním programovacím jazyce, který vyvinul, Lisp . Následně byl použit v dalších programovacích systémech a jazycích, především ve funkcionálních a logických . Potřeba shromažďování odpadků v těchto typech jazyků je způsobena skutečností, že struktura těchto jazyků činí extrémně nepohodlné sledovat životnost objektů v paměti a ručně je spravovat. Seznamy široce používané v těchto jazycích a na nich založené složité datové struktury jsou během provozu programů neustále vytvářeny, přidávány, rozšiřovány, kopírovány a je obtížné správně určit okamžik smazání objektu.
Průmyslové procedurální a objektové jazyky dlouho nepoužívaly sběr odpadu. Přednost byla dána ruční správě paměti jako efektivnější a předvídatelnější. Od druhé poloviny 80. let se však technologie garbage collection používá jak v direktivních ( imperativních ), tak v objektových programovacích jazycích a od druhé poloviny 90. let 20. století přibývá vytvořených jazyků a prostředí zaměřených na programování aplikací. odpadkový mechanismus sběrného mechanismu buď jako jediný, nebo jako jeden z dostupných mechanismů správy dynamické paměti. V současnosti se používá v Oberon , Java , Python , Ruby , C# , D , F# , Go a dalších jazycích.
Tradiční způsob správy paměti pro direktivní jazyky je manuální. Jeho podstata je následující:
V jakémkoli jazyce, který umožňuje vytváření objektů v dynamické paměti, existují dva potenciální problémy: visící odkazy a úniky paměti .
Visící ukazatel je odkaz na objekt, který již byl odstraněn z paměti. Po smazání objektu se všechny odkazy na něj uložené v programu „houpají“. Paměť dříve obsazená objektem může být předána operačnímu systému a stane se nepřístupnou, nebo může být použita k přidělení nového objektu ve stejném programu. V prvním případě pokus o přístup k „visícímu“ odkazu spustí mechanismus ochrany paměti a zhroutí program a ve druhém případě to povede k nepředvídatelným následkům.
Vzhled visících referencí je obvykle výsledkem nesprávného odhadu životnosti objektu: programátor zavolá příkaz k odstranění objektu, než se přestane používat.
Vytvořením objektu v dynamické paměti jej programátor nemusí po dokončení použití odstranit. Pokud je proměnné odkazující na objekt přiřazena nová hodnota a neexistují žádné další odkazy na objekt, stane se programově nedostupnou, ale nadále zabírá paměť, protože nebyl zavolán příkaz delete. Tato situace se nazývá únik paměti .
Pokud jsou v programu neustále vytvářeny objekty, na které se ztrácejí odkazy, pak se únik paměti projevuje postupným zvyšováním množství použité paměti; pokud program běží dlouhou dobu, množství jím využívané paměti neustále roste a po nějaké době se systém znatelně zpomaluje (kvůli nutnosti použít swap pro jakékoli přidělování paměti ) nebo program vyčerpá dostupný adresní prostor a končí chybou.
Pokud by paměť počítače byla nekonečná , bylo by možné jednoduše ponechat v paměti nepotřebné objekty. Automatická správa paměti s garbage collection - emulace takového nekonečného počítače na konečné paměti [2] . Z této metafory pramení mnohá omezení garbage collectorů (neexistuje žádná záruka, že se finalizátor spustí; spravuje pouze paměť, nikoli jiné zdroje).
V systému se shromažďováním odpadků je za uvolnění paměti odpovědné prostředí provádění programu. Programátor pouze vytváří dynamické objekty a používá je, nemusí se starat o mazání objektů, protože to prostředí dělá za něj. K tomu je v runtime prostředí zahrnut speciální softwarový modul zvaný „garbage collector“. Tento modul se periodicky spouští, zjišťuje, které z objektů vytvořených v dynamické paměti již nejsou používány, a uvolňuje paměť, kterou zabírají.
Frekvence provozu sběrače odpadků je určena charakteristikami systému. Kolektor může běžet na pozadí a spouštět se, když je program neaktivní (například když je program nečinný a čeká na vstup uživatele). Kolektor odpadu běží bezpodmínečně a zastavuje provádění programu ( Stop -the -world ), když nelze provést další operaci alokace paměti kvůli skutečnosti, že byla vyčerpána veškerá dostupná paměť. Po uvolnění paměti se operace přidělování přerušené paměti obnoví a program pokračuje v provádění. Pokud se ukáže, že paměť nelze uvolnit, běhové prostředí ukončí program s chybovou zprávou „Nedostatek paměti“.
Optimální by bylo odstranit z paměti objekty, ke kterým nebude při další činnosti programu přistupováno. Identifikace takových objektů je však nemožná, protože se redukuje na algoritmicky neřešitelný problém zastavení (k tomu stačí předpokládat, že nějaký objekt X bude použit právě tehdy, když program P úspěšně dokončí ). Proto popeláři používají konzervativní odhady, aby zajistili, že objekt nebude v budoucnu využíván.
Obvykle je kritériem toho, že se objekt stále používá, přítomnost odkazů na něj: pokud v systému nejsou žádné další odkazy na tento objekt, pak jej již program samozřejmě nemůže používat, a proto může být smazáno. Toto kritérium používá většina moderních popelářů a nazývá se také dosažitelnost objektu . Není to teoreticky nejlepší, protože podle něj mezi dosažitelné objekty patří i ty objekty, které nebudou nikdy použity, ale na které stále existují reference, ale zaručuje ochranu před výskytem „vislých“ referencí a lze je poměrně efektivně implementovat. .
Neformálně lze uvést následující rekurzivní definici dosažitelného objektu:
Algoritmus příznaku
Jednoduchý algoritmus pro určování dosažitelných objektů, algoritmus Mark and Sweep, je následující:
Pokud na sebe dva nebo více objektů odkazuje, ale žádný z těchto objektů není odkazován zvenčí, je celá skupina považována za nedosažitelnou. Tento algoritmus vám umožňuje zaručit odstranění skupin objektů, jejichž používání bylo ukončeno, ale ve kterých existují vzájemné vazby. Takové skupiny jsou často označovány jako „ostrovy izolace“.
Algoritmus počítání referencíDalší variantou algoritmu dosažitelnosti je obvyklé počítání referencí . Jeho použití zpomaluje operace přiřazování referencí, ale definice dosažitelných objektů je triviální - jsou to všechny objekty, jejichž hodnota referenčního počtu přesahuje nulu. Bez dalších upřesnění tento algoritmus, na rozdíl od předchozího, neodstraňuje cyklicky uzavřené řetězce zastaralých objektů, které mají na sebe vazby.
Jakmile je definována sada nedosažitelných objektů, může garbage collector uvolnit paměť, kterou zabírají, a zbytek ponechat tak, jak je. Po uvolnění paměti je také možné přesunout všechny nebo část zbývajících objektů do jiných oblastí paměti a současně s tím aktualizovat všechny odkazy na ně. Tyto dvě implementace jsou označovány jako non -relocating a relocating , v tomto pořadí .
Obě strategie mají výhody i nevýhody.
Rychlost alokace paměti a dealokace Nepřemisťující se garbage collector uvolňuje paměť rychleji (protože pouze označí příslušné bloky paměti jako volné), ale tráví více času jejím alokováním (protože paměť se fragmentuje a alokace musí najít správné množství bloků odpovídající velikosti v paměti ). Kolektor přesunu trvá relativně déle, než shromáždí odpadky ( defragmentace paměti a změna všech odkazů na přesouvané objekty zabere více času), ale přesun umožňuje extrémně jednoduchý a rychlý ( O(1) ) algoritmus alokace paměti. Při defragmentaci se objekty přesouvají tak, aby se veškerá paměť rozdělila na dvě velké oblasti – obsazená a volná, a uloží se ukazatel na jejich hranici. Pro alokaci nové paměti stačí pouze posunout tuto hranici a vrátit kus ze začátku volné paměti. Rychlost přístupu k objektům v dynamické paměti Objekty, jejichž pole jsou sdílená, lze v paměti umístit blízko sebe pomocí kolektoru přesunů. Pak je pravděpodobnější, že budou současně v mezipaměti procesoru , což sníží počet přístupů k relativně pomalé paměti RAM . Kompatibilita zahraničního kódu Přemístění garbage collector způsobuje problémy při použití kódu, který není spravován automatickou správou paměti (takový kód se v tradiční terminologii nazývá cizí nebo v terminologii Microsoftu nespravovaný ) . Ukazatel na paměť alokovanou v systému s nepřemístitelným kolektorem lze jednoduše předat cizímu kódu k použití, přičemž je třeba zachovat alespoň jeden pravidelný odkaz na objekt, aby jej kolektor nevymazal. Pohybující se kolektor mění polohu objektů v paměti, synchronně mění všechny odkazy na ně, ale nemůže měnit odkazy v cizím kódu, v důsledku toho se odkazy předané cizímu kódu po přesunutí objektu stanou nesprávnými. Pro práci s cizím kódem se používají různé speciální techniky, například připnutí je výslovné zablokování objektu, které zamezí jeho pohybu při sbírání odpadu.Jak ukazuje praxe, nedávno vytvořené objekty se stávají nedostupnými častěji než objekty, které existují po dlouhou dobu. V souladu s tímto vzorem mnoho moderních popelářů rozděluje všechny objekty do několika generací - série objektů s blízkou životností. Jakmile dojde paměť přidělená jedné z generací, v této generaci a ve všech „mladších“ generacích se hledají nedosažitelné předměty. Všechny jsou odstraněny a zbývající jsou převedeny na "starší" generaci.
Použití generací zkracuje dobu cyklu shromažďování odpadků snížením počtu objektů, které jsou skenovány během shromažďování, ale tato metoda vyžaduje běhové prostředí, aby bylo možné sledovat odkazy mezi různými generacemi.
Aby program mohl používat garbage collection, musí být splněna řada podmínek, které se týkají jazyka, běhového prostředí a úlohy samotné.
The Need for a Runtime with a Garbage Collector Přirozeně, garbage collection vyžaduje dynamické prostředí, které podporuje provádění programu, a přítomnost garbage collectoru v tomto prostředí. U interpretovaných jazyků nebo jazyků kompilovaných do bytekódu virtuálního stroje může být garbage collector zahrnut do kódu jazyka nebo bajtového interpretru, ale pro jazyky kompilované do objektového kódu je garbage collector nucen stát se součástí systému knihovna, která je při vytváření spustitelného souboru propojena (staticky nebo dynamicky) s programovým kódem, čímž se zvětšuje velikost programu a doba jeho načítání. Podpora programovacího jazyka Sběrač odpadu může správně fungovat pouze tehdy, když dokáže přesně sledovat všechny odkazy na všechny vytvořené objekty. Je zřejmé, že pokud jazyk umožňuje konverzi odkazů (ukazatelů) na jiné datové typy (celá čísla, pole bajtů atd.), jako je C / C++ , nebude možné sledovat použití takto převedených odkazů a odpadní odpad ztrácí smysl. - nechrání před "zavěšením" odkazů a úniky paměti. Proto jazyky orientované na sběr odpadků obvykle výrazně omezují svobodu používat ukazatele, aritmetiku adres, převody typů ukazatelů na jiné datové typy. Některé z nich nemají datový typ „ukazatel“ vůbec, některé ano, ale neumožňují konverze typu ani změny. Technická přípustnost krátkodobých zpoždění v práci programů Svoz odpadu se provádí pravidelně, obvykle v neznámých časech. Pokud pozastavení programu na dobu srovnatelnou s dobou garbage collection může vést ke kritickým chybám , je evidentně nemožné garbage collection v takové situaci použít. Mít určitou rezervu volné paměti Čím více paměti má běhové prostředí k dispozici, tím méně často se garbage collector spouští a tím je efektivnější. Provozování garbage collectoru v systému, kde se množství paměti dostupné pro garbage collector blíží maximální poptávce programu, může být neefektivní a plýtvání. Čím menší je přebytek paměti, tím častěji kolektor běží a tím více času zabere jeho spuštění. Pokles výkonu programu v tomto režimu může být příliš významný.Na rozdíl od toho, co se často říká, přítomnost garbage collection vůbec nezbavuje programátora všech problémů se správou paměti.
Uvolněte další zdroje obsazené objektem Kromě dynamické paměti může objekt vlastnit další zdroje, někdy cennější než paměť. Pokud objekt při vytvoření otevře soubor, musí jej po dokončení použití zavřít, pokud se připojí k DBMS, musí se odpojit. V systémech s manuální správou paměti se tak děje bezprostředně před odstraněním objektu z paměti, nejčastěji v destruktorech odpovídajících objektů. V systémech s garbage collection je obvykle možné provést nějaký kód těsně před smazáním objektu, tzv. finalizéry , ale ty nejsou vhodné pro uvolnění zdrojů, protože okamžik smazání není předem znám a může se změnit že zdroj je uvolněn mnohem později, než se objekt přestane používat. V takových případech musí programátor stále ručně sledovat použití objektu a ručně provádět operace k uvolnění zdrojů obsazených objektem. V C# existuje rozhraní speciálně pro tento účel IDisposable, v Javě - AutoCloseable. Únik paměti V systémech s garbage collection může také dojít k únikům paměti, i když mají trochu jiný charakter. Odkaz na nepoužívaný objekt může být uložen v jiném objektu, který se právě používá, a stane se jakousi „kotvou“, která drží nepotřebný objekt v paměti. Vytvořený objekt je například přidán do kolekce používané pro pomocné operace, poté se přestane používat, ale není z kolekce odstraněn. Sbírka obsahuje odkaz, objekt zůstává dosažitelný a není shromažďován odpadky. Výsledkem je stejný únik paměti. Pro odstranění těchto problémů může runtime podporovat speciální funkci - tzv. slabé reference . Slabé reference objekt neudrží a promění se v nullto, jakmile objekt zmizí – takže kód musí být připraven na to, že jednoho dne reference neukáže nikam. Ztráta efektivity operací s častým přidělováním a přidělováním paměti Některé akce, které jsou na systémech s manuální správou paměti zcela neškodné, mohou na systémech s garbage collection způsobit neúměrně velkou režii. Klasický příklad takového problému je uveden níže. String out = "" ; // Předpokládá se, že řetězce obsahují velké množství krátkých řetězců, // ze kterých je potřeba shromáždit jeden velký řetězec do proměnné out. for ( String str : strings ) { out += str ; // Tento kód vytvoří // novou řetězcovou proměnnou při každé iteraci a přidělí jí paměť. } Tento kód Java vypadá, jako by proměnná out, vytvořená jednou, byla „připojena“ k novému řádku pokaždé ve smyčce. Ve skutečnosti jsou řetězce v Javě neměnné, takže v tomto kódu se při každém průchodu smyčkou stane následující:Ve srovnání s manuální správou paměti je shromažďování odpadu bezpečnější, protože zabraňuje únikům paměti a visícím odkazům z předčasné likvidace objektů. Také to zjednodušuje samotný proces programování .
Předpokládá se, že sběr odpadu výrazně snižuje režii správy paměti ve srovnání s jazyky, které jej neimplementují. Podle studie [3] programátoři v jazyce C stráví 30 až 40 % svého celkového času vývoje (bez ladění) samotnou správou paměti. Existují však studie s opačnými závěry, např. v [4] se uvádí, že skutečný rozdíl v rychlosti vývoje softwaru v C ++, kde není automatický garbage collection, a v Javě, kde je implementován , je malý.
Přítomnost garbage collectoru u nezkušeného vývojáře může vytvořit falešné přesvědčení, že se správě paměti vůbec nemusí věnovat. I když garbage collector redukuje problémy se špatnou správou paměti, neodstraní je úplně a ty, které přetrvávají, se neprojevují jako zjevné chyby, jako je obecná chyba ochrany , ale jako plýtvání pamětí při spuštění programu. Typický příklad: pokud programátor ztratil ze zřetele skutečnost, že na objektu v globálním rozsahu zůstal alespoň jeden nenulovatelný ukazatel, takový objekt nebude nikdy smazán; najít takový pseudoúnik může být velmi obtížné.
Často je kritické nejen zajistit, aby byl prostředek uvolněn, ale také zajistit, aby byl uvolněn před voláním nějaké jiné procedury – například otevření souborů, záznamů v kritických sekcích. Pokusy předat kontrolu nad těmito zdroji garbage collectoru (prostřednictvím finalizátorů ) budou neefektivní nebo dokonce nesprávné, takže je budete muset spravovat ručně. Nedávno byla i v jazycích s garbage collectorem zavedena syntaxe, která zaručuje provedení „čistícího kódu“ (například speciální metoda „destruktoru“), když se proměnná odkazující na objekt dostane mimo rozsah.
V mnoha případech jsou systémy s garbage collection méně efektivní, a to jak z hlediska rychlosti, tak z hlediska využití paměti (což je nevyhnutelné, protože garbage collector sám spotřebovává zdroje a potřebuje nadbytečnou volnou paměť, aby správně fungoval). Navíc v systémech s garbage collection je obtížnější implementovat nízkoúrovňové algoritmy, které vyžadují přímý přístup k paměti RAM počítače, protože volné použití ukazatelů je nemožné a přímý přístup do paměti vyžaduje speciální rozhraní napsaná v nízkoúrovňových jazycích. . Na druhou stranu moderní systémy pro sběr odpadu používají velmi účinné algoritmy správy paměti s minimální režií. Nelze také nevzít v úvahu skutečnost, že RAM je nyní relativně levná a dostupná. Za takových podmínek jsou situace, kdy jsou náklady na svoz odpadu kritické pro efektivitu programu, extrémně vzácné.
Významnou výhodou garbage collection je, když dynamicky vytvářené objekty žijí dlouhou dobu, jsou mnohokrát duplikovány a odkazy na ně jsou předávány mezi různými částmi programu. V takových podmínkách je poměrně obtížné určit místo, kde se objekt přestal používat a lze jej smazat. Vzhledem k tomu, že právě toto je situace s rozšířeným používáním dynamicky se měnících datových struktur (seznamy, stromy, grafy), je garbage collection nezbytný ve funkčních a logických jazycích, které takové struktury široce využívají, jako je Haskell , Lisp nebo Prolog . Použití garbage collection v tradičních imperativních jazycích (založených na strukturálním paradigmatu, možná doplněném o objektová zařízení) je určeno žádoucí rovnováhou mezi jednoduchostí a rychlostí vývoje programu a efektivitou jeho provádění.
Podpora v některých imperativních jazycích pro automatické volání destruktoru, když objekt překročí syntaktický rozsah ( C++ [5] , Ada , Delphi ) umožňuje umístit kód uvolnění paměti do destruktoru a mít jistotu, že bude volán i tak . To vám umožňuje soustředit nebezpečná místa v rámci implementace třídy a nevyžaduje další zdroje, ačkoli to klade vyšší požadavky na kvalifikaci programátora. Současně je možné bezpečně uvolnit další zdroje obsazené objektem v destruktoru.
Alternativou k garbage collection je technologie používání „ chytrých referencí “, kdy odkaz na dynamický objekt sám sleduje počet uživatelů a automaticky maže objekt, když se toto číslo stane nulou. Známým problémem „chytrých referencí“ je to, že v podmínkách, kdy program neustále vytváří v paměti mnoho malých objektů s krátkou životností (například při zpracování struktur seznamu), ztrácí na výkonu garbage collection.
Od 60. let 20. století existuje oblastní správa paměti , technologie, ve které je paměť rozdělena na relativně velké fragmenty zvané regiony a již v rámci regionů je paměť alokována jednotlivým objektům. Při ručním řízení jsou regiony vytvářeny a mazány samotným programátorem, při automatickém řízení se používají různé typy konzervativních odhadů k určení, kdy se přestanou používat všechny objekty alokované v rámci regionu, načež systém správy paměti celý region vymaže. Například je vytvořena oblast, ve které je paměť alokována pro všechny objekty vytvořené v určitém oboru, nikoli předané mimo, a tato oblast je zničena jedním příkazem, když provádění programu opustí tento rozsah. Přechod ve správě paměti (ať už manuální nebo automatické) z jednotlivých objektů na větší celky nám v mnoha případech umožňuje zjednodušit účtování doby životnosti objektů a zároveň snížit režijní náklady. Implementace (různých stupňů automatizace) správy regionální paměti existují pro mnoho programovacích jazyků, včetně ML , Prolog , C , Cyclone .
Programovací jazyk Rust nabízí koncept „vlastnictví“ založený na přesné kontrole překladače nad životností a rozsahem objektů. Myšlenka je taková, že když je objekt vytvořen, proměnná, které je na něj přiřazen odkaz, se stává „vlastníkem“ tohoto objektu a rozsah proměnné vlastníka omezuje životnost objektu. Při opuštění rozsahu vlastníka se objekt automaticky smaže. Přiřazením odkazu na objekt k jiné proměnné jej lze „vypůjčit“, ale vypůjčení je vždy dočasné a musí být dokončeno během životnosti vlastníka objektu. "Vlastnictví" může být převedeno na jinou proměnnou (např. objekt může být vytvořen uvnitř funkce a vrácen jako výsledek), ale původní vlastník ztratí přístup k objektu. Dohromady jsou pravidla navržena tak, aby zajistila, že objekt nemůže být nekontrolovatelně upravován prostřednictvím cizích odkazů. Kompilátor staticky sleduje životnost objektů: jakákoli operace, která může dokonce potenciálně vést k uložení odkazu na objekt poté, co jeho vlastník přejde mimo rozsah, vede k chybě kompilace, která eliminuje výskyt „vislých referencí“ a úniky paměti. Tento přístup komplikuje techniku programování (respektive ztěžuje učení se jazyku), ale eliminuje potřebu jak ruční alokace a dealokace paměti, tak používání garbage collection.
Sběr odpadků jako nepostradatelný atribut prostředí spouštění programu se používá v jazycích založených na deklarativním paradigmatu , jako je LISP , ML , Prolog , Haskell . Jeho nezbytnost je v tomto případě dána samotnou povahou těchto jazyků, které neobsahují nástroje pro ruční správu životnosti objektů a nemají možnost přirozené integrace takových nástrojů. Základní komplexní datovou strukturou v takových jazycích je obvykle dynamický jednotlivě propojený seznam skládající se z dynamicky alokovaných buněk seznamu. Seznamy jsou neustále vytvářeny, kopírovány, duplikovány, kombinovány a rozdělovány, takže je téměř nemožné ručně spravovat životnost každé přidělené buňky seznamu.
V imperativních jazycích je garbage collection jednou z možností spolu s manuálními a některými alternativními technikami správy paměti. Zde je to považováno za prostředek pro zjednodušení programování a předcházení chybám . Jedním z prvních kompilovaných imperativních jazyků s garbage collection byl Oberon , který prokázal použitelnost a poměrně vysokou efektivitu tohoto mechanismu pro tento typ jazyka, ale jazyk Java přinesl tomuto přístupu velkou popularitu a popularitu . Následně byl přístup Java opakován v prostředí .NET a téměř ve všech jazycích v něm pracujících, počínaje C # a Visual Basic .NET . Zároveň se objevilo mnoho interpretovaných jazyků (JavaScript, Python, Ruby, Lua), kde byl garbage collection zahrnut z důvodů jazykové dostupnosti pro neprogramátory a zjednodušení kódování. Nárůst hardwarového výkonu, ke kterému došlo současně se zdokonalováním samotných kolektorů, vedl k tomu, že další režie na svoz odpadu přestala být významná. Většina moderních imperativních jazyků shromažďujících odpadky nemá vůbec žádný způsob, jak explicitně ručně odstranit objekty (jako je operátor delete). V systémech používajících interpret nebo kompilaci do bajtového kódu je garbage collector součástí runtime; ve stejných jazycích, které se kompilují do objektového kódu procesoru, je implementován jako požadovaná systémová knihovna.
Existuje také malý počet jazyků ( nim , Modula-3 , D ), které podporují manuální i automatickou správu paměti, pro kterou aplikace využívá dvě samostatné haldy.