Programador de cogida cerebral
La cogida Programador cerebro ( BFS ) es un planificador de procesos diseñados para el núcleo de Linux en agosto de 2009 como una alternativa a la Feria Programador completamente (SFC) y la O (1) planificador . [2] BFS fue creado por un experimentado programador de kernel, Con Kolivas . [3]
El objetivo de BFS, en comparación con otros programadores, es proporcionar un programador con un algoritmo más simple , que no requiere 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 medio, 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 mejor rendimiento en un tipo de cálculo específico específico. a costa de un peor desempeño en el caso general. [3]Se ha informado que BFS mejora la capacidad de respuesta en las computadoras de escritorio Linux con menos de 16 núcleos . [4]
Poco después de su presentación, el nuevo programador llegó a los titulares de la comunidad de Linux, apareciendo en Slashdot , con reseñas en Linux Magazine y Linux Pro Magazine . [2] [5] [6] Aunque ha habido diversas revisiones de rendimiento y capacidad de respuesta mejorados, Con Kolivas no tenía la intención de que BFS se integrara en el núcleo principal. [3]
En 2009, se introdujo BFS y originalmente había utilizado una estructura de datos de lista doblemente enlazada , [7] [8] pero la estructura de datos se trata como una cola . La inserción de tareas es O (1). [8] : En 119-120, la búsqueda de tareas para la siguiente tarea a ejecutar es O ( n ) en el peor de los casos. [8] : En 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. [8] : En 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 en 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. [8] : ln 1193-1195, 334–335 El intervalo de round robin sintonizable por el usuario ( segmento de tiempo ) es de 6 milisegundos por defecto, que fue elegido como el jitter mínimo justo por debajo de lo detectable por humanos. [8] : En 306, Kolivas afirmó que cualquier cosa por debajo de los 6 ms no tenía sentido y cualquier cosa por encima de 300 ms para el intervalo de tiempo por turnos es infructuosa en términos de rendimiento. [8] : ln 314-320 Este importante elemento sintonizable puede adaptar el programador round robin como una compensación entre rendimiento y latencia. [8]: En 229–320 Todas las tareas obtienen el mismo intervalo de tiempo con la excepción de FIFO en tiempo real, que se supone que tiene un intervalo de tiempo infinito. [8] : en 1646, 1212-1218, 4062, 3910
Kolivas explicó la razón por la que eligió ir con la lista doblemente enlazada mono-runqueue que con la multi-runqueue (round robin [9] : par. 3 ) matriz de prioridad [10] [9] por CPU que se usó en su programador RDSL era facilitar la equidad entre el escenario de CPU múltiple y eliminar la complejidad que cada cola de ejecución en un escenario de cola de ejecución múltiple tenía para mantener sus propias latencias y equidad [de tareas]. [8] : En 81-92 , afirmó que las latencias deterministas estaban garantizadas con BFS en su versión posterior de MuQSS. [11] : En 471-472 También reconoció un posible problema de contención de bloqueo (relacionado con la alteración, eliminación, creación de datos de nodo de tarea) [11] : En 126-144 con el aumento de CPU y la sobrecarga de la siguiente tarea de O (log n ) para la búsqueda de ejecución. [11] : En 472–478, MuQSS intentó resolver esos problemas.
