Sivuvirheen kovasta hinnasta johtuen suunnittelijat haluavat vähentää sivuvirheitä optimoimalla sivujen sijoittelua. Jos virtuaalisivu voidaan kuvata mille tahansa fyysiselle sivulle, käyttöjärjestelmä voi valita minkä sivun se haluaa korvata kun sivuvirhe tapahtuu. Esimerkiksi käyttöjärjestelmä voi käyttää kehittynyttä algoritmia valitessaan sivua jota ei tarvita pitkään aikaan. Virtuaalimuisti systeemi mahdollistaa siis virtuaalisivun kuvauksen mihin tahansa fyysiseen sivuun. Tätä kuvausta kutsutaan täysin assosiatiiviseksi (fully associative), koska mikä tahansa sivu voi assosioitua minkä tahansa fyysisen muistipaikan kanssa.

Jos sivu voi olla missä vain, tarvitaan mekanismi sen löytämiseen. Tämä mekanismi on nimeltään sivutaulu (page table). Muistissa oleva sivutaulu on indeksoitu virtuaalimuistin sivunumeron mukaan ja sisältää vastaavan fyysisen sivun numeron. Jokaisella ohjelmalla on oma sivutaulunsa, joka kuvaa ohjelman virtuaaliosoite avaruuden fyysiseen muistiin. Laitteistossa on rekisteri nimeltään sivutaulu rekisteri, joka osoittaa sivutaulun alun muistissa; tätä rekisteriä kutsutaan sivutaulu rekisteriksi. Kirjastoesimerkissä sivutaulua vastaisi kuvaus kirjan otsikoiden ja kirjaston paikkojen välillä. Oletetaan (aluksi) että sivutaulu on kiinteän kokoinen ja yhtenäinen alue muistia.

Kuva 13, “Sivutaulu” näyttää sivutaulu rekisterin, virtuaaliosoitteen, osoitetun sivutaulun. Validibittiä käytetään jokaiselle taulun alkiolle kuten välimuistissa. Jos bitti ei ole päällä, sivu ei ole fyysisessä muistissa ja sivuvirhe tapahtuu.

Kuva 13. Sivutaulu

Sivutaulu, ohjelmalaskuri ja rekisterit kuvaavat ohjelman tilan. Jos toisen ohjelman halutaan käyttää CPUta, tulee tämä tila säilyttää. Myöhemmin kun tila palautetaan, ohjelma voi jatkaa suoritustaan. Usein tilaa kutsutaan nimellä prosessi. Prosessi on aktiivi, jos se on CPUn omistuksessa, muuten se on ei-aktiivi. Yleensä riittää, että käyttöjärjestelmä lataa pelkän sivutaulu rekisterin.

Jos virtuaalisivun validibitti on pois päältä, syntyy sivuvirhe. Käyttöjärjestelmälle täytyy antaa kontrolli, mikä tehdään poikkeusmekanismilla. Kun käyttöjärjestelmä saa kontrollin, sen tulee hakea sivu seuraavalta hierarkiatasolta (yleensä kovalevyltä) ja päättää mihin pyydetty sivu tulee laittaa fyysisessä muistissa

Sivunumero itsessään ei yleensä kerro missä kohtaa levyllä sivu on. Kun prosessi käynnistetään, varataan levylle tila sen sivuja varten. Varauksen yhteydessä käyttöjärjestelmä luo tietorakenteen, joka kertoo missä kohtaa levyllä sivu on. Tämä rakenne voi olla osa sivutaulua tai se voi olla erillinen tietorakenne jota indeksoidaan kuten sivutaulua. Kuva 14, “Sivutaulu ja levy” esitetään sivutaulu, joka sisältää fyysisten sivujen numerot ja levyosoitteet.

Kuva 14. Sivutaulu ja levy

Jos kaikki sivut fyysisessä muistissa on käytössä, käyttöjärjestelmän tulee valita mikä sivu korvata. Koska sivuvirheiden määrä tulee minimoida, yleensä käyttöjärjestelmät valitsevat sivun jota ei (luultavasti) lähitulevaisuudessa tarvita. Paikallisuus ajassa periaatteen mukaan järjestelmät voivat käyttää kauiten käytettyä sivua (least recntly used, LRU). Esimerkiksi viimeksi käytetyt sivut (järjestyksessä) ovat 10, 12, 9, 7, 11, 10. Jos haetaan sivua 8 joka ei ole muistissa. LRU -sivu on 12, joten se korvataan 8:lla. Jos sitten seuraavakin haku aiheuttaa sivuvirheen, korvataan sivu 9, sillä se on LRU muistissa olevista sivuista.

Jotkin laitteet tarjoavat käyttöbitin (use bit) tai referenssibitin (reference bit), joka asetetaan aina kun sivua on käytetty. Järjestelmä säännöllisesti nollaa käyttöbittejä ja kirjaa ne, jotta se voi päätellä mihin sivuihin on koskettu tiettynä aikavälinä.

Välimuistissa hakuajan ero välimuistin ja päämuistinvälillä on kymmeniä syklejä, jonka vuoksi käytetään kirjoituspuskuria. Koska virtuaalimuistissa päämuistin ja kovalevyn nopeusero on satoja tuhansia syklejä, ei kirjoituspuskuria kannata rakentaa. Sen sijaan kirjoitukset sivuun kerätään yhteen ja kun sivu vaihdetaan, sivun sisältö kopioidaan takaisin levylle. Koska sivun kirjoitus on kuitenkin aikaavievää, sivuun liitetään bitti joka kertoo onko sivun sisältö muuttunut (dirty bit). Ainoastaan likaiset sivut kirjoitetaan takaisin levylle.

Sivutaulut ovat niin isoja että ne täytyy tallettaa päämuistiin. Tämä tarkoittaa että jokainen muistiviittaus vie vähintään kaksinkertaisen ajan: yksi viittaus fyysisen osoitteen hakuun ja toinen tiedon hakuun. Haun nopeutus luottaa sivutaulun viittauksen paikallisuuteen. Kun sivutaulunumeron käännöstä käytetään, sitä ilmeisesti tarvitaan lähitulevaisuudessa. Tämän vuoksi moderneissa koneissa on erityisvälimuisti jossa on viimeksi käytettyjä käännöksiä. Tätä osoitteenkäännös -välimuistia kutsutaan käännöshakutauluksi (translation-lookaside buffer, TLB).

TLB on välimuisti joissa on vain sivutaulukuvauksia. Siten jokainen TLB:n tagi sisältää osan virtuaalisesta sivunumerosta ja tieto-osa sisältää fyysisen sivunumeron. Koska sivutaulua ei enää tarvita joka viittaukseen, TLB:ssä on myös muita bittejä, kuten käyttöbittejä ja likaisuusbittejä.

Kuva 15, “TLB” on TLB- välimuisti.

Kuva 15. TLB

Joka viittauksessa katsotaan virtuaalisivun numero TLB:stä. Jos tulee osuma, fyysinen sivun numero käytetään osoitteen muodostukseen ja vastaava viittausbitti käännetään päälle. Jos prosessori on kirjoittamassa, myös likaisuusbitti käännetään päälle. Jos TLB:ssä tulee huti, tulee katsoa onko huti pelkästään TLB:een alueella, vai onko kyseessä myös sivuhuti. Koska TLB:ssä on paljon vähemmän alkioita kuin fyysisen muistin sivussa, TLB-huteja tulee suhteessa enemmän.

TLB-hudissa jos sivu on muistissa, käännös voidaan ladata sivutaulusta TLB:hen ja haku kokeilla uudelleen. Jos sivu ei ole muistissa, sivuvirhe tapahtuu ja asiasta kerrotaan käyttöjärjestelmälle. TLB virheet voidaan käsitellä joko laitteistolla tai ohjelmallisesti. Käytännössä niiden välillä ei ole suurta eroa, sillä molemmissa tarvitsee tehdä samat asiat.

Kun TLB huti tapahtuu ja puuttuva käännös on haettu sivutaulusta, tulee valita korvattava TLB alkio. Koska käyttö- ja likaisuusbitit ovat TLB:ssä, tulee kyseiset bitit kopioida takaisin sivutauluun ennen korvausta. Nämä bitit ovat ainoat osat TLB alkiossa jotka voivat muuttua. Takaisinkirjoitusstrategia (eli nämä bitit kirjoitetaan takaisin hutiaikana sen sijaan että kirjoitettaisiin aina kun niitä muutetaan) on varsin tehokas, sillä TLB:n hutiaste on pieni.

Tyypillisiä arvoja TLB: voisi olla

Paitsi nämä parametrit, myös käännösten kuvaus TLB:hen vaihtelee huomattavasti. Useat systeemit käyttävät täysin assosiatiivista TLB:tä koska siinä on pienempi hutiaste, lisäksi koska TLB on pieni ei täysin assosiatiivinen kuvaus ole kallista. Täysin assosiatiivista kuvausta käytettäessä korvattavan alkion valinta on vaikeata. Koska TLB hudit tapahtuvat useammin kuin sivuvirheet ja niiden tulee olla paljon halvempia, ei voida käyttää tehokkaita (ja kalliita) algoritmeja kuten sivuvirheillä. Jotkin TLB toteutukset tukevat LRU:ta laitteistolla, mutta LRU tuen hinta kasvaa TLB:n koon mukana.

Kuva 16. TLB ja välimuisti

Kuva 17. Lukeminen TLB:stä ja välimuistista

Parhaassa tapauksessa virtuaaliosoite käännetään TLB:ssä ja lähetetään välimuistiin mistä haluttu tieto löytyy, otetaan ja lähetetään CPU:lle. Pahimmassa tapauksessa viittaus voi epäonnistua kaikissa kolmessa muistihierarkian komponentissa: TLB:ssä, sivutaulussa ja välimuistissa. Seuraava esimerkki kuvaa tilannetta paremmin.

DECStation 3100:n kaltaisessa muistihierarkiassa jossa on TLB ja välimuisti, muistiviittaus voi kohdata kolme erityyppistä hutia: välimuistihuti, TLB-huti ja sivuvirhe. Tarkastellaan kaikkia mahdollisia kombinaatioita missä huti voi tapahtua.

Taulu 7, “Mahdolliset hutikombinaatiot” osoittaa mahdolliset tilanteet sekä voiko ne todella tapahtua.

Virtuaalimuisti ja välimuistisysteemit toimivat yhdessä kuin hierarkia, joten data ei voi olla välimuistissa ellei se ole esillä päämuistissa. Käyttöjärjestelmä on tärkeänä osallisena ylläpitämässä tätä hierarkiaa huuhtomalla (flush) sivun sisällön välimuistista kun se päättää siirtää sivun levylle. Saman aikaisesti käyttäjärjestelmä muuttaa sivutauluja ja TLB:tä, jotta viittaukset sivuun aiheuttavat sivuvirheen.

Taulu 7, “Mahdolliset hutikombinaatiot” olettaa että muistiosoitteet on käännetty fyysisiksi osoitteiksi ennen välimuistiin viittausta, Kuva 16, “TLB ja välimuisti” esittää kyseisen muistin organisaation. Tälläisessa totetuksessa välimuisti on fyysisesti indeksoitu ja fyysisesti tagitettu, eli sekä välimuistin indeksi etti tagi on fyysisiä eikä virtuaalisia osoitetteita. Tällaisessa systeemissä muistiviittaukseen kuluva aika, jos oletetaan osuma, sisältää sekä ajan TLB saantiin että välimuisti saantiin; nämä voidaan toki putkittaa.

Toinen vaihtoehto olisi, että CPU indeksoi välimuistia osoitteilla jotka ovat joko kokonaan tai ainakin osittain virtuaalisia. Tällaisessa muistissa tagit ovat virtuaaliosoitteita, eli muisti on virtuaalisesti indeksoitu ja virtuaalisesti tagitettu. Tällaisessa muistissa TLB:tä ei käytetä normaalissa välimuistiviittauksessa, koska välimuistia käytetään virtuaaliosoitteilla eikä osoitteita tarvitse kääntää fyysisiksi osoitteiksi. Välimuistihudin yhteydessä TLB:tä tarvitaan, jotta muistin fyysinen osoite saadaan selville.

Tällaisen muistin ongelmana on tilanne, missä muistipaikat on jaettu eri ohjelmien kesken (tästä puhutaan myöhemmin). Jos eri ohjelmilla on oma virtuaalinen osoite, eli alias, samalle muistipaikalle, voi tulla tilanne että sama muistipaikka on laitettu välimuistiin kahteen eri paikkaan. Tämän takia toinen ohjelma voi kirjoittaa omaan muistipaikkaansa ilman että toinen ohjelma tietää että sen osoitteessa oleva muistin olisi pitänyt muuttua. Tämä ongelma vaatii käyttöjärjestelmän ja mahdollisesti ohjelmaan tiettyjä muutoksia.

Yleinen kompromissi näiden kahden osoiteratkaisun välillä on käyttää välimuistia, joka on virtuaalisesti indeksoitu, mutta joka käyttää fyysisiä tageja. Cahcea ja TLB:tä käytetään rinnan ja TLB:n antamaa fyysistä osoitetta verratan fyysisen osoitteen tageihin.

Vaikkakin kullakin prosessilla on oma virtuaalinen muistiavaruutensa, fyysinen muisti on jaettu usean käyttäjän prosessin ja käyttöjärjestelmän kesken. Lisäksi ei ole suotavaa että prosessi voi kirjoittelee muitten ohjelmien muistiavaruuteen tai käyttöjärjestelmään. Lisäksi halutaan että ohjelma ei saa lukea toisen ohjelman muistia.

Jokaisella prosessilla on oma virtuaali muistiavaruus. Jos käyttöjärjestelmä pitää sivutaulut siten organisoituna että toisistaan riippumattomat virtuaalisivut kuvautuvat erillisiin fyysisiin sivuihin, prosessi ei saa pääsyä toisen prosessin sivuihin. Tämä vaatii sen että prosessi ei voi muuttaa sivutaulun kuvausta. Käyttöjärjestelmä voi vakuuttua tästä jos se ei anna käyttäjän prosessin muokata omia sivutaulujaan, vaikkakin käyttöjärjestelmä voi.

Jotta käyttöjärjestelmä voi suojauksen virtuaalimuistiin, laitteiston tulee tarjota ainakin seuraavat kolme ominaisuutta:

Näillä mekanismeilla käyttöjärjestelmä voi muuttaa sivutauluja samalla kun se voi estää käyttäjän prosessilta niiden muuttamisen.

Prosessit voivat haluata jakaa informaatiota rajoitetusti. Esimerkiksi käyttöjärjestelmä voi antaa käyttäjän prosessin lukea jotain tietoa prosessista, kuten ajoajan, mutta ei anna prosessin muuttaa tietoaan. Samoin kaksi käyttäjän prosessia voi haluta jakaa tietoa luettavaksi mutta ei kirjoitettavaksi. Vastaavasti useat systeemit tarjoavat mahdollisuuden erottaa sivun lukemisen ja kirjoittamisen ja suojata ne erikseen. Tämä toteutetaan joko kirjoitussuojaus bitillä tai erillisillä luku- ja kirjoitusbiteillä. Tämä bitti on osana jokaista sivutaulu alkiota ja tarkistetaan joka haulla.

Vaikka virtuaaliosoitteen kääntäminen fyysiseksi osoitteeksi on suoraviivaista kun kyseessä on TLB osuma, TLB hutien ja sivuvirheiden käsittely on monimutkaisempaa. TLB huti syntyy kun mikään TLB:n alkio ei vastaa virtuaalista osoitetta. TLB huti voi johtua kahdesta syystä:

Mistä tiedetään kummasta tilanteesta on kysymys? Katsotaan sivutaulusta puuttuvaa sivualkiota. Jos sen validibitti on päällä, sivu on muistissa ja alkio tuodaan TLB:hen. Jos validibitti ei ole päällä, vastaava sivu ei ole muistissa ja tuloksena on sivuvirhe. Jos bitti on päällä, fyysisen sivun numero haetaan sivutaulusta ja käytetään TLB -alkion luontiin. TLB -huti voidaan käsitellä joko ohjelmallisesti tai laitteistolla.

Sivuvirheen käsittely vaatii poikkeusmekanismia aktiivin prosessin keskeyttämiseen. Sivuvirhe havaitaan sen kellosyklin aikana jolloin muistiin viitattiin. Ohjelmalaskuri tallennetaan EPC:hen (exception program counter). Lisäksi sivuvirhe poikkeus tulee asettaa riittävän aikaisin, että tila (valvojatilaan) voidaan siirtää heti seuraavalla kellosyklillä virheen jälkeen. Muussa tapauksessa latauksen yhteydessä kohderekisterissä on väärä arvo.

Esimerkiksi käskyllä

lw $1, 0($1)

koneen tulee estää kirjoittaminen rekisteriin $1, muuten suoritusta ei voi käynnistää uudelleen sillä $1:n sisältö on tuhoutunut. Sama tilanne on tallennuksessa; kirjoitus tulee estää, kunnes osoitteen osoittama sivu on muistissa; tämä tehdään yleensä ottamalla kirjoituslinja pois päältä.

Kun käyttöjärjestelmä ryhtyy käsittelemään sivuvirhettä, se katsoo poikkeusrekisteriä virheen syyn selville saamiseksi. Koska poikkeus on sivuvirhe jonka käsittely on raskas operaatio, se tallettaa koko aktiivin prosessin tilan. Tämä sisältää yleisrekisterit, liukulukurekisterit, sivutaulun osoiterekisterin, EPC:n ja poikkeuksen syy -rekisterin. Jos sivuvirheen aiheutti käskyn osoite, virtuaaliosoite on EPC:ssä. Muussa tapauksessa virheen aiheuttavan osoitteen voi laskea EPC:n osoittaman käskyn kentistä (perusrekisteri ja siirtymäosoite).

Kun käyttöjärjestelmä tietää sivuvirheen aiheuttaneen virtuaaliosoitteen, sen tulee tehdä seuraavat kolme askelta:

Viimeinen askel vie miljoonia syklejä (kuten myös toinen mikäli sivu on likainen). Tämän vuoksi käyttöjärjestelmä yleensä antaa suoritusvuoron jollekin toiselle prosessille, kunnes levyn käsittely on valmis. Kun luku on valmis ja sivuvirheen prosessin suoritusvuoro tulee, käyttöjärjestelmä palauttaa sen tilan. Sitten käyttöjärjestelmä suorittaa käskyn joka palauttaa tilan käyttäjätilaan ja PC palautetaan.

Sinä aikana kun käyttöjärjestelmä on tallettamassa virheen aiheuttaneen prosessin tilaa, on se haavoittuva. Tämän vuoksi yleensä koneissa on mahdollisuus estää uusien poikkeusten syntyminen. Kun tila on tallennettu, keskeyksiä voidaan taas käsitellä.

Sivuvirheiden käsittely on vaikea toteuttaa seuraavista syistä: ne tapahtuvat keskellä käskyä, käskyä ei voi suorittaa loppuun ennen poikkeuksen käsittelyä ja poikkeuksen käsittelyn jälkeen käsky tulee pystyä käynnistämään uudestaan kuin mitään ei olisi tapahtunut.

Käskyn tekeminen uudelleen käynnistettäväksi (restartable) on melko helppoa MIPS™in kaltaisessa arkkitehtuurissa. Koska kukin käsky kirjoittaa ainoastaan yhden tietoalkion ja kirjoitus tapahtuu käskyn viimeisellä syklillä, voidaan käsky yksinkertaisesti estää tapahtumasta ja aloittaa suoritus alusta.

Koneissa joissa on monimutkaisempia käskyjä jotka käsittelevät useita muistipaikkoja (esimerkiksi muisti-muisti arkkitehtuurit) käskyjen tekeminen uudelleen käynnistettäviksi on paljon vaikeampaa. Yhden käskyn käsittely voi generoida useita sivuvirheitä keskellä käskyä. Esimerkiksi joissain koneissa on lohkonsiirto käskyt jotka käsittelevät tuhansia datasanoja. Sellaisissa koneissa käskyjä ei voi käynnistää alusta, kuten MIPS™-käskyjä. Sen sijaan käsky tulee keskeyttää ja jatkaa puolivälistä. Käskyn jatkaminen puolivälistä vaatii jonkin erikoistilan tallentamisen, keskeytyksen käsittelyn ja erikoistilan palauttamisen.

Virtuaalimuisti on nimi muistihierarkiatasolle joka hallitsee päämuistin ja levyn välisen välimuistin. Koska hudit, joita kutsutaan sivuvirheiksi ovat niin kalliita, useita tekniikoita käytetään virheasteen pienentämiseen: