Completely Fair Scheduler ( CFS ) fue un programador de procesos que se fusionó en la versión 2.6.23 (octubre de 2007) del kernel de Linux . Era el programador predeterminado de las tareas de la clase (es decir, tareas que no tienen restricciones de ejecución en tiempo real) y manejaba la asignación de recursos de la CPU para la ejecución de procesos , con el objetivo de maximizar la utilización general de la CPU y, al mismo tiempo, maximizar el rendimiento interactivo.SCHED_NORMAL
A diferencia del planificador O(1) anterior utilizado en los núcleos Linux 2.6 más antiguos, que mantenía y cambiaba las colas de ejecución de las tareas activas y vencidas, la implementación del planificador CFS se basa en colas de ejecución por CPU, cuyos nodos son entidades programables ordenadas en el tiempo que se mantienen ordenadas por árboles rojo-negro . El CFS elimina la antigua noción de porciones de tiempo fijas por prioridad y, en su lugar, apunta a dar una parte justa del tiempo de CPU a las tareas (o, mejor, a las entidades programables). [1] [2]
A partir de la versión 6.6 del kernel de Linux, fue reemplazado por el programador EEVDF .
Una tarea (es decir, un sinónimo de subproceso) es la entidad mínima que Linux puede programar. Sin embargo, también puede administrar grupos de subprocesos, procesos multiproceso completos e incluso todos los procesos de un usuario determinado. Este diseño conduce al concepto de entidades programables, donde las tareas son agrupadas y administradas por el programador como un todo. Para que este diseño funcione, cada task_structdescriptor de tarea incorpora un campo de tipo sched_entityque representa el conjunto de entidades al que pertenece la tarea.
Cada cola de ejecución por CPU de tipo cfs_rqordena sched_entitylas estructuras de manera ordenada en función del tiempo en un árbol rojo-negro (o 'rbtree' en la jerga de Linux), donde el nodo más a la izquierda está ocupado por la entidad que ha recibido la menor porción de tiempo de ejecución (que se guarda en el vruntimecampo de la entidad). Los nodos están indexados por el " tiempo de ejecución " del procesador en nanosegundos. [3]
También se calcula un " tiempo máximo de ejecución " para cada proceso, que representa el tiempo que se habría esperado que el proceso se ejecutara en un "procesador ideal". Este es el tiempo que el proceso ha estado esperando para ejecutarse, dividido por el número total de procesos.
Cuando se invoca al programador para ejecutar un nuevo proceso:
Si el proceso pasa mucho tiempo en reposo, el valor de tiempo empleado es bajo y automáticamente obtiene el aumento de prioridad cuando finalmente lo necesita. Por lo tanto, dichas tareas no obtienen menos tiempo de procesador que las tareas que se ejecutan constantemente.
La complejidad del algoritmo que inserta nodos en la cfs_rqcola de ejecución del planificador CFS es O ( log N ), donde N es el número total de entidades. La elección de la siguiente entidad a ejecutar se realiza en tiempo constante porque el nodo más a la izquierda siempre está almacenado en caché.
El trabajo de Con Kolivas con la programación, más significativamente su implementación de " programación justa " llamada Rotating Staircase Deadline , inspiró a Ingo Molnár a desarrollar su CFS, como reemplazo del planificador O(1) anterior , dando crédito a Kolivas en su anuncio. [4] CFS es una implementación de un algoritmo de programación clásico bien estudiado llamado cola justa ponderada . [5] Originalmente inventado para redes de paquetes , la cola justa se había aplicado previamente a la programación de CPU bajo el nombre de programación de pasos . CFS es la primera implementación de un planificador de procesos de cola justa ampliamente utilizado en un sistema operativo de propósito general. [5]
El kernel de Linux recibió un parche para CFS en noviembre de 2010 para el kernel 2.6.38 que ha hecho que el programador sea "más justo" para su uso en computadoras de escritorio y estaciones de trabajo. Desarrollado por Mike Galbraith usando ideas sugeridas por Linus Torvalds , el parche implementa una característica llamada agrupamiento automático que mejora significativamente el rendimiento interactivo del escritorio. [6] El algoritmo coloca los procesos principales en el mismo grupo de tareas que los procesos secundarios. [7] (Los grupos de tareas están vinculados a sesiones creadas a través de la llamada al sistema setsid(). [8] ) Esto resolvió el problema de los tiempos de respuesta interactivos lentos en sistemas multinúcleo y multi-CPU ( SMP ) cuando realizaban otras tareas que usan muchos subprocesos intensivos de CPU en esas tareas. Una explicación simple es que, con este parche aplicado, uno puede seguir viendo un video, leer correo electrónico y realizar otras actividades típicas del escritorio sin fallas o entrecortamientos mientras, por ejemplo, compila el kernel de Linux o codifica un video.
En 2016, se aplicó un parche al programador de Linux para mejorar el rendimiento multinúcleo, según las sugerencias descritas en el documento "El programador de Linux: una década de núcleos desperdiciados". [9]
En 2023, se estaba preparando un nuevo programador basado en la programación de fecha límite virtual más temprana elegible (EEVDF) para reemplazar a CFS. [10] La motivación era eliminar la necesidad de parches de "latencia agradable" de CFS. [11]