‹#›/43
PB153
OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Virtuální paměť
11

‹#›/43

lVirtuá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
lTechniky 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Í

‹#›/43

lČást procesu umístěnou ve FAP nazýváme „rezidentní množinou“ (resident set)
lOdkaz mimo rezidentní množinu způsobuje přerušení výpadek stránky (page fault)
lOS označí proces za „čekající“
lOS spustí I/O operace a provede nutnou správu paměti pro zavedení odkazované části do FAP
lMezitím běží jiný proces (jiné procesy)
lPo zavedení odkazované části se generuje I/O přerušení
●OS příslušný proces umístí mezi připravené procesy
lPř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Í

‹#›/43

lVe 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ý
lLze 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Í

‹#›/43

lVIRT -  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.
lRES  -  Resident size (kb)
●The non-swapped physical memory a task has used.
lSHR  -  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Í

‹#›/43

lUlož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
lStrá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
lOS 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Í

‹#›/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

‹#›/43

lStrá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
lPř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Í

‹#›/43

lSegmentace
●best-, first-, worstfit
lStránkování
●nemusíme řešit
lKombinace segmentování + stránkování
●nemusíme řešit
KAM STRÁNKU ZAVÉST?
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/43

lUplatňuje se v okamžiku, kdy je FAP plný
lTypicky v okamžiku zvýšení stupně multitaskingu
lKterou stránku „obětovat“ a vyhodit z FAP (politika výběru oběti)?
lPolitika 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Í

‹#›/43

lStránka se zavádí do FAP jen když je potřebná
lPřínosy
●méně I/O operací
●menší požadavky na paměť
●rychlejší reakce
●může pracovat více uživatelů
lKdy 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Í

‹#›/43

lS 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
lPř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

‹#›/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
E
D
C
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

‹#›/43

lPokud se stránka nenachází ve FAP je aktivován OS pomocí přerušení „page fault“ (výpadek stránky)
lOS zjistí:
●nelegální reference → procesu je informován (např. signál SIGSEGV)
●legální reference, ale stránka chybí v paměti → zavede ji
lZavedení 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
lPak se opakuje instrukce, která způsobila „page fault“
VÝPADEK STRÁNKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/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

‹#›/43

lpokud 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
lPotř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Í

‹#›/43

lOdkazy na instrukce programu a na dat mají tendenci tvořit shluky
lČ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ů
l→ lze dělat rozumné odhady o částech programu/dat potřebných v nejbližší budoucnosti
lvnitř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Í

‹#›/43

NÁHRADA STRÁNKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
4
victim
f
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

‹#›/43

lKritérium optimality
●nejmenší pravděpodobnost výpadku stránky
lČím více rámců máme, tím méně často dojde k výpadku stránky
l
l
l
l
l
l
l
ALGORITMY URČENÍ OBĚTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
number of frames
1
2
3
4
5
6
2
4
6
8
10
12
14
16

‹#›/43

lPouze základní typy
●existují desítky variant
lOptimá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í
lAlgoritmus LRU (Least Recently Used)
●oběť = nejdéle neodkazovaná stránka
lAlgoritmus FIFO (First-In-First-Out)
●oběť = stránka nejdéle zobrazená ve FAP
lAlgoritmus 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Í

‹#›/43

lPosloupnost odkazů stránek:
l 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
l
l5 stránek
l3 rámce (3 stránky mohou být ve FAP)
l
l4 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ů
4
4
3

‹#›/43

BELADYHO ANOMÁLIE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
number of frames
1
2
3
4
5
6
7
2
4
6
8
10
12
14
16

‹#›/43

lHodnocení 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
1
7

‹#›/43

lObětí je nejpozdější ze všech následných odkazů na stránky
lPotřebuje znát budoucí posloupnost referencí
lPří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

‹#›/43

lDalší 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

‹#›/43

ANIMACE: OPTIMÁLNÍ ALGORITMUS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/43

lObě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
lPří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

‹#›/43

lDalší příklad:
l
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

‹#›/43

ANIMACE: ALGORITMUS LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/43

lV 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í
lZá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ěť“)
lAproximace: 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
l
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

‹#›/43

ANIMACE: IMPLEMENTACE POLITIKY LRU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/43

lTaké nazývané „Máš ještě šanci“
lVýběr oběti – cyklické procházení
(podobně jako FIFO)
lOdkazem na stránku stránka se nastaví příznak
●ani násobné odkazy příznak nezvyšují, jen nastavují
lOběť, která nemá nastaven příznak a je na řadě
při kruhovém procházení je nahrazovaná
lExperimenty ukazují, že optimalita algoritmu se blíží skutečnému LRU
l
DRUHÁ ŠANCE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/43

lImplementace
●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Í

‹#›/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

‹#›/43

lOPT
●super, ale nutnost znát budoucnost
lLRU
●časové čítače u rámců, ∆t + 1, nulované odkazem
●oběť = rámec s nejvyšší hodnotou čítače
●Implementace má vysokou režii
lFIFO
●snadná implementace, cyklický seznam
●špatná heuristika
lDruhá š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Í

‹#›/43

lint data[128][128];
lJeden řádek odpovídá jedné stránce
lProgram 1
l                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
lProgram 2
●             for (i = 0; i < 128; i++)
               for (j = 0; j < 128; j++)
                     data[i,j] = 0;
●128 výpadků stránky
l
STRUKTURA PROGRAMU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/43

THRASHING
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
degree of multiprogramming
thrashing

‹#›/43

1.A alokuje 64K
2.B alokuje 128K
3.C alokuje 64K
4.D alokuje 128K
BUDDY ALOKAČNÍ ALGORITMUS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
5.C uvolňuje paměť
6.A uvolňuje paměť
7.B uvolňuje paměť
8.D uvolňuje paměť
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
64K
t = 0
1024K
t = 1
A-64K
64K
128K
256K
512K
t = 2
A-64K
64K
B-128K
256K
512K
t = 3
A-64K
C-64K
B-128K
256K
512K
t = 4
A-64K
C-64K
B-128K
D-128K
128K
512K
t = 5
A-64K
64K
B-128K
D-128K
128K
512K
t = 6
128K
B-128K
D-128K
128K
512K
t = 7
256K
D-128K
128K
512K
t = 8
1024K

‹#›/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Í