Marco Lapegna » 7.Lo scheduling dei processi: introduzione e primi esempi

Sistemi operativi

Lo scheduling dei processi: introduzione e primi esempi

Concetti fondamentali

• Il massimo impiego della CPU è ottenuto con la multiprogrammazione
• Presenza in memoria di numerosi processi in attesa di essere eseguiti
• Il modulo che decide quale processo deve accedere alla CPU e lo SCHEDULER

Vari tipi di scheduler

• Scheduler a lungo termine (scheduler dei job):
  • seleziona quali processi possono competere per le risorse del calcolatore
• Scheduler a medio termine (swapper ):
  • rimuove processi dalla memoria (e dalla contesa per la CPU)
• Scheduler a breve termine (scheduler della CPU) :
  • seleziona quale processo debba essere eseguito successivamente, ed alloca la CPU

Dispatcher

• Il modulo dispatcher passa il controllo della CPU al processo selezionato dallo scheduler a breve termine;
• Il dispatcher effettua il cambio di contesto (context switch)
• Latenza di dispatch — è il tempo impiegato dal dispatcher per sospendere un processo e avviare l’ esecuzione di un nuovo processo

Caratteristiche degli scheduler

Preemptive (con prelazione)

• I processi possono essere rimossi dalla CPU
• Può portare ad un miglioramento delle prestazioni
• Essenziale per S.O. interattivi e time-sharing

Nonpreemptive (senza prelazione)

• I processi mantengono l’uso della CPU fino al loro completamento
• Processi poco importanti possono far ritardare quelli importanti

Preemptive / non preemptive

• La politica preemptive è in genere costosa a causa dei continui cambio di contesto. Va quindi usata solo quando necessaria.
• I sistemi operativi batch sono soprattutto non preemptive, in quanto non ci sono utenti in attesa al terminale.

Preemptive / non preemptive

I sistemi operativi time sharing general purpose che favoriscono l’uso interattivo del calcolatore, sono soprattutto preemptive.

I sistemi operativi real time sono spesso non preemptive, per non aumentare l’overhead del sistema e perchè in genere compiono mansioni specifiche e di breve durata e quindi uno scheduler preemptive non è necessario

Priorità

• Non tutti i processi sono della stessa importanza (es. processi di sistema e processi utente)
• Spesso gli scheduler usano delle priorità per determinare il processo da eseguire, dando priorità maggiore a processi più importanti

Priorità

• Priorità statica
  • Non cambia durante l’esecuzione del processo facile da realizzare
• Priorità dinamica
  • Cambia durante l’esecuzione del processo difficile da realizzare e con un maggior overhead

Obiettivi di scheduling

• Massimo utilizzo di CPU — la CPU deve essere più attiva possibile.
• Massimo Throughput — numero di processi che completano la loro esecuzione nell’unità di tempo.
• Minimo Tempo di completamento — tempo medio di esecuzione di un processo (comprese le attese).
• Minimo Tempo di attesa — tempo speso dal processo in attesa nella ready queue.
• Minimo Tempo di risposta — tempo che intercorre tra la sottomissione di una richiesta e la prima risposta prodotta.

Obiettivi di scheduling

Obiettivi generali:

• equità (dare ad ogni processo una porzione equa della CPU)
• controllo (verificare che le politiche vengano messe in atto)
• bilanciamento (tenere occupate tutte le parti del sistema)
• uso della CPU (tenere sempre occupata la CPU)

Obiettivi di scheduling

• Sistemi batch
  • throughput (massimizzare job per unità di tempo)
  • turnaround time (minimizzare il tempo medio di esecuzione)
• Sistemi interattivi
  • response time (minimizzare i tempi di risposta)
• Sistemi real time
  • deadline (rispettare le scadenze)

Definizione: Burst di CPU e di I/O

• Burst di CPU — Uso continuativo della CPU da parte di un processo
• Burst di I/O — Uso continuativo di un dispositivo di I/O da parte di un processo

(burst = raffica)

Scheduling FCFS

Tempi di attesa: P1 = 6; P2 = 0; P3 = 3

Tempi di completamento: P1 = 30; P2 = 3; P3 = 6

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

Tempo medio di completamento = (30 + 3 + 6)/3 = 13

Non si verifica l’effetto, per cui processi di breve durata devono attendere che un processo molto lungo liberi la CPU.

Scheduling Shortest–Job–First (SJF)

• Si associa a ciascun processo la lunghezza del suo burst di CPU successivo.
• Si opera lo scheduling in base alla lunghezza del burst.

Scheduling Shortest–Job–First (SJF)

• Non–preemptive — una volta che la CPU è stata allocata al processo, non gli può essere prelazionata fino al termine del CPU burst corrente
• Preemptive — se arriva un nuovo processo con burst di CPU minore del tempo rimasto per il processo corrente, il nuovo processo prelaziona la CPU. Questo schema è noto come Shortest–Remaining–Time–First (SRTF)

SJF è ottimale — rende minimo il tempo medio di attesa per un dato insieme di processi.

Scheduling SJF preemptive

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

Tempo medio di completamento = (16 + 5 + 1 +6)/4 = 7

E’ chiamato anche Short Remaining Time First.

Scheduling Shortest–Job–First (SJF)

Lo scheduling SJF è ottimale, in quanto minimizza i tempi medi di attesa.

-> Tale stima è calcolata sulla previsione dei tempi di utilizzo della CPU che non sono informazioni presenti nel PCB.

-> Come stimare i tempi di uso della CPU.

Lunghezza del burst successivo

Può essere stimato utilizzando la lunghezza dei burst di CPU precedenti, impiegando una media esponenziale.

1. t_n = lunghezza dell’n-esimo CPU burst
2. τ_n+1 = valore stimato del prossimo CPU burst
3. α, 0 ≤ α ≤ 1
4. Si definisce:

Esempi di media esponenziale

α = 0

• τ_n+1 = τ_n
• La storia recente non è presa in considerazione.

α = 0.5

• τ_n+1 = (τ_n+ t_n)/2
• Media aritmetica tra tempo stimato ed effettivo.

α = 1

• τ_n+1 = t_n
• Viene considerato soltanto l’ultimo CPU burst.

Esempi di media esponenziale

Osservazione:

Espandendo la formula si ottiene:

τ_n+1 = α t_n + (1-α) α t_n-1 + … + (1-α)^j α t_n-j + … + (1-α)ⁿ⁺¹ τ₀

Poiché α e (1-α) sono entrambi minori o uguali ad 1, ciascun termine ha minor peso del suo predecessore.

Prossima lezione

Algoritmi di scheduling

• Scheduling a priorità
• Scheduling round robin
• Scheduling scheduling a code multiple
• Scheduling real time