‹#›/41
PB153
OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Správa paměti
10

‹#›/41

lPro běh procesu je nutné, aby program, který je vykonáván byl umístěn v operační paměti (hlavní
paměti)
lZ 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Í

‹#›/41

lProgram 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“
lVí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

‹#›/41

lPř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
lPř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).
lZa 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, …
●
l
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

‹#›/41

lHardwarový modul převádějící logické adresy na fyzické adresy
lUživatelský program pracuje s logickými adresami, uživatelský program nevidí fyzické adresy
lPř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Í

‹#›/41

RELOKAČNÍ REGISTR
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU
relocation register
14000
+
MMU
memory
14346
346
logical adresses
physical adresses

‹#›/41

lLogický 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í
lLogické a fyzické adresové prostory se shodují v době kompilace a v době zavádění
lLogické 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Í

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

‹#›/41

lDynamic loading
lProgramový kód se nezavádí dokud není zavolán (spuštěn)
lDosahuje se lepšího využití paměti
●nepoužívané části kódu se nikdy nezavádí
lUž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
lProgram 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Í

‹#›/41

lLinux
●dlopen
●dlsym
●dlclose
lWindows API
●LoadLibrary(Ex)
●GetProcAddress
●FreeLibrary
DYNAMICKÉ ZAVÁDĚNÍ - PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/41

lDynamic linking
lVázání je odkládáno na dobu běhu
lPro 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
lPři zavolání stub nahradí sám sebe adresou skutečné funkce a předá jí řízení
lOS musí kontrolovat, zda funkce je mapována do paměti procesu
lJe to technika vhodná zvláště pro knihovní funkce
DYNAMICKÉ VÁZÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/41

lV operační paměti se uchovávají pouze ty instrukce a data, která jsou potřeba po celou dobu běhu
lTechnika, která je nutná v případech, kdy je přidělený prostor paměti menší než je souhrn potřeb
procesu
lVyvolávání překryvů je implementované programátorem, od OS se nepožaduje žádná speciální podpora
lNá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Í

‹#›/41

OVERLAY: PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
pass 1
pass 2
70K
80K
20K
30K
10K
symbol table
common routines
overlay driver

‹#›/41

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

‹#›/41

lOperační paměť se dělí do dvou sekcí
●rezidentní OS, obvykle na počátku FAP s tabulkou ovladačů přerušení
●uživatelské procesy
lPř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Í

‹#›/41

HW PODPORA
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU
limit register
relocation register
memory
physical address
yes
no
logical address
trap; addressing error
<
+

‹#›/41

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

‹#›/41

lKterou 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
lZ 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Í

‹#›/41

lVnější fragmentace
●souhrn volné paměti je dostatečný, ale ne v dostatečné souvislé oblasti
lvnitř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á
lSniž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Í

‹#›/41

lLAP procesu nemusí být jedinou souvislou sekcí FAP, LAP se zobrazuje do (po částech volných) sekcí
FAP
lFAP 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)
lLAP se dělí na sekce zvané stránky (pages)
●pevná délka, shodná s délkou rámců
lUdržujeme seznam volných rámců
lProgram délky n stránek se umístí (zavede) do n rámců
lPřeklad logická adresa → fyzická adresa − pomocí překladové tabulky nastavované OS a
interpretované MMU
lVzniká 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Í

‹#›/41

lLogická 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

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

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

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

‹#›/41

lJe uložena v operační paměti
lJejí počátek a konec je odkazován registrem
●Page-table base register (PTBR), Page-table length register (PTLR)
lZpří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
lProblé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Í

‹#›/41

STRÁNKOVÁNÍ S TLB
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU
d
p
d
f
physical memory
f
p
page table
page number
frame
number
TLB
TLB hit
TLB miss
logical address
physicaladdress

‹#›/41

l32-bitový procesor s 4KB stránkou
lPT (tabulka stránek) je stránkovaná
lLogická adresa
●číslo stránky: 20 bitů
●adresa ve stránce: 12 bitů
lČí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

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

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

‹#›/41

l1 položka v PT pro každý rámec paměti
lObsahuje
●logickou (virtuální) adresu stránky uchovávané v odpovídajícím rámci
●informaci o procesu, který stránku vlastní
lSnižuje se velikost paměti potřebné pro uchovávání PT
lZvyš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Í

‹#›/41

lNapř. AS400 (IBM), UltraSPARC, PowerPC
INVERTOVANÁ TABULKA: PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
CPU
d
p
pid
d
i
physical memory
logical address
physical address
p
pid
i
search
page table

‹#›/41

lSdí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
lPrivá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Í

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

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

‹#›/41

lLogická adresa je dvojice (segment s, offset d)
lTabulka segmentů, Segment table, ST
●base – počáteční adresa umístění segmentu ve FAP
●limit – délka segmentu
lSegment-table base register (STBR)
●odkaz na umístění ST v paměti
lSegment-table length register (STLR)
●počet segmentů, s je legální když s < STLR
lRelokace – dynamická, pomocí ST
SEGMENTOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

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

‹#›/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
offset
page
directory
linear address
page directory base register

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