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