Esercizio - Scheduling con I-O, effetto convoglio ed EDF (eserciziario, esercizio 27)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 27, tre parti).

(a) Quattro processi con burst di CPU $P_1 = 2$, $P_2 = 3$, $P_3 = 7$, $P_4 = 18$ ms, tutti all'istante 0. Ognuno esegue il proprio burst, poi un'operazione di I/O di 10 ms, poi un altro burst della stessa lunghezza del precedente, e infine termina. Gli I/O possono procedere in parallelo. Si disegnino i diagrammi di Gantt con RR con quanto di 2 ms e con SJF preemptive (SRTF) e si valuti il tempo medio di attesa.

(b) Task indipendenti $A, B, C, D$ su un solo processore: appena un task ha finito la propria esecuzione è pronto per la successiva (che non dura necessariamente come la prima).

Gantt con FCFS, tempo di attesa di ciascun task; lo scheduling soffre dell'effetto convoglio?

(c) Processi periodici con scadenza: $T_1$ (arrivo 0, esecuzione 10, scadenza 33), $T_2$ (4, 3, 28), $T_3$ (5, 10, 29). Gantt con EDF e verificare se tutte le scadenze sono rispettate (lo scheduling è fattibile).

Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin →, Scheduling multiprocessore e real-timeNei sistemi real-time conta la scadenza: si misurano latenza di interrupt e latenza di dispatch; i sistemi soft real-time danno priorità ai compiti critici senza garanzie, quelli hard devono rispettare le scadenze; per compiti periodici (burst t, scadenza d, periodo p, con 0 <= t <= d <= p) l'utilizzo è la somma di t/p: Rate Monotonic (priorità fissa, minore il periodo maggiore la priorità) garantisce le scadenze se l'utilizzo non supera N(2^(1/N)-1) (83% per due compiti), Earliest Deadline First (priorità dinamica, scadenza più vicina) le garantisce se l'utilizzo è sotto il 100%; la ripartizione proporzionale assegna T quote con controllo di ammissione; con più processori si hanno code comuni o private (SMP), core con più thread hardware, bilanciamento del carico (push e pull migration), affinità al processore (soft e hard), scheduling NUMA-aware; Linux usa CFS/EEVDF con domini di scheduling, Windows 32 livelli di priorità.Scheduling multiprocessore e real-time →.

(a) Round robin con $q = 2$

Per ogni processo: primo burst, I/O di 10 ms (la CPU è libera), secondo burst della stessa lunghezza. Un processo che torna dall'I/O all'istante $t$ entra in coda; se nello stesso istante scade un quanto, il processo che rientra va prima di quello prelazionato (la soluzione del corso lascia libera la scelta e dà il risultato che segue).

Tempi di attesa in coda (tempo pronto ma non in esecuzione, escluso l'I/O):

• $P_1$: primo burst subito (0); rientra a 12 e parte a 15: $3$.
• $P_2$: $(2 - 0) + (8 - 4) + (20 - 19) + (24 - 22) = 2 + 4 + 1 + 2 = 9$.
• $P_3$: $(4 - 0) + (9 - 6) + (13 - 11) + (19 - 15) + (31 - 30) + (35 - 33) + (39 - 37) = 4 + 3 + 2 + 4 + 1 + 2 + 2 = 18$.
• $P_4$: $(6 - 0) + (11 - 8) + (17 - 13) + (22 - 19) + (25 - 24) + (33 - 31) + (37 - 35) = 6 + 3 + 4 + 3 + 1 + 2 + 2 = 21$.

Media $= (3 + 9 + 18 + 21)/4 = 51/4 = 12{,}75$.

(a) SJF preemptive (SRTF)

Attese: $P_1 = 0$, $P_2 = 2$, $P_3 = 5$, $P_4 = 24$; media $= 31/4 = 7{,}75$. SRTF dà un'attesa media molto più bassa di RR perché favorisce i burst brevi, mentre RR tratta tutti allo stesso modo.

(b) FCFS

Le richieste entrano in coda nell'ordine in cui sono pronte (arrivo o fine del burst precedente).

Attesa totale $=$ somma, per ogni esecuzione, di (inizio $-$ istante in cui è pronta):

• $A$: $(0 - 0) + (16 - 10) + (25 - 22) = 9$;
• $B$: $(10 - 2) + (22 - 13) + (29 - 24) = 8 + 9 + 5 = 22$;
• $C$: $13 - 3 = 10$;
• $D$: $(15 - 5) + (24 - 16) = 10 + 8 = 18$.

Effetto convoglio: sì. Il primo burst di $A$ (10 unità) fa aspettare tutti i brevi ($B$, $C$, $D$) e si ripete: i task brevi accumulano attese ($B = 22$) maggiori di quelle del task lungo ($A = 9$).

(c) EDF

A ogni istante si esegue il processo pronto con scadenza assoluta più vicina. Le scadenze assolute sono quelle date (33, 28, 29).

• a $t=4$ arriva $T_2$ (scadenza 28 < 33): prelaziona $T_1$, che ha eseguito 4 su 10;
• $T_2$ finisce a 7; a $t=5$ era arrivato $T_3$ (29), ma 28 < 29, quindi $T_2$ non è interrotto;
• a $t=7$ tra $T_1$ (33) e $T_3$ (29) vince $T_3$, che finisce a 17;
• $T_1$ riprende e completa i restanti 6 a $t = 23$.

Completamenti: $T_2 = 7 \le 28$, $T_3 = 17 \le 29$, $T_1 = 23 \le 33$: tutte le scadenze sono rispettate, lo scheduling è fattibile (la CPU resta libera dopo il 23).

Nota sugli errori del corso

Nella soluzione del corso la riga intestata "TA" per RR e SJF preemptive riporta 12,75 e 7,75, che sono tempi di attesa medi (somme 3 + 9 + 18 + 21 e 0 + 2 + 5 + 24), non turnaround.

Domande d'esame

Perché con processi che alternano CPU e I/O SRTF batte RR sull'attesa media? Traccia. SRTF dà sempre la CPU a chi ha il burst residuo più breve e finisce i brevi per primi; RR ruota a quanti uguali e prolunga tutti. Qui 7,75 contro 12,75.