Skräpsamling

Skräpsamling (från engelskans garbage collection) är en automatisk dynamisk minneshanteringsmetod. Skräpsamlaren (garbage collector) eller samlaren söker att återvinna skräp, med vilket avses arbetsminne eller andra resurser som tilldelats dataobjekt som aldrig kommer att användas igen, och frigör dessa automatiskt.

Skräpsamling framhålls ibland som raka motsatsen till manuell dynamisk minneshantering, som kräver att programmeraren uttryckligen specificerar vilka objekt som skall frigöras. Dock använder sig flera system en kombination av de två metoderna.

Beskrivning

De två grundläggande uppgifterna för en skräpsamlare är:

1. Bestämma vilka dataobjekt som aldrig kommer att användas igen, det vill säga hitta skräpet.
2. Frigöra skräpet, så att resurserna kan återanvändas.

Eftersom skräpsamling gör manuell deallokation onödig (och vanligtvis omöjlig), slipper programmeraren oroa sig över att själv frigöra oanvända dataobjekt, något som annars kan kräva betydande programmeringsansträngningar. Skräpsamling hjälper också programmerare att göra sina program stabilare eftersom den förhindrar ett antal programmeringsfel.

Många programspråk kräver skräpsamling, antingen som del av språkspecifikationen (till exempel Java, C# och de flesta skriptspråk) eller för att kunna framställa en effektiv tillämpning (till exempel formella språk som lambdakalkyl). Andra språk har utformats för manuell minneshantering, men finns i upplagor med skräphantering (till exempel C, C++). Några språk, som Modula-3, tillåter både skräpsamling och manuell minneshantering att fungera tillsammans i samma program genom att använda separata heapar för automatiskt respektive manuellt hanterade objekt. Andra språk som D har skräpsamling men tillåter programmeraren att manuellt frigöra objekt och stänga av skräpsamlingen helt när prestandakraven dikterar det. Det är betydligt enklare att tillämpa skräpsamling som del av ett programspråks kompilator och runtime-system. Skräphanteraren är nästan alltid intimt kopplad till minnesallokeraren.

Spårande skräpsamlare

Spårande skräpsamlare är den vanligaste typen. De bestämmer först vilka objekt som är åtkomliga (eller i alla fall potentiellt åtkomliga), och frigör alla övriga objekt.

Åtkomlighet

Informellt är ett åtkomligt objekt ett objekt för vilket det finns ett namn i programmiljön som leder till det, antingen direkt eller indirekt genom referenser från andra åtkomliga objekt. Mer precist kan objekt vara åtkomliga endast på två sätt:

1. En särskild mängd objekt antas vara åtkomliga -- dessa kallas för rötter. Vanligtvis räknas samtliga aktiva lokala variabler och parametrar på stacken samt alla globala variabler.
2. Alla objekt som refereras från ett åtkomligt objekt är i sin tur åtkomliga; det vill säga, åtkomlighet är transitiv.

Definitionen av "skräp" som icke åtkomliga objekt är inte optimal, eftersom den sista gången ett program använder ett objekt kan inträffa långt före objektet slutar vara åtkomligt. Ibland markeras skillnaden mellan syntaktiskt skräp, de objekt som programmet omöjligt kommer åt, och semantiskt skräp, de objekt som programmet inte kommer att använda igen. Det visar sig att problemet att identifiera semantiskt skräp är minst lika svårt som stopproblemet. Även om konservativa heuristiska metoder för semantisk skräpsamling är ett aktivt forskningsområde, fokuserar i princip alla praktiska skräpsamlare på syntaktiskt skräp enligt definitionen ovan.

Grundläggande algoritm

Skräpsamlare kallas "spårande" eftersom de spårar igenom arbetsminnen för att hitta åtkomliga objekt. De utför sitt arbete i cykler. En cykel påbörjas när samlaren bestämmer (eller blir åtsagd) att den behöver återvinna lagringsutrymme, något som i synnerhet gäller när systemet har ont om ledigt arbetsminne. Den ursprungliga metoden var en naiv markera-och-sopa-metod (mark-and-sweep) där hela arbetsminnet spåras igenom flera gånger. Denna metod har ersatts av så kallad trefärgsmarkering (tri-colour marking).

I den naiva metoden har varje objekt en flagga, (vanligtvis en bit) som används endast för skräpsamling. Flaggan är alltid omarkerad förutom under en skräpsamlingscykel. Det första stadiet i en skräpsamling sveper igenom alla 'rötterna' och markerar varje åtkomligt objekts flagga som 'åtkomlig'. Alla transitivt åtkomliga objekt markeras också. Slutligen undersöks varje objekt i minnet igen; de som fortfarande har en omarkerad flagga är inte åtkomliga från programmet och deras minne kan återvinnas. Övriga åtkomliga objekt får sin flagga omarkerad igen i förberedelse för nästa cykel.

Denna metod har flera nackdelar, den mest märkbara är att hela systemet måste uppehållas under samlingens gång; inga ändringar i arbetsminnet får göras. Detta orsakar program att 'frysa' periodvis och oförutsägbart, vilket gör realtids- och tidskritiska tillämpningar omöjliga. Dessutom måste hela arbetsminnet genomsvepas, den större delen två gånger, vilket kan orsaka problem i system med virtuellt minne.

På grund av dessa tillkortakommanden tillämpar alla moderna skräpsamlare någon variant av trefärgsmarkering. Den fungerar som följer:

1. Skapa en vit, grå, och svart mängd; dessa mängder kommer att användas för att markera framskridandet under samlingscykeln. I början består den vita mängden av de objekt som är kandidater för att återvinnas. Den svarta mängden består av de objekt som snabbt kan visas sakna referenser till objekt i den vita mängden; i många tillämpningar är den svarta mängden tom i början. Den grå mängden är alla återstående objekt som kan eller inte kan ha referenser till objekt i den vita mängden eller annorstädes. Samtliga objekt i systemet kan tillhöra endast en av dessa tre mängder.
2. Välj ett objekt från den grå mängden. Svärta objektet genom att gråa alla vita objekt det refererar direkt.
3. Upprepa steg 2 tills den grå mängden är tom.
4. När inga grå objekt återstår är alla kvarvarande objekt i den vita mängden bevisligen inte åtkomliga och kan därför frigöras.

Trefärgsmarkeringsalgoritmen bevarar en viktig invariant:

Inget svart objekt pekar direkt på ett vitt objekt.

Detta försäkrar att de vita objekten kan frigöras när den grå mängden är tom.

Trefärgsmarkeringsalgoritmen har en viktig fördel: den kan utföras samtidigt med programmets normala exekvering, utan att 'frysa' det i längre perioder. Detta åstadkoms genom att markera objekt när de allokeras eller modifieras, vilket upprätthåller de tre mängderna. Genom att övervaka de relativa storlekarna hos de tre mängderna kan skräpsamling ske periodiskt, snarare än vid brinnande behov. Dessutom behöver man inte svepa igenom hela arbetsminnet vid varje cykel.