CFS:programación de procesos completamente justa en Linux

Linux adopta un enfoque modular para la programación del procesador en el sentido de que se pueden usar diferentes algoritmos para programar diferentes tipos de procesos. Una clase de programación especifica qué política de programación se aplica a qué tipo de proceso. La programación completamente justa (CFS), que se convirtió en parte del kernel de Linux 2.6.23 en 2007, es la clase de programación para procesos normales (a diferencia de los de tiempo real) y, por lo tanto, se denomina SCHED_NORMAL .

CFS está diseñado para las aplicaciones interactivas típicas de un entorno de escritorio, pero se puede configurar como SCHED_BATCH para favorecer las cargas de trabajo por lotes comunes, por ejemplo, en un servidor web de gran volumen. En cualquier caso, CFS rompe radicalmente con lo que podría llamarse "programación preventiva clásica". Además, la afirmación de "totalmente justo" debe verse con un ojo técnico; de lo contrario, el reclamo podría parecer un alarde vacío.

Profundicemos en los detalles de lo que diferencia a CFS de, de hecho, por encima de otros programadores de procesos. Comencemos con una revisión rápida de algunos términos técnicos básicos.

Algunos conceptos básicos

Linux hereda la vista Unix de un proceso como un programa en ejecución. Como tal, un proceso debe competir con otros procesos por los recursos del sistema compartido:memoria para contener instrucciones y datos, al menos un procesador para ejecutar instrucciones y dispositivos de E/S para interactuar con el mundo exterior. La programación de procesos es la forma en que el sistema operativo (SO) asigna tareas (p. ej., calcular algunos números, copiar un archivo) a los procesadores; luego, un proceso en ejecución realiza la tarea. Un proceso tiene uno o más hilos de ejecución , que son secuencias de instrucciones a nivel de máquina. Programar un proceso es programar uno de sus subprocesos en un procesador.

La terminal de Linux

• Los 7 mejores emuladores de terminal para Linux
• 10 herramientas de línea de comandos para el análisis de datos en Linux
• Descargar ahora:hoja de referencia de SSH
• Hoja de trucos de comandos avanzados de Linux
• Tutoriales de línea de comandos de Linux

En un movimiento simplificador, Linux convierte la programación de procesos en programación de subprocesos al tratar un proceso programado como si fuera un subproceso único. Si un proceso tiene subprocesos múltiples con N subprocesos, luego N Se requerirían acciones de programación para cubrir los subprocesos. Los subprocesos dentro de un proceso de subprocesos múltiples permanecen relacionados en el sentido de que comparten recursos, como el espacio de direcciones de memoria. Los subprocesos de Linux a veces se describen como procesos ligeros, con el ligero subrayando el intercambio de recursos entre los subprocesos dentro de un proceso.

Aunque un proceso puede estar en varios estados, dos son de particular interés en la programación. Un bloqueado El proceso está esperando la finalización de algún evento, como un evento de E/S. El proceso puede reanudar la ejecución solo después de que se complete el evento. Un ejecutable el proceso es uno que no está bloqueado actualmente.

Un proceso está vinculado al procesador (también conocido como limitado a computación ) si consume principalmente procesador en lugar de recursos de E/S, y limitado a E/S en caso contrario; por lo tanto, un proceso vinculado al procesador es mayormente ejecutable, mientras que un proceso vinculado a E/S está mayormente bloqueado. Como ejemplos, el procesamiento de números está limitado por el procesador y el acceso a los archivos está limitado por E/S. Aunque un proceso completo puede caracterizarse como vinculado al procesador o vinculado a la E/S, un proceso dado puede ser uno u otro durante las diferentes etapas de su ejecución. Las aplicaciones de escritorio interactivas, como los navegadores, tienden a estar vinculadas a E/S.

Un buen programador de procesos tiene que equilibrar las necesidades de las tareas vinculadas al procesador y a las E/S, especialmente en un sistema operativo como Linux que prospera en tantas plataformas de hardware:máquinas de escritorio, dispositivos integrados, dispositivos móviles, clústeres de servidores, supercomputadoras. y más.

Programación preventiva clásica versus CFS

Unix popularizó la programación preventiva clásica, que posteriormente adoptaron otros sistemas operativos, incluidos VAX/VMS, Windows NT y Linux. En el centro de este modelo de programación hay una fracción de tiempo fija , la cantidad de tiempo (por ejemplo, 50 ms) que se le permite a una tarea retener un procesador hasta que se reemplaza a favor de otra tarea. Si un proceso adelantado no ha terminado su trabajo, el proceso debe ser reprogramado. Este modelo es poderoso porque admite multitarea (simultaneidad) a través del tiempo compartido del procesador, incluso en las máquinas de antaño con una sola CPU.

El modelo clásico generalmente incluye múltiples colas de programación, una por prioridad de proceso:cada proceso en una cola de mayor prioridad se programa antes que cualquier proceso en una cola de menor prioridad. Como ejemplo, VAX/VMS utiliza 32 colas de prioridad para la programación.

CFS prescinde de intervalos de tiempo fijos y prioridades explícitas. La cantidad de tiempo para una tarea determinada en un procesador se calcula dinámicamente a medida que cambia el contexto de programación durante la vida útil del sistema. Aquí hay un boceto de las ideas motivadoras y los detalles técnicos:

• Imagine un procesador, P, idealizado porque puede ejecutar múltiples tareas simultáneamente . Por ejemplo, las tareas T1 y T2 pueden ejecutarse en P al mismo tiempo, y cada una recibe el 50 % del poder de procesamiento mágico de P. Esta idealización describe la multitarea perfecta , que CFS se esfuerza por lograr en los procesadores reales en lugar de los idealizados. CFS está diseñado para aproximarse a la multitarea perfecta.

• El programador de CFS tiene una latencia objetivo , que es la cantidad mínima de tiempo (idealizada para una duración infinitamente pequeña) requerida para que cada tarea ejecutable obtenga al menos un giro en el procesador. Si tal duración pudiera ser infinitamente pequeña, entonces cada tarea ejecutable habría tenido un turno en el procesador durante cualquier período de tiempo dado, por pequeño que fuera (por ejemplo, 10 ms, 5 ns, etc.). Por supuesto, una duración infinitamente pequeña idealizada debe aproximarse en el mundo real, y la aproximación predeterminada es de 20 ms. Cada tarea ejecutable obtiene un 1/N porción de la latencia de destino, donde N es el número de tareas. Por ejemplo, si la latencia objetivo es de 20 ms y hay cuatro tareas en competencia, cada tarea obtiene un intervalo de tiempo de 5 ms. Por cierto, si solo hay una tarea durante un evento de programación, esta tarea afortunada obtiene toda la latencia de destino como su porción. La feria en CFS pasa a primer plano en el 1/N rebanada dada a cada tarea que compite por un procesador.

• El 1/N el segmento es, de hecho, un segmento de tiempo, pero no uno fijo porque dicho segmento depende de N , el número de tareas que compiten actualmente por el procesador. El sistema cambia con el tiempo. Algunos procesos terminan y se generan otros nuevos; los procesos ejecutables se bloquean y los procesos bloqueados se vuelven ejecutables. El valor de N es dinámico y, por lo tanto, también lo es el 1/N intervalo de tiempo calculado para cada tarea ejecutable que compite por un procesador. La tradicional bonita El valor se utiliza para ponderar el 1/N segmento:un agradable de baja prioridad valor significa que solo una fracción del 1/N rebanada se le da a una tarea, mientras que una prioridad alta agradable valor significa que una fracción proporcionalmente mayor del 1/N slice se le da a una tarea. En resumen, bien los valores no determinan el corte, solo modifican el 1/N rebanada que representa la equidad entre las tareas contendientes.

• El sistema operativo incurre en sobrecarga cada vez que un cambio de contexto ocurre; es decir, cuando un proceso se adelanta a favor de otro. Para evitar que esta sobrecarga se vuelva indebidamente grande, hay una cantidad mínima de tiempo (con una configuración típica de 1 ms a 4 ms) que cualquier proceso programado debe ejecutarse antes de ser reemplazado. Este mínimo se conoce como granularidad mínima . Si muchas tareas (por ejemplo, 20) compiten por el procesador, entonces la granularidad mínima (suponiendo 4 ms) podría ser más que el 1/N rebanada (en este caso, 1 ms). Si la granularidad mínima resulta ser mayor que 1/N slice, el sistema está sobrecargado porque hay demasiadas tareas compitiendo por el procesador, y la equidad desaparece.

• ¿Cuándo ocurre la preferencia? CFS intenta minimizar los cambios de contexto, dada su sobrecarga:el tiempo dedicado a un cambio de contexto es tiempo no disponible para otras tareas. En consecuencia, una vez que una tarea obtiene el procesador, se ejecuta durante todo su ponderado 1/N rebanada antes de ser reemplazada a favor de alguna otra tarea. Supongamos que la tarea T1 se ha ejecutado para su ponderación 1/N slice, y la tarea ejecutable T2 actualmente tiene el tiempo de ejecución virtual más bajo (vruntime) entre las tareas que compiten por el procesador. El vruntime registra, en nanosegundos, cuánto tiempo se ha ejecutado una tarea en el procesador. En este caso, T1 se adelantaría a favor de T2.

• El planificador realiza un seguimiento del tiempo de ejecución de todas las tareas, ejecutables y bloqueadas. Cuanto menor es el tiempo de ejecución de una tarea, más merece la tarea por tiempo en el procesador. En consecuencia, CFS mueve las tareas de bajo tiempo de ejecución al frente de la línea de programación. Los detalles están disponibles porque la línea se implementa como un árbol, no como una lista.

• ¿Con qué frecuencia debe reprogramar el programador de CFS? Hay una forma sencilla de determinar el período de programación . Suponga que la latencia objetivo (TL) es de 20 ms y la granularidad mínima (MG) es de 4 ms:

  TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

  En este caso, cinco o menos tareas permitirían que cada tarea encienda el procesador durante la latencia de destino. Por ejemplo, si el número de tarea es cinco, cada tarea ejecutable tiene un 1/N rebanada de 4ms, que pasa a ser igual a la granularidad mínima; si el número de tarea es tres, cada tarea obtiene un 1/N rebanada de casi 7ms. En cualquier caso, el programador reprogramaría en 20 ms, la duración de la latencia objetivo.

  El problema ocurre si la cantidad de tareas (por ejemplo, 10) excede TL/MG porque ahora cada tarea debe obtener el tiempo mínimo de 4 ms en lugar del 1/N calculado. rebanada, que es de 2 ms. En este caso, el planificador reprogramaría en 40 ms:

  (number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms

Los programadores de Linux anteriores a CFS utilizan heurística para promover el tratamiento justo de las tareas interactivas con respecto a la programación. CFS adopta un enfoque bastante diferente al permitir que los hechos de vruntime hablen principalmente por sí mismos, lo que respalda la equidad del durmiente . Una tarea interactiva, por su propia naturaleza, tiende a dormir mucho en el sentido de que espera las entradas del usuario y, por lo tanto, se vincula a E/S; por lo tanto, dicha tarea tiende a tener un tiempo de ejecución relativamente bajo, lo que tiende a mover la tarea hacia el frente de la línea de programación.

Características especiales

CFS admite el multiprocesamiento simétrico (SMP) en el que cualquier proceso (ya sea kernel o usuario) puede ejecutarse en cualquier procesador. Sin embargo, dominios de programación configurables se puede utilizar para agrupar procesadores para el equilibrio de carga o incluso la segregación. Si varios procesadores comparten la misma política de programación, el equilibrio de carga entre ellos es una opción; si un procesador en particular tiene una política de programación diferente de los demás, entonces este procesador estaría segregado de los demás con respecto a la programación.

Grupos de programación configurables son otra característica de CFS. Como ejemplo, considere el servidor web Nginx que se ejecuta en mi máquina de escritorio. Al inicio, este servidor tiene un proceso maestro y cuatro procesos de trabajo, que actúan como controladores de solicitudes HTTP. Para cualquier solicitud HTTP, el trabajador particular que maneja la solicitud es irrelevante; lo único que importa es que la solicitud se maneje de manera oportuna, por lo que los cuatro trabajadores juntos proporcionan un grupo del que extraer un controlador de tareas a medida que llegan las solicitudes. Por lo tanto, parece justo tratar a los cuatro trabajadores de Nginx como un grupo en lugar de como individuos con fines de programación, y un grupo de programación se puede utilizar para hacer precisamente eso. Los cuatro trabajadores de Nginx podrían configurarse para tener un solo tiempo de ejecución entre ellos en lugar de tiempos de ejecución individuales. La configuración se realiza a la manera tradicional de Linux, a través de archivos. Para vruntime-sharing, un archivo llamado cpu .acciones , con los detalles proporcionados a través de comandos de shell familiares, se crearía.

Como se señaló anteriormente, Linux admite clases de programación para que las diferentes políticas de programación, junto con sus algoritmos de implementación, puedan coexistir en una misma plataforma. Una clase de programación se implementa como un módulo de código en C. CFS, la clase de programación descrita hasta ahora, es SCHED_NORMAL . También hay clases de programación específicas para tareas en tiempo real, SCHED_FIFO (primero en entrar, primero en salir) y SCHED_RR (redondo). En SCHED_FIFO , las tareas se ejecutan hasta su finalización; en SCHED_RR , las tareas se ejecutan hasta que agotan un intervalo de tiempo fijo y se reemplazan.

Implementación de CFS

CFS requiere estructuras de datos eficientes para realizar un seguimiento de la información de las tareas y un código de alto rendimiento para generar las programaciones. Comencemos con un término central en la programación, la ejecución . Esta es una estructura de datos que representa una línea de tiempo para tareas programadas. A pesar del nombre, no es necesario implementar la cola de ejecución de la forma tradicional, como una lista FIFO. CFS rompe con la tradición al utilizar un árbol rojo-negro ordenado por tiempo como cola de ejecución. La estructura de datos es adecuada para el trabajo porque es un árbol de búsqueda binario autoequilibrado, con inserción eficiente y eliminar operaciones que se ejecutan en O(log N) hora, donde N es el número de nodos en el árbol. Además, un árbol es una excelente estructura de datos para organizar entidades en una jerarquía basada en una propiedad particular, en este caso, un tiempo de ejecución virtual.

En CFS, los nodos internos del árbol representan las tareas que se programarán y el árbol como un todo, como cualquier cola de ejecución, representa una línea de tiempo para la ejecución de tareas. Los árboles rojo-negro se utilizan ampliamente más allá de la programación; por ejemplo, Java usa esta estructura de datos para implementar su TreeMap .

Bajo CFS, cada procesador tiene una cola de ejecución específica de tareas y ninguna tarea ocurre al mismo tiempo en más de una cola de ejecución. Cada cola de ejecución es un árbol rojo-negro. Los nodos internos del árbol representan tareas o grupos de tareas, y estos nodos están indexados por sus valores de tiempo de ejecución de modo que (en el árbol como un todo o en cualquier subárbol) los nodos internos de la izquierda tienen valores de tiempo de ejecución más bajos que los de la derecha:

    25     ## 25 is a task vruntime

    /\

  17  29   ## 17 roots the left subtree, 29 the right one

  /\  ...

 5  19     ## and so on

...  \

     nil   ## leaf nodes are nil

En resumen, las tareas con el menor tiempo de ejecución (y, por lo tanto, la mayor necesidad de un procesador) residen en algún lugar del subárbol izquierdo; las tareas con tiempos de ejecución relativamente altos se congregan en el subárbol derecho. Una tarea adelantada iría al subárbol derecho, dando así a otras tareas la oportunidad de moverse hacia la izquierda en el árbol. Una tarea con el tiempo de ejecución más pequeño termina en el nodo más a la izquierda (interno) del árbol, que es, por lo tanto, el frente de la cola de ejecución.

El programador de CFS tiene una instancia, el C task_struct , para realizar un seguimiento de la información detallada sobre cada tarea que se programará. Esta estructura incorpora una sched_entity estructura, que a su vez tiene información específica de programación, en particular, el tiempo de ejecución por tarea o grupo de tareas:

struct task_struct {       /** info on a task **/

  ...

  struct sched_entity se;  /** vruntime, etc. **/

  ...

};

El árbol rojo-negro se implementa en la forma familiar de C, con una prima en los indicadores de eficiencia. Un cfs_rq instancia de estructura incrusta un rb_root campo llamado tasks_timeline , que apunta a la raíz de un árbol rojo-negro. Cada uno de los nodos internos del árbol tiene punteros al padre ya los dos nodos hijos; los nodos hoja tienen nil como su valor.

CFS ilustra cómo una idea sencilla (dar a cada tarea una parte justa de los recursos del procesador) se puede implementar de una manera sencilla pero muy eficiente. Vale la pena repetir que CFS logra una programación justa y eficiente sin artefactos tradicionales como intervalos de tiempo fijos y prioridades de tareas explícitas. La búsqueda de programadores aún mejores continúa, por supuesto; por el momento, sin embargo, CFS es tan bueno como es posible para la programación de procesadores de propósito general.