Sivunvaihtoalgoritmi - Page replacement algorithm

Vuonna tietokone käyttöjärjestelmä , joka käyttää kutsumiseksi varten virtuaalimuistin hallinta , sivu korvaaminen algoritmeja päättää, mitä muistia sivuja sivun, joskus kutsutaan swap ulos, tai kirjoittaa levylle, kun sivua muistia tarvitsee varata. Sivunvaihto tapahtuu, kun pyydetty sivu ei ole muistissa ( sivuvika ) ja vapaata sivua ei voida käyttää varauksen täyttämiseen joko sen vuoksi, että niitä ei ole, tai koska ilmaisten sivujen määrä on pienempi kuin jokin kynnysarvo.

Kun sivulle, joka valittiin vaihdettavaksi ja haettiin pois, viitataan uudelleen, se on sivutettava (luettava levyltä), ja tämä edellyttää I/O -valmistumisen odottamista. Tämä määrittää sivunvaihtoalgoritmin laadun : mitä vähemmän aikaa sivujen odottamiseen, sitä parempi algoritmi. Sivunvaihtoalgoritmi tarkastelee laitteiston tarjoamia rajallisia tietoja pääsyistä sivuille ja yrittää arvata, mitkä sivut on vaihdettava, jotta minimoidaan sivujen kokonaismäärä, samalla kun tämä tasapainotetaan kustannuksilla (ensisijainen tallennustila ja prosessorin aika) itse algoritmi.

Sivun korvaava ongelma on tyypillinen online -ongelma kilpailuanalyysin kannalta siinä mielessä, että optimaalinen deterministinen algoritmi tiedetään.

Historia

Sivunvaihtoalgoritmit olivat kuuma tutkimus- ja keskustelunaihe 1960- ja 1970 -luvuilla. Tämä päättyi pääosin kehittyneiden LRU (vähiten äskettäin käytetyt) lähentämiseen ja toimivien joukkojen algoritmeihin. Siitä lähtien jotkut perinteisten sivunvaihtoalgoritmien perusoletukset mitätöitiin, mikä johti tutkimuksen elvyttämiseen. Erityisesti seuraavat trendit taustalla olevien laitteistojen ja käyttäjätason ohjelmistojen käyttäytymisessä ovat vaikuttaneet sivunvaihtoalgoritmien suorituskykyyn:

• Ensisijaisen tallennustilan koko on kasvanut useita kertoja. Useiden gigatavujen ensisijaisen muistin ansiosta algoritmit, jotka vaativat jokaisen muistikehyksen säännöllisen tarkistamisen, ovat yhä vähemmän käytännöllisiä.
• Muistihierarkiat ovat kasvaneet. Kustannukset CPU välimuisti neiti on huomattavasti kalliimpaa. Tämä pahentaa edellistä ongelmaa.
• Käyttäjäohjelmiston viitepaikka on heikentynyt. Tämä johtuu enimmäkseen olio-ohjelmointitekniikoiden leviämisestä, jotka suosivat suurta määrää pieniä toimintoja, kehittyneiden tietorakenteiden, kuten puiden ja hajautustaulukoiden käytöstä, jotka johtavat yleensä kaoottisiin muistiviittausmalleihin, ja roskien keräämisestä, joka muuttui dramaattisesti sovellusten muistin käyttötapa.

Vaatimukset sivun korvaavan algoritmeja ovat muuttuneet johtuen eroista käyttöjärjestelmän ytimen arkkitehtuurit. Erityisesti useimmissa nykyaikaisissa käyttöjärjestelmän ytimissä on yhtenäinen virtuaalimuisti ja tiedostojärjestelmävälimuistit, jotka edellyttävät sivunvaihtoalgoritmin valitsemaan sivun sekä käyttäjäohjelman virtuaalisten osoitetilojen että välimuistitiedostojen sivujen joukosta. Jälkimmäisillä sivuilla on erityisiä ominaisuuksia. Ne voivat esimerkiksi olla lukittuja tai niillä voi olla kirjoitustilausvaatimuksia päiväkirjoittamisen vuoksi . Lisäksi koska sivunvaihdon tavoitteena on minimoida muistin odotusaika, sen on otettava huomioon muiden muistia varaavien ytimen alijärjestelmien asettamat muistivaatimukset. Tämän seurauksena sivujen korvaaminen nykyaikaisissa ytimissä ( Linux , FreeBSD ja Solaris ) pyrkii toimimaan yleiskäyttöisen ytimen muistinvaraajan tasolla virtuaalimuistialijärjestelmän ylemmällä tasolla.

Paikallinen vs. maailmanlaajuinen korvaaminen

Korvausalgoritmit voivat olla paikallisia tai maailmanlaajuisia.

Kun prosessissa ilmenee sivuvika, paikallinen sivunvaihtoalgoritmi valitsee korvaamaan jonkin samaan prosessiin kuuluvan sivun (tai muistiosion jakavan prosessiryhmän ). Yleinen korvaava algoritmi voi vapaasti valita minkä tahansa sivun muistista.

Paikallinen sivunvaihto edellyttää jonkinlaista muistin osiointia, joka määrittää, kuinka monta sivua määrätylle prosessille tai prosessiryhmälle on osoitettava. Suosituimmista muodoista osiointi on kiinteä jako ja tasapainoisen algoritmeja perustuu käyttöjoukon mallia. Paikallisen sivunvaihdon etuna on sen skaalautuvuus: jokainen prosessi voi käsitellä sivuvirheitään itsenäisesti, mikä johtaa tasaisempaan suoritukseen. Globaali sivunvaihto on kuitenkin tehokkaampi kokonaisjärjestelmäpohjaisesti.

Sivujen, joihin viitataan ja joita muutetaan, tunnistaminen

Nykyaikaisissa yleiskäyttöisissä tietokoneissa ja joissakin sulautetuissa suorittimissa on tuki virtuaalimuistille . Jokaisella prosessilla on oma virtuaalinen osoitetila. Sivutaulu kartoittaa osajoukko prosessin virtuaalinen fyysisiksi osoitteiksi. Lisäksi useimmissa arkkitehtuureissa sivutaulukossa on "pääsy" -bitti ja "likainen" -bitti kullekin sivutaulukon sivulle. Suoritin asettaa käyttöbitin, kun prosessi lukee tai kirjoittaa muistia kyseiselle sivulle. CPU asettaa likaisen bitin, kun prosessi kirjoittaa muistia kyseiselle sivulle. Käyttöjärjestelmä voi muuttaa pääsyä ja likaisia ​​bittejä. Käyttöjärjestelmä voi tunnistaa pääsyn muistiin ja tiedostoihin seuraavilla tavoilla:

• Tyhjentämällä pääsybitti prosessin sivutaulukossa olevilla sivuilla. Jonkin ajan kuluttua käyttöjärjestelmä skannaa sivutaulukon ja etsii sivuja, joiden suoritin on asettanut käyttöbitin. Tämä on nopeaa, koska sen asettama pääsybitti on automaattisesti CPU: n määrittämä ja epätarkka, koska käyttöjärjestelmä ei saa välittömästi ilmoitusta pääsystä eikä sillä ole tietoja järjestyksestä, jolla prosessi käytti näitä sivuja.
• Poistamalla sivut prosessin sivutaulukosta poistamatta niitä välttämättä fyysisestä muistista. Seuraava pääsy kyseiselle sivulle havaitaan välittömästi, koska se aiheuttaa sivuvian . Tämä on hidasta, koska sivuvirheeseen liittyy kontekstikytkin käyttöjärjestelmään, ohjelmiston haku vastaavaa fyysistä osoitetta varten, sivutaulukon muuttaminen ja kontekstikytkin takaisin prosessiin ja tarkka, koska pääsy havaitaan heti sen jälkeen.
• Suoraan, kun prosessi tekee systeemikutsut että mahdollisesti käyttää sivua välimuisti kaltaiset readja writePOSIX.

Esipuhdistus

Useimmat korvaavat algoritmit yksinkertaisesti palauttavat kohdesivun tuloksenaan. Tämä tarkoittaa, että jos kohdesivu on likainen (eli sisältää tietoja, jotka on kirjoitettava vakaan tallennustilaan ennen kuin sivua voidaan palauttaa), I/O on aloitettava lähettämään kyseinen sivu vakaan tallennustilaan ( sivun puhdistamiseksi ). Virtuaalimuistin alkuaikoina siivoukseen käytetty aika ei ollut erityisen huolestuttava, koska virtuaalimuisti otettiin ensin käyttöön järjestelmissä, joissa on kaksisuuntaiset kanavat vakaaseen tallennustilaan, ja puhdistus oli tavallisesti päällekkäistä haun kanssa. Nykyaikaiset hyödykkeet eivät sitä vastoin tue kaksisuuntaista siirtoa, ja kohdesivujen puhdistamisesta tulee ongelma.

Tämän tilanteen ratkaisemiseksi toteutetaan erilaisia esipuhdistuskäytäntöjä . Esipuhdistus on mekanismi, joka käynnistää I/O likaisilla sivuilla, jotka (todennäköisesti) vaihdetaan pian. Ajatuksena on, että kun esipuhdistettu sivu on todella valittu korvaamaan, I/O valmistuu ja sivu on puhdas. Esipuhdistus olettaa, että on mahdollista tunnistaa sivut, jotka korvataan seuraavaksi . Liian innokas esipuhdistus voi tuhlata I/O-kaistanleveyttä kirjoittamalla sivuja, jotka voivat likaantua uudelleen ennen kuin ne valitaan vaihdettavaksi.

Ennakoiva haku

Jotkut järjestelmät käyttävät kysynnän hakua - odottavat, kunnes sivua todella pyydetään, ennen kuin lataat sen RAM -muistiin.

Muut järjestelmät yrittävät lyhentää latenssia arvaamalla, mitkä sivut, joita ei ole RAM-muistissa, todennäköisesti tarvitsevat pian, ja lataavat tällaiset sivut RAM-muistiin ennen sivun pyytämistä. (Tämä liittyy usein esipuhdistukseen, joka arvaa, mitä RAM-muistissa olevia sivuja ei todennäköisesti tarvita pian, ja kirjoittaa ne etukäteen tallennukseen.)

Kun sivuvika ilmenee, "ennakoiva haku" -järjestelmät eivät tuota vain viitattua sivua, vaan myös muutaman seuraavan peräkkäisen sivun (analoginen suorittimen esilatausjonoon ).

Swap prefetch mekanismia mennään vielä pidemmälle latautuvat sivut (vaikka ne eivät ole peräkkäisiä), jotka todennäköisesti tarvitaan pian.

(H, k) -haku-ongelma

(H, k) -hakuongelma on yleistys sivutusongelman mallista: Olkoon h, k positiivisia kokonaislukuja . Mitataan algoritmin suorituskyky välimuistilla suhteessa teoreettisesti optimaaliseen sivunvaihtoalgoritmiin . Jos tarjoamme optimaalisen sivunvaihtoalgoritmin ehdottomasti vähemmän resursseja. ${\ displaystyle h \ leq k}$${\ displaystyle h \ leq k}$${\ displaystyle h <k}$

(H, k) -sivutusongelma on tapa mitata online-algoritmin suorituskykyä vertaamalla sitä optimaalisen algoritmin suorituskykyyn erityisesti parametroimalla erikseen online-algoritmin ja optimaalisen algoritmin välimuistin koko.

Merkintäalgoritmit

Merkintäalgoritmit ovat yleinen hakulagoritmien luokka. Yhdistämme kullekin sivulle sen bitin, jota kutsutaan sen merkkiksi. Aluksi asetimme kaikki sivut merkitsemättömiksi. Sivupyyntöjen vaiheessa merkitsemme sivun, kun sitä pyydetään tässä vaiheessa. Merkintäalgoritmi on sellainen algoritmi, joka ei koskaan poista merkittyä sivua.

Jos ALG on merkintäalgoritmi, jonka välimuisti on k ja OPT on optimaalinen algoritmi, jonka välimuisti on h, missä , niin ALG on kilpailukykyinen. Joten jokainen merkintäalgoritmi saavuttaa -kilpailusuhteen. ${\ displaystyle h \ leq k}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$

LRU on merkintäalgoritmi, kun taas FIFO ei ole merkintäalgoritmi.

Konservatiiviset algoritmit

Algoritmi on konservatiivinen, jos millä tahansa peräkkäisellä pyyntöjaksolla, joka sisältää k tai vähemmän erillisiä sivuviittauksia, algoritmi aiheuttaa k tai vähemmän sivuvirheitä.

Jos ALG on konservatiivinen algoritmi, jonka välimuisti on k ja OPT on optimaalinen algoritmi, jonka välimuisti on , ALG on kilpailukykyinen. Joten jokainen konservatiivinen algoritmi saavuttaa kilpailukyvyn suhteen. ${\ displaystyle h \ leq k}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$${\ displaystyle {\ tfrac {k} {k-h+1}}}$

LRU, FIFO ja CLOCK ovat konservatiivisia algoritmeja.

Sivunvaihtoalgoritmit

Sivunvaihtoalgoritmeja on useita:

Teoreettisesti optimaalinen sivunvaihtoalgoritmi

Teoreettisesti optimaalinen sivunvaihtoalgoritmi (tunnetaan myös nimellä OPT, selvänäköisten korvausalgoritmi tai Béládyn optimaalinen sivunvaihtokäytäntö) on algoritmi, joka toimii seuraavasti: kun sivu on vaihdettava, käyttöjärjestelmä vaihtaa sivun, jonka seuraava käyttökerta tapahtuu kauimpana tulevaisuudessa. Esimerkiksi sivu, jota ei käytetä seuraavan 6 sekunnin aikana, vaihdetaan sivulle, jota aiotaan käyttää seuraavan 0,4 sekunnin kuluessa.

Tätä algoritmia ei voida toteuttaa yleiskäyttöisessä käyttöjärjestelmässä, koska on mahdotonta laskea luotettavasti, kuinka kauan kestää ennen kuin sivua käytetään, paitsi jos kaikki järjestelmässä toimivat ohjelmistot ovat joko etukäteen tiedossa ja niitä voidaan käyttää sen muistiviittausmallien staattinen analyysi tai vain sovellusluokka, joka mahdollistaa ajonaikaisen analyysin. Tästä rajoituksesta huolimatta on olemassa algoritmeja, jotka voivat tarjota lähes optimaalisen suorituskyvyn. Tämä algoritmi voi tarjota lähes optimaalisen suorituskyvyn, mutta ei ohjelman ensimmäisellä kerralla ja vain jos ohjelman muistiviittausmalli on suhteellisen johdonmukainen joka kerta, kun se suoritetaan.

Hakulaiteongelmaa on analysoitu myös online -algoritmien alalla . Satunnaistettujen online -algoritmien tehokkuus hakuongelmaan mitataan käyttämällä lyhennettyä analyysiä .

Ei äskettäin käytetty

Ei -äskettäin käytetty (NRU) sivunvaihtoalgoritmi on algoritmi, joka suosii äskettäin käytettyjen sivujen pitämistä muistissa. Tämä algoritmi toimii seuraavalla periaatteella: kun sivulle viitataan, kyseiselle sivulle asetetaan viitattu bitti, joka merkitsee sen viitatuksi. Samoin, kun sivua muutetaan (kirjoitetaan), muokattu bitti asetetaan. Bittien asetukset tehdään yleensä laitteistolla, vaikka se on mahdollista tehdä myös ohjelmistotasolla.

Tietyllä kiinteällä aikavälillä ajastinkeskeytys laukaisee ja tyhjentää viitatun bitin kaikista sivuista, joten vain sivut, joihin viitataan nykyisen ajastinvälin sisällä, on merkitty viitatulla bitillä. Kun sivu on vaihdettava, käyttöjärjestelmä jakaa sivut neljään luokkaan:

3. viitattu, muutettu

2. viitattu, ei muutettu

1. ei viitattu, muutettu

0. ei viitattu, ei muutettu

Vaikka sivun muuntaminen ei vaikuta mahdolliselta, mutta siihen ei ole viitattu, tämä tapahtuu, kun luokan 3 sivun viitattu bitti on poistettu ajastinkeskeytyksestä. NRU -algoritmi valitsee satunnaisen sivun alimmasta luokasta poistettavaksi. Joten edellä mainituista neljästä sivuluokasta NRU-algoritmi korvaa ei-viitatun, muokkaamattoman sivun, jos sellainen on olemassa. Huomaa, että tämä algoritmi merkitsee sitä, että muokattu mutta ei viitattu (viimeisen ajastinvälin sisällä) -sivu on vähemmän tärkeä kuin ei-muokattu sivu, johon viitataan voimakkaasti.

NRU on merkintäalgoritmi, joten se on kilpailukykyinen. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Ensimmäinen sisällä ensimmäinen ulkona

Yksinkertaisin sivunvaihtoalgoritmi on FIFO-algoritmi. FIFO (first-in, first-out) -sivun korvausalgoritmi on pienikokoinen algoritmi, joka vaatii vähän kirjanpitoa käyttöjärjestelmältä . Ajatus on ilmeinen nimestä - käyttöjärjestelmä seuraa kaikkia muistissa olevia sivuja jonossa, viimeisin saapuminen takana ja vanhin saapuminen edessä. Kun sivu on vaihdettava, jonon edessä oleva sivu (vanhin sivu) valitaan. Vaikka FIFO on halpa ja intuitiivinen, se toimii huonosti käytännön sovelluksissa. Siksi sitä käytetään harvoin muuttamattomassa muodossaan. Tämä algoritmi kokee Béládyn poikkeavuuden . Yksinkertaisesti sanottuna, sivuvirheessä pisin muistissa ollut kehys korvataan.

VAX/VMS -käyttöjärjestelmä käyttää FIFO -sivunvaihtoalgoritmia tietyin muutoksin. Osittainen toinen mahdollisuus annetaan ohittamalla rajoitettu määrä merkintöjä, joissa on kelvolliset käännöstaulukon viittaukset, ja lisäksi sivut siirretään prosessityöjoukosta koko järjestelmän kokoiseen pooliin, josta ne voidaan palauttaa, jos niitä ei ole jo käytetty uudelleen.

FIFO on konservatiivinen algoritmi, joten se on kilpailukykyinen. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Toinen mahdollisuus

FIFO-sivunvaihtoalgoritmin muutettu muoto, joka tunnetaan nimellä toisen mahdollisuuden sivunvaihtoalgoritmi, toimii suhteellisen paremmin kuin FIFO pienin kustannuksin parannuksesta. Se toimii katsomalla jonon etuosaa FIFOn tapaan, mutta sen sijaan, että sivua haetaan heti, se tarkistaa, onko viitattu bitti asetettu. Jos sitä ei ole asetettu, sivu vaihdetaan. Muussa tapauksessa viitattu bitti tyhjennetään, sivu lisätään jonon takaosaan (ikään kuin se olisi uusi sivu) ja tämä prosessi toistetaan. Tätä voidaan ajatella myös pyöreänä jonona. Jos kaikilla sivuilla on viitattu bittiasetuksensa, luettelon ensimmäisen sivun toisella kohtaamisella kyseinen sivu vaihdetaan, koska sillä on nyt viitattu bitti. Jos kaikkien sivujen viitebitti on tyhjennetty, toisen mahdollisuuden algoritmi rappeutuu puhtaana FIFO: na.

Kuten nimestä voi päätellä, Second-mahdollisuus antaa jokaiselle sivulle "toisen mahdollisuuden"-vanha sivu, johon on viitattu, on todennäköisesti käytössä, eikä sitä tule vaihtaa uuden sivun päälle, johon ei ole viitattu.

Kello

Kello on tehokkaampi versio FIFOsta kuin toinen mahdollisuus, koska sivuja ei tarvitse työntää jatkuvasti luettelon takaosaan, mutta se suorittaa saman yleisen tehtävän kuin toinen mahdollisuus. Kelloalgoritmi pitää pyöreän luettelon sivuista muistissa, jolloin "käsi" (iteraattori) osoittaa luettelon viimeistä tutkittua sivukehystä. Kun sivuvika ilmenee eikä tyhjiä kehyksiä ole, R (viitattu) -bitti tarkastetaan käden sijainnissa. Jos R on 0, uusi sivu asetetaan "käden" osoittaman sivun tilalle ja käsi siirtyy yhden askeleen eteenpäin. Muussa tapauksessa R -bitti tyhjennetään, kellokelloa lisätään ja prosessi toistetaan, kunnes sivu korvataan. Tämän algoritmin kuvasi ensimmäisen kerran vuonna 1969 FJ Corbató .

Kellon vaihtoehdot

• GCLOCK: Yleistetty kellosivun korvausalgoritmi.
• Clock-Pro pitää pyöreän luettelon äskettäin viitattujen sivujen tiedoista, mukaan lukien kaikki muistissa olevat M-sivut sekä viimeisimmät sivut, jotka on haettu. Nämä lisätiedot sivutetuilla sivuilla, kuten ARC: n ylläpitämät vastaavat tiedot , auttavat sitä toimimaan paremmin kuin LRU suurissa silmukoissa ja kertaluonteisissa skannauksissa.
• WSclock. Yhdistämällä Kello -algoritmi työjoukon käsitteeseen (eli sivusarjaan, jota kyseinen prosessi käyttää tietyn ajanjakson aikana), algoritmin suorituskykyä voidaan parantaa. Käytännössä "ikääntymisen" algoritmi ja "WSClock" -algoritmi ovat luultavasti tärkeimpiä sivunvaihtoalgoritmeja.
• Clock with Adaptive Replacement (CAR) on sivunvaihtoalgoritmi, jonka suorituskyky on verrattavissa ARC : iin ja joka ylittää huomattavasti sekä LRU: n että kellon. CAR-algoritmi virittää itseään eikä vaadi käyttäjän määrittämiä taikuusparametreja.

CLOCK on konservatiivinen algoritmi, joten se on kilpailukykyinen. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Vähiten äskettäin käytetty

Vähiten äskettäin käytetty (LRU) sivunvaihtoalgoritmi, vaikkakin nimeltään samanlainen kuin NRU, eroaa siinä, että LRU seuraa sivun käyttöä lyhyen ajan, kun taas NRU tarkastelee vain viimeisen kellovälin käyttöä. LRU työskentelee ajatuksen mukaan, että sivuja, joita on käytetty eniten viime aikoina, käytetään todennäköisesti voimakkaasti myös seuraavissa ohjeissa. Vaikka LRU voi tarjota teoriassa lähes optimaalisen suorituskyvyn (melkein yhtä hyvä kuin mukautuva korvaava välimuisti ), sen toteuttaminen käytännössä on melko kallista. Tälle algoritmille on olemassa muutamia toteutustapoja, jotka yrittävät alentaa kustannuksia ja kuitenkin pitää mahdollisimman paljon suorituskykyä.

Kallein menetelmä on linkitetty luettelomenetelmä, joka käyttää linkitettyä luetteloa, joka sisältää kaikki muistissa olevat sivut. Tämän luettelon takana on vähiten käytetty sivu, ja edessä on viimeksi käytetty sivu. Tämän toteutuksen hinta on se, että luettelon kohteita on siirrettävä jokaisen muistiviittauksen ympärille, mikä on hyvin aikaa vievä prosessi.

Toinen menetelmä, joka vaatii laitteistotukea, on seuraava: oletetaan, että laitteistossa on 64-bittinen laskuri, jota lisätään jokaisen käskyn yhteydessä. Aina kun sivua avataan, se saa arvon, joka on yhtä suuri kuin laskuri sivun käytön aikana. Aina kun sivu on vaihdettava, käyttöjärjestelmä valitsee sivun, jolla on pienin laskuri, ja vaihtaa sen.

Toteutuskustannusten vuoksi voidaan harkita (kuten seuraavat) algoritmeja, jotka ovat samanlaisia ​​kuin LRU, mutta jotka tarjoavat halvempia toteutuksia.

Yksi LRU -algoritmin tärkeä etu on, että se soveltuu täydelliseen tilastolliseen analyysiin. On esimerkiksi osoitettu, että LRU ei voi koskaan aiheuttaa yli N-kertaa enemmän sivuvirheitä kuin OPT-algoritmi, jossa N on verrannollinen hallinnoidun poolin sivumäärään.

Toisaalta LRU: n heikkous on se, että sen suorituskyky pyrkii heikentymään monien melko yleisten viitemallien alla. Jos esimerkiksi LRU -varannossa on N sivua, sovellus, joka suorittaa silmukan N + 1 -sivuryhmän yli, aiheuttaa sivuvian jokaisessa käyttökerrassa. Koska silmukat suurten matriisien yli ovat yleisiä, LRU: n muuttamiseen on pyritty paljon toimimaan paremmin tällaisissa tilanteissa. Monet ehdotetuista LRU -muunnoksista yrittävät havaita silmukointireferenssimallit ja siirtyä sopivaan korvausalgoritmiin, kuten viimeksi käytetty (MRU).

Vaihtoehdot LRU: sta

1. LRU-K häätää sivun, jonka viimeisin K-käyttöoikeus on kauimpana aiemmin. Esimerkiksi LRU-1 on yksinkertaisesti LRU, kun taas LRU-2 poistaa sivut niiden viimeisen käyttöajan mukaan. LRU-K parantaa merkittävästi LRU: ta paikallisuuden suhteen ajoissa.
2. ARC algoritmi ulottuu LRU ylläpitämällä historian äskettäin häätää sivuja ja käyttää tätä muutosta etusija viime tai usein pääsy. Se on erityisen kestävä peräkkäisille skannauksille.

ARC: n vertailu muihin algoritmeihin (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) löytyy julkaisusta Megiddo & Modha 2004.

LRU on merkintäalgoritmi, joten se on kilpailukykyinen. ${\ displaystyle {\ tfrac {k} {k-h+1}}}$

Satunnainen

Satunnainen korvausalgoritmi korvaa satunnaisen sivun muistissa. Tämä poistaa sivuviittausten yleiskustannukset. Yleensä se toimii paremmin kuin FIFO, ja muistiviittausten silmukointi on parempi kuin LRU, vaikka yleensä LRU toimii paremmin käytännössä. OS/390 käyttää maailmanlaajuista LRU -lähentämistä ja palaa satunnaiseen korvaamiseen, kun LRU: n suorituskyky heikkenee, ja Intel i860 -prosessori käytti satunnaista korvauskäytäntöä (Rhodehamel 1989).

Ei usein käytetty (NFU)

Ei usein käytetty (NFU) sivunvaihtoalgoritmi vaatii laskurin, ja jokaisella sivulla on yksi oma laskuri, joka on alun perin asetettu arvoon 0. Kullakin kellojaksolla kaikkien sivujen välillä, joihin on viitattu tällä aikavälillä, lisätään laskuria 1. Käytännössä laskurit seuraavat, kuinka usein sivua on käytetty. Näin ollen sivu, jolla on pienin laskuri, voidaan vaihtaa tarvittaessa.

NFU: n suurin ongelma on se, että se seuraa käyttötaajuutta ottamatta huomioon käyttöaikaa. Siten monikierroksisessa kääntäjässä sivut, joita käytettiin voimakkaasti ensimmäisen kierroksen aikana, mutta joita ei tarvita toisessa vaiheessa, ovat suosituimpia kuin sivut, joita käytetään toisessa vaiheessa verrattain kevyesti, koska niillä on korkeammat taajuuslaskurit. Tämä johtaa huonoon suorituskykyyn. On olemassa muita yleisiä skenaarioita, joissa NFU toimii samalla tavalla, kuten käyttöjärjestelmän käynnistys. Onneksi samanlainen ja parempi algoritmi on olemassa, ja sen kuvaus seuraa.

Usein käytetty sivunvaihtoalgoritmi tuottaa vähemmän sivuvirheitä kuin vähiten käytetty sivunvaihtoalgoritmi, kun sivutaulukko sisältää nollaosoittimen arvot.

Ikääntyminen

Ikääntymisalgoritmi on NFU -algoritmin jälkeläinen, ja siihen on tehty muutoksia, jotta se olisi tietoinen käytön ajanjaksosta. Sen sijaan, että vain lisättäisiin viitattujen sivujen laskureita ja korostettaisiin yhtä paljon sivuviittauksia ajasta riippumatta, sivun viitelaskuria siirretään ensin oikealle (jaettuna 2: lla), ennen kuin lisätään viitattu bitti kyseisen binääriluvun vasemmalle puolelle. Jos esimerkiksi sivulla on viitattu bitteihin 1,0,0,1,1,0 kuuden viimeisen kellopisteen kohdalla, viitattu laskuri näyttää tältä: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Sivuviittaukset lähempänä tällä hetkellä on enemmän vaikutusta kuin sivuviittaukset kauan sitten. Tämä varmistaa, että sivut, joihin on viitattu viime aikoina, vaikkakin harvemmin viitattuja, ovat korkeammalla prioriteetilla kuin sivut, joihin viitataan aiemmin. Näin ollen, kun sivu on vaihdettava, valitaan sivu, jolla on pienin laskuri.

Seuraava Python -koodi simuloi ikääntymisalgoritmia. Laskurit alustetaan${\ displaystyle V_ {i}}$0 ja päivitetty edellä kuvatulla tavalla käyttämällä aritmeettisia siirtooperaattoreita . ${\ displaystyle V_ {i} \ leftarrow (R_ {i} \ ll (k-1)) | (V_ {i} \ gg 1)}$

from collections.abc import Sequence

def simulate_aging(Rs: Sequence, k: int) -> None:
    """Simulate aging."""
    print(' t  |  R-bits (0-{length})        |  Counters for pages 0-{length}'.format(length=len(Rs)))
    Vs = [0] * len(Rs[0])
    for t, R in enumerate(Rs):
        Vs[:] = [R[i] << k - 1 | V >> 1
                 for i, V in enumerate(Vs)]
        print('{:02d}  |  {}  |  [{}]'.format(t, R,
                                              ', '.join(['{:0{}b}'.format(V, k)
                                                         for V in Vs])))

Esitetyssä esimerkissä R-biteistä 6 sivulle yli 5 kellopistettä, toiminto tulostaa seuraavan tulosteen, jossa luetellaan kunkin kellokentän t R-bitit ja yksittäiset laskurin arvot jokaiselle sivulle binääriesityksessä . ${\ displaystyle V_ {i}}$

>>> Rs = [[1,0,1,0,1,1], [1,1,0,0,1,0], [1,1,0,1,0,1], [1,0,0,0,1,0], [0,1,1,0,0,0]]
>>> k = 8
>>> simulate_aging(Rs, k)
 t  |  R-bits (0-5)        |  Counters for pages 0-5
00  |  [1, 0, 1, 0, 1, 1]  |  [10000000, 00000000, 10000000, 00000000, 10000000, 10000000]
01  |  [1, 1, 0, 0, 1, 0]  |  [11000000, 10000000, 01000000, 00000000, 11000000, 01000000]
02  |  [1, 1, 0, 1, 0, 1]  |  [11100000, 11000000, 00100000, 10000000, 01100000, 10100000]
03  |  [1, 0, 0, 0, 1, 0]  |  [11110000, 01100000, 00010000, 01000000, 10110000, 01010000]
04  |  [0, 1, 1, 0, 0, 0]  |  [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]

Huomaa, että ikääntyminen eroaa LRU: sta siinä mielessä, että ikääntyminen voi seurata vain viimeisimpiä viittauksia 16/32 (prosessorin kokonaislukujen bittikoosta riippuen) aikavälejä. Näin ollen kahdella sivulla on saattanut viitata 00000000: n laskureihin, vaikka yhdelle sivulle viitattiin 9 aikaväliä ja toisille 1000 aikaväliä sitten. Yleisesti ottaen viimeisen 16 välin käytön tunteminen riittää tekemään hyvän päätöksen siitä, mikä sivu vaihdetaan. Siten ikääntyminen voi tarjota lähes optimaalisen suorituskyvyn kohtuulliseen hintaan.

Pisin etäisyys ensin (LDF) -sivun korvausalgoritmi

Tämän algoritmin perusidea on referenssialue, jota käytetään LRU: ssa, mutta ero on siinä, että LDF: ssä paikannus perustuu etäisyyteen eikä käytettyihin viittauksiin. Vaihda LDF: ssä sivu, joka on kauimpana nykyisestä sivusta. Jos kaksi sivua on samalla etäisyydellä, sivu, joka on nykyisen sivun vieressä kellon vastaisessa kiertossa, korvataan.

Toteutuksen yksityiskohdat

Tekniikat laitteistoille ilman viitebittiä

Monet edellä käsitellyistä tekniikoista olettavat, että jokaiselle sivulle liittyy viitebitti. Joillakin laitteilla ei ole tällaista bittiä, joten sen tehokas käyttö vaatii tekniikoita, jotka toimivat hyvin ilman sitä.

Yksi merkittävä esimerkki on VAX -laitteisto, jossa on käytössä OpenVMS . Tämä järjestelmä tietää, onko sivua muokattu, mutta ei välttämättä, jos sivu on luettu. Sen lähestymistapa tunnetaan toissijaisena sivuvälimuistina. Työsarjoista (yleensä prosessin yksityinen muisti) poistetut sivut sijoitetaan erikoisluetteloihin, kun ne ovat fyysisessä muistissa jonkin aikaa. Sivun poistaminen toimivasta joukosta ei ole teknisesti sivunvaihtotoimenpide, mutta se tunnistaa sivun ehdokkaana. Sivu, jonka taustavarasto on edelleen voimassa (jonka sisältö ei ole likainen tai jota ei muuten tarvitse säilyttää), sijoitetaan vapaiden sivujen luettelon loppuun. Sivu, joka vaatii kirjoittamisen taustakauppaan, lisätään muokattujen sivujen luetteloon. Nämä toiminnot käynnistyvät yleensä, kun vapaiden sivujen luettelon koko laskee alle säädettävän kynnyksen.

Sivut voidaan valita työkokonaisuuden poistamiseksi oleellisesti satunnaisesti, sillä odotuksella, että jos tehdään huono valinta, tuleva viittaus voi noutaa kyseisen sivun vapaasta tai muokatusta luettelosta ennen kuin se poistetaan fyysisestä muistista. Tällä tavalla viitattu sivu poistetaan Ilmainen- tai Muokattu -luettelosta ja asetetaan takaisin prosessityöryhmään. Muokattu sivuluettelo tarjoaa lisäksi mahdollisuuden kirjoittaa sivuja taustakauppaan useamman kuin yhden sivun ryhmissä, mikä lisää tehokkuutta. Nämä sivut voidaan sitten sijoittaa ilmaisten sivujen luetteloon. Vapaiden sivujen luettelon päähän kulkeva sivujärjestys muistuttaa LRU- tai NRU-mekanismin tuloksia ja kokonaisvaikutelmassa on samankaltaisuuksia kuin aiemmin kuvattu Second-Chance -algoritmi.

Toinen esimerkki on käyttävät Linux-ytimen päälle ARM . Laitteisto-ominaisuuksien puute korvataan tarjoamalla kaksi sivutaulukkoa-suorittimen alkuperäiset sivutaulukot, joissa ei ole viitattuja tai likaisia ​​bittejä , ja ohjelmiston ylläpitämät sivutaulukot, joissa vaaditut bitit ovat läsnä. Ohjelmiston ylläpitämän taulukon emuloidut bitit asetetaan sivuvirheiden mukaan. Sivuvirheiden saamiseksi toisen taulukon emuloitujen bittien poistaminen peruuttaa osan vastaavan sivun käyttöoikeuksista, mikä toteutetaan muuttamalla alkuperäistä taulukkoa.

Sivun välimuisti Linuxissa

Linux käyttää yhtenäistä sivuvälimuistia

• brkja nimettömät mmaped -alueet. Tämä sisältää kasan ja pino on käyttäjä-avaruus ohjelmia. Se on kirjoitettu vaihdettavaksi, kun sitä haetaan.
• Muut kuin nimettömät (tiedostojen tukemat) mmaped-alueet. Jos fyysinen sivu on muistissa eikä sitä ole muokattu yksityisesti, se jaetaan tiedoston välimuistin tai puskurin kanssa.
• Yhteinen muisti hankittu kautta shm_open.
• Tmpfs muistissa tiedostojärjestelmä; kirjoitettu vaihdettavaksi, kun se haetaan.
• Tiedoston välimuisti, mukaan lukien; kirjoitetaan taustalla olevaan lohkotallennustilaan (mahdollisesti puskurin läpi, katso alla), kun se haetaan.
• Lohkolaitteiden välimuisti, jota Linux kutsuu "puskuriksi" (ei pidä sekoittaa muihin rakenteisiin, joita kutsutaan myös puskureiksi, kuten joita käytetään putkissa ja puskureissa, joita käytetään sisäisesti Linuxissa); kirjoitetaan taustalla olevaan tallennustilaan, kun se haetaan.

Yhtenäinen sivuvälimuisti toimii pienimmillä sivukokoisilla yksiköillä, joita CPU tukee (4 KiB ARMv8: ssa , x86 ja x86-64 ), ja jotkut seuraavan suuren koon sivut (2 MiB x86-64 ), joita kutsutaan "valtaviksi sivuiksi" Linux. Sivun välimuistin sivut on jaettu aktiiviseen ja ei -aktiiviseen joukkoon. Molemmat sarjat pitävät LRU -sivuluettelon. Perustapauksessa, kun käyttäjätilaohjelma käyttää sivua, se asetetaan passiivisen joukon päähän. Kun sitä käytetään toistuvasti, se siirretään aktiiviseen luetteloon. Linux siirtää sivut aktiivijoukosta ei -aktiiviseen joukkoon tarpeen mukaan niin, että aktiivinen joukko on pienempi kuin ei -aktiivinen joukko. Kun sivu siirretään passiiviseen joukkoon, se poistetaan minkä tahansa prosessiosoitealueen sivutaulukosta poistamatta sitä fyysisestä muistista. Kun sivu poistetaan passiivisesta joukosta, se haetaan fyysisestä muistista. Luettelon "aktiivinen" ja "ei /proc/meminfo-aktiivinen" kokoa voidaan hakea kentistä "Aktiivinen", "Ei -aktiivinen", "Aktiivinen (anon)", "Ei -aktiivinen (anon)", "Aktiivinen (tiedosto)" ja "Ei -aktiivinen" (tiedosto) ".

Toimiva setti

Prosessin työjoukko on joukko sivuja, joita prosessi käyttää tietyn ajanjakson aikana.

"Työsarjamalli" ei ole sivun korvaava algoritmi suppeassa mielessä (se on itse asiassa eräänlainen keskipitkän aikavälin ajastin )

Viitteet

Lue lisää