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]
Desarrollador (es) | Con Kolivas |
---|---|
Lanzamiento final | 0.512 / 3 de octubre de 2016 [1] |
Escrito en | C |
Sistema operativo | Linux |
Licencia | GNU GPL |
Sitio web | kernel |
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 introducció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]
Diseño teórico y eficiencia
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 ajuste puede adaptar el planificador de operación por turnos 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 CPU en aumento y la sobrecarga de O (log n ) siguiente tarea de búsqueda de ejecución. [11] : 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. [12] Esta vez esto alteró la eficiencia del programador. Señaló O (log n) inserción de tareas, O (1) búsqueda de tareas; O (k), con k <= 16, para la eliminación de tareas. [12] : en 4
Fecha límite virtual
La fórmula de la fecha límite virtual es una fecha límite futura que es el intervalo de tiempo de round robin escalado basado en el nivel agradable compensado por la hora actual (en unidades niffy o jiffies de nanosegundos, también conocido como un contador de tiempo interno del kernel). [8] : En 4023, 4063 La fecha límite virtual solo sugiere el orden, pero no garantiza que una tarea se ejecutará exactamente en el futuro programado niffy. [8] : en 161-163
Primero se crea una tabla de búsqueda de ratios de prio. [8] : En 8042–8044 Se basa en una secuencia recursiva. Aumenta un 10% cada buen nivel. [8] : En 161 sigue un patrón parabólico si se representa gráficamente, y las tareas niced se distribuyen como una función cuadrática móvil de 0 a 39 (correspondiente de mayor a menor prioridad nice) como dominio y de 128 a 5089 como rango. [8] : En 177-179, 120, 184-185 La parte móvil proviene de la variable t en la fórmula de fecha límite virtual que insinuó Kolivas.
- g (0) = 128
- g (i) = INT (g (i-1) * 11/10)
Índice | Numerador |
---|---|
0 | 128 |
1 | 140 |
2 | 154 |
3 | 169 |
4 | 185 |
5 | 203 |
6 | 223 |
7 | 245 |
8 | 269 |
9 | 295 |
10 | 324 |
11 | 356 |
12 | 391 |
13 | 430 |
14 | 473 |
15 | 520 |
dieciséis | 572 |
17 | 629 |
18 | 691 |
19 | 760 |
20 | 836 |
21 | 919 |
22 | 1010 |
23 | 1111 |
24 | 1222 |
25 | 1344 |
26 | 1478 |
27 | 1625 |
28 | 1787 |
29 | 1965 |
30 | 2161 |
31 | 2377 |
32 | 2614 |
33 | 2875 |
34 | 3162 |
35 | 3478 |
36 | 3825 |
37 | 4207 |
38 | 4627 |
39 | 5089 |
La función de mapeo agradable al índice de la tareaf (n) se asigna de nice −20… 19 al índice 0… 39 para ser utilizado como entrada a la tabla de búsqueda de relación de prio. Esta función de mapeo es la TASK_USER_PRIO()
macro en sched.h en el encabezado del kernel. La implementación interna del kernel difiere ligeramente con un rango de prioridad estática entre 100 y 140, pero los usuarios lo verán como −20 ... 19 agradable.
Lindo | Índice |
---|---|
−20 | 0 |
−19 | 1 |
−18 | 2 |
−17 | 3 |
−16 | 4 |
−15 | 5 |
−14 | 6 |
−13 | 7 |
−12 | 8 |
−11 | 9 |
−10 | 10 |
−9 | 11 |
−8 | 12 |
−7 | 13 |
−6 | 14 |
−5 | 15 |
−4 | dieciséis |
−3 | 17 |
−2 | 18 |
−1 | 19 |
0 | 20 |
1 | 21 |
2 | 22 |
3 | 23 |
4 | 24 |
5 | 25 |
6 | 26 |
7 | 27 |
8 | 28 |
9 | 29 |
10 | 30 |
11 | 31 |
12 | 32 |
13 | 33 |
14 | 34 |
15 | 35 |
dieciséis | 36 |
17 | 37 |
18 | 38 |
19 | 39 |
El plazo virtual se basa en esta fórmula exacta: [8] : ln 4063, 4036, 4033, 1180
- T = 6
- N = 1 << 20
- re (norte, t) = t + g (f (n)) * T * (N / 128)
Alternativamente,
- [13]
dónde d (n, t) es la fecha límite virtual en nanosegundos enteros u64 en función de nice n y t que es la hora actual en niffies (como en jiffies de nanosegundos), g (i) es la búsqueda en la tabla de razones de prio como función del índice, f (n) es la función de mapeo de índice agradable de la tarea, T es el intervalo de tiempo de round robin en milisegundos, N es una constante de 1 milisegundo en términos de nanosegundos como una aproximación reductora de latencia del factor de conversión de pero Kolivas usa una constante de base 2 N con aproximadamente esa escala. [8] : En 1173-1174 Valores más pequeños de d significa que la fecha límite virtual es anterior y corresponde a valores agradables negativos. Valores mayores de d indica que la fecha límite virtual se retrasa más tarde correspondiente a valores positivos positivos. Utiliza esta fórmula cada vez que expira el intervalo de tiempo. [8] : en 5087
128 en base 2 corresponde a 100 en base 10 y posiblemente un "pseudo 100". [8] : En 3415 115 en base 2 corresponde a 90 en base 10. Kolivas usa 128 para " cambios rápidos ", [8] : En 3846, 1648, 3525 ya que en la división es el desplazamiento a la derecha base 2.
Lindo | Fecha límite virtual en porciones de tiempo en relación con t | Fecha límite virtual en segundos exactos en relación con t |
---|---|---|
−20 | 1.0 | 0,006 |
−19 | 1.09 | 0,006562 |
−18 | 1.2 | 0,007219 |
−17 | 1.3 | 0,007922 |
−16 | 1.4 | 0,008672 |
−15 | 1,5 | 0,009516 |
−14 | 1,7 | 0.010453 |
−13 | 1,9 | 0.011484 |
−12 | 2.1 | 0.012609 |
−11 | 2.3 | 0.013828 |
−10 | 2.5 | 0.015187 |
−9 | 2,7 | 0.016688 |
−8 | 3,0 | 0.018328 |
−7 | 3.3 | 0.020156 |
−6 | 3.6 | 0.022172 |
−5 | 4.0 | 0.024375 |
−4 | 4.4 | 0.026812 |
−3 | 4.9 | 0.029484 |
−2 | 5.3 | 0.032391 |
−1 | 5.9 | 0.035625 |
0 | 6.5 | 0.039188 |
1 | 7.1 | 0.043078 |
2 | 7.8 | 0.047344 |
3 | 8,6 | 0.052078 |
4 | 9.5 | 0.057281 |
5 | 10,5 | 0.063000 |
6 | 11,5 | 0.069281 |
7 | 12,6 | 0.076172 |
8 | 13,9 | 0.083766 |
9 | 15,3 | 0.092109 |
10 | 16,8 | 0.101297 |
11 | 18,5 | 0.111422 |
12 | 20,4 | 0.122531 |
13 | 22,4 | 0.134766 |
14 | 24,7 | 0.148219 |
15 | 27,1 | 0.163031 |
dieciséis | 29,8 | 0.179297 |
17 | 32,8 | 0.197203 |
18 | 36,1 | 0.216891 |
19 | 39,7 | 0.238547 |
Políticas de programación
BFS utiliza políticas de programación para determinar la cantidad de tareas de la CPU que se pueden usar. BFS usa 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 [8] : En 4146–4161, las que están en la parte superior se ejecutan primero.
Cada tarea tiene un valor especial llamado prio. En la edición v0.462 (utilizada en el conjunto de parches del kernel -ck 4.0), hay un total de 103 "colas de prioridad" (también conocidas como prio) 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 prio más bajo significa que es más importante y se ejecuta primero.
Política en tiempo real
La política en tiempo real se diseñó para tareas en tiempo real . Esta política implica que las tareas en ejecución no pueden ser interrumpidas (es decir, sustituidas) por la tarea con prioridad más baja o los niveles de política de prioridad más baja. Las clases de prioridad consideradas por el planificador bajo la política de tiempo real son aquellas marcadas como SCHED_RR y SCHED_FIFO. [8] : En 351, 1150 El programador trata de manera diferente el round robin en tiempo real (SCHED_RR) y el FIFO en tiempo real (SCHED_FIFO). [8] : en 3881–3934
El diseño dispuso las primeras 100 colas de prioridad estática. [8] : en 189
La tarea que se elegirá para su ejecución se basa en la disponibilidad de la tarea del valor más bajo de prio de las 100 colas y la programación FIFO. [8] : en 4146–4161
En las bifurcaciones , la prioridad del proceso se degradará a la política normal. [8] : en 2708
En el uso sin privilegios (es decir, un usuario no root) de sched_setscheduler llamado con una solicitud de clase de política en tiempo real, el planificador degradará la tarea a política isócrona. [8] : en 350–359, 5023–5025
Política isócrona
La política Isochronous fue diseñada para un rendimiento casi en tiempo real para usuarios no root . [8] : en 325
El diseño presentaba 1 cola de prioridad que, de forma predeterminada, se ejecutaba como tareas en pseudo-tiempo real, pero que se puede ajustar como un grado de tiempo real. [8] : en 1201, 346–348
El comportamiento de la política puede permitir que una tarea se pueda degradar a la política normal [8] : En 336 cuando excede un porcentaje de manejo de recursos sintonizable (70% por defecto [8] : En 343, 432 ) de 5 segundos escalado al número de CPU en línea y la resolución del temporizador más 1 tic. [8] : En 343, 3844–3859, 1167, 338 [11] : En 1678, 4770–4783, 734 La fórmula se modificó en MuQSS debido al diseño de múltiples colas de ejecución. Las fórmulas exactas son:
dónde T es el número total de tics 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 sintonizable no en decimal sino como un número entero. La frecuencia del temporizador está configurada en 250 de forma predeterminada y se puede editar en el kernel, pero generalmente se ajusta a 100 Hz para servidores y 1000 Hz para escritorios interactivos. 250 es el valor equilibrado. Configuración R a 100 hizo que las tareas se comportaran como en tiempo real y 0 lo hizo no en pseudo-tiempo real y cualquier cosa en el medio fue en pseudo-tiempo real. [8] : en 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 de round robin sintonizable (con 6 ms como valor predeterminado) una tras otra en una feria. igualdad de oportunidades sin tener en cuenta el buen nivel. [8] : en 334
Este comportamiento de la política isócrona es exclusivo solo de BFS y MuQSS y es posible que no se implemente en otros programadores de CPU. [8] : ln 324, 8484–8485 [11] : ln 1287–1288
Política normal
La política normal se diseñó para un uso regular y es la política predeterminada. Las tareas recién creadas generalmente se marcan como normales. [8] : en 502
El diseño estableció una cola de prioridad y las tareas se eligen para ejecutarse primero en función de la fecha límite virtual más temprana.
Política de prioridad inactiva
La prioridad inactiva se diseñó 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. [8] : en 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 . [8] : en 368
La siguiente tarea ejecutada con prioridad inactiva con otras que residen en la misma política de prioridad se selecciona en la fecha límite virtual más temprana. [8] : en 4160–4161
Derecho preferente de compra
La preferencia puede ocurrir cuando una tarea recién lista con una política de mayor prioridad (es decir, mayor prioridad) tiene una fecha límite virtual anterior a la tarea que se está ejecutando actualmente, que se desprogramará y se colocará al final de la cola. [8] : En 169-175 Desprogramado significa que su fecha límite virtual se actualiza. [8] : En 165–166 El tiempo de la tarea se vuelve a llenar al máximo cuántico round robin cuando se ha agotado todo el tiempo. [8] : ln 4057–4062, 5856 Si el programador encontró la tarea en el prio más alto 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 con hyperthreaded / subprocesos SMT ) están ocupados. El planificador retrasará la apropiación tanto como sea posible si hay CPU lógicas no utilizadas.
Si una tarea está marcada como política de prioridad inactiva, no puede adelantarse ni siquiera a otras tareas marcadas como política inactiva, sino que utiliza la multitarea cooperativa . [8] : en 2341-2344
Colocación de tareas, múltiples núcleos
Cuando el programador descubre una tarea de activación, deberá determinar qué CPU lógica ejecutará la tarea de activación en el sistema no unicore. El programador favorece la mayoría de los núcleos hiperthreaded inactivos (o subprocesos SMT inactivos ) primero en la misma CPU en la que se ejecutó la tarea, [8] : en 261, luego en el otro núcleo inactivo de una CPU multinúcleo, [8] : en 262 y luego en el otro CPU en el mismo nodo NUMA, [8] : en 267, 263–266, 255–258 y luego todos los núcleos hiperprocesados ocupados / subprocesos SMT / CPU lógicas para ser reemplazados en el mismo nodo NUMA , [8] : en 265–267 luego el otro nodo NUMA (remoto) [8] : En 268-270 y está clasificado en una lista de preferencias. [8] : En 255–274 Este análisis especial existe para minimizar la sobrecarga de latencia resultante de la migración de la tarea. [8] : En 245, 268–272
La orden de preferencia es similar al párrafo anterior. El orden de preferencia son unidades de núcleo / SMT con hiperproceso en el mismo núcleo múltiple primero, luego el otro núcleo en el núcleo múltiple y luego la otra CPU en el mismo nodo NUMA. [8] : En 265–267 Cuando se busca una tarea para apropiarse en el otro nodo NUMA remoto, la preferencia es solo cualquier subproceso ocupado con un priocio menor o igual o una fecha límite virtual posterior, asumiendo que todas las CPU lógicas (incluido el núcleo hiperthreaded / Subprocesos SMT) en la máquina están todos ocupados. [8] : En 270, el programador tendrá que buscar una tarea adecuada con una tarea de política de prioridad menor o tal vez igual (con una fecha límite virtual posterior si es necesario) para adelantarse y evitar CPU lógicas con una tarea con una política de prioridad más alta que no se puede adelantar. La preferencia local tiene un rango más alto que la búsqueda de una unidad NUMA inactiva remota. [8] : en 265–269
Cuando una tarea se reemplaza 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 regulador de frecuencia de la CPU), la tarea se marca especialmente como "pegajosa" excepto aquellas marcadas como política en tiempo real. [8] : En 2085 Marcado fijo indica que la tarea aún tiene tiempo sin usar y la tarea está restringida a ejecutarse en la misma CPU. [8] : En 233–243 La tarea se marcará como pegajosa siempre que el regulador de escalado de la CPU haya escalado la CPU a una velocidad más lenta. [8] : En 2082–2107, 8840–8848 La tarea fija inactiva volverá a ejecutarse a la velocidad máxima 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. [8] : en 2082–2086, 239–242, 2068–2079 No es deseable migrar la tarea a otros lugares, sino dejarla inactiva debido al aumento de latencia provocado por la sobrecarga para migrar la tarea a otra CPU o nodo NUMA . [8] : En 228, 245 Esta característica pegajosa 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.
herramienta
Un usuario privilegiado puede cambiar la política de prioridad de un proceso con el programa schedtool [8] : En 326, 373 o lo hace un programa en sí. [8] : En 336 La clase de prioridad se puede manipular a nivel de código con una llamada al sistema como sched_setscheduler sólo disponible para root, [14] que utiliza schedtool. [15]
Benchmarks
En un estudio contemporáneo, [4] 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 Completely Fair Scheduler (CFS) en el kernel vanilla de Linux y el BFS en el kernel correspondiente parcheado con el conjunto de parches ck1. Se utilizaron siete máquinas diferentes para ver si existen diferencias y hasta qué punto se escalan utilizando métricas basadas en el rendimiento. El número de CPU lógicas varió de 1 a 16. Estos puntos finales nunca fueron factores en los principales objetivos de diseño del BFS. Los resultados fueron alentadores.
Los kernels parcheados con el conjunto de parches ck1, incluido el BFS, superaron al kernel de vainilla utilizando CFS en casi todos los puntos de referencia basados en el rendimiento probados. [4] Se podrían realizar más estudios con un conjunto de pruebas más grande, pero en base al pequeño conjunto de pruebas de 7 PC evaluados, estos aumentos en la cola de procesos, eficiencia / velocidad son, en general, independientes del tipo de CPU (mono, dual, quad, hyperthreaded, etc.), arquitectura de CPU (32 bits y 64 bits) y de multiplicidad de CPU (mono o doble socket).
Además, en varias CPU "modernas", como Intel Core 2 Duo y Core i7 , que representan estaciones de trabajo y portátiles comunes, BFS superó sistemáticamente al CFS en el kernel básico en todos los puntos de referencia. Las ganancias de eficiencia y velocidad fueron de pequeñas a moderadas.
Adopción
BFS es el programador predeterminado para las siguientes distribuciones de Linux de escritorio:
- NimbleX y Sabayon Linux 7 [16]
- PCLinuxOS 2010 [17]
- Zenwalk 6.4 [18]
- GalioOS 2.1 [19]
Además, BFS ha sido añadido a una rama experimental de Google 's Android repositorio de desarrollo. [20] No se incluyó en la versión de Froyo después de que las pruebas a ciegas no mostraran una mejor experiencia de usuario. [21]
MuQSS
BFS se ha retirado en favor de MuQSS , conocido formalmente como el Programador de lista de omisión de colas múltiples , una implementación reescrita del mismo concepto. [22] [23]
Diseño teórico y eficiencia
MuQSS utiliza una lista de omisión de 8 niveles en matriz estática bidireccional y las tareas se ordenan por prioridad estática [colas] (refiriéndose a la política de programación) y una fecha límite virtual. [11] : En 519, 525, 537, 588, 608 8 se eligió para encajar la matriz en la línea de caché. [11] : En 523 se eligió un diseño de estructura de datos doblemente enlazado para acelerar la eliminación de tareas. Eliminar una tarea solo requiere O (1) con una lista de omisión doble en comparación con el diseño original de William Pugh, que toma O ( n ) en el peor de los casos. [11] : en 458
La inserción de tareas es O (log n ). [11] : ln 458 La siguiente tarea para la búsqueda de ejecución es O ( k ), donde k es el número de CPU. [11] : En 589–590, 603, 5125 La siguiente tarea para la ejecución es O (1) por cola de ejecución , [11] : En 5124 pero el programador examina todas las demás colas de ejecución para mantener la equidad de tareas entre las CPU, en busca de latencia o equilibrio ( para maximizar el uso de la CPU y la coherencia de la caché en el mismo nodo NUMA sobre los que acceden a través de los nodos NUMA), por lo que, en última instancia, O ( k ). [11] : En 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. [11] : En 521 Utiliza varias 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 sea lo primero y la prioridad de la política inactiva sea la última. [11] : En 2356–2358 La política de prioridad normal e inactiva aún se ordena por fecha límite virtual que usa valores agradables . [11] : En 2353, las tareas de políticas en tiempo real e isócronas se ejecutan en orden FIFO ignorando los valores agradables. [11] : En 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, en la parte superior del nodo más verticalmente) y las tareas en el nivel 0 o en la parte frontal inferior se ejecución primero antes de los más cercanos a la parte superior verticalmente y los más alejados del nodo principal. [11] : en 2351-2352, 590 La clave utilizada para la clasificación insertada es la prioridad estática [11] : en 2345, 2365 o la fecha límite virtual. [11] : en 2363
El usuario puede optar por compartir colas de ejecución entre varios núcleos o tener una cola de ejecución por CPU lógica. [11] : En 947-1006 La especulación de compartir el diseño de las colas de ejecución era reducir la latencia con una compensación del rendimiento. [11] : en 947–1006
Un nuevo comportamiento introducido por MuQSS fue el uso del temporizador de alta resolución para una precisión de menos de milisegundos cuando se agotaron los intervalos de tiempo, lo que resultó en la reprogramación de tareas. [11] : en 618–630, 3829–3851, 3854–3865, 5316
Ver también
- Programación equitativa
Referencias
- ^ "-ck hacking: BFS versión 0.512, linux-4.8-ck1, MuQSS para linux-4.8" . ck-hack.blogspot.com . 2016-10-03 . Consultado el 10 de noviembre de 2016 .
- ^ a b "Con Kolivas presenta nuevo programador BFS» Revista Linux " . Linuxpromagazine.com. 2009-09-02 . Consultado el 30 de octubre de 2013 .
- ^ a b c "Preguntas frecuentes sobre BFS v0.330" . Ck.kolivas.org . Consultado el 30 de octubre de 2013 .
- ^ a b c "Programadores de CPU comparados" (PDF) . Repo-ck.com . Consultado el 30 de octubre de 2013 .
- ^ "Con Kolivas Returns, con un programador de Linux orientado a escritorio" . Slashdot . Consultado el 30 de octubre de 2013 .
- ^ "Ingo Molnar prueba nuevo programador BF" . Revista Linux. 2009-09-08 . Consultado el 30 de octubre de 2013 .
- ^ "sched-bfs-001.patch" . Con Kolivas. 2009-08-13 . Consultado el 9 de octubre de 2020 .
- ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar como en au av aw ax ay az ba bb bc bd be bf bg bh "4.0-sched-bfs-462.patch" . Con Kolivas. 2015-04-16 . Consultado el 29 de enero de 2019 .
- ^ a b "El planificador de plazos de escalera giratoria" . corbet. 2007-03-06 . Consultado el 30 de enero de 2019 .
- ^ "sched-rsdl-0.26.patch" . Con Kolivas. Archivado desde el original el 26 de julio de 2011 . Consultado el 30 de enero de 2019 .
- ^ a b c d e f g h i j k l m n o p q r s t u v "0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" . Con Kolivas. 2018-08-27 . Consultado el 29 de enero de 2019 .
- ^ a b "4.7-sched-bfs-480.patch" . Con Kolivas. 2016-09-02 . Consultado el 9 de octubre de 2020 .
- ^ La fórmula alternativa se presenta para facilitar la comprensión. Todas las matemáticas se realizan en matemáticas enteras, por lo que la pérdida de precisión sería excelente. Es posible que sea la razón por la que Kolivas aplazó la división por 128 a uno de los números más grandes como múltiplo de 128, lo que no da como resultado ningún resto.
- ^ "El programador de Linux" . Moshe Bar. 2000-04-01 . Consultado el 29 de enero de 2019 .
- ^ "schedtool.c" . freek. 2017-07-17 . Consultado el 30 de enero de 2019 .
- ^ "Sabayon 7 trae el paraíso de Linux" . Ostatic.com . Consultado el 30 de octubre de 2013 .
- ^ "La edición 2010 ya está disponible para descargar" . PCLinuxOS. 2013-10-22 . Consultado el 30 de octubre de 2013 .
- ^ "¡Zenwalk 6.4 está listo! - Lanzamientos - Noticias" . Zenwalk.org. Archivado desde el original el 23 de octubre de 2013 . Consultado el 30 de octubre de 2013 .
- ^ "Acerca de GalliumOS - GalliumOS Wiki" . wiki.galliumos.org . Consultado el 8 de junio de 2018 .
- ^ [1] Archivado el 22 de septiembre de 2009 en la Wayback Machine.
- ^ "CyanogenMod 5 para el G1 / ADP1" . Lwn.net . Consultado el 30 de octubre de 2013 .
- ^ "ck-hacking: linux-4.8-ck2, MuQSS versión 0.114" . ck-hack.blogspot.com . 2016-10-21 . Consultado el 10 de noviembre de 2016 .
- ^ https://www.phoronix.com/scan.php?page=news_item&px=MuQSS-First-Major-Release
enlaces externos
- Preguntas frecuentes sobre Brain Fuck Scheduler