Definición
El planificador de Linux llamado Completely Fair implementa el que se denomina fair-share scheduling de una forma altamente eficiente y de forma escalable.
Para lograr la meta de ser eficiente, CFS, intenta gastar muy poco tiempo tomando decisiones de planificación, de dos formas, por su diseño y debido al uso inteligente de estructuras de datos para esa tarea
Modo de operación básico
Mientras que los planificadores tradicionales se basan alrededor del concepto de un time-slice fijo, CSF opera de forma un poco diferente. Su objetivo es sencillo, dividir de forma justa la Procesador entre todos los procesos que están compitiendo por ella.
Logra dividir la CPU mediante una simple técnica para contar llamada virtual runtime. A medida que un proceso se ejecuta este acumula vruntime. En el caso más básico cada vruntime de un proceso se incrementa con la misma tasa, en proporción al tiempo físico. Cuando una decisión de planificación ocurre, CFS seleccionará el proceso con menos vruntime para que sea el próximo en ser ejecutado.
Decisión de parar la ejecución
El punto clave aquí es que hay un punto de tensión entre performance y equitatividad
- Si el CFS switchea de proceso en tiempos muy pequeños estará garantizado que todos los procesos se ejecuten a costa de perdida de performance. Esto es por demasiados context switch
- Si el CFS switchea pocas veces, la performance del scheduler es buena pero el costo está puesto del lado de la equitatividad (fairness)
La forma en que CFS maneja esta tensión es mediante varios parámetros de control
sched_latency- Este valor determina por cuanto tiempo un proceso tiene que ejecutarse antes de considerar su switcheo. El valor típico de este parámetro es de
, CFS divide este valor por el número de procesos ( ) ejecutándose en la Procesador para determinar el time-slice de un proceso, y entonces se asegura que por ese periodo de tiempo, CFS va a ser completamente justo.
- Este valor determina por cuanto tiempo un proceso tiene que ejecutarse antes de considerar su switcheo. El valor típico de este parámetro es de
min_granularity- Para lidiar con los multiples context switch que puede producir un
sched_latencymuy chico, se introduce otro parámetro llamadomin_grunularity, que normalmente se setea con el valor de. Entonces CFS nunca sedería el time-slice de un proceso por debajo de ese número, por ende con esto se asegura que no haya overhead por el context switch
- Para lidiar con los multiples context switch que puede producir un
CFS utiliza una interrupción periódica de tiempo, lo que significa que sólo puede tomar decisiones en periodos de tiempos fijos (
Weighting
CFS tiene control sobre las prioridades de los procesos, de forma tal que los usuarios y administradores puedan asignar más Procesador a un determinado proceso. Esto se hace con un mecanismo clásico de UNIX llamado nivel de proceso nice, este valor va de
Estos pesos permite calcular efectivamente el time slice para cada proceso pero teniendo en cuenta las distintas prioridades para cada proceso
Con esto se debe generalizar el calculo de vruntime
Este se calcula tomando el tiempo de ejecución real que el
Un aspecto inteligente de la construcción de la tabla de pesos anterior es que la tabla conserva las proporciones de ratio de la Procesador cuando la diferencia en valores de nice es constante
Utiliza árboles rojo y negro
Uno de los focos de eficiencia del CFS está en la implementación de las políticas anteriores. Pero también en una buena selección del tipo de dato cuando el planificador debe encontrar el próximo job a ser ejecutado
- Las listas no escalan bien
- Los árboles sí, en este caso los árboles Rojo-Negro
Para tener una idea cerrada de donde aparece el árbol rojo y negro dentro del kernel de Linux a partir de la versión del kernel 2.6.0
El algoritmo
Cuando el scheduler es invocado para correr un nuevo proceso, la forma en que el scheduler actúa es la siguiente:
- El nodo más a la izquierda del árbol de planificación es elegido (ya que tiene el tiempo de ejecución más bajo), y es enviado a ejecutarse
- Si el proceso simplemente completa su ejecución, este es eliminado del sistema y del árbol de planificación
- Si el proceso alcanza su máximo tiempo de ejecución o de otra forma se para la ejecución del mismo voluntariamente o vía una interrupción, este es reinsertado en el árbol de planificación basado en su nuevo tiempo de ejecución (vruntime)
- El nuevo nodo que se encuentra más a la izquierda del árbol será ahora el seleccionado, repitiéndose así la iteración