Adresace paměti 11.přednáška
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á vnitřní sběrnice procesoru
[email protected]
adresní sys. sběrnice 2
Adresový prostor 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
[email protected]
3
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 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.
[email protected]
4
Adresace bez jednotky DAT OZ
operand
Adresní registry (IND)
+
Segmentové registry
+ efektivní adresa
Adresový buffer
fyzická adresa
Nemá-li procesor segmentové registry, uloží se modifikovaný operand přímo do adres. bufferu.
[email protected]
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 5
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 logický adresový prostor
fyzická adresa
Logický adresový prostor lineární segmentovaný
[email protected]
6
Adresace s jednotkou DAT lineární adresový prostor 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
[email protected]
7
Adresace s jednotkou DAT 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 [email protected]
8
Adresace s jednotkou DAT 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 [email protected]
9
Adresace s jednotkou DAT segmentový adresový prostor
tabulka deskriptorů
[email protected]
INTEL 80386
10
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ů přidělování dynamických souvislých úseků přidělování virtuálního adresového prostoru
[email protected]
11
Přidělování statických souvislých úseků 0
O p e r a č n í sy sté m
128 kB
192 kB
256 kB
384 kB
ú se k 1 (6 4 k B ) ú se k 2 (6 4 k B )
Paměť je po celou dobu běhu operačního systému rozdělena na souvislé úseky, jejichž umístění se nemění
ú se k 3 (1 2 8 k B )
ú se k 4 (1 2 8 k B )
512 kB
ú se k 5 (2 5 6 k B )
Proces se uloží do nejmenšího volného úseku, do kterého ho lze uložit
768 kB
ú se k 6 (2 5 6 k B )
[email protected]
12
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
Proces 1
Proces 1
Proces 1 Proces 4
Proces 5 Proces 4
Proces 2
Proces 3
Proces 2 ukončen [email protected]
Proces 5 Proces 4 Proces 3
Proces 3
Proces 3
Proces 4 spuštěn
Proces 3
Proces 1 ukončen a místo něj zaveden do paměti proces 5
Realokace 13
Přidělování souvislých úseků - výhoda 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
[email protected]
14
Přidělování souvislých úseků - nevýhody 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
[email protected]
15
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ěť [email protected]
16
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 [email protected]
17
Virtuální paměť lineární adresový prostor 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) [email protected]
18
Virtuální paměť lineární adresový prostor logická adresa číslo stránky
R egistr tabulky stránek
p osuv
T abulka stránek
P RW X Z
blok
číslo rám u
rám
[email protected]
fyzická adresa
posuv
19
Virtuální paměť lineární adresový prostor 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 [email protected]
20
Virtuální paměť – příklad Procesor pracuje s velikostí stránky 4kB (4096 B). Proces A má obsazenu tabulku stránek takto: bit platnosti
číslo rámu
0
1
1 2
stránka
…
Hlavní paměť 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 [email protected]
21
Virtuální paměť – příklad Procesor pracuje s velikostí stránky 4kB (4096 B). Proces A má obsazenu tabulku stránek takto: bit platnosti
číslo rámu
0
1
1 2
stránka
…
Hlavní paměť 0
rám 0
2
4096
rám 1
0
40
8192
rám 2
1
3
12288
rám 3
…
…
…
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 [email protected]
22
Virtuální paměť – příklad Procesor pracuje s velikostí stránky 4kB (4096 B). Proces A má obsazenu tabulku stránek takto: bit platnosti
číslo rámu
0
1
1 2
stránka
…
Hlavní paměť 0
rám 0
2
4096
rám 1
0
40
8192
rám 2
1
3
12288
rám 3
…
…
…
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 [email protected]
23
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
[email protected]
24
Víceúrovňové stránkování
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ů. [email protected]
25
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 [email protected]
26
Invertovaná tabulka stránek logická adresa stránka
posuv
Hash tabulka Invertovaná tabulka stránek Rám 0 Rám 1
P RWX Z
blok
rám [email protected]
posuv 27
Virtuální paměť 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
[email protected]
28
Segmentovaný adresový prostor v UNIXu 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) H lavní pam ěť
P roces A
P roces B
STA C K
STA C K
D A TA
D A TA
TEX T
TEX T
[email protected]
29
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 [email protected]
30
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ěť
[email protected]
31
Proces čtení z paměti / zápisu do paměti řádek tabulky stránek není v TLB
logická adresa
C ache
TLB
stránka
posuv
řádek tabulky stránek je v TLB
TA G TA G
+
nesouhlasí tag
T abulka stránek
+
H lavní pam ěť
Souhlasí tag, obsah adresy je v cache
[email protected]
32
Děkuji za pozornost ! Příští přednáška: Přerušovací systémy, sběrnice a komunikace po sběrnici
