Mäluhaldus

Taustast: masinkoodis programm on käsukoode ja mäluaadresse sisaldavate baitide jada. Töölepanekuks laetakse programmikood põhimällu. Probleem: kuidas tagada, et programmikoodis olevad viited mälupesadele vastaksid protsessile eraldatud mälu õigetele aadressidele.

Kõige lihtsam lahendus: nõuda, et programm laetakse mälus kindlasse, fikseeritud piirkonda. Sel juhul võib kompileerimisel tekitada nn. absoluutkoodi, kuhu on õigete mälupesade aadressid sisse kirjutatud. Seda lähenemist kasutati kõige esimeste programmide korral ning ka näiteks MS-DOS .com laiendiga programmide korral. Puuduseks on see, et töötamiseks peab programmikood paiknema alati ühes ja samas kohas, seega on mitme programmi korraga mälus hoidmine raskendatud (nõutavad piirkonnad võivad kattuda).

Järgmine lähenemine: nn.lükandkood, mille korral sidumine konkreetsete füüsiliste mälupesadega toimub programmi mällulaadimisel. Sel juhul võib sama programmi käivitamiseks laadida ta suvalisse kohta põhimälus. Probleemid: kuna multitöötluse korral laetakse mällu järjest uusi programme ning osad mälus olnud programmid lõpetavad töö, siis võib tekkida olukord, kus vaba mälu on suhteliselt väikeste tükkidena laiali. Kui programmi käivitamiseks on vaja talle eraldada terviklik mäluplokk, siis võib tekkida olukord, kus vaba mälu on põhimõtteliselt piisavalt, kuid programmi laadimiseks liiga väikeste plokkidena, nn. väline killustatus. 

Lahendusideed: a) võimaldada protsesside ümberpaigutamist töö käigus; b) võimaldada programmikood laadida laialipaiknevatesse mälupiirkondadesse.
Mõlema idee realiseerimiseks on kasulik lahutada loogiline mälu (mille aadressid on kirjas programmis) füüsilisest mälust (kus andmed tegelikult paiknevad). Programmi kood genereeritakse nii, nagu oleks programmile eraldatud piisavalt suur terviklik mälupiirkond alates mälupesast aadressiga 0. Kui CPU üritab pöörduda mingi programmi koodiga antud mälupesa poole, siis spetsiaalne riistvaraline seade, MMU (Memory Management Unit) tõlgib selle aadressi füüsilise mälu aadressiks. Programmikood ja CPU tegelevad loogilise mäluga, asjade tegelikku asukohta teab ainult MMU. Tõlkimine käigupealt. 

Lihtsaim võimalus töö käigus ümberpaigutamise võimaldamiseks: üks lisaregister, mille sisu liidetakse igale CPU poolt esitatud aadressile.

Mälu

MMU liidab lisaregistri

füüsiline aadress 28128

Loogiline aadress 128

CPU

28000

Mälu kaitseks lisatakse veel üks lisaregister (limiidiregister). Ennem loogilisele aadressile vastava mälupesa sisule juurdepääsu võimaldamist kontrollib MMU, kas loogiline aadress on limiidiregistri sisust väiksem. Kui ei ole, siis tekib katkestus ning op süsteem saab kontrolli enda kätte.
	Selle skeemi puuduseks on see, et ei võimalda protsessidel lihtsalt mälu ning alamprogramme jagada ning võimaldab ainult tervikliku mälupiirkonna eraldamist (seega on vaba mälu killustatus ikka probleemiks). Võimaldab küll pooleliolevaid protsesse mälus killustatuse vähendamiseks ümber paigutada, kuid see on tavaliselt liiga aeganõudev toiming.

Teine idee: leheküljed, mälupaneelid (frame). Füüsiline mälu jaotatud fikseeritud suurustega paneelideks (512Byte-16MB), mälu eraldatakse ainult paneelide kaupa. Loogiline aadress jaotatakse sama suurteks osadeks, nii et loogiline aadress koosneb lehekülje numbrist ja nihkest, füüsiline aadress aga paneeli numbrist ja nihkest. Iga protsessi jaoks on olemas tabel, kus on kirjas, millises füüsilise mälu paneelis protsessi leheküljed paiknevad. Riistvara tõlgib seda tabelit kasutades loogilised aadressid füüsilisteks.
Väline killustatus puudub: kuna programmikoodi leheküljed võivad paikneda suvalistes mälupaneelides (mis ei pea olema järjestikused), siis on piisava hulga vaba mälu olemasolus võimalik see ka protsessile eraldada. Tekib aga sisemine killustatus: kuna mälu eraldatakse ainult paneelide kaupa, siis üldjuhul eraldatakse vajalikust rohkem mälu (viimane eraldatud paneel jääb osaliselt kasutamata). Seega kasutamata mälu on, kuid op süsteem sellest ei tea. Keskmiselt jääb kasutamata pool paneeli mälu protsessi kohta, nii et protsentuaalselt on sisemine killustatus seda suurem, mida suuremad on mälupaneelid (ja leheküljed). Teisest küljest võib aga väikeste paneelide korral vaja minna väga suurt lehekülgede tabelit, mis samuti võtab mälu protsessidelt ära. Seega on kõige otstarbekam kasutada keskmise suurusega paneele. Praegu on kõige enam kasutatavateks paneelisuurusteks 4KB ja 8KB.
Kui lehekülgede tabel on põhimälus, siis ühe mäluaadressi sisu saamiseks läheb vaja kaks pöördumist: üks lehekülgede tabelist füüsilise aadressi leidmiseks ning teine sealt aadressilt andmete saamiseks. Kiirendamiseks hoitakse osa tabelist spetsiaalsetes kiiretes registrites.
	Kaitse: iga protsess saab pöörduda füüsilise mälu poole ainult lehekülgede tabeli kaudu, seega ei saa kasutada talle eraldamata mälu. Kui protsess proovib kasutada tabelis mitteolevat lehekülge, siis katkestus (invalid page fault). Op süsteemil on lihtne võimaldada mälu jagamist, selleks tuleb lihtsalt vastavate protsesside lehekülgede tabelisse sobivasse kohta kirjutada sama paneeli number.

Kolmas idee: segmenteerimine. Programm on loogiliselt jagatud mitmesugusteks funktsionaalselt terviklikeks osadeks (põhiprogramm, alamprogrammid, andmeplokk), mitte fikseeritud suurusega lehekülgedeks. Andmete ja alamprogrammide jagamisel on seda samuti loomulikum teha terviklike programmiosada ja andmeplokkide, mitte lehekülgede kaupa. Siit idee: eraldada mälu segmentide kaupa. Iga protsessi jaoks on selleks vaja segmentide tabelit, kus iga segmendi kohta on kirjas selle algusaadress füüsilises mälus ning eraldatud märupiirkonna suurus. Riistvaraliselt tähendab see, et on olemas palju registripaare, iga segmendi jaoks baasregister (eraldatud mäluploki algus) ning limiidiregister (suurus). Loogiline aadress koosneb sel juhul segmendinumbrist ja nihkest (mitmes bait alates segmendi algusest). MMU kontrollib limiidiregistrit kasutades, kas nihe on lubatav ning seejärel moodustab vastava segmendi baasregistrit kasutades füüsilise aadressi.
	Probleem: kuna programmi segmendid on erineva suurusega ja ülaltoodud lahendus võimaldab mälu eraldada terviklike plokkide kaupa (kuigi ühe programmi segmendid võivad olla füüsilises mälus laiali), tekib probleem välise killustatusega.

Segmenteerimine koos lehekülgedega. Nii segmenteerimisel kui ka lehekülgede kasutamisel (paging) on oma plussid ja miinused. Intel 80x86 ja Pentium protsessorid kasutava seetõttu kombineeritud lähenemist, kus segmendid on jaotatud omakorda lehekülgedeks. Ilma peenete detailide kirjeldamiseta käib mälu kasutamine järgneva skeemi kohaselt. Iga segmendi jaoks on oma lehekülgede tabel. Loogiline aadress koosneb segmendi numbrist ja nihkest. Segmentide jaoks hoitakse tabelit, kus on kirjas limiit ning vastava segmendi lehekülgede tabeli asukoht. Nihet võrreldakse limiidiga ning vajadusel tekib katkestus (kui nihe on limiidist suurem). Seejärel leitakse nihet kasutades segmendi vaadeldavale baidile vastava lehekülje number ja leheküljesisene nihe ning lehekülgede tabelist saadakse füüsilise mälu paneeli number, mille abil tekitatakse füüsilise mälu aadress.

Virtuaalmälu

Enamasti on programmil osi, mida  käivitatakse väga harva (näiteks eriolukordadega tegelevad alamprogrammid), samuti võivad programmis olla deklareeritud suured massiivid, millest kasutatakse enamasti ainult väikest osa. Seega tundub väga ahvatlevana võimalus jooksutada programme, millest ainult osa on põhimälus. Sel juhul oleks võimalik töötada ka programmidel, mis vajavad rohkem mälu, kui tegelikult arvutisüsteemis olemas on. Selle idee kasutamisel tekitatakse programmikood nii, nagu oleks see laetud terviklikku (kuitahes suurde) mälupiirkonda alates aadressist 0. Seda mälupiirkonda kutsutakse virtuaalseks mäluks. Programmi töötamisel paikneb osa tema virtuaalsest mälust põhimälus, osa aba kettaseadmel.
	Virtuaalmälu kasutamise eelised:
1.	Mittekasutatavat koodiosa ei paigutata põhimällu, seega programmi laadimise ning kettale saalimise aeg lüheneb
2.	Programmeerija ei pea muretsema selle üle, et kood tervikuna põhimällu mahuks. See lihtsustab oluliselt programmeerimist.
3.	On võimalik jooksutada rohkem programme (jooksutatavate programmide summaarne mäluvajadus võib olla füüsilisest mälust suurem)
Loomulikult on ka teatud probleeme, kuna op süsteemi töö muutub keerulisemaks ning on vaja lisatuge riistvara poolt.
	Virtuaalne mälu on tavaliselt realiseeritud nii, et lehekülgi saalitakse nõudmise korral (demand paging).

Lehekülgede saalimine nõudmise korral

Virtuaalmälu kasutamise korral on vaja eristada neid lehekülgi, mis on põhimälus nendest, mida parajasti hoitakse kettal. Selleks lisatakse lehekülgede tabelis paneeli numbrile lisabitt, nn. õige/vigane bitt (valid/invalid). Kui lehekülg on vigane, siis see võib tähendada kaht asja: programmil ei pruugi olla vastava numbriga lehekülge või paikneb see lehekülg parajasti kõvakettal. Kui käimasoleva protsessi mingi käsk üritab pöörduda lehekülje poole, mis on märgitud vigaseks, siis tekib katkestus (lehekülje viga, page fault) ning vabade mälupaneelide olemasolul toimuvad järgnevad tegevused:
1.	op süsteem kontrollib, kas tegu on illegaalse leheküljega või legaalse leheküljega, mis on parajasti välismälus. Esimesel juhul protsessi töö katkestatakse. Tavaliselt hoitakse infot kõvakettal olevate lehekülgede kohta protsessi kontrollplokis.
2.	Kui lehekülg oli legaalne, siis leitakse vaba mälupaneel
3.	Op. süsteem algatab vastava lehekülje andmete lugemise kõvakettalt leitud mälupaneeli
4.	Kui I/O on valmis, siis modifitseeritakse PCB andmeid ning lehekülgede tabelit näitamaks, et nõutud lehekülg on põhimälus
5.	op süsteem taaskäivitab protsessi sellest käsust alates, mis eelnevalt põhjustas katkestuse.
Kuna kettalt lugemine on põhimälu kasutamisest tunduvalt (sadu tuhandeid kordi) aeglasem, siis on tähtis, et lehekülje vigu tekiks väga harva.

Lehekülgede asendamise algoritmid

Võib juhtuda, et lehekülje vea tekkimisel op süsteem avastab, et nõutud lehekülg on kõvakettal, kuid vabu mälupaneele ei ole. Sel juhul peab op süsteem valima mingi mälupaneeli kettale kirjutamiseks ning seejärel sinna nõutud lehekülje lugemiseks. Tuntumad algoritmid on järgnevad:
1.	FIFO algoritm: asendatakse kõige kauem põhimälus olnud lehekülg. Tekitab suhteliselt palju vigu ning on võimalik nn. Belady anomaalia, kus mingi fikseeritud programmi jaoks võib kasutatavate mälupaneelide arvu suurenemisel tekkivate leheküljevigade arv mõnikord suureneda.
2.	Opimaalne algoritm: asendatakse lehekülg, mida tulevikus kõige hiljem jälle kasutatakse. Praktiliselt mitterealiseeritav, kasutatakse teiste algoritmidega võrdlemiseks.
3.	LRU (Least Recently Used) algoritm: asendatakse lehekülg, mida pole kõige kauem kasutatud. Nõuab realiseerimiseks riistvaralisi lisavahendeid lehekülgede kasutamise info hoidmiseks.
4.	Teise võimaluse algoritm (second chance): nõuab, et iga leheküljega oleks seotud bitt, mida muudetakse riistvara poolt vastava lehekülje kasutamise korral. Lehekülg valitakse asendamiseks FIFO algoritmi korral, kuid kui valitud lehekülge on kasutatud, siis antakse talle teine võimalus mälus olemiseks: nullitakse kasutamist näitav bitt, saabumisaeg muudetakse momendi ajaks ning otsitakse asendamisele minevat lehekülge teiste lehekülgede hulgast.
Mälu eraldamise algoritmid

Lisaks lehekülgede asendamise algoritmile peab op süsteemil olema ka algoritm mälu eraldamiseks. lihtsaimad võimalused: võrdne mälueraldamine ning proportsionaalne mälueraldamine. Viimasel juhul eraldatakse protsessidele mälu võrdeliselt nende suurusega.
	Mälueraldamise algoritmi tähtis aspekt on see, kas lehekülgede asendamine toimub globaalselt (ühe protsessi poolt nõutava lehekülje mällutoomiseks võidakse asendada mingi teise protsessi mälus olev lehekülg) või lokaalne (lehekülgede asendamine toimub ainult ühele protsessile eraldatud mälupaneelide piires). Globaalne asendamine võimaldab arvestada protsesside prioriteete (op süsteem võib kõrge prioriteediga protsessi lehekülje mällutoomiseks võtta mälu ära madalama prioriteediga protsessilt).

	Sõltuvalt protsessori tüübist  on iga arvutisüsteemi jaoks olemas minimaalne mälupaneelide arv, mida ühele protsessile võib eraldada. Näiteks kui mingi masinkoodi käsk kasutab kahte mäluaadressi, siis peab igale protsessile eraldama vähemalt kolm mälupaneeli, kuna sellise käsu täitmiseks peavad korraga mälus paiknema selle käsu koodi sisaldav mälulehekülg ning kummalegi aadressile vastavad leheküljed, mis võivad kõik olla erinevad.
	Kui protsessile on eraldatud vähem mälupaneele, kui ta aktiivselt kasutab, siis tekkib nn. visklemine (thrashing): protsess asendab pidevalt selliseid lehekülgi, mida tal kohe jälle vaja läheb. Sellega kaasneb selle protsessi töö tunduv aeglustumine (kuna kõvakettalt lugemine on aeglane). Kuna see protsess visklemise korral muudkui kasutav kõvaketast, siis aeglustub ka kõikide teiste protsesside töö, mis kõvaketast vajavad, seega aeglustub kogu süsteemi töö. Seega peab op. süsteem arvestama protsessi poolt aktiivselt kasutatavate paneelide arvu ning kui see on eraldatud paneelide arvust suurem, siis võimaluse korral eraldama rohkem mälupaneele või siis selle protsessi ajutiselt kettale saalima.
Aktiivse hulga mudel
Aktiivse hulga mudeli korral jätab op. süsteem etteantud numbri  korral meelde iga protsessi viimase  mälupöörduse korral kasutatud lehekülgede numbrite hulga, mida kutsutakse aktiivseks hulgaks. Op. süsteem eraldab selle mudeli kasutamise korral igale protsesile vähemalt niipalju mälupaneele, kui palju lehekülgi on aktiivses hulgas või kui see ei ole võimalik, siis valib välja protsessi, mida mälupaneelide vabastamiseks kettale saalida. Aktiivse hulga realiseerimisel on põhiraskuseks arvepidamine protsesside aktiivsete hulkade üle.
Leheküljevigade arvestamine visklemise vältimiseks
Kui op. süsteem peab arvet leheküljevigade kohta, siis on võimalik ette anda leheküljevigade sageduse ülemine ja alumine piir. Kui leheküljevigade arv tõuseb üle ülemise piiri, siis tuleb protsessile mälu juurde anda, alla alumise piiri langemisel võetakse mälupaneele aga ära.
Näide: Windows2000
Windows 2000 kasutab 4KB suuruseid lehekülgi. Mäluaadressid on 32-bitised, seega saab iga protsess kasutada kuni 4GB suurust virtuaalmälu. Igal protsessil on lehekülgede kataloog, kus on 1024 4-baidist kirjet, mis viitavad lehekülgede tabelitele, kus igaühes on 1024 4-baidist mälupaneeli aadressi. Igale protsessile eraldatakse algselt 30 mälupaneeli ning aktiivse hulga suuruseks loetakse samuti 30. Kui protsessil   tekib lehekülje viga, siis vabade paneelide olemasolul eraldatakse protsessile mälupaneel. Kui vabu paneele ei ole, siis võetakse FIFO algoritmi kohaselt paneele ära nendelt protsessidelt, mis kasutavad aktiivse hulga suurusest rohkem paneele. Windows2000 jälgib nende protsesside leheküljevigade sagedust, mis töötavad oma aktiivse hulga suurusele vastava paneelide arvuga ning vajadusel suurendab aktiivse hulga suurust. Kui leheküljevigade sagedus on väike, siis Windows2000 proovib mõnda lehekülge protsessilt ära näpata. Kui lehekülje näppamine vigu ei tekita, siis vastav mälupaneel vabastatakse ning protsessi aktiivse hulga suurust vähendatakse ühe võrra.