Esercizio - shortest-first job scheduling, proprietà SJF e sottostruttura (esercitazione greedy, es. 10.2)

Passo 1: una formula per il costo

Il tempo $t_{\pi(j)}$ del job eseguito in posizione $j$ compare nell'attesa di tutti i job eseguiti dopo, cioè delle posizioni $j+1, \dots, n$, che sono $n - j$. Quindi $$T_{sum}^\pi = \sum_{i=1}^{n} \sum_{j=1}^{i-1} t_{\pi(j)} = \sum_{j=1}^{n-1} (n - j)\, t_{\pi(j)} .$$ (L'ultimo job pesa con $n - n = 0$: non fa aspettare nessuno.) Il primo job ha peso $n - 1$, il secondo $n - 2$, e così via: i job eseguiti prima contano di più, ed è per questo che conviene mettere avanti quelli brevi. La formula è la base di tutto il resto.

Esempio. $t = (3, 1, 4, 2)$ per $J_1, \dots, J_4$. Nell'ordine $J_1, J_2, J_3, J_4$ le attese sono $0, 3, 4, 8$ e $T_{sum} = 15$ (con la formula: $3 \cdot 3 + 2 \cdot 1 + 1 \cdot 4 = 15$). Nell'ordine $J_2, J_4, J_1, J_3$ (durate $1, 2, 3, 4$) le attese sono $0, 1, 3, 6$ e $T_{sum} = 10$ ($3 \cdot 1 + 2 \cdot 2 + 1 \cdot 3 = 10$).

Passo 2: la proprietà SJF

Dimostrazione per assurdo con scambio (cut-and-paste). Sia $\pi^\ast$ ottimo e si supponga che non soddisfi SJF: $\pi^\ast(1) = r$ e $J_r$ non è di durata minima. Esiste allora un job $J_s$ con $s \ne r$ più breve, $t_s < t_r$, eseguito in una posizione $k > 1$: $\pi^\ast(k) = s$.

Si costruisce $\hat\pi$ scambiando $J_r$ e $J_s$: $$\hat\pi(i) = \begin{cases} s & i = 1 \\ r & i = k \\ \pi^\ast(i) & i \ne 1, k . \end{cases}$$

Si confrontano le attese $T_i^{\hat\pi}$ con $T_i^{\pi^\ast}$:

• $i = 1$: entrambe $0$.
• $1 < i \le k$: la somma $\sum_{j<i} t_{\hat\pi(j)}$ contiene la posizione $1$ ma non la posizione $k$ (perché $j < i \le k$). Rispetto a $\pi^\ast$ compare $t_s$ al posto di $t_r$: $$T_i^{\hat\pi} = T_i^{\pi^\ast} - t_r + t_s < T_i^{\pi^\ast}, \quad\text{perché } t_s - t_r < 0 .$$
• $i > k$: la somma contiene entrambe le posizioni $1$ e $k$, scambiate: gli addendi sono gli stessi, in ordine diverso per due di essi. $T_i^{\hat\pi} = T_i^{\pi^\ast}$.

Poiché $k > 1$, c'è almeno un indice ($i = 2$) con diminuzione stretta, e in totale $$T_{sum}^{\hat\pi} = T_{sum}^{\pi^\ast} - (k-1)(t_r - t_s) < T_{sum}^{\pi^\ast},$$ (la diminuzione è $t_r - t_s$ per ciascuno degli indici $i = 2, \dots, k$, cioè $k - 1$ volte). Questo contraddice l'ottimalità di $\pi^\ast$. $\square$

Osservazione: la proprietà vale per ogni ottimo (versione più forte della scelta greedy "esiste un ottimo"). Con tempi uguali possono esserci più ottimi, tutti con primo job di durata minima.

Passo 3: l'algoritmo e la sottostruttura ottima

Se si vede la scelta di $\pi^\ast(1)$ come scelta greedy (Paradigma greedy - scelta golosa, sottostruttura e selezione delle attivitàIl paradigma greedy compie subito una scelta localmente migliore (scelta greedy), pulisce l'istanza (clean-up) e risolve l'unica sottoistanza residua, con ricorsione di coda eliminabile; il codice è facile, la correttezza no e richiede due proprietà, la scelta greedy (esiste un ottimo che la contiene) e la sottostruttura ottima (cut-and-paste), da cui la correttezza segue per induzione. Caso di studio: la selezione delle attività, con l'algoritmo del primo che finisce, correttezza completa, complessità Theta(n) dopo l'ordinamento e controesempi per le scelte greedy sbagliate.Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività →), la SJF dice che essa è un job di durata minima. Non c'è clean-up: la residua è semplicemente l'insieme degli altri $n-1$ job, $\{J_1, \dots, J_n\} \setminus \{J_{\pi^\ast(1)}\}$. Ripetendo la scelta, lo scheduling che ne esce si ottiene ordinando i job per durata non decrescente: $\pi(i)$ è l'indice dell'$i$-esimo job della sequenza ordinata. Il codice si riduce a una chiamata a una routine di ordinamento (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →): costo $O(n \log n)$.

SJF_SCHEDULE(t)
    ordina gli indici 1..n per t non decrescente      // O(n log n)
    pi(i) <- indice del job in posizione i dell'ordine
    return pi

Sottostruttura ottima. Sia $\pi^\ast$ ottimo (conterrà la scelta greedy) e sia $\pi_R^\ast : \{2, \dots, n\} \to \{1, \dots, n\} \setminus \{\pi^\ast(1)\}$, con $\pi_R^\ast(i) = \pi^\ast(i)$, lo scheduling dei job successivi, cioè dell'istanza residua. Il tempo di attesa di ogni job della residua, sotto $\pi_R^\ast$, è quello sotto $\pi^\ast$ diminuito di $t_{\pi^\ast(1)}$, perché il primo job non c'è più. I job della residua sono $n-1$, quindi $$T_{sum}^{\pi^\ast} = (n - 1)\, t_{\pi^\ast(1)} + T_{sum}^{\pi_R^\ast} .$$ Il primo termine non dipende da $\pi_R^\ast$: se $\pi_R^\ast$ non fosse ottimo per la residua, sostituendolo con uno scheduling migliore (cut-and-paste) si avrebbe per l'istanza principale un costo minore di $T_{sum}^{\pi^\ast}$, assurdo. Quindi $\pi_R^\ast$ è ottimo per la residua.

Correttezza. Per induzione sul numero di job: per $n = 0$ (o $1$) lo scheduling vuoto (o banale) è ottimo; per $n \ge 1$ lo scheduling ordinato inizia con un job di durata minima (SJF), prosegue con lo scheduling ordinato della residua, ottimo per ipotesi induttiva, e per la formula sopra ha costo $(n-1) t_{\min} + \mathrm{opt}(\text{residua}) = \mathrm{opt}$.

Una seconda lettura. Dalla formula $T_{sum}^\pi = \sum_j (n-j)\, t_{\pi(j)}$ si vede che si accoppiano i pesi decrescenti $n-1, n-2, \dots, 0$ con i tempi: la somma è minima quando i pesi grandi vanno ai tempi piccoli (disuguaglianza del riordinamento), cioè con tempi non decrescenti. È lo stesso risultato per un'altra strada.

Tutte le affermazioni (formula del costo, SJF per ogni ottimo, sottostruttura, ottimalità dell'ordine per durata) sono state verificate con Python generando tutte le permutazioni per $n \le 7$ su 2000 istanze casuali. Lo stesso criterio, visto dal punto di vista di un sistema operativo (attesa media, versione preemptive), è in 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 →.