1/41
PB153
OPERAČNÍ SYSTÉMY
A JEJICH ROZHRANÍ
Správa paměti
8
2/41
 Pro běh procesu je nutné, aby program, který je
vykonáván byl umístěn v operační paměti (hlavní
paměti)
 Z programu se stává proces (aktivní entita
schopná spuštění na CPU) provedením celé řady
kroků
● naplnění tabulek, umístění do operační paměti
● vázání adres instrukcí a dat na adresy operační paměti
PRINCIPY, ZÁKLADY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
3/41
 Program je složen z částí se vzájemně
odlišnými vlastnostmi
● moduly s instrukcemi jsou označovány
„jen ke spuštění“ (execute-only).
● datové moduly jsou buďto „read-only“
nebo „read/write“
● některé moduly jsou „soukromé“
(private), jiné jsou veřejné „public“
 Více procesů může sdílet společnou část paměti,
aniž by se tím porušovala ochrana paměti
● neboť sdílení jedné datové struktury je lepší řešení než
udržování konzistence násobných kopií vlastněných
jednotlivými proces
SPRÁVA PAMĚTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
subroutine
stack
symbol
table
main
program
sqrt
logical adresses
4/41
 Při kompilaci
● umístění v paměti je známé a priori
● lze generovat absolutní kód
● při změně umístění se musí program znovu přeložit
 Při zavádění
● umístění v paměti není známé v době
kompilace
● generuje se přemístitelný kód
(relocatable code).
 Za běhu
● jestliže proces může měnit svoji polohu
během provádění, vázání se zpožďuje
na dobu běhu
● musí být dostupná hardwarová podpora
● bázové registry, mezní registry, …
VÁZÁNÍ ADRES – MOŽNOSTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
operating
system
process
300040
0
256000
300040
420940
880000
1024000
base
120900
limit
process
process
5/41
 Hardwarový modul převádějící logické adresy na
fyzické adresy
 Uživatelský program pracuje s logickými
adresami, uživatelský program nevidí fyzické
adresy
 Připočítává se obsah „relokačního registru“ k
adresám generovaným uživatelským procesem v
okamžiku, kdy je předávána jako ukazatel do
operační paměti
MEMORY-MANAGEMENT UNIT
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
6/41
RELOKAČNÍ REGISTR
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU
relocation
register
14000
+
MMU
memory
14346346
logical
adresses
physical
adresses
7/41
 Logický adresový prostor (LAP), fyzický adresový
prostor (FAP)
● LAP – (logická adresa, virtuální adresa) dána adresou
ve strojovém jazyku, generuje CPU
● FAP – (fyzická) adresa akceptovaná operační pamětí
 Logické a fyzické adresové prostory se shodují v
době kompilace a v době zavádění
 Logické a fyzické adresové prostory mohou být
rozdílné při vázání v době běhu
ADRESOVÝ PROSTOR
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
8/41
PROCES VYTVÁŘENÍ PROGRAMU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
source
program
compiler or
assembler
object
module
linkage editor
load
module
loader
in-memory
binary
memory
image
other
object
modules
system
library
dynamically
loaded
system
library
compile
time
load
time
execution time
(run time)
dynamic
linking
9/41
 Dynamic loading
 Programový kód se nezavádí dokud není zavolán
(spuštěn)
 Dosahuje se lepšího využití paměti
● nepoužívané části kódu se nikdy nezavádí
 Užitečná technika v případech, kdy se musí velkými
programovými moduly řešit zřídka se vyskytující
alternativy
● Např. tzv. plug-in moduly
 Program nevyžaduje žádnou speciální podporu od
operačního systému
DYNAMICKÉ ZAVÁDĚNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
10/41
 Linux
● dlopen
● dlsym
● dlclose
 Windows API
● LoadLibrary(Ex)
● GetProcAddress
● FreeLibrary
DYNAMICKÉ ZAVÁDĚNÍ - PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
11/41
 Dynamic linking
 Vázání je odkládáno na dobu běhu
 Pro umístění příslušných knihovních programů
rezidentních v operační paměti se používá kód
malého rozsahu – tzv. stub
 Při zavolání stub nahradí sám sebe adresou
skutečné funkce a předá jí řízení
 OS musí kontrolovat, zda funkce je mapována do
paměti procesu
 Je to technika vhodná zvláště pro knihovní funkce
DYNAMICKÉ VÁZÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
12/41
 V operační paměti se uchovávají pouze ty instrukce a
data, která jsou potřeba po celou dobu běhu
 Technika, která je nutná v případech, kdy je přidělený
prostor paměti menší než je souhrn potřeb procesu
 Vyvolávání překryvů je implementované
programátorem, od OS se nepožaduje žádná
speciální podpora
 Návrh překryvové struktury ze strany programátora je
značně složitý
PŘEKRYVY, OVERLAYS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
13/41
OVERLAY: PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
pass 1 pass 270K 80K
20K
30K
10K
symbol
table
common
routines
overlay
driver
14/41
ANIMACE: OVERLAY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
15/41
 Operační paměť se dělí do dvou sekcí
● rezidentní OS, obvykle na počátku FAP s tabulkou
ovladačů přerušení
● uživatelské procesy
 Přidělování jedné souvislé části paměti
● pro ochranu procesů uživatelů mezi sebou a OS lze
použít schéma s relokačním registrem
● relokační registr: hodnota nejmenší fyzické adresy
paměti procesu
● mezní registr: rozpětí logických adres,
logická adresa musí být menší nebo rovna meznímu
registru
SOUVISLÉ OBLASTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
16/41
HW PODPORA
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU
limit
register
relocation
register
memory
physical
addressyes
no
logical
address
trap; addressing error
< +
17/41
 Přidělování několika částí paměti
● díra – blok dostupné paměti
● Bloky jsou roztroušeny po FAP
● evidenci o přidělených a volných sekcí udržuje OS
SOUVISLÉ OBLASTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
OS
process 5
process 8
process 2
OS
process 5
process 2
OS
process 5
process 2
OS
process 5
process 9
process 2
process 9
process 10
18/41
 Kterou oblast délky n přidělit, když volná paměť je rozmístěna ve více
souvislých nesousedních sekcích?
● First-fit:
● přiděluje se první dostatečně dlouhá volná oblast resp. její počátek
● Best-fit:
● přiděluje se nejmenší dostatečně dlouhá volná oblast resp. její
počátek
● generují se velmi malé (nejmenší) možné volné díry
● Worst-fit:
● přiděluje se největší dostatečně dlouhá volná oblast resp. její počátek
● generují se největší možné volné díry
 Z hlediska rychlosti a kvality využití paměti jsou First-fit a Best-fit jsou
lepší techniky než technika Worst-fit
PŘIDĚLOVÁNÍ PAMĚTI
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
19/41
 Vnější fragmentace
● souhrn volné paměti je dostatečný, ale ne v dostatečné souvislé
oblasti
 vnitřní fragmentace
● přidělená oblast paměti je větší než požadovaná velikost, tj. část
přidělené paměti je nevyužitá
 Snižování vnější fragmentace setřásáním
● přesouvají se obsahy paměti s cílem vytvořit (jeden) velký volný
blok
● použitelné jen když je možná dynamická relokace (viz MMU)
● provádí se v době běhu
● problém I/O
● s vyrovnávacími paměťmi plněnými z periférií autonomně nelze hýbat
– umisťují se proto do prostoru OS
PROBLÉM FRAGMENTACE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
20/41
 LAP procesu nemusí být jedinou souvislou sekcí FAP, LAP se
zobrazuje do (po částech volných) sekcí FAP
 FAP se dělí na sekce zvané rámce (frames)
● pevná délka, délka v násobcích mocnin 2 (obvykle mezi 512 až
8192 bajty)
 LAP se dělí na sekce zvané stránky (pages)
● pevná délka, shodná s délkou rámců
 Udržujeme seznam volných rámců
 Program délky n stránek se umístí (zavede) do n rámců
 Překlad logická adresa → fyzická adresa − pomocí překladové
tabulky nastavované OS a interpretované MMU
 Vzniká vnitřní fragmentace, neboť paměť je procesu přidělována v
násobcích velikosti rámce
STRÁNKOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
21/41
 Logická adresa (generovaná CPU) se dělí
● číslo stránky, p
● index do tabulky stránek
● index bázové adresy rámce přiděleného stránce, které
patří logická adresa
● offset ve stránce, d
● přičítáme k začátku stránky/rámce
DYNAMICKÝ PŘEKLAD ADRES
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
stránka offset
22/41
PŘÍKLAD STRÁNKOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU p d f d
p
logical
adresses
physical
adresses
f
page table
physical
memory
f
f0000 … 0000
f1111 … 1111
23/41
PŘÍKLAD STRÁNKOVÁNÍ (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
0 1
1 4
2 3
3 7
0
1 page 0
2
3 page 2
4 page 1
5
6
7 page 3
frame
number
physical
memory
page table
page 0
page 1
page 2
page 3
logical
memory
0 5
1 6
2 1
3 2
0
4 i
j
k
l
8 m
n
o
p
12
16
20 a
b
c
d
24 e
f
g
h
28
page table
0
1
2
3
a
b
c
d
4
5
6
7
e
f
g
h
8
9
10
11
i
j
k
l
12
13
14
15
m
n
o
p
logical
memory
physical
memory
24/41
PŘÍKLAD STRÁNKOVÁNÍ (3)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
page 0
page 1
page 2
page 3
new process
free-frame list
14
13
18
20
15
page 0
page 1
page 2
page 3
new process
free-frame list
15
13
14
15
16
17
18
19
20
21
13 page 1
14 page 0
15
16
17
18 page 2
19
20 page 3
21
0 14
1 13
2 18
3 20
new process page table
(a) (b)
25/41
 Je uložena v operační paměti
 Její počátek a konec je odkazován registrem
Page-table base register (PTBR), Page-table length
register (PTLR)
 Zpřístupnění údaje / instrukce v operační paměti
vyžaduje dva přístupy do operační paměti
● jednou do tabulky stránek
● jednou pro údaj/instrukci
 Problém zhoršení efektivnosti dvojím přístupem lze
řešit speciální rychlou hardwarovou cache pamětí
● asociativní paměť
● translation look-aside buffers (TLBs)
TABULKA STRÁNEK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
26/41
STRÁNKOVÁNÍ S TLB
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU dp
df
physical memory
f
p
page table
page
number
frame
number
TLB
TLB hit
TLB miss
logical
address
physicala
ddress
27/41
 32-bitový procesor s 4KB stránkou
 PT (tabulka stránek) je stránkovaná
 Logická adresa
● číslo stránky: 20 bitů
● adresa ve stránce: 12 bitů
 Číslo stránky se dále dělí
● číslo stránky 10-bitů
● adresa v tabulce stránek 10-bitů
DVOUÚROVŇOVÁ TABULKA STRÁNEK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
page number page offset
pi p2 d
10 10 12
28/41
DVOUÚROVŇOVÁ TABULKA STRÁNEK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
outer-page
table
1
500
100
708
929
900
page of
page table
page table memory
0
1
100
500
708
900
929
29/41
TVORBA ADRESY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
p1 p2 d
p1
outer-page
table
p2
page of
page table
d
logical address
30/41
 1 položka v PT pro každý rámec paměti
 Obsahuje
● logickou (virtuální) adresu stránky uchovávané v
odpovídajícím rámci
● informaci o procesu, který stránku vlastní
 Snižuje se velikost paměti potřebné pro uchovávání
PT
 Zvyšuje se doba přístupu do PT, indexový přístup je
nahrazen prohledáváním
● lze zvýšit efektivnost využitím hašování
● perfektní hašování – 1 přístup k PT
● jinak několik přístupů k PT
INVERTOVANÁ TABULKA STRÁNEK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
31/41
 Např. AS400 (IBM), UltraSPARC, PowerPC
INVERTOVANÁ TABULKA: PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU dppid di
physical
memory
logical
address
physical
address
ppid
isearch
page table
32/41
 Sdílený kód je umístěn v paměti pouze jednou
● kód je reentrantní a „read-only“
● musí se nacházet na stejné logické adrese ve všech
procesech
 Privátní data
● každý proces udržuje svoji privátní kopii dat
(a nesdíleného kódu)
SDÍLENÍ STRÁNEK
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
33/41
SDÍLENÍ STRÁNEK: PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
0
1 data 1
2 data 3
3 ed 1
4 ed 2
5
6 ed 3
7 data 2
8
9
10
3
4
6
7
ed 1
ed 2
ed 3
data 2
process P2
page table
for P2
3
4
6
1
ed 1
ed 2
ed 3
data 1
process P1
page table
for P1
3
4
6
2
ed 1
ed 2
ed 3
data 3
process P3
page table
for P3
34/41
SEGMENTOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
1
3
2
4
1
4
2
3
physical memory space
subroutine
stack
symbol
table
main
program
sqrt
logical adresses space
user space
35/41
 Logická adresa je dvojice (segment s, offset d)
 Tabulka segmentů, Segment table, ST
● base – počáteční adresa umístění segmentu ve FAP
● limit – délka segmentu
 Segment-table base register (STBR)
● odkaz na umístění ST v paměti
 Segment-table length register (STLR)
● počet segmentů, s je legální když s < STLR
 Relokace – dynamická, pomocí ST
SEGMENTOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
36/41
PŘÍKLAD SEGMENTACE
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
logical adresses space
subroutine
segment 0
stack
segment 3
symbol
table
segment 4
Sqrt
segment 1
main
program
segment 2
limit base
0 1000 1400
1 400 6300
2 400 4300
3 1100 3200
4 1000 4700
1400
2400
segment 0
3200
4300
segment 3
4700
segment 2
5700
segment 4
6300
6700
segment 1
physical memory
segment table
37/41
STRÁNKOVÁNÍ A SEGMENTOVÁNÍ (INTEL 386)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
logical adress selector offset
descriptor table
+segment descriptor
page frame
physical address
page table
page table entry
page directory
directory entry
offsetpagedirectorylinear address
page directory
base register
38/41
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Í