ˇ
Správa pamäti, 1. cast’
Úvod, metódy pridel’ovania pamäti
Ing. Viliam Solˇcány, PhD.
solanyfiit.stuba.sk
ZS 2011/2012
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 1 / 45
Osnova
Úvod
Metódy pridel’ovania
pamäti
Úvod
Organizácia pamäti
Možnosti adresovania v programoch
Požiadavky kladené na systém správy pamäti
Obraz procesu
Dynamický výpoˇcet adries
Metódy pridel’ovania pamäti
Metódy pridel’ovania pamäti – prehl’ad
Monoprogramovanie
Monoprogramovanie versus multiprogramovanie
Úseky pevnej d´lžky (Fixed Partitioning)
Úseky variabilnej d´lžky (Dynamic Partitioning)
Dvojice úsekov (Buddy system)
Stránkovanie
Segmentácia
Segmentácia so stránkovaním
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 2 / 45
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
adries
Metódy pridel’ovania
pamäti
Viliam Solˇcány, FIIT STU Bratislava
Úvod
Operaˇcné systémy 2011/12
Predn. 7 – 3 / 45
Organizácia pamäti
Úvod
• Ideál programátora – neobmedzene vel’ká pamät’, rýchla, lacná,
• Organizácia pamäti
• Možnosti adresovania
perzistentná
v programoch
• Požiadavky kladené
na systém správy
pamäti
◦ Taká pamät’ neexistuje
• Obraz procesu
• Dynamický výpoˇcet
• Rýchlejšia pamät’ je drahšia ⇒ je jej menej ⇒ hierarchia pamätí
adries
registre
cache
hlavná pamät’
Metódy pridel’ovania
pamäti
magnetické disky
CD, DVD
magnetické pásky
• Dôležité z hl’adiska OS
◦ Vykonávané procesy sú v hlavnej pamäti
◦ Disk slúži ako záložná (sekundárna) pamät’
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 4 / 45
Organizácia pamäti (2)
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
• Pamät’ je tvorená koneˇcným poˇctom pamät’ových miest
• Podl’a spôsobu prístupu
◦ Pamät’ so sekvenˇcným prístupom
•
•
adries
Napr. magnetická páska
Modelová údajová štruktúra – zret’azený zoznam
Tail
Head
Metódy pridel’ovania
pamäti
◦ Pamät’ s priamym prístupom (Random Access Memory)
•
•
Napr. hlavná pamät’
Modelová údajová štruktúra – pole
0
•
Viliam Solˇcány, FIIT STU Bratislava
1
2
3
n−1
Prvky sú prístupné pomocou indexov (adries)
Operaˇcné systémy 2011/12
Predn. 7 – 5 / 45
Organizácia pamäti (3)
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Pamät’ podl’a spôsobu adresovania
◦ Poziˇcná – “bežná” pamät’
•
• Obraz procesu
• Dynamický výpoˇcet
Adresa urˇcuje pozíciu
odkazovanej položky
data
addr
int i, p, pole[N℄;
p = *(pole + i);
// p = pole[i℄;
adries
Metódy pridel’ovania
pamäti
•
T.j. adresy (indexy) nie
sú v pamäti uložené
◦ Asociatívna – “pamät’ adresovaná obsahom”
•
Pamät’ obsahuje dvojice
(k©ú£, hodnota)
•
Viliam Solˇcány, FIIT STU Bratislava
key
key
value
value
Adresa je kl’úˇc patriaci
požadovanej hodnote
Operaˇcné systémy 2011/12
Predn. 7 – 6 / 45
Možnosti adresovania v programoch
Úvod
• Pre prácu s pamät’ou sú potrebné absolútne (fyzické) adresy
• Organizácia pamäti
• Možnosti adresovania
Absolute
addr
v programoch
• Požiadavky kladené
na systém správy
pamäti
1024
CODE
JUMP 1424
• Obraz procesu
• Dynamický výpoˇcet
1424
adries
LOAD 2224
Metódy pridel’ovania
pamäti
DATA
2224
• Ako to dosiahnut’
1.
2.
3.
Program je zostavený s absolútnymi adresami
Absolútne adresy poˇcíta zavádzaˇc (loader)
Absolútne adresy sa poˇcítajú za behu programu
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 7 / 45
Možnosti adresovania v programoch (2)
1.
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
Program je zostavený s absolútnymi adresami
• Výpoˇcet adries robí programátor, kompilátor
• Rýchle za behu, ale
• Program musí byt’ zavedený od danej adresy – žiadna
flexibilita
• Obraz procesu
• Dynamický výpoˇcet
adries
Absolute address
Metódy pridel’ovania
pamäti
Program
2.
Main memory
Absolútne adresy poˇcíta zavádzaˇc (loader)
• Kompilátor vloží adresy relatívne voˇci (obvykle) zaˇciatku
• Zavádzaˇc modifikuje adresy pred zavedením – vloží
absolútne adresy pre danú adresu zaˇciatku
• Program je možné zaviest’ od l’ubovol’nej adresy
• Premiestnenie (relokácia) neskôr nie je možné – je dôležité
pre výmeny (swapping), kompakciu
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 8 / 45
Možnosti adresovania v programoch (3)
Úvod
• Absolútne versus relatívne adresy
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
Absolute
addr
1024
CODE
• Obraz procesu
• Dynamický výpoˇcet
400
1424
LOAD 2224
LOAD 1200
DATA
DATA
1200
2224
Viliam Solˇcány, FIIT STU Bratislava
JUMP 400
JUMP 1424
adries
Metódy pridel’ovania
pamäti
Relative
addr
0
CODE
Operaˇcné systémy 2011/12
Predn. 7 – 9 / 45
Možnosti adresovania v programoch (4)
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
adries
Metódy pridel’ovania
pamäti
3.
Absolútne adresy sa poˇcítajú za behu programu
• Kompilátor vloží relatívne adresy, s nimi sa program zavedie
• Adresovací hardvér pri každom prístupe do pamäti vypoˇcíta
absolútnu (fyzickú) adresu
• Zavedenie možné od l’ubovol’nej adresy, možná aj relokácia!
• Dá sa robit’ tiež kontrola hraníc – ochrana pamäti
(memory protection)
Base reg
Relative address
INTR
11111
00000
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
Bounds reg
Program
Viliam Solˇcány, FIIT STU Bratislava
Addressing HW
Operaˇcné systémy 2011/12
Main memory
Predn. 7 – 10 / 45
Požiadavky kladené na systém správy pamäti
ˇ
• Premiestnovanie
(Relocation)
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
◦ Hlavná pamät’ je zdiel’aná mnohými procesmi
◦ V cˇ ase písania/zostavovania programu nie je možné urˇcit’ kde
◦
adries
Metódy pridel’ovania
pamäti
v pamäti bude zavedený
Proces môže byt’ poˇcas svojej existencie (vel’akrát) odsunutý
do záložnej pamäti, pri opätovnom zavedení do hlavnej
pamäti pôvodné miesto nemusí byt’ k dispozícii
• Ochrana (Protection)
◦ Proces nesmie svojvol’ne pristupovat’ k pamät’ovým miestam,
◦
ktoré patria iným procesom alebo OS
Nedá sa zabezpeˇcit’ v cˇ ase kompilácie
•
•
Lokácia procesu nie je známa, teda ani absolútne adresy
ˇ
Programovacie jazyky (napr. C) umožnujú
dynamický
výpoˇcet adries
◦ Musí zabezpeˇcit’ HW (OS nie je “pri tom” ked’ sa vykonávajú
inštrukcie procesu)
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 11 / 45
Požiadavky kladené na systém správy pamäti (2)
Úvod
Príklad
• Organizácia pamäti
• Možnosti adresovania
hlavna_pamat
0
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
v programoch
• Požiadavky kladené
na systém správy
pamäti
100
PC
8000
dispecer
11111111111
00000000000
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
• Obraz procesu
• Dynamický výpoˇcet
adries
5000
Proces A
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
Metódy pridel’ovania
pamäti
8000
Proces B
12000
Proces C
11111111111
00000000000
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
00000000000
11111111111
Bez ochrany pamäti by mohol proces A vykonat’ napr.
alebo STORE 116
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
JUMP 8004,
Predn. 7 – 12 / 45
Požiadavky kladené na systém správy pamäti (3)
• Spoloˇcná pamät’ (Sharing)
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
adries
Metódy pridel’ovania
pamäti
ˇ
◦ Mechanizmus ochrany musí byt’ flexibilný, aby umožnoval
◦
◦
riadený prístup k spoloˇcnej pamäti, ak to procesy potrebujú
Kooperujúce procesy pristupujú k spoloˇcným dátam
Viaceré procesy s rovnakým kódom zdiel’ajú kód
• Logická organizácia
◦ Programy je cˇ asto vhodné štruktúrovat’ do modulov
◦ Je výhodné ked’ systém správy pamäti toto podporuje:
•
•
•
Moduly je možné samostatne vyvíjat’, referencie medzi
modulmi rieši systém v cˇ ase behu
Moduly môžu mat’ nastavené rôzne ochrany (read-only,
execute-only)
Otvára sa možnost’ zaviest’ mechanizmy pre zdiel’anie
modulov – ked’že moduly špecifikuje používatel’, môže im
nastavit’ stupenˇ zdiel’ania
◦ Moduly podporuje spôsob správy pamäti zvaný segmentácia
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 13 / 45
Požiadavky kladené na systém správy pamäti (4)
Úvod
• Fyzická organizácia
• Organizácia pamäti
• Možnosti adresovania
◦ V systéme je nevyhnutné využívat’ asponˇ dve úrovne
v programoch
• Požiadavky kladené
na systém správy
pamäti
pamät’ovej hierarchie
•
• Obraz procesu
• Dynamický výpoˇcet
adries
•
Metódy pridel’ovania
pamäti
•
Hlavná pamät’ nemá dostatoˇcnú kapacitu – platí vždy :-)
Hlavná pamät’ nie je perzistentná (je volatilná)
Záložná pamät’ (disk) je väˇcšia, je perzistentná
◦ Z toho vyplýva potreba presunov dát medzi hlavnou a
záložnou pamät’ou
•
1
Je žiadúce aby to zabezpeˇcoval systém správy pamäti, nie
programátor1
Ako kontrapríklad slúži technika zvaná overlaying, ktorá sa snaží riešit’ problém nedostatoˇcnej kapacity hlavnej pamäti postupným (striedavým) zavádzaním modulov
programu. Musí to ale zabezbeˇcit’ programátor, cˇ o je nepríjemné.
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 14 / 45
Obraz procesu
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
adries
Metódy pridel’ovania
pamäti
• Pamät’ový obraz procesu (core image) typicky pozostáva z troch
cˇ astí – segmentov, regiónov : kód (text), dáta, zásobník (stack)
long n;
int fun(void) {
long *p1 = &n; // ptr to data
int (*p2) = fun; // to ode
void *p3 = &p2;
// to stak
}
p1
p2
p3
stack
n
data
func
text
• Obraz procesu musí byt’ umiestnený v hlavnej pamäti, aby
proces mohol bežat’
◦ OS rozhoduje (vyhl’adá miesto) kam (od ktorej adresy) bude
proces umiestnený
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 15 / 45
ˇ adries
Dynamický výpocet
Úvod
Base reg
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
Relative address
INTR
• Obraz procesu
• Dynamický výpoˇcet
111111
000000
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
Core
Image
Bounds reg
adries
Program
Metódy pridel’ovania
pamäti
Addressing HW
Main memory
• Pri jednoduchej relokácii (na obr.) program používa relatívne
adresy
• Dá sa zovšeobecnit’ – prepoˇcet adries môže byt’ “l’ubovol’ná”
operácia, nielen ’+’
◦ Program pracuje s logickými adresami
◦ Hlavná pamät’ sa adresuje fyzickými adresami
◦ Prepoˇcet logických adries na fyzické je preklad adries
◦ Spôsob logického adresovania, preklad adries a umiestnenie
procesu v pamäti vzájomne súvisia
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 16 / 45
ˇ adries (2)
Dynamický výpocet
• Rozsah logických adries, ktoré môže používat’ program je logický
Úvod
• Organizácia pamäti
• Možnosti adresovania
v programoch
• Požiadavky kladené
na systém správy
pamäti
• Obraz procesu
• Dynamický výpoˇcet
adries
Metódy pridel’ovania
pamäti
adresový priestor
ˇ
• Rozsah fyzických adries, ktoré fyzická pamät’ umožnuje
používat’
je fyzický adresový priestor
• Adresovací HW je zaradený medzi samotný procesor a pamät’
◦ Jednotka správy pamäti – Memory Management Unit, MMU
◦ Na cˇ ipe procesora
• Správa pamäti vyžaduje spoluprácu OS a MMU
ˇ
◦ OS rozhoduje o umiestnení procesu a podl’a toho nap´lna
◦
◦
◦
registre MMU
OS zabezpeˇcuje tiež zavedenie a príp. výmeny procesov
MMU robí preklad adries a tiež kontrolu “legálnosti”
prekladaných adries
OS ošetruje výnimky vzniknuté pri preklade
ˇ
• Existujú rôzne metódy pridel’ovania pamäti (t.j. umiestnovania
procesov do pamäti) a s tým súvisiace spôsoby logického
adresovania a prekladu adries
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 17 / 45
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
Metódy pridel’ovania pamäti
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 18 / 45
Metódy pridel’ovania pamäti – prehl’ad
• Monoprogramovanie
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
• Jednoduché metódy pridel’ovania pamäti pre
multiprogramovanie/multiprocesing
◦ Úseky (oblasti) pevnej d´lžky
◦ Úseky variabilnej d´lžky
◦ Dvojice úsekov (Buddy system)
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
• Sofistikované, dômyselnejšie metódy
Bez výmen /
s výmenami
(swap)
◦ Stránkovanie
◦ Segmentácia
◦ Segmentácia so stránkovaním
stránkovaním
• Virtuálna pamät’
Výmeny procesov (swap) – proces z hlavnej pamäti sa odsunie do
záložnej pamäti (disk), aby sa vytvorilo miesto pre iný proces
• Ak všetky procesy v hlavnej pamäti sú blokované
• Ak sa všetky aktívne procesy nevojdú do hlavnej pamäti
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 19 / 45
Monoprogramovanie
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
• Najjednoduchší spôsob pridel’ovania pamäti
• V pamäti je (okrem OS) jeden proces, po jeho ukonˇcení môže
byt’ zavedený d’alší ⇒ výmeny procesov (“swapovanie”) nie sú
• Rôzne možnosti realizácie:
versus
multiprogramovanie
• Úseky pevnej d´lžky
0xFF...
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
OS in ROM
User
Program
Device drivers
in ROM
0xFF...
User
Program
User
Program
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
0xFF...
OS in RAM
OS in RAM
0x00...
0x00...
0x00...
Old mainframes,
Palmtop,
Early PC
minicomputers
embedded
(MS-DOS)
systems
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 20 / 45
Monoprogramovanie versus multiprogramovanie
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
• Využitie procesora (utilization) pri monoprogramovaní je nízke
◦ Ked’ proces vykonáva I/O operáciu, procesor “nemá cˇ o robit’”
◦ I/O zariadenia sú voˇci procesoru vel’mi pomalé
◦ Procesy s cˇ astými I/O operáciami, napr. spracovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
hromadných dát ⇒ procesor môže až 90% cˇ asu strávit’
cˇ akaním
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
• Multiprogramovanie
◦ n nezávislých procesov, každý cˇ aká na I/O s pravdep. p
⇒ využitie procesora je utilization = 1 − pn
◦ Napr. pre p = 0.8 a n = 10 je utilization = 0.892
◦ Presnejšie modely využitia procesora (aj I/O zariadení)
◦
– systémy hromadnej obsluhy (queuing systems)
Pozri tiež predn. 3 – Prierez históriou OS
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 21 / 45
Úseky pevnej d´lžky (Fixed Partitioning)
Úvod
• Pamät’ je pri štarte systému rozdelená na úseky, ktoré sa poˇcas
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
behu systému nemenia
• Do každého úseku môže byt’ zavedený jeden proces
• Úseky majú rovnakú vel’kost’, alebo rôzne vel’kosti
ˇ
• Umiestnovanie
procesov
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
◦ Ak sú úseky rovnako vel’ké, proces sa umiestni do
hociktorého vol’ného
•
Znaˇcná vnútorná fragmentácia – neefektívne využívanie
pamäti
◦ Pri rôznych vel’kostiach úsekov – umiestnenie do
najmenšieho možného úseku (pre danú vel’kost’ procesu)
minimalizuje vnútornú fragmentáciu
•
ˇ ak taký úsek nie je vol’ný, ale je vol’ný väˇcší?
Co
◦
Viliam Solˇcány, FIIT STU Bratislava
Závisí od organizácie pridel’ovania úsekov:
Operaˇcné systémy 2011/12
Predn. 7 – 22 / 45
Úseky pevnej d´lžky (2)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
Partition 4
Partition 4
Partition 3
Partition 3
Partition 2
Partition 2
Partition 1
Partition 1
OS
OS
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
Samostatné rady
procesov
stránkovaním
Spoloˇcný rad
procesov
• Pri samostatných radoch je proces zaradený tak, aby sa
minimalizovala vnútorná fragmentácia
• Pri spoloˇcnom rade je vyššie využitie procesora
◦ Ak sú v systéme výmeny, hl’adá sa vhodný úsek pri každom
opätovnom zavedení procesu
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 23 / 45
Úseky pevnej d´lžky (3)
• Systém s úsekmi pevnej d´lžky môže byt’ bez výmen procesov,
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
alebo s výmenami
• Relokácia a ochrana pamäti
◦ V systéme bez výmen staˇcí relokácia vykonaná zavádzaˇcom
◦
pri zavedení procesu
V systéme s výmenami tiež, ak sa proces dostane vždy do
toho istého úseku
•
Úseky rôznych d´lžok so samostatnými radmi
◦ Dynamická relokácia je pri výmenách nutná ak sa úsek hl’adá
vždy nanovo
•
•
Úseky rovnakých d´lžok
Úseky rôznych d´lžok so spoloˇcným radom
◦ Ochrana pamäti je potrebná v každom prípade
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 24 / 45
Úseky pevnej d´lžky (4)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
• Evidencia obsadenosti pamäti je jednoduchá – poˇcet úsekov je
konštantný
◦ Napr. pomocou bitovej mapy, každému úseku zodpovedá 1 bit
• Problémy
◦ Ak je proces príliš malý pre pridelený úsek – vel’ká vnútorná
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
◦
◦
fragmentácia
Ak je proces príliš vel’ký, nevojde sa celý do úseku – musí si
sám riadit’ zavádzanie po cˇ astiach (overlays)
Podobne ak proces vopred nevie celkovú vel’kost’, poˇcas
vykonávania sa zväˇcší (dynamicky alokuje pamät’) a prerastie
vel’kost’ úseku
• Príklad systému s úsekmi pevnej d´lžky
◦ IBM 360, operaˇcný systém OS/MFT (Multiprogramming with a
Fixed Number of Tasks)
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 25 / 45
Úseky variabilnej d´lžky (Dynamic Partitioning)
Úvod
• Každý proces dostane práve taký vel’ký úsek pamäti aký
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
potrebuje
• Motivácia
• Monoprogramovanie
• Monoprogramovanie
◦ Odstránit’ vnútornú fragmentáciu, zlepšit’ využitie pamäti –
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
umožnit’ umiestnenie viacerých procesov
ˇ
• Poˇcas behu systému procesy uvolnujú
obsadené úseky
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
(ukonˇcenie procesov, výmeny) a na dané miesto sú umiestnené
iné procesy
• Stránkovanie
• Segmentácia
• Segmentácia so
◦ Po cˇ ase sa v pamäti striedajú obsadené úseky s vol’nými
stránkovaním
◦
dierami
Diery sú príliš malé pre umiestnenie procesov
– Vonkajšia (externá) fragmentácia
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 26 / 45
Úseky variabilnej d´lžky (2)
Príklad
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
8M
OS
P1 in
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
56M
P2 in
8M
20M
36M
OS
P1
8M
20M
14M
OS
P1
P2
8M
20M
14M
OS
P1
P2
8M
20M
14M
OS
P1
8M
20M
8M
OS
P1
P4
8M
20M
8M
22M
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
P3 in
P2 out
P4 in
stránkovaním
P1 out
Viliam Solˇcány, FIIT STU Bratislava
P3
18M
6M
14M
OS
P2
4M
6M
8M
P4
Operaˇcné systémy 2011/12
18M
4M
P3
6M
P4
8M
4M
P3
OS
P2 in
18M
18M
4M
P3
6M
18M
4M
P3
Predn. 7 – 27 / 45
Úseky variabilnej d´lžky (3)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
• Eliminácia externej fragmentácie – kompakcia (kondenzácia)
pamäti
◦ Premiestnenie procesov súvisle za sebou
ˇ
◦ Casovo
nároˇcná operácia
versus
multiprogramovanie
• Úseky pevnej d´lžky
8M
14M
6M
8M
6M
OS
P2
8M
14M
8M
18M
OS
P2
P4
P3
P4
18M
4M
P3
(Fixed Partitioning)
• Úseky variabilnej
Compaction
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
16M
• Systém s úsekmi variabilnej d´lžky môže byt’ bez výmen
procesov, alebo s výmenami
• Relokácia a ochrana pamäti
◦ Aj v systéme bez výmen je potrebná dynamická relokácia
◦
– kompakcia môže proces premiestnit’ na inú adresu
Ochrana pamäti je potrebná v každom prípade
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 28 / 45
Úseky variabilnej d´lžky (4)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
• Evidencia obsadenosti pamäti – bitová mapa
◦ Pamät’ je rozdelená na alokaˇcné jednotky vel’kosti niekol’ko
◦
◦
◦
◦
◦
◦
bajtov, alebo slov, . . .
Každej alokaˇcnej jednotke zodpovedá jeden bit v bit. mape
Hodnota bitu 0 = vol’ná jednotka, 1 = obsadená
ˇ
Cím
väˇcšia alokaˇcná jednotka, tým menšia bitová mapa
Pamät’ová réžia je nízka
Spájanie susedných vol’ných úsekov nestojí niˇc
Hl’adanie vol’ného úseku je cˇ asovo nároˇcné – nájst
postupnost’ núl danej d´lžky, aj cez hranice slov
P1
P2
P3
stránkovaním
11111111 Bitmap
11100001
11111000
00111111
11111110
00
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 29 / 45
Úseky variabilnej d´lžky (5)
• Evidencia obsadenosti pamäti – zret’azený zoznam
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
◦ Prvok zoznamu zodpovedá jednému úseku (proces alebo
diera), obsahuje adresu zaˇciatku a d´lžku
• Monoprogramovanie
• Monoprogramovanie
P1
versus
multiprogramovanie
• Úseky pevnej d´lžky
P2
P
(Fixed Partitioning)
0 11
P3
H 11 4
P 15 6
P 26 13
H 39 3
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
H 21 5
ˇ
◦ Usporiadanie podl’a zaˇciatoˇcnej adresy umožnuje
jednoducho
spájat’ uvolnený úsek so susednými (pri obojsmer. zret’azení)
stránkovaním
Pred uvolnením X
A
X
A
X
X
B
Po uvolnení X
A
B
A
B
B
X
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 30 / 45
Úseky variabilnej d´lžky (6)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Obsadzovacie algoritmy
◦ Prvý vol’ný – First fit – prehl’adáva od zaˇciatku pamäti
◦ Nasledujúci vol’ný – Next fit – prehl’adáva od posledne
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
◦
◦
nájdeného úseku
S najmenším zvyškom – Best fit
S najväˇcším zvyškom – Worst fit
• “First fit” je najrýchlejší a obvykle aj najlepší (v zmysle externej
fragmentácie a teda potrebnej frekvencie kompakcií)
• Problém – cˇ o ked’ sa proces za behu zväˇcšuje (dynamická
alokácia pamäti, rast zásobníka)
• Príklady systémov s úsekmi pevnej d´lžky
◦ IBM OS/MVT (Multiprogramming with Variable Number of
◦
Tasks)
Minix3
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 31 / 45
Dvojice úsekov (Buddy system)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
• Kompromis medzi úsekmi pevnej a variabilnej d´lžky
◦ Pri pevných d´lžkach je obmedzený poˇcet procesov, ak je úsek
◦
príliš vel’ký, pamät’ je využitá neefektívne
Pri variabilných d´lžkach je znaˇcná réžia na kompakciu
• Buddy systém pridel’uje úseky, ktorých vel’kost’ je mocnina 2:
Procesu vel’kosti s pridelí úsek vel’kosti 2i , priˇcom
2i−1 < s ≤ 2i
• Ak úsek 2i nie je vol’ný, získa sa rekurzívnym delením väˇcšieho
na polovice:
2i+d = 2i+d−1 + 2i+d−2 + . . . + 2i+1 + 2i + 2i
stránkovaním
napr. 128 = 64 + 32 + 16 + 8 + 8
• Ak po uvolnení vzniknú vedl’a seba dva úseky 2i , spoja sa do
jedného 2i+1 (rekurzívne)
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 32 / 45
Dvojice úsekov (2)
1M
Req A(100K)
A
128K
Req B(240K)
A
128K
Req C(64K)
A
C
Req D(256K)
A
Rel B
Rel A
256K
512K
B
512K
64K
B
512K
C
64K
B
D
256K
A
C
64K
256K
D
256K
128K
C
64K
256K
D
256K
Req E(75K)
E
C
64K
256K
D
256K
Rel C
E
256K
D
256K
D
256K
128K
Rel E
Rel D
Viliam Solˇcány, FIIT STU Bratislava
512K
1M
Operaˇcné systémy 2011/12
Predn. 7 – 33 / 45
Dvojice úsekov (3)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
• Pre každú vel’kost’ je zoznam vol’ných úsekov
• Algoritmus hl’adania úseku 2i
void get_hole(int i) {
if(i == MAX_I + 1) error();
if(<i_list empty>) {
get_hole(i+1);
<split hole into buddies>;
<put buddies on i_list>;
}
<take first hole on i_list>;
}
ˇ
• Algoritmus uvolnovania
(a spájania) úsekov??
• Buddy systém je rozumný kompromis
• Modifikovaná verzia sa používa na alokovanie pamäti v jadre
tradiˇcného UNIXu
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 34 / 45
Stránkovanie
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Nech logická adresa má n bitov, t.j. logický adr. priestor je 2n
• Preklad adries – prepoˇcet nemusí byt’ len ’+’
Base reg
• Monoprogramovanie
• Monoprogramovanie
Relative address
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
Program
Addressing HW
111111
000000
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
Core
Image
Main memory
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
• Napr. majme pre procesy nie jeden, ale 2 bázové registre B0, B1
◦ Pre logické adresy s MSB = 0 sa použije B0, pre MSB = 1 B1
◦ Logická adresa sa potom mapuje do jedného z dvoch úsekov
stránkovaním
◦
◦
◦
fyzickej pamäti
Zvyšných n − 1 bitov urˇcuje posunutie v rámci úseku
Predpokladáme, že dané 2 úseky vo fyzickej pamäti sa
neprekrývajú
Celkovo môžeme adresovat’ stále rovnako vel’ký priestor:
2 × 2n−1 = 2n
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 35 / 45
Stránkovanie (2)
Úvod
• Alebo majme 4 bázové registre, z ktorých sa vyberá pomocou
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
2 najvyšších bitov logickej adresy. . .
• . . . 2k bázových registrov
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
◦ Na výber bázového registra sa používa k najvyšších bitov
◦
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
◦
◦
logickej adresy ⇒ cˇ ísla úsekov sú 0, 1, . . . , 2k − 1
Zvyšných n − k bitov urˇcuje posunutie v rámci úseku
⇒ vel’kost’ úseku je 2n−k (všetky sú rovnako vel’ké)
Prvá adresa v každom úseku má posunutie 0 ⇒ i–ty úsek
zaˇcína logickou adresou i × 2n−k (binárne i a n − k núl)
Posledná adresa v každom úseku má posunutie 2n−k − 1
⇒ i–ty úsek konˇcí logickou adresou
i × 2n−k + 2n−k − 1 = (i + 1) × 2n−k − 1
◦ T.j. úseky súvisle pokrývajú celý logický adresový priestor 2n
◦ Adresovací HW potrebuje pole bázových registrov, na jeho
indexovanie sa používa k najvyšších bitov logickej adresy
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 36 / 45
Stránkovanie (3)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Príklad: n = 11, k = 3
◦ Logický adr. priestor je
211 = 2048
◦ Poˇcet úsekov je 23 = 8
◦ Vel’kost’ úseku je
211−3 = 256
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
úsek logické adresy (dec | hex)
0
0 ... 255 | 0x000 ... 0x0FF
1
256 ... 511 | 0x100 ... 0x1FF
2
512 ... 767 | 0x200 ... 0x2FF
3
768 ... 1023 | 0x300 ... 0x3FF
4
1024 ... 1279 | 0x400 ... 0x4FF
5
1280 ... 1535 | 0x500 ... 0x5FF
6
1536 ... 1791 | 0x600 ... 0x6FF
7
1792 ... 2047 | 0x700 ... 0x7FF
• Terminológia
◦ Úseky logického adresového priestoru – stránky (page)
◦ Pole bázových registrov – tabul’ka stránok (page table)
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 37 / 45
Stránkovanie (4)
ˇ
• Umiestnovanie
procesov do pamäti
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
ˇ
◦ Stránky sa umiestnujú
na adresy zarovnané na vel’kost’
◦
◦
stránky – fyzická pamät’ “je rozdelená” na stránkové rámy
(page frames)
Stránkový rám je bud’ celý obsadený práve jednou stránkou,
alebo celý vol’ný
Stránkových rámov je konštantný poˇcet
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
• Preklad adries
Logical address
Page#
11111
00000
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
Offset
stránkovaním
Page table
Process
Viliam Solˇcány, FIIT STU Bratislava
Frame# Offset
Physical address
Addressing HW
Operaˇcné systémy 2011/12
Main memory
Predn. 7 – 38 / 45
Stránkovanie (5)
• Vlastnosti
Úvod
◦ Stránky nemusia byt’ umiestnené vo fyzickej pamäti súvisle
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
(v stránkových rámoch po sebe nasledujúcich)!
• Monoprogramovanie
• Monoprogramovanie
Main memory
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
Frame#
0
1
2
3
0
1
2
3
Frame#
Frame#
0
1
2
3
Process A
page table
7
8
9
10
Process B
page table
Page#
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
Frame#
• Úseky variabilnej
A.0
A.1
A.2
A.3
C.0
C.1
C.2
B.0
B.1
B.2
B.3
C.3
C.4
Page#
(Fixed Partitioning)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Page#
versus
multiprogramovanie
• Úseky pevnej d´lžky
0
1
2
3
4
4
5
6
11
12
Process C
page table
13
14
Free frames
Otázka: Nech logické adresy sú 16-bitové a stránka dlhá 1K. Aká
fyzická adresa zodpovedá logickej adrese 0x0E5C v procese B?
(0x2A5C)
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 39 / 45
Stránkovanie (6)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
• Vlastnosti (pokraˇc.)
◦ Vel’kost’ stránky je mocnina 2 ⇒ pri preklade nie je potrebné
◦
sˇcítanie, staˇcí zret’azenie – rýchlejšie
Proces nemusí využívat’ max. logický adresový priestor
• V poslednej stránke procesu môže byt’ cˇ ast’ pamäti
nevyužitá – interná fragmentácia
• Zväˇcšovanie procesu za behu nie je problém
◦ Relokácia – stránky môžu byt’ umiestnené do l’ubov. rámov
◦ Každý proces má svoju tabul’ku stránok ⇒ nemôže sa
svojvol’ne dostat’ do pamäti iného procesu (OS korektne
ˇ
umiestnuje
stránky do rámov)
• Pri prepínaní procesov musí OS pripravit’ tabul’ku stránok
nového procesu – réžia
◦ Zdiel’anie pamäti je možné – namapovat’ rám(y) do logického
priestoru viacerých procesov
• Staršie implementácie UNIXu využívali stránkovanie s výmenami
celých procesov
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 40 / 45
Segmentácia
Úvod
• Pamät’ so stránkovaním poskytuje programom jednorozmerné
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
pole logických adries (lineárne adresy)
• Pre programátora môže byt’ výhodné použitie viacerých
nezávislých adresových priestorov – segmenty
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
◦ Segment obsahuje logicky ucelený modul – segmenty vytvára
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
◦
◦
◦
stránkovaním
◦
◦
programátor
Segment môže rást’ nezávisle od iných segmentov
Segment môže byt’ kompilovaný nezávisle od iných
segmentov
Segment môže strážit’ svoje hranice (limit) nezávisle od iných
segmentov
Segment môže mat’ nastavený spôsob prístupu (r, x, rw)
nezávisle od iných segmentov – programátor vie cˇ o segment
obsahuje (na rozdiel od stránkovania)
Segment môže byt’ zdiel’aný viacerými procesmi
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 41 / 45
Segmentácia (2)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Príklady štruktúrovania programu na segmenty
◦ Procedúra (niekol’ko súvisiacich procedúr)
•
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
•
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
Separátny vývoj, kompilácia a zostavenie - segmenty s
“klientskými” procedúrami netreba kompilovat’ aj ked’ sa
vel’kost’ procedúry zmení
Segment s procedúrou môže byt’ zdiel’aný viacerými
procesmi – zdiel’ané knižnice (pri cˇ istom stránkovaní ide
tiež, ale komplikovanejšie – simulácia segmentov)
◦ Pole
•
Kontrola indexov
◦ Niekol’ko premenných
•
Používanie (aj zdiel’anie) s vhodným spôsobom prístupu
(read-only, read-write)
◦ Zásobník
•
Viliam Solˇcány, FIIT STU Bratislava
Môže rást’ nezávisle, limit pre preteˇcenie je ovel’a vyšší
Operaˇcné systémy 2011/12
Predn. 7 – 42 / 45
Segmentácia (3)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Logická adresa je dvojica (£íslo_segmentu, posunutie)
• Porovnanie vlastností stránkovania a segmentácie
• Monoprogramovanie
• Monoprogramovanie
Vlastnost’
versus
multiprogramovanie
• Úseky pevnej d´lžky
Potrebuje programátor vediet’,
Stránkovanie
Segmentácia
Nie
Áno
1
Vel’a
Nie
Áno
Nie
Áno
Nie
Áno
že sa daná technika používa
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
Kol’ko adresových priestorov
má proces k dispozícii
Dajú sa odlíšit’ dáta od kódu
a môžu mat’ iný typ prístupu
Dá sa l’ahko vysporiadat’ s dátami,
stránkovaním
ktoré znaˇcne menia vel’kost’
Je možné zdiel’anie procedúr
medzi procesmi
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 43 / 45
Segmentácia (4)
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Implementácia
◦ Pre preklad adries sa využíva tabul’ka segmentov – analógia
tabul’ky stránok – obsahuje fyzické adresy zaˇciatkov
segmentov
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
•
(Fixed Partitioning)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
•
Index do tabul’ky segmentov je cˇ íslo segmentu z logickej
adresy
Fyzická adresa je súˇctom bázovej adresy segmentu a
posunutia
◦ Tabul’ka segmentov obsahuje pre každý segment tiež limit a
stránkovaním
◦
prístupový mód – adresovací HW ich kontroluje pri každom
prístupe
Na rozdiel od stránok, segmenty nemajú konštantnú vel’kost’
⇒ implementácia cˇ istej segmentácie vedie na úseky
variabilnej d´lžky
•
Viliam Solˇcány, FIIT STU Bratislava
Problém externej fragmentácie, potreba kompakcie pamäti
Operaˇcné systémy 2011/12
Predn. 7 – 44 / 45
Segmentácia so stránkovaním
Úvod
Metódy pridel’ovania
pamäti
• Metódy pridel’ovania
pamäti – prehl’ad
• Monoprogramovanie
• Monoprogramovanie
versus
multiprogramovanie
• Úseky pevnej d´lžky
(Fixed Partitioning)
• Segmentácia prináša výhody pre programátora
• Implementácia cˇ istej segmentácie je jej slabé miesto
ˇ
• Spojenie so stránkovaním umožnuje
využit’ výhody oboch
prístupov
◦ Segment je cˇ lenený na stránky, každý segment má vlastnú
tabul’ku stránok (segment je 1-rozmerný adresový priestor)
◦ Logická adresa má tvar
(£íslo_segmentu, lineárna_adresa_v_segmente)
• Úseky variabilnej
d´lžky (Dynamic
Partitioning)
• Dvojice úsekov
(Buddy system)
• Stránkovanie
• Segmentácia
• Segmentácia so
stránkovaním
◦ Položka tabul’ky segmentov obsahuje adresu tabul’ky stránok
◦
pre daný segment
Princíp prekladu adresy:
• Pre dané £íslo_segmentu (1. cˇ ast’ log. adresy) sa v
tabul’ke segmentov zistí adresa tabul’ky stránok
• Indexom do tabul’ky stránok sú vyššie bity 2. cˇ asti log.
adresy (lineárna_adresa_v_segmente)
• Na danom indexe sa zistí cˇ íslo stránkového rámu, ktoré sa
zret’azí s nižšími bitmi 2. cˇ asti log. adresy, cˇ ím sa získa
fyzická adresa
Viliam Solˇcány, FIIT STU Bratislava
Operaˇcné systémy 2011/12
Predn. 7 – 45 / 45
Download

Správa pamäti, 1. ˇcast`