Scheduling CPU

Scheduling della CPU

Scheduler a breve termine

• Seleziona fra i processi in memoria, pronti per l'esecuzione, quello a cui allocare la CPU.

La selezione dello scheduling può avvenire quando un processo:

1. passa da running a waiting
2. passa da running a ready
3. passa da waiting a new a ready
4. termina

Nei casi 1 e 4 lo scheduling è non preemptive, negli altri è preemptive.

Esso della relazione ha effetti sulla progettazione del Kernel (accesso concorrente delle stesse strutture dati)

Dispatcher

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

• Context switch
• Passaggio della CPU da supervisor mode a user mode
• Salto alla locazione del programma utente 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 più carica possibile
• Throughput: numero di processi completati nell'unità di tempo
• Tempo di turnaround: tempo totale impiegato per l'esecuzione di un processo
• Tempo di attesa: quanto tempo un processo ha atteso in ready
• Tempo di risposta: quanto tempo è trascorso da quando era richiesto l'uso individuale quando è ottenuto la prima risposta. (Non throughput!) è pensato per i sistemi time-sharing.

• Variazione del tempo di risposta: quando il tempo di risposta è variabile.

Algoritmi di Scheduling

First Come First Served (FCFS)

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

Esempio: ordine Processi

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

Diagramma di Gantt:

(P₁, t)   (P₂, t)   (P₃, t)

P₁   P₂   P₃

0   24   27   30

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 migliore rispetto al caso precedente.

Effetto convoglio: i processi di I/O bound si accodano dietro un processo cpu bound

Esempio

q = 20

Processo Burst time

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

Diagramma di Gantt

P₄ P₂ P₃ P₄ P₁ P₃ P₄ P₁ P₃

0 20 34 57 71 91 117 121 134 154 162

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

Prestazioni dello scheduling RR

• q grande ⇒ degenza 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 inferiore a q