Automaattinen roskienkeräys

Automaattinen roskienkeräys (engl. garbage collection) tai roskankeruu tarkoittaa tietotekniikassa automaattista muistinhallintamekanismia. Siinä roskienkerääjä (engl. garbage collector, GC) pyrkii poistamaan automaattisesti muistista tiedot, joihin sovellus ei tule enää viittaamaan, ja vapauttamaan niiden käyttämän muistitilan uudelleen käytettäväksi. Roskienkeruun keksi John McCarthy vuoden 1959 aikoihin kehittäessään Lisp-ohjelmointikieltään. Lisp-murteiden lisäksi roskienkeruuta käyttävät esimerkiksi Java, OCaml, Python, Perl ja Ruby.

Vastakohtana roskienkeruulle on manuaalinen muistinhallinta, jossa ohjelmoijan tulee itse määritellä milloin aiemmin varattu muisti vapautetaan. Tällaisia kieliä ovat esimerkiksi C ja C++. Molemmissa on mahdollista käyttää viitelaskentaa seuraamaan milloin varattu muisti voidaan vapauttaa.

Useissa olio-ohjelmointikielissä muistin varaus tehdään olion konstruktorissa ja muistin vapauttaminen sen destruktorissa (RAII, engl. Resource acquisition is initialization). Tällöin roskienkeruumenetelmälle ei ole tarvetta.

Vastakohtana ajonaikaiselle roskienkeruulle on kehitetty käännösaikainen roskienkeruu staattisen analyysin avulla kuten Mercury-kielelle.

Edut ja haitat

Ilmeinen ja merkittävä etu automaattisessa muistinhallinnassa on ohjelmien helpompi toteuttaminen.^lähde?

Monet virheet ohjelmissa liittyvät muistinhallintaan, esimerkiksi viittaaminen muistialueeseen joka on jo vapautettu tai viittaaminen muistialueeseen jota ei ole varattu. Molemmissa tapauksissa muistialue voi sisältää epävalidia dataa, joka voi aiheuttaa virhetoiminnon.

Haittana on taas roskienkeruusta johtuva jätekuorma (engl. overhead), joka voi joskus olla ongelma. Roskienkeräys on usein aikaa vievä operaatio, jossa kaikki ohjelman muistiviittaukset käydään läpi, ja tämä saattaa viedä jopa sekunteja. Käyttämällä manuaalista muistinhallintaa ohjelmoija voi suunnitella koodin optimaaliseksi muistinhallinnan osalta, koska hän saattaa tietää tarkoin missä vaiheessa muistia tarvitaan milläkin hetkellä.

Mekanismit

Roskienkeruuseen on erilaisia algoritmeja, jotka eroavat toisistaan tehokkuudeltaan ja monimutkaisuudeltaan. Useiden muiden algoritmien tapaan yksinkertaiset roskienkeruun toteutukset ovat keskimäärin tehokkuudeltaan heikompia kuin monimutkaiset.

• Merkitse ja pyyhi (engl. mark and sweep)
• Pysähdy ja kopioi (engl. stop-and-copy)

Käyttökohteet

Roskienkeruuta käytetään pääasiassa ohjelman varaaman muistin vapauttamiseen. Roskienkeruu ei koske asioita kuten verkko- ja tiedostokahvoja, graafisen käyttöliittymän komponentteja ja niin edelleen.

Strategiat

Jäljittäminen

Jäljittelevä roskienkeruu on käytetyin roskienkeruu tapa, jonka takia roskienkeruulla, usein viitataan juuri siihen, eikä muihin tapoihin, kuten viitelaskentaan. Jäljittelevän roskienkeruun yleinen strategia koostuu siitä, että selvitetään mitkä objektit on keräämisen arvoista jäljittämällä, mitkä objektit ovat saavutettavissa juurikohteiden referenssiketjun kautta, ja loput objektit merkitään roskaksi ja kerätään pois. Kuitenkin käytännössä on kyse suureasta määrästä algoritmeja, joilla on laaja vaihtelu monimutkaisuudessa ja suorituskykyominaisuuksissa.^lähde?

Viitelaskenta

Viitelaskennalla tehtävä roskienkeruu perustuu siihen, että jokaisella objektilla on laskuri, johon kirjoitetaan ylös, kuinka monta referenssiä objektilla on. Viitelaskentaa käyttäen roskat tunnistetaan referenssi määrän kautta, jolloin kerätään vain ne objektit joiden referenssimäärä on nolla. Objektin referenssi määrä kasvaa, kun objektiin luodaan referenssi ja laskee, kun kyseinen referenssi poistetaan. Objektista vapautetaan muisti, kun referenssimäärä laskee nollaan. Kuten manuaalisen muistinhallinnan kanssa, ja toisin kuin jäljittelevä roskienkeruun keräys, viitelaskennan roskienkeruussa objektit ovat tuhottu heti, kun niiden viimeinen referenssi poistetaan.^lähde?

Koska viitelaskennan perusteella tapahtuvassa roskienkeruussa on monta haittapuolta, niin niitä ratkaistaan erilaisten algoritmien kautt.^lähde?

Sykli

Jos kaksi tai enemmän objektia viittaavat toisiansa, ne voivat muodostaa syklin, jolloin niiden viite määrä ei tule laskemaan 0, ja siitä johtuen niitä ei nimitetä roskiksi ja tuhota. Jotkut roskienkeruu systeemit käyttävät syklien havaitsemisalgoritmeja korjaamaan tilanteen. Mutta toinen tapa on käyttää heikkoa viitettä. Tämä viite toimii viitelaskennassa samalla tavalla, kuin heikko viite toimisi jäljittelevässä roskienkeruussa. Olemalla erityinen viite, niin se ei nosta objektin viitelaskuria.^lähde?