Christian Davéns personliga hemsida.
En jämförelse av tekniker för automatisk skräphantering
11 november 2004, för kursen Avancerad objektorientering vid KTH/DSV
Det finns flera olika tekniker för automatisk skräphantering (eng. garbage collection) och i denna artikel tas tre av dem upp. Tekniska detaljer som locality of reference och minnesfragmentering berörs inte alls.
Referensräkning
Referensräkning (eng. reference counting) är den allra enklaste formen av skräphantering. Det fungerar så att alla objekt innehåller en räknare som visar hur många referenser som pekar till det. Varje gång en ny referens skapas ökas räknarens värde och vice versa. När räknaren slutligen visar att det inte längre finns någon referens till objektet innebär det att programmet inte längre kan nå det. Då kan minnet som objektet tagit upp frigöras.
Den stora fördelen med referensräkning är just enkelheten -- det är lätt att implementera. En nackdel är den extra tidskostnad som tillkommer vid varje skapad och borttagen referens när räknarna ska justeras. Detta gör att referensräkning är lämpligt i miljöer där prestanda- och minneskraven inte är alltför höga.
En mer allvarlig nackdel är den att cykliska referenser aldrig frigörs även när de blir isolerade från övriga programmet. Exempelvis kan två objekt referera till varandra antingen direkt eller via andra objekt. Dessa referensräknare kommer då aldrig bli noll trots att programmet kan ha tagit bort den sista referensen till denna "objektklunga". På grund av detta kan det trots skräphanteringen finnas oanvänt minne som aldrig frigörs.
Exempel på programspråk som använder sig av referensräkning är Python, Perl och Visual Basic.
Markera och sopa
Tekniken "markera och sopa" (eng. mark and sweep) är något mer avancerad än referensräkning. Den går ut på att skräphanteraren startar i en rot-mängd av objekt och följer alla referenser till andra objekt rekursivt. Varje objekt man stöter på markeras som aktivt. Efter genomsökningen går hanteraren igenom alla allokerade objekt (även de onåbara) och frigör minnet som upptas av de objekt som inte är markerade.
Det krävs att programmet under en kort stund pausas för att inga referenser ska förändras under hanteringen. Denna paus kan i värsta fall bli såpass långvarig att programmets prestanda blir ordentligt lidande. Under sopningsfasen går hanteraren igenom alla objekt på heapen vilket kan skapa stora prestandaproblem om delar av heapen har växlats ut på hårddisken.
Tekniken är vanligen icke-deterministisk, vilket innebär att skräphanteringen kan ske precis när som helst och ta godtyckligt lång tid att genomföra. Den rekursiva sökningen genom alla aktiva objekt kan också kräva mycket minne. Detta betyder att tekniken inte bör användas i system med kritisk prestanda.
Även denna teknik är förhållandevis enkel att implementera. Den klarar också av att hantera cykliska referenser och är därför ofta att föredra framför eller tillsammans med den simplare referensräkningen.
Markera och sopa kräver också att det finns en entydig rot-mängd av objekt, som inte är fallet i exempelvis Python. Dock används tekniken på många andra håll, till exempel i vissa implementationer av Eiffel, Smalltalk och Java.
Generational
De allra flesta objekt är väldigt kortlivade. Därför kan man räkna med att ju längre ett objekt refereras av programmet, desto mindre är sannolikheten att referenserna kommer försvinna. Med detta som utgångspunkt har man tagit fram ännu en teknik för skräphantering, nämligen generational. Denna teknik hanterar objekten på olika sätt beroende på hur gamla de är -- vilken generation de tillhör.
Heapen delas upp i ett antal partitioner och alla nyskapade objekt hamnar i samma partition. När skräphanteringen tagit hand om denna partition flyttas alla kvarvarande objekt till en annan partition. Partitionen för nya objekt genomsöks mycket oftare än övriga och endast en partition genomsöks varje omgång. Genomsökningen sker med någon annan metod för skräphantering.
Om exempelvis markera och sopa används för att genomsöka partitionen för de nya, kortlivade objekten kommer i regel endast en mindre andel av objekten markeras. De allra flesta kommer redan vara onåbara och ska därför sopas bort, vilket gör att hanteringen går snabbare än om en större andel av de genomsökta objekten fortfarande skulle vara aktiva.
Tack vare partitioneringen och uppdelningen i kortlivade och beständiga objekt blir paustiderna kortare, vilket leder till mindre störningar i programmets körning. Däremot behöver skräphanteringen ske oftare eftersom det finns flera partitioner att genomsöka. För högsta effektivitet krävs att partitionen för de nya objekten är större än övriga, samt att objekten i programmet är kortlivade. Om dessa krav inte uppfylls blir tekniken ineffektiv eftersom alla partitioner då behöver hanteras ungefär lika ofta.
Tekniken används i vissa implementationer av Eiffel, Smalltalk och exempelvis Sun Microsystems Java HotSpot.
Länkar
- An Introduction to Garbage Collection
- Garbage Collection in the HotSpot JVM
- Garbage Collection for Python
| Allt material faller under Creative Commons-licensen.
”Om man vill förstå mänsklighetens göromål kan det vara till hjälp om man är klar över att de flesta av historiens stora triumfer och tragedier skapas, inte av människor som i grunden är goda eller onda, utan av människor som i grunden är människor.”