El largo camino para implementar la “preempción perezosa” en el planificador de CPU de Linux

• El kernel de Linux ha mantenido varios modos de preempción como compromiso entre rendimiento y tiempo de respuesta, y con el nuevo conjunto de parches de Peter Zijlstra volvió a tomar fuerza la discusión sobre la preempción perezosa (PREEMPT_LAZY)
• Los modos existentes PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL y PREEMPT_RT difieren en cuánto permiten la preempción; cuanto más frecuente es, mejor puede ser la capacidad de respuesta, pero mayor es el costo para el rendimiento y la contención de locks
• PREEMPT_LAZY usa el flag TIF_NEED_RESCHED_LAZY para indicar “se necesita replanificar, pero no de inmediato”, y retrasa la mayoría de las preempciones hasta el tick del temporizador
• A largo plazo, la idea es reducir los modos de preempción no en tiempo real a PREEMPT_LAZY y PREEMPT_FULL, y eliminar en gran medida las llamadas a cond_resched() dispersas por el kernel
• El conjunto actual de parches todavía necesita más estabilización, revisión de puntos de llamada y pruebas de rendimiento; en las pruebas iniciales, el rendimiento de PREEMPT_LAZY quedó ligeramente por debajo de PREEMPT_VOLUNTARY

---

Modos de preempción existentes en el kernel de Linux

• El kernel actual ofrece varios modos de preempción que controlan cuándo una tarea en ejecución puede ser interrumpida por otra
  • PREEMPT_NONE: el modo más simple, que solo permite preempción cuando la tarea en ejecución agotó su time slice
  • PREEMPT_VOLUNTARY: un modo que agrega muchos puntos dentro del kernel donde se puede preemptar si hace falta
  • PREEMPT_FULL: un modo que permite preempción en casi todos los puntos, excepto en secciones donde el kernel la bloquea, como al mantener un spinlock
  • PREEMPT_RT: un modo que prioriza la preempción por encima de casi todo y permite preempción incluso en la mayor parte del código que mantiene spinlocks
• Un nivel de preempción más alto permite reaccionar más rápido a eventos como mover el mouse o una señal inminente de anomalía en un reactor nuclear
• Pero si la preempción se vuelve demasiado frecuente, puede bajar el rendimiento total de trabajos intensivos de CPU y aumentar la contención de locks
• Muchas distribuciones compilan el kernel con el pseudomodo PREEMPT_DYNAMIC
  • En el arranque se puede elegir uno de los tres modos no RT anteriores
  • El valor predeterminado es PREEMPT_VOLUNTARY
  • En sistemas con debugfs montado, el modo actual puede verse en /sys/kernel/debug/sched/preempt

Por qué hacía falta cond_resched()

• PREEMPT_NONE y PREEMPT_VOLUNTARY no permiten preempción arbitraria durante la ejecución del código del kernel
• Si dentro del kernel se encadenan tareas largas, incluso en sistemas donde la latencia mínima no es la prioridad absoluta puede aparecer latencia excesiva
• Para evitarlo, se agregaron llamadas a cond_resched() en distintos bucles de larga duración
  • Cada llamada es un punto adicional de preempción voluntaria
  • También funciona en modo PREEMPT_NONE
  • Hay cientos de estas llamadas dentro del kernel
• Este enfoque es una heurística que solo funciona en los lugares donde los desarrolladores la insertaron
  • Puede haber llamadas innecesarias
  • También puede faltar la llamada en lugares donde sí hace falta
  • La lógica para decidir sobre planificación termina dispersa por todo el código del kernel

Funcionamiento central de la preempción perezosa

• El kernel observa varias variables al decidir si la tarea actual puede ser preemptada
• Entre ellas, TIF_NEED_RESCHED es un flag que indica que una tarea de mayor prioridad está esperando acceso a la CPU
  • Si una tarea de mayor prioridad despierta, este flag puede establecerse en la tarea que está corriendo
  • Si este flag no está presente, el kernel no necesita preemptar la tarea actual
• El kernel puede revisar TIF_NEED_RESCHED en varios puntos para preemptar la tarea actual
  • En el tick del temporizador del planificador
  • Al volver al espacio de usuario después de una llamada al sistema
  • Al finalizar un handler de interrupción
  • En llamadas a cond_resched()
• El parche de preempción perezosa agrega un nuevo flag: TIF_NEED_RESCHED_LAZY
  • Significa que hace falta replanificar, pero no necesariamente ejecutar el cambio de inmediato
  • En modo PREEMPT_LAZY, la mayoría de los eventos establecen este nuevo flag en lugar de TIF_NEED_RESCHED
• En los puntos donde el kernel vuelve al espacio de usuario, si cualquiera de los dos flags está establecido, se termina llamando al planificador
• En los puntos de preempción voluntaria y en la ruta de retorno de interrupciones solo se revisa TIF_NEED_RESCHED

El compromiso que plantea PREEMPT_LAZY

• En PREEMPT_LAZY, la mayoría de los eventos dentro del kernel no preemptan de inmediato la tarea actual
• En cambio, el handler del tick del temporizador revisa si TIF_NEED_RESCHED_LAZY está establecido
  • Si lo está, también establece TIF_NEED_RESCHED
  • Como resultado, la tarea en ejecución puede ser preemptada
• Por lo general, una tarea sigue ejecutándose durante un tiempo cercano a su time slice, a menos que ceda voluntariamente la CPU
  • Se espera que este comportamiento lleve a buen rendimiento
• Con este cambio, PREEMPT_LAZY también puede ejecutarse, como PREEMPT_FULL, con la preempción del kernel activa casi siempre
  • Puede haber preempción en cualquier momento si el contador de preempción lo permite
  • Si no hay otras condiciones que la bloqueen, también puede preemptarse código del kernel de larga duración
• Cuando de verdad hace falta preempción inmediata, no se retrasa
  • Por ejemplo, si como resultado del manejo de una interrupción una tarea en tiempo real pasa a estar lista para ejecutarse, se establece TIF_NEED_RESCHED
  • En ese caso, la preempción ocurre casi de inmediato, sin esperar el tick del temporizador
• Si solo está establecido TIF_NEED_RESCHED_LAZY, la preempción no ocurre
  • Por eso, un kernel PREEMPT_LAZY tiene muchas menos probabilidades de preemptar la tarea en ejecución que un kernel PREEMPT_FULL

El trabajo pendiente para eliminar cond_resched()

• El objetivo de largo plazo es reducir los modos de preempción no RT a solo dos
  • PREEMPT_LAZY
  • PREEMPT_FULL
• PREEMPT_LAZY ocupará el lugar intermedio entre PREEMPT_NONE y PREEMPT_VOLUNTARY, y reemplazará a ambos
• Si la preempción pasa a ser posible casi en cualquier parte, disminuye la necesidad de agregar puntos específicos de preempción voluntaria
• Por ahora, las llamadas a cond_resched() siguen ahí
  • Son necesarias mientras existan PREEMPT_NONE y PREEMPT_VOLUNTARY
  • También ayudan a evitar problemas durante la estabilización de la preempción perezosa
• En el conjunto actual de parches, cond_resched() solo revisa TIF_NEED_RESCHED
  • Por eso, en PREEMPT_VOLUNTARY o PREEMPT_NONE, muchas situaciones que antes habrían causado preempción inmediata podrían retrasarse
• Steve Rostedt preguntó si, especialmente en PREEMPT_VOLUNTARY, mantener el significado anterior de cond_resched() podría facilitar la transición
• Thomas Gleixner considera correcta la decisión de revisar solo TIF_NEED_RESCHED
  • Porque obliga a revisar todas las llamadas a cond_resched()
  • Las llamadas que no necesitan revisar el bit lazy podrán eliminarse al aplicar PREEMPT_LAZY
  • Las llamadas que sí necesiten revisar el bit lazy deberán permanecer
• Gleixner estima que menos del 5% de las llamadas a cond_resched() necesitarán revisar TIF_NEED_RESCHED_LAZY
• Antes de completar la transición, habrá que revisar cientos de llamadas a cond_resched() y eliminar la mayoría
• Un conjunto de parches aparte de Ankur Arora aborda algunos de esos detalles relacionados
• También harán falta pruebas de rendimiento amplias
  • En pruebas iniciales de Mike Galbraith, el rendimiento de la preempción perezosa quedó ligeramente por debajo de PREEMPT_VOLUNTARY

Objetivo final

• Como resultado del trabajo en preempción perezosa, el kernel podría volverse un poco más pequeño y simple
• La meta es un kernel que ofrezca latencias predecibles sin esparcir llamadas relacionadas con el planificador por todo el código
• El enfoque actual parece una mejor solución, pero todavía hará falta tiempo para llegar a ese punto

[GN⁺]

Opiniones en Hacker News

• Se ve prometedor. Como EEVDF, va en la dirección de simplificar y mejorar el estado actual, así que difícilmente podría ser mejor.

• Me pregunto por qué el nivel de preempción no es un modo global, sino una propiedad de ciertos eventos. Algunos eventos deberían procesarse con menor latencia que otros.

  • Para evaluar la prioridad de un evento, primero se necesita tiempo de CPU. Esa evaluación solo es posible después de interrumpir el proceso que se está ejecutando en la CPU actual.
    Por lo tanto, incluso la prioridad máxima que puede tener un evento queda limitada por lo corta que pueda ser la porción de tiempo que recibe un programa antes de pasar por un cambio de contexto. Para responder de forma confiable y con baja latencia a cualquier tipo de evento, todos los programas intensivos en CPU tendrían que pagar siempre el costo de rendimiento, por más raro que sea ese evento.
  • Aquí hay dos conceptos que son fáciles de confundir. Uno es el momento en que un proceso puede ser preemptado, y el otro es si efectivamente será preemptado.
    Los puntos potenciales de preempción son una propiedad del scheduler, y eso es lo que aquí se discute como modo global. Si hay más puntos de preempción, naturalmente aumenta la posibilidad de que un proceso sea preemptado en un momento inconveniente, pero al mismo tiempo también aumentan las oportunidades de reflejar correctamente las prioridades. El nivel de preempción al que se refiere la pregunta, es decir, la prioridad que da el scheduler, sí es una propiedad del proceso y también puede configurarse. El scheduler predeterminado de Linux también les da porciones de tiempo más grandes a los procesos con prioridad e intenta preemptar menos a otros procesos.
  • PREEMPT_VOLUNTARY, explicado en el artículo, en cierta medida fue un intento en esa dirección, y ahora puede verse como algo que se está retirando.
  • Este parche cumple en cierta medida ese papel. Según https://lwn.net/ml/all/[e-mail]...:
    SCHED_IDLE, SCHED_BATCH y SCHED_NORMAL/OTHER usan preempción diferida, mientras que FIFO, RR y DEADLINE usan el comportamiento Full existente.
  • Un sistema así probablemente genere disputas entre programas que reclaman prioridad diciendo que ellos son importantes. En la práctica, es muy probable que las grandes empresas lo aprovechen para una “mejor” experiencia de usuario.
    Por eso es importante minimizar la cantidad de aplicaciones en ejecución o controlar manualmente esos momentos breves que experimenta la mayoría de los usuarios. Incluso las tareas intensivas en CPU a veces tienen más probabilidades de ser mal código que un uso realmente eficiente de los recursos. En los juegos hay que priorizar el rendimiento, pero se necesita un equilibrio delicado para no hacer que el sistema se detenga al hacer multitarea. De todos modos, esto está pensado principalmente para tareas inactivas, así que no parece haber mucha necesidad de automatizarlo más allá de ofrecer un comando simple para que el usuario pueda alternar varias acciones desde un script.

• Dice que “el kernel actual tiene cuatro modos que controlan cuándo una tarea puede ser preemptada a favor de otra”, y me pregunto si eso se refiere a tareas del kernel o si también incluye tareas de usuario.

  • Se refiere al código del kernel. El código en espacio de usuario siempre puede ser preemptado.

• No encontré cifras en el hilo enlazado donde se subió el parche. Me da curiosidad; parecería que ya debería haber al menos algunos benchmarks iniciales que muestren el potencial práctico de este cambio.

  • Está en el penúltimo párrafo del artículo.
    Dice que se necesitan pruebas de rendimiento amplias, que Mike Galbraith empezó el trabajo inicial, y que los resultados mostraron que el throughput de la preempción diferida es ligeramente menor que el de PREEMPT_VOLUNTARY.
  • Me pregunto cómo habría que benchmarkear algo así. ¿Sería ejecutando varios procesos al mismo tiempo y ordenándolos por tiempo total de ejecución, o habría que medir la latencia de cada proceso individual?

• Me pregunto qué tan fuertemente está acoplado el scheduler con el resto del código del kernel.
  Por ejemplo, si quisiera simplificar drásticamente el scheduler para una aplicación de cómputo científico que no se preocupa en absoluto por la preempción, ¿sería posible hacerlo de una forma limpia y modular? ¿Habría beneficios reales?

  • Si quieres ejecutar un conjunto de procesos reduciendo la preempción tanto como sea posible, por ejemplo en un entorno HPC, la opción más fuerte es configurar algunos núcleos como CPU aisladas, reiniciar y luego poner las tareas directamente ahí con taskset.
    El problema es que entonces realmente tienes que asignar manualmente los trabajos a las CPU, y también es fácil terminar con todos los trabajos en la CPU equivocada. La forma estándar es configurar máscaras de interrupción para que las interrupciones no vayan a las CPU de “trabajo”, y usar cpuset para que solo ciertos cgroups se ejecuten en el cpuset dado.
  • En un sistema limpio, con casi ningún daemon, si ajustas la aplicación para que tenga un hilo del sistema operativo por cada hilo de CPU y aplicas afinidad de CPU para que no se mueva, puedes llegar como al 95%.
    Como la lista de ejecución se vuelve muy corta, lo que haga el scheduler tendrá un impacto bastante pequeño. Si la aplicación no hace mucha E/S, tampoco habrá muchas interrupciones. Si puedes usar un kernel tickless —no sé si hoy sigue siendo una opción aparte o si ya es el valor predeterminado—, puede que durante largos periodos casi no haya interrupciones.
  • La última vez que lo vi, estaba sorprendentemente bien separado.
    Pero la razón para simplificarlo mucho sería evitar bugs, no obtener mucho rendimiento frente a un scheduler predeterminado bien configurado. Hay muchas opciones de configuración, pero tampoco había muchos bugs en esa parte. Si lo simplificas de forma ingenua, en la mayoría de los casos perderás rendimiento en lugar de ganarlo. Si corres un sistema no interactivo, el cambio más fácil es aumentar la cuota de tiempo de los procesos.
  • Yo simplemente usaría RT Linux. Tiene su propio scheduler básico, y el scheduler del kernel se ejecuta como tarea inactiva, mientras que las tareas en tiempo real tienen prioridad sobre todo.