Operativni sistemi – CPU raspoređvanje

Osnovni koncepti

• Maksimalno iskorišćenje CPU-a se dobija multiprogramming-om
• CPU–I/O Burst Cycle – Izvršenje procesa se sastoji od cycle CPU izvršavanja i I/O čekanja
• CPU burst distribucija

CPU raspoređivač

• Selektuje procese u memoriji koji su spremni za izvršenje i dodeljuje jednog od njih CPU
• 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

• Raspoređivanje pod 1 i 4 je nonpreemptive
• Sva ostala raspoređivanja su preemptive

Dispečer
Dispatcher modul daje kontrolu nad CPU-om procesu selektovanom kratkoročnim raspoređivačem; ovo uključuje:

• promenu konteksta – switching context
• prebacivanje u korisnički mod
• skok na odgovarajuću lokaciju u korisničkom programu da bi se restartovao taj program

Dispatch latency – vreme potrebno dispečeru da stopira jedan proces i startuje drugi koji je u running stanju

Kriterijumi za raspoređivanje

• Iskorišćenje CPU-a – održava CPU zauzetim što je moguće duže
• Propusnost – broj procesa koji kompletiraju svoje izvršenje u jedinici vremena
• Turnaround time – vreme okreta – količina vremena da se izvrši poseban proces
• Waiting time – vreme čekanja – količina vremena kada proces čeka u spremnom redu
• 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)
• Max CPU utilization
• Max throughput
• Min turnaround time
• Min waiting time
• Min response time

Shortest-Job-First (SJF) raspoređivanje (najkraći-posao-prvo)

• Dužina sledećeg CPU burst-a je pridružena svim procesima. Koriste se ove dužine za raspored procesa sa najkraćim vremenom
• Dve šeme:
  • nonpreemptive – jednom CPU dat procesu ne može da bude preempted-prekinut dok ne kompletira njegov CPU burst
  • 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)
• SJF je optimalno raspoređivanje ako je kriterijum srednje vreme čekanja – daje minimalno srednje vreme čekanja za dati skup procesa
• Raspoređivanje po prioritetu
• Prioritet (ceo broj) je pridružen svakom procesu
• CPU se dodeljuje procesu sa najvećim prioritetom (najmanji ceo broj º najveći prioritet)

Preemptive

Nonpreemptive

• SJF je raspoređivanje po prioritetu gde je prioritet predikciono vreme sledećeg CPU burst-a
• Problem º Starvation (“gladovanje”) – procesi sa malim prioritetom mogu da ne budu izvršeni nikada
• Rešenje º Aging (“starenje”) – kako vreme prolazi povećava se prioritet procesa

Round Robin (RR) – “Kružno” raspoređivanje

• 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.
• 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.
• Performanse

q veliko Þ FIFO
q malo Þ q mora biti veće zbog promene konteksta, inače su opšti troškovi (overhead) suviše veliki