Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/www/novacisko.cz/subdomains/bredy/init.php on line 11

Warning: mysql_connect(): Headers and client library minor version mismatch. Headers:50562 Library:100020 in /home/www/novacisko.cz/subdomains/bredy/init.php on line 11

Warning: Cannot modify header information - headers already sent by (output started at /home/www/novacisko.cz/subdomains/bredy/init.php:11) in /home/www/novacisko.cz/subdomains/bredy/index.php on line 38
Garbage collector - automatický úklid objektů v C++ - Bredyho blog - Ondřej Novák
Bredyho blog - Ondřej Novák

Garbage collector - automatický úklid objektů v C++

Článek navazuje na GarbageCollector v C++, prototyp, kde jsme si představili prototyp třídy provádějící automatický úklid objektů známy jako "garbage collector". Dnes si ukážeme další verzi, nazvěme ji "alfa"


Úvodem

Přestože jsem stále zarputilým odpůrcem všelijakých automatizovaných nástrojů na "úklid nepořádku" přímo integrovaných do programovacího jazyka (tedy, jazyky, které jsou na garbage collectorech založené), stalo se mi, že v jednom projektu se takovému systému jednoduše nevyhnu. Jak praví přísloví, "člověk míní, bohové mění" a tak nakonec padlo rozhodnutí, že život určité skupiny objektů bude hlídat právě "garbage collector" (budeme zkracovat na GC).

A protože celý projekt je v C++ a měl by v tomto jazyce zůstat, rozhodl jsem se oprášit starý prototyp, trochu jej vylepšit a na jeho základě vystavět novou verzi GC, která by už byla ve stavu možném k nasazení.

Jak na GC v C++

Předně už z předchozího dílu je zřejmé, že GC začíná u chytrých ukazatelů. Stejně jako auto_ptr nebo shared_ptr se jedná o objekt, který emuluje funkcionalitu klasického ukazatele s tím, že některé operace provádí jinak a tím rozšiřuje jeho možnosti. Například auto_ptr automaticky destruuje objekt, na který ukazatel ukazuje v při volání destruktoru auto_ptr. A protože destruktory objektů alokovaných automaticky se volají též automaticky, benefit takového chytrého ukazatele je, že odpadá starost programátora o likvidaci objektů.

Chytrým ukazatelem u našeho GC bude GCPtr. Bude to šablona, obalující funkcionalitu klasického ukazatele. Automaticky bude sledovat vznik nových objektů, a ... a to je u GC nejdůležitější ... vznik a zánik referencí mezi objekty.

Hlídání referencí

Aby GC pracoval, musí sledovat všechny reference mezi objekty, které spravuje. Tak lze jedině poznat, které objekty jsou ještě referencované a které nejsou. Pojďme si tedy popsat, jakým způsobem bude GC toto provádět.

Typy referencí

GC musí hlídat, který objekt odkazuje na který. Z hlediska typu odkazu (reference) rozlišujeme dva druhy

  • interní
  • externí.

Interní reference je taková, kde jeden objekt spravovaný GC ukazuje na jiný objekt spravovaný tímtéž GC. Naproti tomu externí reference je reference, o které se ví, že ukazuje na nějaký objekt spravovaný v GC, ale jeho zdroj je neznámy, leží mimo oblast, kterou GC spravuje. Tyto reference bývají právě zpravidla ty, které drží všechny objekty "na živu". Bez externích referencí by totiž GC usoudil, že žádný z objektů, které spravuje není potřebný (navzájem se referencují), a všechny by smazal.

Názorný příklad

Tento obrázek ukazuje příklad, jak mohou vypadat reference mezi objekty
,Obecný orientovaný graf
Modrými kroužky jsou označené objekty ležící mimo oblast spravovanou GC.

Kostra grafu

Obrázek není přehledný ani pro člověka ani pro počítač. Není zřejmé, co na čem závisí hodně a co málo. Pouze návrhář mohl některým odkazům dát větší váhu než jiným, ale bez toho, aby se tyto odkazy označily to nezjistíme. Při používání GC ani nechceme nic takového specifikovat. GC si tedy musí vypomoci sám. Protože v grafu vidíme cykly a ty nejsou žádoucí (cyklické reference podporují samy sebe v cyklu), musíme v grafu vytvořit podgraf, který nebude cyklický. Z teorie grafů si vzpomeneme, že stačí sestavit kostru grafu. A protože graf je orientovaný, je v tomto případě potřeba sestavit kostru takovou, aby bylo možné se po šipkách dostat ze všech uzlů podpořených externí referencí do všech ostatních uzlů. Pokud by pro některé uzly neexistovala žádná taková cesta z externího uzlu, pak tyto uzly jsou kandidáty na uklizení.

Ukažme si stejný příklad s zvýrazněnou kostrou grafu.

Už to vypadá přehledněji. Zároveň zde vidíme prostor pro optimalizaci GC. Je vidět, že GC nemusí reagovat na všechny zrušené reference. Pokud totiž program zruši referenci, kterou si GC neoznačil (černá šipka), nemusí se GC situací nijak více zabývat, protože ví, že odstraněním šipky se graf nerozpadne. Teorie grafů říká o kostře: Kostra je taková minimální množina hran grafu, že odstraněním libovolné hrany náležící do této množiny se graf rozpadne do dvou komponent. Uvedenou optimalizaci ještě na obrázku:

Všimněte si, že pro každý uzel platí, že má vždy právě jednu modrou šipku, která na něj ukazuje. Pokud by existoval uzel, který nemá žádnou takovou šipku, pak je kandidát na smazání.

Pokud odstraníme šipku označenou zeleným křížkem, nic se nestane. GC musí ovšem zasáhnout v případě, že odstraníme šipku označenou červeným křížkem.

Situace po odstranění šipky s červeným křížkem bude vypadat takto.

  1. Řekli jsme si, že uzel, který ztratí modrou šipku (ukazující na něj) je kandidát na smazání.
  2. Uzel však má pud sebezáchovy, a tak se začne hledat způsob, jak přežít. Naštěstí má na výběr ještě jednu šipku (tu která byla označena zeleným křížkem, avšak v tomhle příkladě jsme ji neodstranili)
  3. Uzel zjistí, že druhá šipka jej spojí s uzlem, který je podpořen další modrou šipkou.
  4. Protože je uzel nedůvěřivý, nechá si ověřit, že bude-li postupovat proti modrým šipkám, skutečně dosáhne externí reference.
  5. Z grafu je vidět, že uspěje, má tedy povoleno ze zbývající šipky udělat modrou a tím odvrátit hrozící likvidaci.

Výsledek:

V dalším příkladě se program rozhodne odříznout jednu z externích referencí, například proto, že nějaká část programu už nepotřebuje objekty dále referovat.

Je zřejmé, že uzel, který ztrácí modrou šipku, opět začne hledat podporu, aby odvrátil hrozící likvidaci. Na výběr má dva sousedy, uzel nahoře a uzel dole. Oba dva jsou podpořeny modrou šipkou. Důležitou součástí celého postupu je ale ověření, že opravdu modré šipky vedou od externí reference!!. Právě ověřením, postupem proti šipkám, dosáhne uzel sama sebe, nikoliv však žádné externí reference. Je zřejmé, že modré šipky v jeho okolí nejsou platné a tak je přebarví na černé.

Uzly, které takto ztratí modré šipky jsou taktéž kandidáty na smazání, a protože i oni mají pud sebezáchovy, začnou se shánět po sousedech mající podporu modré šipky.

Je zřejmé, že uzel uprostřed uspěje v hledání podpory a může tak tuto podporu předat dalším uzlům. Nakonec svou podporu najdou všechny uzly a graf bude vypadat takto:


(není to jediné řešení)

Buďme teď trochu zákeřní, a v následujícím kroku naše aplikace odstraní modrou šipku, která jako první podpořila naši skupinu ohrožených uzlů (označená křížkem)

Aplikováním postupu uvedeného nahoře dojdeme k tomu, že všechny modré šipky sousedů ohroženého uzlu nejsou platné, protože nejsou podpořeny externí referencí a jsou tudíž přebarveny na černé. Ohrožena je celá skupinka uzlu ležící nalevo obrázku. Teprve uzel úplně nahoře, podpořen modrou šipkou skupinku zachrání a graf bude vypadat takto:

Na grafu je už vyznačen i další postup, kdy odstraníme i poslední modrou šipku, která skupinu zachránila. Nyní má ohrožený uzel na výběr jen jedninou podporu a tou je červená šipka. Jenže žádná z podporu nevede k externímu odkazu. Nakonec všechny uzly přijdou o modré šipky a žádný uzel nezíská od žádného souseda podporu v podobě modré šipky. V tenhle okamžik GC má jistotu, že objekty v levé části může smazat.

Postup implementace

Jak už bylo naznačeno, na začátku stojí chytrý ukazatel GCPtr. Protože napsat chytrý ukazatel zvládne každý průměrny C++ programátor, nebudeme se jím zabývat, postačí, když si budeme definovat rozhraní, pomocí jakého ukazatel komunikuje s vlastním GC.

Budou tam operace

Registrace objektu
Je zřejmé, že každý objekt je třeba do GC registrovat, aby o něm GC věděl. Registrace objektu se bude provádět v konstruktoru GCPtr. Tady je potřeba si dát pozor na jednu záležitost. Často tvoříme objekty a ihned je přiřazujeme ukazateli předka (rozhraní). GCPtr musí být napsán tak, aby v době konstrukce ještě věděl typ vytvořeného objektu před tím, než o tuto informaci přijdeme. K registraci objektu bude totiž potřeba znát jeho adresu (ovšem první adresu vůbec), a jeho celkovou velikost. Ani jedna informace po přiřazení předkovi nemusí být z vlastního ukazatele zjistitelná, minimálně prostředky standardního C++ (hacking RTTI tabulky neuvažujeme)
Registrace reference
Kdykoliv vznikne reference, tak GC musí být informován o tom "odkud-kam".
Zánik reference
Je důležité právě proto, aby se vědělo, jestli existuje ještě nějaká reference.

Doplňkově lze zařadit funkce zrušení registrace (viz dále) a různé pomocné funkce, jako třeba funkci vynucení collect

Mapa paměti

Tak jako v předchozím dílě, kdy se popisoval prototyp. i tato implementace je tzv, neintruzivní. JInými slovy, vlastní činnost GC nezasahuje nijak do života spravovaných objektů a referencí. Jedinou výjimkou je vlastní proces ničení (finalizace), avšek v té době již objekt zpravidla nikdo nevlastní a GC tedy vlastní akcí zničení nikam nezasahuje.

K této implementaci tedy potřebujeme někde bokem uchovávat informace o různých objektech spravované v GC. Říkejme tomu mapa paměti, nebo taky databáze registrovaných objektů. Každý objekt, který je spravován GC zde má záznam a v záznamu se dočteme...

  • Adresu objektu
  • Velikost objektu v bajtech
  • Likvidační funkci - funkce implementující likvidaci toho příslušného objektu.
  • Kontejner zpětných odkazů
  • Zpětný odkaz na kostře
  • .. a další (viz dále).

Adresa a délka objektu jsou vedena zejména z toho důvodu, aby mohly vznikat reference odkazující odněkud prostředka jednoho objektu někam doprostřed druhého objektu. První případ nastává běžně, pokud GCPtr zařadíme mez členské proměnné daného objektu. Druhý případ se vyskytuje při vícenásobné dědičnosti.
Mazací funkci definuje GCPtr, ale pomocí traits lze definovat vlastní. Výchozí implementace volá operator delete
Kontejner zpětných odkazů už úzce souvisí z činnosti GC. Kontejner mapuje všechny odkazy, ale evidovány opačně. Tedy jsou shromážděny u toho objektu, na který ukazují. Při hledání opory (modré šipky) tak není potřeba komplikované chodit proti šipkám, stačí projít kontejner zpětných odkazů.
Zpětný odkaz na kostře je vůbec nejdůležitější. Jak jsme si ukázali na příkladu, každý uzel měl aspoň jednu modrou šipku. Pokud ji definujeme jako zpetný odkaz, postačí nám jedna proměnná v pro každý registrovaný objekt.

Běžné operace s GC

Při běžné činnosti GC pouze registruje nově vznikající objekty a zapisuje, či ruší vzniklé zpětné odkazy. U zpětných odkazů vedeme zejména adresy ukazatelů. Pokud náhodou evidujeme zrušení zpětného odkazu, který byl zároveň oporou (modrá šipka), je potřeba objekt, u kterého se tak stalo, nějakým způsobem označit, aby v případě provádění Collect byl tento objekt uvolněn. Collect není třeba provádět ihned, protože by nemuselo být efektivní přepočítávat kostru, kterou následně opět někdo poruší, je lepší kostru přepočítávat hromadně, po větším množství rušení zpětných odkazů.

K označování objektů vhodných ke zkontrolování se používá v této implementaci spojový seznam. Ten je implementován přímo v záznamech mapy paměti a je organizován jako zásobník. (Implementace je řešena formou 'ukazatel na další'). Mezi objekty vhodn0 ke zkontrolování jsou také zařazovány ty, jež přišly o referenci a zároveň nemají definovanou oporu (modrou šipku), protože samy jsou odkazovány některou externí referencí. Neprovádí se zkoumání, zda ztracená reference byla, či nebyla externí. To je ze dvou důvodů. Prvním důvodem je fakt, že prověřování typu reference v tomto místě nemusí být efektivní, mnohem rychlejší je během jednorázového Collect prověřit zbývající reference (a zpravidla tam už není žádná). Druhým důvodem je nenadálý zánik externí reference registrací. Je totiž potřeba si uvědomit, jak vlastně vzniká taková propojená objektová struktura. Zejména při hromadné konstrukci nějakým konstruktorem.

Pokud máme objekt A, který v konstruktoru instanciuje objekt B a přiřadí jej do GCRef, pak pro objekt B je tento GCRef externí reference. Následně však přiřadíme objekt A do nějakého jiného GCRef a v tu chvíli se z reference na B stává interní reference. Přitom nalézt takovou situaci vyžaduje procházet reference dopředu, zatímco my vedeme seznam zpětných referencí. Z toho důvodu jsou automaticky podezřelé všechny objekty, které byly v minulosti referencovány externí referencí. Pokud taková reference existuje, pak zpracování takového objektu je velice rychlé. Pokud neexistuje, ale existuje interní, je nalezena kostra grafu a tím je celý problém vyřešen.

Collect

Collect je zvláštní druh operace, která pozastaví program (v MT prostředí pozastaví pouze veškeré alokace) a přezkoumá zpětné reference všech označených objektů (a zařazených do spojového seznamu).

  1. Collect postupně prochází zásobník (začne naposledy vloženým objektem). Aby bylo možné během collect používat označování, je zásobník přesunut do jiné proměnné a původní zásobník vynulován (což je přesun ukazatele)
  2. Pro každý objekt zkontroluje všechny zpětné odkazy podle postupu popsané v první části.
  3. Pakliže objekt nenajde žádné opory, je znovu označen (zařazen do nového zásobníku).

Takto Collect projde celý původní zásobník objektu. Přitom eviduje, zda během kontrol došlo k nějaké činnosti (nějaký objekt uspěl v hledání opory, nebo přibyly nějaké další označené objekty. Pakliže takovou činnost zaznamenal, celý cyklus se opakuje.
Ale v případě, že již žádná činnost zaznamenána není, je zřejmé, že jakékoliv další opakování by opět vedlo k nečinnosti. V tom případě, jak už bylo ukázáno v první části, opora nalezena není a všechny označené objekty jsou fyzicky odstraněny.

Operace collect má nejhorší složitost v případě, kdy je třeba sestavit kostru grafu spojového seznamu. V tomto případě asymptoticky dosahuje O(N^2). Přesnější asymptotu lze popsat, pokud si uvědomíme, že při úspěšném nalezení kostry budou jednotlivé objekty postupně odebírány, pak je složitost vyjádřena N+(N-1)+(N-2)+...+3+2+1 = O(N^2/2). V praxi ale bude složitost řádově menší, počet cyklů bude hodně záviset na komplikovanosti propojení objektu, ale v průměru to může být desetiny až setiny N^2. (V mém testu dokonce tisíciny N^2). Složitost také sníží i to, že objekty jsou procházeny stylem ping-pong, neboli nejprve se projdou v jednom pořadí, a díky označování ukládáním na zásobník se pak prochází v opačném pořadí (takže i ten spojový seznam není krajní případ, protože bude vyžadovat dva až tři velké průchody, bez ohled na N).

Validace kostry

Při hledání opory každého objektu je třeba validovat nalezené kostry. Protože na jednu kostru se zpravidla narazí z několika směrů, je zbytečné, aby se neustále dokola validovala. Jednotlivé objekty (uzly) tedy také vedou informaci, zda-li nalezená kostra je již validovaná (tedy v rámci jednoho collect byla ověřena). Aby bylo možné rušit ověření hromadně, provádí se označování pomocí čítače. V globálním čítači se inkrementuje hodnota pokaždé, když je třeba validaci prohlásit za neplatnou. Ověřená kostra je pouze ta, jejíž objekt (uzel), který obsahuje odkaz na další objekt (uzel) v kostře má v lokálním čítači, stejnou hodnotu, jako hodnota globálního čítače. Pokud ne, musí se kostra ověřit a po úspěšném ověření se lokální čítač každého uzlu v kostře aktualizuje.

Vícenásobný Collect

V kapitole "Collect" byl popsán algoritmus uvolňování nereferencovaných objektů. Přitom se jedná jen o část operace. Při uvolnění několika objektů totiž může nastat situace, kdy zmizí také některé reference, které se odregistrují během rušení objektů destruktory. Je na diskuzi, zda-li na tuto situaci reagovat opakováním "collect". Má verze to dělá, s tím, že případě, lze tuto funkcionalitu vypnout. Je to zejména z toho důvodu, aby například uvolňování dlouhých spojových seznamů nebyla dlouhotrvající operace. Když si představíme, že s každým provedením "collect" zmizí jeden objekt, pakliže má spojový seznam několik tisíc objektů, teoreticky by uvolnění všech objektů trvalo 1000x collect. Pokud přitom collect voláme jen občas, hromadně, třeba jednou za 5 sekund, paměť po spojovém seznamu by se uvolnila za 5000sec. Proto se po uvolnění několika objektů provádí opakovaný "collect", a to proto, aby se zpracovala paměť, která se ocitla bez referencí po uvolnění některých objektů.

Collect má tedy tři vnořené cykly

  1. Nejvnitřnější cyklus zpracování jednoho objektu
  2. Prostřední cyklus zpracování všech označených objektů
  3. Vnější cyklus zpracování veškerých uvolněných objektů nereferencovaných objektů vzniklých během bodu 2.

Příště

Aby článek nebyl moc dlouhý, rozdělím jej do více částí. V další části si popíšeme API celého GC a v poslední části se podíváme na MT řešení s použitím extra vlákna pro GC.

Pro zájemce, zdrojáky ke GC lze stáhnout pomocí Subversion na adrese:

http://light-speed.svn.sourceforge.net/svnroot/light-speed/branches/devel/lightspeed/gc (subversion!!)

(podotýkám, že projekt je závislý na lightspeed/base, jehož složku najdete o adresář výše)

vytvořeno: 30.12.2008 23:31:15, změněno: 30.12.2008 23:48:38
Jsou informace v článku pro Vás užitečné?
  • (2)
  • (4)
  • (1)
  • (0)
  • (1)
Nick nebo OpenID
Vzkaz
 
25.7.2016 18:15:11

hUPP6juPn5R

Een producer die een muzikant verbied om een drtiaprumj opnieuw te spelen omdat er een fout in zat dat hoor je niet vaak. Blijkbaar was het geen storende fout in het nummer

Podobné články

Garbage collector v C++ - Popis API tříd kolekce LightSpeed::GC

V tomto článku si představíme rozhrani Garbage Collectoru v knihovně LightSpeed. Princip GC byl přidstaven v předchozím díle

GarbageCollector v C++, prototyp

Neustále slýchám, jak v C++ chybí Garbage Collector. Ač si o tomto nástroji myslím své, a v zásadě jsem proti zavedení GC v C++, přijal jsem tyto nářky jako výzvu.

Jak sdílet prostředky (resources) v C++

Nemnohokrát jsem řešil v programech psaných v C++, jak sdílet prostředky (resources), jinými slovy, jak zajistit, že jedinečné prostředky budou uvolňovány až v okamžiku, kdy je nikdo nepotřebuje. Podívejme se na jednoduché řešení.

Úvod do obecného OOP 2. díl

V tomto díle prozkoumáme život objektů

Jak na destruktory v Javě

Chybí vám destruktor v Javě. Úplně jej nahradit neumíme, ale jisté řešení by se našlo
Reklama: