I vari tipi di scheduling di CPU
14 agosto 2013  //  By:   //  System  //  1 comment   //   757 Views

Un pò di appunti di Sistemi Operativi , Le priorità

  • Partiamo dallo scheduling più semplice in assoluto è il FCFS (First Come First Served).

Questo meccanismo prevede l’esecuzione dei processi Ready esattamente nell’ordine in cui si trovano nella coda. Non è prevista prelazione, dunque un processo rimane in esecuzione fino a quando non termina oppure decide di rilasciare la CPU spontaneamente.Questo scheduling sfavorisce eccessivamente i processi I/O bound a favore dei processi CPU bound che verranno eseguiti ininterrottamente per tutta la loro durata.

  • Feedback, implementato tramite code a priorità multipla.

Ogni processo viene inserito in una determinata coda al momento della sua creazione. I processi della coda a priorità maggiore verranno processati prima degli altri. Un processo può mutare la propria priorità in base alla particolare politica che si vuole implementare. Il vantaggio di questa implementazione sta nel favorire, grazie a determinate politiche, processi I/O bound, integrandosi perfettamente con i sistemi interattivi moderni.

  • Round-Robin virtuale 

Questo prevede l’utilizzo di due code: una per i processi che provengono dallo stato running e una per i processi che provengono dallo stato blocked. Un processo presente nella seconda coda avrà priorità maggiore e un quanto di tempo minore (time-slice – consumoDiQuantoPrecedente), quindi variabile per ogni processo. Una volta che un processo ha consumato tutto il quanto viene inserito nella coda a priorità minore. Si tenta così di restituire ai processi che sfruttano IO il tempo perso sul dispositivo. Questo scheduling può risultare inutile quando tutti i processi al momento ready hanno consumato tutto il quanto a disposizione. In questo scheduler è molto importante la scelta del time-slice nell’algoritmo di dispatching Round-Robin. L’algoritmo infatti prevede l’esecuzione dei processi Ready a turno, per un quanto di tempo specifico (slice). E’ prevista prelazione, quindi un processo può essere bloccato anche se non ha utilizzato completamente il suo quanto di tempo. Questo metodo di scheduling svantaggia i processi I/O bound a favore dei processi CPU bound (che sfrutteranno l’intero quanto di tempo disponibile), dunque non è ottimale per la gestione dei processi interattivi. Vi è una criticità nella scelta del time-slice, infatti questa impatta sul numero di quanti necessari per attivare una richiesta di I/O. Se il quanto di tempo è eccessivamente piccolo, occorreranno 2 o più quanti per un’interazione I/O, penalizzando ulteriormente i processi I/O bound. E creando un sottoutilizzo delle periferiche di I/O

  • Shortest-Process-Next (SPN)

Utilizzando lo scheduling SPN, i processi Ready vengono mandati in esecuzione in funzione della lunghezza del loro prossimo CPU Burst (quantità di tempo di utilizzo continuato della cpu prima di liberarla), in particolare in ordine crescente di CPU Burst. Non è prevista Prelazione, la variante con prelazione prende il nome di SRT (shortest-remaing-time). I vantaggi di questo meccanismo sono dati dalla buona gestione dei processi interattivi, situazione che assicura anche un utilizzo efficiente delle periferiche (con prelazione). L’aspetto svantaggioso oltre ad una difficile implementazione, è il calcolo del prossimo CPU Burst e favorisce starvation per processi lunghi.

  • Highest-Response-Ratio-Next

Lo scheduling Highest-Response-Ratio-Next prevede lo scheduling dei processi in base ad un fattore chiamato Rapporto di risposta (RR). L’RR è dato dal rapporto tra la somma del tempo di attesa (w) e il tempo di esecuzione (s) fratto il tempo di esecuzione. Per tempo di attesa si intende la quantità di tempo trascorsa dall’ultima esecuzione del processo. Per tempo di esecuzione invece la quantità di tempo che il processo intende utilizzare nella sua esecuzione (CPU Burst). Si può capire come questo rapporto favorisca i processi I/O bound, caratterizzati da piccoli valori di s, e i processi non schedulati da molto tempo, con alti valori di w. Il principale svantaggio è dato dal calcolo di s, molto complicato da applicare. Ogni processo ready ha una propria priorità.

About the Author :

BI CONSULTING. Studente di Ingegneria Informatica, Sistemista Linux e appassionato di tutto ciò che sia tecnologico ma soprattutto Open Source. Distro: Debian e Arch LInux. Smartphone: Nexus / Lg G2 Buona Lettura  Visualizza il profilo su Linkedln

1 Comment to “I vari tipi di scheduling di CPU”

Leave a reply