Esercizio 1

Esercizio

Supponiamo di ricevere 5 job (A,B,C,D,E) tali che:

job Tempo stimato Tempo di arrivo

A 26 0

B 60 1

C 5 2

D 8 3

E 10 4

Descrivere la sequenza di esecuzione dei job in CPU (ad es. tramite Gantt chart) e calcolare l'istante

in cui ogni job completa il suo task e il relativo tempo totale di completamento ottenuto con:

scheduling FIFO
scheduling round-robin con quanto di tempo 5
scheduling a code multiple di priorita' con quanto di tempo 5,
considerando le seguenti priorità: A: 3, B: 4, C: 1, D: 2, E: 2 (4 più alta)
e supponendo che lo scheduler controlli le code e possa prelazionare la CPU ogni secondo

Si ignori il tempo impiegato nel context-switching.

Soluzione.

1. Viene prima eseguito A, quindi B, ecc.

A partire dall’istante 0, l'istante di completamento con scheduling FIFO è:

Job A: 26 (quindi tempo totale compl. = 26)

Job B: 86 (tc=85)

Job C: 91 (tc=89)

Job D: 99 (tc=96)

Job E: 109 (tc=105)

2. A viene eseguito per 5 unità, B x 5, C x 5, D x 5, E x 5, quindi nuovamente A x 5, B x 5, D x 3 (completato), E x 5 (completato),

A x 5, B x 5, A x 5, B x 5, A x 5, B x 5, A x 1, B x le restanti 35 unità.

Quindi a partire dall’istante 0, l'istante di completamento con scheduling Round Robin è:

Job A: 74 (tc=...)

Job B: 109

Job C: 15

Job D: 38

Job E: 43

3. Usiamo Gantt chart

Tempo	0-1 (1unita)	1-61 (12quanti)	61-86 (5quanti)	86-91 (1quanto)	91-96 (1quanto)	96-99 (3unita)	99-104 (1quanto)	104-109 (1quanto)
Job in CPU	A	B	A	D	E	D	E	C

Quindi istante di completamento (a partire dal tempo zero):

Job A: 86

Job B: 61

Job C: 109

Job D: 99

Job E: 104

Esercizio

Supponiamo di ricevere 5 job (A,B,C,D,E) tali che:
job Tempo stimato Tempo di arrivo Priorita
A 8 0 2

                B                             6                           1                    3
                C                             3                           2                    2
                D                            4                           3                    2
                E                             3                           4                    2

Descrivere la sequenza di esecuzione dei job in CPU (ad es. tramite Gantt chart) e calcolare l'istante

in cui ogni job completa il suo task e il relativo tempo totale di completamento ottenuto con:

Scheduling a code multiple di priorita' e feedback dove ogni coda e' gestita con la strategia FCFS.
Il feedback è definito come segue: la priorità diminuisce di 1 (fino al livello base 1) se si passano più di 6 unità di tempo (consecutive)

in CPU ed aumenta di 1 per ogni 6 unità di tempo passate in attesa in una qualsiasi coda.

Soluzione

Lo scheduler controlla le code (prelaziona la CPu se necessario) ogni unita' di tempo
Utilizzamo un Gantt chart:

Tempo (*)		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
Stato dei Job	A	2							3						2						3				3
	B		3
	C			2						3					3		3					4		4
	D				2						3						4
	E					2						3						4			4

Istante di completamento:

A 24
B 7
C 23
D 19
E 22

Nota:
La preemption avviene al tempo 13: C sostituisce A; e al tempo 15: D sostituisce C;
Al tempo 19: la coda di priorita 4 ha E in testa e C in coda (C entra nella coda dopo E)

Legenda:

(*) N indica l'intervallo [N,N+1] (ogni casella = 1 unita di tempo)

	Non presente
N	Esecuzione in CPU (con priorita N)
N	Attesa nella coda a priorita N
	Completato

Esercizio 2
Cinque processi, P₁, P₂, P₃, P₄ e P₅ richiedono contemporaneamente di poter utilizzare la CPU.
La lunghezza dei CPU-burst e le priorità sono dati nella seguente tabella (supponiamo che numeri bassi
corrispondano a priorità alte e viceversa):

	P₁	P₂	P₃	P₄	P₅
CPU burst	10	6	2	4	8
Priorità	3	5	2	1	4

Disegnare il diagramma di Gantt e calcolare il tempo di completamento di ogni processo per ciascuna
delle seguenti politiche di scheduling della CPU:

FIFO (supponendo che i processi siano stati inseriti in coda in ordine crescente di indice)
Shortest Job First
Priorità
Round Robin (con quanto di tempo q = 2 e trascurando il tempo di context switch)

Soluzione:

FIFO
Gantt chart:
P1 (0-10), P2 (10-16), P3 (16-18), P4 (18-22), P5 (22-30)

Tempi di completamento:
P1: 10,
P2: 16,
P3: 18,
P4:22,
P5: 30
SJF
Gantt chart:
P3 (0-2), P4 (2-6), P2 (6-12), P5 (12-20), P1 (20-30)

Tempi di completamento:
P1: 30,
P2: 12,
P3: 2,
P4:6,
P5: 20
Priorità
Gantt chart:
P4 (0-4), P3 (4-6), P1 (6-16), P5 (16-24), P2 (24-30)

Tempi di completamento:
P1: 16,
P2: 30,
P3: 6,
P4:4,
P5: 20
Round Robin
Gantt chart:
P1 (0-2), P2 (2-4), P3 (4-6), P4 (6-8), P5 (8-10),P1 (10-12), P2 (12-14), P4 (14-16),
P5 (16-18),P1 (18-20), P2 (20-22), P5 (22-24),P1(24-26),P5(26-28),P1(28-30)

Tempi di completamento:
P1: 30,
P2: 22,
P3: 6,
P4:16,
P5: 28

Esercizio 2 (A)

Considerate i seguenti Job:

Job	Burst time	Tempo di arrivo	Prima risposta
A	7	0	4.5
B	5	1	3.5
C	4	3	2.5
D	1	5	0.5

E2.1
Supponete di utilizzare una politica Shortest Job First senza preemption.

Assumete che lo scheduler venga attivato quando un job entra nella coda di attesa e quando un job completa l'esecuzione in CPU.

Descrivere la sequenza di esecuzione dei job in CPU e calcolare il tempo di completamento e di risposta di ogni Job.

Soluzione

Lo scheduler non applica preemption e quindi non interrompe mai i processi in esecuzione.

0-1	1-2	2-3	3-4	4-5	5-6	6-7	7-8	8-9	9-10	10-11	11-12	12-13	13-14	14-15	15-16	16-17
A	A	A	A	A	A	A	D	C	C	C	C	B	B	B	B	B

Tempi di completamento
A:        7
B: 17-1= 16
C: 12-3= 9
D: 8-5 = 3

Tempo di risposta

A:          4.5
B: 15.5-1= 14.5
C: 10.5-3= 7.5
D: 7.5-5 = 2.5

E2.2
Considerate ora la seguente politica di scheduling.

Lo scheduler di lungo termine immette job nella coda di attesa nell'ordine di arrivo
(supponiamo che tale operazione abbia costo zero).

Per ogni job J nel sistema lo scheduler di breve termine mantiene due contatori CPU_J e WAIT_J
inizialmente a zero.

Lo scheduler viene risvegliato dal clock ogni 2 secondi (tempo 2,4,6,...) ed inoltre quando un job completa la sua esecuzione.

In entrambi i casi esegue le seguenti operazioni:

per ogni job J incrementa il suo contatore CPU_J di 1 se J e' nello stato running in CPU, incrementa il contatore WAIT_J di 1 se J e' nello stato ready_to_run (e' nella coda di attesa)
dopo aver aggiornato i contatori di ogni processo, seleziona per l'esecuzione in CPU il processo tale che WAIT_J > CPU_J, applicando il criterio First-Come-First-Served rispetto al tempo di arrivo (vedi tabella) nel caso in cui siano possibili diverse scelte o nel caso in cui WAIT_J =< CPU_J per ogni J.

Descrivere la sequenza di esecuzione dei job in CPU e calcolare il tempo di completamento e
di risposta di ogni Job.

Soluzione

0-1

1-2

2-3

3-4

4-5

5-6

6-7

7-8

8-9

9-10

10-11

11-12

12-13

13-14

14-15

15-16

16-17

Wa=0 (*)

Wa=1

Wa=2

Wa=3

Wa=4

Ca=1

Ca=2

Ca=3

Wb=1

Wb=2

Wb=3

Wb=4

Cb=0

Cb=1

Cb=2

Wc=1

Wc=2

Wc=3

Wc=4

Wc=5

Wc=6

Cc=0

Cc=1

Wd=1

Wd=2

Wd=3

Wd=4

Wd=5

Wd=6

Wd=7

Cd=0

Al tempo 0 i contatori sono tutti a 0, A entra e lo scheduler viene attivato al tempo 2.

(*) nella colonna [i,i+1] indica aggiornamento delle variabili al tempo i+1

Tempi di completamento
A: 14
B: 13-1=12
C: 16-3=13
D: 17-5=12

Tempo di risposta

A: 10.5
B: 9.5
C: 14.5
D: 16.5

Esercizio

Considerate i seguenti Job:

Job	Burst time	Tempo di arrivo	Prima risposta
A	7	0	4.5
B	5	1	3.5
C	4	3	2.5
D	1	5	0.5

E2.1
Supponete di utilizzare una politica Shortest Job First con preemption
(chiamata anche Shortest Remaining-Time First).
Assumete che lo scheduler venga attivato quando un job entra nella coda di attesa e
quando un job completa l'esecuzione in CPU.

Descrivere la sequenza di esecuzione dei job in CPU e calcolare
il tempo di completamento e di risposta di ogni Job.

Soluzione

Lo scheduler applica preemption e quindi puo' interrompere processi in esecuzione.

0-1	1-2	2-3	3-4	4-5	5-6	6-7	7-8	8-9	9-10	10-11	11-12	12-13	13-14	14-15	15-16	16-17
A	B	B	B	B	B	D	C	C	C	C	A	A	A	A	A	A

Nota: al tempo 5: b (Running) e D (Ready) hanno Remaining Time uguale a 1 --> non si effettua lo switch

Tempi di completamento
A:        17
B: 6-1 =   5
C: 11-3=   8
D: 7-5 =   2

Tempo di risposta

A:         14.5
B: 15.5-1= 4.5
C: 10.5-3= 9.5
D: 7.5-5 = 6.5

E2.2
Considerate ora la seguente politica di scheduling.
Lo scheduler di lungo termine immette job nella coda di attesa nell'ordine di arrivo
(supponiamo che tale operazione abbia costo zero).

Per ogni job J nel sistema lo scheduler di breve termine mantiene due contatori CPU_J e WAIT_J
inizialmente a zero.
Lo scheduler viene risvegliato dal clock ogni 2 secondi (2,4,6,..) ed inoltre quando un job completa
la sua esecuzione.

In entrambi i casi esegue le seguenti operazioni:

per ogni job J incrementa il suo contatore CPU_J di 1 se J e' nello stato running in CPU, incrementa il contatore WAIT_J di 1 se J e' nello stato ready_to_run (e' nella coda di attesa)
dopo aver aggiornato i contatori di ogni processo, seleziona per l'esecuzione in CPU il processo tale che WAIT_J - CPU_J ha valore massimo su tutti i J, applicando il criterio First-Come-First-Served rispetto al tempo di arrivo (vedi tabella) nel caso in cui siano possibili diverse scelte.