Java-platformens garbage collection-mekanisme øger i høj grad udviklerens produktivitet, men en dårligt implementeret garbage collector kan overforbruge programressourcerne. I denne tredje artikel i serien om optimering af JVM-ydelsen tilbyder Eva Andreasson Java-anbegyndere en oversigt over Java-platformens hukommelsesmodel og GC-mekanisme. Derefter forklarer hun, hvorfor fragmentering (og ikke GC) er den største “gotcha!” for Java-applikationers ydeevne, og hvorfor generationsbaseret garbage collection og komprimering i øjeblikket er de førende (om end ikke de mest innovative) tilgange til håndtering af heap-fragmentering i Java-applikationer.

Garbage collection (GC) er den proces, der har til formål at frigøre optaget hukommelse, der ikke længere refereres af noget Java-objekt, der kan nås, og er en væsentlig del af Java virtual maskinens (JVM) dynamiske hukommelsesstyringssystem. I en typisk affaldsindsamlingscyklus bevares alle objekter, som der stadig henvises til, og som derfor kan nås. Den plads, der er optaget af tidligere refererede objekter, frigøres og genindvindes for at muliggøre ny objektallokering.

For at forstå garbage collection og de forskellige GC-tilgange og algoritmer skal du først vide et par ting om Java-platformens hukommelsesmodel.

Garbage collection og Java-platformens hukommelsesmodel

Når du angiver opstartsindstillingen -Xmx på kommandolinjen for din Java-applikation (f.eks.: java -Xmx:2g MyApp), tildeles hukommelse til en Java-proces. Denne hukommelse omtales som Java-heap (eller blot heap). Dette er det dedikerede hukommelsesadresseområde, hvor alle objekter, der oprettes af dit Java-program (eller nogle gange JVM’en), allokeres. Efterhånden som dit Java-program kører og allokerer nye objekter, vil Java-heap (dvs. dette adresseområde) blive fyldt op.

Eventuelt vil Java-heap være fuld, hvilket betyder, at en allokerende tråd ikke kan finde et tilstrækkeligt stort sammenhængende afsnit af ledig hukommelse til det objekt, den ønsker at allokere. På det tidspunkt bestemmer JVM’en, at der skal foretages en garbage collection, og den underretter garbage collector’en herom. En garbage collection kan også udløses, når et Java-program kalder System.gc(). Brug af System.gc() garanterer ikke en garbage collection. Før en garbage collection kan starte, vil en GC-mekanisme først afgøre, om det er sikkert at starte den. Det er sikkert at starte en garbage collection, når alle programmets aktive tråde er på et sikkert punkt, der tillader det, f.eks. forklares det blot, at det ville være dårligt at starte garbage collection midt i en igangværende objektallokering eller midt i udførelsen af en sekvens af optimerede CPU-instruktioner (se min tidligere artikel om compilere), da man kan miste kontekst og dermed ødelægge slutresultaterne.

En garbage collector bør aldrig kræve et aktivt refereret objekt tilbage; at gøre det ville bryde specifikationen for Java virtual machine. En garbage collector er heller ikke forpligtet til straks at indsamle døde objekter. Døde objekter indsamles i sidste ende i løbet af efterfølgende garbage collection-cyklusser. Selv om der er mange måder at implementere garbage collection på, gælder disse to antagelser for alle varianter. Den virkelige udfordring ved garbage collection er at identificere alt, hvad der er levende (stadig refereret), og at genvinde al ikke-refereret hukommelse, men uden at det påvirker de kørende programmer mere end nødvendigt. En garbage collector har således to mandater:

1. At hurtigt frigøre ikke-refereret hukommelse for at opfylde et programs allokeringshastighed, så det ikke løber tør for hukommelse.
2. At genvinde hukommelse, mens det påvirker ydelsen minimalt (f.eks, latency og gennemløb) af et kørende program.

To slags garbage collection

I den første artikel i denne serie berørte jeg de to hovedtilgange til garbage collection, som er referencetælling og tracing collectors. Denne gang vil jeg bore yderligere ned i hver tilgang og derefter introducere nogle af de algoritmer, der bruges til at implementere tracing collectors i produktionsmiljøer.

Referencetællingsopsamlere

Referencetællingsopsamlere holder styr på, hvor mange referencer der peger på hvert Java-objekt. Når tællingen for et objekt bliver nul, kan hukommelsen straks genindvindes. Denne øjeblikkelige adgang til genbrugte hukommelse er den største fordel ved referenceoptællingsmetoden til affaldsindsamling. Der er meget lidt overhead, når det gælder om at holde fast i hukommelse uden referencer. Det kan dog være ret dyrt at holde alle referencetællinger ajour.

Den største vanskelighed ved referencetællende opsamlere er at holde referencetællingerne nøjagtige. En anden velkendt udfordring er den kompleksitet, der er forbundet med håndtering af cirkulære strukturer. Hvis to objekter refererer til hinanden, og der ikke er noget levende objekt, der refererer til dem, vil deres hukommelse aldrig blive frigivet. Begge objekter vil for evigt forblive med en tælling, der ikke er nul. Tilbagekaldelse af hukommelse i forbindelse med cirkulære strukturer kræver en større analyse, hvilket medfører et dyrt overhead for algoritmen og dermed for programmet.

Sporingssamlere

Sporingssamlere er baseret på den antagelse, at alle levende objekter kan findes ved iterativt at spore alle referencer og efterfølgende referencer fra et indledende sæt af objekter, der vides at være levende. Det indledende sæt af levende objekter (kaldet rodobjekter eller blot rødder) lokaliseres ved at analysere registre, globale felter og stack frames på det tidspunkt, hvor en garbage collection udløses. Når et indledende sæt levende objekter er blevet identificeret, følger sporingsopsamleren referencerne fra disse objekter og sætter dem i kø for at blive markeret som levende og efterfølgende få deres referencer sporet. Når alle fundne refererede objekter markeres som levende, betyder det, at det kendte levende sæt øges over tid. Denne proces fortsætter, indtil alle refererede (og dermed alle levende) objekter er fundet og markeret. Når sporingsopsamleren har fundet alle levende objekter, kræver den den resterende hukommelse tilbage.

Sporingsopsamlere adskiller sig fra referenceoptællingsopsamlere ved, at de kan håndtere cirkulære strukturer. Fangsten ved de fleste sporingsopsamlere er markeringsfasen, som medfører en ventetid, før de kan genvinde hukommelse uden referencer.

Sporingsopsamlere anvendes oftest til hukommelsesstyring i dynamiske sprog; de er langt de mest almindelige til Java-sproget og har været kommercielt afprøvet i produktionsmiljøer i mange år. Jeg vil fokusere på sporingsopsamlere i resten af denne artikel og starte med nogle af de algoritmer, der implementerer denne tilgang til garbage collection.

Sporingsopsamleralgoritmer

Kopiering og mark-and-sweep garbage collection er ikke nye, men de er stadig de to mest almindelige algoritmer, der implementerer sporingsopsamling af garbage collection i dag.

Kopieringsopsamlere

Traditionelle kopieringsopsamlere bruger et from-space og et to-space — det vil sige to separat definerede adresseområder i heap’en. På tidspunktet for garbage collection kopieres de levende objekter inden for det område, der er defineret som from-space, til den næste tilgængelige plads inden for det område, der er defineret som to-space. Når alle de levende objekter inden for from-space er flyttet ud, kan hele from-space genindvindes. Når allokeringen begynder igen, starter den fra den første frie plads i to-space.

I ældre implementeringer af denne algoritme bytter from-space og to-space plads, hvilket betyder, at når to-space er fuldt, udløses garbage collection igen, og to-space bliver til from-space, som vist i figur 1.

Mere moderne implementeringer af kopieringsalgoritmen giver mulighed for at tildele vilkårlige adresseområder inden for heap’en som to-space og from-space. I disse tilfælde behøver de ikke nødvendigvis at skifte placering med hinanden; de bliver snarere hver især til et andet adresseområde inden for heap.

En af fordelene ved kopierende opsamlere er, at objekter allokeres tæt sammen i to-space, hvilket helt eliminerer fragmentering. Fragmentering er et almindeligt problem, som andre garbage collection-algoritmer kæmper med; noget jeg vil diskutere senere i denne artikel.

Nedlemmer ved kopierende indsamlere

Kopierende indsamlere er normalt stop-the-world-opsamlere, hvilket betyder, at der ikke kan udføres noget applikationsarbejde, så længe garbage collection er i cyklus. I en stop-the-world-implementering gælder det, at jo større det område er, du skal kopiere, jo større er indvirkningen på din programydelse. Dette er en ulempe for programmer, der er følsomme over for responstid. Med en kopi-opsamler skal du også overveje det værst tænkelige scenarie, når alt er levende i from-området. Der skal altid være tilstrækkelig plads til, at der kan flyttes levende objekter, hvilket betyder, at to-space skal være stort nok til at rumme alt i from-space. Kopieringsalgoritmen er lidt hukommelsesmæssigt ineffektiv på grund af denne begrænsning.

Mark-and-sweep-kollektorer

De fleste kommercielle JVM’er, der anvendes i virksomhedens produktionsmiljøer, kører mark-and-sweep- (eller markerings) kollektorer, som ikke har den ydelsesmæssige påvirkning, som kopierings-kollektorer har. Nogle af de mest kendte markeringssamlere er CMS, G1, GenPar og DeterministicGC (se Ressourcer).

En mark-and-sweep-samler sporer referencer og markerer hvert fundet objekt med en “levende” bit. Normalt svarer en sat bit til en adresse eller i nogle tilfælde til et sæt adresser på bunken. Den levende bit kan f.eks. være gemt som en bit i objekthovedet, en bitvektor eller et bitmap.

Når alt er blevet markeret levende, går sweep-fasen i gang. Hvis en opsamler har en sweep-fase, indeholder den grundlæggende en eller anden mekanisme til at gennemløbe heap’en igen (ikke kun det levende sæt, men hele heap-længden) for at lokalisere alle ikke-markerede bidder af på hinanden følgende hukommelsesadresserum. Ikke-mærket hukommelse er fri og kan genindvindes. Indsamleren sammenkæder derefter disse ikke-markerede dele til organiserede frie lister. Der kan være forskellige frie lister i en skraldesamler – normalt organiseret efter chunk-størrelser. Nogle JVM’er (f.eks. JRockit Real Time) implementerer opsamlere med heuristik, der dynamisk opstiller lister med størrelsesintervaller baseret på programprofileringsdata og statistikker over objektstørrelser.

Når fejningsfasen er afsluttet, begynder allokeringen igen. Nye allokeringsområder allokeres fra de frie lister, og hukommelsesklumperne kan matches med objektstørrelser, objektstørrelsesgennemsnit pr. tråd-ID eller de programafstemte TLAB-størrelser. Ved at tilpasse de frie områder bedre til størrelsen af det, som programmet forsøger at allokere, optimeres hukommelsen, og det kan bidrage til at reducere fragmenteringen.

Ulemper ved mark-and-sweep-opsamlere

Markeringsfasen er afhængig af mængden af levende data på din heap, mens sweep-fasen er afhængig af heap-størrelsen. Da du skal vente på, at både markerings- og fejningsfasen er afsluttet for at genvinde hukommelse, giver denne algoritme udfordringer med pausetid for større heaps og større levende datasæt.

En måde, du kan hjælpe stærkt hukommelsesforbrugende programmer på, er at bruge GC-tuningmuligheder, der imødekommer forskellige programscenarier og behov. Tuning kan i mange tilfælde hjælpe med i det mindste at udskyde, at en af disse faser ikke bliver en risiko for dit program eller dine serviceniveauaftaler (SLA’er). (En SLA angiver, at applikationen skal overholde bestemte applikationsresponstider – dvs. latency.) Tuning for hver belastningsændring og applikationsændring er imidlertid en gentagende opgave, da tuningen kun gælder for en bestemt arbejdsbyrde og tildelingshastighed.

Implementeringer af mark-and-sweep

Der findes mindst to kommercielt tilgængelige og gennemprøvede tilgange til implementering af mark-and-sweep-indsamling. Den ene er den parallelle fremgangsmåde og den anden er den samtidige (eller overvejende samtidige) fremgangsmåde.

Parallelle opsamlere

Parallel opsamling betyder, at de ressourcer, der er tildelt processen, anvendes parallelt med henblik på skraldespandsopsamling. De fleste kommercielt implementerede parallelle opsamlere er monolitiske stop-the-world-opsamlere — alle applikationstråde stoppes, indtil hele affaldsindsamlingscyklussen er afsluttet. Ved at stoppe alle tråde kan alle ressourcer bruges effektivt parallelt til at afslutte skraldesamlingen gennem markerings- og fejningsfaserne. Dette fører til et meget højt effektivitetsniveau, hvilket normalt resulterer i høje resultater på gennemløbsbenchmarks som SPECjbb. Hvis gennemløb er afgørende for din applikation, er den parallelle tilgang et fremragende valg.