Osnovni koncepti
n
Maksimalno iskorišćenje CPU-a se dobija multiprogramming-om
n
CPU–I/O Burst Cycle – Izvršenje procesa se sastoji od
cycle
CPU
izvršavanja i I/O čekanja
n
CPU burst distribucija
CPU raspoređivač
n
Selektuje procese u memoriji koji su spremni za izvršenje i dodeljuje
jednog od njih CPU
n
Odluke CPU raspoređivanja mogu da se donose kada se proces:
1.
prebacuje iz running u waiting stanje
2.
prebacuje iz running u ready stanje
3.
prebacuje iz waiting u ready stanje
4.
završava
n
Raspoređivanje pod 1 i 4 je
nonpreemptive
n
Sva ostala raspoređivanja su
preemptive
Dispečer
n
Dispatcher modul daje kontrolu nad CPU-om procesu selektovanom
kratkoročnim raspoređivačem; ovo uključuje:
l
promenu konteksta - switching context
l
prebacivanje u korisnički mod
l
skok na odgovarajuću lokaciju u korisničkom programu da bi
se restartovao taj program
n
Dispatch latency
– vreme potrebno dispečeru da stopira jedan proces
i startuje drugi koji je u running stanju
Kriterijumi za raspoređivanje
n
Iskorišćenje CPU-a – održava CPU zauzetim što je moguće duže
n
Propusnost – broj procesa koji kompletiraju svoje izvršenje u jedinici
vremena
n
Turnaround time – vreme okreta - količina vremena da se izvrši
poseban proces
n
Waiting time – vreme čekanja - količina vremena kada proces čeka u
spremnom redu
n
Response time – vreme odziva - količina vremena koja je potrebna
od trenutka kada je zahtev podnešen do prvog odziva, to
nije
izlaz
(za okruženje sa vremenskom raspodelom)
n
Max
CPU utilization
n
Max
throughput
n
Min
turnaround time
n
Min
waiting time
n
Min
response time
Shortest-Job-First (SJF) raspoređivanje
(najkraći-posao-prvo)
n
Dužina sledećeg CPU burst-a je pridružena svim procesima. Koriste
se ove dužine za raspored procesa sa najkraćim vremenom
n
Dve šeme:
l
nonpreemptive – jednom CPU dat procesu ne može da bude
preempted-prekinut dok ne kompletira njegov CPU burst
l
preemptive – ako stiže novi proces sa dužinom sledećeg CPU
burst-a manjom od preostalog vremena procesa koji se tekuće
izvršava, preempt. Ova šema je poznata kao Shortest-
Remaining-Time-First (SRTF)
n
SJF je optimalno raspoređivanje ako je kriterijum srednje vreme
čekanja – daje minimalno srednje vreme čekanja za dati skup
procesa
Raspoređivanje po prioritetu
n
Prioritet (ceo broj) je pridružen svakom procesu
n
CPU se dodeljuje procesu sa najvećim prioritetom (najmanji ceo broj
º
najveći prioritet)
l
Preemptive
l
Nonpreemptive
n
SJF je raspoređivanje po prioritetu gde je prioritet predikciono
vreme sledećeg CPU burst-a
n
Problem
º
Starvation ("gladovanje") – procesi sa malim prioritetom
mogu da ne budu izvršeni nikada
n
Rešenje
º
Aging ("starenje") – kako vreme prolazi povećava se
prioritet procesa
Round Robin (RR) - "Kružno" raspoređivanje
n
Svaki proces dobija malu količinu CPU vremena (
vremenski
kvantum
), obično 10-100 milisekundi. Nakon ovog vremena, proces
se prekida (preempt) i dodaje na kraj spremnog reda.
n
Ako postoji
n
procesa u spremnom redu i ako je vremenski kvantum
q
, onda svaki proces dobija 1/
n
od CPU vremena u porciji-veličini od
najviše
q
vremenskih jedinica odjednom. Nijedan proces ne čeka više
od (
n
-1)
q
vremenskih jedinica.
n
Performanse
l
q
veliko
Þ
FIFO
l
q
malo
Þ
q
mora biti veće zbog promene konteksta, inače su
opšti troškovi (overhead) suviše veliki
Ovaj materijal je namenjen za učenje i pripremu, ne za predaju.
