Raspoređivanje (Scheduling)

 

Bez obzira o kojem se tipu sustava radi, scheduler treba imati sljedeće ciljeve: pravednost (treba dati svakom procesu jednako pravo na procesorsko vrijeme), provođenje politike (dani pravila oko principa raspoređivanja moraju biti poštovana) te balansiranost (ravnomjerna zauzetost svih dijelova sustava).

Ako se radi o sustavu u kojem se zadaci obavljaju serijski tada algoritam raspoređivanja treba još imati sljedeće ciljeve: protok (throughput – maksimiziranje broja poslova po satu), vrijeme zadržavanja (turnaround time – minimiziranje vremena proteklog od zaprimanja posla i njegovog završetka) te utrošak procesorskog vremena (poželjno da je da procesor uvijek bude opterećen) dok u interaktivnim sustavima algoritam raspoređivanja mora imati za cilj poboljšanje vremena odziva.

 

Algoritmi raspoređivanja

 

First-Come First-Serve (FCFS)

Najednostavnije algoritam. Kada proces dodje na sustav stavklja se na kraj reda. Procesi se uzimaju s početka reda. Ako neki proces ostane blokiran (npr.čeka I/O) stavlja ga se na kraj reda.

 

Shotest Job First (SJF)

Kada nekoliko proces čeka u listi procesa ovaj algoritam će odabrati onog koji najkraće traje. Npr. neka imamo 4 procesa sa vremenima a, b, c i d. Prvi završi nakon a vremena, drugi nakon a+b itd. Ukupno vrijeme je (4a + 3b + 2c + d) / 4. Očito je da a treba biti što manji.

Ovaj slučaj ne mora vrijediti ako procesi nisu istovremeno dostupni. (npr. procesi koji traju 2,4,1,1,1 a dolaze u vremenima 0,0,3,3,3 SJF bi tada imao ABCDE i prosječno vrijeme čekanja 4.6 , a npr. BCDEA 4.4)

 

 

Shortest Remaining Time Next

Modifikacija SJF algoritma na način da kada novi proces dođe na sustav njegovo vrijeme izvršavanja se uspoređuje sa vremenom potrebnom trenutnom procesu da završi. U slučaju da je to vrijeme manje, trenutni proces se prekida i novi proces se započinje izvršavati.

 

Round-Robin (RR)

Jedan od najstarijih,najjednostavnijih, najpravednijih i najčešće korištenih. Svakom procesu se dodjeljuje vremenski interval, tzv. quantum, unutar kojeg se ima pravo izvršavati. Ako ne završi u tom intervalu biva preknut, procesor se dodjeljuje nekom drugom procesu . Također ako proces postane blokiran prije isteka kvantuma također se procesor dodjeljuje nekom drugom procesu. Kada proces iskoristi svoj kvantum biva stavljen na kraj liste. Postavlja se pitanje koliko treba biti duljina kvantuma. Ako je duljina kvantuma premala previše se procesorskog vremena gubi na promjenu procesa (i promjenu konteksta) (overhead), a ako je preveliki onda je odziv u interaktivnim sustavima spor. (Tannenbaum 20-50 ms)

 

Priority Scheduling (PS)

Svakom procesu dodijeljen je prioritet i iz liste se odabire onaj najveceg prioriteta. Razne varijacije: Kako bi izbjegli da proces visokog prioriteta se stalno izvršava može mu se smanjivati prioritet u u svakom određenom vremenskom intervalu. Također može se svakom procesu dodijeliti broj kvantuma koji će se moći izvršavati.

Prioriteti se mogu dodijeljivati dinamički i statički. Dinamički se to može izvesti da se se svakom procesu vezano za I/O dodijeli prioritet 1/f gdje je f udio posljednjeg kavntuma kojeg je koristio.

ili npr. aging (nova težina = aT0 + (1-a)T1  (T0 prethodno trajanja, T1 procjena novog trajanja))

 

 

Multiple Queues (MQ)

Varijacija gornje algoritma. CTSS (Compatibile Time Sharing System) (1962.) na računalu 3.generacije 7094 je imao problem jer je promjena procesa bila vrlo spora, pa su dizajneri uvidjeli da je bolje cpu-vezanim procesima bolje dati veći kvantum odjednom nego nekoliko malih. Kao primjer promotrimo sljedeći slučaj: Neka je nekom procesu potrebno 100 kvanta vremena. Inicijalno će dobiti 1 kvant, pa će biti promijenjen. Kada sljedeći put postane aktivan dobit će 2 kvanta, zatim 4, 8, ... 32, 64 (iako ćemu zadnji put trebati samo 37). Na ovaj način bilo je potrebno samo 7 promjena umjesto 100 sa čistim round robinom. Istovremeno taj proces će padati na listi prioriteta tako da će rjeđe dobivati priliku, omogućujući kratkim procesima rad.

npr. Multilevel Feedback Queueing.

 

Raspoređivanje u real-time sustavima

Ako se događaj i (i=1..m) pojavljuje sa periodom Pi i zahtjeva Ci vremena za obradu onda za taj real-time sustav mora vrijediti .

Npr:

Sustav u realnom vremenu sadrži 4 periodička događaja sa periodima 50,100,200 i 250 msec. Pretpostavimo da ta 4 događaja zahtjevaju 35,20,10 i x msec procesorskog vremena za obradu. Kolika je najveća vrijednost od x da je sustav rasporediv (schedulable)?

 

 

 

Zadaci:

1. Mjerenja u nekom sustavu su pokazala da se prosječni proces izvršava T vremena prije nego što završi ili postane blokiran na nekoj od I/O operacija. Promjena procesa traje vrijeme S, što je efektivno gubitak vremena (overhead). Za round-robin način raspoređivanja sa kvantumom Q nađite formulu iskoristivosti procesora za sljedeće slučajeve:

            a) Q  = ∞

            b) Q > T

            c) S < Q < T

            d) Q = S

            e) Q približno jednako 0

 

2. Pet poslova A, ... , E dolaze u red za izvršavanje u istom trenutku. Procjene njihovim izvršavanja su 10,6,2,4 i 8 minuta. Njihovi (izvana određeni) prioriteti su 3,5,2,1 i 4, gdje 5 označava najveći prioritet. Za svaki od sljedećih algoritama, pronađite prosječno vrijeme obrade. Vrijeme promjene procesa (overhead) je zanemarivo

            a) round-robin

            b) priority scheduling

            c) first-come first serve

            d) shortest job first

Rj:

RR1: 15.1,       RR2: 14..4,      PS: 14.0,         FCFS: 13.2,    SJB: 8.0

 

3. Pet poslova A, ... , E dolaze u red za izvršavanje u istom trenutku. Procjene njihovim izvršavanja su 10,1,3,2 i 5 kvantuma. Njihovi (izvana određeni) prioriteti su 3,5,1,4 i 2, gdje 1 označava najveći prioritet. Za svaki od sljedećih algoritama, pronađite prosječno vrijeme obrade. Vrijeme promjene procesa (overhead) je zanemarivo

            a) round-robin  (sa q=1 i q=2)

            b) priority scheduling

            c) first-come first serve

            d) shortest job first

Rj:

RR1: 7.4,         RR2: 7.8,         PS: 9.8,           FCFS: 10.2,    SJB: 4.2

 

4. Proces koji se izvršava u sustavu sa CTSS algoritmom raspoređivanja treba 30 kvantuma da bi završio. Koliko puta mora biti zamijenjen, uključujući i prvi put (kada se još nije počeo izvršavati)?

Rj: 30 = (11110)2 < (11111)2  tj. 1+2+4+8+16 tj. treba biti 5 puta zamijenjen prije nego šro završi

 

5. Na sustav dolazi 6 procesa u različitim vremenskim trenutcima i različitog trajanja. Vremena dolaska i trajanja (u nekim vremenskim intervalima) su po procesima (1,7) , (3,2), (7,9) , (12, 4) , (16,8), (20,2). Utvrdite redoslijed izvršavanja kod algoritama round robin (sa kvantom od 3 vremenske jedinice) i Multilevel Feedback Queueing sa 2 nivoa prioriteta (Unutar svakog od nivoa je round robin princip. U višem svaki proces dobiva 2 kvanta, u nižem 4 kvanta.)

 

 

6. Koristeći donju tablicu, za dane nizove procese nacrtajte gantogram za algoritme First Come First Served (FCFS), Round Robin (RR) sa kvantom 1, Shortest Job First (SJF) Zatim izračunajte  vremena zadržavanja, vremena završetaka, vremena čekanja te prosječna vremena čekanja. Pretpostavimo da se odluke o raspoređivanju donose točno na početku kvanta i da svaki proces dolazi točno prije početka kvanta. (npr. u trenutku 0 A je dostupan za raspoređivanje, a u trenutku 2 dostupni su i A i B.

 

Process

Vrijeme dolaska

CPU vrijeme

A

0

3

B

2

6

C

3

10

D

7

1

E

8

5

 

Vrijeme

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

Dolasci

A

B    C

 

 

D    E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

FCFS

A

A

A

B

B

B

B

B

B

C

C

C

C

C

C

C

C

C

C

D

E

E

E

E

E

RR

A

A

B

A

C

B

C

B

D

C

E

B

C

E

B

C

E

B

C

E

C

E

C

C

C

SRTN

A

A

A

B

B

B

B

D

B

B

E

E

E

E

E

C

C

C

C

C

C

C

C

C

C

SJF

A

A

A

B

B

B

B

B

B

D

E

E

E

E

E

C

C

C

C

C

C

C

C

C

C

 

 

SJF

Vrijeme dolaska

Trajanje

Vrijeme završetka

Vrijeme zadržavanja

Vrijeme čekanja

Prosječno vrijeme čekanja

Prosječno vrijeme zadržavanja

A

0

3

3

3

0

3.4

8.4

B

2

6

9

7

1

C

3

10

25

22

12

D

7

1

10

3

2

E

8

5

15

7

2

 

SRTN

Vrijeme dolaska

Trajanje

Vrijeme završetka

Vrijeme zadržavanja

Vrijeme čekanja

Prosječno vrijeme čekanja

Prosječno vrijeme zadržavanja

A

0

3

3

3

0

3.2

8.2

B

2

6

10

8

2

C

3

10

25

22

12

D

7

1

8

1

0

E

8

5

15

7

2

 

 

RR

Vrijeme dolaska

Trajanje

Vrijeme završetka

Vrijeme zadržavanja

Vrijeme čekanja

Prosječno vrijeme čekanja

Prosječno vrijeme zadržavanja

A

0

3

4

4

1

6.6

11.6

B

2

6

18

16

10

C

3

10

25

22

12

D

7

1

9

2

1

E

8

5

22

14

9

 

FCFS

Vrijeme dolaska

Trajanje

Vrijeme završetka

Vrijeme zadržavanja

Vrijeme čekanja

Prosječno vrijeme čekanja

Prosječno vrijeme zadržavanja

A

0

3

3

3

0

6.2

11.2

B

2

6

9

7

1

C

3

10

19

16

6

D

7

1

20

13

12

E

8

5

25

17

12

 

7. Zamislimo neka je u tablici raspored radnog dana nekog studenta:

Oznaka radnje

Opis radnje

Vrijeme kad se ideja pojavila

Vremensko trajanje

 

P1

Kava

6:00

0:15

P2

Doručak

6:00

1

P3

Učenje

7:00

5

P4

Odmor (drijemanje)

10:00

1

P5

Ručak

12:00

0:15

P6

Posjet prijatelju

12:00

4

P7

Rješavanje ispita

14:00

4

P8

Vrijeme za čaj

17:00

0:15

 

Pronađite efikasnu metodu raspoređivanja gornjih poslova.

 

a) Round robin sa kvantom od 1h: U tom slučaju radni dan izgleda ovako:

 

Vrijeme

Zadatak

Vrijeme čekanja

Vrijeme zadržavanja u sustavu

6:00 – 6:15

P1 – kava

0

0.15

6:15 – 7:15

P2 – doručak

0:15

1:15

7:15 – 10:15

P3 - Učenje

0:15

 

10:15 – 11:15

P4 - Drijemanje

0:15

1:15

11:15 – 12:15

P3 - Učenje

1

 

12:15 – 12:30

P5 - Ručak

0:15

0:30

12:30 – 13:30

P6-Posjet prijatelju

0:30

 

13:30 – 14:30

Učenje

1:15

7:30

14:30 – 15:30

P7–Rješavanje zadataka

0:30

 

15:30 – 16:30

P6-Posjet prijatelju

2

 

16:30 – 17:30

P7 – Rješavanje ispita

1

 

17:30 – 17:45

P8 – Vrijeme za čaj

0:30

0:45

17:45 – 18:45

P6-Posjet prijatelju

1:15

 

18:45 – 19:45

P7–Rješavanje ispita

1:15

 

19:45 - 20:45

P6-Posjet prijatelju

1

8:45

20:45 – 21:45

P7–Rješavanje ispita

1

7:45

 

Prosječno vrijeme čekanja = (12h i15min) / 8 = priblizno = 1h 32 minute

 

b) SJF

Vrijeme

Zadatak

Vrijeme čekanja

Vrijem zadržavanja

6:00-6:15

P1 - Kava

 

0:15

6:15 – 7:15

P2 - Doručak

0:15

1:15

7:15 – 12:15

P3 – Učenje

0:15

5:15

12:15 – 12:30

P5 – Ručak

0:15

0:30

12:30 – 13:30

P4 - Drijemanje

2:30

3:30

13:30 – 17:30

P6- Posjet prijatelju

1:30

5:30

17:30 – 17:45

P8 – Vrijeme za čaj

0:30

0:30

17:45 – 21:45

P7– Rješavanje ispita

3:45

7:45

Prosječno vrijeme čekanja 9 / 8 = cca 1h 7 min

 

 

c) Preemptive SJF  (SRTN)

Vrijeme

Zadatak

Vrijeme čekanja

Vrijem zadržavanja

6:00-6:15

P1 - Kava

 

0:15

6:15 – 7:15

P2 - Doručak

0:15

1:15

7:15 – 10:00

P3 – Učenje

0:15

 

10:00 – 11:00

P4 - Drijemanje

 

1

11:00 – 12:00

P3 - Učenje

1

 

12:00 – 12:15

P5 - Ručak

 

0:15

12:15 – 13:30

P3 - Učenje

0:15

6:30

13:30 – 17:00

P6- Posjet prijatelju

1:30

 

17:00 – 17:15

P8 – Vrijeme za čaj

 

0:15

17:15 – 17:45

P6 – Posjet prijatelju

0:15

5:45

17:45 – 21:45

P7 – Rješavanje ispita

3:45

7:45

Prosječno vrijeme čekanja (7h 15 min) / 8 = cca 54 min

 

 

8.  Sustav za upravljanje procesorom ima sljedeće zadatke (zadane su parovi vrijeme dolaska, vrijeme trajanja): (1,7)  , (4,x2) , (6,10), (7,x4), (12,5).

Utvrdite raspon vrijednosti za x2 i x4 tako da se algoritmom SRTN drugi proces izvrši pretposljednji, a četvrti proces posljednji.

Za tako dobivene vrijednosti x2 i x3, provedite postupke RR sa q=2 i Multilevel Feedback Queueing (Foreground-Background)  (q(foreground)=2, q(background)=4)