Википедија

Sakupljanje smeća (računarstvo)

U računarstvu, sakupljanje smeća (SS) je forma automatskog upravljanja memorijom. Sakupljač smeća, ili samo sakupljač, pokušava da pokupi smeće, ili memoriju okupiranu objektima koje program više ne koristi. Sakupljač smeća je patentiran od strane Džona Makartnija, negde oko 1959. godine za apstraktno upravljanje memorijom u Lispu.[1][2]

Sakupljanje smeća je češće predstavljeno kao suprotnost manuelnog upravljanja memorijom, koje zahteva od programera da odredi koje objekte da delocira i vrati u memorijski sistem. Međutim, mnogi sistemi koriste kombinaciju pristupa, uključujući druge tehnike kao što je alokacija jezgra i pristup regiona. Kao i druge tehnike upravljanja memorijom, sakupljanje smeća može predstavljati značajan deo ukupne obrade vremena u programu i, kao rezultat,  može imati značajan uticaj na performanse.

Resursi različiti od memorije, kao što je internet soket, upravljanje bazom podataka, korisnički interakcijski prozor, i fajl i deskriptori uređaja, nisu tipično upravljivi uz pomoć sakupljača smeća. Metode korišćene za upravljanje takvim resursima, posebno destruktorima, mogu dovoljno dobro da upravljaju memorijom, čineći sakupljanje smeća nepotrebnim. Neki sistemi sakupljanja smeća dozvoljavaju da drugi resursi budu povezani sa memorijskom regijom, kada se skupe, uzroci drugih izvora mogu biti vraćeni; ovo se naziva finalizacija. Finalizacija može dovesti do komplikacija između ograničavanja svoje korisnosti, kao što je nepodnošljivo kašnjenje između neupotrebe i vraćanja posebno ograničenih resursa, ili nedostatak kontrole nad kojim nit obavlja posao vraćanja.

Principi

uredi

Osnovni principi sakupljača smeća jesu da se nađe podatak objekta u programu koji se ne može pokrenuti, i vratiti resurs korišćen od strane tih objekta.

Mnoštvo programskih jezika zahteva sakupljače smeća, kao deo programske specifikacije (na primer, Java, C#, D program, Gou i mnoštvo skript programa) ili efektivno za praktičnu implementaciju (npr. , formalni programi kao lambda račun); za njih se kaže da su programi za sakupljanje smeća. Drugi programi su dizajnirani za upotrebu sa maunelnim upravljanjem memorije, ali imaju implementaciju sakupljanja smeća  (npr. C i C++). Neki programi, kao Ada, Modula-3, i C++/CLI, dozvoljava i sakupljanje smeća i manuelno upravljanje memorijom da koegzistiraju u istoj aplikaciji koristeći odvojene strukture podataka za sakupljene i manuelno upravljive objekte; neki programi, kao D, imaju sakupljača smeća ali dozvoljavaju korisniku da manuelno obriše objekte i potpuno isključi sakupljanje smeća kada je brzina potrebna.

Dok integracija sakupljača smeća u kompilatoru programskih jezika i sistemu izvršavanja omogućava mnoštvo metoda ,posle-hoka sistemi sakupljača smeća postoje, kao APB (automatski pristup brojaču), i imaju neke nepotrebne rekompilacije . (Post-hok sakupljač smeća je ponekad označen kao kolekcija đubriva.) sakupljač smeća će skoro uvek biti blisko integrisan sa memorijom alokatora.

Prednosti

uredi

Sakupljanje smeća oslobađa programera od manuelnog slaganja sa memorijskom delokacijom. Kao rezultat, određene kategorije bagova su eleminisane ili znatno redukovane:

  • Apsolutni pokazivač bagova, koji se javljaju kada je deo memorije slobodan dok su pokazivači i dalje tu, a jedan od tih pokaziača je neadresiran. Do tada memorija se može koristiti u neke druge svrhe, sa nepredvidivim rezultatima.
  • Dvostruko slobodni bagovi, koji se javljaju kada program pokušava da se oslobodi dela memorije koja je već oslobođena, i možda ponovo podeljena.
  • Određene vrste memorijskih rupa (pukotina), u kojim program neuspešno pokušava da oslobodi memoriju okupiranu od strane objekata koji su postali nedostupni, mogu dovesti do memorijskog izvršavanja. (Smeće se obično ne dovodi u vezu sa neograničenom akumulaciojm podataka (podaci koji su dostupni), ali to zapravno neće biti korišćeno od strane programa.)
  • Efikasne implementacije stalnih struktura podataka.

Neki od bagova, koji su adresirani od strane sakupljača smeća, mogu imati bezbednosne komplikacije.

Mane

uredi

Sakupljanje smeća ima i neke nedostatke, uključujući korišćenje dodatnih sredstava, uticaj performansi, moguća ograničenja u izvršavanju prorama, i neusaglašenost sa manuelnim upravljanjem resursa.

Sakupljač smeća troši računarske resurse u odlučivanju koji deo memorije da oslobodi, čak i ako je programer već znao ovu informaciju. Posledica za ne obeležavanje roka trajanja objekata je ta da je manuelno izvorni kod u stvari višak , što može dovesto do smanjenja ili neujednačenosti performansi.[3] "Vršnjak" magazin je došao da rešenja da sakupljanje smeća treba 5 puta memoriju da kompenzuje za prostor iznad i da se izvrši onoliko brzo koliko dozvoljava eksplicitno upravljanje memorijskim menadžmentom. [4] Interakcija sa memorijsko-hijerarhijskim efektima može učiniti prostor iznad nedopustivim u okolnostima koje je teško predvideti ili detektovati u rutinskom testiranju. Uticaj na performanse je naveo Epl da ne ugradi sakupljanje smeća u iOS uprkos tome što je to najželjenija karakteristika.[5]

Momenat kada je otpad sakupljen, može biti nepredvidiv, rezultirajući to u vidu ograničenja (pauze u promeni, slobodna memorija). Nepredviđena ograničenja mogu biti neprihvatljiva u realnom-vremenskom okruženju, u transakcijskom procesuiranju, ili ieaktivnim programima. Rastući, istovremeni, sakupljači smeća koji rade u realnom vremenu, rešavaju ove probleme različitim metodama.

Moderne implementacije sakupljača smeća pokušavaju da izbegnu blokiranje zaustavi svet ograničenja, radeći što više u pozadini, npr. označavanje nedostupnih instanci otpada dok aplikacioni proces nastavlja da radi. Uprkos ovim dostignućima, na primer u .NET CLR paradigmi je i dalje veoma teško održavanje velikog broja objekata (milioni objekata) sa rezidentnim objektima koji su promovisani u starije generacije bez zapa stvaranja zapaženijih kašnjenja (ponekad traje nekoliko sekundi).

Nedeterminističko sakupljanje smeća je nespojivo sa RAII (RAII) kojem je upravljanje bazirano na nesakupljene resurse. Kao rezultat, potreba za eksplicitnnim manuelnim upravljanjem resursa (osloboditi/zatvoriti) za ne sakupljene resurse, postaje prenosan na kompoziciju. To je: u ne-determinističkim sistemima sakuljpača smeća, ako resurs ili resurs kao objekat zahteva manuelno upravljanje resursima (osloboditi/zatvoriti), i ovaj objekat je korišćen kao deo drugog objekta, zatim taj sastavljen objekat će postati resur kao objekat koji zahteva manuelno upravljanje memorijom.

Putanja sakpuljača smeća

uredi

Putanja sakupljanja smeća je najčešći tip sakupljanja smeća, toliko da se sakupljanje smeća često odnosi na putanju sakupljanja smeća, češće nego ostale metode kao što je referentno brojanje. Celokupna strategija se statoji od određovanja koje bi objekte trebalo sakupiti uz pomoć sakupljača smeća prateći koji su objekti dostupni od strane lanca referenci iz pojedinih korena objekata, a ostatak smatrajući smećem i pokupiti ga. Međutim, postoje ogromni brojevi algoritama korišćenih u implementaciji, sa širokom različitom kompleksnošću i performansnim karakteristikama.

Referentno brojanje

uredi

Referentno brojanje je forma sakupljanja smeća pri čemu svaki objekat ima brojač broja referenci na njega. Smeće je identifikovano uz pomoć brojanja nulte reference. Brojač reference objekata se povećava kada se kreira referenca na njega, a smanjuje kada se referenca uništi. Kada brojač dostigne nulu, memorija objekata se vraća.

Kao kod manuelnog upravljanja memorijom, a za raziliku od praćenja sakupljanja smeća, referentno brojanje garantuje to da objekti budu uništeni ubrzo nakon što njihove poslednje reference budu uništene, a obično pristupa memoriji koja je smeštena u CPU, u objekte koji su oslobođeni, ili direktno uperene u one, i na taj način nema značajne negativne efekte na CPU skladište i virtualnu memoriju.

Postoji nekoliko mana referentnog brojanja; ovo se generalno može rešiti ili ublažiti uz pomoć više sofisticiranih algoritama:

Ciklusi
Ako se dva ili više objekta odnose jedan prema drugome, oni mogu da kreiraju ciklus kojim ništa neće biti sakupljeno tako što njihove zajedničke reference neće dopustiti njihovim referencama da brojač dođe do nule. Neki sistemi sakupljača smeća koriste referentno brojanje (kao u CPython-u) koristeći specifične algoritme detektovanja ciklusa koji se poklapaju sa ovim ishodom.[6] Drugi način je korišćenje slabih referenci za "reindikatore" koji kreiraju ciklus. Ispod referentnog brojanja, slaba referena je slična slaboj referenci ispod putanje sakupljača smeća. To je specijalni referentni objekat čija postojanost ne uvećava referentni brojač referentnog objekta. Osim toga, slaba referenca je sigurna kada referentni objekat postane smeće, bilo koja slaba referenca u tom slučaju je greška, umesto da bude apsolutno dozvoljena za preostale, tj. da se pretvori u predvidivu vrednost, kao što je nulta referenca.
Prostor iznad (referentno brojanje)
Referentno brojanje zahteva prostor za raspodelu skladištenja objekta njegovog referentnog brojača. Brojač može biti sačuvan uporedno u memoriji objekta ili u nekom drugom delu, ali u svakom slučaju, svaka pojedinačno izbrojana referenca objekta zahteva dodatnu memoriju za referentni brojač. Memorijski prostor sa nepriključenim indikatorom je često korišćen za ovaj slučaj, misleći da 32-bitni ili 64-bitni referentni brojači moraju biti raspodeljeni na svaki objekat.
Na nekim sistemima je moguće smanjiti prosto iznad koristeći tagovane indikatore da sačuvaju referentni brojač u nekorišćenim delovima memorije objekta. Često, arhitektura ne dozvoljava programima da 100% pristupe adresi memorija koja bi se mogla sačuvati u svom prirodnom indikatori; određeni broj visokih bajtova u adresi je neprimetno ili označeno nulom. Ako se pouzdano zna da objekat ima indikator na određenoj lokaciji, referentno brojanje može biti sačuvano u nekorišćenim bajtovima indikatora. Na primer, svaki objekat u Objektiv-C-u ima indikatora svojeklase na početku svoje memorije; na ARM arhitekturi korišćenoj u iOS 7, 19 nekorišćenih bajtova te klase indikatora je iskorišćeno da sačuva referentni brojač objekata.
[7][8]
Brzina prostora iznad (rast/opadanje)
U nepogodnim implementacijama, svaki prenos referenci i svako izdvajanje referenci iz delokruga često zahteva modifikacije jednog ili više referentnih brojača. Međutim, u očekivanom slučaju kada je referenca kopirana od pormenljive (koja je izvan delokruga) u promenljivu (koje je u okviru delokruga) tako da je životni vek trajanja promenljive unutar delokruga ograničen životnim vekom trajanja promenljive koja je izvan delokruga, rast reference može biti eleminisana. Promenljive izvan delokruga "poseduju" reference. U programskom jeziku C++, ova tehnika je ubačena i demonstrirana korišćenjem const  referenci.
Referentni brojač u C ++ je obično ubačen koristeći "pametne indikatore" kojim konstrukotri, destruktori i zadati operatori upravljaju uz pomoć referenci. Pametan indikator se može preći preko reference do funkcije, koja izbegava potrebu da bude kopirana-konstrukcija novoh pametnijeg indikatora (koji bi povećao referentni brojač u ulasku u funkciju a smanjio na izlasku). Umesto toga, funkcija dobija referencu sa pametnim indikatorom koji je jeftino proizveden.
Potrebna valentnost
Kada se koristi u višenitnom okruženju, ove modifikacije (rast i opadanje) mogu biti potrebne za valentne operacije kao što je uporedi-i-razmeni, najmanje za bilo koji objekat koji je dostupan ili potencijalno dostupan među više niti. Valentne operacije su skupe na multiprocesoru, a još su skuplje ako moraju da budu slični sa softverskim algoritmima. Moguće je izbeći ovaj problem dodajući po-navoju ili po-CPU referentne brojače i jedini pristup globalnom referentnom brojaču kada lokalni referentni brojač postane ili nije više nula (ili, drugačije, koristeći binarno stablo referetnih brojača, ili dati determinističku destrukciju u zaemnu za ne dobijanje globalnog referentnog brojača), ali ovo dodaje značajnu memoriju iznad i na taj način teži da bude korisno samo u specijalnim slučajevima (koristi se, npr. u referentnom brojaču Linuksovog jezgra modula).
Nerealno vreme
Nepraktične implementacije referentnog brojača generalno nemaju ponašanje realnog vremena, zato što bilo koji preneseni indikator može potencijalno izazvati ograničeni broj objekata od strane raspodeljene veličine memorije koja je rekurzivno oslobođena dok nit ne može da obavlja druge poslove. Moguće je izbeći ovaj problem uz pomoć delegiranja slobodnih objekata čiji se referentni brojači odbacuju tj. izjednačavaju se sa nulom za ostale navoje, na trošku "prostora iznad".

Izbegavanje analize

uredi

Izbegavanje analize se može koristiti za pretvaranje gomile raspodela u ograničene raspodele, smanjujući iznos potrebnog posla koji će biti odrađen od strane sakupljača smeća. Ovo je urađeno koristeći analizu izvršavanja vremena da bi se odredio raspodeljeni objekat bez funkcije, koji nije pristupačan izvan toga (izbegavanje), na druge funkcije ili teme. U takvom slučaju objekat se može raspodeliti direktno na povezana ograničenja i osloboditi kada se funkcija vrati, smanjujuči potencijalnu grešku sakupljača smeća.

Vreme izvršavanja

uredi

Vreme izvršavanja sakupljanja otpadaka je forma statičke analite koja dozvoljava memoriji da se ponovo koristi i bude vraćena bazirano na poznate invarijante tokom kompilacije. Ova forma sakupljanja smeća je proučavana u Merkurijevom programskom jeziku,[9] i pokazao se efikasnijim sa uvođenjem VMNR automatski brojač referenci (ABC)u Eplov ekosistem (iOS i OS X) u 2011.[10][11][12]

Dostupnost

uredi

Generalno, programski jezici visokog nivoa bi trebalo da imaju sakupljanje smeća kao standardnu odliku. U programima koji nemaju ugrađeno sakupljanje smeća, ono se može dodati kroz biblioteku, kao što je slučaj sa Boemov sakupljač smeća za C (za "skoro sve programe") i C++. Ovaj pristup ima greške, kao što je menjanje kreiranja objekta i uništavanje mehanizma.

Najfunkcionalniji programski jezici kao što su ML (ML), Haskel (Haskell) i APL(APL), imaju ugrađeno sakupljanje smeća. Lisp je posebno značajan kao prvi funkcionalni programski jezik i kao prvi programski jezik koji je uveo sakupljanje smeća.

Ostali dinamički programi, kao što je Rubi (ali ne i Perl 5 ili PHP pre verzije 5.3,[13] koji koriste referentno brojanje), takođe koriste sakupač smeća. Objektno orijentisani programi kao što su Smalltalk, Java i ECMASkript obično pružaju integrisano sakupljanje smeća. Izuzeci su C++ i Delfi koji imaju destruktore.

Bejsik (BASIC)

uredi

Istorijski gledano, programi namenjeni za početnike, kao što su Bejsik i Logo, su češće koristili sakupljanje smeća za gomilu-alociranih promenivih-dužina tipova podataka, kao što su stringovi i liste, tako da ne opterećuje programere sa manuelnim upravljanjem memorije. Na prvim mikrokompijuterima, sa njihovom limitiranom memorijom i sporim procesorom, Bejsikov sakupljač smeća je mogao često da izazove nasumično, neobjašnjive pauze usred izvršavanja programa.

Neki Bejsikomovi interpretatori, kao što je Eplsoft BEJSIK iz Epl 2 familije, su u više navrata skenirali stringove deskriptore za string koji ima najveću adresu da bi bio kompaktan u odnosu na visoku memoriju, dajući  Veliko O performansu, koja može da proizvede pauze od nekoliko minuta u toku izvršavanja intezivnih programa. Izmenjeni sakupljač smeća za Eplsoft BEJSIK predstavljen u Zovi-EPL (Januar 1981, 40-45 strana, Rendi Viginton) je identifikovao grupu stringova u svakom prelazu preko gomile, što smanjuje dramatično vreme sakupljanja. BEJSIK. Sistem, izašao 1983 u ProDOS-u, sadrži prozorski sakupljač smeća za BEJSIK koji uprošćava mnoštvo sakupljanja u frakciji sekunde. 

Objektiv-C

uredi

Dok Objektiv-C tradicionalno nije imao sakupljanje smeća, sa izlazom OS X 10.5 u 2007. godini Apple Inc. je uveo sakupljanje smeća za Objektiv-C 2.0, koristeći  razvijeni brzi sakupljač.[14] Međutim, u 2012, sa izlaskom OS X 10.8, sakupljanje smeća je zastarelo u korist LLVM-ovog automatskog pristupa brojača (APB) koji je uveden sa OS X 10.7.[15] Osim toga, od maja 2015, Epl zabranjuje korišćenje sakupljanja smeća za nove OS X aplikacije u Epl prodavnici.[12][16] U iOS-u, sakupljnje smeća se nikada nije koristilo za probleme u performansama aplikacije; umesto, iOS-a koristi se APB.[10]

Ograničena okruženja

uredi

Sakupljanje smeća je retko korišćeno na ugrađene sisteme ili sisteme u realnom vremenu zbog stroge potrebe za uskom kontrolom preko korišćenja limitiranih resursa. Međutim, sakupljači smeća su kompatibilni sa limitiranim okruženjima i tako su se razvijali.[17] Majkrosoftov. NET Mikro frejmvork i Java Platforma, Mikro edicija su ugrađene softverske platforme tako da sadrže sakupljače smeća, kao i njihovi rođaci.

Vidi još

uredi

Reference

uredi
  1. ^ "Recursive functions of symbolic expressions and their computation by machine, Part I".
  2. ^ "Recursive functions of symbolic expressions and their computation by machine, Part I" Arhivirano na sajtu Wayback Machine (4. oktobar 2013).
  3. ^ Zorn, Benjamin (1993-01-22).
  4. ^ Matthew Hertz, Emery D. Berger (2005).
  5. ^ "Developer Tools Kickoff - session 300" (PDF).
  6. ^ "Reference Counts".
  7. ^ Mike Ash.
  8. ^ "Hamster Emporium: [objc explain]: Non-pointer isa".
  9. ^ Mazur, Nancy (May 2004).
  10. ^ a b Napier & Kumar 2012, str. 83.
  11. ^ Cruz, José R.C. (2012-05-22).
  12. ^ a b Apple says Mac app makers must transition to ARC memory management by May by AppleInsider (February 20, 2015)
  13. ^ "PHP: Performance Considerations". php.net.
  14. ^ Apple Computer, Inc. „Objective-C 2.0 Overview”. Arhivirano iz originala 24. 07. 2010. g. Pristupljeno 5. 1. 2016. 
  15. ^ Mac OS X 10.7 Lion: the Ars Technica review John Siracusa (20 Juli 2011)
  16. ^ Cichon, Waldemar (2015-02-21).
  17. ^ "Wei Fu and Carl Hauser, "A Real-Time Garbage Collection Framework for Embedded Systems".

Literatura

uredi
Preuzeto iz „https://sr.wiki.x.io/w/index.php?title=Сакупљање_смећа_(рачунарство)&oldid=27438640”