Systém adresace paměti Základní pojmy Adresa fyzická - adresa, která je přenesena na adresní sběrnici a fyzicky adresuje hlavní paměť logická - adresa, kterou má k dispozici proces k adresaci přiděleného adresového prostoru efektivní - adresa, která vzniká modifikací operandu segmentovými registry Obvyklý postup překladu adres:
operand Æ efektivní Æ logická Æ fyzická
Lineární adresový prostor Tvoří jej souvislá (lineární) posloupnost efektivních adres Segmentový adresový prostor Tvoří jej posloupnost segmentů efektivních adres Každý segment tvoří lineární adresový prostor Segmenty jsou definovány zapsáním bázové (základní) adresy segmentu do segmentového registru Segmenty mohou mýt různou velikost a vzájemně se překrývat Procesory bez dynamického překladu adres Efektivní adresa se ukládá přímo do adresového bufferu, odkud je pak přenesena na adresní sběrnici Procesory s dynamickým překladem adres Mezi vnitřní sběrnici procesoru a adresní sběrnici je vložena jednotka DAT (Dynamic Adress Translation), která překládá efektivní (logickou) adresu na fyzickou.
-1-
Způsoby adresace Adresace bez jednotky DAT Přičtení obsahu adresních registrů k adrese v poli operandu Æ modifikace operandu Přičtení obsahu segmentového registru k modifikované adrese operandu Æ efektivní adresa Efektivní adresa se uloží do adresního bufferu Æ fyzická adresa
OZ
operand
Adres ní regis try (IND)
+
Segm entové regis try
+
efektivní adres a Adres ový buffer
fyzická adres a
Nemá-li procesor segmentové registry, uloží se modifikovaný operand přímo do adres. bufferu.
-2-
Adresace s jednotkou DAT Na vstup jednotky DAT je přiváděna efektivní adresa Výstupem jednotky DAT je efektivní adresa přeložená na adresu fyzickou
vnitřní sběrnice
efektivní adresa
systémová (adresní) sběrnice
DAT fyzická adresa
logický adresový prostor
Logický adresový prostor lineární segmentovaný
Lineární adresový prostor OZ
Operand
Adresní registry
+ efektivní adresa = logická adresa
DAT Pevná adresa
+
Převedení logické adresy na fyzickou adresu
Adresový buffer
fyzická adresa
-3-
Logické adresy se každému procesu přidělují od pevně zvolené adresy p Všechny procesy mají stejný logický adresový prostor, jehož velikost je dána šířkou vnitřní sběrnice n Logické adresy procesů jsou z intervalu
Obvykle u procesorů RISC
Segmentový adresový prostor Adresový prostor je složený ze segmentů různé velikosti, které se mohou překrývat Segmenty jsou chráněny – regulace přístupu procesů k segmentům Některé segmenty mohou procesy mezi sebou sdílet – např. jádro operačního systému Jednotka DAT obsahuje tabulku deskriptorů segmentů V deskriptoru je zaznamenáno: velikost segmentu adresa jeho báze způsob ochrany
tabulka deskriptorů
-4-
Strategie přidělování paměti Pokud je multitaskingový operační systém v činnosti, je rezidentní část jádra operačního systému umístěna obvykle na začátku hlavní paměti. Zbývající část hlavní paměti operační systém přiděluje zpracovávaným procesům. Jsou možné tyto způsoby jejího přidělování: přidělování statických souvislých úseků Paměť je po celou dobu běhu operačního systému rozdělena na souvislé úseky, jejichž umístění se nemění Proces se uloží do nejmenšího volného úseku, do kterého ho lze uložit. Překlad mezi logickou a fyzickou je možné provést jednoduchou jednotkou DAT (i bez jednotky DAT) – Překlad spočívá v přičtení počáteční adresy (báze) k logické adrese – Hodnota báze je zapsána do bázového registru operačním systémem při spuštění procesu přidělování dynamických souvislých úseků Operační systém vybere nejmenší souvislou volnou část paměti tak, aby do ní mohl umístit celý proces. Paměť obsahuje řadu malých, procesy neobsazených částí Æ fragmentace paměti – U přidělování dynamických úseků lze odstranit realokací obsazených úseků paměti – spotřebovává procesorový čas Proces není chráněn před ostatními procesy – Proces může přepsat oblast paměti vyhrazenou jinému procesu – Ochrana procesu pomocí techniky klíč-zámek přidělování virtuálního adresového prostoru
-5-
Virtuální paměť Je-li proces větší než fyzická paměť počítače, nelze jej přímo uložit a spustit Proces je nutno rozdělit na menší části (tzv. overlays) a postupně nahrávat do paměti a zpracovávat Je-li postupné umísťování do paměti prováděno automaticky, mapuje jednotka DAT logický adresový prostor procesu na fyzický tak, jak stanovuje operační systém Procesor může pracovat v celém svém logickém prostoru, jakoby se fyzická paměť rozšířila na velikost logické paměti – virtuální paměť
Lineární adresový prostor Stránkování paměti virtuální adresový prostor rozdělen na stránky (1-8kB) fyzický adresový prostor rozdělen na stejně velké úseky – rámy nebo rámce (frames) Logická (virtuální) adresa rozdělena na číslo stránky posuv (offset) – vyjadřuje umístění (lokální adresu) v rámci stránky Každý proces má svoji tabulku stránek Každý řádek tabulky stránek odpovídá jedné stránce, v řádce je uvedeno: číslo rámu, které OS stránce přidělil bit platnosti stránky – P kód autorizace – R (povolení číst) W (povolení zapisovat) X (použít stránku pro řízení procesu) bit změny obsahu stránky – Z číslo bloku, ze kterého lze stránku získat (systém souborů, swappovací oblast)
-6-
logická (virtuální) adresa číslo stránky
Registr tabulky stránek
posuv
Tabulka stránek
P RWX Z
blok
číslo rámu
rám
posuv
fyzická adresa
Operační systém procesu namapuje jen určitý počet stránek – použije-li proces virtuální adresu mimo namapovaný prostor, dojde k výpadku stránky Æ je generováno přerušení Æ OS požadovanou stránku namapuje Operační systém často mapuje procesu stránky až, když dojde k výpadku stránky – stránkování na žádost Nastane-li situace, kdy nejsou žádné volné rámy, OS musí některé stránky odmapovat – různé strategie výběru stránek - nejlepší LRU (poslední použitá) Přenosy při řešení výpadku stránky velmi zdržují. Nesmí být požadovány příliš často. Nebezpečí ZAHLCENÍ – „trashing“. Proto je rozumné určit pro každý proces tak zvanou PRACOVNÍ MNOŽINU (= počet stránek, které by měly být přítomny v paměti trvale). Zda je volné místo pro pracovní množinu kontrolovat před zahájením procesu programem řízení úloh (spolu s tím, zda jsou volné nesdílitelné zdroje).
-7-
Virtuální paměť – příklad Procesor pracuje s velikostí stránky 4kB (4096 B). Proces A má obsazenu tabulku stránek takto:
Hlavní paměť bit platnosti
číslo rámu
0
1
1 2
stránka
0
rám 0
2
4096
rám 1
0
40
8192
rám 2
1
3
12288
rám 3
…
…
…
…
Program, který řídí proces A má startovací adresu 100. Kde ve fyzické paměti je obsah této adresy umístěn? logická adresa: stránka (0 . 4096) + posuv (100) fyzická adresa: rám (2) + posuv (100) 8192 + 100 = 8292 Proces provede instrukci LDX R, 9000. Kterou adresu fyzické paměti procesor do registru načte? logická adresa: stránka (2 . 4096) + posuv (808) fyzická adresa: rám (3) + posuv (808) 12288 + 808 = 13096 Následně procesor začne provádět instrukci ADX R, 4098. Popište činnost procesoru a operačního systému při zpracování této instrukce. logická adresa: stránka (1 . 4096) + posuv (2) fyzická adresa: bit platnosti = 0 Æ výpadek stránky
Víceúrovňové stránkování Předpokládejme, že logická adresa má 32 bitů a velikost stránky je 4kB (12 bitů). Tabulka stránek musí potom mít 1M (20 bitů) řádků. Každý řádek má několik bytů … Æ tabulka stránek by v paměti zabírala příliš místa Operační systém tabulku stránek také stránkuje – udržuje její kopii na disku a do paměti uloží jen část Adresa stránky se rozdělí na adresu adresáře stránek vlastní adresu stránky
-8-
Pokud rozdělíme 20 bitů adresy stránek z příkladu na adresu adresáře s 10 bity a adresu stránky také s 10 bity, potom obě tabulky budou mít jen 1024 řádků.
Invertovaná tabulka stránek Jiným řešením příliš velké tabulky stránek je použití tzv. invertované tabulky stránek Tabulka s přiřazením stránky a rámu je organizována podle čísel rámů (rámů je podstatně méně než stránek) OS hledá k číslu stránky číslo rámu a musí mít přímý přístup do tabulky podle čísla stránky – realizováno pomocí hash tabulky Hash funkce je dána vztahem číslo stránky mod velikost základní části hash tabulky Více stránek může být mapováno do stejného místa hash tabulky Æ rehashing logická adresa stránka
posuv
Hash tabulka Invertovaná tabulka Rám Rám
P RWX Z
blok
rám
-9-
posuv
Segmentovaný adresový prostor Segmentovaný adresový prostor umožňuje: strukturovat program a data do oddělených segmentů s různými způsoby ochrany sdílení dat mezi procesy realizovat podprogramy uložením do segmentu, který je přístupný všem procesům nezávislý překlad (kompilaci) částí programu Některé implementace operačního systému UNIX (SYSTEM V) ukládají do různých segmentů program (text), data a zásobník (stack) Hlavní paměť
Proces A
Proces B
STACK
STACK
DATA
DATA
TEXT
TEXT
TLB cache Pro uchovávání právě načtené řádky tabulky stránek jsou procesory vybaveny rychlou vyrovnávací pamětí – TLB cache (Translation Look aside Buffer) obvykle plně asociativní obsahuje řádově desítky řádků Příklad: Procesor má TLB cache s 32 řádky. Velikost stránky je 4kB. V jak velikém rozsahu adres může pracovat program, aniž by procesor musel při překladu adresy číst z hlavní paměti? (Samozřejmě s výjimkou počátečního naplnění TLB cache) TLB cache může obsahovat 32 stránek, každá o velikosti 4 kB Æ rozsah adres = 32 . 4 = 128 kB
- 10 -
Proces čtení z paměti / zápisu do paměti Čtení z paměti / zápis do paměti probíhá následovně: Adresová jednotka nejdříve hledá zobrazení adresy stránky na adresu rámu v TLB cache Nenajde-li v TLB, hledá v tabulce stránek (možný výpadek stránky) Je-li známa fyzická adresa, hledá její obsah v cache paměti (mezi procesorem a hlavní pamětí) Není-li obsah paměti v cache, obrátí se na hlavní paměť
řádek tabulky stránek není v TLB
logická adresa
Cache
TLB
stránka
posuv
řádek tabulky stránek je v TLB
TAG TAG
+
nesouhlasí tag
Tabulka stránek
+
Hlavní paměť
Souhlasí tag, obsah adresy je v cache
- 11 -
