Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmi planiranja - Coggle Diagram
Algoritmi planiranja
FCFS algoritam
First Come. First Served
- jednostavnost i pravednost
- zasnovan na ideji da se procesor dodeljuje procesima po redu kako su ga zatrazili, tj. prijavili za njegovo koriscenje
implemetira se koriscenjem FIFO strukture
- kada se proces pokrene i prijavi za koriscenje procesora, on se postavlja na kraj reda
- kada se procesor oslobodi prvi sledeci proces se izbacuje iz reda i dobija pravo koriscenja procesora
nema verziju koja dozvoljava prekidanje procesa jer bi to bilo u suprotnosti sa glavnim principom na kom je zasnovan
prednost:
- laka implementacija
Mane:
- vreme cekanja je veliko
- moze dovesti do "efekta konvoja" situacije kod koje dosta procesa ceka da se izvrsi jedan vremenski zahtevan proces
procesima koji se dugo izvrsavaju odgovara ovaj algoritam za razliku od procesa koji ne zahtevaju puno vremena, a prinudjeni su da cekaju da se pre njih izvrse neki koji se duze izvrsavaju
primena:
sistemi ili situacije koje ne dozvoljavaju prekidanje procesa vec podrzaumevaju da se procesima koji su dobili priliku da se izvrsavaju na procesoru omoguci da zavrse zapoceti posao bez obzira na situaciju u sistemu
-
SPF algoritam
Shortest Process First
- zasnovan na ideji da se favorizuju procesi ciji je (sledeci) zahtev za procesorom (procesorskim vremenom) manji
- svakom procesu se pridruzuje ocekivano vreme za njegovo sledece izvrsavanje na procesoru
- procesor se dodeljuje redom procesima koji zahtevaju manje vremena
- ukoliko se dogodi da dva procesa imaju isto ocekivano vreme obicno se primenjuje FCFS algoritam za odluku koji proces ce dobiti prednost
verzija koja dozvoljava prekidanje procesa
- kada se pojavi novi proces cija je sledeca operacija manje zahtevna od one koja se trenutno izvrsava -> vrsi se prebacivanje konteksta procesa koji se izvrsava, a novom procesu se dozvoljava da na procesoru izvrsava operaciju
Prednost:
- optimalan kada se posmatra srednje vreme cekanja za bilo koji skup poslova
Mane:
- odredjivanje duzine sledeceg zahteva za procesorom, odnosno procena duzine trajanja sledece aktivnosti procesa na procesoru (do U/I operacije ili zavrsetka procesa)
dugorocno planiranje
- unapred zadata granica vremena potrebnog da se posao zavrsi
- efikasnost sistema zavisi od mogucnosti da se realno proceni trajanje posla
kratkorocno planiranje
- nema pouzdanog nacina da se precizno odredi trajanje sledece aktivnosti procesa na procesoru
- aproksimacija vremena - eksponencijalna sredina prethodnih aktivnosti i prethodnih procena potrebnog vremena
- pretpostavka da ce sledeca aktivnost biti slicne duzine kao prethodne i procenjene za taj proces
-
Kruzni algoritam
- zasnovna na ideji za opsluzivanje racunara slicno kao kada je deljenje vremena (Time-sharing) u pitanju
- svaki proces dobija procesor na unapred zadati vremenski interval koji se naziva kvantum vremena
- kada to vreme istekne ili ako se proces zavrsi do kraja, proces se prekida a procesor na kvantum vremena dobija sledeci proces iz reda spremnih procesa
- prekinuti proces (ukoliko se nije izvrsio do kraja) se stavlja na kraj reda spremnih procesa
- ako ima n spremnih procesa, a vremenski kvantum je duzine q onda svaki proces dobija najmanje 1/n procesorskog vremena, najvise po q u jednom prolazu
- nijedan proces se ne ceka vise od (n-1)q vremena
performanse zavise od kvantuma vremena:
- ako je veci od svih mogucih zahteva za procesorom (tezi beskonacnosti) ovaj algoritam se ponasa kao FCFS
- ako je veoma mali, kruzni algoritam se naziva deljenje procesora i teoretski izgleda da svaki od n procesa ima sopstveni procesor koji je n puta sporiji od procesora koji se nalazi u sistemu
- na kraju svakog kvantuma vrsi se prebacivanje konteksta procesa - iz ugla izvrsavanj procesa totalno nekoristan posao
- zavisi od brzine memorije, broja registara i postojanja specijalnih instrukcija
- pozeljno je da se kvantum izabere tako da bude znatno duzi od vremena potrebnog za prebacivanje konteksta
- vreme obrade zavisi od kvantuma jer je ono krace ako vecina poslova svoju aktivnost na procesoru zavrsava za jedan kvantum vremena
- izbor kvantuma je vrlo delikatan posao jer je bolje imati duzi kvantum vremena, ali ako je preveliki onda algoritam vise lici na FCFS
Redovi u vise nivoa
- pristup zasnovan na ideji da se red spremnih procesa podeli u vise redova sa razlicitim prioritetima
- procesi koji pristizu svrstavaju se u odgovarajuci red na osnovu nekog kriterijuma
- svaki red moze imati sopstveni algoritam planiranja, a izmedju redova postoji jasno definisana razlika u prioritetu
- proces koji je prvi u svom redu moze dobiti procesor iskljucivo ako su redovi viseg prioriteta prazni
Najjednostavniji primer pretpostavlja da postoje 2 reda:
- interaktivni red - kruzni algoritam
- paketni - FCFS algoritam
-
Uvod
neki od algoritama imaju i verzije koje dozvoljavaju i prekidanje procesa
prebacivanje konteksta procesa koji se izvrsava i ucitavanje drugog procesa, na osnovu odluke planera, pre nego sto je prvi proces iskoristio procesor onoliko koliko mu je bilo potrebno da:
- obavi posao
- dodje do U/I operacija ili
- da se zavrsi do kraja
-> veca fleksibilnost pri upravljanju procesima