In un articolo su deverloperWorks viene affrontato il tema del funzionamento dello scheduler CFS, Completely Fair Scheduler, di Linux e dell’evoluzione rispetto ai precedenti algoritmi.
Il concetto alla base del CFS è il mantenimento di un’equa distribuzione del tempo a tutti i processi. Quando uno o più processi non ricevono la loro giusta parte di tempo macchina allora l’algoritmo ribilancia la situazione dandogli la possibilità di essere eseguiti.
Per determinare il bilanciamento vengono mantenute in un RB-albero le informazioni sul tempo processore utilizzato e sul tempo in attesa di input/output.
Questa struttura dati consente di effettuare operazioni in tempo O(log n) e di bilanciarsi da sola. Lo scheduler prende il processo più a sinistra dell’albero e dopo averlo fatto girare, se è ancora runnable, lo reinserisce dopo avergli aggiungo il tempo processore utilizzato tornando a competere con gli altri per il processore.
Via | Ibm
Seguici
ossblog è un supplemento alla testata Blogo.it registrata presso il Tribunale di Milano n. 487/06, P. IVA 04699900967. Contatti, Chi siamo, Condizioni di utilizzo, Privacy.
© 2004-2012 Blogo.it, alcuni diritti riservati sotto licenza Creative Commons.
Per informazioni pubblicitarie e progetti speciali su Ossblog.it contattare la concessionaria esclusiva Populis Engage.
(5 Voti | Media: 4.2 su 5)
thelostone
20 dic 2009 - 17:52 - #1Lpt sei andato proprio nel dettaglio tecnico con questo post!! Chiunque non abbia studiato per esami di Algoritmi, Sistemi Operativi e Programmazione non avrà idea di quello di cui si parla! Comunque molto interessante, approfondirò.
Khamel
20 dic 2009 - 21:09 - #2D’accordissimo con thelostone.Complimenti per gli articoli Lpt On Fire!,sono tutti molto interessanti :)
dgrossato.101
21 dic 2009 - 10:50 - #3Ne avevo già parlato anch’io nel 2007 in termini un po’ più semplici e in italiano nell’articolo http://blog.dgrossato.com/2007/10/cfs-per-tutti-cfs-for-dummies.html . Se a qualcuno interessa .. ;-)
lascoltodelvenerdi
21 dic 2009 - 16:36 - #4Mi pare di ricordare vagamente, che uno dei “punti deboli” degli alberi-RB era che, in alcuni casi particolari, il bilanciamento diventava molto costo (cioè molti nodi da eliminare e/o sortare).
Come hanno risolto sto problema? oppure è una cosa puramente teorica che in pratica si può ignorare?