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

Antonino Mazzeo » 10.Scheduling dei processi


Sommario

  • Schedulatore
    • Tipologie di schedulatori
  • Algoritmo di scheduling
  • Tipi di algoritmi di scheduling
    • FCFS
    • Round Robin
    • Short Process Next
    • Short Remaining Time
    • Feedback
    • Multilevel Feedback

Schedulatore

  • Lo schedulatore (o scheduler) è quella parte del S.O. preposta all’assegnazione di risorse a favore dei processi
  • La selezione di un processo in una coda può avvenire mediante differenti criteri, a seconda dell’algoritmo di scheduling che implementa uno schedulatore
  • Tipologie di Scheduler
    • lo schedulatore a breve termine o scheduler della CPU
    • lo schedulatore a medio termine o schedulatore di swap (swapper)
    • lo schedulatore a lungo termine o schedulatore di job
Schedulatore di lungo termine

Schedulatore di lungo termine


Algoritmo di scheduling

  • L’obiettivo dell’algoritmo di scheduling del Dispatcher è quello di allocare il processore in maniera tale da ottimizzare uno o più aspetti del comportamento del sistema
  • I criteri più utilizzati sono:
    • User-oriented. Si riferiscono al comportamento del sistema così come percepiti dall’utente o da un processo (ad es. tempo di risposta)
      • Tempo di turnaround, Tempo di risposta, Deadlines
    • System-oriented. L’obiettivo è quello di utilizzare in modo efficiente il processore (ad es. il throughput)
      • Throughput, Utilizzo della CPU, Fairness
  • Il progetto e l’implementazione di una politica di scheduling implica sempre un compromesso tra vari requisiti contrastanti. La scelta dovrà essere fatta tenendo conto “per cosa dovrà essere utilizzato il sistema”

Algoritmi di Scheduling

  • I processi tipicamente sono raggrupati in classi di priorità
    • l’algoritmo sceglie il processo pronto appartenente alla classe di priorità più alta
      • Problema della starvation, a cui si fa fronte utilizzando schemi di priorità dinamiche (es. Aging).
  • Lo scheduler di breve termine può essere
    • Nonpreemptive: non può interrompere un processo in esecuzione
    • Preemptive: può interrompere un processo in esecuzione
  • First-Come-First-Served (FCFS)
    • Quando il processo cessa la sua esecuzione, viene scelto il processo che attende da più tempo
  • Round-Robin
    • Nasce dalla trasformazione preemptive del FCFS mediante l’impiego di un timer

Algoritmi di scheduling

  • Shortest Process Next
    • Vengono selezionati i Processi con il minor tempo di esecuzione stimato
    • In genere viene utilizzata una stima basata su media esponenziale come illustrato nell’immagine:
  • Shortest Remaining Time
    • E’ la versione Preemptive dell’alg. Shortest Process Next
    • Anche in questo caso c’è il problema della stima del tempo di esecuzione
Valore stimato

Valore stimato


Algoritmi di scheduling

  • Feedback
    • Favorisce i processi più corti
    • Utile se non si hanno indicazioni sulla lunghezza relativa dei vari processi (nel qual caso non è possibile utilizzare gli algoritmi SPN, SRT)
  • Multilevel Feedback
    • Lo scheduling è di tipo preemptive basato su quanto di tempo
    • …è utilizzato un meccanismo di priorità dinamico (se un processo usa “troppo” tempo di eleborazione CPU, viene spostato in una coda con prioirtà minore)
      • Quando un processo entra nel sistema si pone nella coda a più alta priorità (RQ0)
      • Dopo la prima prelazione il processo ritorna nello stato di ready nella coda RQ1
      • …così via fino ad arrivare alla coda a minima priorità (RQn)

Caratteristiche delle politiche di scheduling

w= tempo di attesa; e= tempo di esecuzione; s= tempo di servizio incluso

Tabella esplicativa (politiche di scheduling)

Tabella esplicativa (politiche di scheduling)


Prossima lezione

Introduzione alla Sincronizzazione dei Processi

I materiali di supporto della lezione

P. Ancilotti, M.Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap.2)

W. Stallings, “Operating Systems : Internals and Design Principles (5th Edition) ”, Prentice Hall (Cap. 9)

A. Silbershatz, G. Gagne, "Sistemi Operativi" (sesta edizione), Addison-Wesley

Scheduling

  • 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