Scheduling CPU

Scheduling della CPU

Scheduler a breve termine

Seleziona tra i processi in memoria e pronti per l'esecuzione quello a cui allocare la CPU. Lo scheduling può avere luogo quando un processo:

1. Passa da running a waiting
2. Passa da running a ready
3. Passa da waiting o new a ready
4. Termina

Nei casi 1 e 4 lo scheduling è non-preemptive, negli altri è preemptive. L'uso della rotazione ha effetti sulla progettazione del kernel (accesso concorrenza delle stesse strutture dati).

Dispatcher

Modulo che dà il controllo della CPU al processo selezionato dallo scheduler di breve termine. Questo compito include:

• Context switch
• Passaggio della CPU da supervisor mode a user mode
• Salto alla locazione del programma adeguata per riprendere il processo

È essenziale che il dispatcher sia veloce. La latenza di dispatch è il tempo necessario per fermare un processo e riprendere un altro.

Criteri di valutazione dello Scheduling

• Utilizzo della CPU: mantenere la CPU il più carico possibile
• Throughput: numero di processi completati nell'unità di tempo
• Tempo di turnaround: tempo totale impiegato per esecuzione di un processo
• Tempo di attesa: quanto tempo un processo ha atteso in ready
• Tempo di risposta: quanto tempo è trascorso da quando un richiedente viene inizializzato, quando si ottiene la prima risposta
• Cardinal throughput: Time-sharing è pensato per i sistemi

Algoritmi di scheduling

First-Come First-Served (FCFS)

Senza prelazione, inadatto per time-sharing. Equo: ma c'è pericolo di starvation.

Esempio: ordine Processi

Ordine di arrivo: P₁, P₂, P₃

Diagramma di Gantt:

P₁   P₂   P₃
(P₁, 0)   (P₂, 24)   (P₃, 27)

Tempi di attesa:

• P₁ = 0
• P₂ = 24
• P₃ = 27

Tempo di attesa medio: (0 + 24 + 27) / 3 = 17

Supponiamo che l’ordine di arrivo ora sia P₂, P₃, P₁

Diagramma di Gantt:

P₂   P₃   P₁
0   3   6   30

Tempi di attesa:

• P₁ = 6
• P₂ = 0
• P₃ = 3

Tempo di attesa medio: (6 + 0 + 3) / 3 = 3, molto meglio rispetto al caso precedente.

Effetto concaffio: i processi di I/O bound si accodano dietro un processo CPU-bound.

Shortest Job First (SJF)

Associa ad ogni processo la lunghezza del suo prossimo burst di CPU. I processi vengono ordinati e schedulati per tempi crescenti. Due schemi possibili:

• Non preemptive: quando la CPU viene assegnata ad un processo, questa lo mantiene finché non termina il suo burst.
• Preemptive: se nella ready queue arriva un nuovo processo il cui massimo burst è minore del tempo rimanente per il processo attualmente in esecuzione, quest’ultimo viene messo in coda (Scheduling Shortest Remaining Time First SRTF).

SJF se preemptive → SRTF. SJF è ottimale: fornisce il minimo tempo d'attesa per un dato insieme di processi. Rischio: starvation.

Esempio di SJF non preemptive

Diagramma di Gantt:

P₁   P₃   P₂   P₄
0   7   8   12   16

Tempo di attesa medio: (0 + 6 + 3 + 7) / 4 = 4

Per calcolare il tempo di attesa di ognuno, ricordati di tenere conto anche dei tempi di arrivo.

CPU burst: fasi in cui viene utilizzato solo la CPU senza operazioni di I/O. CPU burst di breve durata per I/O bound, lunga durata per CPU-bound.

Esempio di SJF preemptive

Tempo di atteso medio: (9 + 1 + 0 + 2) / 4 = 3

Come determinare la lunghezza del massimo ciclo di burst? Si può solo stimare: nei sistemi batch, il tempo viene stimato dagli utenti. Nei sistemi time-sharing, possono essere usati valori dei burst precedenti con una media pesata esponenziale dove:

• t_n = tempo dell'n-unesimo burst di CPU
• T_{n + 1} = valore previsto per il prossimo burst di CPU
• α = parametro 0 ≤ α ≤ 1

T̂_n+1 = α t_n + (1 - α) T_n

Espandendo la formula:

T_n+1 = α t_n + (1 - α) α t_n-1 + ... + (1 - α)ⁿ T₀

Se α = 0 → T_n+1 = T₀ la storia recente non conta. Se α = 1 → T_n+1 = t_n solo l'ultimo burst conta. Valore tipico per α: 0,5, in tal caso la formula diventa:

T̂_n+1 = ^{t_n + T_n}/₂

Scheduling a priorità

Ad ogni processo viene assegnato un numero (intero) di priorità (min maggiore e lo minor), la CPU viene dedicata al processo con priorità più alto. Le priorità possono essere definite:

• Internamente
• Esternamente

In base ai parametri misurati dal sistema sul processo (tempo di CPU impiegato, file aperti, memoria, interactivity, uso di I/O, ...). Gli scheduling con priorità possono essere preemptive o non-preemptive.

Problema: Starvation, i processi con bassa priorità potrebbero non venire mai eseguiti data la presenza di processi con priorità maggiore continua.

Soluzione: Aging → col passare del tempo, i processi non eseguiti aumentano la loro priorità.

Round Robin (RR)

Algoritmo con rotazione specifico dei sistemi time-sharing simile a FIFO ma con rotazione quantizzata. Ogni processo riceve una piccola quantità di tempo della CPU (quanto) generalmente da 10-100 ms, dopo questo tempo il processo viene pre-emmato e rimesso nella coda di ready. Se ci sono n processi nella coda di ready e q è il quanto allora ogni processo riceve 1/n del tempo di CPU in periodi di durata massima q. Nessun processo attende più di (n-1) q per essere eseguito.

Esempio:

• P₁ = 53
• P₂ = 17
• P₃ = 68
• P₄ = 24

Diagramma di Gantt:

P₄   P₂   P₃   P₄   P₁   P₃   P₁   P₁   P₃
0   20   34   57   77   97   117   121   134   154

Tipicamente si ha un tempo di turnaround medio maggiore, ma minore tempo di risposta.

Prestazioni dello scheduling RR:

• q grande → degenerazione nel FCFS
• q piccolo → q deve essere comunque grande rispetto al tempo di context switch altrimenti l'overhead è elevato
• L'80% dei CPU burst dovrebbe essere inferiori a q

Scheduling con code multiple

La coda di ready è partizionata in più code separate, ad esempio processi foreground e processi background. Ogni coda ha il suo algoritmo di scheduling: ad esempio RR per processi foreground e SJF o FCFS per quelli background. Lo scheduling deve avvenire tra tutte le code.

Scheduling a priorità fissa

Rischio di starvation. Quanti di tempo per le code.

Scheduling a code multiple con feedback

I processi vengono spostati da una coda all'altra dinamicamente. Ad esempio: se un processo ha usato recentemente poca CPU allora viene spostato in una coda a priorità maggiore, se ne ha usato molta viene degradato ad una coda con priorità più bassa. Uno scheduler a code multiple con feedback viene definito dai seguenti parametri:

• Numero di code
• Algoritmo di scheduling per ogni coda
• Come determinare quando promuovere un processo
• Come determinare quando degradare un processo
• Come determinare in quale coda mettere un processo quando entra nello stato di ready

Esempio di code multiple con feedback: 3 code: Q₀, Q₁ e Q₂

• Q₀ → quanti di 8 ms
• Q₁ → 9 o 16 ms
• Q₂ → FCFS senza preliezione

Scheduling:

• Un nuovo job entra in Q₀, il non termina passa in Q₁. In Q₀ ogni job è servito, come in Q₀, con FCFS con precedenza; se non termina (dopo che Q₀) e si è svuotato) passa in Q₂
• In Q₂ ogni job è servito dal FCFS normale, quando Q₀ e Q₁ sono vuoti.

Scheduling garantito

Si promette un certo quality of service: Se per esempio ci sono n utenti ciascuno ha diritto ad un tempo di CPU pari a 1/n.

Implementazione: Per ogni processo T_i si tiene un contatore da quando è stato lanciato. È tempo di cui avrebbe diritto è pari a T_i = T/n dove T_i è il tempo trascorso dall'inizio del processo. La priorità dunque diventa T_i/T_p (più è bassa, maggiore è la priorità).

Schedulazione a lotteria

Semplice implementazione di una schedulazione garantita: Essegnano un certo numero di biglietti per ogni risorsa; ogni processo acquista un sottinsieme di tali biglietti. Viene estratto un biglietto e la risorsa viene assegnata ai vincitore. Per la legge dei grandi numeri: alla lunga l'accesso è proporzionale al numero di biglietti. I biglietti possono essere passati da un processo all'altro per equilibrare priorità.

Scheduling multi-processor

Lo scheduling diventa più complesso quando più CPU sono disponibili. Nei sistemi omogenei è indifferente quale processore esegue il massimo task. Tuttavia, potrebbe comunque essere richiesto che certi task vengano eseguiti su una loro macchina specifica (pinning).

Problemi: bilanciamento del carico - tutti i processori selezionano i processi dalle stesse ready queue. - accesso condiviso alle strutture dati del kernel.

Asymmetric MultiProcessing (AMP)

Solo un processore alla volta può accedere alle strutture dati del kernel. Semplifica il problema ma diminuisce le prestazioni.

Symmetric MultiProcessing (SMP)

C'è una condivisione delle strutture dati tra tutti i processori. Serve hardware particolare e controlli di sincronizzazione in kernel.

Scheduling Real-Time

Hard Real-Time

Si richiede che un task critico venga completato entro un tempo ben preciso e garantito. Questo comporta:

• Prenotazione delle risorse
• Determinazione di tutti i tempi di risposta, non ci possono essere memorie virtuali
• Conoscenza di se
• Sostituirli a hardware dedicati

Soft Real-Time

I processi critici sono prioritari rispetto agli altri:

• Possono coesistere con i normali processi time-sharing
• Lo scheduler deve mantenere i processi real time prioritari
• La latenza di dispatch deve essere più bassa possibile
• Adatto nei piattaforme general purpose, trattamento audiovisivo