Completely Fair Scheduler ( CFS ) es un programador de procesos que se fusionó en la versión 2.6.23 (octubre de 2007) del kernel de Linux y es el programador predeterminado de las tareas de la clase (es decir, tareas que no tienen ejecución en tiempo real). restricciones). Maneja la asignación de recursos de CPU para ejecutar procesos y tiene como objetivo maximizar la utilización general de la CPU y al mismo tiempo maximizar el rendimiento interactivo.SCHED_NORMAL
A diferencia del programador O(1) anterior utilizado en kernels Linux 2.6 anteriores, que mantenía y cambiaba las colas de ejecución de tareas activas y vencidas, la implementación del programador CFS se basa en colas de ejecución por CPU, cuyos nodos son entidades programables ordenadas en el tiempo. que se mantienen ordenados por árboles rojo-negro . El CFS elimina la antigua noción de intervalos de tiempo fijos por prioridad y, en cambio, apunta a dar una parte justa del tiempo de CPU a las tareas (o, mejor, a entidades programables). [1] [2]
Una tarea (es decir, un sinónimo de hilo) es la entidad mínima que Linux puede programar. Sin embargo, también puede gestionar grupos de subprocesos, procesos completos de subprocesos múltiples e incluso todos los procesos de un usuario determinado. Este diseño conduce al concepto de entidades programables, donde las tareas son agrupadas y gestionadas por el planificador en su conjunto. 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.
cfs_rqCada cola de ejecución de tipo por CPU clasifica sched_entitylas estructuras ordenadas en el 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 ejecución. tiempo (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 para representar el tiempo que el proceso habría esperado ejecutar 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 planificador para ejecutar un nuevo proceso:
Si el proceso pasa gran parte de su tiempo durmiendo, entonces el valor de su tiempo invertido es bajo y automáticamente obtiene el aumento de prioridad cuando finalmente lo necesita. Por lo tanto, estas tareas no requieren menos tiempo de procesamiento que las tareas que se ejecutan constantemente.
La complejidad del algoritmo que inserta nodos en la cfs_rqcola de ejecución del programador 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 la " programación justa " llamada Fecha límite de escalera giratoria , inspiró a Ingo Molnár a desarrollar su CFS, como reemplazo del anterior programador O(1) , y le da crédito a Kolivas en su anuncio. [4] CFS es una implementación de un algoritmo de programación clásico y bien estudiado llamado cola justa ponderada . [5] Originalmente inventado para redes de paquetes , el sistema de colas justas se había aplicado anteriormente a la programación de CPU bajo el nombre de programación a pasos agigantados . CFS es la primera implementación de un programador 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 hizo que el programador fuera "más justo" para su uso en computadoras de escritorio y estaciones de trabajo. Desarrollado por Mike Galbraith utilizando ideas sugeridas por Linus Torvalds , el parche implementa una característica llamada agrupación automática que aumenta significativamente el rendimiento del escritorio interactivo. [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 de múltiples núcleos y múltiples CPU ( SMP ) cuando realizaban otras tareas. que utilizan muchos subprocesos que consumen mucha CPU en esas tareas. Una explicación simple es que, con este parche aplicado, uno aún puede ver un video, leer correos electrónicos y realizar otras actividades típicas del escritorio sin fallas ni interrupciones mientras, por ejemplo, se compila el kernel de Linux o se codifica un video.
En 2016, se parcheó el 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 primera programación de fecha límite virtual elegible (EEVDF) para reemplazar al CFS. [10] La motivación era eliminar la necesidad de parches de "latencia agradable" de CFS. [11]