Riadenie pamäte
V Kapitole 4 sme ukázali, ako CPU môže byť zdieľané množinou procesov. Vďaka plánovaniu CPU
môžeme vylepšiť využitie CPU aj rýchlosť odpovede počítača užívateľom. Avšak, aby sme to
zrealizovali, musíme uchovávať niekoľko procesov v pamäti; t.j. musíme zdieľať pamäť. V tejto
kapitole, budeme diskutovať o rôznych spôsoboch riadenia pamäte. Algoritmy na riadenie pamäte sa
menia od primitívnych k stránkovacím a segmentačným stratégiám. Každý prístup má svoje vlastné
výhody i nevýhody. Výber metódy na riadenie pamäte pre špecifický systém závisí od množstva
faktorov obzvlášť od hardvérového návrhu systému. Ako uvidíme, mnoho algoritmov požaduje
hardvérovú podporu.
1 Základy
V tejto sekcii poskytneme základné informácie o pamäti.
1.1 Pamäť
Pamäť je centrum operácií moderného počítačového systému. Pamäť pozostáva z veľkého poľa slov
alebo bajtov, každý má svoju vlastnú adresu. CPU vyberie inštrukcie z pamäte podľa hodnoty
čítača inštrukcií (Program Counter). Tieto inštrukcie môžu zapríčiniť ďalšie zavádzanie a ukladanie
dát na špecifické adresy pamäte. Typický cyklus vykonávania inštrukcií najskôr vyberie inštrukciu
z pamäte. Inštrukcia je potom dekódovaná a môže spôsobiť, že sa z pamäte vyberú operandy. Po tom,
ako inštrukcia bola vykonaná na operandoch, výsledok inštrukcie môže byť uložený späť do
pamäte. Pamäťová jednotka vidí len prúd adries pamäte; nevie, ako sú generované (čítačom
inštrukcií, indexáciou, priamo, nepriamo a tak ďalej) alebo čo reprezentujú (inštrukcie alebo dáta).
Preto môžeme ignorovať, ako adresa pamäte je generovaná programom. Zaujíma nás iba postupnosť
pamäťových adries generovaná bežiacim programom. Hlavná pamäť musí obsluhovať operačný
systém aj rôzne užívateľské procesy. Z toho dôvodu potrebujeme prideliť rôzne časti pamäte čo
najefektívnejšie. Pamäť je zvyčajne rozdelená na dve oblasti: jedna pre príslušný operačný systém a
jedna pre užívateľské procesy. Operačný systém môžeme umiestniť do vysokej, či nízkej pamäti.
Hlavným faktorom ovplyvňujúcim toto rozhodnutie je umiestnenie vektora prerušení. Pretože vektor
prerušení je často v nízkej pamäti, programátori zvyčajne umiestňujú operačný systém tiež do nízkej
pamäti. Preto v tomto texte budeme rozoberať iba situáciu, keď operačný systém sídli v nízkej
pamäti. Vývoj inej situácie je podobný.
1.2 Prideľovanie adries
Zvyčajne program je uložený na disku ako binárny spustiteľný súbor. Program musí byť prenesený
do pamäte a uložený vo vnútri procesu, aby sa mohol vykonať. Kolekcia procesov na disku, ktorá
čaká na prenesenie do pamäte, aby bola vykonaná, tvorí vstupný front. V závislosti na použitom
riadení pamäte, proces môže byť prenášaný medzi diskom a pamäťou počas svojho vykonávania.
Normálna procedúra je vybrať jeden z procesov vo vstupnom fronte a zaviesť tento proces do pamäte.
Počas vykonávania procesu, proces pristupuje k inštrukciám a dátam z pamäte. Napokon, proces
skončí a jeho pamäťový priestor je prehlásený ako voľný. Väčšina systémov dovoľuje užívateľskému
procesu sídliť v hociktorej časti fyzickej pamäte. Hoci adresovateľný priestor počítača začína na 0,
prvá adresa užívateľského procesu nemusí byť 0. Vo väčšine prípadov užívateľský program prejde
niekoľko krokov — niektoré z nich môžu byť nepovinné — skôr, ako je vykonaný (Obrázok 1).
Adresy môžu byť reprezentované rôznym spôsobom počas týchto krokov. Adresy v zdrojovom
programe sú spravidla symbolické adresy (tak ako počet). Kompilátor obvykle priradí (Bind) tieto
symbolické adresy k relokovateľným adresám (tak ako „14 bajtov od začiatku tohto modulu”).
Spojovací editor alebo zavádzač priradí tieto relokovateľné adresy k absolútnym adresám (napríklad
74014). Každé priradenie je mapovaním (zobrazením) z jedného adresovateľného priestoru do
druhého. Klasicky, priradenie inštrukcií a dát k adresám pamäte sa môže uskutočniť na hocijakom
kroku tejto cesty:
Studenovský: Operačné systémy 8 Pamäť 1
Čas kompilácie: Ak počas kompilácie viete, kde proces bude sídliť v pamäti, tak môže byť
generovaný absolútny kód. Napríklad, ak viete, že užívateľský proces začína na pozícii R, potom
generovaný kompilačný kód bude začínať na tejto pozícii. Ak v neskoršom čase sa zmení
počiatočná adresa, potom bude nevyhnutné prekompilovať tento kód. MS–DOS
programy formátu .COM sú absolútne kódy určené v čase kompilácie.
Čas zavádzania: Ak v čase kompilácie nie je známe, kde proces bude uložený v pamäti,
potom kompilátor musí vygenerovať relokovateľný kód (premiestniteľný kód). V tomto prípade,
finálne prideľovanie adries je zadržané až do času zavádzania. Ak sa zmení počiatočná adresa,
potrebujeme len znovu zaviesť užívateľský kód s ohľadom na túto zmenenú hodnotu.
Čas vykonávania: Ak proces môže byť presunutý počas svojho vykonávania z jedného
pamäťového segmentu do druhého, tak prideľovanie adries musí byť zadržané až po čas behu.
Aby táto schéma fungovala, k dispozícii musí byť špeciálny hardvér, ako bude diskutované v
Sekcii 1.3. Väčšina univerzálnych operačných systémov používa túto metódu.
zdrojový
program
kompilátor
assembler
čas
kompilácie
object
modul
linkage editor iné
object
moduly
systémová
knižnica
dynamicky
zavedená
systémová
knižnica
Dynamické spájanie
spojovací editor
zavediteľn
ý modul
čas
zavádzania
zavádzač
loader
Vnútorný binárny
pamäťový obraz
čas vykonávania
Obrázok 1 Viackrokové spracovanie užívateľského programu.
Väčšia časť tejto kapitoly je vyčlenená na ukázanie, ako tieto rôzne prideľovania adries môžu byť
uskutočnené efektívne v počítačovom systéme a na diskusiu o príslušnej hardvérovej podpore.
Studenovský: Operačné systémy 8 Pamäť 2
1.3 Logický — verzus fyzický adresový priestor
Na adresu, ktorá je generovaná CPU sa zvyčajne odvolávame ako na logickú adresu, zatiaľ čo na
adresu, ktorú vidí jednotka na riadenie pamäte a register pamäťových adries sa zvyčajne odvolávame
ako na fyzickú adresu. Metódy na prideľovanie adresy v čase kompilácie a v čase zavádzania
generujú identické logické a fyzické adresy. Avšak, schéma na prideľovanie adresy v čase vykonania
má za následok odlíšenie logických a fyzických adries. Množina všetkých logických adries
generovaných programom je logický adresový priestor; množina všetkých fyzických adries
odpovedajúcich týmto logickým adresám je fyzický adresový priestor. Preto v schéme na
prideľovanie adresy v čase vykonania logický a fyzický adresový priestor sa líšia. Mapovanie z
logických do fyzických adries v čase vykonávania sa vykonáva hardvérovým zariadením nazývaným
jednotka riadenia pamäte (Memory Management Unit — MMU). Môžeme si vybrať spomedzi
množstva rozdielnych metód na vykonanie takého mapovania, ako diskutujeme v Sekciách 3 až 6.
Zatiaľ objasníme toto mapovanie na jednoduchej MMU schéme, ktorá je zovšeobecnením schémy
bázového registra popísanej v Kapitole 2 Sekcii 5.3.
MMU
Pamäť
relokačný
register
CPU
logická
adresa
346
14000
+
fyzická
adresa
14346
Obrázok 2 Dynamická relokácia s použitím relokačného registra.
Ako ilustruje Obrázok 2, táto metóda požaduje hardvérovú podporu nepatrne odlišnú od hardvérovej
konfigurácie prejednanej v Kapitole 2. Bázový register sa teraz nazýva relokačný
register. Hodnota v relokačnom registri sa pripočíta ku každej adrese generovanej užívateľským
procesom v čase, keď je posielaná do pamäte. Napríklad, ak báza je 14000, pokus užívateľa
adresovať pozíciu 0 je dynamicky relokovaný na pozíciu 14000; prístup k pozícii 346 je mapovaný
na pozíciu 14346. Operačný systém MS–DOS bežiaci na procesoroch rodiny Intel 80x86 používa
štyri relokačné registre pri zavádzaní a behu procesov. Užívateľský program nikdy nevidí reálne
fyzické adresy. Užívateľský program sa zaoberá
logickými adresami. Pamäť mapujúci hardvér konvertuje logické adresy na fyzické adresy. Takto,
teraz máme dva rozličné typy adries: logické adresy (v rozsahu od 0 do max) a fyzické adresy (v
rozpätí od R + 0 do R + max pre bázovú hodnotu R). Užívateľ generuje iba logické adresy a myslí si,
že proces beží na pozíciách od 0 do max. Užívateľský program dodáva logické adresy; tieto logické
adresy hardvér mapuje na fyzické adresy skôr, ako sú použité. Koncepcia, že logický adresový
priestor a fyzický adresový priestor sú separované, je hlavnou koncepciou pre vlastné riadenie
pamäte.
1.4 Dynamické zavádzanie
V našej diskusii sme sa dopracovali k tomu, že celý program a dáta procesu musia byť vo fyzickej
pamäti, aby sa vykonal proces. Veľkosť procesu je limitovaná kapacitou fyzickej pamäte. Aby sme
dosiahli lepšie využitie priestoru pamäte, môžeme použiť dynamické zavádzanie. S dynamickým
zavádzaním, procedúra nie je zavedená, až kým nie je volaná. Všetky procedúry sú uložené na
disku v relokovatelnej zavediteľnej forme. Hlavný program sa zavedie do pamäte a je
vykonávaný. Ak procedúra potrebuje zavolať inú procedúru, volajúca procedúra najprv skontroluje,
či tá druhá procedúra už bola zavedená. Ak nie, zavolá sa zavádzač, aby zaviedol požadovanú
procedúru do pamäte a aktualizoval tabuľky adries programu ako odzrkadlenie tejto zmeny. Potom
riadenie sa odovzdá tejto zavedenej procedúre.
Studenovský: Operačné systémy 8 Pamäť 3
Výhodou dynamického zavádzania je, že nepoužitá procedúra sa nikdy nezavedie. Táto metóda je
obzvlášť výhodná, keď je potrebné veľké množstvo kódu na manipuláciu v zriedkavých prípadoch,
ako sú chybové procedúry. V tomto prípade, hoci celková veľkosť programu môže byť veľká, časť,
ktorá je zavedená, môže byť oveľa menšia. Dynamické zavádzanie nevyžaduje špeciálnu podporu
operačného systému. Je na zodpovednosti užívateľov navrhovať svoje programy tak, aby využívali
takúto metódu. Operačné systémy môžu pomôcť programátorovi a to poskytovaním knižničných
procedúr na implementáciu dynamického zavádzania.
1.5 Dynamické spájanie a zdieľané knižnice
Obrázok 1 taktiež znázorňuje dynamicky spájané a zdieľané knižnice (Dynamic Linking Library
–– súbory .dll). Niektoré operačné systémy podporujú iba statické spájanie, kde systémové jazykové
knižnice sú spracované tak, ako každý iný cieľový (Object) modul a sú kombinované spojovacím
programom do binárneho obrazu programu. Koncepcia dynamického spájania je podobná ako u
dynamického zavádzania. Spájanie je odložené do doby vykonávania. Táto črta je zvyčajne
používaná pre systémové knižnice, ako aj jazykové knižnice procedúr. Bez tohoto prostriedku by
všetky programy v systéme potrebovali mať kópiu svojej jazykovej knižnice zahrnutú vo
vykonateľnom obraze. Táto požiadavka plytvá hlavnú pamäť. Pri dynamickom spájaní,
odkaz (Stub) je zahrnutý v binárnom obraze pre každý odkaz na procedúru z knižnice. Tento odkaz
je malý kus kódu, ktorý indikuje, ako lokalizovať príslušnú knižničnú procedúru v pamäti alebo
ako zaviesť knižnicu, ak procedúra nie je prítomná v pamäti. Keď je tento odkaz vykonávaný, on
kontroluje, či potrebná procedúra je už v pamäti. Ak nie, program zavedie procedúru do pamäte,
odkaz sa nahradí adresou procedúry a vykoná sa procedúra. Takto v nasledujúcom čase, knižničná
procedúra je vykonaná priamo, bez vynaloženia nákladov pre dynamické spájanie. Pri tejto schéme,
všetky procesy, ktoré používajú jazykovú knižnicu, vykonávajú iba jednu kópiu knižničného kódu.
Táto črta môže byť rozšírená na aktualizácie knižníc. Knižnica môže byť nahradená novou verziou a
všetky programy, ktoré na ňu odkazujú, budú automaticky používať novú verziu. Bez dynamického
spájania by všetky také programy potrebovali byť znovu spájané, aby dosiahli prístup k novej
knižnici. Aby programy vykonávali požadovanú verziu knižnice, tak informácia o verzii je zahrnutá
v oboch, v programe i knižnici. Viac ako jedna verzia knižnice môže byť zavedená do pamäte a
každý program používa svoju informáciu o verzii, aby vedel, ktorú kópiu knižnice použiť. Tento
systém je tiež známy ako zdieľané knižnice. Na rozdiel od dynamického zavádzania, dynamické
spájanie obvykle vyžaduje pomoc od operačného systému. Ak procesy v pamäti sú chránené jeden od
druhého, potom operačný systém je jedinou entitou, ktorá môže kontrolovať, či potrebná procedúra
je v pamäťovom priestore iného procesu alebo, ktorá môže dovoliť viacerým procesom pristupovať
na rovnaké adresy pamäte. Túto koncepciu rozvedieme v Sekcii 4.14.
1.6 Prekrývajúce segmenty
Aby sme umožnili procesu byť väčší, ako jemu pridelený rozsah pamäte, môžeme použiť
prekrývajúce segmenty (Overlay). Ideou prekrývajúcich segmentov je uchovávať v pamäti len tie
inštrukcie a dáta, ktoré sú potrebné na nejaký daný čas. Keď sú potrebné iné inštrukcie, oni sú
zavedené do priestoru predtým obsadeného takými inštrukciami, ktoré už nie sú potrebné. Ako
príklad, uvažujme dvojfázový assembler. Počas fázy 1, konštruuje tabuľku symbolov; potom, počas
fázy 2, generuje kód v strojovom jazyku počítača. Môžeme rozdeliť takýto assembler na kód fázy 1,
kód fázy 2, tabuľku symbolov a všeobecné podprogramy používané pri fáze 1 aj fáze 2.
Predpokladajme, že veľkosti týchto komponentov sú nasledujúce:
Fáza 1 70 KB Fáza 2 80 KB
Tabuľka symbolov 20 KB
Všeobecné podprogramy 30 KB
Studenovský: Operačné systémy 8 Pamäť 4
Aby sme zaviedli do pamäte všetko naraz, bude to vyžadovať 200 KB pamäte. Ak je k dispozícii len
150 KB, nemôžeme spustiť náš proces. Avšak, všimnime si, že fáza 1 a fáza 2 nemusia byť v pamäti
v tom istom čase. Takto si definujeme dva prekrývajúce segmenty: Prekrývajúci segment A je
tabuľka symbolov, všeobecné podprogramy a fáza 1 a prekrývajúci segment B je tabuľka symbolov,
všeobecné podprogramy a fáza 2. Pridáme ovládač na prekrývanie segmentov (10 KB).
Tabuľka symbolov
Všeobecné podprogramy
Ovládač prekrývania
Fáza 1 Fáza 2
Obrázok 3 Prekrývanie pre dvojprechodový assembler.
Začneme so segmentom A v pamäti. Po skončení fázy 1 prejdeme na ovládač prekrývania
segmentov, ktorý načíta segment B do pamäte, prepíše segment A, a potom odovzdá riadenie fáze 2.
Segment A potrebuje len 120 KB, zatiaľ čo segment B potrebuje 130 KB (Obrázok 3). Takto môžeme
spustiť náš assembler v 140 KB pamäti. Zavedie sa trocha rýchlejšie, pretože je potrebné preniesť
menej dát predtým, než začne vykonávanie. Avšak, bude bežať o trochu pomalšie kvôli extra I/O na
čítanie kódu pre prekrývajúci segment B, ktorým prekryje segment A. Kód pre prekrývajúci
segment A a kód pre prekrývajúci segment B sú uložené na disku ako absolútne pamäťové obrazy a
sú čítané ovládačom prekrývania, keď je to potrebné. Špeciálne relokačné a spájacie algoritmy sú
potrebné ku konštrukcii prekrývajúcich segmentov. Prekrývajúce segmenty nevyžadujú žiadnu
špeciálnu podporu od operačného systému. Môžu byť kompletne implementované programátorom
alebo kompilátorom s jednoduchými súborovými štruktúrami, čítajúce zo súborov do pamäte a
potom prejsť k tejto pamäti a vykonať nanovo prečítané inštrukcie. Na druhej strane programátor
musí navrhovať a naprogramovať štruktúru prekrývajúcich segmentov správne. Táto úloha môže byť
tvrdším orieškom, lebo vyžaduje kompletné vedomosti o štruktúre programu, jeho kóde a dátových
štruktúrach. Pretože program je samozrejme veľký, získavanie dostatočného porozumenia
programu môže byť ťažké. Kvôli týmto príčinám, použitie prekrývajúcich segmentov je súčasne
limitované na mikropočítače a systémy, ktoré majú malú pamäť a nedostatočnú podporu pre
rozvinutejšie metódy. Niektoré mikropočítačové kompilátory poskytujú programátorovi podporu pre
prekrývanie segmentov.
2 Swapovanie
Proces musí byť v pamäti, aby bol vykonaný. Avšak proces môže byť dočasne prenesený
(swapovaný) von z pamäte do záložného priestoru na disku a potom
prenesený späť do pamäte k pokračovaniu vykonávania. Napríklad,
predpokladajme time–sharing prostredie s „round–robin“
CPU–rozvrhovacím algoritmom. Keď skončí časové kvantum, správca
pamäti začne swapovať von proces, ktorý práve bežal na CPU a
swapovať dnu iný proces do pamäťového priestoru, ktorý bol uvoľnený
(Obrázok 4). Medzit ým plánovač CPU pridelí časové kvantum nejakému
inému procesu v pamäti. V ideálnom prípade môže správca pamäti
swapovať procesy dostatočne rýchlo, takže niektoré procesy budú v
pamäti pripravené na vykonanie, keď chce plánovač CPU znovu rozvrhnúť
C P U . K Operačný
v a n t u m Systém
musí byť dostatočne veľké, takže medzi swapovaniami sú
v y k o n a nUžívateľský
é r o z u mProces
npriestor
é m Pn o ž s t v Swap
á v ý pdnu
očtov.
Pamäť
Disk
1
Swap von
Proces P2
Obrázok 4 Swapovanie dvoch procesov s využitím disku ako záložného priestoru.
Studenovský: Operačné systémy 8 Pamäť 5
Variant tejto politiky swapovania je použitý v rozvrhovacích algoritmoch založených na prioritách.
Ak príde proces s vyššou prioritou a chce službu, správca pamäti môže swapovať von proces s nižšou
prioritou, takže môže zaviesť a vykonať proces s vyššou prioritou. Keď proces s vyššou prioritou
skončí, môže sa swapovať späť proces s nižšou prioritou a pokračovať v ňom. Tento variant
swapovania je niekedy nazývaný roll out, roll in. Normálne proces, ktorý je swapovaný von, bude
swapovaný späť na to isté pamäťové miesto, ktoré obsadzoval predtým. Toto obmedzenie je
diktované metódou prideľovania adries. Ak prideľovanie je vykonané v čase prekladu alebo
zavádzania, potom proces nemôže byť presunutý na iné miesta. Ak je prideľovanie adries robené v
čase vykonávania, potom môže byť proces swapovaný na iné pamäťové miesto, pretože fyzické
adresy sú vypočítané počas času vykonávania. Swapovanie potrebuje záložný priestor. Záložným
priestorom je bežne rýchly disk. Musí byť dostatočne veľký na zhromaždenie kópií všetkých
pamäťových obrazov pre všetkých užívateľov a musí poskytovať priamy prístup k týmto pamäťovým
obrazom. Systém udržiava front pripravených, obsahujúci všetky procesy, ktorých pamäťové
obrazy sú v záložnom priestore alebo v pamäti a sú pripravené na vykonanie. Kedykoľvek sa
plánovač CPU rozhodne vykonať proces, zavolá dispečera. Dispečer preskúma, či proces nasledujúci
vo fronte je v pamäti. Ak nie a nie je žiadna voľná pamäťová oblasť, dispečer swapuje von
momentálny proces v pamäti a swapuje dnu požadovaný proces. Potom znovu zavedie registre z
PCB ako normálne pri prepnutí kontextu a odovzdá riadenie zvolenému procesu.
Čas prepínania kontextu v takom swapovanom systéme je dosť vysoký. Na pochopenie času
prepínania kontextu, predpokladajme, že užívateľský proces má veľkosť 1 MB a záložným
priestorom je štandardný pevný disk s rýchlosťou prenosu 5 MB/s. Aktuálny prenos 1 MB procesu do
alebo z pamäti trvá 1MB / 5 MB za sekundu = 1/5 sekundy = 200 milisekúnd. Predpokladajme,
že žiadne nastavenia hlavičiek disku nie sú nutné a priemerná otáčacia doba trvá 8 milisekúnd, takže
čas swapovania je 208 milisekúnd. Pretože musíme swapovať von a swapovať dnu, celkový čas
swapovania je potom okolo 416 milisekúnd. Pre účinné využitie CPU chceme, aby bol čas
vykonávania pre každý proces dlhý v porovnaní s časom swapovania. Takže napríklad v
„round–robin“ CPU rozvrhovacom algoritme časové kvantum musí byť podstatne dlhšie ako 416
milisekúnd. Pamätajme, že hlavnou časťou času swapovania je čas prenosu. Celkový čas prenosu je
priamo úmerný množstvu swapovanej pamäti. Ak máme počítačový systém so 128 MB hlavnej
pamäti a príslušný operačný systém odoberá 5 MB, maximálna veľkosť užívateľských procesov je
123 MB. Ak 1 MB proces bol swapovaný von za 208 milisekúnd, tak 123 MB proces je
swapovaný von za 25 sekúnd. Preto by bolo užitočné vedieť presne, koľko pamäti užívateľský
proces využíva a nielen, koľko by mohol využívať. Preto musí užívateľ informovať systém o
akýchkoľvek zmenách
požiadaviek na pamäť. Takže proces musí vydávať systémové volania (request pamäť a
release pamäť), aby informoval operačný systém o meniacich sa požiadavkách na pamäť.
Swapovanie je tiež obmedzené aj inými faktormi. Ak chceme swapovať proces, musíme si
byť istí, že proces je úplne nečinný. Špeciálnym prípadom je každý nevyriešený I/O. Proces môže
práve čakať na I/O operáciu, keď ho chceme swapovať kvôli uvoľneniu jeho pamäti. Avšak, ak I/O
asynchrónne pristupuje k užívateľskej pamäti pre I/O bufre, potom proces nemôže byť swapovaný.
Dvomi hlavnými riešeniami tohto problému sú nikdy neswapovať proces s nevybaveným I/O alebo
vykonať I/O operácie len do bufrov operačného systému. Swapovací priestor je pridelený ako kus
disku, oddelený od súborového systému, takže jeho používanie je čo najrýchlejšie. V súčasnosti
štandardné swapovanie je používané v málo systémoch. Potrebuje príliš veľa swapovacieho času a
poskytuje príliš málo výkonného času na to, aby bolo rozumným riešením riadenia pamäte. Avšak
modifikované verzie swapovania sa nachádzajú v mnohých systémoch. Modifikácia swapovania je
použitá v mnohých verziách UNIX. Swapovanie je normálne vypnuté, ale začalo by, ak by veľa
procesov bežalo a používalo hraničné množstvo pamäte. Swapovanie by bolo zastavené, keď by
zavádzanie procesov v systéme bolo znížené. Prvým počítačom chýbal premyslený hardvér na
implementáciu viac rozvinutých metód riadenia pamäti, ale boli používané na bežanie viacerých
rozsiahlych procesov podľa modifikovanej verzie swapovania. Prvým príkladom je operačný systém
Microsoft Windows 3.1, ktorý podporuje súbežné vykonanie procesov v pamäti. Ak je zavedený
nový proces a je nedostatok hlavnej pamäti,
Studenovský: Operačné systémy 8 Pamäť 6
starý proces je swapovaný na disk. Tento operačný systém avšak neposkytuje plné swapovanie,
pretože užívateľ, radšej ako CPU plánovač, rozhoduje, kedy je čas uprednostniť jeden proces pred
druhým. Akýkoľvek swapovaný von proces zostane swapovaný, až kým ho užívateľ nevyberie na
bežanie. Nasledujúce Microsoft operačné systémy ako Windows NT využívajú výhodu
rozvinutých MMU čŕt, teraz nachádzajúcich sa dokonca na PC.
3 Súvislá alokácia pamäti
Zvyčajne chceme usídliť v pamäti niekoľko užívateľských procesov súčasne. Preto potrebujeme
zvážiť, ako prideliť voľnú pamäť procesom, ktoré čakajú vo vstupnom fronte na disku na prenesenie
do pamäti. Pri súvislej alokácii pamäti je každý proces obsiahnutý v jednej súvislej časti pamäti —
partícii.
3.1 Ochrana pamäti
Predtým, ako budeme preberať pridelenie pamäti, musíme prebrať kľúčový bod: ochranu pamäti —
ochrániť operačný systém od užívateľských procesov a užívateľské procesy jeden od druhého.
Ochranu môžeme poskytnúť použitím relokačného registra a limitného registra. Relokačný register
obsahuje hodnotu najmenšej fyzickej adresy partície (adresu začiatku partície); limitný register
obsahuje veľkosť partície. Napríklad relokácia = 100000 a limit = 74600. Každá logická adresa musí
byť menšia ako limitný register; MMU mapuje logickú adresu dynamicky pripočítaním hodnoty
relokačného registra. Táto mapovaná adresa je odoslaná do pamäti (Obrázok 5).
limitný register
relokačný register
pamäť
logická
adresa
CPU
<
áno nie
+
fyzická
adresa
Odlúčenie; chyba adresácie
Obrázok 5 Hardvérová podpora pre relokačný a limitný register.
Keď CPU plánovač vyberie proces na vykonanie, dispečer naplní relokačný a limitný register
korektnými hodnotami ako súčasť prepnutia kontextu. Pretože každá adresa generovaná CPU je
kontrolovaná voči týmto registrom, môžeme ochrániť operačný systém aj iné užívateľské programy a
dáta od zmeny týmto bežiacim procesom.
3.2 Pridelenie pamäti
Teraz sme pripravení vrátiť sa k prideleniu (alokácii) pamäti. Jednou z najjednoduchších metód
pridelenia pamäti je rozdeliť pamäť na niekoľko partícií (oblastí) pevnej dĺžky. Každá partícia
môže obsahovať presne jeden proces. Takže stupeň multiprogramovania je ohraničený počtom
partícií. V tejto metóde viacnásobných pevných partícií, keď partícia je voľná, proces je vybraný
zo vstupnej fronty a zavedený do voľnej partície. Keď proces skončí, partícia sa stane dostupnou
pre iný proces. Táto metóda bola originálne použitá u operačného systému IBM OS/360; už sa
viac nepoužíva.
Ďalej popísaná metóda sa nazýva metóda viacnásobných variabilných partícií; je používaná
primárne v dávkovom prostredí. Operačný systém obsahuje tabuľku ukazujúcu, ktoré časti pamäte
sú k dispozícii a ktoré sú obsadené. Na začiatku celá pamäť je k dispozícii užívateľským procesom a
je považovaná ako jeden veľký pamäťový blok, diera. Keď príde proces a potrebuje pamäť, hľadáme
dieru dostatočne veľkú pre tento proces. Ak ju nájdeme, pridelíme len toľko pamäti, koľko je treba,
ponechávajúc zvyšok k dispozícii na uspokojenie budúcich požiadaviek.
Studenovský: Operačné systémy 8 Pamäť 7
Keď procesy vstupujú do systému, sú vložené do vstupného frontu. Operačný systém berie do úvahy
pamäťové požiadavky každého procesu a množstvo dostupného pamäťového priestoru pri
rozhodovaní, ktorým procesom bude prideľovať pamäť. Keď procesu je pridelený pamäťový
priestor, proces je zavedený do pamäti a môže súperiť o CPU. Keď proces skončí, uvoľní pamäť,
ktorú operačný systém môže potom vyplniť iným procesom zo vstupného frontu. V nejakom danom
čase máme k dispozícii zoznam veľkostí dostupných blokov a vstupný front. Operačný systém môže
usporiadať vstupný front podľa nejakého algoritmu rozvrhovania. Pamäť je prideľovaná procesom zo
vstupného frontu, až kým nakoniec pamäťové požiadavky nasledujúceho procesu nemôžu byť
splnené; žiadny z dostupných blokov (alebo dier) nie je dostatočne veľký na uchovanie tohto
procesu. Operačný systém môže čakať, až kým nie je k dispozícii dostatočne veľký blok alebo môže
preskočiť vo vstupnom fronte a pozrieť sa, či nenájde iný proces s menšími pamäťovými
požiadavkami. Vo všeobecnosti množina dier rôznych veľkostí je rozptýlená v pamäti v danom čase.
Keď príde proces a potrebuje pamäť, systém hľadá v tejto množine dieru dostatočne veľkú pre tento
proces. Ak diera je príliš veľká, je rozdelená na dve: jedna časť je pridelená prichádzajúcemu
procesu; druhá je vrátená do množiny dier. Keď proces ukončí, uvoľní svoj blok pamäti, ktorý je
potom položený späť do množiny dier. Ak nová diera susedí s inými dierami, tieto susedné diery sú
zlúčené a vytvoria jednu väčšiu dieru. V tomto okamihu systém môže skontrolovať, či existujú
procesy čakajúce na pamäť a či by táto novo uvoľnená a pre usporiadaná pamäť mohla splniť
požiadavky niektorého z čakajúcich procesov. Táto procedúra je zvláštnym prípadom všeobecného
problému dynamického prideľovania pamäti, ktorý spočíva v tom, ako splniť požiadavku veľkosti
n zo zoznamu voľných dier. Existujú viaceré riešenia tohoto problému. Množina dier je prehľadaná
kvôli určeniu, ktorú dieru je najlepšie prideliť. Stratégie first–fit, best–fit a worst–fit sú tými
najbežnejšími na vyhľadanie voľnej diery z množiny dostupných dier.
First–fit: Prideliť prvú dieru, ktorá je dostatočne veľká. Hľadanie môže začať buď na začiatku
množiny dier alebo tam, kde skončilo predchádzajúce first–fit prehľadávanie. Hľadanie môžeme
zastaviť vtedy, keď nájdeme dostatočne veľkú voľnú dieru.
Best–fit: Prideliť najmenšiu dieru, ktorá je dostatočne veľká. Musíme prehľadávať celý zoznam,
pokiaľ nie je zoradený podľa veľkosti.
Worst–fit: Prideliť najväčšiu dieru. Musíme prehľadávať celý zoznam, pokiaľ nie je utriedený
podľa veľkosti.
Simulácie ukázali, že tak first–fit ako aj best–fit sú lepšie ako worst–fit, čo sa týka využitia pamäte.
Ani first–fit ani best–fit nie je jasne lepší vo využití pamäte, ale first–fit je rýchlejší.
3.3 Fragmentácia
Tieto algoritmy ale trpia externou fragmentáciou. Keď sú procesy zavádzané a odstraňované z
pamäte, voľný pamäťový priestor je rozbitý na malé kúsky. Externá fragmentácia je, keď existuje
dostatok celkového pamäťového priestoru na splnenie požiadavky, ale tento priestor nie je súvislý;
pamäť je rozdelená na veľké množstvo malých dier, takže tam nie je žiadna dostatočne veľká diera
pre splnenie požiadavky. Tento problém fragmentácie môže byť vážny. V najhoršom prípade by sme
mohli mať blok voľnej pamäti medzi každými dvoma procesmi. Výber first–fit alebo best–fit
stratégie môže ovplyvniť stupeň fragmentácie. First–fit je lepšia pre niektoré systémy, zatiaľ čo
best–fit je lepšia pre iné. Štatistická analýza first–fit ukazuje, že pri daných N pridelených blokoch
bude N/2 dier stratených kvôli fragmentácii. To znamená, že tretina pamäti môže byť nepoužiteľná!
Táto vlastnosť je známa ako 50-percentné pravidlo. Fragmentácia pamäti môže byť externá ako aj
interná. Predpokladajme, že proces požaduje 1002 bajtov a máme dieru 1004 bajtov. Ak pridelíme
presne požadovaný blok, ostane nám diera 2 bajty. Náklady na udržiavanie stopy tejto 2 bajtovej
diery budú podstatne väčšie ako úžitok z tejto diery. Všeobecný prístup spočíva v rozdelení fyzickej
pamäti na bloky pevnej dĺžky a pridelení pamäti, ktorej jednotka je rovná veľkosti bloku (napríklad 1
kB). Pomocou tohto prístupu môže byť pamäť pridelená procesu len nepatrne väčšia ako požadovaná
pamäť. Rozdiel týchto dvoch čísel je
interná fragmentácia — veľkosť pamäte, ktorá je interná v partícii, ale nie je
použitá.
Studenovský: Operačné systémy 8 Pamäť 8
Jedným riešením problému externej fragmentácie je kompakcia. Cieľom je presunúť obsahy pamäte,
aby sme mohli umiestniť všetku voľnú pamäť dokopy do jedného veľkého bloku. Kompakcia nie je
vždy možná. Ak relokácia je statická a je vykonávaná v čase prekladu alebo v čase zavádzania,
kompakcia nemôže byť urobená; kompakcia je možná len, ak relokácia je dynamická a prebieha v
čase vykonávania. Ak sú adresy relokované dynamicky, relokácia požaduje len presun programu a
dát a potom zmenu bázového registra na ukázanie novej bázovej adresy. Keď je kompakcia možná,
musíme určiť jej cenu. Najjednoduchší kompakčný algoritmus je jednoducho presunúť všetky
procesy smerom k jednému koncu pamäti; všetky diery presunúť opačným smerom, vytvárajúc
jednu veľkú dieru využiteľnej pamäti. Táto schéma môže byť drahá.
4 Stránkovanie
Stránkovanie je schéma riadenia pamäte, ktorá povoľuje, aby fyzický adresový priestor procesu bol
nesúvislý. Stránkovanie je bežne používané v mnohých operačných systémoch.
4.1 Základy stránkovania
Fyzická pamäť je rozdelená do blokov pevnej dĺžky nazývaných rámce. Logická pamäť je tiež
rozdelená do blokov rovnakej veľkosti nazývaných stránky. Dĺžku rámca a stránky označme r.
Keď proces má byť vykonaný, jeho stránky sú zavedené do nejakých voľných pamäťových rámcov
zo záložného úložiska. Prehľad o priradení rámcov stránkam procesu je držaný v tabuľke stránok
procesu (Obrázok 6). Záložné úložisko (disk) je tiež rozdelené do blokov dĺžky r.
page 0
page 1
page 2
page 3
logical
memor y
0
1
2
3
frame n0
umber 1
1
4
3
2
3
4
5
6
7
7
T
page 0
page 2
page 1
physical
m emory
page 3
Obrázok 6 Model stránkovania logickej a fyzickej pamäti.
4.2 Stránkovací hardvér
Hardvérová podpora pre stránkovanie je ilustrovaná na Obrázku 7. Každá logická adresa
generovaná CPU je rozdelená na dve časti: číslo stránky (Page) p a posunutie (Offset) d. Číslo
stránky je použité ako index v tabuľke stránok. Tabuľka stránok obsahuje číslo rámu f každej
stránky. Toto číslo rámu f je spojené (konkatenácia reťazcov) s ofsetom d na definovanie fyzickej
pamäťovej adresy, ktorá je odoslaná pamäťovej jednotke.
f
fyzická adresa logická
CPU
f 0000 ... 0000
adresa
f dp d
p
f 1111 ...
1111
f
tabuľka stránok
Obrázok 7 Stránkovací hardvér.
Studenovský: Operačné systémy 8 Pamäť 9
fyzická
pamäť
Veľkosť stránky r je definovaná hardvérom. Veľkosť stránky je mocninou 2, pohybuje sa medzi
512 bajtmi a 16 MB v závislosti od architektúry počítača. Výber mocniny 2 ako veľkosť stránky
uľahčuje preklad logickej adresy na číslo stránky a ofset stránky. Ak je veľkosť fyzickej pamäte 2
m
bajtov, potom
m-n vyšších
a veľkosť
stránky bitov
je 2 nlogickej adresy určujú číslo stránky a n nižších bitov určuje ofset
stránky. Teda, logická adresa vyzerá nasledovne:
4.3 Príklad
Ako konkrétny príklad uvažujme pamäť na Obrázku 8. S použitím 4–bajtovej veľkosti stránky
a 32–bajtovej fyzickej pamäti (8 rámcov) ukážeme, ako môže byť užívateľský pohľad na pamäť
5
do fyzickej
Najväčšia fyzická (aj logická) adresa môže byť 32 = 2
.mapovaný
Veľkosť stránky
r = 4pamäti.
=2
= m.
2
n
2
= . Odtiaľ vyplýva m = 5 a n = 2.
2 0, offset 0. V tabuľke stránok nájdeme, že stránka 0 je v rámci 5. Teda,
Logická adresa 0 je stránka
logická adresa 0 prislúcha fyzickej adrese 20 = 5*4+0. Logická adresa 3 (stránka 0, offset 3)
prislúcha fyzickej adrese 23 = 5*4+3. Logická adresa 4 je na stránke 1, offset 0; podľa tabuľky
stránok stránka 1 je mapovaná do rámca 6. Teda, logickej adrese 4 prislúcha fyzická adresa 24 =
6*4+0. Dedukujeme, že fyzická adresa a’= f r +
d.
0
0
a
Strana Rámec 0
1
1
b
2
2
c
3
0
3
d
0 5
4
ij
1
1
5
k
4
e
6
1
6
l
2
f
5
7
1
3
2
6
g
7
h
89
10
11
i
j
k
l
12
13
14
15
m
n
o
p
89
10
11
2
2
3
Tabuľka stránok
m
n
o
p
12
13
14
15
3
4
5
6
7
16
17
18
19
logická
pamäť
fyzická
pamäť
20
21
22
23
a
b
c
d
24
25
26
27
e
f
g
h
28
29
30
31
Obrázok 8 Príklad stránkovania pre 32–bajtovú pamäť s 4-bajtovými stránkami.
Logická adresa 13 je na stránke 3 ofset 1. Stránke 3 zodpovedá v tabuľke stránok rámec 2. Preto
logická adresa 13 je mapovaná k fyzickej adrese 9 = 2*4+1. Logická adresa 13 je binárne 01101. Z
toho prvých m–n = 5–2 = 3 bitov je 011 (číslo stránky = 3) a posledných n = 2 bitov je 01 (ofset =
1). Rámec 2 je binárne 010. Výslednú fyzickú adresu dostaneme konkatenáciou rámca 010 a ofsetu
01, čo je 01001 binárne a to je 9 dekadicky. Experimentálne, na jednej konkrétnej adrese sme
preverili, že stránkovací hardvér správne vypočíta fyzickú adresu.
4.4 Matematické poznanie stránkovania
Veľkosť stránky je r. Onačme a logickú adresu. Adresa a sa nachádza na strane p a má ofset d
(posunutie od začiatku strany). Preto a = p r + d. Odtiaľ vyplýva p = a / r, d = a % r. Označme T
tabuľku
. Označme
stránok.
a’ fyzickú
Potom
adresu,
stránka
ktorá
p jezodpovedá
umiestnenálogickej
vo fyzickej
adrese
pamäti
a. Táto
v rámci
fyzická
f =adresa
T
pje v rámci f a
má ofset d.
Preto a’ = fr + d. Na základe vyššie uvedeného matematického poznania metódy môžeme
navrhnúť nasledujúci algoritmus na výpočet fyzickej adresy. Pre danú logickú adresu a
vypočítame:
Studenovský: Operačné systémy 8 Pamäť 10
pa’= =a / frr +
d=
a % r f = Thardvér to počítap inak:
d Stránkovací
p d,
= kde
m – n jep roperácia
v ýc h b spájanie
i t o v a reťazcov.
d = n Je
p ovidieť,
s l e d nže
ýchardvér
h b i t o vsaavyhol
f =časovo
a’= f náročným
p
T
operáciám
násobenia a delenia. Dokážeme, že postup hardvéru je rovnaký ako vyššie uvedený algoritmus.
Dôkaz. Celočíselné delenie mocninou 10 a zvyšok v dekadickej sústave sa počíta nasledovne:
3574829 / 1000 = 3574 3574829 % 1000 = 829. Podobne sa počíta delenie mocninou 2 v binárnej
sústave: Napríklad: 01101 / 100 = 011 01101 % 100 = 01
, tak postup
To znamená,
pri výpočte
že ak m
podielu
miestne
p ačíslo
zvyšku
a delíme
d je nasledovný:
číslom r = 2
n
p = m–n prvých číslic a d = n posledných číslic a
4.5 Fragmentácia
Keď používame schému stránkovania nemáme externú fragmentáciu. Avšak, môžeme mať internú
fragmentáciu. Posledný pridelený rámec nemusí byť úplne plný. V priemernom prípade očakávame
vnútornú fragmentáciu pol stránky pre proces. V najhoršom prípade bude vnútorná fragmentácia
skoro celý rámec (na poslednej stránke bude len jeden bajt).
4.6 Veľkosť stránky
Táto úvaha o fragmentácii naznačuje, že sú vhodné malé veľkosti stránok. Na druhej strane je
želateľné mať malé tabuľky stránok a teda veľké veľkosti stránok. Treba vybrať kompromis. Dnes je
veľkosť stránok zvyčajne medzi 4 KB a 8 KB a niektoré systémy poskytujú ešte väčšie stránky.
Niektoré CPU dokonca podporujú viac veľkostí stránok. Napríklad Solaris používa 8 KB a 4 MB
veľkosti stránok v závislosti od dát uložených stránkami. Výskumníci teraz vyvíjajú rôzne podpory
pre plávajúce veľkosti stránok. Každá položka tabuľky stránok je zvyčajne 32 bitov dlhá. 32 bitová
položka môže ukazovať na jeden z 2
32
fyzických rámcov. Ak má rámec 29 = 512 B, potom tento systém môže adresovať 2 41
bajtov = 2 TB fyzickej pamäte (KB = 210 B, MB = 20 B, GB = 30 B, TB = 240 B).
2
2
4.7 Prideľovanie pamäti
Keď proces príde do systému na vykonanie, preskúma sa jeho veľkosť vyjadrená v stránkach. Každá
stránka procesu potrebuje jeden rámec. Teda, ak proces požaduje n stránok, v pamäti musí byť
dostupných aspoň n rámcov. Ak n rámcov je dostupných, sú pridelené tomuto prichádzajúcemu
procesu. Prvá stránka procesu je zavedená do jedného z pridelených rámcov a do tabuľky stránok pre
tento proces je vložené číslo tohoto rámca. Ďalšia stránka je zavedená do ďalšieho rámca, číslo
rámca je vložené do tabuľky stránok a tak ďalej (Obrázok 9 – pozor, chýba 14 v zozname voľných).
Obrázok 9 Voľné rámce. (a) Pred alokáciou. (b) Po alokácii.
Studenovský: Operačné systémy 8 Pamäť 11
4.8 Rôzne pohľady na pamäť
Dôležitým aspektom stránkovania je jasné rozlíšenie medzi užívateľovým pohľadom na pamäť a
aktuálnou fyzickou pamäťou. Užívateľský pohľad ukazuje túto pamäť ako jeden súvislý priestor
obsahujúci len tento jeden program. V skutočnosti užívateľský program je rozptýlený vo fyzickej
pamäti, ktorá obsahuje aj iné programy.
4.9 Tabuľka rámcov
Pretože operačný systém spravuje fyzickú pamäť, musí mať prehľad o detailoch pridelenia fyzickej
pamäte: ktoré rámce sú pridelené, ktoré rámce sú dostupné, koľko je celkovo rámcov a tak ďalej.
Tieto informácie sú vo všeobecnosti uložené v dátovej štruktúre nazývanej tabuľka rámcov.
Tabuľka rámcov má jednu položku pre každý rámec ukazujúcu, či je tento rámec voľný alebo
pridelený a ak je pridelený, ku ktorej stránke, ktorého procesu alebo procesov.
4.10 Manuálny výpočet fyzickej adresy
Ak užívateľ urobí systémové volanie a zadá ako parameter adresu, táto adresa musí byť mapovaná,
aby určila správnu fyzickú adresu. Operačný systém uchováva kópiu tabuľky stránok pre každý
proces. Táto kópia sa používa na preklad logických adries na fyzické adresy, kedykoľvek musí
operačný systém prideliť logickým adresám fyzické adresy manuálne.
4.11 Implementácia tabuľky stránok
Kópiu tabuľky stránok procesu využíva CPU dispečer na definovanie hardvérovej tabuľky stránok,
keď má byť proces pridelený procesoru. Z tohto dôvodu stránkovanie zvyšuje čas na prepnutie
kontextu. Každý operačný systém má vlastné metódy na uloženie tabuľky stránok. Väčšina
prideľuje tabuľku stránok pre každý proces. Ukazovateľ na tabuľku stránok je uložený v riadiacom
bloku procesu. Keď má dispečer štartovať proces, musí v rámci prepnutia kontextu definovať
správne hodnoty hardvérovej tabuľky stránok z uloženej užívateľovej tabuľky stránok.
Hardvérová implementácia tabuľky stránok môže byť realizovaná viacerými spôsobmi, ktoré
nebudeme preberať. Jedna z nich je metóda TLB.
4.12 Ochrana
Uvedomme si, že pri stránkovaní užívateľský proces nemôže pristupovať k pamäti, ktorú nevlastní.
Nemá žiadnu možnosť adresovať pamäť mimo svojej tabuľky stránok a tabuľka zahŕňa len tie
stránky, ktoré vlastní proces. Ochrana pamäte v stránkovom prostredí je uskutočňovaná ochrannými
bitmi, ktoré sú pridružené ku každému rámcu. Normálne sú tieto bity držané v tabuľke stránok.
Jeden bit môže definovať stránku ako read–write alebo read–only. Každý odkaz na pamäť ide cez
tabuľku stránok, aby sa našlo správne číslo rámca. V tom istom čase, ako sa vypočítava fyzická
adresa, sa môžu skontrolovať ochranné bity, či nedošlo k žiadnemu zápisu na read–only stránku.
Pokus o zápis na read–only stránku spôsobí odlúčenie (trap) k operačnému systému (porušenie
ochrany pamäte). Tento prístup môžeme ľahko rozšíriť na jemnejšiu úroveň ochrany. Môžeme
vytvoriť hardvér na poskytovanie read–only, read–write alebo execute–only ochrany. Alebo
poskytnutím rôznych ochranných bitov pre každý druh prístupu môžeme umožniť akúkoľvek
kombináciu týchto prístupov; neprípustné prístupy spôsobia odlúčenie k operačnému systému.
Každej položke v tabuľke stránok je zvyčajne priradený ešte jeden bit: platný–neplatný bit
(Valid–Invalid Bit). Keď je tento bit nastavený na „platný“, tak táto hodnota naznačuje, že pridružená
stránka je v logickom adresovom priestore procesu a teda je to legálna (alebo platná) stránka. Ak
je bit nastavený na „neplatný“, táto hodnota naznačuje, že stránka nie je v logickom adresovom
priestore procesu. Využitím platný–neplatný bitu sa zachytávajú ilegálne adresy. Operačný systém
nastaví tento bit pre každú stránku procesu tak, aby umožňoval alebo neumožňoval prístup na túto
stránku.
Studenovský: Operačné systémy 8 Pamäť 12
Príklad
V systéme so 14–bitovým adresovým priestorom (od 0 do 16383) chceme mať program, ktorý by
mal používať len adresy od 0 po 10468. So zadanou veľkosťou stránky 2 KB dostávame situáciu
zobrazenú na Obrázku 10. Adresy na stránkach 0, 1, 2, 3, 4 a 5 sú mapované normálne cez tabuľku
stránok. Avšak každý pokus o generovanie adresy na stránke 6 alebo 7 zistí, že platný–neplatný bit je
nastavený na „i“ = „neplatný“ a počítač sa odlúči k operačnému systému (neplatný odkaz na
stránku).
Obrázok 10 Platný (v) alebo neplatný (i) bit v tabuľke stránok.
Keďže program sa nachádza len po adresu 10468, každý odkaz za touto adresou je neprípustný.
Adresy po stránku 5 sú však vyhodnotené ako platné, teda prístupy na adresy po 12287 sú platné. Len
adresy od 12288 po 16383 sú neplatné. Tento problém je dôsledkom 2 KB veľkosti stránky a
zohľadňuje internú fragmentáciu stránkovania.
4.13 Modifikácie metódy stránkovania
Existujú rôzne modifikácie základnej metódy stránkovania ako napríklad:
Hierarchické (viacúrovňové) stránkovanie.
Hašované tabuľky stránok.
Invertovaná tabuľka stránok.
4.14 Zdieľané stránky
Ďalšia výhoda stránkovania je možnosť zdieľania spoločného kódu. Táto okolnosť je dôležitá hlavne
v time–sharing prostredí. Uvážte systém, ktorý podporuje 40 užívateľov, z ktorých každý spustí
textový editor. Ak textový editor pozostáva zo 150 KB kódu a 50 KB dátového priestoru, potrebovali
by sme 8000 KB na podporu 40 užívateľov. Ale, ak kód je reentrantný, dá sa zdieľať. Reentrantný
kód (alebo pravý kód) je kód, ktorý nemôže modifikovať sám seba. Ak je kód reentrantný, počas
vykonávania sa nikdy nemení. Teda dva alebo viac procesov môže vykonávať ten istý kód naraz.
Každý proces má vlastnú kópiu registrov a dátové úložisko k držaniu dát pri vykonávaní procesu.
Dáta pre dva rôzne procesy sa budú samozrejme navzájom odlišovať. Vo fyzickej pamäti
potrebujeme držať iba jednu kópiu editora. Každá užívateľská tabuľka stránok mapuje na tú istú
fyzickú kópiu editora, ale dátové stránky sa mapujú do rôznych rámcov. A tak, pre 40 užívateľov
potrebujeme len jednu kópiu editora (150 KB) plus 40 kópií 50 KB dátového priestoru na užívateľa.
Potrebujeme celkovo 2150 KB namiesto 8000 KB — významná úspora. Ďalšie často využívané
programy sa tiež dajú zdieľať — kompilátory, systémy okien, run– time knižnice, databázové
systémy a tak ďalej. Aby sa kód dal zdieľať, musí byť reentrantný. Charakteristika read–only
zdieľaného kódu zaručí, že kód sa nebude meniť; túto vlastnosť read– only by mal vynútiť operačný
systém.
Studenovský: Operačné systémy 8 Pamäť 13
Obrázok 11 ukazuje trojstránkový editor — každá stránka veľkosti 50 KB. Editor je zdieľaný
troma procesmi. Každý proces má vlastnú dátovú stránku.
ed 1
1
6
4
3
ed 2
ed 3 ed 1
dáta 1
proces P1
tabuľka stránok
pre P
1
dáta 3
ed 3
ed 2
ed 1
3
4
7
6
4
3
dáta 2
ed 3
ed 2
proces
P
6
2
2
dáta 2
89
7ed 3 ed 2 ed
61 dáta 3 dáta
51
4
3
2
1
0
tabuľka stránok
pre P
2
10
tabuľka stránok
pre P
3
proces P3
Obrázok 11 Zdieľanie kódu v prostredí stránkovania.
V Kapitole 5 Sekcii 1 sme opisovali zdieľanú pamäť ako metódu medzi–procesovej komunikácie.
Niektoré operačné systémy implementujú zdieľanú pamäť pomocou zdieľaných stránok.
5 Segmentácia
Dôležitý aspekt správy pamäte, ktorý sa stal nevyhnutným pri stránkovaní, je oddelenie užívateľského
pohľadu na pamäť a skutočnej fyzickej pamäte. Užívateľský pohľad na pamäť nie je rovnaký ako
skutočná fyzická pamäť. Užívateľský pohľad je mapovaný na fyzickú pamäť. Tento „estetický“
nedostatok odstraňuje segmentovanie.
5.1 Základy segmentácie
Predstavujú si užívatelia pamäť ako lineárne pole bajtov, kde niektoré bajty obsahujú inštrukcie a iné
dáta? Väčšina ľudí by povedala, že nie. Užívatelia skôr uprednostňujú pozerať sa na pamäť, ako na
kolekciu rôzne veľkých segmentov bez nutnosti ich zoradenia (Obrázok 12). Zamyslite sa nad tým,
ako rozmýšľate o programe, keď ho píšete. Predstavujete si ho ako hlavný program s množinou
podprogramov, procedúr, funkcií alebo modulov. Môžu tam tiež byť rozličné dátové štruktúry:
tabuľky, polia, zásobníky, premenné a tak ďalej. Na každý z týchto modulov alebo dátových prvkov
odkazujete pomocou mena. Hovoríte o „tabuľke symbolov“, „funkcii Sqrt”, „hlavnom programe”,
bez toho, že by ste sa starali o adresy v pamäti, ktoré tieto elementy zaberajú. Nezaujímate sa o to, či
tabuľka symbolov je uložená pred alebo za funkciou
Sqrt. Každý z týchto segmentov má rôznu dĺžku. Elementy vnútri segmentu sú identifikované podľa
svojho ofsetu (posunutia) od začiatku segmentu: Prvý príkaz v programe, sedemnásta položka v
tabuľke symbolov, piata inštrukcia funkcie Sqrt a tak ďalej.
Studenovský: Operačné systémy 8 Pamäť 14
Segmentácia je schéma riadenia pamäte, ktorá podporuje tento užívateľský pohľad na pamäť.
Logický adresový priestor je kolekcia segmentov. Každý segment má meno a dĺžku. Adresu určujú
meno segmentu a ofset vnútri segmentu. Užívateľ preto špecifikuje každú adresu pomocou dvoch
veličín: mena segmentu a ofsetu. Pre jednoduchosť implementácie segmenty sú očíslované a
odkazuje sa na ne skôr pomocou
čísla ako pomocou mena. Logická adresa teda pozostáva z dvojice: <číslo segmentu,
ofset> Kompilátor automaticky vytvorí segmenty podľa požiadaviek v zdrojovom
programe.
logický adresový priestor
zásobník
podprogram
tabuľka
symbolov
Sqrt
hlavný
program
Obrázok 12 Užívateľský pohľad na program.
5.2 Segmentačný hardvér
Hoci užívateľ teraz môže odkazovať na objekty v pamäti cez dvojrozmerné adresy, skutočná fyzická
pamäť je samozrejme jednorozmerná postupnosť bajtov. Preto musíme definovať mapovanie
dvojrozmerných adries definovaných užívateľom na jednorozmerné fyzické adresy. Mapovanie je
ovplyvnené tabuľkou segmentov. Každá položka tabuľky segmentov má bázu segmentu a limit
segmentu. Báza segmentu obsahuje začiatočnú fyzickú adresu, na ktorej sa segment v pamäti
nachádza, zatiaľ čo limit segmentu špecifikuje jeho dĺžku.
s
limit báza
sd
CPU
+<
án
o
nie
odlúčenie; chyba
adresácie
Obrázok 13 Segmentačný hardvér.
fyzická
pamäť
Použitie tabuľky segmentov je zobrazené na Obrázku 13. Logická adresa pozostáva z dvoch
častí: z čísla segmentu s a ofsetu d. Číslo segmentu sa používa ako index v tabuľke segmentov. Ofset
logickej adresy d musí byť medzi 0 a limitom segmentu. Ak nie je, nastane odlúčenie k operačnému
systému (pokus o prístup k logickej adrese za koncom segmentu). Ak tento ofset je
Studenovský: Operačné systémy 8 Pamäť 15
platný, pripočíta sa k báze segmentu, čím vznikne adresa želaného bajtu vo fyzickej pamäti. Tabuľka
segmentov je teda v podstate pole dvojíc báza – limit.
5.3 Príklad
0
Podprogram
Segment 0
Sqrt
Segment 1
Zásobník
Segment 3
1
2
Limit Base
1000
1400 400
6300 400
4300 1100
3200 1000
4700
Tabuľka
symbolov
Segment 4
Hlavný
program
Segment 2
1400
2400
3200
4300
4700
5700
6300
6700
Segment 0
Segment 3
Segment 2
Segment 4
Segment 1
Obrázok 14 Príklad segmentácie
Uvažujme situáciu na Obrázku 14. Máme päť segmentov očíslovaných od 0 po 4. Segmenty sú
uložené vo fyzickej pamäti tak, ako ukazuje obrázok. Tabuľka segmentov má samostatnú položku
pre každý segment udávajúcu začiatočnú adresu segmentu vo fyzickej pamäti (alebo báza) a dĺžku
daného segmentu (alebo limit). Napríklad segment 2 je dlhý 400 bajtov a začína na pozícii 4300.
Teda odkaz na 53 bajt segmentu 2 sa mapuje na pozíciu 4300 + 53 = 4353. Odkaz na segment 3, bajt
852 sa mapuje na 3200 + 852 = 4052. Odkaz na 1222 bajt segmentu 0 by mal za následok
prerušenie operačného systému, keďže tento segment je dlhý len 1000 bajtov.
5.4 Ochrana
Osobitnou výhodou segmentácie je spojenie ochrany so segmentmi. Keďže segmenty reprezentujú
sémanticky definované časti programu je pravdepodobné, že všetky položky segmentu sa budú
používať rovnakým spôsobom. Niektoré segmenty sú inštrukcie iné dáta. V modernej architektúre
inštrukcie nemenia samy seba, takže inštrukčné segmenty môžu byť definované ako „iba na čítanie“
alebo „iba na vykonávanie“. Hardvér mapujúci pamäť bude kontrolovať ochranné bity asociované s
každou položkou tabuľky segmentov, aby zabránil nepovoleným prístupom do pamäti, ako sú
napríklad pokusy o zápis do segmentu len na čítanie alebo použitie segmentu na vykonanie ako dáta.
Umiestnenie pola do samostatného segmentu umožní, aby hardvér správy pamäte automaticky
kontroloval, či indexy pola sú povolené a nezablúdili mimo hraníc pola. Takže veľa spoločných
programových chýb budú detekované hardvérom.
5.5 Zdieľanie
Ďalšia výhoda segmentácie je zdieľanie kódu a dát. Každý proces má pridelenú tabuľku segmentov,
ktorú dispečer použije na definovanie hardvérovej tabuľky segmentov, keď pridelí tento proces k
CPU. Segmenty sú zdieľané, keď položky v tabuľke segmentov pre dva rôzne procesy ukazujú na
rovnaké fyzické umiestnenie (Obrázok 15).
5.6 Alokácia
Dlhodobý plánovač musí nájsť a alokovať (prideliť) pamäť všetkým segmentom užívateľského
programu. Postupuje sa rovnako, ako pri súvislej alokácii – schéme viacnásobných variabilných
partícií. Teda alokácia pamäte pri segmentácii je problémom dynamického prideľovania pamäti,
obyčajne riešený best–fit alebo first–fit algoritmom.
Studenovský: Operačné systémy 8 Pamäť 16
editor
segment 0
dáta 1
43062
editor
segment 1
hranica základ
logická pamäť
procesu P 1
25286
4425
72773
68348
dáta 1
43062
68348
tabuľka segmentov
procesu P
1
editor
90003
dáta
2
98853
dáta 2 segment 0
segment 1
logická pamäť
hranicaOzáklad
brázok
1 543062
25286
8850
fyzická pamäť
90003
Obrázok 15. Zdieľanie
segmentov
v segmentovanom systéme
tabuľka
segmentov
pamäti.
procesu P
2
procesu P2
5.7 Fragmentácia
Segmentácia môže spôsobiť vonkajšiu fragmentáciu, ak všetky voľné pamäťové bloky sú príliš malé
na to, aby sa do nich uložil segment. V tomto prípade proces musí počkať, kým sa neuvoľní viac
pamäte, alebo kým kompakcia nevytvorí väčšiu dieru. Pretože segmentácia je vo svojej podstate
dynamický relokačný algoritmus, môžeme kompakovať pamäť, kedykoľvek chceme. Aký závažný
je problém vonkajšej fragmentácie pre schému segmentácie? Pomôže dlhodobé plánovanie s
kompakciou? Odpovede závisia hlavne od priemernej veľkosti segmentu. V jednom extréme by sme
mohli definovať každý proces ako jeden segment. Tento prístup sa redukuje na schému
viacnásobných variabilných partícií. V druhom extréme by sa každý bajt mohol vložiť do vlastného
segmentu. Táto úprava celkom vylučuje vonkajšiu fragmentáciu; ale každý bajt by potreboval bázový
register na relokáciu a to by zdvojnásobilo spotrebu pamäte! Samozrejme, ďalší logický krok —
malé segmenty pevnej veľkosti — to je stránkovanie. Všeobecne, ak je priemerná veľkosť segmentu
malá, vonkajšia fragmentácia bude tiež malá. (Analogicky uvažujme vkladanie tašiek do kufra auta;
nikdy celkom nepasujú. Ale, ak otvoríte tašky a poukladáte do kufra jednotlivé veci, je
pravdepodobnejšie, že sa tam zmestia.) Keďže jednotlivé segmenty sú menšie než celý proces, skôr
sa zmestia do dostupných pamäťových blokov.
Studenovský: Operačné systémy 8 Pamäť 17
6 Segmentácia so stránkovaním
Výhody a nevýhody segmentácie a stránkovania sa dajú užitočne skombinovať pomocou
segmentovaného stránkovania. Tieto schémy môžu byť veľmi komplikované, načrtneme len základnú
myšlienku.
Základom je segmentácia, t.j. prvotná fáza prevodu logickej adresy na fyzickú adresu je segmentácia.
Ako výsledok dostaneme lineárnu adresu. Táto lineárna adresa sa potom stránkuje, t.j. priestor
lineárnych adries je rozdelený na stránky a týmto stránkam sa v druhej fáze prevodu priraďujú rámce
popísaným algoritmom stránkovania –– takto dostaneme fyzickú adresu. Napríklad, Intel 386 a
pokračujúca rodina Pentium využíva segmentáciu s dvojúrovňovým stránkovaním, pričom
stránkovacie tabuľky môžu byť swapované na disk.
7 Virtuálna pamäť
Táto technika umožňuje beh procesov, ktorých LAP (logický adresový priestor) nie je celý vo FAP
(fyzický adresový priestor), t.j. celý proces nie je zavedený v operačnej pamäti. Jedna z možných
implementácií je stránkovanie na žiadosť, ktoré tu stručne a zjednodušene popíšeme.
7.1 Stránkovanie na žiadosť
Základom je stránkovanie alebo segmentované stránkovanie. Každý rámec má ale priradené miesto
aj na disku — v tzv. odkladacej oblasti. Nie každá stránka procesu musí byť v pamäti, niektoré
môžu byť odložené na disku.
Čo sa ale stane, ak sa proces snaží pristúpiť k stránke, ktorá je odložená? Nastane tzv. výpadok
stránky — proces prejde do stavu čakajúci a operačný systém prenesie stránku do pamäti. V
podstate proces môže začať svoj beh tak, že len jeho „úvodná stránka“ (začiatok programu) je v
pamäti, ostatné sú odložené. Po prenesení chýbajúcej stránky do pamäti, proces prejde do stavu
pripravený a eventuálne sa dostane k procesoru. Pri tejto schéme súčet veľkostí LAP procesov v
systéme môže prekročiť veľkosť FAP. Čo rozhoduje, je súčet veľkostí stránok, ktoré sú v pamäti.
Samozrejme, môže nastať situácia, že po výpadku stránky chceme odloženú stránku zaviesť z disku
do pamäti, ale nie je voľný žiaden rámec vo FAP. Vtedy sa jeden z obsadených rámcov musí odložiť
na disk. Výber obete presahuje rámec prednášky.
8 Zhrnutie
Algoritmy riadenia pamäte pre multiprogramové operačné systémy sú v rozsahu od jednoduchých,
systémov až po stránkovanú segmentáciu. Rozhodujúci činiteľ pri voľbe metódy je poskytovaný
hardvér. Každá pamäťová adresa generovaná procesorom musí byť kontrolovaná a možno mapovaná
na fyzickú adresu. Kontrola nemôže byť implementovaná softvérovo. Takže sme obmedzení
možnosťami hardvéru. Preberané algoritmy riadenia pamäte (súvislá alokácia, stránkovanie,
segmentácia a kombinácie stránkovania a segmentácie) sa líšia v mnohých aspektoch. V porovnávaní
rozličných stratégií riadenia pamäte by ste mali zvážiť nasledovné:
Hardvérová podpora: Jednoduchý bázový register pre schému jedna partícia alebo schému
viacnásobných pevných partícií alebo dvojica bázový a limitný register pre schému viacnásobných
variabilných partícií je postačujúca, zatiaľ čo stránkovanie a segmentácia potrebujú mapovacie
tabuľky na definovanie priradenia adresy.
Výkon: Čím sa algoritmus riadenia pamäte stáva viac zložitým, tým sa čas potrebný na
priradenie fyzickej adresy k logickej adrese zvyšuje. V jednoduchých systémoch potrebujeme len
porovnať alebo pripočítať k logickej adrese –– operácie, ktoré sú rýchle. Stránkovanie a
segmentácia môžu byť rýchle, ak tabuľka je implementovaná v rýchlych registroch. Ak tabuľka je
v pamäti, prístup užívateľa do pamäte môže byť podstatne spomalený. TLB dokáže znížiť
spomalenie výkonu na prijateľnú úroveň.
Studenovský: Operačné systémy 8 Pamäť 18
Fragmentácia: Multiprogramové systémy sú vo všeobecnosti výkonnejšie, ak používajú vyššiu
úroveň multiprogramovania. Pre danú množinu procesov môžeme zvýšiť úroveň
multiprogramovania iba zbalením viacerých procesov do pamäte. Na zvládnutie tejto úlohy
musíme obmedziť plytvanie pamäťou čiže fragmentáciu. Systémy s pevne danou veľkosťou
alokačných jednotiek, ako napríklad schéma viacnásobných pevných partícií a stránkovanie,
doplácajú na vnútornú fragmentáciu. Systémy s variabilnou veľkosťou alokačných jednotiek, ako
napríklad schéma viacnásobných variabilných partícií a segmentácia, doplácajú na vonkajšiu
segmentáciu.
Relokácia: Jedno riešenie problému vonkajšej fragmentácie je kompakcia. Kompakcia zahŕňa
posúvanie programu v pamäti bez toho, aby program spozoroval zmenu. Tento činiteľ vyžaduje
dynamickú relokáciu adresy v čase vykonávania. Ak adresy sú relokovateľné len v čase
zavádzania, nemožno robiť kompakciu.
Swapovanie: Do hociktorého algoritmu možno zabudovať swapovanie. V intervale určenom
operačným systémom, zvyčajne diktovaným CPU plánovacou politikou, procesy sú kopírované z
hlavnej pamäte do záložného priestoru a neskôr sú kopírované späť do hlavnej pamäte. Táto
schéma dovoľuje bežať viacerým procesom, než môžu byť v pamäti.
Zdieľanie: Ďalší spôsob zvýšenia úrovne je zdieľať kód a dáta medzi rôznymi užívateľmi.
Zdieľanie väčšinou vyžaduje použiť buď stránkovanie alebo segmentovanie, aby bolo možné
zdieľať malé balíčky informácií (stránky alebo segmenty). Zdieľanie je spôsob bežania mnohých
procesov s obmedzeným množstvom pamäte, ale zdieľané programy a dáta musia byť navrhnuté
opatrne.
Ochrana: Keď je poskytované stránkovanie alebo segmentácia, rôzne sekcie užívateľského
programu môžu byť deklarované ako iba na vykonávanie, iba na čítanie, alebo čítanie–
zapisovanie. Toto obmedzenie je potrebné pre zdieľaný kód alebo dáta a je všeobecne užitočné v
prípade poskytovania jednoduchých kontrol chýb za behu programu.
Studenovský: Operačné systémy 8 Pamäť 19
Download

8 Pamat.pdf