Skupljaci otpada Flashcards
Zasto uvodimo garbage collector?
Na nekim nivoima programiranje je suvisno i moze da dovodi do raznoraznih bagova, kao i nepogodnosti alokacije memorije na hipu.Oni rade automatski u haskellu
Brojanje referenci
Ova metoda radi tako sto broji koliko stvari pokazuje na neki objekat pomocu brojaca referenci. Ako na objekat nista ne pokazuje, da li mozemo njemu da pristupimo? Odgovor je ne i zato zelimo da ga obrisemo. Svako kopiranje objekta je samo povecanje referenci na taj objekat.
Prednosti:
1. Determinizam - U trenutku kada niko ne koristi objekat, on biva unisten.
2. Efikasnost - Efikasne su operacije
3. Memorijska lokalnost - Brojaci se pamte zajendo sa objektom
Mane:
- Ciklicne strukture
- Mutibalne strukture i sve operacije su mutabilne - narusava koncept imutabilnosti
- Fragmentacija memorije
- Nemamo kontrolu - Objekat se unistava u trenutku kada nista ne pokazuje na njega. To moze da dovede do lancanog unistavanja objekta sto moze da uspori neki kritican deo programa.
- Nije sakupljac podataka - Posto se objekat odmah brise cim nista ne pokazuje na njega, onda taj objekat nije ni djubre
Autowrite Memory Managment
Najjednostavniji nacin baratanja memorijom, imamo “live” memoriju i “garbage” memoriju
- “live” - imamo pokazivac iz programa na nju
- “garbage” - memorija koja je zauzata a necemo je nikada koristiti
Brojac referenci je jedna od nih.
Optimizovani brojac referenci
Korititi obican brojac referenci uz sledece dodatke:
- Odlozeno azuriranje brojaca
- Spajanje uzastopnih promena brojaca
- Baferovanje uzastopnih promena brojaca
Ako u nekom cvoru brojac referenci za objekat postane 0, ne unistavamo i taj objekat postaje “garbage”. Time brojac referenci postaje garbage collector
Mark and Sweep
Ovaj aparat brlise djubre iz 2 koraka:
1. Sakupljamo sve pokazivace sa steka koji formiraju neki graf i obilazimo ga gde u svakom cvoru obelezavamo objekte na hipu, jer su inicijalno neobelezeni. Svi elemneti koji ostanu neobelezeni po definiciji su djubre. Ovo je “mark” korak.
- Prolazimo kroz objekte na hipu i brisemo ih ako nisu markirani. Ovaj korak se naziva “sweep”
Ne mozemo da znamo da li je nesto djubre na steku ali mozemo da znamo da li je nesto djubre na hipu. Stek sam cisti svoje djubre
Prednosti:
- radi sa ciklusima
- Jeftino kopiranje, ne usporava program
- Ne usporava program kada objekat postane djubre
Mane:
- “Stop the world” - U trenutku kada brisemo djubre, zelimo da odrzimo konzistentnost. Ako brisemo djubre u realnom vremenu, mozemo da izgubimo njihove pokazivace na druge objekte. Zato moramo da zamrznemo svet, i da obrisemo sve djubre pre nastavka programa. Brisanje se najcesce primenjuje kada ponestane slobodne memorije
- Lokalnost memorije i fragmentacija
Izgubili smo determinizam a dobili smo efikasnost. U svakom trenutku imamo promenu u kesu, jer svaki put proveravamo objekat na drugoj memorijskoj lokaciji
Time: O(m) - mark deo , O(m+n) - sweep deo
m- live memorija , n - garbage memorija
Mark and Compact
Modifikacija Mark-and-Sweep algoritma, ideja je da se resimo fregmentacije memorije na hipu time sto radimo compact korak nakom sweep koraka. Ideja je da memoriju na hipu spojimo tako da ne bude “rupa”
Kako vrsimo ovaj proces? Radimo “sliding” objekata i time mozemo a i ne moramo da cuvamo poredak. Kada nam poredak nije bitan, mozemo da ubacujemo objekat u slobodan prostor izmedju 2 prethodna objekta, sto je efikasnije. Posle ovoga imamo malu fregmentaciju i lokalizovana je. Ovo je veoma skupa operacija za sakupljanje djubreta
Two finger compaction
Particionisanjem sa dva pokazivaca (pocetak/ kraj), ova metoda je pogodna za objekte iste velicine
Kopirajuci sakupljac djubreta
Ovom metodom svaki put kopiramo sve. Razdvajamo memoriju na 2 dela, “fromspace” i “tospace”, na kraju obrcemo fromspace i tospace.
Obilazimo sve objekte, samo sto umesto obelezeavanja kao u “mark” koraku prebacujemo ih sve u drugi deo.
Smenjujemo “sweep” deo, jer ne moramo da obilazimo kroz sve objekte na hipu. Dosta efikasna tehnika za programe koji imaju mnogo djubreta a malo podataka.
Prednosti:
- Lokalnost
- Jednostavno skupljanje objekata
- Brza alokacija
- Mala fregmentacija
Mana:
-duplo manja memorija
- kopiranje podataka
- Kopiranje velikih i trajnih objekata
Generacijski sakupljac djubreta
Ovaj sakupljac radi na sledecim pretpostavkama:
- Najmladji objekti, koji su skoro alocirani, imaju veliku sansu da budu unisteni
- Mali objekti se cesce unistavaju. Ako imamo program koji konstantno alocira i brise velike objekte onda nesto ne sljaka.
Kako ovo radi?
Vrsimo Mark-and-Sweep i cuvamo brojac za svaki objekat koji oznacava koliko generacija je preziveli. Kada brojac dostigne odredjenu generaciju vrsimo prebacivanje. Opet cuvamo privremeni forward pokazivac do sledeceg “marka”, kada se pokazivaci azuriraju. Najstariji objekti su oni koji su opstali najvise generacija.
Generalni problem sa GC je sto svakako trose procesorsko vreme. Svi prethodni algoritmi zauzimaju svet da bi mogli da prociste djubre. Uvek je jeftinije ne raditi nista, ako nije potrebno da se rad. Bolje resenje od GC-a ke da imamo sistem koji ne zahteva ciscenje preko njih. Jedna od alternativa je sledeca metoda.
Linearni tipvi
Ova metoda se zasniva na pretpostavci da vrednost sme samo jednom da se iskoristi.Nema potrebe za brojanje referenci ili GC-a. Ovde nije dozvoljeno kopiranje jer deterministicki unistavamo podatke.
