Brain Fuck Scheduler ( BFS ) es un programador de procesos diseñado para el núcleo Linux en agosto de 2009 basado en la programación de fecha límite virtual más temprana elegible (EEVDF), [2] como una alternativa al Completely Fair Scheduler (CFS) y al programador O(1) . [3] BFS fue creado por Con Kolivas . [4]
El objetivo de BFS, en comparación con otros planificadores, es proporcionar un planificador con un algoritmo más simple , que no requiera el ajuste de heurísticas o parámetros de ajuste para adaptar el rendimiento a un tipo específico de carga de trabajo computacional . Kolivas afirmó que estos parámetros ajustables eran difíciles de entender para el usuario promedio, especialmente en términos de interacciones de múltiples parámetros entre sí, y afirmó que el uso de dichos parámetros de ajuste a menudo podría resultar en un rendimiento mejorado en un tipo específico de cálculo objetivo, a costa de un peor rendimiento en el caso general. [4] Se ha informado que BFS mejora la capacidad de respuesta en computadoras de escritorio Linux con menos de 16 núcleos . [5]
Poco después de su introducción, el nuevo programador fue noticia dentro de la comunidad Linux, apareciendo en Slashdot , con reseñas en Linux Magazine y Linux Pro Magazine . [3] [6] [7] Aunque ha habido diversas revisiones sobre el rendimiento y la capacidad de respuesta mejorados, Con Kolivas no tenía la intención de que BFS se integrara en el núcleo principal. [4]
En 2009, se introdujo BFS y originalmente había utilizado una estructura de datos de lista doblemente enlazada , [8] [9] pero la estructura de datos se trata como una cola . La inserción de tareas es . [9] : ln 119–120 La búsqueda de tareas para la siguiente tarea a ejecutar es el peor de los casos. [9] : ln 209 Utiliza una única cola de ejecución global que utilizan todas las CPU. Las tareas con prioridades de programación más altas se ejecutan primero. [9] : ln 4146–4161 Las tareas se ordenan (o distribuyen) y se eligen según la fórmula de fecha límite virtual en todas las políticas, excepto en las clases de prioridad de tiempo real e isócrona.
El comportamiento de ejecución sigue siendo una variación ponderada del Programador Round-Robin, especialmente cuando las tareas tienen la misma prioridad por debajo de la política Isócrona. [9] : ln 1193–1195, 334–335 El intervalo round robin ajustable por el usuario ( porción de tiempo ) es de 6 milisegundos de forma predeterminada, que se eligió como el jitter mínimo justo por debajo de lo detectable por los humanos. [9] : ln 306 Kolivas afirmó que cualquier cosa por debajo de los 6 ms era inútil y cualquier cosa por encima de los 300 ms para la porción de tiempo round robin es inútil en términos de rendimiento. [9] : ln 314–320 Este importante ajuste puede adaptar el programador round robin como un compromiso entre el rendimiento y la latencia. [9] : ln 229–320 Todas las tareas obtienen la misma porción de tiempo con la excepción del FIFO en tiempo real, que se supone que tiene una porción de tiempo infinita. [9] : en 1646, 1212–1218, 4062, 3910
Kolivas explicó la razón por la que eligió la cola de ejecución única de lista doblemente enlazada en lugar de la cola de ejecución múltiple (round robin [10] : par. 3 ) con la matriz de prioridad [11] [10] por CPU que se usó en su programador RDSL para facilitar la equidad entre el escenario de múltiples CPU y eliminar la complejidad de que cada cola de ejecución en un escenario de múltiples colas de ejecución tenía que mantener sus propias latencias y equidad [de tareas]. [9] : ln 81–92 Afirmó que las latencias deterministas estaban garantizadas con BFS en su iteración posterior de MuQSS. [12] : ln 471–472 También reconoció un posible problema de contención de bloqueo (relacionado con la alteración, eliminación y creación de datos de nodos de tareas) [12] : ln 126–144 con el aumento de CPU y la sobrecarga de la siguiente tarea para la búsqueda de ejecución. [12] : En 472–478 MuQSS intentó resolver esos problemas.
Kolivas luego cambió el diseño a una lista de omisión en la versión v0.480 de BFS en 2016. [13] Esta vez esto alteró la eficiencia del programador. Señaló inserción de tareas, búsqueda de tareas; , con , para la eliminación de tareas. [13] : ln 4
La fórmula de fecha límite virtual es un tiempo límite futuro que es el intervalo de tiempo round robin escalado basado en el nivel nice desplazado por el tiempo actual (en unidades niffy o jiffies de nanosegundos , un contador de tiempo interno del núcleo). [9] : ln 4023, 4063 La fecha límite virtual solo sugiere el orden pero no garantiza que una tarea se ejecutará exactamente en el niffy programado futuro. [9] : ln 161–163
Primero se crea una tabla de búsqueda de proporciones a priori. [9] : ln 8042–8044 Se basa en una secuencia recursiva. Aumenta un 10% en cada nivel de nice. [9] : ln 161 Sigue un patrón parabólico si se grafica, y las tareas niced se distribuyen como una función cuadrada móvil de 0 a 39 (que corresponde de la prioridad nice más alta a la más baja) como el dominio y de 128 a 5089 como el rango. [9] : ln 177–179, 120, 184–185 La parte móvil proviene de la variable t en la fórmula de fecha límite virtual que Kolivas insinuó.
g(0) = 128g(i) = INT( g(i-1)*11/10 )
La función de mapeo de nice a índice f(n) de la tarea se mapea de nice −20...19 a índice 0...39 para usarse como entrada en la tabla de búsqueda de relación de prioridades. Esta función de mapeo es la macro en sched.h en el encabezado del kernel. La implementación interna del kernel difiere levemente con un rango entre 100 y 140 de prioridad estática, pero los usuarios la verán como −20...19 nice.TASK_USER_PRIO()
La fecha límite virtual se basa en esta fórmula exacta: [9] : ln 4063, 4036, 4033, 1180
T = 6N = 1<<20d(n,t) = t + g(f(n)) * T * (N/128)
Alternativamente,
donde d(n,t) es la fecha límite virtual en u64 nanosegundos enteros como una función de nice n y t que es el tiempo actual en niffies, g(i) es la búsqueda en la tabla de relación de prioridades como una función de índice, f(n) es la función de mapeo nice-a-índice de la tarea, T es el intervalo de tiempo round robin en milisegundos, N es una constante de 1 milisegundo en términos de nanosegundos como una aproximación de reducción de latencia del factor de conversión de pero Kolivas usa una constante de base 2 N con aproximadamente esa escala. [9] : ln 1173–1174 Valores más pequeños de d significan que la fecha límite virtual es anterior correspondiente a valores nice negativos. Valores más grandes de d indican que la fecha límite virtual se retrasa más tarde correspondiente a valores nice positivos. Usa esta fórmula siempre que el intervalo de tiempo expira. [9] : ln 5087
128 en base 2 corresponde a 100 en base 10 y posiblemente a un "pseudo 100". [9] : ln 3415 115 en base 2 corresponde a 90 en base 10. Kolivas usa 128 para " desplazamientos rápidos ", [9] : ln 3846, 1648, 3525 como en la división es desplazamiento a la derecha en base 2.
BFS utiliza políticas de programación para determinar qué cantidad de CPU pueden utilizar las tareas. BFS utiliza 4 niveles de programación (llamados políticas de programación o clases de programación) ordenados de mejor a peor, lo que determina cómo se seleccionan las tareas [9] : ln 4146–4161, y las que están en la parte superior se ejecutan primero.
Cada tarea tiene un valor especial llamado prioridad. En la edición v0.462 (usada en el conjunto de parches del kernel -ck 4.0), hay un total de 103 "colas de prioridad" (también conocidas como prioridad) o valores permitidos que puede tomar. No se utilizó ninguna estructura de datos especial real como cola de prioridad, sino solo la cola de ejecución de lista doblemente enlazada. El valor de prioridad más bajo significa que es más importante y se ejecuta primero.
La política de tiempo real fue diseñada para tareas en tiempo real . Esta política implica que las tareas en ejecución no pueden ser interrumpidas (es decir, precluidas) por tareas con menor prioridad o niveles de política de menor prioridad. Las clases de prioridad consideradas bajo la política de tiempo real por el programador son aquellas marcadas como SCHED_RR y SCHED_FIFO. [9] : ln 351, 1150 El programador trata el round robin en tiempo real (SCHED_RR) y el FIFO en tiempo real (SCHED_FIFO) de manera diferente. [9] : ln 3881–3934
El diseño estableció las primeras 100 colas de prioridad estáticas. [9] : ln 189
La tarea que se elegirá para su ejecución se basa en la disponibilidad de la tarea del valor más bajo de prioridad de las 100 colas y la programación FIFO. [9] : ln 4146–4161
En las bifurcaciones , la prioridad del proceso se degradará a la política normal. [9] : ln 2708
En caso de uso sin privilegios (es decir, por parte de un usuario no root) de sched_setscheduler llamado con una solicitud de clase de política en tiempo real, el programador degradará la tarea a la política isócrona. [9] : ln 350–359, 5023–5025
La política isócrona fue diseñada para un rendimiento casi en tiempo real para usuarios no root . [9] : ln 325
El diseño estableció una cola de prioridad que, de manera predeterminada, se ejecutaba como tareas en pseudotiempo real, pero que se podía ajustar como un grado de tiempo real. [9] : ln 1201, 346–348
El comportamiento de la política puede permitir que una tarea se degrade a la política normal [9] : ln 336 cuando excede un porcentaje de manejo de recursos ajustable (70% por defecto [9] : ln 343, 432 ) de 5 segundos escalado al número de CPU en línea y la resolución del temporizador más 1 tic. [9] : ln 343, 3844–3859, 1167, 338 [12] : ln 1678, 4770–4783, 734 La fórmula fue alterada en MuQSS debido al diseño de cola de ejecución múltiple. Las fórmulas exactas son:
donde T es el número total de ticks isócronos, F es la frecuencia del temporizador, n es el número de CPU en línea, R es el porcentaje de manejo de recursos ajustable no en decimal sino como un número entero. La frecuencia del temporizador está establecida en 250 de manera predeterminada y es editable en el núcleo, pero generalmente se ajusta a 100 Hz para servidores y 1000 Hz para escritorios interactivos. 250 es el valor equilibrado. Establecer R en 100 hizo que las tareas se comportaran como tiempo real y 0 hizo que no fuera pseudo-tiempo real y cualquier cosa en el medio fuera pseudo-tiempo real. [9] : ln 346–348
Se eligió la tarea que tenía una fecha límite virtual más temprana para su ejecución, pero cuando existen múltiples tareas isócronas, se programan como round robin, lo que permite que las tareas ejecuten el valor round robin ajustable (con 6 ms como valor predeterminado) una después de la otra con una probabilidad justa y equitativa sin considerar el nivel agradable. [9] : ln 334
Este comportamiento de la política isócrona es exclusivo de BFS y MuQSS y no puede implementarse en otros programadores de CPU. [9] : ln 324, 8484–8485 [12] : ln 1287–1288
La política normal fue diseñada para el uso habitual y es la política predeterminada. Las tareas recién creadas suelen marcarse como normales. [9] : ln 502
El diseño establece una cola de prioridades y las tareas se eligen para ejecutarse primero en función de la fecha límite virtual más temprana.
La prioridad inactiva fue diseñada para procesos en segundo plano, como programas distribuidos y transcodificadores, de modo que los procesos en primer plano o aquellos por encima de esta política de programación puedan ejecutarse sin interrupciones. [9] : ln 363–368
El diseño estableció una cola de prioridad y las tareas se pueden promover a la política normal automáticamente para evitar la retención indefinida de recursos . [9] : ln 368
La siguiente tarea ejecutada con prioridad inactiva con otras que residen en la misma política de prioridad se selecciona por la fecha límite virtual más temprana. [9] : ln 4160–4161
La preempción puede ocurrir cuando una tarea recién lista con una política de prioridad más alta (es decir, mayor prio) tiene una fecha límite virtual anterior a la tarea que se está ejecutando actualmente, la cual será desprogramada y puesta al final de la cola. [9] : ln 169–175 Desprogramado significa que su fecha límite virtual se actualiza. [9] : ln 165–166 El tiempo de la tarea se vuelve a llenar al quantum máximo de round robin cuando ha usado todo su tiempo. [9] : ln 4057–4062, 5856 Si el programador encontró la tarea con el mayor prio con la fecha límite virtual más temprana, se ejecutará en lugar de la tarea menos importante que se está ejecutando actualmente solo si todas las CPU lógicas (incluidos los núcleos hiperprocesados / subprocesos SMT) están ocupados. El programador retrasará la preempción tanto como sea posible si hay CPU lógicas sin usar.
Si una tarea está marcada con una política de prioridad inactiva, no puede preemitir en absoluto ni siquiera otras tareas marcadas con una política inactiva, sino que utiliza la multitarea cooperativa . [9] : ln 2341–2344
Cuando el programador descubre una tarea de activación en un sistema que no es unicore, deberá determinar en qué CPU lógica ejecutar la tarea. El programador favorece primero a la mayoría de los núcleos hiperprocesados inactivos (o subprocesos SMT inactivos ) en la misma CPU en la que se ejecutó la tarea, [9] : ln 261 luego el otro núcleo inactivo de una CPU multinúcleo, [9] : ln 262 luego las otras CPU en el mismo nodo NUMA, [9] : ln 267, 263–266, 255–258 luego todos los núcleos hiperprocesados ocupados / subprocesos SMT / CPU lógicas que se van a interrumpido en el mismo nodo NUMA , [9] : ln 265–267 luego el otro nodo NUMA (remoto) [9] : ln 268–270 y se clasifica en una lista de preferencias. [9] : ln 255–274 Este escaneo especial existe para minimizar la sobrecarga de latencia resultante de la migración de la tarea. [9] : ln 245, 268–272
El orden de preempción es similar al párrafo anterior. El orden de preempción es el núcleo hiperprocesado / unidades SMT en el mismo multinúcleo primero, luego el otro núcleo en el multinúcleo, luego la otra CPU en el mismo nodo NUMA. [9] : ln 265–267 Cuando comienza a escanear en busca de una tarea para preemptar en el otro nodo NUMA remoto, la preempción es simplemente cualquier hilo ocupado con una prioridad menor o igual o una fecha límite virtual posterior asumiendo que todas las CPU lógicas (incluidos los hilos de núcleo hiperprocesado / SMT) en la máquina están ocupados. [9] : ln 270 El programador tendrá que escanear en busca de una tarea adecuada con una política de prioridad menor o tal vez igual (con una fecha límite virtual posterior si es necesario) para preemptar y evitar CPU lógicas con una tarea con una política de prioridad más alta que no puede preemptar. La preempción local tiene un rango más alto que el escaneo de una unidad NUMA remota inactiva. [9] : ln 265–269
Cuando una tarea es interrumpida involuntariamente en el momento en que la CPU se ralentiza como resultado del escalado de frecuencia de la CPU mediado por el núcleo (también conocido como gobernador de frecuencia de la CPU), la tarea se marca especialmente como "pegajosa", excepto aquellas marcadas como política de tiempo real. [9] : ln 2085 Marcado como pegajoso indica que la tarea aún tiene tiempo sin usar y la tarea está restringida a la ejecución en la misma CPU. [9] : ln 233–243 La tarea se marcará como pegajosa siempre que el gobernador de escalado de la CPU haya escalado la CPU a una velocidad más lenta. [9] : ln 2082–2107, 8840–8848 La tarea pegajosa inactiva volverá a ejecutarse a la velocidad completa de Ghz por casualidad o se reprogramará para ejecutarse en la mejor CPU inactiva que no sea la misma CPU en la que se ejecutó la tarea. [9] : ln 2082–2086, 239–242, 2068–2079 No es deseable migrar la tarea a otros lugares, sino dejarla inactiva debido a la mayor latencia provocada por la sobrecarga al migrar la tarea a otra CPU o nodo NUMA. [9] : ln 228, 245 Esta característica persistente se eliminó en la última iteración de BFS (v0.512) correspondiente al conjunto de parches 4.8-ck1 de Kolivas y no existía en MuQSS.
Un usuario privilegiado puede cambiar la política de prioridad de un proceso con el programa schedtool [9] : ln 326, 373 o lo hace el propio programa. [9] : ln 336 La clase de prioridad se puede manipular a nivel de código con una llamada al sistema como sched_setscheduler solo disponible para root, [15] que utiliza schedtool. [16]
En un estudio contemporáneo, [5] el autor comparó el BFS con el CFS utilizando el kernel de Linux v3.6.2 y varios puntos finales basados en el rendimiento. El propósito de este estudio fue evaluar el Completely Fair Scheduler (CFS) en el kernel de Linux original y el BFS en el kernel correspondiente parcheado con el conjunto de parches ck1. Se utilizaron siete máquinas diferentes para ver si existían diferencias y hasta qué punto escalaban utilizando métricas basadas en el rendimiento. La cantidad de CPU lógicas varió de 1 a 16. Estos puntos finales nunca fueron factores en los objetivos de diseño primarios del BFS. Los resultados fueron alentadores.
Los núcleos parcheados con el conjunto de parches ck1, incluido el BFS, superaron al núcleo estándar que utiliza el CFS en casi todos los puntos de referencia basados en el rendimiento probados. [5] Se podrían realizar estudios adicionales con un conjunto de pruebas más grande, pero en función del pequeño conjunto de pruebas de 7 PC evaluado, estos aumentos en la cola de procesos, la eficiencia/velocidad son, en general, independientes del tipo de CPU (mono, dual, quad, hyperthreaded, etc.), la arquitectura de la CPU (32 bits y 64 bits) y la multiplicidad de la CPU (mono o dual socket).
Además, en varias CPU "modernas", como Intel Core 2 Duo y Core i7 , que representan estaciones de trabajo y computadoras portátiles comunes, BFS superó consistentemente a CFS en el kernel original en todos los puntos de referencia. Las ganancias de eficiencia y velocidad fueron entre pequeñas y moderadas.
BFS es el programador predeterminado para las siguientes distribuciones de Linux de escritorio:
Además, BFS se ha añadido a una rama experimental del repositorio de desarrollo de Android de Google . [21] No se incluyó en la versión Froyo después de que las pruebas a ciegas no mostraran una experiencia de usuario mejorada. [22]
BFS se ha retirado en favor de MuQSS , conocido formalmente como Multiple Queue Skiplist Scheduler , una implementación reescrita del mismo concepto. [23] [24] El autor principal abandonó [25] el trabajo en MuQSS a fines de agosto de 2021.
MuQSS utiliza una lista de omisión estática bidireccional de 8 niveles y las tareas se ordenan por prioridad estática [colas] (en referencia a la política de programación) y una fecha límite virtual. [12] : ln 519, 525, 537, 588, 608 Se eligió 8 para ajustar la matriz en la línea de caché. [12] : ln 523 Se eligió el diseño de estructura de datos doblemente enlazada para acelerar la eliminación de tareas. Eliminar una tarea toma solo O(1) con una lista de omisión doble en comparación con el diseño original de William Pugh que toma el peor caso. [12] : ln 458
La inserción de tareas es . [12] : ln 458 La siguiente tarea para la búsqueda de ejecución es , donde k es el número de CPU. [12] : ln 589–590, 603, 5125 La siguiente tarea para la ejecución es por cola de ejecución, [12] : ln 5124 pero el programador examina todas las demás colas de ejecución para mantener la equidad de tareas entre las CPU, para la latencia o el equilibrio (para maximizar el uso de la CPU y la coherencia de la memoria caché en el mismo nodo NUMA sobre aquellos que acceden a través de nodos NUMA), por lo que en última instancia . [12] : ln 591–593, 497–501, 633–656 El número máximo de tareas que puede manejar son 64k tareas por cola de ejecución por CPU. [12] : ln 521 Utiliza múltiples colas de ejecución de tareas en algunas configuraciones, una cola de ejecución por CPU, mientras que su predecesor BFS solo usaba una cola de ejecución de tareas para todas las CPU.
Las tareas se ordenan como un gradiente en la lista de omisión de manera que la prioridad de la política en tiempo real viene primero y la prioridad de la política inactiva viene al final. [12] : ln 2356–2358 La política de prioridad normal e inactiva todavía se ordena por fecha límite virtual que usa valores agradables . [12] : ln 2353 Las tareas de política en tiempo real e isócrona se ejecutan en orden FIFO ignorando los valores agradables. [12] : ln 2350–2351 Las nuevas tareas con la misma clave se colocan en orden FIFO, lo que significa que las tareas más nuevas se colocan al final de la lista (es decir, el nodo superior verticalmente), y las tareas en el nivel 0 o en la parte inferior delantera se ejecutan primero antes que las más cercanas a la parte superior verticalmente y las más alejadas del nodo principal. [12] : ln 2351–2352, 590 La clave utilizada para la ordenación insertada es la prioridad estática [12] : ln 2345, 2365 o la fecha límite virtual. [12] : ln 2363
El usuario puede elegir compartir colas de ejecución entre núcleos múltiples o tener una cola de ejecución por CPU lógica. [12] : ln 947–1006 La especulación del diseño de colas de ejecución compartidas fue reducir la latencia con una compensación de rendimiento. [12] : ln 947–1006
Un nuevo comportamiento introducido por MuQSS fue el uso del temporizador de alta resolución para una precisión inferior a milisegundos cuando se agotaban los intervalos de tiempo, lo que daba como resultado la reprogramación de tareas. [12] : ln 618–630, 3829–3851, 3854–3865, 5316
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}
