Planificación de CPU

Un planificador de CPU elige el proceso o hilo listo que se ejecutará a continuación en una CPU. La regla que sigue es su política. El despachador lleva a cabo la elección cambiando la ejecución al trabajo seleccionado. Una política distinta puede usar el mismo mecanismo de cambio.

Sigue los cambios de estado

Un trabajo en ejecución ocupa una CPU. Un trabajo listo podría ejecutarse, pero espera su turno. Un trabajo bloqueado espera un evento, como la finalización de una lectura de disco. Solo los trabajos listos son candidatos para la selección.

Supón que un editor inicia una lectura de disco mientras un compilador está listo. El editor pasa de ejecución a bloqueado, por lo que el compilador puede ejecutarse. Cuando termina la lectura, una interrupción devuelve el editor al estado listo. No necesariamente se ejecuta de inmediato: la política debe elegir entre él y los demás trabajos listos.

Las decisiones de planificación se producen cuando un trabajo se bloquea, termina, pasa al estado listo o es interrumpido y devuelto al estado listo. La cesión voluntaria también libera la CPU. La expropiación o desalojo consiste en retirar la CPU a un trabajo que podría haber seguido ejecutándose; el trabajo conserva su estado guardado y puede reanudarse más tarde.

Una interrupción del temporizador permite al núcleo imponer un intervalo de tiempo asignado, incluso si un programa ejecuta un bucle sin ceder la CPU. Una operación de entrada/salida terminada también puede provocar una expropiación al hacer que una tarea más favorecida pase al estado listo. Linux, Windows y macOS usan planificación expropiativa.

El trabajo llega en ráfagas

Los programas alternan entre ráfagas de CPU, cuando calculan, y periodos de espera de entrada/salida. Un programa limitado por la CPU, como un codificador, tiene ráfagas de CPU largas. Un programa limitado por la entrada/salida, como un editor, suele calcular brevemente y después esperar. Atender pronto a un editor después de una pulsación puede mejorar su capacidad de respuesta sin darle mucho tiempo total de CPU.

El despachador guarda el estado de la tarea anterior, restaura los registros de la tarea elegida y reanuda su secuencia de instrucciones en modo usuario. La latencia de despacho es el tiempo que se tarda en transferir la ejecución. El cambio también altera las cachés y el búfer de traducción adelantada, o TLB, que almacena en caché traducciones de direcciones. La siguiente tarea puede necesitar rellenarlos, por lo que el tiempo de guardar registros es solo una parte del coste.

Tres escalas de tiempo de planificación

El planificador a largo plazo admite los trabajos enviados y controla cuántos hay en el sistema. El planificador a medio plazo puede suspender procesos completos sacándolos de la memoria mediante intercambio y restaurándolos después. El planificador a corto plazo selecciona la siguiente tarea lista y actúa con frecuencia. Los sistemas de propósito general dependen principalmente de esta última función; los sistemas por lotes y los clústeres también pueden controlar la admisión explícitamente.

Comienza la comparación de políticas con trabajos sencillos que solo usan CPU y tienen duraciones conocidas. Después cambia una característica: las duraciones desiguales muestran los retrasos de FIFO, las llegadas posteriores muestran los límites de la planificación no expropiativa, la entrada/salida crea oportunidades para solapar trabajo y las duraciones desconocidas requieren predicción o realimentación.

Una planificación te indica cuándo se ejecutan los trabajos. Una métrica te indica qué parte de esa planificación importa. Registra la llegada, la primera ejecución y la finalización de cada trabajo antes de calcular los promedios.

Distingue los tres tiempos

El tiempo de retorno mide todo el intervalo desde la llegada hasta la finalización. El tiempo de respuesta mide la demora hasta la primera ejecución. El tiempo de espera suma todos los intervalos en los que el trabajo está listo pero no se ejecuta.

Para un trabajo que solo usa CPU, el tiempo de retorno es igual a la suma del tiempo de espera y el tiempo de ejecución en la CPU. Si hay entrada/salida, el tiempo bloqueado también forma parte del retorno, por lo que restar solo el tiempo de CPU sobreestimaría la espera. Aquí se usa la definición de respuesta basada en la primera ejecución; un servicio dirigido a usuarios puede medir por separado el tiempo hasta su primera salida.

Resuelve una línea de tiempo FIFO

A llega en 0 ms y necesita 8 ms de tiempo de CPU. B llega en 1 ms y necesita 4 ms. C llega en 2 ms y necesita 2 ms. Sin coste de cambio, FIFO da:

• A: 0–8 ms.
• B: 8–12 ms.
• C: 12–14 ms.

El tiempo de retorno promedio es $\frac{8+11+12}{3}=\frac{31}{3}\approx \mathrm{10,33}$ ms. Los tiempos promedio de respuesta y espera son ambos $\frac{0+7+10}{3}=\frac{17}{3}\approx \mathrm{5,67}$ ms. Coinciden porque cada trabajo se ejecuta una vez sin interrupción. Con expropiación, un trabajo puede volver a esperar después de su primer turno, por lo que la espera puede superar la respuesta.

Mide toda la carga de trabajo

La tasa de procesamiento cuenta los trabajos terminados por unidad de tiempo transcurrido. La planificación termina tres trabajos en 14 ms, aproximadamente 214,29 trabajos/s. La utilización de la CPU es el tiempo ocupado de CPU dividido entre el tiempo transcurrido; aquí es del 100 % porque la CPU nunca está inactiva. Especifica el intervalo de medición: añadir un periodo de inactividad después de la finalización cambiaría ambas cifras.

Una alta utilización puede ir acompañada de largas esperas. Tampoco implica necesariamente que todo el tiempo ocupado se dedique a trabajo útil de las aplicaciones: las mediciones reales pueden contar los cambios de contexto y otros trabajos del núcleo como tiempo ocupado. Indica si un cálculo de sobrecarga mide tiempo ocupado o trabajo útil.

Elige qué optimizar

El trabajo por lotes suele valorar el tiempo de retorno promedio. El trabajo interactivo valora una respuesta rápida. Los servicios compartidos necesitan acceso equitativo además de una buena tasa de procesamiento. La inanición significa que un trabajo elegible espera indefinidamente, por lo que un buen promedio por sí solo no demuestra un trato equitativo.

Examina las demoras individuales y los percentiles altos de la distribución. Un tiempo de respuesta del percentil 99 describe la demora en la que se sitúa o por debajo de la cual queda aproximadamente el 99 % de las observaciones; unas pocas demoras graves pueden quedar ocultas en un promedio bajo. Resta siempre el instante de llegada del propio trabajo y cuenta sus intervalos de ejecución como servicio, nunca como espera.

FIFO, también llamado primero en llegar, primero en ser atendido o FCFS, ejecuta los trabajos listos por orden de llegada. Es no expropiativo: una llegada posterior no puede interrumpir una ráfaga de CPU en ejecución. En los ejemplos que solo usan CPU, cada trabajo seleccionado se ejecuta hasta terminar.

Observa el efecto convoy

A, B y C llegan a la vez. A necesita 60 ms; B y C necesitan 6 ms cada uno. Con A en primer lugar, FIFO ejecuta A 0–60, B 60–66 y C 66–72. Los tiempos de retorno son 60, 66 y 72 ms, con un promedio de 66 ms. Los trabajos pequeños pasan la mayor parte de su vida esperando detrás de A. Este es el efecto convoy.

Primero el trabajo más corto (SJF) selecciona la siguiente ráfaga de CPU más corta entre los trabajos listos y no la interrumpe. Con las mismas llegadas, ejecuta B 0–6, C 6–12 y después A 12–72. El tiempo de retorno promedio pasa a ser $\frac{6+12+72}{3}=30$ ms. El trabajo total de CPU sigue siendo de 72 ms; la mejora se debe a que los trabajos cortos terminan antes.

¿Por qué ayuda esto? Si una ráfaga larga se ejecuta inmediatamente antes que una corta, ambos trabajos esperan a que termine todo el trabajo anterior. Intercambiar solo estos dos reduce la demora del trabajo corto en la duración de la ráfaga larga y aumenta la demora del trabajo largo solo en la duración de la ráfaga corta. Repetir estos intercambios coloca las ráfagas en orden ascendente. Cuando todos los trabajos llegan a la vez y se conocen sus duraciones, SJF minimiza los tiempos promedio de retorno y espera; la respuesta hasta la primera ejecución también es igual a la espera en este caso no expropiativo que solo usa CPU.

Limita la elección a los trabajos listos

Ahora A llega en 0 ms, mientras B y C llegan en 10 ms. En 0 ms, A es la única opción. SJF no expropiativo ejecuta A 0–60, B 60–66, C 66–72. Los tiempos de retorno son 60, 56 y 62 ms, con un promedio de aproximadamente 59,33 ms. SJF no puede actuar sobre un trabajo futuro ni interrumpir una ráfaga que ya ha iniciado.

FIFO evita la inanición cuando los trabajos anteriores terminan cediendo la CPU. SJF puede causar inanición de un trabajo largo en espera si siguen llegando trabajos cortos.

Predice una ráfaga

La siguiente ráfaga de CPU suele ser desconocida. Un promedio exponencial combina la última ráfaga medida con la predicción anterior:

Aquí, $t_n$ es la ráfaga medida, ${\tau }_n$ la predicción anterior y $\alpha$ un peso entre 0 y 1. Partiendo de 10 ms y usando $\alpha =\mathrm{0,5}$, una medición de 6 ms da una predicción de 8 ms. Una medición posterior de 4 ms da 6 ms; otra de 6 ms la mantiene en 6 ms. Con peso cero, las mediciones no tienen efecto; con peso uno, solo importa la medición más reciente. La magnitud prevista es la duración de la ráfaga de CPU, no el tamaño del archivo de programa ni el número de líneas.

Primero el trabajo con menor tiempo restante (STCF, también SRTF) es SJF expropiativo. Cuando llega o termina un trabajo, compara el tiempo de CPU que aún necesita cada trabajo listo. Un recién llegado interrumpe el trabajo actual cuando necesita menos tiempo del que le queda a este.

Compara el tiempo restante

A necesita 60 ms y llega en 0 ms. B y C necesitan 6 ms cada uno y llegan en 10 ms. A se ejecuta durante 10 ms y le quedan 50 ms. En 10 ms, B gana porque 6 ms es menos que 50 ms; C tiene la misma duración, por lo que el orden de llegada y después el nombre resuelven el empate.

La línea de tiempo es A 0–10, B 10–16, C 16–22, A 22–72. Los tiempos de retorno son A 72 ms, B 6 ms y C 12 ms, con un promedio de 30 ms. Los tiempos de respuesta son 0, 0 y 6 ms, con un promedio de 2 ms. SJF no expropiativo con estas llegadas da promedios de aproximadamente 59,33 ms de retorno y 35,33 ms de respuesta.

Resta siempre el servicio ya recibido. Sería incorrecto comparar una nueva ráfaga de 12 ms con los 60 ms originales de A si a A solo le quedaran 5 ms. STCF terminaría A primero. Con duraciones conocidas de trabajos que solo usan CPU y un coste de cambio nulo, STCF minimiza el tiempo de retorno promedio para cualquier patrón de llegadas. Los trabajos largos pueden seguir sufriendo inanición si llegan continuamente trabajos más cortos.

Cuando todos los trabajos que solo usan CPU llegan a la vez, SJF y STCF dan el mismo orden. Al trabajo más corto en ejecución le queda cada vez menos tiempo, por lo que ningún trabajo en espera se convierte en motivo para expropiarle la CPU.

Aprovecha el tiempo bloqueado de otro trabajo

Un trabajo bloqueado no puede usar la CPU. Su espera de entrada/salida es una oportunidad para ejecutar otros trabajos listos, incluso con una política no expropiativa. La expropiación vuelve a ser relevante cuando una operación de entrada/salida terminada deja lista una ráfaga corta mientras otro trabajo se ejecuta.

Considera A con cinco ráfagas de CPU de 10 ms y una lectura de disco de 10 ms después de cada una de sus primeras cuatro ráfagas. B necesita una ráfaga de CPU de 50 ms. Ambos llegan en 0 ms. Si la CPU permanece inactiva durante las lecturas de A y retrasa B hasta que A termina, A finaliza en 90 ms y B en 140 ms.

Trata cada ráfaga de A que vuelve como trabajo corto listo:

• A se ejecuta 0–10; su lectura ocupa 10–20 mientras B se ejecuta.
• A vuelve para 20–30; a B le quedan 40 ms, por lo que ganan los 10 ms de A.
• B se ejecuta 30–40 durante la siguiente lectura. La alternancia se repite.
• La última ráfaga de A se ejecuta 80–90; B termina sus últimos 10 ms durante 90–100.

A sigue terminando en 90 ms, pero B termina en 100 ms. La CPU realiza 100 ms de trabajo en 100 ms de tiempo transcurrido. La actividad del disco y la de la CPU se solapan; la CPU no ejecuta A mientras A está bloqueado. Una interrupción de dispositivo marca A como listo cuando termina cada lectura, tras lo cual STCF compara su nueva ráfaga con el trabajo restante de B.

La planificación por turnos (RR) mantiene una cola FIFO de trabajos listos y da al trabajo situado al principio como máximo un cuanto de tiempo o intervalo de tiempo asignado. Un trabajo que termina o se bloquea abandona la CPU antes. Un trabajo que sigue listo cuando termina su intervalo pasa al final de la cola.

Sigue los turnos antes de calcular los tiempos

A, B y C llegan en 0 ms y necesitan 9 ms cada uno. Con un cuanto de 3 ms, RR ejecuta:

• Primera ronda: A 0–3, B 3–6, C 6–9.
• Segunda ronda: A 9–12, B 12–15, C 15–18.
• Última ronda: A 18–21, B 21–24, C 24–27.

Las primeras ejecuciones son en 0, 3 y 6 ms, por lo que la respuesta promedio es de 3 ms. Las finalizaciones son en 21, 24 y 27 ms, por lo que el retorno promedio es de 24 ms. FIFO da una respuesta promedio de 9 ms y un retorno promedio de 18 ms. Aquí RR hace que todos comiencen pronto, pero aplaza el primer trabajo terminado hasta los 21 ms.

RR divide el acceso a la CPU mientras los trabajos compiten; no iguala los tiempos de finalización. Un trabajo corto puede terminar en su primer turno. Con una población fija de $n$ trabajos listos y un cuanto $q$, la espera entre turnos es como máximo $(n-1)q$ sin costes de cambio. Las llegadas continuas, otras clases de prioridad y las restricciones sobre las CPU en que se puede ejecutar una tarea cambian las condiciones de ese límite.

Gestiona las llegadas al final de un intervalo

Usa el orden de llegada y después el orden alfabético para resolver empates. Un trabajo que llega justo cuando termina un intervalo entra antes que el trabajo expropiado. Si A llega en 0 ms y necesita 8 ms, B en 1 ms y necesita 4 ms, y C en 2 ms y necesita 2 ms, un cuanto de 2 ms da A 0–2, B 2–4, C 4–6, A 6–8, B 8–10, A 10–14.

El último intervalo de A contiene dos turnos consecutivos sin competidores. Los tiempos de respuesta son 0, 1 y 2 ms; los tiempos de retorno son 14, 9 y 4 ms. Sus promedios son 1 ms y 9 ms. Cuando un trabajo bloqueado vuelve en RR básico, entra para un turno nuevo; no reserva tiempo de CPU sin usar mientras está bloqueado.

Haz que el cuanto compense su coste

Un cuanto muy grande hace que RR se comporte como FIFO para las ráfagas más cortas que ese cuanto. Un cuanto diminuto provoca muchos despachos y alteraciones repetidas de las cachés. En una implementación sencilla basada en temporizador, el cuanto es un número entero de periodos del temporizador.

Para un coste de cambio $s$ después de cada intervalo útil de duración $q$, la fracción aproximada de sobrecarga es $\frac{s}{q+s}$. Un cambio de 0,1 ms cuesta aproximadamente un 9,1 % con un intervalo de 1 ms, pero aproximadamente un 0,99 % con uno de 10 ms. Los intervalos más largos amortizan el coste del cambio al repartirlo entre más trabajo útil.

Una regla práctica habitual para dimensionarlo es permitir que la mayoría de las ráfagas, por ejemplo alrededor del 80 %, terminen dentro de un intervalo. La elección adecuada depende de las duraciones de ráfaga medidas y de las demoras de respuesta que la carga de trabajo pueda tolerar. Cuenta los cambios entre tareas por separado de los eventos del temporizador que simplemente permiten continuar a la misma tarea cuando es la única lista.

Un planificador por prioridades ejecuta el trabajo listo de mayor prioridad. Los trabajos de igual prioridad pueden seguir el orden FIFO o ejecutarse por turnos. En una versión expropiativa, un trabajo de mayor prioridad que acaba de pasar al estado listo toma la CPU de inmediato; en una versión no expropiativa espera hasta que el trabajo actual la libera.

Interpreta la dirección de la escala

Los números de prioridad no tienen una dirección universal. En los ejemplos de los manuales de esta unidad, usa números menores para indicar mayor prioridad. Los valores nice de Linux siguen esa dirección, pero los niveles de prioridad de Windows y las prioridades de tiempo real de Linux usan números mayores para indicar mayor prioridad.

A, B y C llegan en 0 ms con ráfagas de 4, 3 y 5 ms y prioridades 2, 1 y 3. La planificación no expropiativa por prioridades ejecuta B 0–3, A 3–7 y C 7–12. Sus tiempos de espera son 0, 3 y 7 ms, con un promedio de aproximadamente 3,33 ms; los tiempos de retorno son 3, 7 y 12 ms, con un promedio de aproximadamente 7,33 ms.

Una prioridad interna procede del comportamiento medido, como el uso de la CPU o las esperas de entrada/salida. SJF obtiene la prioridad a partir de la duración prevista de la ráfaga. Una prioridad externa procede de una persona, como un administrador que marca una copia de seguridad como menos urgente. Ninguna de las dos opciones garantiza que el trabajo de baja prioridad reciba tiempo si llegan continuamente trabajos de mayor prioridad.

Eleva la prioridad con la espera

El envejecimiento eleva gradualmente la prioridad de un trabajo en espera. Si la prioridad mejora en uno cada 100 ms, un trabajo que comienza con prioridad 20 alcanza la prioridad máxima 0 después de 2 s de espera en estado listo. La mayor prioridad le permite competir con los trabajos favorecidos; las reglas de desempate determinan los turnos entre trabajos con la misma prioridad.

La inanición es la falta de progreso causada por la selección repetida de otros trabajos. El envejecimiento la combate cambiando la prioridad con el tiempo. Cumple una función distinta de la predicción de la duración de las ráfagas: un trabajo largo que lleva mucho tiempo esperando puede merecer un turno aunque su ráfaga siga siendo larga.

Sigue la dependencia en la inversión de prioridades

Un trabajo H de alta prioridad puede estar bloqueado por un cerrojo que posee el trabajo L de baja prioridad. Un trabajo M de prioridad media puede expropiar la CPU a L. Ahora H no puede continuar, aunque M tenga menor prioridad que H: primero debe ejecutarse L para liberar el cerrojo. Esto es una inversión de prioridades.

Con la herencia de prioridades, L hereda temporalmente la prioridad de H mientras posee el cerrojo que H necesita. M ya no puede impedir que L use la CPU. L se ejecuta, libera el cerrojo y pierde la prioridad heredada; H pasa al estado listo y puede ejecutarse.

Elevar la propia prioridad de H no libera el cerrojo: H sigue bloqueado. La clave es permitir que se ejecute el hilo que puede resolver la dependencia. En 1997, Mars Pathfinder encontró un problema de inversión de prioridades que se solucionó activando la herencia de prioridades.

Las colas multinivel con realimentación (MLFQ) combinan prioridades con planificación por turnos. Su objetivo es aproximarse al servicio de los trabajos cortos y mantener una respuesta rápida para el trabajo interactivo sin que se le indique el tiempo de ejecución futuro de cada trabajo. El uso reciente de CPU proporciona la realimentación.

Aplica las reglas de las colas

Cada trabajo listo pertenece a una cola de prioridad. La versión básica con contabilización sigue cuatro reglas:

1. Elige la cola de mayor prioridad que contenga trabajos listos.
2. Dentro de esa cola, alterna por turnos los trabajos de igual prioridad.
3. Coloca un trabajo nuevo en la cola superior.
4. Baja de prioridad a un trabajo cuando consume su asignación de tiempo de CPU en el nivel actual, contando el uso acumulado entre todos los turnos y las interrupciones por entrada/salida.

Un cuanto limita un turno. Una asignación limita el servicio total en un nivel de prioridad. Un nivel puede permitir varios cuantos antes del descenso. En el nivel inferior, un descenso deja el trabajo en la cola inferior.

Esto da a un trabajo nuevo la oportunidad de terminar rápidamente. Un trabajo que consume tiempo de CPU repetidamente revela una demanda mayor y desciende. Una ráfaga corta que se bloquea consume poca asignación, por lo que los trabajos interactivos tienden a permanecer más tiempo en los niveles altos.

Sigue un trabajo largo y uno recién llegado

Usa las colas Q2, Q1 y Q0, con Q2 como la más alta, cuantos de 10 ms y asignaciones de 10 ms en cada nivel, sin elevación de prioridad durante este seguimiento. A necesita 200 ms y llega en 0 ms. Se ejecuta en Q2 de 0–10, en Q1 de 10–20 y después en Q0.

En 100 ms, A ha recibido 100 ms de tiempo de CPU. B llega y necesita 20 ms. B entra en Q2 y expropia la CPU a A, después se ejecuta 100–110 en Q2. Ha consumido la asignación de ese nivel y baja a Q1. Q1 tiene mayor prioridad que Q0, donde está A, por lo que B se ejecuta 110–120 y termina. A se reanuda en 120 y completa sus 100 ms restantes en 220 ms. El tiempo de retorno de B es de 20 ms pese a llegar después de un trabajo mucho más largo.

Sigue el trabajo restante de A mientras B se ejecuta: permanece en 100 ms. El tiempo transcurrido avanza durante el servicio de B, pero A no recibe servicio de CPU entonces.

Distingue la espera del consumo de CPU

Un editor que se ejecuta durante 1 ms y espera una entrada consume una asignación de 10 ms a lo largo de diez ráfagas de este tipo. El tiempo bloqueado no cuenta para la asignación de CPU. Con una contabilización estricta, esas ráfagas cortas siguen sumándose, por lo que el editor termina bajando de nivel salvo que una elevación de prioridad lo devuelva antes a la cola superior.

Una regla inicial de MLFQ solo bajaba de nivel a los trabajos que usaban un cuanto completo sin interrupción. Un trabajo que cedía la CPU justo antes de que terminara conservaba su prioridad. Esa regla permitía una respuesta rápida del trabajo interactivo, pero también permitía la manipulación deliberada. Contabilizar el uso acumulado de CPU cierra esa posibilidad.

Las colas inferiores se ejecutan cuando ninguna cola superior tiene trabajos listos. Un trabajo bloqueado de mayor prioridad no impide que los trabajos de menor prioridad usen la CPU. Si la demanda de alta prioridad se mantiene, los trabajos inferiores necesitan un mecanismo adicional contra la inanición, proporcionado por las elevaciones periódicas.

La realimentación crea una separación útil, pero el comportamiento pasado de un trabajo puede dejar de representar sus necesidades actuales. Un cálculo largo puede volverse interactivo más adelante. Mientras tanto, un trabajo de la cola inferior puede esperar indefinidamente si las colas superiores siguen ocupadas.

Reconsidera cada trabajo periódicamente

Una elevación de prioridad devuelve todos los trabajos a la cola superior después de un periodo $S$. Permite que los trabajos en espera compartan la cola superior y que el planificador vuelva a aprender los cambios de comportamiento. Un trabajo elevado que está limitado por la CPU consume después su asignación y vuelve a bajar.

Considera las primeras reglas de MLFQ: dos trabajos interactivos siempre ceden la CPU antes de completar un intervalo de 10 ms y juntos mantienen ocupada Q2. Un trabajo limitado por la CPU espera en Q0. Sin elevaciones no recibe servicio. En una planificación repetitiva en la que una elevación cada 100 ms le da un turno de 10 ms en el nivel superior antes de que descienda y el trabajo de mayor prioridad ocupe el resto, recibe el 10 % de la CPU. Ese porcentaje procede de este seguimiento; una elevación no asigna una proporción fija general.

Un periodo largo entre elevaciones deja largas esperas entre oportunidades. Un periodo muy corto devuelve repetidamente los trabajos limitados por la CPU a la cola superior y reduce la ventaja del trabajo interactivo. Algunos diseños han usado periodos de alrededor de un segundo, pero el periodo es una elección de ajuste basada en el comportamiento de la carga de trabajo y los objetivos de respuesta.

Contabiliza el uso entre cesiones

Un problema aparte es la manipulación del planificador. Con la primera regla del intervalo completo, un programa puede ejecutarse durante 9 ms, solicitar una operación de entrada/salida de 1 ms y repetir el proceso. Nunca usa un intervalo completo de 10 ms de una sola vez, por lo que conserva la prioridad máxima mientras consume casi todo el tiempo de CPU disponible.

Con una asignación acumulada de 10 ms, la primera ráfaga consume 9 ms y deja 1 ms. Después de la operación de entrada/salida, un milisegundo más agota la asignación y el trabajo baja de nivel durante su segunda ráfaga. Una solicitud de entrada/salida cambia el estado; no borra el servicio ya recibido. La regla de contabilización impide esta táctica incluso sin una elevación de prioridad.

Ajusta los niveles

Elige el número de colas, el cuanto de cada cola, la asignación de cada nivel y el periodo entre elevaciones. Las colas superiores suelen usar cuantos cortos, por ejemplo de 10 ms, para alternar rápidamente entre trabajos interactivos. Las colas inferiores pueden usar cuantos mucho más largos, a veces de cientos de milisegundos, para reducir los cambios durante los cálculos continuos.

La asignación puede crecer independientemente del cuanto. Un nivel con un cuanto de 5 ms y una asignación de 15 ms puede permitir tres turnos completos antes del descenso. Aumentar la asignación retrasa la clasificación como trabajo de larga duración; aumentar el cuanto alarga un turno individual.

El diseño de tiempo compartido de Solaris ilustra la realimentación basada en tablas: su tabla clásica configurable tiene 60 niveles de prioridad, con cuantos que van desde aproximadamente 20 ms con prioridad alta hasta unos pocos cientos de milisegundos con prioridad baja. En cambio, los diseños clásicos de BSD calculaban la prioridad a partir del uso reciente de CPU, cuya influencia disminuye con el tiempo. Ambos hacen que el uso antiguo de CPU pierda influencia, de modo que el historial lejano de un hilo no determina permanentemente su trato.

La planificación de reparto proporcional busca dividir el servicio de CPU según las proporciones asignadas. En la planificación por lotería, cada trabajo que puede ejecutarse posee boletos. Un boleto ganador elegido al azar determina el trabajo para el siguiente intervalo de igual duración. La probabilidad de que gane un trabajo es su número de boletos dividido entre el total de boletos de los trabajos que pueden ejecutarse.

Localiza un boleto ganador

A tiene 100 boletos, B 50 y C 250. Numera los 400 boletos del 0 al 399. A posee los boletos 0–99, B posee los 100–149 y C posee los 150–399. Un sorteo de 300 selecciona C.

Una implementación basada en listas sortea un número y acumula los números de boletos. Los totales acumulados son 100 después de A, 150 después de B y 400 después de C. Detente en el primer total estrictamente mayor que el número sorteado. Usar «mayor o igual que» asignaría incorrectamente los boletos situados en los límites: el número sorteado 100 pertenece a B. Situar primero a quienes poseen más boletos reduce la longitud promedio de esta búsqueda en la lista.

Distingue lo esperado de una garantía

Con A en posesión de 75 boletos y B de 25, la proporción esperada de A es del 75 %. En 100 sorteos independientes de intervalos iguales, con ambos trabajos disponibles para ejecutarse, se espera que A gane 75. La desviación estándar es:

$\sqrt{100\times \mathrm{0,75}\times \mathrm{0,25}}\approx \mathrm{4,33}$ intervalos.

Un resultado de alrededor de 71–79 victorias está aproximadamente a una desviación estándar de la media; no es un intervalo garantizado. Las ejecuciones cortas pueden alejarse notablemente de la proporción prevista de 3:1. A medida que crece el periodo de observación, la variación aleatoria relativa disminuye. La lotería proporciona equidad probabilística, no un reparto exacto en un periodo finito ni una espera acotada hasta el siguiente turno.

Para dos trabajos con igual número de boletos e iguales demandas de CPU, la métrica de falta de equidad U divide el tiempo de finalización más temprano entre el más tardío. La razón alcanza 1 cuando terminan juntos y es menor cuando uno termina mucho antes. Esta razón de finalización es especialmente variable para los trabajos cortos planificados por lotería.

Asigna boletos entre usuarios y dependencias

El sistema de monedas de boletos permite a un usuario dividir localmente un derecho global asignado. El usuario X tiene 200 boletos globales y asigna 300 boletos locales a X1 y 100 a X2. De 400 boletos locales, X1 tiene tres cuartos, lo que le da 150 boletos globales; X2 recibe 50. El usuario Y tiene 100 boletos globales para Y1. El total es 300, por lo que X1 recibe una proporción esperada del 50 %, X2 de aproximadamente el 16,67 % y Y1 de aproximadamente el 33,33 % de la CPU disputada.

La transferencia de boletos presta temporalmente los boletos de un cliente a un servidor que trabaja para él y los devuelve cuando termina la solicitud. Esto sigue la dependencia del trabajo. La inflación de boletos permite que los trabajos que cooperan aumenten su propio número de boletos para solicitar más servicio. Requiere confianza o límites: la inflación sin restricciones permite que un trabajo acaparador reduzca las proporciones de todos los demás.

La lotería necesita los totales de boletos, pero no un registro de cuánto se ha adelantado cada trabajo en servicio. Un trabajo nuevo simplemente aporta sus boletos al conjunto de trabajos que pueden ejecutarse. La asignación de boletos sigue siendo una decisión de política; el sorteo aleatorio aplica esa elección en términos esperados. Los boletos de un trabajo bloqueado no compiten por un intervalo que no puede usar.

La planificación por pasos convierte las proporciones de boletos en una secuencia determinista. Cada trabajo que puede ejecutarse tiene un paso, calculado como una constante grande dividida entre sus boletos, y un valor de avance que registra su progreso ponderado. Elige el menor valor de avance, ejecuta ese trabajo durante un intervalo de igual duración y después suma su paso a su valor de avance.

Calcula los pasos

A tiene 50 boletos, B 25 y C 100. Con la constante 1000, sus pasos son 20, 40 y 10. Más boletos producen un paso menor. El valor de avance de un trabajo favorecido aumenta lentamente, por lo que se convierte en el mínimo con más frecuencia.

Inicia todos los valores de avance en cero y resuelve los empates alfabéticamente. Mantén la tupla en el orden fijo A, B, C:

Solo cambia el valor de avance del trabajo seleccionado. En siete intervalos, A recibe dos turnos, B uno y C cuatro: la proporción exacta 50:25:100. Con el valor de avance compartido de 40, cada uno ha progresado la misma cantidad de servicio ponderado. Entre esos puntos de coincidencia, las proporciones en periodos cortos no tienen por qué ser exactas.

Distingue el servicio real del progreso virtual

El valor de avance sirve para ordenar, no es tiempo transcurrido ni un número de boletos. El paso grande de B hace que espere mientras A y C lo alcanzan en valor de avance. Aun así, recibe la proporción prevista de un séptimo durante este ciclo repetitivo. Sumar el número de boletos al valor de avance invertiría el diseño: el trabajo con más boletos daría el mayor salto y se seleccionaría con menos frecuencia.

La constante controla la escala de los pasos, no las proporciones previstas de boletos. Las implementaciones con enteros necesitan suficiente precisión para evitar que el redondeo distorsione esas proporciones. Las comparaciones y actualizaciones deben usar una escala coherente.

Sitúa de forma razonable a un recién llegado

Supón que los trabajos establecidos tienen valores de avance de alrededor de 4000. Un trabajo nuevo que empezara en cero ganaría repetidamente mientras se pone al día, incluso si tuviera pocos boletos. Inicializa su valor de avance en relación con el progreso actual del sistema, por ejemplo con el valor mínimo actual, para que no acumule servicio por el tiempo anterior a su llegada.

El tiempo de ejecución virtual de Linux usa la idea relacionada de contabilizar el progreso ponderado por el servicio real de CPU. En ambos diseños, un derecho mayor hace que ese progreso crezca más lentamente, manteniendo la tarea en competencia para recibir servicio más adelante.

Los planificadores equitativos de Linux registran el servicio de CPU ponderado. El planificador completamente equitativo (CFS), introducido en Linux 2.6.23 en 2007, elegía la tarea que podía ejecutarse con el menor tiempo de ejecución virtual. Linux comenzó a sustituir esa regla de selección por EEVDF en la versión 6.6 en 2023.

Divide el servicio por peso

Un valor nice va de −20, el más favorecido, a +19, el menos favorecido. Nice 0 tiene un peso de 1024. Cada paso hacia un valor nice mayor reduce el peso por un factor de aproximadamente 1,25. Algunos pesos de ejemplo son 3121 con nice −5, 820 con nice 1, 335 con nice 5, 110 con nice 10 y 15 con nice 19.

Nice 0 frente a nice 1 da $\frac{1024}{1024+820}\approx \mathrm{0,555}$, aproximadamente un 55,5 % frente a un 44,5 %. Las proporciones dependen aproximadamente de la diferencia entre los valores nice: $3121\mathrm{/}1024$ y $335\mathrm{/}110$ son ambos aproximadamente 3,05. Nice +19 compitiendo con nice 0 sigue recibiendo aproximadamente el 1,4 % en este sencillo modelo de dos tareas.

CFS clásico distribuye una latencia de planificación objetivo según el peso:

Para los pesos 1024, 1024 y 335, el total es 2383. Un periodo objetivo de 48 ms da aproximadamente 20,63 ms a cada tarea de mayor peso y 6,75 ms a la de menor peso. Estos parámetros son ilustrativos, no valores predeterminados universales del núcleo. Con cuatro tareas iguales, 48 ms dan 12 ms a cada una. Con diez, 4,8 ms para cada una quedarían por debajo de una granularidad mínima ilustrativa de 6 ms, por lo que el periodo debe crecer.

Contabiliza el progreso virtual

CFS aumenta el tiempo de ejecución virtual de una tarea en ejecución en:

Una tarea con peso 1024 gana un milisegundo virtual por cada milisegundo real. Una tarea con peso 335 gana aproximadamente 3,06. Contabilizar más rápido el progreso de las tareas de menor peso hace que esperen antes, mientras que las de mayor peso reciben más servicio real.

CFS clásico ordena las tareas en cola que pueden ejecutarse en un árbol rojinegro por tiempo de ejecución virtual. La inserción y la eliminación requieren tiempo logarítmico; un puntero almacenado al nodo situado más a la izquierda permite encontrar el mínimo en tiempo constante. Las tareas bloqueadas salen de este árbol de tareas que pueden ejecutarse. La ubicación al despertar limita la posibilidad de que un largo periodo de suspensión se convierta en un derecho ilimitado a recuperar servicio.

Elige entre tareas elegibles con EEVDF

Primero el plazo virtual más temprano entre las tareas elegibles conserva los pesos y la contabilización del servicio virtual. Una tarea tiene déficit de servicio positivo cuando se le debe servicio y negativo cuando ha recibido más de lo que le corresponde. Las tareas con déficit no negativo son elegibles. EEVDF selecciona la tarea elegible con el plazo virtual más temprano.

El plazo combina el inicio virtual de una solicitud con la duración del servicio solicitado ajustada al tiempo virtual. Es un valor para ordenar el servicio, no una promesa de finalización en el tiempo real del reloj. Un intervalo solicitado más corto puede dar a una tarea elegible un plazo más temprano y mejorar la latencia sin aumentar la proporción que le corresponde por su peso a largo plazo. Linux actual admite solicitudes de intervalos mediante sched_setattr().

Varias CPU solo ayudan cuando hay trabajo paralelo. Un solo hilo se ejecuta en una CPU lógica a la vez; varios hilos o programas independientes pueden usar varias CPU juntos. Un planificador debe elegir tanto qué trabajo se ejecuta como dónde se ejecuta.

Comparte la responsabilidad de planificación

En el multiprocesamiento simétrico (SMP), las CPU ejecutan código del núcleo y toman decisiones de planificación por sí mismas. En el multiprocesamiento asimétrico, un procesador principal coordina la planificación mientras los demás ejecutan el trabajo asignado. El control central es más sencillo, pero el procesador principal puede convertirse en un cuello de botella. Los sistemas de propósito general usan SMP.

Las decisiones simultáneas requieren coordinación. Si dos CPU retiran tareas de una cola compartida de trabajos listos, sus actualizaciones deben sincronizarse para que ninguna pierda una entrada ni seleccione dos veces la misma tarea en cola. Más CPU pueden aumentar la contención por esa estructura compartida.

Conserva el contenido útil de las cachés

Los núcleos tienen cachés pequeñas y rápidas, normalmente cachés L1 y L2 privadas y una L3 más grande compartida por varios núcleos. La localidad temporal significa reutilizar datos a los que se accedió recientemente. La localidad espacial significa acceder a datos cercanos, como elementos consecutivos de un arreglo.

Un hilo que ordena datos en el núcleo 0 llena sus cachés y la TLB. Si se reanuda allí después de una breve expropiación, muchas entradas necesarias pueden seguir presentes. En el núcleo 3, puede necesitar recuperar los mismos datos de nuevo de una caché compartida o de la memoria. La afinidad de caché es la tendencia del planificador a mantener un hilo cerca de la CPU que usó recientemente. El beneficio exacto depende de lo que permanezca en caché y de la topología de compartición de cachés.

Distingue la coherencia de la sincronización

La coherencia de caché impide que los núcleos usen indefinidamente copias en caché incompatibles de una misma ubicación de memoria. La observación del bus es una idea de implementación: las cachés observan el tráfico e invalidan o actualizan las copias cuando otro núcleo escribe. Los sistemas más grandes pueden usar otros mecanismos de coherencia.

La coherencia no convierte varias instrucciones en una operación atómica. Si dos CPU leen la longitud de una cola, modifican entradas y vuelven a escribir la longitud, las lecturas y escrituras individuales coherentes siguen permitiendo intercalados perjudiciales. El planificador necesita cerrojos u otro método de sincronización para toda la actualización. La línea de caché compartida de un cerrojo puede moverse entre núcleos mientras compiten por él.

Interpreta la organización del hardware

Intel llama Hyper-Threading a su implementación de SMT. Dos hilos ocupados en CPU lógicas del mismo núcleo compiten por los recursos de ese núcleo; dos CPU lógicas no equivalen a dos núcleos físicos independientes. Una migración en NUMA también puede alejar el cálculo de la memoria que usa, incluso cuando la recuperación de datos en caché es breve.

Mover un hilo a una CPU inactiva puede eliminar una larga demora en la cola. Mantenerlo en su sitio puede conservar la localidad. Compara esos costes usando la carga de trabajo real: la afinidad es una preferencia de rendimiento, mientras que una máscara de afinidad explícita restringe las CPU que se permiten.

Un planificador multiprocesador necesita un lugar donde mantener los trabajos listos. Una sola cola compartida facilita encontrar trabajo. Las colas separadas por CPU reducen la contención por recursos compartidos y conservan la ubicación, pero pueden dejar una CPU sobrecargada mientras otra está inactiva.

Compara los diseños de colas

En la planificación multiprocesador con una sola cola, todas las CPU toman trabajos de una cola compartida. Si los trabajos pueden ejecutarse en cualquier CPU, el trabajo en espera ocupa de forma natural una CPU inactiva. Un cerrojo compartido protege la cola, por lo que aumentar el número de CPU puede convertir ese cerrojo en un cuello de botella.

Con cinco trabajos A–E planificados por turnos en cuatro CPU, una secuencia asigna A, B, C, D en la primera ronda; E, A, B, C en la segunda; y D, E, A, B en la tercera. A se ejecuta en la CPU 0, después en la 1 y después en la 2. La máquina permanece ocupada, pero A cambia repetidamente de cachés privadas. Las reglas de afinidad pueden conservar la mayoría de las ubicaciones mientras mueven trabajos seleccionados para equilibrar la carga.

Detecta proporciones desiguales

En la planificación multiprocesador con múltiples colas, cada CPU planifica su propia cola. Supón que la CPU 0 tiene A y C y la CPU 1 tiene B y D, todos limitados por la CPU y compartiéndola localmente por turnos. Al principio cada trabajo obtiene media CPU. Cuando C termina, A recibe toda la CPU 0 mientras B y D siguen recibiendo cada uno la mitad de la CPU 1.

La máquina sigue utilizándose por completo, pero los trabajos ya no reciben proporciones iguales. Si A también termina, la CPU 0 queda inactiva aunque B y D están listos. Mover uno de ellos a la CPU 0 da a ambos una CPU completa y usa capacidad que antes estaba inactiva.

Con tres trabajos iguales limitados por la CPU y dos CPU, un servicio equitativo a largo plazo es de dos tercios de una CPU por trabajo. Una ubicación fija deja un trabajo solo y dos compartiendo. Alternar periódicamente qué trabajo está solo puede aproximarse al reparto equitativo. Ningún hilo se ejecuta en ambas CPU a la vez.

Decide cuándo migrar

La migración mueve una tarea a la cola de otra CPU. El robo de trabajo es una estrategia de extracción: una CPU con poco trabajo examina la cola de una CPU más ocupada y toma trabajo. Las comprobaciones frecuentes crean tráfico de sincronización; las poco frecuentes dejan el desequilibrio sin resolver. El robo también debe respetar las CPU en las que puede ejecutarse la tarea y la localidad de memoria.

Compara el tiempo de espera que se espera ahorrar con el coste de migración. Una cola larga en una CPU y una CPU compatible inactiva dan una razón de peso para mover trabajo. Una pequeña diferencia temporal entre colas puede desaparecer antes de recuperar los costes de volver a llenar la caché.

Los diseños O(1) y CFS de Linux usaban colas de ejecución por CPU; Linux equilibra la carga entre dominios de planificación de hardware, teniendo en cuenta los núcleos y zócalos compartidos. El planificador alternativo BF Scheduler usaba una sola cola. Los usuarios pueden restringir la ubicación con taskset o sched_setaffinity() en Linux y SetThreadAffinityMask() en Windows. Una máscara de afinidad restrictiva puede explicar por qué una tarea lista no usa una CPU que parece inactiva.

Linux planifica hilos, llamados tareas en el núcleo. La política de planificación, el valor nice, los controles de grupo y la afinidad de CPU de una tarea responden a distintas preguntas sobre cuándo y dónde se ejecuta.

Interpreta primero la política

Las políticas normales tienen prioridad estática 0. FIFO y RR de tiempo real usan 1–99, donde 99 es la más alta. Una tarea FIFO continúa hasta que se bloquea, cede la CPU o un trabajo de mayor prioridad se la expropia. RR añade turnos entre tareas de igual prioridad; sched_rr_get_interval() informa de su cuanto. Estos nombres describen políticas de Linux: la planificación normal equitativa no es el algoritmo RR de intervalos iguales de los manuales.

Cambia las proporciones y la ubicación

Nice va de −20 a +19, con 0 como valor predeterminado. Los valores mayores reducen el peso de la clase equitativa aproximadamente por un factor de 1,25 por paso. En un inicio típico con nice 0, nice -n 10 make inicia una compilación con nice 10; -n es un ajuste al valor nice heredado. renice -n 5 -p 4321 establece nice 5 para el proceso indicado. Un usuario puede hacer que su propio trabajo sea menos favorecido; aumentar la prioridad requiere el privilegio adecuado o un límite de recursos que lo permita.

taskset -c 0,1 ./app permite que un programa se ejecute en las CPU 0 y 1. No crea un segundo hilo ni promete el uso exclusivo de ninguna de las dos CPU. ps -o pid,cls,ni,rtprio,comm muestra campos relacionados con la política, mientras que top ayuda a observar la prioridad, nice y el consumo de CPU.

chrt -f 50 ./app selecciona la prioridad 50 de tiempo real FIFO. Usa la configuración de tiempo real solo en un entorno controlado: un hilo ocupado de alta prioridad puede retrasar el intérprete de comandos y el trabajo esencial del sistema. Los límites predeterminados de ancho de banda de tiempo real reservan algo de tiempo para el trabajo normal, pero no garantizan que todas esas cargas respondan con rapidez. La preferencia cambia el acceso al servicio de CPU, no la velocidad de una instrucción.

Distingue el peso de grupo de la cuota

En cgroup v2, cpu.weight va de 1 a 10 000, con 100 como valor predeterminado, y divide la capacidad de CPU disputada de la clase equitativa entre los grupos activos del mismo nivel. Los pesos 200 y 100 dan aproximadamente dos tercios y un tercio de una CPU cuando ambos grupos están activos. Si el segundo queda inactivo, el primero puede usar toda la capacidad disponible.

cpu.max establece un límite de ancho de banda. El valor «50000 100000» permite 50 ms de tiempo de CPU agregado por periodo de 100 ms, equivalente a media CPU en promedio. Varios hilos pueden consumir ese presupuesto en paralelo y agotarlo antes en tiempo transcurrido. Un grupo limitado puede ver restringida su ejecución incluso cuando existe capacidad de CPU disponible.

Sitúa los nombres en la historia

El planificador O(1) de Linux 2.6.0 usaba arreglos de prioridades y realimentación de interactividad. CFS llegó en la versión 2.6.23 en 2007. Linux 6.6 en 2023 comenzó la transición a la selección EEVDF en la clase equitativa. Desde Linux 6.12 en 2024, sched_ext admite políticas de planificación BPF cargadas dinámicamente en núcleos configurados para ello. Si un planificador de este tipo falla o detiene el avance de trabajos que pueden ejecutarse, el núcleo restaura la planificación integrada.

Windows planifica los hilos listos por prioridad del 0 al 31, con números mayores para mayor prioridad. Los hilos listos de igual prioridad se alternan por turnos. Un hilo de mayor prioridad que acaba de pasar al estado listo expropia la CPU a uno de menor prioridad sin esperar a que termine su cuanto. La prioridad 0 pertenece al hilo de puesta a cero de páginas, que borra las páginas libres.

Obtén la prioridad base a partir de dos ajustes

La prioridad base de un hilo depende de la clase de prioridad de su proceso y de su propio nivel relativo de hilo. Las clases de proceso son Idle, Below normal, Normal, Above normal, High y Realtime. Los niveles de hilo incluyen Idle, Lowest, Below normal, Normal, Above normal, Highest y Time critical.

Time critical da 15 fuera de la clase Realtime y 31 dentro de ella. El nivel de hilo Idle da 1 fuera de Realtime y 16 dentro de ella. Estos niveles extremos son entradas especiales de la tabla, por lo que sumar un desplazamiento fijo a cada clase daría resultados incorrectos.

Sigue una elevación temporal

Las prioridades 1–15 son el intervalo variable; las 16–31 son el intervalo de tiempo real. Un hilo comienza con la prioridad dinámica igual a la prioridad base. Para los hilos del intervalo variable, eventos como una entrada o la finalización de una espera pueden elevar temporalmente la prioridad dinámica. Los hilos con prioridades base de tiempo real no reciben esas elevaciones.

Supón que un hilo con prioridad base 8 se eleva a 14. Si sigue calculando, su prioridad dinámica baja un nivel después de cada cuanto completo: 13 después del primero, 12 después del segundo y 8 después del sexto. La elevación no cambia permanentemente la prioridad base ni disminuye por debajo de ella.

Esto es realimentación: el trabajo desbloqueado recientemente recibe servicio rápido, mientras que el uso continuo de CPU pierde la ventaja temporal. Windows también usa elevaciones temporales para los hilos listos que llevan mucho tiempo esperando, con el fin de combatir la inanición. Una elevación de este tipo puede ayudar a progresar a un titular de cerrojo de baja prioridad, pero es un mecanismo distinto de la herencia de prioridades asociada a un cerrojo.

Reconoce diseños relacionados

La clase de tiempo compartido de Solaris es un diseño MLFQ basado en tablas. ULE de FreeBSD usa colas de ejecución por CPU y compara el comportamiento de suspensión con el de ejecución para identificar hilos interactivos. Estos sistemas comparten la idea de adaptar el servicio al comportamiento observado sin usar reglas de cola idénticas.

macOS proporciona clases de calidad de servicio (QoS), entre ellas interactivo para el usuario, iniciado por el usuario, predeterminado, utilidad y segundo plano. Describen la urgencia del trabajo. En Apple silicon, QoS ayuda al sistema a distribuir el trabajo entre núcleos de rendimiento y de eficiencia. Los programas comunican la importancia del trabajo; el sistema operativo elige la ubicación según la política y el hardware disponible.

Los planificadores reales combinan realimentación, prioridades, equidad y afinidad. Una clase Realtime de Windows tiene mayor preferencia, pero no garantiza un cálculo más rápido ni la corrección completa de tiempo real.

Elige el objetivo de la carga de trabajo antes de elegir un planificador. Una cola de trabajos por lotes puede valorar que muchos trabajos pequeños terminen rápidamente. Un editor necesita atención inmediata después de una entrada. Un servidor compartido necesita una asignación justificable entre usuarios o grupos.

Adapta el mecanismo al objetivo

Compara las políticas con las mismas entradas

A llega en 0 ms y necesita 8 ms, B en 1 ms y necesita 4 ms, y C en 2 ms y necesita 2 ms. Ignora el coste de cambio. FIFO ejecuta A, B, C. SJF también comienza con A, pero después ejecuta C antes que B. STCF ejecuta A 0–1, B 1–2, C 2–4, B 4–7, A 7–14. RR usa un cuanto de 2 ms y coloca las llegadas al final de un intervalo en la cola antes que la tarea cuyo intervalo ha terminado.

STCF gana en ambas métricas con esta carga porque cada nuevo trabajo más corto se ejecuta de inmediato al llegar. RR permite comenzar rápidamente sin conocer las duraciones de las ráfagas. Con llegadas simultáneas de igual duración, FIFO puede tener un tiempo de retorno promedio menor que RR. Una clasificación basada en una carga de trabajo aporta información sobre esa carga.

Elige un método de evaluación

El modelado determinista calcula a mano un seguimiento fijo. Da resultados exactos para sus entradas y facilita examinar las decisiones, pero a menudo omite los costes de despacho y caché. Los modelos de colas describen los patrones de llegada y servicio mediante distribuciones y predicen el comportamiento promedio.

Para un sistema estable en régimen estacionario, la ley de Little relaciona la población promedio $n$, la tasa de llegada $\lambda$ y el tiempo promedio de permanencia $W$:

Con 14 trabajos/s y un tiempo promedio de 0,5 s en el sistema, la población promedio es de 7 trabajos. Mantén coherente el ámbito de medición: una población de la cola de trabajos listos requiere el tiempo de espera en esa cola, mientras que una población de todo el sistema requiere el tiempo en todo el sistema. Convierte las unidades antes de multiplicar.

La simulación ejecuta un modelo del planificador, a menudo con una traza de carga de trabajo registrada. Puede evaluar patrones complejos de llegada y bloqueo, pero sus conclusiones dependen del modelo y de las trazas elegidas. La implementación evalúa el planificador en un sistema operativo real e incluye la sobrecarga real; requiere más esfuerzo y sigue necesitando cargas de trabajo representativas y mediciones repetibles.

Examina la tasa de procesamiento, la utilización, las demoras individuales y de los percentiles altos, la equidad y el consumo de energía junto con los promedios. En un multiprocesador, una máquina ocupada puede seguir repartiendo el servicio de forma desigual o gastar tiempo en rellenar cachés. Compara las políticas usando el mismo intervalo de observación y la misma carga de trabajo y después varía las características de la carga que importan a los usuarios previstos.