Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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