Silberschatz 10a castellano cap5

Vista previa del material en texto

Cap 5
Planificación de CPU
La Planificación de la CPU es la base de los sistemas operativos multiprogramados. Cambiando la CPU entre procesos, el sistema operativo puede hacer que la computadora sea más productiva. En este capítulo, presentamos conceptos básicos de Planificación de CPU y presentan varios algoritmos de Planificación de CPU, incluidos los sistemas en tiempo real. También consideramos el problema de seleccionar un algoritmo para un sistema en particular. 
En el Capítulo 4, presentamos hilos al modelo de proceso sistemas, son hilos a nivel de núcleo, no procesos, que de hecho están siendo planificado por el sistema operativo. Sin embargo, los términos "Planificación de procesos" y "Planificación de hilos" a menudo se usan indistintamente. En este capítulo, usamos Planificación de procesos cuando se discuten conceptos generales de Planificación y Planificación de hilos para referirse a ideas específicas de hilo.
De manera similar, en el Capítulo 1 describimos cómo un núcleo es la unidad básica computacional de una CPU, y que un proceso se ejecuta en un núcleo de la CPU. Sin embargo, en muchas instancias en este capítulo, cuando usamos la terminología general de Planificar un proceso para "ejecutarse en una CPU", estamos implicando que el proceso se ejecuta en un Núcleo de la CPU.
OBJETIVOS DEL CAPÍTULO
• Describir varios algoritmos de Planificación de CPU.
• Evaluar algoritmos de Planificación de CPU basados ​​en criterios de Planificación.
• Explicar los problemas relacionados con la Planificación multiprocesador y multinúcleo.
• Describir varios algoritmos de Planificación en tiempo real.
• Describir los algoritmos de Planificación utilizados en Sistemas operativos Windows, Linux y Solaris.
• Aplicar modelos y simulaciones para evaluar algoritmos de Planificación de CPU.
• Diseñar un programa que implemente varios algoritmos de Planificación de CPU diferentes.
Conceptos básicos
En un sistema con un solo núcleo de CPU, solo se puede ejecutar un proceso a la vez. Otros procesos deben esperar hasta que el núcleo de la CPU esté libre y pueda replanificarse. El objetivo de la multiprogramación es tener algún proceso en ejecución en todo momento, para maximizar la utilización de la CPU. La idea es relativamente simple. El proceso se ejecuta hasta que debe esperar, generalmente para completar alguna solicitud de E/S. En un sistema de computador simple, la CPU se queda inactiva. Todo este tiempo de espera se desperdicia; no hay trabajo útil que se lleve a cabo. Con la multiprogramación, tratamos de utilizar este tiempo productivamente.
Varios procesos se guardan en la memoria al mismo tiempo. Cuando un proceso tiene que esperar, el sistema operativo quita la CPU de ese proceso y le da la CPU a otro proceso. Este patrón continúa. Cada vez que un proceso tiene que esperar, otro proceso puede hacerse cargo del uso de la CPU. En un sistema multinúcleo, este concepto de mantener ocupada la CPU se extiende a todos los núcleos de procesamiento en el sistema.
La planificación de esta clase es una función fundamental del sistema operativo. Casi todos los recursos informáticos están planificados antes de su uso. La CPU es, por supuesto, uno de los principales recursos computacionales. Por lo tanto, su planificación es fundamental para el diseño del sistema operativo.
Figura 5.1 Secuencia alterna de ráfagas de CPU y E/S
5.1.1 Ciclo de ráfagas de CPU - E/S
El éxito de la planificación de la CPU depende de una propiedad observada de los procesos:
La ejecución del proceso consiste en un ciclo de ejecución de la CPU y espera por E/S. Los Procesos
alternan entre estos dos estados. La ejecución del proceso comienza con una ráfaga de CPU.
Esto es seguido por una ráfaga de E/S, y luego por otra ráfaga de CPU, y otra ráfaga de E/S, y así sucesivamente. Finalmente, la ráfaga final de la CPU termina con una solicitud de llamada al sistema para finalizar la ejecución (Figura 5.1).
Las duraciones de las ráfagas de CPU se han medido ampliamente. A pesar de que varían mucho de un proceso a otro y de una computadora a otra, tienden a tener una curva de frecuencia similar a la que se muestra en la Figura 5.2. La curva generalmente se caracteriza como exponencial o hiperexponencial, con una gran cantidad de ráfagas cortas de CPU o una pequeña cantidad de ráfagas largas de CPU. 
Un programa limitado por la E/S generalmente tiene muchas ráfagas cortas de CPU. 
Un programa limitado por CPU podría tener algunas ráfagas de CPU largas. 
Esta distribución puede ser importante al implementar un algoritmo de planificación de CPU.
5.1.2 Planificador de CPU
Cada vez que la CPU queda inactiva, el sistema operativo debe seleccionar uno de los procesos en la lista de espera para ser ejecutados. El proceso de selección se lleva a cabo por el planificador de la CPU, que selecciona un proceso de los procesos que están listos en memoria para ejecutarse y asignan la CPU a ese proceso.
Tenga en cuenta que la cola lista no es necesariamente una cola de primero en entrar, primero en salir (FIFO).
Como veremos cuando consideremos los diversos algoritmos de planificación, una lista
la cola se puede implementar como una cola FIFO, una cola prioritaria, un árbol o simplemente
una lista enlazada desordenada Conceptualmente, sin embargo, todos los procesos están listos
la cola está alineada esperando la oportunidad de ejecutarse en la CPU. Los registros en el
Las colas son generalmente bloques de control de proceso (PCB) de los procesos.
5.1.3 Planificación apropiativa y no apropiativa
Las decisiones de Planificación de la CPU pueden tener lugar en las siguientes cuatro circunstancias:
1. Cuando un proceso cambia del estado de ejecución al estado de espera (por ejemplo, como resultado de una solicitud de E/S o una invocación de wait () para esperar la terminación de un proceso hijo)
2. Cuando un proceso cambia del estado de ejecución al estado listo (por ejemplo, cuando ocurre una interrupción)
3. Cuando un proceso cambia del estado de espera al estado listo (para ejemplo, al finalizar la E/S)
4. Cuando termina un proceso
Por las situaciones 1 y 4, no hay otra opción en términos de planificación: un nuevo proceso (si existe uno en la cola lista) debe seleccionarse para su ejecución. Pero para las situaciones 2 y 3, puede haber otra opción.
Cuando la Planificación se lleva a cabo solo en las circunstancias 1 y 4, decimos que el esquema de Planificación no es apropiativo o cooperativo. De lo contrario, es apropiativo. Bajo la Planificación no apropiativa, una vez que la CPU ha sido asignada a un proceso, el proceso mantiene la CPU hasta que la libera cuando termina o cambia al estado de espera. Prácticamente todos los sistemas operativos modernos.
Windows, macOS, Linux y UNIX utilizan algoritmos de Planificación apropiativos.
Desafortunadamente, la Planificación apropiativa puede generar condiciones de carrera cuando los datos se comparten entre varios procesos. Considere el caso de dos procesos que comparten datos mientras un proceso está actualizando los datos, y el kernel le quita la CPU para darle al otro proceso. El segundo proceso luego intenta leer el datos, que están en un estado inconsistente. Este problema será explorado en detalle en el Capítulo 6.
La expulsión también afecta el diseño del kernel del sistema operativo. Durante el procesamiento de una llamada del sistema, el kernel puede estar ocupado con una actividad en nombre de un proceso. Dichas actividades pueden implicar el cambio de datos importantes en el kernel (por ejemplo, colas de E/S). ¿Qué sucede si el proceso se expulsa en medio de estos cambios y el kernel (o el controlador del dispositivo) necesita leer o modificar la misma estructura? Se produce el caos. Como se discutirá en Sección 6.2, los kernels del sistema operativo pueden diseñarse como no apropiativos o apropiativo. Un kernel no apropiativo esperará a que se complete una llamada al sistema o hasta que se bloquee un proceso, mientras se espera que se complete la E/S antes que se haga un cambio de contexto.Este esquema asegura que la estructura del kernel sea simple, ya que el kernel no expulsará a un proceso mientras las estructuras de datos del kernel están en un estado inconsistente. Desafortunadamente, este modelo de ejecución de kernel es pobre para soportar la computación en tiempo real, donde las tareas deben completar la ejecución dentro de un marco de tiempo dado. En la Sección 5.6, exploramos las demandas de Planificación de sistemas en tiempo real. Un kernel apropiativo requiere mecanismos como bloqueos mutex para evitar condiciones de carrera al acceder a estructuras de datos de kernel compartidas.
La mayoría de los sistemas operativos modernos ahora son totalmente apropiativos cuando se ejecutan en modo kernel.
Porque las interrupciones pueden, por definición, ocurrir en cualquier momento, y porque el kernel no siempre puede ser ignorado, las secciones de código afectadas por interrupciones deben protegerse del uso simultáneo. El sistema operativo necesita aceptar interrupciones en casi todo momento. De lo contrario, la entrada podría perderse o terminar sobrescrito Para que estas secciones de código no sean accedidas simultáneamente por varios procesos, deshabilitan las interrupciones en la entrada y vuelven a habilitar las interrupciones a la salida. Es importante tener en cuenta que las secciones de código que deshabilitan las interrupciones no ocurren muy a menudo y típicamente contienen pocas instrucciones.
5.1.4 Despachador
Otro componente involucrado en la función de planificación de la CPU es el despachador.
El despachador es el módulo que da control de la CPU al proceso seleccionado por el planificador de la CPU. Esta función implica lo siguiente:
• Cambiar el contexto de un proceso a otro
• Cambiar al modo de usuario
• Saltar a la ubicación adecuada en el programa de usuario para reanudar ese programa.
El despachador debe ser lo más rápido posible, ya que se invoca durante cada cambio de contexto. El tiempo que tarda el despachador en detener un proceso y comenzar otra ejecución se conoce como latencia de despacho y se ilustra en la Figura 5.3.
Figura 5.3 El papel del despachador.
Una pregunta interesante a considerar es, ¿con qué frecuencia ocurren los cambios de contextos? A nivel de todo el sistema, se puede obtener el número de cambios de contexto utilizando el comando vmstat que está disponible en sistemas Linux. Abajo se muestra la salida (que se ha recortado) del comando:
vmstat 1 3
Este comando proporciona 3 líneas de salida en un lapso de 1 segundo:
------cpu-----
24
225
339
La primera línea muestra el número promedio de cambios de contexto durante 1 segundo desde el inicio del sistema, y las siguientes dos líneas dan el número de cambios de contexto en dos intervalos de 1 segundo. Desde que esta máquina arrancó, ha promediado 24 cambios de contexto por segundo. Y en el último segundo, se hicieron 225 cambios de contexto, con 339 cambios de contexto en el segundo anterior a eso.
También podemos usar el sistema de archivos /proc para determinar el número de cambios de contexto para un proceso dado. Por ejemplo, el contenido del archivo /proc /2166/status enumerará varias estadísticas para el proceso con pid = 2166. El comando:
cat /proc/2166/status
proporciona el siguiente resultado recortado:
voluntary ctxt switches 150
nonvoluntary ctxt switches 8
Este resultado muestra el número de cambios de contexto durante la vida útil del proceso. Observe la distinción entre cambio de contexto voluntario y no voluntario. Un cambio de contexto voluntario ocurre cuando un proceso ha dejado el control de la CPU porque requiere un recurso que actualmente no está disponible (como cuando se bloquea en una E/S). Se produce un cambio de contexto no voluntario cuando la CPU ha sido retirada de un proceso, como cuando su intervalo de tiempo ha expirado o ha sido reemplazado por un proceso de mayor prioridad.
5.2 Criterios de planificación
Diferentes algoritmos de planificación de CPU tienen diferentes propiedades, y la elección de un algoritmo particular puede favorecer una clase de procesos sobre otra. Al elegir qué algoritmo usar en una situación particular, debemos considerar las propiedades de los diversos algoritmos.
Se han sugerido muchos criterios para comparar algoritmos de planificación de CPU.
¿Cuáles características deben utilizarse para la comparación? Eso puede hacer un sustancial diferencia sobre qué algoritmo se considera mejor. Los criterios incluyen lo siguiente:
• Utilización de la CPU. Queremos mantener la CPU lo más ocupada posible. Conceptualmente la utilización de la CPU puede variar de 0 a 100 por ciento. En un sistema real, esto debe variar entre el 40% (para un sistema con poca carga) y el 90 por ciento (para un sistema muy cargado). (La utilización de la CPU se puede obtener utilizando el comando top en sistemas Linux, macOS y UNIX).
• Rendimiento. Si la CPU está ocupada ejecutando procesos, entonces se está haciendo trabajo. Una medida del trabajo es la cantidad de procesos que se completan por unidad de tiempo, se llama rendimiento. Para procesos largos, esta tasa puede ser un proceso en varios segundos; para transacciones cortas, puede ser decenas de procesos por segundo.
• Tiempo de retorno. Desde el punto de vista de un proceso particular, un criterio importante es cuánto tiempo lleva ejecutar ese proceso. El intervalo desde el momento de la llegada de un proceso hasta el momento de finalización es el tiempo de respuesta El tiempo de actividad de un proceso es la suma de los períodos de espera en la cola lista, ejecutándose en la CPU y haciendo E/S.
• Tiempo de espera. El algoritmo de planificación de la CPU no afecta la cantidad de tiempo durante el cual un proceso ejecuta o realiza una E/S. Afecta solo a la cantidad de tiempo que un proceso pasa esperando en la lista de espera. El tiempo es la suma de los períodos de espera en la lista de espera.
• Tiempo de respuesta. En un sistema interactivo, el tiempo total de un proceso puede no ser el mejor criterio. A menudo, un proceso puede producir un resultado parcial pronto y puede continuar calculando nuevos resultados mientras se están obteniendo resultados de salida al usuario. Por lo tanto, otra medida es el tiempo desde la presentación de una solicitud hasta que se produzca la primera respuesta. Esta medida, llamada tiempo de respuesta, es el tiempo que lleva en comenzar a responder, no el tiempo que lleva para dar salida a la respuesta completa.
Es deseable maximizar la utilización y el rendimiento de la CPU y minimizar el tiempo de retorno, tiempo de espera y tiempo de respuesta. En la mayoría de los casos, optimizamos la medida promedio. Sin embargo, en algunas circunstancias, preferimos optimizar los valores mínimos o máximos en lugar del promedio. Por ejemplo, para garantizar que todos los usuarios obtengan un buen servicio, podemos minimizar el Tiempo máximo de respuesta.
Los investigadores han sugerido que, para sistemas interactivos (como una PC o sistema de escritorio o portátil), es más importante minimizar la varianza del tiempo de respuesta que minimizar el promedio del tiempo de respuesta. Un sistema con un tiempo de respuesta razonable y predecible puede considerarse más deseable que un sistema que es más rápido en promedio pero es muy variable. Sin embargo, poco se ha trabajado en algoritmos de planificación de CPU que minimizan la varianza.
Mientras discutimos varios algoritmos de planificación de CPU en la siguiente sección, Ilustramos su funcionamiento. Una ilustración precisa debería involucrar a muchos procesos, donde cada uno tenga una secuencia de varios cientos de ráfagas de CPU y ráfagas de E/S.
Sin embargo, para simplificar, consideramos solo una ráfaga de CPU (en milisegundos) por proceso en nuestros ejemplos. Nuestra medida de comparación es el tiempo de espera promedio. En la Sección 5.8 se analizan mecanismos de evaluación más elaborados.
5.3 Algoritmos de planificación
La planificación de la CPU aborda el problema de decidir cuál de los procesos en la cola deprocesos listos debe asignarse al núcleo de la CPU. Hay muchos algoritmos de planificación de CPU diferentes. En esta sección, describimos varios de ellos. A pesar de que la mayoría de las arquitecturas de CPU modernas tienen múltiples núcleos de procesamiento, describimos estos algoritmos de planificación en el contexto de un solo núcleo de procesamiento disponible. Es decir, una sola CPU que tiene un sólo núcleo de procesamiento, por lo tanto, el sistema es capaz de ejecutar sólo un proceso a la vez. En la Sección 5.5 discutimos la planificación CPU en el contexto de sistemas multiprocesador.
5.3.1 Planificación por orden de llegada
De lejos, el algoritmo de planificación de CPU más simple es el primero en llegar (FCFS) algoritmo de planificación. Con este esquema, el proceso que solicita primero se le asigna la CPU primero. La implementación de la política de FCFS se gestiona fácilmente con una cola FIFO. Cuando un proceso entra en la cola lista, su PCB está vinculado al final de la cola. Cuando la CPU está libre, se le asigna al proceso de la cabecera de la cola. El proceso en ejecución se elimina de la cola. El código para la planificación de FCFS es simple de escribir y comprender. En el lado negativo, el tiempo de espera promedio bajo la política FCFS es a menudo bastante largo. Considere el siguiente conjunto de procesos que llegan al tiempo 0, con la longitud de la ráfaga de CPU dada en milisegundos:
Process 	Burst Time
P1		 	24
P2 			3
P3 			3
Si los procesos llegan en el orden P1, P2, P3 y se sirven en el orden FCFS, obtenemos el resultado que se muestra en el siguiente gráfico de Gantt, que es un gráfico de barras que ilustra un horario particular, que incluye las horas de inicio y finalización de cada uno de los procesos participantes:
El tiempo de espera es de 0 milisegundos para el proceso P1, 24 milisegundos para el proceso P2 y 27 milisegundos para el proceso P3. Por lo tanto, el tiempo de espera promedio es (0 + 24 + 27)/3= 17 milisegundos. Si los procesos llegan en el orden P2, P3, P1, sin embargo, los resultados serán los que se muestran en el siguiente diagrama de Gantt:
El tiempo de espera promedio es ahora (6 + 0 + 3) / 3 = 3 milisegundos. Esta reducción es sustancial. Por lo tanto, el tiempo promedio de espera bajo una política de FCFS generalmente no es mínimo y puede variar sustancialmente si los tiempos de ráfaga de CPU de los procesos varían Además, considere el rendimiento de la planificación FCFS en una dinámica situación. Supongamos que tenemos un proceso limitado a la CPU y muchos procesos limitados a E/S. A medida que los procesos fluyen por el sistema, el siguiente escenario puede resultar. El proceso limitado a la CPU obtendrá y mantendrá la CPU. Durante este tiempo, todos los otros procesos terminarán su E/S y pasarán a la cola lista, esperando la CPU. Mientras los procesos esperan en la cola lista, los dispositivos de E/S están inactivos. Finalmente, el proceso limitado a la CPU termina su ráfaga de CPU y se mueve a un dispositivo de E/S. Todos los procesos limitados a E/S, que tienen ráfagas cortas de CPU, ejecutan rápidamente y vuelven a las colas de E/S. En este punto, la CPU se encuentra inactiva. El proceso limitado a la CPU volverá a la cola de listos y se le asignará la CPU. Nuevamente, todos los procesos de E/S terminan esperando en la lista de espera hasta que finalice el proceso limitado a la CPU. Hay un efecto convoy ya que todos los demás procesos esperan el gran proceso para salir de la CPU. Este efecto da como resultado una menor utilización de la CPU y del dispositivo de lo que podría ser posible si se permite que los procesos fueran primero.
Tenga en cuenta también que el algoritmo de programación FCFS no es preventivo. Una vez que La CPU se ha asignado a un proceso, ese proceso mantiene la CPU hasta que la libera, ya sea terminando o solicitando E/S. El algoritmo FCFS es así particularmente problemático para sistemas interactivos, donde es importante que cada proceso obtenga una parte de la CPU a intervalos regulares. Sería desastroso permitir que un proceso mantenga la CPU durante un período prolongado.
5.3.2 Planificación de trabajo más corto primero
Un enfoque diferente para la Planificación de la CPU es el algoritmo de Planificación de trabajos más cortos primero (SJF). Este algoritmo asocia con cada proceso la longitud de la próxima ráfaga de CPU del proceso. Cuando la CPU está disponible, se asigna al proceso que tiene la próxima ráfaga de CPU más pequeña. Si las siguientes ráfagas de CPU de dos procesos tienen la misma ráfaga, se utiliza la Planificación FCFS para romper el empate. Tenga en cuenta que más apropiado sería el término para este método: “Algoritmo de Planificación por la ráfaga de CPU más corta”, porque la Planificación depende de la duración de la próxima ráfaga de CPU de un proceso, en lugar de su longitud total. Utilizamos el término SJF porque la mayoría de los libros de texto usan este término para referirse a este tipo de Planificación.
Como ejemplo de Planificación SJF, considere el siguiente conjunto de procesos, con la longitud de la ráfaga de CPU dada en milisegundos:
Process 	Burst Time
P1 			6
P2 			8
P3 			7
P4 			3
Usando la Planificación SJF, planificaríamos estos procesos de acuerdo con el siguiente diagrama de Gantt:
El tiempo de espera es de 3 milisegundos para el proceso P1, 16 milisegundos para el proceso P2, 9 milisegundos para el proceso P3 y 0 milisegundos para el proceso P4. Por lo tanto, el tiempo de espera promedio es (3 + 16 + 9 + 0) / 4 = 7 milisegundos. En comparación, si estuviéramos usando el esquema de planificación FCFS, el tiempo de espera promedio sería ser 10.25 milisegundos. El algoritmo de Planificación SJF es demostrablemente óptimo, ya que proporciona el mínimo tiempo de espera promedio para un conjunto dado de procesos. Priorizando un proceso corto antes de que uno largo disminuye el tiempo de espera del proceso corto más y aumenta el tiempo de espera del proceso largo. En consecuencia, el promedio el tiempo de espera disminuye.
Aunque el algoritmo SJF es óptimo, no se puede implementar a nivel de Planificación de CPU, ya que no hay forma de saber la duración de la próxima ráfaga de CPU. Un enfoque para este problema es tratar de aproximar la Planificación SJF. No sabemos la duración de la próxima ráfaga de CPU, pero es posible que podamos predecir su valor. Por ejemplo, Esperamos que la próxima ráfaga de CPU sea similar en longitud a la anterior unos. Al calcular una aproximación de la longitud de la próxima ráfaga de CPU, nosotros podemos elegir el proceso con la ráfaga de CPU pronosticada más corta.
La siguiente ráfaga de CPU generalmente se predice como un promedio exponencial de las longitudes medidas de las ráfagas de CPU anteriores. Podemos definir la exponencial promedio con la siguiente fórmula. Sea tn la longitud de la enésima ráfaga de CPU, y deje que τn + 1 sea nuestro valor predicho para la próxima ráfaga de CPU. Entonces, para α, 0 ≤ α ≤ 1, se define:
τn+1 = α tn + (1 − α)τn.
El valor de tn contiene nuestra información más reciente, mientras que τn almacena la historia pasada. El parámetro α controla el peso relativo de la historia reciente y pasada en nuestra predicción Si α = 0, entonces τn + 1 = τn, y el historial reciente no tiene efecto (se supone que las condiciones actuales son transitorias). Si α = 1, entonces τn + 1 = tn, y sólo importa la ráfaga de CPU más reciente (se supone que el historial es antiguo e irrelevante). Más comúnmente, α = 1/2, por lo que la historia reciente y la historia pasada tienen el mismo peso. La τ0 inicial se puede definir como una constante o como un promedio general del sistema La figura 5.4 muestra un promedio exponencial con α = 1/2 y τ0 = 10.
Figura 5.4 Predicción de la duración de la próxima ráfaga de CPU.
Para comprender el comportamiento del promedio exponencial, podemos expandir la fórmula para τn + 1 sustituyendo por τn para encontrar
τn+1 = αtn + (1 − α)αtn−1 + · · · + (1 − α)jαtn−j + · · ·+(1 − α)n+1τ0.
Típicamente,α es menor que 1. Como resultado, (1 - α) también es menor que 1, y cada término sucesivo tiene menos peso que su predecesor.
El algoritmo SJF puede ser apropiativo o no apropiativo. La elección surge cuando un nuevo proceso llega a la cola lista mientras que un proceso anterior todavía se está ejecutando. La próxima ráfaga de CPU del proceso recién llegado puede ser más corta de lo que queda del proceso actualmente en ejecución. Un algoritmo apropiativo SJF expulsará al proceso que se está ejecutando actualmente, mientras que un algoritmo SJF no apropiativo permitirá que el proceso actualmente en ejecución termine su ráfaga de la CPU. La planificación SJF apropiativa a veces se llama el tiempo más corto restante planificación de abetos.
Como ejemplo, considere los siguientes cuatro procesos, con la longitud de la ráfaga de CPU dada en milisegundos:
Process 	Arrival Time 	Burst Time
P1 		0 		8
P2 		1 		4
P3 		2 		9
P4 		3		5
Si los procesos llegan a la cola lista en los momentos indicados y necesitan los tiempos de ráfaga indicados, entonces el cronograma del SJF apropiativo resultante es como se muestra en el siguiente diagrama de Gantt:
El proceso P1 se inicia en el momento 0, ya que es el único proceso en la cola. Proceso P2 llega en el momento 1. El tiempo restante para el proceso P1 (7 milisegundos) es mayor que el tiempo requerido por el proceso P2 (4 milisegundos), entonces el proceso P1 toma la CPU, y el proceso P2 se planifica. El tiempo de espera promedio para este ejemplo es [(10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)] / 4 = 26/4 = 6.5 milisegundos.
La planificación SJF no apropiatva daría como resultado un tiempo de espera promedio de 7.75 milisegundos.
5.3.3 Planificación Round-Robin
El algoritmo de planificación round-robin (RR) es similar a la planificación FCFS, pero se le agrega apropiatividad para permitir que el sistema cambie entre procesos. Se define una unidad de tiempo pequeña, denominada cuanto de tiempo o rodaja de tiempo. Un cuanto de tiempo es generalmente de 10 a 100 milisegundos. La cola lista se trata como una cola circular. El planificador de la CPU recorre la cola, asignando la CPU a cada proceso durante un intervalo de tiempo de hasta 1 cuanto de tiempo.
Para implementar la planificación RR, nuevamente tratamos la cola lista como cola FIFO de procesos. Se agregan nuevos procesos a la cola lista.
El planificador de la CPU selecciona el primer proceso de la cola lista, establece un temporizador para interrumpir después de 1 cuanto de tiempo, y despacha el proceso.
Entonces sucederá una de dos cosas. El proceso puede tener una expulsión de CPU de menos de 1 cuanto de tiempo. En este caso, el proceso mismo liberará la CPU voluntariamente. El planificador procederá al siguiente proceso en la cola lista. Si la ráfaga de CPU del proceso actualmente en ejecución es más de 1 cuanto, venncerá el temporizador y provocará una interrupción en el funcionamiento del sistema. Se ejecutará un cambio de contexto y el proceso se colocará en cola de la cola lista. El planificador de la CPU luego seleccionará el siguiente proceso en la cola lista.
El tiempo promedio de espera bajo la política RR suele ser largo. Considera el siguiente conjunto de procesos que llegan al tiempo 0, con la duración de ráfagas de CPU dadas en milisegundos:
Process 	Burst Time
P1 			24
P2 			 3
P3 			 3
Si usamos un cuanto de tiempo de 4 milisegundos, el proceso P1 obtiene los primeros 4 milisegundos y como requiere otros 20 milisegundos, se lo expulsa después del primer cuanto, y la CPU se entrega al siguiente proceso en la cola, el proceso P2. El proceso P2 no necesita 4 milisegundos, por lo que se retira antes que el cuanto de tiempo expire. La CPU pasa al siguiente proceso, el proceso P3. Una vez cada proceso ha recibido 1 cuanto de tiempo, la CPU vuelve al proceso P1 por un cuanto de tiempo adicional. El planificador RR resultante es el siguiente:
Calculemos el tiempo de espera promedio para esta planificación. P1 espera 6 milisegundos (10-4), P2 espera 4 milisegundos y P3 espera 7 milisegundos. Por lo tanto, el tiempo de espera promedio es 17/3 = 5.66 milisegundos.
En el algoritmo de planificación RR, no se asigna ningún proceso a la CPU por más de 1 cuanto de tiempo en una vuelta (a menos que sea el único proceso ejecutable). Si la ráfaga de CPU del proceso supera 1 cuanto, ese proceso se expulsa y se pone de nuevo en la lista de espera. El algoritmo de planificación RR es, por lo tanto, apropiativo.
Si hay n procesos en la cola lista y el cuanto de tiempo es q, entonces cada proceso obtiene 1/n del tiempo de CPU en fragmentos de como máximo q unidades de tiempo. Cada proceso no debe esperar más de (n - 1) × q unidades de tiempo hasta su próxima cantidad de tiempo. Por ejemplo, con cinco procesos y un tiempo cuanto de 20 milisegundos, cada proceso obtendrá hasta 20 milisegundos cada 100 milisegundos.
El rendimiento del algoritmo RR depende en gran medida del tamaño del cuanto de tiempo. En un extremo, si el tiempo del cuanto es extremadamente grande, la política RR es la misma que la política FCFS. Por el contrario, si el tiempo cuanto es extremadamente pequeño (digamos, 1 milisegundo), el enfoque RR puede resultar en un gran Número de cambios de contexto. Supongamos, por ejemplo, que solo tenemos un proceso de 10 unidades de tiempo. Si el cuanto es de 12 unidades de tiempo, el proceso termina en menos de 1 cuanto de tiempo, sin sobrecarga. Si el cuanto es de 6 unidades de tiempo, sin embargo, el proceso requiere 2 cuantos, lo que resulta en un cambio de contexto. Si el tiempo de cuanto es de 1 unidad de tiempo, entonces ocurrirán nueve cambios de contexto, disminuyendo la velocidad ejecución del proceso en consecuencia (Figura 5.5).
Figura 5.5 Cómo una cantidad de tiempo menor aumenta los cambios de contexto.
Por lo tanto, queremos que el cuanto de tiempo sea grande con respecto al tiempo de cambio de contexto. Si el tiempo de cambio de contexto es aproximadamente el 10 por ciento del cuanto de tiempo, entonces aproximadamente el 10 por ciento del tiempo de CPU se gastará en cambio de contexto. En la práctica, la mayoría de los sistemas modernos tienen cantidades de tiempo que van desde 10 a 100 milisegundos. El tiempo requerido para un cambio de contexto suele ser menor de 10 microsegundos; por lo tanto, el tiempo de cambio de contexto es una pequeña fracción del cuanto de tiempo.
El tiempo de retorno también depende del tamaño del cuanto de tiempo. Como podemos ver en la Figura 5.6, el tiempo de retorno promedio de un conjunto de procesos no necesariamente mejora a medida que aumenta el tamaño del cuanto de tiempo. En general, el tiempo de retorno promedio puede mejorarse si la mayoría de los procesos finalizan su siguiente ráfaga de CPU en un solo cuanto de tiempo. Por ejemplo, dados tres procesos de 10 unidades de tiempo cada uno y un cuanto de 1 unidad de tiempo, el tiempo de retorno promedio el tiempo es 29. Sin embargo, si el 
tiempo cuanto es 10, el tiempo de retorno promedio cae a 20. Si se agrega el tiempo de cambio de contexto, el tiempo de retorno promedio aumenta aún más para un cuanto de tiempo más pequeño, ya que habrá más cambios de contexto.
Figura 5.6 Cómo varía el tiempo de respuesta con el cuanto de tiempo.
Aunque el cuanto de tiempo debe ser grande en comparación con el tiempo de cambio de contexto, no debería ser demasiado grande. Como señalamos anteriormente, si el Quantum de tiempo es demasiado grande, la planificación RR degenera en una política FCFS. Una regla práctica es que el 80 por ciento de las ráfagas de CPU deben ser más cortas que el cuanto de tiempo.
5.3.4 Planificación prioritaria
El algoritmo SJF es un caso especial del algoritmo de planificación de prioridad general. Se asocia una prioridad a cada proceso y la CPU se asigna al proceso con la máxima prioridad. Los procesos de igual prioridad se planifican en Orden de FCFS. Un algoritmo SJF es simplemente un algoritmo de prioridad donde la prioridad (p) es el inverso de la próxima ráfaga de CPU (prevista). Cuantomás grande es la ráfaga de la CPU, menor será la prioridad, y viceversa.
Tenga en cuenta que discutimos la planificación en términos de alta prioridad y baja prioridad. Las prioridades generalmente se indican mediante un rango fijo de números, como 0 a 7 o 0 a 4.095. Sin embargo, no existe un acuerdo general sobre si 0 es la Máxima o Mínima prioridad. Algunos sistemas usan números bajos para representar bajas prioridad; otros usan números bajos para alta prioridad. Esta diferencia puede conducir a confusión. En este texto, suponemos que los números bajos representan alta prioridad. Como ejemplo, considere el siguiente conjunto de procesos, que se supone que tienen llegó en el momento 0 en el orden P1, P2, · · ·, P5, con la longitud de la ráfaga de CPU dada en milisegundos:
Process 	Burst Time 	Priority
P1 		10 		3
P2 		1 		1
P3 		2 		4
P4 		1 		5
P5 		5 		2
Usando la planificación prioritaria, planificaríamos estos procesos de acuerdo con el siguiente diagrama de Gantt:
El tiempo de espera promedio es de 8.2 milisegundos.
Las prioridades se pueden definir internamente o externamente. Las prioridades definidas internamente usan una cantidad o cantidades medibles para calcular la prioridad de un proceso. Por ejemplo, límites de tiempo, requisitos de memoria, el número de archivos abiertos, y la relación entre el promedio de las ráfagas de E/S y el promedio de las ráfagas de CPU que han utilizado en la computación. Las prioridades externas se establecen por criterios fuera del sistema operativo, como la importancia del proceso, el tipo y el monto que se paga por el uso de la computadora, el departamento que patrocina el trabajo, y otros factores, a menudo políticos.
La planificación de prioridad puede ser apropiativa o no apropiativa. Cuando el proceso llega a la cola lista, su prioridad se compara con la prioridad del proceso actualmente en ejecución. Un Algoritmo de planificación de prioridad apropiativa de la CPU, si la prioridad del proceso recién llegado es mayor que la prioridad del proceso actualmente en ejecución. Con el algoritmo de Planificación de prioridad no apropiativa, simplemente colocará el nuevo proceso al frente de la cola lista.
Un problema importante con los algoritmos de planificación prioritarios es el bloqueo indefinido, o inanición. Un proceso que está listo para ejecutarse pero que espera por la CPU pueda ser considerado bloqueado. Un algoritmo de planificación prioritario puede dejar a Procesos de baja prioridad en espera indefinida. En un sistema informático muy cargado, el flujo constante de procesos de mayor prioridad puede evitar a un proceso de baja prioridad obtener la CPU. En general, una de dos cosas sucederá: Ya sea el proceso finalmente se ejecutará (a las 2 a.m. del domingo, cuando el sistema finalmente esté ligeramente cargado), o el sistema informático eventualmente se trabará (pantalla azul) y perderá todo lo que no esté terminado de procesos de baja prioridad. (Se rumorea que cuando cerraron el IBM 7094 en el MIT en 1973, encontraron un proceso de baja prioridad que se había presentado en 1967 y aún no se había ejecutado.). 
Una solución al problema del bloqueo indefinido de procesos de baja prioridad es el denominado “envejecimiento”. El envejecimiento implica aumentar gradualmente la prioridad de los procesos que esperan en el sistema durante mucho tiempo. Por ejemplo, si las prioridades oscilan entre 127 (bajo) a 0 (alto), podríamos aumentar periódicamente (por ejemplo, cada segundo) la prioridad de un proceso de espera en 1. Eventualmente, incluso un proceso con una prioridad inicial de 127 tendría la más alta prioridad en el sistema y sería ejecutado. De hecho, tomaría un poco más de 2 minutos para que un proceso de prioridad 127 envejezca a un proceso de prioridad 0.
Otra opción es combinar planificación round-robin y prioritaria de tal forma que el sistema ejecuta el proceso de mayor prioridad y elija procesos con la misma prioridad usando la planificación round robin. Vamos a ilustrar con un ejemplo usando el siguiente conjunto de procesos, con el tiempo de ráfaga en milisegundos:
Process 	Burst Time 	Priority
P1 		4 		3
P2 		5 		2
P3 		8 		2
P4 		7 		1
P5 		3 		3
Usando la planificación de prioridad con round-robin para procesos con igual prioridad, planificaríamos estos procesos de acuerdo con el siguiente diagrama de Gantt usando un tiempo de cuanto de 2 milisegundos:
En este ejemplo, el proceso P4 tiene la máxima prioridad, por lo que se ejecutará hasta su finalización. Los procesos P2 y P3 tienen la siguiente prioridad más alta, y se ejecutarán en round robin. Observe que cuando el proceso P2 finaliza en el momento 16, el proceso P3 es el proceso de mayor prioridad, por lo que se ejecutará hasta que complete la ejecución. Ahora, solo quedan los procesos P1 y P5, y como tienen la misma prioridad, se ejecutará en orden round-robin hasta que se completen.
5.3.5 Planificación de cola multinivel
Tanto con la prioridad como con la planificación de turnos (round robin), todos los procesos pueden colocarse en una sola cola, y el planificador luego selecciona el proceso con la más alta prioridad para ejecutar. Dependiendo de cómo se gestionan las colas, una búsqueda O (n) puede ser necesaria para determinar el proceso de mayor prioridad. En la práctica, a menudo es más fácil tener colas separadas (una por cada prioridad distinta) y la planificación prioritaria simplemente planifica el proceso en la cola de mayor prioridad. Esta se ilustra en la figura 5.7. Este enfoque, conocido como cola multinivel, también funciona bien cuando la planificación prioritaria se combina con round-robin: si hay varios procesos en la cola de mayor prioridad, se ejecutan en orden de todos contra todos. En la forma más generalizada de este enfoque, una prioridad se asigna estáticamente a cada proceso, y un proceso permanece en la misma cola por la duración de su tiempo de ejecución.
Figura 5.7 Colas separadas para cada prioridad
Un algoritmo de planificación de colas multinivel también se puede utilizar para particionar procesos en varias colas separadas según el tipo de proceso (Figura 5.8). Por ejemplo, se hace una división entre procesos de primer plano (interactivo) y procesos de fondo (lote). Estos dos tipos de procesos tienen diferentes requisitos de tiempo de respuesta y, por lo tanto, pueden tener diferentes necesidades de planificación. Además, los procesos en primer plano pueden tener prioridad (externamente definida) sobre procesos en segundo plano. Se pueden usar colas separadas para procesos en primer plano y en segundo plano, y cada cola puede tener su propio algoritmo de planificación. La cola de primer plano puede ser planificada por un algoritmo RR, por ejemplo, mientras la cola en segundo plano está planificada por un algoritmo FCFS.
Además, debe haber una planificación entre las colas, que es comúnmente implementado como planificación apropiativa de prioridad fija. Por ejemplo, la cola en tiempo real puede tener prioridad absoluta sobre la cola interactiva.
Veamos un ejemplo de un algoritmo de planificación de colas multinivel con cuatro colas, enumeradas a continuación en orden de prioridad:
1. Procesos en tiempo real
2. Procesos del sistema
3. Procesos interactivos
4. Procesos por lotes
Cada cola tiene prioridad absoluta sobre las colas de menor prioridad. Ningún proceso en la cola por lotes, por ejemplo, podría ejecutarse a menos que las colas para procesos en tiempo real, procesos del sistema y procesos interactivos estén todas vacías. Si un proceso interactivo ingresó a la lista de espera mientras se ejecutaba un proceso por lotes, el proceso en lote se expulsaría.
Otra posibilidad es dividir el tiempo entre las colas. Aquí, cada cola obtiene una cierta porción del tiempo de CPU, que luego puede planificar entre sus diferentes procesos. Por ejemplo, en el ejemplo de cola de primer plano y fondo, la cola en primer plano puede recibir el 80 por ciento del tiempo de CPU para la planificación de RR entre sus procesos, mientras que la cola de fondo (batch)recibe el 20 por ciento de la CPU para dar a sus procesos sobre una orden FCFS.
5.3.6 Planificación de cola de retroalimentación multinivel
Normalmente, cuando se utiliza el algoritmo de planificación de colas multinivel, los procesos se asignan permanentemente a una cola cuando ingresan al sistema. Sí hay colas separadas para procesos en primer plano y en segundo plano, por ejemplo, los procesos no se mueven de una cola a otra, ya que los procesos no cambian su naturaleza de primer plano o de fondo. Esta configuración tiene la ventaja de baja sobrecarga de planificación, pero es inflexible.
El algoritmo de planificación de cola de retroalimentación multinivel, por el contrario, permite a un proceso moverse entre colas. La idea es separar los procesos de acuerdo a las características de sus ráfagas de CPU. Si un proceso usa demasiado tiempo de CPU, se moverá a una cola de menor prioridad. Este esquema deja a los procesos limitados por E/S y a los procesos interactivos, que generalmente se caracterizan por ráfagas cortas de CPU en las colas de mayor prioridad. Además, un proceso que espera demasiado en la cola de menor prioridad se puede mover a una cola de mayor prioridad. Esta forma el envejecimiento previene la inanición. Por ejemplo, considere un planificador de cola de retroalimentación multinivel con tres colas, numeradas del 0 al 2 (Figura 5.9). El planificador primero ejecuta todo los procesos de la cola 0. Solo cuando la cola 0 esté vacía ejecutará procesos en la cola 1. Del mismo modo, los procesos en la cola 2 se ejecutarán solo si las colas 0 y 1 están vacías. Un proceso que llega a la cola 1 expulsará a un proceso de la cola 2. Un proceso en la cola 1 será reemplazado por un proceso que llegue a la cola 0.
Un proceso ingresa siempre por la cola 0. Un proceso en la cola 0 recibe un cuanto de tiempo de 8 milisegundos. Si no termina dentro de este tiempo, se mueve a la cola 1. Si la cola 0 está vacía, el proceso irá a la cabecera de la cola 1 con un cuanto de 16 milisegundos. Si no se completa, se expulsa y se pone en la cola 2. Los procesos en la cola 2 se ejecutan con criterio FCFS pero se ejecutan solo cuando las colas 0 y 1 están vacías. Para evitar la inanición, un proceso que espera demasiado tiempo en una cola de menor prioridad se puede mover gradualmente a una cola de prioridad más alta.
Figura 5.9 Colas multinivel con retroalimentación 
Este algoritmo de planificación otorga la máxima prioridad a cualquier proceso con una ráfaga de CPU de 8 milisegundos o menos. Tal proceso obtendrá rápidamente la CPU, finalizará su ráfaga de CPU, y pasa a su próxima ráfaga de E/S. Procesos que necesitan más de 8 pero menos de 24 milisegundos también se sirven rápidamente, aunque con menor prioridad que procesos más cortos. Los procesos largos salen rápidamente a la cola 2 y se sirven en orden FCFS con cualquier ciclo de CPU restante de las colas 0 y 1. 
En general, el planificador de colas multinivel con retroalimentación y varios niveles se define por los siguientes parámetros:
• El número de colas.
• El algoritmo de planificación para cada cola.
• El método utilizado para determinar cuándo actualizar un proceso a una prioridad más alta cola
• El método utilizado para determinar cuándo degradar un proceso a una prioridad inferior cola
• El método utilizado para determinar qué cola de un proceso entrará cuando eso proceso necesita servicio.
La definición de un planificador de colas multinivel con realimentación lo hace un algoritmo de planificación de CPU más general. Se puede configurar para que coincida con un específico sistema en diseño. Desafortunadamente, también es el algoritmo más complejo, ya que definir el mejor planificador requiere algunos medios para seleccionar valores para todos los parámetros
5.4 Planificación de hilos
En el Capítulo 4, introducimos hilos al modelo de proceso, distinguiendo entre hilos de nivel de usuario y nivel de kernel. En la mayoría de los sistemas operativos modernos reconocen los hilos (a nivel de kernel), entonces son los hilos no los procesos, los que son planificados por el sistema operativo. Los hilos a nivel de usuario son administrados por una biblioteca de hilos y el kernel no los conoce. Para ejecutarse en una CPU, los hilos de nivel de usuario deben finalmente ser mapeado a un hilo asociado a nivel de kernel, aunque este mapeo puede ser indirecto y puede usarse un proceso ligero (LWP). En esta sección, nosotros vemos los problemas de planificación que involucran los hilos a nivel de usuario y a nivel de kernel y ofrecemos ejemplos específicos de planificación para Pthreads.
5.4.1 Alcance de contención (ámbito de la pelea por los recursos)
Una distinción entre hilos a nivel de usuario y a nivel de kernel radica en cómo están planificados o quién los planifica. En los sistemas que implementan la función de muchos a uno (Sección 4.3.1) y modelos de muchos a muchos (Sección 4.3.3), la biblioteca de hilos planifica los hilos a nivel de usuario para ejecutar en un LWP disponible. Este esquema se conoce como contención a nivel proceso (PCS), ya que la competencia por la CPU se lleva a cabo entre hilos que pertenecen al mismo proceso. Cuando decimos que la biblioteca de hilos planifica los hilos de usuario en LWP disponibles, no queremos decir que los hilos en realidad se ejecutan en una CPU, ya que eso requiere que el sistema operativo planifique el hilo del kernel de un LWP en un núcleo de CPU (física.) Para decidir cuál hilo a nivel de kernel se planifica en una CPU, el kernel utiliza un alcance de contención del sistema (SCS). La competencia por la CPU con la planificación SCS se lleva a cabo entre todos los hilos en el sistema. Sistemas que utilizan el modelo uno a uno (Sección 4.3.2), como los hilos de planificación de Windows y Linux usando solo SCS.
Normalmente, PCS se realiza de acuerdo con la prioridad: el planificador selecciona el hilo ejecutable con la máxima prioridad para ejecutar. Prioridades de hilos a nivel de usuario los establece el programador y la biblioteca de hilos no los ajusta, aunque algunas bibliotecas de hilos pueden permitir que el programador cambie la prioridad de un hilo. Es importante tener en cuenta que PCS generalmente expulsará al hilo que actualmente está ejecutándose a favor de un hilo de mayor prioridad; sin embargo, no hay garantía de la porción de tiempo (Sección 5.3.3) entre hilos de igual prioridad.
5.4.2 Planificación de hilos
Proporcionamos un ejemplo de programa POSIX Pthread en la Sección 4.4.1, junto con una introducción a la creación de hilos con Pthreads. Ahora, destacamos el POSIX Pthread API que permite especificar PCS o SCS durante la creación de hilos. Pthreads identifica los siguientes valores de alcance de contención:
• PTHREAD SCOPE PROCESS schedules threads using PCS scheduling.
• PTHREAD SCOPE SYSTEM schedules threads using SCS scheduling.
En los sistemas que implementan el modelo de muchos a muchos, la política PTHREAD SCOPE PROCESS planifica hilos a nivel de usuario en LWPs disponibles. La biblioteca de hilos mantiene el número de LWP, quizás utilizando activaciones del planificador (Sección 4.6.5). La política de planificación del PTHREAD SCOPE SYSTEM creará y vinculará un LWP para cada hilo a nivel de usuario en sistemas de muchos a muchos, mapeando hilos de manera efectiva utilizando la política uno a uno. 
El Pthread IPC (comunicación entre procesos) proporciona dos funciones para establecer y obtener la política de alcance de contención:
• pthread attr setscope(pthread attr t *attr, int scope)
• pthread attr getscope(pthread attr t *attr, int *scope)
El primer parámetro para ambas funciones contiene un puntero al conjunto de atributos para el hilo. El segundo parámetro para la función pthread attr setscope () se pasa ya sea para el valor de SISTEMA PTHREAD SCOPE o el PROCESO PTHREAD SCOPE, que indica cómo se debe establecer el alcance de contención. En el caso de pthread attr getscope (), este segundo parámetro contiene un puntero a un valor int que se establece en el valor actual delalcance de contención. Si ocurre un error, cada una de estas funciones devuelve un valor distinto de cero.
En la Figura 5.10, ilustramos una API de planificación de Pthread. El programa primero determina el alcance de contención existente y lo establece en SISTEMA PTHREAD SCOPE. Luego crea cinco hilos separados que ejecutan usando la política de planificación de SCS. Tenga en cuenta que en algunos sistemas, solo ciertos valores de alcance de contención se permiten. Por ejemplo, sistemas Linux y macOS permiten solo SISTEMA PTHREAD SCOPE.
Figura 5.10 API de planificación de Pthread.
5.5 Planificación multiprocesador
Nuestra discusión hasta ahora se ha centrado en los problemas de planificación de la CPU en un sistema con un solo núcleo de procesamiento. Si hay varias CPU disponibles, se hace posible compartir la carga, donde múltiples hilos pueden ejecutarse en paralelo, sin embargo los problemas de planificación se vuelven correspondientemente más complejos. Muchas posibilidades han sido tratadas y como vimos en la planificación de CPU con una CPU de un solo núcleo, No hay una mejor solución.
Tradicionalmente, el término multiprocesador se refería a sistemas que proporcionaban múltiples procesadores físicos, donde cada procesador contenía un solo núcleo de CPU. Sin embargo, la definición de multiprocesador ha evolucionado significativamente, y en sistemas informáticos modernos, el multiprocesador ahora se aplica a las siguientes arquitecturas de sistema:
• CPUs multinúcleo (multicore)
• Núcleos multihilados (multithreading)
• Sistemas NUMA
• Multiprocesamiento heterogéneo
Aquí, discutimos la planificación multiprocesador en el contexto de estas diferentes arquitecturas. En los primeros tres ejemplos nos concentramos en sistemas en los que los procesadores son idénticos, homogéneos, en términos de su funcionalidad. Entonces podemos usar cualquier CPU disponible para ejecutar cualquier proceso en la cola. En el último ejemplo exploramos un sistema donde los procesadores no son idénticos en sus capacidades.
5.5.1 Enfoques para la planificación de múltiples procesadores
Un enfoque para la planificación de la CPU en un sistema multiprocesador es que tiene todas las decisiones de la planificación, procesamiento de E/S y otras actividades del sistema sean manejadas por un solo procesador: el servidor maestro. Los otros procesadores solo ejecutan código de usuario. Este multiprocesamiento asimétrico es simple porque sólo un núcleo accede a las estructuras de datos del sistema, lo que reduce la necesidad de compartir datos. Lo malo de este enfoque es que el servidor maestro se convierte en un posible cuello de botella en general y el rendimiento del sistema puede verse reducido.
El enfoque estándar para admitir multiprocesadores es el multiprocesamiento simétrico (SMP), donde cada procesador se auto-planifica. La planificación procede haciendo que el planificador de cada procesador examine la cola lista y seleccione un hilo para ejecutar. Tenga en cuenta que esto proporciona dos posibles estrategias para organizar los hilos elegibles para ser planificados:
1. Todos los hilos pueden estar en una cola lista común.
2. Cada procesador puede tener su propia cola privada de hilos.
Estas dos estrategias se contrastan en la figura 5.11. Si seleccionamos el primero opción, tenemos una posible condición de carrera en la cola compartida de listos y por lo tanto, debe asegurarse de que dos procesadores separados no elijan planificar el mismo hilo y esos hilos no se pierdan de la cola. 
Figura 5.11 Organización de las colas de hilos listos
Como se discutió en Capítulo 6, podríamos usar alguna forma de bloqueo para proteger el acceso común a la cola de listos a la condición de carrera. Sin embargo, el bloqueo sería muy difícil, ya que todos los accesos a la cola podrían bloquearse y el acceso a la cola compartida probablemente sea un cuello de botella en el rendimiento. La segunda opción permite a cada procesador planificar hilos desde su cola de ejecución privada y por lo tanto no sufre los posibles problemas de rendimiento asociados con una única cola de ejecución compartida. Por lo tanto, es el enfoque más común en los sistemas compatibles con SMP. Además, como se describe en la Sección 5.5.4, que tiene un procesador por cada cola de hecho puede conducir a un uso más eficiente de la memoria caché. Existen problemas con las colas de ejecución por procesador, especialmente las cargas de trabajo de diferentes tamaños Sin embargo, como veremos, los algoritmos de equilibrio pueden usarse para igualar las cargas de trabajo entre todos los procesadores.
Prácticamente todos los sistemas operativos modernos admiten SMP, incluidos Windows, Linux y macOS, así como sistemas móviles como Android e iOS. En el resto de esta sección, discutimos cuestiones relacionadas con los sistemas SMP cuando diseñamos algoritmos de planificación de CPU.
5.5.2 Procesadores multinúcleo
Tradicionalmente, los sistemas SMP han permitido que varios procesos se ejecuten en paralelo proporcionando múltiples procesadores físicos. Sin embargo, en computadoras más modernas el hardware ahora coloca múltiples núcleos en el mismo chip físico, lo que resulta en un procesador multinúcleo. Cada núcleo mantiene su arquitectura y, por lo tanto, aparecen para el sistema operativo como una CPU lógica separada. Los sistemas SMP que utilizan procesadores multinúcleo son más rápidos y consumen menos energía que los sistemas en los que cada CPU tiene su propio chip físico. Los procesadores multinúcleo pueden complicar los problemas de planificación. Consideremos Cómo puede suceder esto. Los investigadores han descubierto que cuando un procesador accede a memoria, pasa una cantidad significativa de tiempo esperando que los datos estén disponibles. Esta situación, conocida como pérdida de memoria, ocurre principalmente porque los procesadores modernos funcionan a velocidades mucho más rápidas que la memoria. Sin embargo, una pérdida de memoria también puede ocurrir debido a un fallo de caché (acceso a datos que no están en la memoria caché). La figura 5.12 ilustra una pérdida de tiempo por la memoria. En este escenario, el procesador puede pasar hasta el 50 por ciento de su tiempo esperando datos para estar disponible en la memoria.
Figura 5.12 Espera por la memoria.
Para remediar esta situación, muchos diseños recientes de hardware han implementado núcleos de procesamiento multiproceso en los que dos (o más) hilos de hardware se asignan a cada núcleo. De esa manera, si un hilo de hardware se detiene mientras espera por la memoria, el núcleo puede cambiar a otro hilo. La figura 5.13 ilustra un núcleo de procesamiento de doble hilo en el que la ejecución del hilo 0 y la ejecución del hilo 1 está intercalada. Desde la perspectiva del sistema operativo, cada hilo de hardware mantiene su arquitectura, como el conjunto de instrucciones de puntero y registro, y por lo tanto aparece como una CPU lógica que está disponible para ejecutar un hilo de software. Esta técnica, conocida como chip multihilo (CMT) —Está ilustrado en la figura 5.14. Aquí, el procesador contiene cuatro núcleos de computación, y cada núcleo contiene dos hilos de hardware. Desde la perspectiva del sistema operativo, hay ocho CPU lógicas.
Figura 5.13 Sistema multinúcleo con multihilado (por hardware).
Los procesadores Intel usan el término hiperthreading (también conocido como multihilos simultáneos o SMT) para describir la asignación de múltiples hilos de hardware a un solo núcleo de procesamiento. Los procesadores Intel contemporáneos, como el i7, soportan dos hilos por núcleo, mientras que el procesador Oracle Sparc M7 admite ocho hilos por núcleo, con ocho núcleos por procesador, proporcionando así el funcionamiento de un sistema con 64 CPU lógicas.
Figura 5.14 Chip multihilo.
En general, hay dos formas de manejar hilos en un núcleo de procesamiento: de grano grueso y de grano fino. 
Con multihilo de grano grueso, un hilo se ejecuta en un núcleo hasta un evento de larga latencia, como una demorade memoria. Debido al retraso causado por el evento de larga latencia, el núcleo debe cambiar a otro hilo para comenzar la ejecución. Sin embargo, el costo de cambiar entre los hilos es alto, ya que la canalización de instrucciones (el pipe line o segmentación de cauce) se debe vaciar antes de que el otro hilo pueda comenzar a ejecutarse en el núcleo del procesador. Una vez producido esto, el nuevo hilo comienza a ejecutarse, y comienza a llenar la tubería con sus instrucciones. 
Con multihilo de grano fino (o intercalado) cambia entre hilos en un nivel de granularidad mucho más fina, típicamente en el límite de un ciclo de instrucción. Sin embargo, el diseño arquitectónico de los sistemas de grano fino incluye la lógica para el cambio de hilos. Como resultado, el costo de cambiar entre hilos es pequeño. Es importante tener en cuenta que los recursos del núcleo físico (como las cachés y tuberías) deben compartirse entre sus hilos de hardware y, además un núcleo de procesamiento solo puede ejecutar un hilo de hardware a la vez. Por consiguiente, un procesador multihilado y multinúcleo en realidad requiere dos niveles diferentes de planificación, como se muestra en la Figura 5.15, que ilustra un procesamiento de doble núcleo e hilado.
Figura 5.15 Dos niveles de planificación.
En un nivel están las decisiones de planificación que debe tomar el sistema operativo, ya que elige qué hilo de software ejecutar en cada hilo de hardware (CPU lógica). A todos los efectos prácticos, tales decisiones han sido enfoque principal de este capítulo. Por lo tanto, para este nivel de planificación, el sistema operativo puede elegir cualquier algoritmo de planificación, incluidos los descritos en la Sección 5.3.
Un segundo nivel de planificación especifica cómo cada núcleo decide qué hilo de hardware ejecutará. Hay varias estrategias para adoptar en esta situación. Una es el enfoque que consiste en utilizar un algoritmo simple round-robin para planificar un hilo de hardware al núcleo de procesamiento. Este es el enfoque adoptado por UltraSPARC T3. Intel Itanium utiliza otro enfoque, un procesador de doble núcleo con dos hilos gestionados por hardware por núcleo. Asignado a cada hilo de hardware hay un valor de urgencia dinámica que va de 0 a 7, donde 0 representa el valor más bajo de urgencia y 7 el más alto. El Itanium identifica cinco eventos diferentes que pueden desencadenar un cambio de hilo. Cuando ocurre uno de estos eventos, la lógica de cambio de hilo compara la urgencia de los dos hilos y selecciona el hilo con el valor de urgencia más alto para ejecutar en el núcleo del procesador.
Tenga en cuenta que los dos niveles diferentes de planificación que se muestran en la Figura 5.15 no son necesariamente mutuamente excluyentes. De hecho, si el planificador del sistema operativo (el primer nivel) se da cuenta del intercambio de recursos del procesador, puede tomar decisiones de planificación más efectivas. Como ejemplo, suponga que una CPU tiene dos núcleos de procesamiento, y cada núcleo tiene dos hilos de hardware. Si dos hilos de software se están ejecutando en este sistema, se pueden ejecutar en el mismo núcleo o en núcleos separados. Si ambos están planificados para ejecutarse en el mismo núcleo, tienen que compartir los recursos del procesador y, por lo tanto, es probable que procedan más lentamente que si estuvieran planificados en núcleos separados. Si el sistema operativo es consciente del nivel de compartición de recursos del procesador, puede planificar hilos de software en procesadores lógicos que no comparten recursos.
5.5.3 Equilibrio de carga
En los sistemas SMP, es importante mantener la carga de trabajo equilibrada entre todos lo procesadores para aprovechar al máximo los beneficios de tener más de un procesador. De otra manera, uno o más procesadores pueden permanecer inactivos mientras que otros procesadores tienen mucha carga de trabajo, junto con colas listas de hilos que esperan la CPU. El Balanceo de carga intenta mantener la carga de trabajo distribuida uniformemente entre todos los procesadores en un sistema SMP. Es importante tener en cuenta que el equilibrio de carga suele ser necesario sólo en sistemas donde cada procesador tiene su propia cola privada de hilos listos elegibles para ejecutar. En sistemas con una cola de ejecución común, el equilibrio de carga es innecesario, porque una vez que un procesador queda inactivo, inmediatamente extrae un hilo ejecutable de la cola lista común.
Hay dos enfoques generales para el equilibrio de carga: empujar a la migración y tirar de la migración. Con la migración de inserción, una tarea específica verifica periódicamente la carga en cada procesador y, si encuentra un desequilibrio, distribuye uniformemente la carga moviendo (o empujando) hilos de sobrecarga a inactivo a procesadores menos ocupado. La migración de extracción se produce cuando un procesador inactivo extrae una tarea en espera de un procesador ocupado La migración de empujar y tirar no necesita ser mutuamente excluyente y, de hecho, a menudo se implementan en paralelo en sistemas de equilibrio de carga. Por ejemplo, el planificador Linux CFS (descrito en la Sección 5.7.1) y el planificador ULE disponible para sistemas FreeBSD implementa ambas técnicas.
El concepto de una "carga equilibrada" puede tener diferentes significados. Una vista de una carga equilibrada puede requerir simplemente que todas las colas tengan aproximadamente el mismo número de hilos. Alternativamente, el balance puede requerir una distribución equitativa de prioridades de hilo en todas las colas. Además, en ciertas situaciones, ninguna de estas estrategias puede ser suficiente. De hecho, pueden trabajar contra el objetivo del algoritmo de planificación. (Dejamos una mayor consideración de esto como un ejercicio.)
5.5.4 Afinidad del procesador
Tenga en cuenta lo que sucede con la memoria caché cuando un hilo se ha estado ejecutando en un procesador específico. Los datos a los que el hilo ha accedido más recientemente llenan el caché para el procesador. Como resultado, sucesivos accesos del hilo a la memoria a menudo se satisfacen en la memoria caché (conocida como "caché en caliente"). Ahora considere: ¿Qué sucede si el hilo migra a otro procesador? Por ejemplo, debido al equilibrio de carga. El contenido de la memoria caché debe ser invalidado para el primer procesador, y el caché para el segundo proceso debe ser actualizado. Debido al alto costo de invalidar y repoblar cachés, la mayoría de los sistemas operativos con soporte SMP, trata de NO migrar un hilo de un procesador a otro e intenta mantener un hilo ejecutándose en el mismo procesador y tomar ventaja de un caché caliente. Esto se conoce como afinidad de procesador, es decir, un proceso tiene una afinidad por el procesador en el que se está ejecutando actualmente.
Las dos estrategias descritas en la Sección 5.5.1 para organizar la cola de los hilos disponibles para la planificación tienen implicaciones para la afinidad del procesador. Si nosotros adoptamos el enfoque de una cola lista común, se puede seleccionar un hilo para ejecución en cualquier procesador. Por lo tanto, si un hilo está planificado en un nuevo procesador, el caché de ese procesador debe actualizarse. Con colas privadas de hilos listos, para cada cola procesador, un hilo siempre se planifica en el mismo procesador y, por lo tanto, puede beneficiarse del contenido de un caché caliente. Esencialmente ¡Las colas de hilos listos por procesador proporcionan afinidad de procesador!
La afinidad del procesador tiene varias formas. Cuando un sistema operativo tiene una política de intentar mantener un proceso ejecutándose en el mismo procesador, pero sin garantizar que lo haga, tenemos una situación conocida como afinidad suave. Aquí, el sistema operativo intentará mantener un proceso en un único procesador, pero es posible que un proceso migre entre procesadores durante el equilibrio de carga Por el contrario, algunos sistemas proporcionan llamadas al sistema que admiten afinidad, permitiendoasí que un proceso especifique un subconjunto de procesadores en el que pueda correr. Muchos sistemas proporcionan afinidad suave y dura. Por ejemplo, Linux implementa una afinidad suave, pero también proporciona la llamada al sistema sched_setaffinity (), que admite una afinidad dura al permitir que un hilo especifique el conjunto de CPU en el que es elegible para ejecutarse.
Figura 5.16 Planificación de NUMA y CPU
La arquitectura de memoria principal de un sistema puede afectar la afinidad del procesador problemas también. La figura 5.16 ilustra una arquitectura que presenta acceso no uniforme a memoria (NUMA) donde hay dos chips de procesador físico y cada uno con su propia CPU y memoria local. Aunque una interconexión del sistema permite a todas las CPUs en un sistema NUMA compartir un espacio de direcciones físicas. Obviamente una CPU tiene más velocidad de acceso a su memoria local que a la memoria local a otra CPU. Si el funcionamiento del planificador de la CPU del sistema y los algoritmos de asignación de memoria son compatibles con NUMA y pueden trabajan juntos, entonces a un hilo que ha sido planificado en una CPU en particular se le puede asignar la memoria más cercana al lugar donde reside la CPU, proporcionando así al hilo el acceso de memoria más rápido posible.
Curiosamente, el equilibrio de carga a menudo contrarresta los beneficios de la afinidad de procesador. Es decir, el beneficio de mantener un hilo ejecutándose en el mismo procesador hace que el hilo aproveche que sus datos están en la memoria caché de esa memoria de procesador. Balancear la carga moviendo un hilo de un procesador a otro elimina este beneficio. Del mismo modo, la migración de un hilo entre procesadores puede incurrir en una penalización en los sistemas NUMA, donde un hilo se puede mover a un procesador y eso requiere tiempos de acceso de memoria más largos. En otras palabras, hay una tensión entre el equilibrio de carga y la minimización de los tiempos de acceso a la memoria. Así, los algoritmos de planificación para sistemas multinúcleo modernos NUMA se han vuelto bastantes complejos. En la Sección 5.7.1, examinamos el algoritmo de planificación CFS de Linux y exploramos cómo equilibra estos objetivos en competencia.
5.5.5 Multiprocesamiento heterogéneo
En los ejemplos que hemos discutido hasta ahora, todos los procesadores son idénticos en términos de sus capacidades, permitiendo así que cualquier hilo se ejecute en cualquier núcleo de procesamiento. La única diferencia es que el tiempo de acceso a la memoria puede variar según las políticas de equilibrio de carga y afinidad del procesador, así como en sistemas NUMA.
Aunque los sistemas móviles ahora incluyen arquitecturas multinúcleo, algunos sistemas ahora están diseñados con núcleos que ejecutan el mismo conjunto de instrucciones, pero varían en términos de su velocidad de reloj y administración de energía, incluida la capacidad de ajustar el consumo de energía de un núcleo hasta el punto de inactividad del núcleo. Tales sistemas se conocen como multiprocesamiento heterogéneo (HMP). Tenga en cuenta que esto no es una forma de multiprocesamiento asimétrico como se describe en la Sección 5.5.1 porque ambas tareas del sistema y del usuario pueden ejecutarse en cualquier núcleo. Más bien, la intención detrás de HMP es para gestionar mejor el consumo de energía asignando tareas a ciertos núcleos basados en las demandas específicas de la tarea.
Para los procesadores ARM que lo admiten, este tipo de arquitectura es conocida como big.LITTLE donde los núcleos grandes de mayor rendimiento se combinan con la energía eficiente de PEQUEÑOS núcleos. Los núcleos grandes consumen mayor energía y, por lo tanto, solo deberían usarse por cortos períodos de tiempo. Del mismo modo, los núcleos pequeños usan menos energía y por lo tanto se puede usar por períodos más largos.
Hay varias ventajas de este enfoque. Al combinar una serie de núcleos más lentos con núcleos más rápidos, un planificador de CPU puede asignar tareas que no requieren un alto rendimiento, pero es posible que deba ejecutarse durante períodos más largos (como tareas de fondo) a pequeños núcleos, lo que ayuda a preservar la carga de la batería. Del mismo modo, las aplicaciones interactivas que requieren más potencia de procesamiento, pero puede ejecutarse por períodos más cortos, puede asignarse a núcleos grandes. Además, si el dispositivo móvil está en modo de ahorro de energía, los núcleos grandes que consumen mucha energía pueden estar deshabilitados y el sistema puede confiar únicamente en pequeños núcleos energéticamente eficientes. Windows 10 admite la planificación HMP al permitir que un hilo seleccione una política de planificación que respalde mejor sus demandas de administración de energía.
5.6 Planificación de CPU en tiempo real
La planificación de la CPU para sistemas operativos en tiempo real implica problemas especiales. En general, podemos distinguir entre sistemas blandos en tiempo real y sistemas duros en tiempo real sistemas. Los sistemas blandos en tiempo real no ofrecen ninguna garantía sobre cuándo se planificará un proceso en tiempo real. Solo garantizan que el proceso tendrá preferencia sobre los procesos no críticos. Los sistemas duros en tiempo real tienen requisitos más estrictos. Una tarea debe ser atendida antes de su plazo límite; si el servicio se da después de que el plazo límite ha expirado es lo mismo que ningún servicio. En esta sección, exploramos Varios problemas relacionados con la planificación de procesos tanto en sistemas operativos de tiempo real blandos como en duros
5.6.1 Minimizando la latencia
Considere la naturaleza de eventos impulsados en un sistema en tiempo real. Normalmente el sistema está esperando que ocurra un evento en tiempo real. Los eventos pueden surgir en el software —Como cuando caduca un temporizador — o en hardware — como cuando un control remoto de un vehículo detecta que se está acercando a una obstrucción. Cuando ocurre un evento, el sistema debe responder y atenderlo lo más rápido posible. Nos referimos a latencia de evento como la cantidad de tiempo que transcurre desde que ocurre un evento hasta cuando se da servicio (Figura 5.17)
Figura 5.17 Latencia de eventos.
Por lo general, diferentes eventos tienen diferentes requisitos de latencia. Por ejemplo, el requisito de latencia para un sistema antibloqueo de frenos puede ser de 3 a 5 milisegundos. Es decir, desde el momento en que una rueda detecta por primera vez que se está deslizando, el sistema controla los frenos antibloqueo y tiene de 3 a 5 milisegundos para responder y controlar la situación. Cualquier respuesta que tome más tiempo podría resultar en el automóvil que se desvíe de control. Por el contrario, un sistema integrado que controla el radar en un avión podría tolerar un período de latencia de varios segundos.
Dos tipos de latencias afectan el rendimiento de los sistemas en tiempo real:
1. Latencia de interrupción
2. Latencia de despacho
La latencia de interrupción se refiere al período de tiempo desde la llegada de una interrupción a la CPU hasta el inicio de la rutina que da servicio a la interrupción. Cuando se produce una interrupción, el sistema operativo primero debe completar la instrucción que se ejecuta y determinar el tipo de interrupción que ocurrió. Luego debe guardar el estado del proceso actual antes de dar servicio a la interrupción usando la rutina de servicio de interrupción (ISR) específica. El tiempo total requerido para realizar estas tareas es la latencia de interrupción (Figura 5.18).
Obviamente, es crucial para los sistemas operativos en tiempo real minimizar la latencia de interrupción para garantizar que las tareas en tiempo real reciban atención inmediata. En efecto, para sistemas de tiempo real difíciles, la latencia de interrupción no debe simplemente minimizarse, sino debe limitarse para cumplir con los estrictos requisitos de estos sistemas.
Un factor importante que contribuye a la latencia de interrupción es la cantidad de tiempo que las interrupcionespueden deshabilitarse mientras las estructuras de datos del núcleo están siendo actualizadas. Los sistemas operativos en tiempo real requieren que las interrupciones estén deshabilitadas solo por períodos muy cortos de tiempo.
La cantidad de tiempo requerida para que el despachador de planificación detenga uno de un procesador e inicie otro se conoce como latencia de despacho. Proporcionar tareas en tiempo real con acceso inmediato a los mandatos de la CPU que operan en los sistemas de tiempo real también minimizan esta latencia. La técnica más efectiva para mantener la latencia de despacho baja es proporcionar kernels apropiativos (o expulsivos). En los sistemas de tiempo real duro, la latencia de despacho generalmente se mide en varios microsegundos.
En la figura 5.19, diagramamos la composición de la latencia de despacho. La fase de conflicto de latencia de envío tiene dos componentes:
1. Expulsión de cualquier proceso que se ejecute en el kernel
2. Liberación de los recursos que posean los procesos de baja prioridad que se necesiten en procesos de alta prioridad.
Después de la fase de conflicto, la fase de despacho planifica al proceso de alta prioridad en una CPU disponible.
Figura 5.18 Latencia de interrupción
Figura 5.19 Latencia de despacho.
5.6.2 Planificación basada en prioridades
La característica más importante de un sistema operativo en tiempo real es responder de inmediato a un proceso en tiempo real tan pronto como ese proceso requiera la CPU. Como un resultado, el planificador para un sistema operativo en tiempo real debe admitir un algoritmo con expulsión por prioridad. Recordemos que los algoritmos de planificación basados ​​en prioridades asignan a cada proceso una prioridad en función de su importancia; A las tareas más importantes se les asignan prioridades más altas que las que se consideran menos importantes. Si el planificador también admite la expulsión, un proceso que actualmente se ejecuta en la CPU se expulsará si hay un proceso de mayor prioridad disponible para ejecutarse.
Los algoritmos de planificación apropiativos (expulsivos) basados ​​en prioridades se analizan en detalle en La Sección 5.3.4 y la Sección 5.7 presenta ejemplos de características de la planificación en tiempo real suave de los sistemas operativos Linux, Windows y Solaris. Cada uno de estos sistemas asigna a los procesos en tiempo real la máxima prioridad de planificación. Por ejemplo, Windows tiene 32 niveles de prioridad diferentes. Los niveles más altos: prioridad valores 16 a 31: están reservados para procesos en tiempo real. Solaris y Linux tienen esquemas de priorización similares.
Tenga en cuenta que proporcionar un planificador apropiativo basado en prioridades solo garantiza funcionalidad en tiempo real suave. Los sistemas en tiempo real duros deben garantizar aún más que las tareas en tiempo real serán atendidas de acuerdo con sus requisitos de plazo, y hacer cumplir con tales garantías requiere características de planificación adicionales. En el resto de esta sección, cubrimos algoritmos de planificación apropiados para sistemas en tiempo real.
Sin embargo, antes de continuar con los detalles de los planificadores individuales, debemos definir ciertas características de los procesos que se van a planificar. Primero, los procesos se consideran periódicos. Es decir, requieren la CPU en intervalos constantes (períodos). Una vez que un proceso periódico ha adquirido la CPU, tiene un tiempo de procesamiento fijo t, un plazo d por el cual debe ser atendido por la CPU, y un punto p. La relación del tiempo de procesamiento, el plazo de vencimiento y el período puede expresarse como 0 ≤ t ≤ d ≤ p. La tasa de una tarea periódica es 1∕p. La figura 5.20 ilustra la ejecución de un proceso periódico a lo largo del tiempo. Los Planificadores pueden aprovechar estas características y asignar prioridades de acuerdo con una fecha límite del proceso o requisitos de tarifas.
Figura 5.20 Tarea periódica.
Lo inusual de esta forma de planificación es que un proceso puede tener que anunciar sus requisitos de fecha límite al planificador. Luego, usando una técnica conocida como algoritmo de control de admisión, el planificador hace una de dos cosas. O bien admite el proceso, garantizando que el proceso se completará a tiempo, o rechaza la solicitud como imposible si no puede garantizar que la tarea será atendida por su fecha límite.
5.6.3 Planificación monotónica por tasa
El algoritmo de planificación monotónica por tasa planifica tareas periódicas utilizando una Política de prioridad estática con expulsión. Si se está ejecutando un proceso de menor prioridad y un proceso de mayor prioridad está disponible para ejecutarse, se expulsará al proceso de menor prioridad. Al ingresar al sistema, a cada tarea periódica se le asigna una prioridad que será inversa de su período. Cuanto más corto es el período, la prioridad será mayor; cuanto más largo sea el período, menor será la prioridad. Lo racional detrás de esta política está asignar una mayor prioridad a las tareas que requieren la CPU más a menudo. Además, la planificación monotónica por tasa supone que el tiempo de procesamiento de un proceso periódico es el mismo para cada ráfaga de CPU. Es decir, cada vez un proceso adquiere la CPU, la duración de su ráfaga de CPU es la misma.
Consideremos un ejemplo. Tenemos dos procesos, P1 y P2. Los periodos para P1 y P2 son 50 y 100, respectivamente, es decir, p1 = 50 y p2 = 100. Los tiempos de procesamiento son t1 = 20 para P1 y t2 = 35 para P2. La fecha límite para cada proceso requiere que complete su ráfaga de CPU al comienzo de su próximo período.
Primero debemos preguntarnos si es posible planificar estas tareas para que cada uno cumpla con sus plazos. Si medimos la utilización de CPU de un proceso Pi como la relación de su ráfaga a su período, ti ∕ pi, la utilización de CPU de P1 es 20∕50 = 0.40 y el de P2 es 35∕100 = 0.35, para una utilización total de CPU de 75 por ciento Por lo tanto, parece que podemos planificar estas tareas de tal manera que ambas cumplan sus plazos y aún dejan la CPU con los ciclos disponibles.
Supongamos que asignamos a P2 una prioridad más alta que P1. La ejecución de P1 y P2 en esta situación se muestra en la figura 5.21. Como podemos ver, P2 comienza la ejecución primero y termina en el tiempo 35. En este punto, comienza P1; completa su ráfaga de CPU en tiempo 55. Sin embargo, la primera fecha límite para P1 fue en el tiempo 50, por lo que el planificador provocó que P1 no cumpliera su fecha límite.
Figura 5.21 Planificación de tareas cuando P2 tiene una prioridad más alta que P1.
Ahora supongamos que usamos la planificación de tasa monotónica, en la que asignamos a P1 una prioridad más alta que P2 porque el período de P1 es más corto que el de P2. La ejecución de estos procesos en esta situación se muestra en la Figura 5.22. P1 comienza primero y completa su ráfaga de CPU en el momento 20, cumpliendo así su primera fecha límite. P2 comienza a correr en este punto y corre hasta el tiempo 50. En este momento, es expulsado por P1, aunque todavía le quedan 5 milisegundos en su ráfaga de CPU. P1 completa su ráfaga de CPU en el momento 70, momento en el cual el planificador reanuda P2. P2 completa su ráfaga de CPU en el momento 75, y también cumple con su primer plazo. El sistema está inactivo hasta el tiempo 100, cuando P1 se planifica nuevamente.
La planificación de tasa monotónica se considera óptima en el caso de que un conjunto de procesos no puede ser planificado por este algoritmo, no puede ser planificado por ningún otro algoritmo que asigna prioridades estáticas. A continuación, examinemos un conjunto de procesos que no se puede planificar utilizando el algoritmo de tasa monotónica.
Suponga que el proceso P1 tiene un período de p1 = 50 y una ráfaga de CPU de t1 = 25. Para P2, los valores correspondientes son p2 = 80 y t2 = 35. 
Figura 5.22 Planificación monotónica de frecuencia
La planificación por tasa monotónica asignaría al proceso P1 una prioridad más alta, ya que tiene el