Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

Scheduler a breve termine

In figura si mostra los chema di funzionamento di uno scheduler a breve termine, con indicazione della ready queue.

Schema di funzionamento (breve termine)

Schema di funzionamento (breve termine)


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

Context switch

  1. I registri della CPU contengono i dati relativi a P1 (program counter, stack pointers, PID, stato,…)
  2. La cpu passa in modalità sistema e salva il contenuto dei registri nel PCB1
  3. La cpu carica nei registri il contenuto del PCB2 e passa in mod. utente
  4. La cpu ha il controllo di P2
Procedura per passi (context switch)

Procedura per passi (context switch)


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

Esempio

In figura si mostra una tabella esplicativa relativa alle priorità di Windows XP.

Tabella delle priorità (windows)

Tabella delle priorità (windows)


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 First–Come–First–Served

Processo -> Tempo di burst

P1 -> 24

P2 -> 3

P3 -> 3

I processi arrivano al sistema nell’ordine: P1 , P2 , P3. Il diagramma di Gantt per lo scheduling FCFS è:

Diagramma di Gantt

Diagramma di Gantt


Scheduling First–Come–First–Served

Tempi di attesa: P1 = 0; P2 = 24; P3 = 27.

Tempi di completamento: P1 = 24; P2 = 27; P3 = 30.

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

Tempo medio di completamento = (24 + 27 + 30)/3 = 27.

Diagramma di Gantt

Diagramma di Gantt


Scheduling FCFS

Se l’ordine di arrivo è P2 , P3 , P1 il diagramma di Gantt risulta:

Diagramma di Gantt

Diagramma di Gantt


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 non–preemptive

Processo -> Tempo di arrivo -> Tempo di burst

  • P1 -> 0.0 -> 7
  • P2 -> 2.0 -> 4
  • P3 -> 4.0 -> 1
  • P4 -> 5.0 -> 4

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

Tempo medio di completamento = (7 + 10 + 4 + 11)/4 = 8

Diagramma di Gantt

Diagramma di Gantt


Scheduling SJF preemptive

Processo -> Tempo di arrivo -> Tempo di burst

  • P1 -> 0.0 -> 7
  • P2 -> 2.0 -> 4
  • P3 -> 4.0 -> 1
  • P4 -> 5.0 -> 4
Diagramma di Gantt

Diagramma di Gantt


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. tn = lunghezza dell’n-esimo CPU burst
  2. τn+1 = valore stimato del prossimo CPU burst
  3. α, 0 ≤ α ≤ 1
  4. Si definisce:

Esempio

In figura è mostrato un esempio numerico con relativo diagramma.

Schema dell’esempio

Schema dell'esempio


Esempi di media esponenziale

α = 0

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

α = 0.5

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

α = 1

  • τn+1 = tn
  • Viene considerato soltanto l’ultimo CPU burst.

Esempi di media esponenziale

Osservazione:

Espandendo la formula si ottiene:

τn+1 = α tn + (1-α) α tn-1 + … + (1-α)j α tn-j + … + (1-α)n+1 τ0

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
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion