27.Garbagecollec.onAA2016-2017
1
Ges,onedellamemoria
Sta,careao dimensionefissa,contenu,determina,ealloca,acompilazione
Run-,mestacko dimensionevariabile(recordaBvazione)o ges,onesoEoprogrammi Heapo dimensionefissa/variabileo supportoallaallocazionedioggeBestruEureda,dinamiche! mallocinC,newinJava
2
Allocazionesta,ca
En,tàchehaunindirizzoassolutocheèmantenutopertuEal’esecuzionedelprogramma Solitamentesonoalloca,sta,camenteo variabiliglobalio variabililocalisoEoprogrammi(senzaricorsione)o costan,determinabiliatempodicompilazioneo tabelleusatedalsupportoarun-,me(pertypechecking,garbagecollec,on,ecc.)
SpessousateinzoneproteEedimemoria
3
Allocazionesta,capersoEoprogrammi
Registri salvati
Informazione debugging
Spesso nei registri
4
Allocazionedinamica:pila
PerogniistanzadiunsoEoprogrammaarun-,meabbiamounrecorddiaBvazionecontenenteleinformazionirela,veataleistanza Analogamente,ognibloccohaunsuorecorddiaBvazione(piùsemplice) Ancheinunlinguaggiosenzaricorsionepuòessereu,leusarelapilaperrisparmiarememoria...
5
Allocazionedinamicaconheap
Heap:regionedimemoriaicuiblocchidimemoriapossonoesserealloca,edealloca,inmomen,arbitrari
NecessarioquandoillinguaggiopermeEeo allocazioneesplicitadimemoriaarun-,meo oggeBdidimensionivariabilio oggeBconvitanonLIFO
Lages,onedelloheapnonèbanaleo ges,oneefficientedellospazio:frammentazioneo velocitàdiaccesso
6
Heap:blocchididimensionefissa
7
Heapsuddivisoinblocchididimensionefissa(abbastanzalimitata).Inizialmente:tuAiblocchicollega.nellalistalibera
Heap:blocchididimensionefissa
8
Allocazionediunoopiùblocchicon.guiDeallocazione:res.tuzioneallalistalibera
Heap:blocchididimensionevariabile
Inizialmenteunicoblocconelloheap Allocazione:determinazionediunbloccoliberodelladimensioneopportuna Deallocazione:res,tuzioneallalistalibera
Problemi:o leoperazionidevonoessereefficien,o evitarelosprecodimemoria
! frammentazioneinterna! frammentazioneesterna
9
Frammentazione
Frammentazioneinternao lospaziorichiestoèXo vieneallocatounbloccodi
dimensioneY>X
o lospazioY-Xèsprecato Frammentazioneesternao cisarebbelospazio
necessariomaèinusabileperchésuddivisoin“pezzi”troppopiccoli
10
Ges,onedellalistalibera
Inizialmenteunsoloblocco,delladimensionedelloheap Adognirichiestadiallocazionecercabloccodidimensioneopportunao firstfit:primobloccograndeabbastanzao bestfit:quellodidimensionepiùpiccola,grandeabbastanza
Seilbloccosceltoèmoltopiùgrandediquellocheservevienedivisoindueelaparteinu,lizzataèaggiuntaallaLL
Quandounbloccoède-allocato,vieneres,tuitoallaLL(seunbloccoadiacenteèliberoidueblocchisono``fusi’’inununicoblocco)
11
Ges,oneheap
FirstfitoBestfit?SolitasituazioneconfliEuale…o Firstfit:piùveloce,occupazionememoriapeggiore
o Bestfit:piùlento,occupazionememoriamigliore
ConunicaLLcostoallocazionelinearenelnumerodiblocchiliberi Permigliorarelisteliberemul,ple:laripar,zionedeiblocchifralevarielistepuòessere
! sta,ca! dinamica
12
Problema:iden,ficazionedeiblocchidade-allocare
NellaLLvannoreinseri,iblocchidade-allocare Comevengonoindividua,?o linguaggiconde-allocazioneesplicita(,pofree):seppuntaastruEurada,,freepde-allocalamemoriachecon,enelastruEura
o linguaggisenzade-allocazioneesplicita:unaporzionedimemoriaèrecuperabilesenonèpiùraggiungibile“innessunmodo”
Ilprimomeccanismoèpiùsemplice,malascialaresponsabilitàalprogrammatore,epuòcausareerrori(danglingpointer) Ilsecondomeccanismorichiedeunopportunomodellodellamemoriaperdefinire“raggiungibilità”
13
Ges,onememoria
I“moderni”linguaggidiprogrammazioneassumonounmodellodiges,oneautoma,cadellamemoriaaheapEsempio(daOCAML)o letrecappendxy=ifx=[]theny
elsehdx::append(tlx)yletrecrevls=ifls=[]then[] elseappend(rev(tlls))[hdls]
o Assumiamochelength(ls)=10,cosasuccedequandorev(ls)èinvocata?
14
Modelloagrafodellamemoria
Ènecessariodeterminareilrootset,cioèl’insiemedeida,sicuramente“aBvi”o Javarootset=variabilista,che+variabileallocatesulrun-,mestack
PerognistruEurada,allocata(nellostackenelloheap)occorresaperedovecipossonoesserepuntatoriaelemen,delloheap(informazionepresenteneitypedescriptor) Reachableac2vedata:lachiusuratransi,vadelgrafoapar,redalleradici,cioètuBida,raggiungibiliancheindireEamentedalrootsetseguendoipuntatori
15
Celle,“liveness”,blocchiegarbage
Cella=bloccodimemoriasulloheap UnacellavienedeEaliveseilsuoindirizzoèmemorizzatoinunaradiceoinunaaltracellaliveo quindi:unacellaèliveseesoloseappar,eneaiReachableac)vedata
Unacellaègarbagesenonèlive Garbagecollec,on(GC):aBvitàdiges,onedellamemoriadinamicaconsistentenell’individuarelecellegarbage(o“ilgarbage”)erenderleriu,lizzabili,peres.inserendolenellaListaLibera16
Garbageedanglingreference
classnode{intvalue;nodenext;
}nodep,q;
17
p=newnode();q=newnode();q=p;freep;
Dangling reference
garbage
GC:perchéèinteressante?
Applicazionimodernesembranononaverelimi,allospaziodimemoriao 4GBlaptop,8GBdesktop,8-512GBservero spaziodiindirizzia64-bit Mal’usoscorreEofaemergereproblemicomeo memoryleak,danglingreference,nullpointerdereferencing,heapfragmenta,on
o problemidiinterazioneconcachingepaginazione Lages.onedellamemoriaesplicitaviolailprincipiodell’astrazionedeilinguaggidiprogrammazione
18
GCeastrazionilinguis,che
GCnonèunaastrazionelinguis,ca GCèunacomponentedellamacchinavirtualeo VMdiLisp,Scheme,Prolog,Smalltalk…o VMdiCandC++nonloavevanomalibreriedigarbagecollec,onsonostateintrodoEeperC/C++
Sviluppirecen,delGCo linguaggiOO:Modula-3,Java,C#o linguaggiFunzionali:ML,Haskell,F#
19
IlgarbagecollectorperfeEo
NessunimpaEovisibilesull’esecuzionedeiprogrammi Operasuogni,podiprogrammaesuogni,podistruEurada,dinamica(esempio:struEurecicliche)Individuailgarbage(esolamenteilgarbage)inmodoefficienteeveloceNessunoverheadsullages,onedellamemoriacomplessiva(cachingepaginazione)Ges,oneheapefficiente(nessunproblemadiframmentazione)
20
QualisonoletecnichediGC?
Referencecoun.ng–Contatoridiriferimentoo ges,onedireEadellecelleliveo lages,oneèassociataallafasediallocazionedellamemoriadinamica
o nonhabisognodideterminarelamemoriagarbage Tracing:iden,ficalecellechesonodiventategarbageo mark-sweepo copycollec.onTecnicaup-to-date:genera.onalGC
21
Referencecoun,ng
Aggiungereuncontatorediriferimen,allacelle(numerodicamminidiaccessoaBviversolacella) Overheaddiges,oneo spaziopericontatoridiriferimentoo operazionichemodificanoipuntatoririchiedonoincrementoodecrementodelvaloredelcontatore.
o ges,one“real-,me” Unix(filesystem)usalatecnicadeireferencecountperlages,onedeifile JavaperlaRemoteMethodInvoca,on(RMI) C++“smartpointer”
22
Referencecoun,ng
Integeri=newInteger(10);o RC(i)=1.
j=k;(j,kriferisconoaoggeB)o RC(j)--.o RC(k)++.
23
Referencecoun,ng:esempio
24
1 root set
Heap space
2
1 1 1
1 1 2
Referencecoun,ng:caraEeris,che
Incrementaleo lages,onedellamemoriaèamalgamatadireEamenteconleoperazionidelleprimi,velinguis,che
Faciledaimplementare Coesisteconlages,onedellamemoriaesplicitadaprogramma(esempiomallocefree) Riusodellecellelibereimmediatoo if(RC==0)then<res,tuirelacellaallalistalibera>
25
Referencecoun,ng:limitazioni
Overheadspaziotempoo spazioperilcontatoreo lamodificadiunpuntatorerichiedediverseoperazioni
MancataesecuzionediunaoperazionesulvalorediRCpuògeneraregarbage Nonperme6ediges2restru6ureda2concicliinterni
26
Referencecoun,ng:cicli
27
1 root set
Heap space
1
1 1 1
1 1 2 memoryleak
“Smartpointer”(C++)
28
T* obj: int cnt: 2
object of type T
RefObj<T> *ref
RefObj<T> Ref<T>
RefObj<T> *ref
x
y
sizeof(RefObj<T>) = 8 byte per reference-counter dell’oggetto sizeof(Ref<T>) = 4 byte
• un normale puntatore
mark-sweep
Ognicellaprevedespazioperunbitdimarcatura Garbagepuòesseregeneratodalprogramma(nonsonoprevis,interven,preven,vi)L’aBvazionedelGCcausalasospensionedelprogrammainesecuzione Markingo sipartedalrootsetesimarcanolecellelive Sweepo tuEelecellenonmarcatesonogarbageesonores,tuiteallalistalibera.
o resetdelbitdimarcaturasullecellelive
29
mark-sweep(1)
30
root set
Heap space
mark-sweep(2)
31
root set
Heap space
mark-sweep(3)
32
root set
Heap space
mark-sweep(4)
33
root set
Heap space
cellemarcate
garbage
mark-sweep:valutazione
OperacorreEamentesullestruEurecircolari(+)Nessunoverheaddispazio(+)Sospensionedell’esecuzione(-) Nonintervienesullaframmentazionedelloheap(-)
34
Copyingcollec,on
L’AlgoritmodiCheneyèunalgoritmodigarbagecollec,oncheoperasuddividendolamemoriaheapinduepar,o “from-space”e“to-space”
Solamenteunadelleduepar,delloheapèaBva(permeEepertantodiallocarenuovecelle)QuandovieneaBvatoilgarbagecollector,lecellelivevengonocopiatenellasecondaporzionedelloheap(quellanonaBva)o allafinedellaoperazionedicopiairuolitraleduepar,delleheap
vengonoscambia,(lapartenonaBvadiventaaBvaeviceversa)
LecellenellapartenonaBvavengonores,tuiteallalistaliberainununicobloccoevitandoproblemidiframmentazione
35
Esempio
36
from-space
to-space
root A
C B
D
forwarding address
pointer
A’ B’ C’ D’
Scambiodeiruoli
37
to-space
from-space
forwarding address
pointer
A’ B’ C’ D’ root
Copyingcollector:valutazione
Èefficacenellaallocazionediporzionidispaziodidimensionidifferen,eevitaproblemidiframmentazione CaraEeris,canega,va:duplicazionedelloheapo da,sperimentalidiconochefunzionamoltobenesuarchiteEurehardwarea64-bit
38
Genera,onalGarbageCollec,on
Osservazionedibaseo “mostcellsthatdie,dieyoung”(adesempioacausadelleregolediscopedeiblocchi)
Sidivideloheapinuninsiemedigenerazioni Ilgarbagecollectoroperasullegenerazionipiùgiovani
39
Esempio(1)
40
Young
Old
root set
A
B
C
D
E
F
G
Esempio(2)
41
Young
Old
root set
A
B
D
E
F
G
C
Copying+generazioni
42
Youngest
Oldest
To-space
From-space
From-space
To-space
root set
.
.
.
Middle generation(s)
GCnellapra,ca
Sun/OracleHotspotJVMo GCcontregenerazioni(0,1,2)o Gen.1copycollec,ono Gen.2mark-sweepconmeccanismiperevitarelaframmentazione
Microso�.NET–GCcontregenerazioni(0,1,2)–Gen.2mark-sweep(nonsemprecompaEaiblocchisulloheap)
43
Top Related