Upravljanje memorijom - Operativni sistemi

Report
Operativni sistemi
Upravljanje memorijom
Upravljanje memorijom
•
U jednoprogramskom sistemu, glavna memorija se deli na dva
dela: jedan deo za operativni sistem (kernel), a drugi za
korisnički program koji se trenutno izvršava (primer: RAF_OS).
•
U multiprogramskom sistemu, korisnički deo memorije mora da
se dalje podeli, da bi prihvatio više procesa koji će uskoro biti u
stanju spremnosti na izvršenje.
•
Zadatak te dalje podele dinamički izvršava operativni sistem, a
to je poznato kao upravljanje memorijom.
•
Unutar procesa, dinamičko dodeljivanje memorije najčešće se
vrši upotrebom bibliotečkih funkcija (npr. malloc/free iz C
biblioteke stdlib) koje mogu da budu implementirane na razne
načine.
Memorijska adresa
• Logička
– Referenca na memorijsku lokaciju nezavisno od toga gde se
podaci zaista nalaze u memoriji.
– Logička adresa mora da bude prevedena u fizičku adresu
najkasnije u trenutku pristupa podacima.
• Relativna
– Adresa izražena kao relativna u odnosu na neku poznatu tačku
(npr. na početak programa).
• Fizička
– Apsolutna adresa stvarne lokacije u operativnoj memoriji.
Zaštita
• Proces ne sme da pristupi memorijskoj lokaciji nekog drugog
procesa bez posebne dozvole.
• Nemogućnost provere apsolutnih adresa u vreme kompajliranja.
• Ove adrese moraju da budu proverene u vreme izvršenja.
• Zahteve za zaštitu memorije mora da ispuni hardver, jer
operativni sitem ne može da predvidi sve memorijske reference
koje je program u stanju da napravi.
Deljenje memorije
• Više procesa može istovremeno da pristupi istom delu
memorije.
• Bolje je dozvoliti svakom procesu pristup istoj kopiji programa
nego imati zasebne kopije za svaki proces.
Logička organizacija
• Programi se pišu kao moduli.
• Moduli mogu da se pišu i kompajliraju nezavisno.
• Modulima se daju različiti stepeni zašite (read-only,
execute-only).
• Procesi mogu međusobno da dele module.
Fizička organizacija
• Količina memorije koja je na raspolaganju programu i njegovom
podacima može da bude nedovoljna.
• Preklapanje (overlay) omogućuje različitim modulima da koriste
iste memorijske regione.
• Preklapanje mora da obezbedi programer, ali on ne zna koliko
će memorije imati na raspolaganju.
Dodeljivanje kontinualne memorije
• Deljenje na fiksne particije.
• Deljenje na particije promenljive veličine (dinamičko
deljenje na particije).
Deljenje na fiksne particije
• Deljenje na particije iste veličine.
• Svaki proces koji je po veličini isti ili je manji od veličine
particije, može da se učita u bilo koju particiju.
• Ukoliko su sve particije zauzete, operativni sistem može da
prebaci neki proces na disk (swap-out).
• Program može da bude veći od veličine particije. U tom slučaju
mora da se koristi preklapanje.
• Upotreba operativne memorije je neefikasna. Svaki program,
bez obzira koliko mali bio, zauzima čitavu particiju. Ostatak
memorije u toj particiji je neiskorišćen. To je interna
fragmentacija.
Primer fiksnih particija
Algoritam za smeštanje
• Particije iste veličine
– Nije bitno koja se particija koristi za smeštanje procesa.
• Particije različite veličine
– Smeštanje u najmanju particiju u koju proces može da stane.
– Svaka particija ima red čekanja.
– Memorija se dodeljuje tako da se minimizuje neiskorišćen prostor
unutar particije.
Dodeljivanje memorije fiksnim particijama
Dinamičko deljenje na particije
• Particije su različite veličine koja je poznata tek tokom
učitavanja procesa.
• Procesu se dodeljuje tačno onoliko memorije koliko mu je
potrebno.
• Ukoliko se proces prebaci na disk a na njegovo mesto učita
novi, manji proces, nastaje rupa u memoriji. Ovo se naziva
eksterna fragmentacija.
• S vremena na vreme, mora da se vrši sažimanje (compaction)
zauzetih particija. Tako se pravi kompaktan blok zauzete
memorije. Sve rupe se pojavljuju na kraju memorije kao
slobodan prostor.
Efekat dinamičkog deljenja
Efekat dinamičkog deljenja ...
Algoritmi za izbor prazne particije
• Bit-mapa
• Ulančana lista
– First-fit
– Next-fit
– Best-fit
– Worst-fit
• Partnerski sistem (Buddy System)
– Binarni sistem (proučićemo samo ovaj, ostali su slični)
– Fibonacci-jev sistem
– Težinski sistem
Bit-mapa
B
A
8
C
16
a)
a)
b)
D
E
24
Deo memorije sa 5 procesa (A – E) i tri rupe.
Crtice označavaju jednice memorije za dodelu.
Osenčene oblasti (0 u bit-mapi) su slobodne.
Odgovarajuća bit-mapa.
b)
• Svaki blok u memoriji predstavljen je jednim bitom u bit-mapi, pri
čemu 0 znači slobodan, a 1 znači zauzet.
• Glavni problem nastaje kada je potrebno učitati k jedinica u
memoriju jer je potrebno izvršiti pretraživanje i naći k uzastopnih 0.
Ovo je spora operacija i zato se bit-mapa retko koristi.
Ulančana lista
8
16
24
a)
Slobodno Početna Dužina
adresa
Dodeljeno
A = dodeljena memorija
b)
a)
b)
F = slobodna memorija
Deo memorije
Odgovarajuća ulančana lista
Ulančana lista: First-fit
• Pretražuje se memorija od početka i bira se prvi blok i koji
može da stane željeni proces (rupa).
• Najbrži algoritam.
• Na početku memorije se obično već nalazi određeni broj
procesa, koji, sve jedno, moraju da se pretražuju da bi se
našao prvi odgovarajući slobodan blok.
Ulančana lista: Next-fit
• Pretražuje se memorija počev od poslednje upotrebljene
lokacije.
• Često dodeljuje blok na kraju memorije, gde se inače nalazi
najveći slobodni blok.
• Njaveći slobodan blok podeljen je na manje blokove.
• Podrebno je sažimanje da bi se ponovo dobio veliki blok na
kraju memorije.
Ulančana lista: Best-fit
• Operativni sistem bira blok koji je po veličini najbliži onom
koji se zahteva
• Algoritam sa najlošijim performansama
• Dobra strana: mala fragmentacija
• Loša strana: često sažimanje memorije
Ulančana lista: Worst-fit
• Radi slično kao i Best-fit.
• Razlika je u tome što Best-fit traži najmanju rupu, dok
Worst-fit bira najveću raspoloživu rupu.
• Ova strategija i nakon upotrebe ostavlja za sobom veliku
rupu koja može da se iskoristi prilikom sledećeg
dodeljivanja. Best-fit obično ostavlja malu rupu, što dovodi
do fragmentacije i potrebe za sažimanjem.
Partnerski sistem (Buddy System)
• I fiksno i dinamičko deljenje na particije ima svoje
nedostatke.
• Fiksno deljenje ograničava broj aktivnih procesa i može
neefikasno da koristi prostor ako je slaba podudarnost
između veličina raspoloživih particija i procesa.
• Dinamičko deljenje na particije je složenije za održavanje
i obuhvata dodatno opterećenje zbog sažimanja.
Partnerski sistem (Buddy System)
• Kompromis: Binarni partnerski sistem (Binary Buddy System).
– Ceo memorisjki prostor se tretira kao jedinstven blok veličine 2U.
– Ako je zahtev za delom memorije takav da je 2U-1 < zahtev <= 2U,
dodeljuje se ceo blok.
– U suprotnom, blok se deli na dva identična – partnerska dela
(buddies).
– Algoritam se nastavlja sve dok se ne generiše najmanji blok koji je
veći ili jednak zahtevu.
Videti primer: http://os.raf.rs/Primeri/buddy.c
Primer partnerskog sistema
Binarni partnerski sistem
nivo 0
nivo 1
...
Dodeljivanje diskontinualne memorije
• Operativna memorija koja se dodeljuje procesu ne mora da se
sastoji od kontinualnog niza fizičkih adresa!
• Segmentacija
• Straničenje
• Potrebna nam je podrška hardvera (procesora).
Straničenje
• Linearni adresni prostor i adresni prostor fizički prisutne memorije
delimo na zamišljene delove iste veličine.
• U linearnom prostoru ove delove nazivano stranice (pages), a u
fizičkom adresnom prostoru nazivamo ih okviri (frames).
• Bilo koja stranica može da se smesti u bilo koji okvir fizičke
memorije, jer su iste veličine.
• Sada je potrebno samo uspostaviti vezu između stranica i okvira u
koje se te stranice smeštaju (tabela stranica – okvir).
• Ova veza se prilikom adresiranja koristi za translaciju linearne
adrese u adresu fizički prisutne memorije.
• Translaciju obavlja hardver – jednica za upravljanje memorijom
(Memory Management Unit – MMU).
Napomena: Često se u svakodnevnom govoru za okvir fizičke memorije koristi termin stranica.
Straničenje
Procesor
CPU
3621A0A0
3621A0A4
c
MMU
Primer:
12FC00AC
Bazna adresa
tabele stranica
Translacija na osnovu
tabele stranica
793400A4
793400A0
c
Stranica
Okvir
4D
00
793400A0
00
793400A1
02
793400A2
23
793400A3
03
793400A4
C1
793400A5
A3
793400A6
...
793400A7
...
...
...
3621Axxx
79340xxx
...
12FC00AA
...
...
...
12FC00AB
...
...
20 bitova za pronalaženje stranice
read write
12 bitova za adresiranje unutar
address
data
stranice. Ukupno 32 adresnih bitova.
xxx su kontrolni indikatori (flags).
12FC00AC
Tabela
stranica
12FC00AD
12FC00AE
12FC00AF
c
Veličina stranice
• Glavna motivacija za upotrebu manjih stranica je ušteda u memoriji
izbegavanjem interne fragmentacije (prosečna interna fragmentacija
iznosi 1,5 veličina stranice). Ovo se može zanemariti kod računara
sa stotinama megabajta memorije i veličinom stranice od 4 KB.
• Veličina tabele stranica je obrnuto proporcionalna veličini stranice.
• Zbog efikasnijeg pretraživanja tabela, stranično adresiranje vrši se
hijerarhijski, u dva nivoa, upotrebom direktorijuma tabela stranica i
samih tabela stranica.
• Cena za ovo je dvostruki pristup memoriji radi izračunavanja adrese,
ali i to se rešava adekvatnim keširanjem.
• Dobra stvar je da direktorijum staje u jednu stranicu. Isto važi i za
svaku od tabela stranica, što znatno pojednostavljuje manipulaciju.
Aliasing
Aliasing na nivou
stranice 4KB
D
Aliasing na nivou
tabele stranica senčenje 4MB
(Shadowing)
C
B
Stranični
direktorijum
A
Linearni prostor
Tabele stranica
Fizički prostor
Stranične greške
• Iako se na osnovu imena dolazi do drugačijeg zaključa, ovo nisu
greške već izuzeci doji doprinose normalnom funkcionisanju sistema.
• Postoje dva tipa straničnih grešaka: Page Fault i Protection Fault
– Minor Page Fault. Stranica je učitana u memoriju, ali odgovarajući bit u
njenom deskriptoru još uvek nije postavljen na vrednost 1. Ovo može da
se dogodi kod deljene memorije, kada je neki drugi proces učitao
stranicu.
– Major Page Fault *. Stranica nije učitana u memoriju. Ovo je osnovni
mehanizam za implementaciju virtuelne memorije.
– Invalid Page Fault. Referenciranje upotrebom NULL pointera. Operativni
sistem preslikava delove fizičke memorije za hvatanje ove grešeke. Npr.
Windows koristi deo memorije od 64KB na početku adresnog prostora
isključivo za “hvatanje” NULL pointera.
• Protection Fault nastaje kada proces pokuša pristup stanici koja nije
translirana u njegov adresni prostor, ili pokuša upis u stranicu koja je
Read-Only, ili pristupa stranici koja ima viši nivo privilegije.
* Windows (npr. Vista, u Reliability and Performance Monitor) to zove Hard Fault
Copy on Write
• Protection Fault nije greška ukoliko se koristi kao mehanizam za
implementaciju Copy on Write (COW), memorijske tehnike koju
koristi većina današnjih operativnih sistema.
Stranice
označene kao
Read-Only
Stranica 1
Originalni podaci
Stranica 2
Originalni podaci
Stranica 3
Proces 1
Fizička memorija
Proces 2
Copy on Write
• Proces 1 i Proces 2 koriste aliasing sve dok, npr. Proces 2 ne pokuša
upis u Stranicu 2. Tada se gereniše Protection Fault. Rutina za obradu
ovog izuzetka modifikuje odgovarajuću tabelu stranica (nema više
aliasinga), a zatim se ponovo izvršava instrukcija koja je to izazvala.
Stranica 1
Originalni podaci
Stranica 2
Modifikovani podaci
Stranica 3
Kopija stranice 2
Proces 1
Fizička memorija
Proces 2
Copy on Write
• Unix i Linux sistemi na ovaj način implemetiraju fork ( ).
• Windows nema fork (sem kada se koristi Posix/Interix podsistem),
ali i on koristi Copy on Write kao mehanizam uštede fizičke
memorije i smanjivanja broja nepotrebnih kopiranja.
• Kod operativnog sistema Windows, broj straničnih grešaka u
sekundi koje se koriste za Copy on Write može se naći u (WMI)
Performance Monitor → Performance Counter→ Memory →Write
Copies/sec.
Anuliranje stranica
• Anuliranje memorije: Upisivanje nula u memorijske lokacije.
• Podaci u fizičkoj memoriji koju je koristio neki proces moraju da se
anuliraju pre dodeljivanja te memorije drugom procesu.
• malloc ( ) vraća pointer na anuliranu memoriju.
• Razlog je bezbednost (privatnost) procesa. Podaci nekog procesa ne
bi smeli da budu dostupni drugom procesu, sem ako se to ne radi
namerno, radi međuprocesne komunikacije.
• Anuliranje može da se radi na zahtev ili da to radi neki pozadinski
proces.
• Stranica se dodeli procesu ali se označi kao nevažeća
• Prilikom pokušaja čitanja, nastaje greška stranice. Rutina za obradu
greške upisuje nule u sve lokacije stranice.
Straničenje na zahtev
• Precizniji naziv za staničenje na zahtev (Demand Paging) mogao bi
da bude “zamena stranice usled (stranične) greške”.
• Pokušaj adresiranja stranice koja nije prisutna generiše grešku.
• Ovaj izuzetak mora da poseduje svoju stavku u IDT.
• Rutina za obradu, na osnovu kôdne oznake greške koju uzima sa
steka, određuje zbog čega je nastala greška. Pretpostavimo da je u
pitanju Major Page Fault.
• Rutina za obradu greške proverava da li je linearna adresa ispravna
(da li je translacija dozvoljena i da li je moguća translacija u fizičku
adresu). Ako nije, procesu se šalje signal ili poruka, nakon čega se
on zaustavlja (“ubija”) i o tome se ispisuje poruka*.
*
Može da bude i Unix Kernel Panic ili Windows BSOD
Straničenje na zahtev
• Ako je adresa ispravna, rutina proverava da li ima slobodnih okvira u
fizičkoj memoriji. Ako nema, primenjuje neki od algoritama zamene*.
• Ukoliko izabrani okvir sadrži prljavu stranicu, on se označava kao
zauzet (In Transition), kako ga neki drugi proces u međuvremenu ne
bi koristio. Ako je stranica čista, njen okvir odmah može da se koristi.
• Sledi blokirajući sistemski poziv rutine za upis sadržaja okvira na disk.
• U deskriptor stranice koja je izazvala izuzetak kopira se adresa
izabranog okvira, u stari deskriptor P=0 (nije prisutna), a u ostatak
starog deskriptora lokacija stare stranice na disku.
* Izlazi iz okvira ovog kursa
Straničenje na zahtev
• Tekući proces se stavlja u blokirano stanje čekanja na završetak
disk operacije. U međuvremenu se izvršava neki drugi proces.
• Po završetku disk operacije upisivanja stranice, blokirani proces se
aktivira, a u deskriptor se upisuje da je stranica čista. Okvir sada
može da se koristi za učitavanje nove stranice.
• Tražena stranica se pronalazi na disku.
• Ponovo se koristi blokirajući sistemski poziv za učitavanje sa diska,
tokom koga proces ponovo blokira, a neki drugi se izvršava.
• Kada se završi učitavanje stranice, ažurira se odgovarajuća tabela
stranica, a okvir se označava kao Normal.
• Programski brojač na steku ponovo se postavlja na instrukciju koja
je napravila Major Page Fault.
• Proces se prebacuje u stanje spreman.
• Nastavalja se izvršavanje rutine za obradu stranične greške, koja se
na svom izlazu vraća procesu kao da se greška nije ni dogodila.
Virtuelna memorija
Ne koristi se
?
Data segment
Ne koristi se
Data segment
Podaci
malloc
Direktno
preslikavanje
Kodni segment
Kôd
Linearni prostor
Fizički prostor
Virtuelna memorija
Pronaći stranicu koja ima fizički
okvir, ali npr. nije dugo korišćena
P=0 (nije prisutna)
0
Data segment
Sadržaj
se snima
na disk
Kodni segment
Linearni prostor
Tabela stranica
Fizički prostor
Virtuelna memorija
Kopira se adresa okvira iz deskriptora
pronađene stranice, a na njeno meto se
upisuje adresa stare stranice na disku.
1
Data segment
Kodni segment
Linearni prostor
0
Tabela stranica
Fizički prostor
Virtuelna memorija
Šta se događa kada je ponovo
potreban prethodni sadržaj okvira?
1
Data segment
Učitava
se sa
diska
Kodni segment
Linearni prostor
0
Tabela stranica
Fizički prostor
Virtuelna memorija
Kopira se adresa okvira iz deskriptora
stranice koja više nije potrebna
0
Data segment
Kodni segment
Linearni prostor
1
Tabela stranica
Fizički prostor
Virtuelna memorija
• Korišćenjem disk prostora na ovaj način, svakom procesu se može
dodeliti onoliko memorije koliko mu je potrebno, bez obzira na
stvarnu veličinu fizičke memorije.
• Zato se to zove virtuelna memorija.
• Svaki proces “misli” da raspolaže sa kompletnim linearnim adresnim
prostorom.
• U virtuelnoj memoriji može se nalaziti veliki broj ovakvih procesa.
• Pitanje: Pod pretpostavkom da procesor adresira virtuelnu i fizičku
memoriju preko adresne magistrale iste širine, da li virtuelna adresa
može da bude veća od veličine linearnog adresnog prostora?
• Pitanje: Da li veličina procesa može da bude veća od celokupne
fizičke memorije?

similar documents