OPERATIVNI SISTEMI
II KOLOKVIJUM (odgovori na pitanja iz IV,V,VI i VII oblasti)
IV Upravljanje deljenim resursima
28. Objasniti model pristupa deljenim resursima-čitaoci i pisci
Koncept monitora obezbeđuje isključenje pristupa konkurentnih procesa do deljenog resursa, uz
eventualnu uslovnu sinhornizaciju. Međutim, koncept potpunog međusobnog isključenja kod monitora
ponekad predstavlja suviše restriktivnu politiku koja smanjuje konkurentnost programa. Često se
operecije nad deljenim resursom mogu svrstati u operacije koje:
Samo čitaju deljene podatke, odnosno ne menjaju stanje resursa (operacije čitanja)
Upisuju u odeljene podatke, tj menjaju stanje resursa (opracije upisa)
Koncept monitora ne dozvoljava nikakvu konkurentnost ovih operacija. Konkurentnost se može povećati
ako se dozvoli da:
Proizvoljno mnogo procesa izvršava operacije čitanja (čitaoci, readers)
Najviše jedan proces izvršava operaciju upisa (pisac, writer),međusobno isključivo sa drugim piscima,ali i
sa čitaocima.
Na taj način, deljenom resursu u datom trenutku može pristupati ili samoj edan pisac, ili jedan ili više
čitalaca,ali ne istovremeno i jedni i drugi-više čitalaca-jedan pisac.
Postoje različite varijante ove šeme koje se razlikuju u pogledu prioriteta koji se daje procesima koji
čekaju na pristup resursu:
Prioritet imaju pisci koji čekaju, tj čim postoji pisac koji čeka, svi novi čitaoci biće blokirani sve dok svi
pisci ne završe.
Prioritet imaju čitaoci, tj piscu se ne dozvoljava pristup sve dok svi čitaoci ne završe, a novi čitaoci se
puštaju pre pisaca.
29. Objasniti model filozofa koji večeraju
Pet filozofa sedi za okruglim stolom na kome se nalaziposuda sa špagetama, jedu i razmišljaju. Svaki
filozof ima svoj tanjir, a izmedju svaka dva susedna tanjira stoji po jedna viljuška. Pretpostavlja se da su
svakom filozofu, da bi se poslužio, potrebne dve viljuške, kao i da može da koristi samo one koje se
nalaze levo i desno od njegovog tanjira. Ako je jedna od njih zauzeta, on mora da čeka. Svaki filozof
ciklično jede, pa razmišlja. Kada završi sa jelom, filozof spušta obe viljške na sto i nastavlja da razmišlja.
Posle nekog vremena vremena, filozof ogldani i ponovo pokušava da jede. Potrebno je definisati
protokol (pravila ponašaanja, algoritam) koji će obezbediti ovakvo ponašanje filozofa i pristup do
viljušaka.
30. Koje uslove mora da zadovolji konkurentni program da bi bio korektan?
Da bi konkurentni program bio korektan, mora da zadovolji sledeće uslove:
Logičku korektnost rezultata bez obzira na redosled preplitanja izvršavanja delova konkurentnog
programa.
Život ili napredak:sve što je programom predviđeno da se desi, treba da se desi u konačnom vremenu;
procesi morju da naoreduju , ne smeju večno da čekaju.
31. Objasniti utrkivanje kao jedan od problema nadmetanja za deljene resurse.
Primer (nekorektne) uslovne sinhonizacije:
Suspend: bezuslovno suspenduje pozivajući process
Resume: bezuslovno deblokira imenovani process, ako je blokiran
Ovakav neispravan uslov naziva se utrkivanje (race condition). Nastaje zbog preplitanja delova koji bi
morali biti izvršeni neprekidivo. Tipično nastaje kao posledica toga što se odluka o promeni stanja
procesa (suspenziji) donosi na osnovu ispitivanja vrednosti deljene promenljive, pri čemu ta dva koraka
nisu nedeljiva, pa može doći do preuzimanja, tj “utrkivanja” od strane drugog procesa koji pristupa istoj
deljenoj promenljivoj.
32. Objasniti mrtvo blokiranje kao jedan od problema nadmetanja za deljene
resurse.
Scenario: svaki filozof uzme svoju levu viljušku i čeka na desnu?!
Ovakav neregularan uslov nastaje tako što se grupa procesa koji konkurišu za deljene resurse
međusobno kružno blokiraju ‐
mrtvo
(ili
kružno
)
blokiranje
(
deadlock
).
U opštem slučaju, mrtvo blokiranje nastaje tako što se grupa procesa nadmeće za ograničene
resurse, pri čemu proces
P1
drži ekskluzivan pristup do resursa
R1
i pri tom čeka blokiran da se
oslobodi resurs
R2
, proces
P2
drži ekskluzivan pristup do resursa
R2
i pri tom čeka blokiran da
se oslobodi resurs
R3
, itd., proces
Pn
drži ekskluzivan pristup do resursa
Rn
i pri tom čeka
blokiran da se oslobodi resurs
R1
. Tako procesi ostaju neograničeno suspendovani u cikličnom
lancu blokiranja.
Jedan od najtežih problema koji mogu da nastanu u konkurentnim programima,
multiprogramskim sistemima i samim operativnim sistemima.
33.
Objasniti živo blokiranje kao jedan od problema nadmetanja za deljene
resurse.
Scenario: svi filozofi uzmu svoju levu viljušku, ne mogu da uzmu desnu, pa spuste levu, i tako
ciklično!?
Ovakva neregularna situacija u konkurentnom programu, kod koje se grupa procesa izvršava, ali
nijedan ne može da napreduje jer u petlji čeka na neki uslov, naziva se
živo blokiranje
(
livelock
).
Treba razlikovati živo od mrtvog blokiranja. Iako se u oba slučaja procesi nalaze "zaglavljeni"
čekajući na ispunjenje nekog uslova, kod mrtvog blokiranja su oni suspendovani, dok se kod
V Raspoređivanje procesa
37.
Kada i kako proces (može da iz)gubi procesor (promena konteksta)?
•
Kada i kako proces (može da iz)gubi procesor (promena
konteksta):
•
sinhrono:
*
blokira se na sinhronizacionoj primitivi (eksplicitno):
-
čeka na međuprocesnu sinhronizaciju
-
čeka na I/O operaciju
-
čeka na istek zadatog vremena
*
završava se (eksplicitno)
*
izvršava neblokirajući sistemski poziv, ali OS dobija priliku da izvrši promenu
konteksta (implicitno)
•
asinhrono (na prekid):
*
pojavljuje se novi spreman proces (zadovoljen uslov sinhronizacije, završena I/O
operacija, isteklo vreme čekanja).
*
isteklo vreme dodeljeno procesu (
time slice
)
38.
Navesti kriterijume za poređenje algoritama raspoređivanja procesa.
Izbor algoritma raspoređivanja zavisi od prirode procesa. Svaki algoritam ima svoje
karakteristike i pogodniji je za neke vrste procesa.
Kriterijumi poređenja algoritama:
•
Iskorišćenje procesora (
CPU utilization
)
•
Propusnost: broj završenih procesa u jedinici vremena
•
Ukupno vreme provedeno u sistemu (
turnaround time
): vreme koje protekne
od kreiranja do gašenja procesa
•
Vreme čekanja (
waiting time
): vreme koje proces provede u redu spremnih
procesa
•
Vreme odziva (
response time
) u interaktivnom sistemu: vreme koje protekne
od korisničkog zahteva do odziva na taj zahtev
39.Navesti načine optimizacije parametara pri izboru algoritma raspoređivanja.
Načini optimizacije:
•
optimizovati srednje vrednosti navedenih parametara
•
optimizovati maksimalne/minimalne vrednosti ovih parametara
•
minimizovati varijansu vrednosti: kod interaktivnih sistema, važnija je
predvidivost
odziva nego srednja vrednost njegovog odziva.
40.
Objasniti algoritam raspoređivanja –
First-Come, First Served
(FCFS).
First‐Come, First Served
(FCFS): prvi došao, prvi opslužen; process koji je prvi tražio CPU, prvi će
ga i dobiti.
Najjednostavniji algoritam; jednostavna implementacija pomoću FIFO reda: iz reda spremnih
uzima se prvi proces, a novi se stavlja na kraj.
Zaključak: vreme čekanja (a time i vreme odziva) kod FCFS nije uvek minimalno i može jako da
varira ako su vremena izvršavanja procesa značajno različita.
Konvoj efekat
: grupa I/O‐bound procesa čeka da jedan CPU‐bound proces završi svoje dugo
izvršavanje i stalno tako u krug “ide za njim kao konvoj” iz reda spremnih u red čekanja
na I/O – slabije iskorišćenje CPU i uređaja nego da procesi sa kraćim izvršavanjem idu prvi
FCSF je podrazumevano
nonpreemptive
(bez prekidanja) I zato nepogodan za sisteme sa
raspodelom vremena. Algoritam dozvoljava procesu koji trenutno koristi processor da ga koristi
sve dok mu je potreban.
Prednosti: jednostavan algoritam
Nedostaci: neodgovarajuci za interaktivne sisteme, moguće su velike varijacije u srednjem
potrebnom vremenu izvršavanja programa.
41.
Objasniti algoritam raspoređivanja -
Shortest-Job-First
(SJF).
Shortest
‐
Job
‐
First
(SJF): najkraći posao prvi; Planer iz reda čekanja bira posao koji zahteva
najmanje procesorskog vremena.
Svakom procesu pridružuje se vrednost dužine sledećeg izvršavanja (
CPU burst
); CPU se
dodeljuje onom procesu koji ima najmanju ovu vrednost u redu spremnih.
Dokazivo je da je SJF
optimalan
u smislu da za dati skup procesa daje minimalno srednje vreme
čekanja.
Osnovni problem SJF algoritma: kako znati vrednost dužine narednog izvršavanja (
CPU burst
)?
Kod paketne obrade, ova procena se ostavlja korisniku kao procena ograničenja vremena
izvršavanja
Kod kratkoročnog raspoređivanja, ovo se ne može
znati
unapred, može se samo
predvideti
(npr.
na osnovu predistorije).
Zbog ovog problema, iako je optimalan, SJF se upotrebljava samo kod dugoročnog
raspoređivanja. Kod kratkoročnog (CPU) raspoređivanja, nije primenjiv egzaktno, već samo kao
aproksimacija (na osnovu predviđenog vremena).
SJF može biti i sa i bez preuzimanja.
Preemptive SJF
uzima u obzir procenu
preostalog
vremena
izvršavanja procesa koji je prekinut.
Nedostatak: u opštem slučaju ne može biti implementiran. Takođe, moguće je “gladovanje”
(“starvation”).
Implementacija nije jednostavna, jer nisu unapred poznata vremena izvršavanja svih procesa.
Ovaj algoritam se samo u kombinaciji sa drugim algoritmima koristi u operativnim
sistemima.
42. Objasniti algoritam raspoređivanja –
Priority Scheduling
(Priority Sch).
