Esercizio - Rate monotonic ed EDF su due compiti periodici (slide di scheduling)

Testo (esempi delle slide di scheduling del corso di Sistemi Operativi, Ing. Informatica UniPD). Due compiti periodici con scadenza uguale al periodo.

• Caso 1: $P_1$ con $p_1 = 50$, $t_1 = 20$; $P_2$ con $p_2 = 100$, $t_2 = 35$. Il carico complessivo (75%) è sostenibile? Si confrontino le assegnazioni di priorità fissa $P_2 > P_1$ e Rate Monotonic.
• Caso 2: $P_1$ con $p_1 = 50$, $t_1 = 25$; $P_2$ con $p_2 = 80$, $t_2 = 35$. Si verifichi la schedulabilità con Rate Monotonic e con EDF.

Teoria: 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 →. I compiti sono rilasciati a $0, p, 2p, \dots$ e devono finire entro $p$ unità dal rilascio.

Caso 1

Utilizzo: $\dfrac{20}{50} + \dfrac{35}{100} = 0{,}40 + 0{,}35 = 0{,}75$.

Priorità $P_2 > P_1$. $P_2$ esegue 0 .. 35, poi $P_1$ 35 .. 55: ma la scadenza della prima istanza di $P_1$ è 50: persa. Il 75% non basta se la priorità è sbagliata.

Rate Monotonic ($P_1$, periodo più breve, priorità più alta):

• $P_1$ finisce a 20 $\le 50$; seconda istanza rilasciata a 50, finisce a 70 $\le 100$;
• $P_2$ parte a 20, a 50 è prelazionato (ha fatto 30 su 35), riprende a 70 e finisce a 75 $\le 100$.

Entrambe le scadenze sono rispettate. Conferma dal limite: per $N = 2$ il limite di RMS è $2(\sqrt{2} - 1) = 0{,}828$ e $0{,}75 < 0{,}828$.

Caso 2

Utilizzo $\dfrac{25}{50} + \dfrac{35}{80} = 0{,}5 + 0{,}4375 = 0{,}9375$, oltre il limite RMS 0,828.

RMS ($P_1$ ha priorità, $p_1 < p_2$):

$P_2$ finisce a 85, ma la sua scadenza è 80: scadenza mancata. (Il limite è solo sufficiente: oltre di esso non si può garantire, e qui avviene davvero.)

EDF (priorità alla scadenza assoluta più vicina):

• a $t=50$ arriva la 2ª istanza di $P_1$ (scadenza 100) ma $P_2$ ha scadenza 80: nessuna prelazione, $P_2$ finisce a 60;
• a $t=60$ resta solo $P_1$ (scad. 100), finisce a 85;
• a $t=80$ è rilasciata la 2ª istanza di $P_2$ (scadenza 160); a 85 $P_2$ è l'unico pronto: esegue fino a 100 (15 unità);
• a $t=100$ la 3ª istanza di $P_1$ (scadenza 150) ha scadenza minore di quella di $P_2$ (160) e prelaziona; finisce a 125; $P_2$ riprende e finisce a 145 $\le 160$.

Tutte le scadenze sono rispettate: EDF funziona perché $U = 0{,}9375 < 1$ (RMS richiede $U \le 0{,}828$ per garantire).

I tracciati sono stati confermati con una simulazione in Python sull'iperperiodo.

Domande d'esame

Con $U = 0{,}9$ per due compiti, RMS è garantito? E EDF? Traccia. RMS garantisce solo fino a $2(2^{1/2} - 1) = 0{,}828$: non garantito (può funzionare, ma va verificato). EDF garantisce per ogni $U \le 1$.