Scheduling algoritmi

Definicija problema scheduling-a:
Općenito za definiciju pojma scheduling-a potrebno je specificirati sljedeće skupove:

• Skup od n procesa J={J1,J2,J3,...,Jn}
• Skup od m procesora P={P1,P2,P3,...,Pm}
• Skup od s tipova resursa R={R1,R2,R3,...,Rs}

Nadalje, precedence ograničenja među procesima mogu biti specificirana pomoću usmjerenog acikličkog grafa i vremenska ograničenja mogu biti specificirana za svaki proces. U danom kontekstu "Scheduling" znači dodjelu procesora iz skupa P i resursa iz skupa R procesima iz skupa J, i to na takav način da se ostvari završetak svih procesa uz zadovoljenje svih zadanih ograničenja. U svojem općem obliku ovaj problem je neriješiv.

---

Scheduling algoritmi se mogu podijeliti u nekoliko klasa:

1. Preemptive algoritmi

   Proces koji se trenutno izvodi može biti prekinut te se procesor dodjeli nekom drugom procesu, a to se može dogoditi u bilo kojem trenutku i to prema odluci danog scheduling algoritma.

2. Non-preemptive algoritmi

   Kad je proces jednom pokrenut na procesoru, on se izvršava do svoje kompletizacije.

3. Statički algoritmi

   Odluke o schedulingu su bazirane na fiksnim parametrima, koji su pridjeljeni procesima prije njihove aktivacije.

4. Dinamički algoritmi

   Odluke o schedulingu su bazirane na dinamičkim parametrima koji se mogu mijenjati tijekom rada sistema.

5. Off-line algoritmi

   Ova klasa scheduling algoritama se izvršava na cijelom skupu procesa prije njihove stvarne aktivacije. Redosljed procesa dobiven ovim algoritmom je spremljen u tabeli i kasnije se izvršava od strane dispačera.

6. On-line algoritmi

   Odluke dobivene ovim algoritmima se koriste za vrijeme izvršenja skupa procesa i odluke se donose svaki put kad novi process uđe u sustav.

7. Optimalni algoritmi

   Algoritam je optimalan ako minimizira danu funkciju troška za dani skup procesa.

8. Heuristički algoritmi

   Algoritam je heuristički ako on teži prema, ali ne garantira pronalazak optimalnog redoslijeda procesa.

---

U hard real-time sustavima zahtjeva se potpuno predvidljivo ponašanje, te se ostvarivost danog skupa procesa mora znati unaprijed. Na ovaj način ako se neki proces ne može izvršiti u zadovoljavajućim granicama, sistem još uvijek može poduzeti alternativne mjere u pokušaju da izbjegne katastrofične posljedice. U statičkim sistemima scheduling algoritam se izvodi i testira off-line. U dinamičkim sistemima algoritam se izvodi on-line. U oba slučaja algoritam mora dati garanciju održivosti sustava u svim situacijama u kojima se on može naći. Takvi algoritmi nazivaju se "guarantee-based" algoritmi.

U nekim real-time aplikacijama neki procesi imaju soft constraints-e. Ukoliko se takva ograničenja ne ispune sustav se neće raspasti ali će mu se degradirati performanse. Tipičan primjer ovakovih aplikacija su multimedijske aplikacije. U takvim real-time aplikacijama koriste se "best-effort" scheduling algoritmi. Oni ne garantiraju izvršenje skupa procesa pod zadanim ograničenjima, ali daju sve od sebe.

U pojedinim aplikacijama koriste se takozvani "imprecise computation" algoritmi. Ukoliko neki proces za svoje zadovoljavajuće izvršenje zahtijevaju određeni minimalni postotak svoga proračuna, onda će se upravo taj dio po ovom algoritmu sigurno i ostvariti, a ostatak proračuna će se obaviti ukoliko to bude moguće.

Performanse scheduling algoritama se određuju pomoću funkcije troška( cost function ) definirane na danom skupu procesa. Primjer je "utility" funkcija koja opisuje vrijednost pridodijeljenu nekom procesu kao funkciju vremena izvršenja tog procesa. Oblik takvih funkcija za soft, hard i firm procese prikazan je na slijedećoj slici.

---