Sivunkorvausalgoritmit

Sivunkorvausalgoritmit ovat tietojenkäsittelytieteessä käytettyjä menetelmiä, jotka optimoivat muistinhallintaa, erityisesti virtuaalimuistin yhteydessä. Kun fyysinen keskusmuisti ei riitä kaikille käynnissä oleville ohjelmille tarvittavalle datalle, käyttöjärjestelmä siirtää osan tiedosta kiintolevylle tai SSD-asemalle, jota kutsutaan swappiness-tilaksi. Sivunkorvausalgoritmien tehtävänä on päättää, mitkä muistisivut (pienet lohkot muistia) tulisi siirtää pois keskusmuistista, kun uutta dataa on ladattava.

Tavoitteena on minimoida sivuvirheet, eli tilanteet, joissa ohjelma yrittää käyttää dataa, joka on siirretty pois keskusmuistista. Tehokas sivunkorvausalgoritmi pyrkii pitämään muistissa ne sivut, joita ohjelma todennäköisimmin tarvitsee lähitulevaisuudessa. Tämä perustuu usein oletukseen, että hiljattain käytetyt sivut tai sivut, joita ei ole käytetty vähään aikaan, toistavat käyttäytymismalliaan.

Yleisimpiä sivunkorvausalgoritmeja ovat First-In, First-Out (FIFO), jossa vanhimmat sivut poistetaan ensin, ja Least Recently Used (LRU), jossa poistetaan vähiten äskettäin käytetty sivu. LRU on usein tehokkaampi, mutta sen toteutus voi olla monimutkaisempi. Muita algoritmeja ovat esimerkiksi Optimal (OPT), joka on teoreettinen ideaali mutta ei käytännössä toteutettavissa, ja erilaiset likimääräiset LRU-toteutukset, jotka pyrkivät tasapainottamaan tehokkuutta ja resurssien käyttöä. Valinta algoritmista riippuu järjestelmän vaatimuksista ja muistinhallinnan monimutkaisuudesta.