1/43
PB153
OPERAČNÍ SYSTÉMY
A JEJICH ROZHRANÍ
Virtuálnípaměť
9
2/43
 Virtuální paměť
● separace LAP a FAP
● ve FAP se mohou nacházet pouze části programů
nutné pro bezprostřední řízení procesů
● LAP může být větší než FAP
● adresové prostory lze sdílet mezi jednotlivými procesy
● lze efektivněji vytvářet procesy
 Techniky implementace
● Stránkování na žádost, Demand Paging
● Segmentování na žádost, Demand Segmentation
ZÁKLADNÍ PRINCIPY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
3/43
 Část procesu umístěnou ve FAP nazýváme „rezidentní množinou“
(resident set)
 Odkaz mimo rezidentní množinu způsobuje přerušení výpadek
stránky (page fault)
 OS označí proces za „čekající“
 OS spustí I/O operace a provede nutnou správu paměti pro
zavedení odkazované části do FAP
 Mezitím běží jiný proces (jiné procesy)
 Po zavedení odkazované části se generuje I/O přerušení
● OS příslušný proces umístí mezi připravené procesy
 Překlad adresy LAP na adresu FAP se dělá indexováním tabulky
PT/ST pomocí hardware CPU
BĚH PROCESŮ VE VIRTUÁLNÍ PAMĚTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
4/43
 Ve FAP lze udržovat více procesů najednou
● čím více je procesů ve FAP, tím je větší
pravděpodobnost, že stále bude alespoň jeden
připravený
 Lze realizovat procesy požadující více paměti
než umožňuje FAP
● aniž se o řešení tohoto problému stará programátor /
kompilátor
● jinak bychom museli použít překryvy (overlays)
VIRTUÁLNÍ PAMĚŤ – VLASTNOSTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
5/43
 VIRT - Virtual Image (kb)
● The total amount of virtual memory used by the task. It includes all code, data and shared libraries plus
pages that have been swapped out.
 RES - Resident size (kb)
● The non-swapped physical memory a task has used.
 SHR - Shared Mem size (kb)
● The amount of shared memory used by a task. It simply reflects memory that could be potentially shared
with other processes.
PŘÍKLAD: LINUX – příkaz top
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
6/43
 Uložení obrazu LAP (virtuální paměti) v externí paměti
● nepoužívá se standardní systém souborů OS, používají
se speciální metody, optimalizované pro tento účel
● speciální partition/slice disku
 Stránkování / segmentaci musí podporovat hardware
správy paměti
● stránkování na žádost
● segmentování na žádost
● žádost – dynamicky kontextově generovaná indikace
nedostatku
 OS musí být schopen organizovat tok stránek /
segmentů mezi vnitřní a vnější pamětí
VIRTUÁLNÍ PAMĚŤ – VLASTNOSTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
7/43
LAP VĚTŠÍ NEŽ FAP
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
physical
memory
memory map
virtual memory
page 0
page 1
page 2
page v
8/43
 Stránkování na žádost (Demand paging)
● stránka se zobrazuje do FAP při odkazu na ni, pokud
ve FAP není již zobrazena
● počáteční shluky výpadků stránek
 Předstránkování (Prepaging)
● umístění na vnější paměti sousedních stránek v LAP
bývá blízké („sousedi“)
● princip lokality
● zavádí se více stránek než se žádá
● vhodné při inicializaci procesu
KDY ZAVÁDĚT STRÁNKU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
9/43
 Segmentace
● best-, first-, worstfit
 Stránkování
● nemusíme řešit
 Kombinace segmentování + stránkování
● nemusíme řešit
KAM STRÁNKU ZAVÉST?
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
10/43
 Uplatňuje se v okamžiku, kdy je FAP plný
 Typicky v okamžiku zvýšení stupně multitaskingu
 Kterou stránku „obětovat“ a vyhodit z FAP (politika výběru oběti)?
 Politika nahrazování
● určení oběti
● politika přidělování místa
● kolik rámců přidělit procesu?
● intra/extra (local/global) množina možných obětí
● oběti lze hledat jen mezi stránkami procesu, který vyvolal výpadek
stránky?
● oběti lze hledat i mezi stránkami ostatních procesů (např. podle priorit
procesů)?
● nelze obětovat kteroukoliv stránku
● někde rámce jsou „zamčeny“
● typicky I/O buffery, řídicí struktury OS, …
KTEROU STRÁNKU NAHRADIT?
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
11/43
 Stránka se zavádí do FAP jen když je potřebná
 Přínosy
● méně I/O operací
● menší požadavky na paměť
● rychlejší reakce
● může pracovat více uživatelů
 Kdy je stránka potřebná?
● byla odkazovaná
● legální reference
● Nachází se ve FAP, přeloží se logická adresa na fyzickou
● nelegální reference (porušení ochrany) → abort procesu
● reference stránky, která není ve FAP → její zavedení do FAP
● zprostředkovává OS
STRÁNKOVÁNÍ NA ŽÁDOST
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
12/43
 S každým řádkem PT je spojen
bit V/I (valid/invalid)
(1 → je ve FAP, 0 → není právě
ve FAP)
● iniciálně jsou všechny V/I bity
nastaveny na 0
 Při překladu adresy
● jestliže je bit valid/invalid roven
0, generuje se přerušení typu
„page fault“
BIT VALID-INVALID
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Frame # valid-invalid bit
1
1
1
1
0
.
.
.
0
0
page table
13/43
PŘÍKLAD: TABULKA STRÁNEK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
1 A
2 B
3 C
4 D
5 E
6 F
7 G
0
1
2
3
4 A
5
6 C
7
8
9 F
10
11
12
13
14
15
logical
memory
A B
EDC
F G H
physical
memory
0 4 v
1 i
2 6 v
3 i
4 i
5 9 v
6 i
7 i
page table
frame
valid-invalid
bit
14/43
 Pokud se stránka nenachází ve FAP je aktivován OS
pomocí přerušení „page fault“ (výpadek stránky)
 OS zjistí:
● nelegální reference → procesu je informován (např.
signál SIGSEGV)
● legální reference, ale stránka chybí v paměti → zavede
ji
 Zavedení stránky
● získání prázdného rámce
● zavedení stránky do tohoto rámce
● úprava tabulky, nastaven bit valid/invalid na 1
 Pak se opakuje instrukce, která způsobila „page
fault“
VÝPADEK STRÁNKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
15/43
ZPRACOVÁNÍ VÝPADKU STRÁNKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
load M
free frame
i
physical memory
operating system
page table
1
6
5 4
2
3
restart
instruction
reference
reset page
table
trap
page is on
backing store
bring in
missing page
16/43
 pokud není žádný rámec aktuálně označen jako
volný, musíme nějaký uvolnit
● nalezneme se „oběť“ – nepotřebnou stránku ve FAP
(nevíme, co je nepotřebné, můžeme pouze odhadovat)
● je-li to nutné, před uvolněním stránky ji zapíšeme na
disk
● pokud se do ní nezapsalo, její kopie na disku je aktuální
● zda se do stránky zapsalo zjistíme v bitu modify (dirty)
● bit modify nastavuje HW automaticky při zápisu do stránky
 Potřebujeme algoritmus pro hledání „oběti“ a řešení
náhrady
● kritérium optimality algoritmu: nejméně výpadků
stránek
VOLNÝ RÁMEC
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
17/43
 Odkazy na instrukce programu a na dat mají tendenci tvořit shluky
 Časová lokalita a prostorová lokalita
● provádění programu je s výjimkou skoků a volání podprogramů
sekvenční
● programy mají tendenci zůstávat po jistou dobu v rámci nejvýše
několika procedur (nelze jen něco volat a hned se vracet)
● většina iterativních konstruktů představuje malý počet často
opakovaných instrukcí
● často zpracovávanou datovou strukturou je pole dat nebo
posloupnost záznamů
 → lze dělat rozumné odhady o částech programu/dat potřebných
v nejbližší budoucnosti
 vnitřní paměť se může zaplnit
● něco umístit do FAP pak znamená nejdříve něco odložit z FAP
PRINCIP LOKALITY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
18/43
NÁHRADA STRÁNKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
4
victimf
physical memory
3
1
swap
desired
page in
swap out
victim
page
frame valid-invalid bit
page table
2
reset page
table for new
page
change to
invalid
0
f
i
v
19/43
 Kritérium optimality
● nejmenší pravděpodobnost výpadku stránky
 Čím více rámců máme, tím méně často dojde k
výpadku stránky
ALGORITMY URČENÍ OBĚTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
number of frames
numberofpagefaults
1 2 3 4 5 6
2
4
6
8
10
12
14
16
20/43
 Pouze základní typy
● existují desítky variant
 Optimální algoritmus
● příští odkazy na oběť je
nejpozdější ze všech
následných odkazů na
stránky
● generuje nejmenší počet
výpadků stránek
● neimplementovatelný, neboť
neznáme budoucnost
● používá se jen pro srovnání
 Algoritmus LRU (Least
Recently Used)
● oběť = nejdéle
neodkazovaná stránka
 Algoritmus FIFO (First-In-
First-Out)
● oběť = stránka nejdéle
zobrazená ve FAP
 Algoritmus poslední šance
● FIFO + vynechávání z
výběru těch stránek, na
které od posledního výběru
bylo odkázáno
ALGORITMY URČENÍ OBĚTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
21/43
 Posloupnost odkazů stránek:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 5 stránek
 3 rámce (3 stránky mohou být
ve FAP)
 4 rámce
● Beladyho anomálie
● více rámců → více výpadků
ALGORITMUS FIRST-IN-FIRST-OUT
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
1
2
3
1
2
3
4
1
2
5
3
4
9 výpadků
1
2
3
1
2
3
5
1
2
4
5 10 výpadků
44 3
22/43
BELADYHO ANOMÁLIE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
number of frames
numberofpagefaults
1 2 3 4 5 6 7
2
4
6
8
10
12
14
16
23/43
 Hodnocení FIFO strategie
● často používané stránky jsou v mnoha případech právě
ty nejstarší
● pravděpodobnost výpadku takové stránky je vysoká
● tj. algoritmus zbytečně odkládá často používané stránky
● jednoduchá implementace
● stačí udržovat ukazatelem vazbu do cyklického pořadí
ALGORITMUS FIRST-IN-FIRST-OUT
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
7
reference string
page frames
0
7
1
0
7
1
3
2
0
3
4
1
0
2
3
1
0
3
2
0
2
1
7
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
0
3
2
0
2
4
3
2
4
2
1
0
2
0
7
1
0
7
24/43
 Obětí je nejpozdější ze všech následných odkazů na
stránky
 Potřebuje znát budoucí posloupnost referencí
 Příklad
● proces s 5 stránkami
● k dispozici máme 4 rámce
● Posloupnost přístupů:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
● celkem 6 výpadků stránky
OPTIMÁLNÍ ALGORITMUS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
1
2
3
4
4 5
25/43
 Další příklad:
OPTIMÁLNÍ ALGORITMUS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
7
reference string
page frames
0
7
1
0
7
3
0
2
3
4
2
1
0
2
1
0
2
3
0
2
1
0
7
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
26/43
ANIMACE: OPTIMÁLNÍ ALGORITMUS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
27/43
 Obětí je nejdéle neodkazovaná stránka
● princip lokality říká, že pravděpodobnost jejího brzkého
použití je velmi malá
● výkon blízký optimální strategii
 Příklad:
● proces s 5 stránkami, k dispozici 4 rámce
● 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
ALGORITMUS LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
5
2
4
3
1
2
3
4
1
2
5
4
1
2
5
3
1
2
4
3
28/43
 Další příklad:
ALGORITMUS LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
7
reference string
page frames
0
7
1
0
7
3
0
2
3
0
4
1
0
2
2
3
1
2
3
0
7
0
1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
2
0
4
2
3
4
2
0
1
29/43
ANIMACE: ALGORITMUS LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
30/43
 V položkách PT se udržuje (HW)
čítač (sekvenční číslo nebo logický
čas) posledního přístupu ke stránce
● čítač má konečnou kapacitu
● problém jeho přečtení
 Zásobník
● zásobník čísel stránek, při přístupu
ke stránce je položka odstraněna
ze zásobníku a přemístěna na
vrchol (na spodu je „oběť“)
 Aproximace: iniciálně je bit nastaven
na 0, při každém přístupu je
nastaven bit přístupu na 1
● neznáme pořadí přístupu ke
stránkám
● víme jen které stránky byly použity
IMPLEMENTACE POLITIKY LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
reference string
4 7 0 7 1 0 1 2 1 2 7 1 2
2
1
0
7
4
7
2
1
0
4
stack
before
a
stack
after
b
a b
31/43
ANIMACE: IMPLEMENTACE POLITIKY LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
32/43
 Také nazývané „Máš ještě šanci“
 Výběr oběti – cyklické procházení
(podobně jako FIFO)
 Odkazem na stránku stránka se nastaví příznak
● ani násobné odkazy příznak nezvyšují, jen nastavují
 Oběť, která nemá nastaven příznak a je na řadě
při kruhovém procházení je nahrazovaná
 Experimenty ukazují, že optimalita algoritmu se blíží
skutečnému LRU
DRUHÁ ŠANCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
33/43
 Implementace
● Množina rámců kandidujících na nahrazení je
organizována jako cyklický buffer
● Když se stránka nahradí, ukazatel se posune na příští
rámec v bufferu
● Pro každý rámec se nastavuje „use bit“ na 1 když
● se do rámce zavede stránka poprvé
● kdykoliv se odpovídající stránka referencuje
● Když se má nalézt oběť, nahradí se stránka v prvním
rámci s „use bit“ nastaveným na 0.
● Při hledání kandidáta na nahrazení se každý „use bit“
nastavený na 1 nastavuje na 0
DRUHÁ ŠANCE (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
34/43
DRUHÁ ŠANCE (3)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
0
0
1
1
0
1
1
reference bits pages
circular queue of pages
(a)
circular queue of pages
(b)
…
…
next
victim
0
0
0
0
0
1
1
reference bits pages
…
…
35/43
 OPT
● super, ale nutnost znát
budoucnost
 LRU
● časové čítače u rámců, ∆t +
1, nulované odkazem
● oběť = rámec s nejvyšší
hodnotou čítače
● Implementace má vysokou
režii
 FIFO
● snadná implementace,
cyklický seznam
● špatná heuristika
 Druhá šance
● upravené FIFO
● z výběru obětí se vynechává
alespoň jednou odkázaná
stránka od posledního
výběru
● use_bit = (počátečně) 0 / po
odkazu 1
● úprava druhá šance
● use_bit = 0 / 1, doplněný
modified_bit = 0 / 1
● pořadí výběru: 00, 01, 1x
● 0x šetří výpis
nemodifikované stránky
SROVNÁNÍ ALGORITMŮ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
36/43
 int data[128][128];
 Jeden řádek odpovídá jedné stránce
 Program 1
for (j = 0; j <128; j++)
for (i = 0; i < 128; i++)
data[i,j] = 0;
● 128 x 128 = 16,384 výpadků stránky
 Program 2
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i,j] = 0;
● 128 výpadků stránky
STRUKTURA PROGRAMU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
37/43
THRASHING
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPUutilization
degree of multiprogramming
thrashing
38/43
Výukovou pomůcku zpracovalo
Servisní středisko pro e-learning na MU
http://is.muni.cz/stech/
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ