Planificación (informática)

El planificador de procesos es una parte del sistema operativo que decide qué proceso se ejecuta en un momento dado. Generalmente, tiene la capacidad de pausar un proceso en ejecución, moverlo al final de la cola de ejecución e iniciar un nuevo proceso; este tipo de planificador se conoce como planificador preventivo . Si el planificador no puede pausar un proceso en ejecución e iniciar uno nuevo, se trata de un planificador cooperativo . ^{[ 5 ]}

Distinguimos entre planificación a largo plazo , planificación a medio plazo y planificación a corto plazo en función de la frecuencia con la que deben tomarse decisiones. ^{[ 6 ]}

Primero en entrar, primero en salir ( FIFO ), también conocido como primero en llegar, primero en ser atendido (FCFS), es el algoritmo de planificación más simple. FIFO simplemente pone en cola los procesos en el orden en que llegan a la cola de listos. Esto se usa comúnmente para uncola de tareas , por ejemplo, como se ilustra en esta sección.

• Dado que los cambios de contexto solo se producen al finalizar el proceso y no se requiere ninguna reorganización de la cola de procesos, la sobrecarga de planificación es mínima.
• El rendimiento puede ser bajo porque los procesos largos pueden estar acaparando la CPU, lo que provoca que los procesos cortos tengan que esperar mucho tiempo (lo que se conoce como efecto convoy).
• No hay inanición, porque cada proceso tiene la oportunidad de ejecutarse después de un tiempo determinado.
• El tiempo de procesamiento , el tiempo de espera y el tiempo de respuesta dependen del orden de llegada y pueden ser elevados por las mismas razones mencionadas anteriormente.
• No se establece ninguna priorización, por lo que este sistema tiene problemas para cumplir con los plazos de los procesos.
• La falta de priorización implica que, siempre y cuando todos los procesos se completen, no hay escasez de recursos. En un entorno donde algunos procesos podrían no completarse, sí puede haber escasez de recursos.
• Se basa en el sistema de colas.

El algoritmo de planificación dinámica "Early deadline first" (EDF, por sus siglas en inglés) o " Least time to sgo" (menor tiempo restante ) se utiliza en sistemas operativos en tiempo real para colocar procesos en una cola de prioridad. Cada vez que ocurre un evento de planificación (una tarea finaliza, se libera una nueva tarea, etc.), se busca en la cola el proceso más próximo a su fecha límite, que será el siguiente en programarse para su ejecución.

Similar al algoritmo de procesamiento de trabajos más cortos (SJF). Con esta estrategia, el planificador ordena los procesos con el menor tiempo de procesamiento restante estimado para que sean los siguientes en la cola. Esto requiere conocimientos o estimaciones avanzadas sobre el tiempo necesario para que un proceso se complete.

• Si un proceso más corto llega durante la ejecución de otro, el proceso en ejecución se interrumpe (fenómeno conocido como preempción), dividiéndose en dos bloques de cálculo separados. Esto genera una sobrecarga adicional debido al cambio de contexto. El planificador también debe colocar cada proceso entrante en un lugar específico de la cola, lo que genera una sobrecarga adicional.
• Este algoritmo está diseñado para obtener el máximo rendimiento en la mayoría de los casos.
• El tiempo de espera y el tiempo de respuesta aumentan a medida que se incrementan los requisitos computacionales del proceso. Dado que el tiempo de respuesta se basa en la suma del tiempo de espera y el tiempo de procesamiento, los procesos más largos se ven significativamente afectados. En general, el tiempo de espera es menor que en el método FIFO, ya que ningún proceso tiene que esperar a que finalice el proceso más largo.
• No se presta especial atención a los plazos de entrega; el programador solo puede intentar que los procesos con plazos de entrega sean lo más breves posible.
• Es posible que se produzca inanición, especialmente en un sistema con mucha actividad y en el que se ejecutan numerosos procesos pequeños.
• Para utilizar esta política, deberíamos tener al menos dos procesos de prioridades diferentes.

El sistema operativo asigna un rango de prioridad fija a cada proceso, y el planificador organiza los procesos en la cola de listos según su prioridad. Los procesos de menor prioridad son interrumpidos por los procesos entrantes de mayor prioridad.

• Los gastos generales no son mínimos, ni tampoco significativos.
• FPPS no ofrece ninguna ventaja particular en términos de rendimiento con respecto a la planificación FIFO.
• Si el número de clasificaciones es limitado, se puede describir como una colección de colas FIFO, una para cada clasificación de prioridad. Los procesos en las colas de menor prioridad se seleccionan solo cuando todas las colas de mayor prioridad están vacías.
• El tiempo de espera y el tiempo de respuesta dependen de la prioridad del proceso. Los procesos de mayor prioridad tienen tiempos de espera y de respuesta más cortos.
• Se pueden cumplir los plazos dando mayor prioridad a los procesos que los tienen.
• Es posible que los procesos de menor prioridad se queden sin recursos cuando un gran número de procesos de alta prioridad hacen cola para obtener tiempo de CPU.

El planificador asigna una unidad de tiempo fija a cada proceso y los ejecuta de forma iterativa. Si el proceso finaliza dentro de ese intervalo de tiempo, se termina; de lo contrario, se reprograma después de dar tiempo a todos los demás procesos.

• La planificación de los trenes implica una gran cantidad de gastos generales, especialmente con una unidad de tiempo pequeña.
• Rendimiento equilibrado entre FCFS/FIFO y SJF/SRTF: los trabajos más cortos se completan más rápido que en FIFO y los procesos más largos se completan más rápido que en SJF.
• Buen tiempo de respuesta promedio; el tiempo de espera depende del número de procesos, y no de la duración promedio de los procesos.
• Debido a los elevados tiempos de espera, en un sistema RR puro rara vez se cumplen los plazos de entrega.
• La inanición nunca puede ocurrir, ya que no se otorga ninguna prioridad. El orden de asignación de unidades de tiempo se basa en el tiempo de llegada del proceso, de forma similar al método FIFO (primero en entrar, primero en salir).
• Si el intervalo de tiempo es grande, se convierte en FCFS/FIFO, o si es corto, se convierte en SJF/SRTF.

Esto se utiliza en situaciones donde los procesos se pueden dividir fácilmente en diferentes grupos. Por ejemplo, se suele establecer una división entre procesos en primer plano (interactivos) y procesos en segundo plano (por lotes). Estos dos tipos de procesos tienen diferentes requisitos de tiempo de respuesta y, por lo tanto, pueden tener diferentes necesidades de planificación. Resulta muy útil para problemas de memoria compartida .

Un planificador que conserva el trabajo es aquel que siempre intenta mantener ocupados los recursos programados si hay trabajos listos para ser programados. Por el contrario, un planificador que no conserva el trabajo es aquel que, en algunos casos, puede dejar inactivos los recursos programados a pesar de la presencia de trabajos listos para ser programados.

Existen varios problemas de programación cuyo objetivo es decidir qué trabajo se asigna a qué estación y en qué momento, de manera que se minimice el tiempo total de finalización:

• Programación de talleres : hay n trabajos y m estaciones idénticas. Cada trabajo debe ejecutarse en una sola máquina. Esto se suele considerar un problema en línea. 
• Programación de taller abierto : hay n trabajos y m estaciones diferentes. Cada trabajo debe pasar cierto tiempo en cada estación, en un orden libre. 
• Programación de flujo de producción : hay n trabajos y m estaciones diferentes. Cada trabajo debe pasar un tiempo determinado en cada estación, en un orden predeterminado. 

Un método muy común en sistemas embebidos es la planificación manual de tareas. Esto puede hacerse, por ejemplo, mediante multiplexación temporal. En ocasiones, el núcleo se divide en tres o más partes: planificación manual, planificación preventiva y planificación a nivel de interrupción. Los métodos exactos para la planificación de tareas suelen ser de propiedad exclusiva.

• No hay problemas de escasez de recursos.
• Muy alta predictibilidad; permite la implementación de sistemas de tiempo real estricto.
• Casi sin gastos generales
• Puede que no sea óptimo para todas las aplicaciones.
• La efectividad depende completamente de la implementación.

Al diseñar un sistema operativo, un programador debe considerar qué algoritmo de planificación tendrá el mejor rendimiento según el uso previsto del sistema. No existe un algoritmo de planificación óptimo universal , y muchos sistemas operativos utilizan extensiones o combinaciones de los algoritmos de planificación mencionados anteriormente.

Por ejemplo, Windows NT /XP/Vista utiliza una cola de retroalimentación multinivel , una combinación de planificación preventiva de prioridad fija, round-robin y algoritmos FIFO (primero en entrar, primero en salir). En este sistema, los subprocesos pueden aumentar o disminuir dinámicamente su prioridad dependiendo de si ya han sido atendidos o si han estado esperando durante mucho tiempo. Cada nivel de prioridad está representado por su propia cola, con planificación round-robin para los subprocesos de alta prioridad y FIFO para los de menor prioridad. En este sentido, el tiempo de respuesta es corto para la mayoría de los subprocesos, y los subprocesos del sistema, cortos pero críticos, se completan muy rápidamente. Dado que los subprocesos solo pueden usar una unidad de tiempo del round-robin en la cola de mayor prioridad, la inanición puede ser un problema para los subprocesos de alta prioridad más largos.

IBM OS/360 estaba disponible con tres planificadores diferentes. Las diferencias eran tales que a menudo se consideraba que las variantes eran tres sistemas operativos distintos:

• La opción Planificador secuencial único , también conocida como Programa de control primario (PCP), proporcionaba la ejecución secuencial de un único flujo de trabajos.
• La opción de Planificador Secuencial Múltiple , conocida como Multiprogramación con Número Fijo de Tareas (MFT), permitía la ejecución de múltiples trabajos concurrentes. La ejecución se regía por una prioridad que tenía un valor predeterminado para cada flujo o que podía solicitarse por separado para cada trabajo. La versión II de MFT añadió subtareas (hilos), que se ejecutaban con una prioridad basada en la del trabajo principal. Cada flujo de trabajo definía la cantidad máxima de memoria que podía utilizar cualquier trabajo en ese flujo.
• La opción de Planificadores de Prioridad Múltiple , o Multiprogramación con un Número Variable de Tareas (MVT) , incluía subtareas desde el principio; cada trabajo solicitaba la prioridad y la memoria que requería antes de su ejecución.

Las versiones posteriores de almacenamiento virtual de MVS añadieron una función de Administrador de carga de trabajo al planificador, que programa los recursos del procesador según un esquema elaborado definido por la instalación.

Los primeros sistemas MS-DOS y Microsoft Windows no eran multitarea y, por lo tanto, no contaban con un planificador. Windows 3.1x utilizaba un planificador no preemptivo, lo que significa que no interrumpía los programas. Dependía de que el programa finalizara o le indicara al sistema operativo que no necesitaba el procesador para poder pasar a otro proceso. Esto se conoce generalmente como multitarea cooperativa. Windows 95 introdujo un planificador preemptivo rudimentario; sin embargo, para garantizar la compatibilidad con versiones anteriores, optó por permitir que las aplicaciones de 16 bits se ejecutaran sin interrupción. ^{[ 10 ]}

Los sistemas operativos basados ​​en Windows NT utilizan una cola de retroalimentación multinivel. Se definen 32 niveles de prioridad, del 0 al 31, donde las prioridades del 0 al 15 son prioridades normales y las del 16 al 31 son prioridades de tiempo real flexible, que requieren privilegios para su asignación. El nivel 0 está reservado para el sistema operativo. Las interfaces de usuario y las API trabajan con clases de prioridad para el proceso y los subprocesos del proceso, que luego el sistema combina para obtener el nivel de prioridad absoluto.

El núcleo puede cambiar el nivel de prioridad de un hilo dependiendo de su uso de E/S y CPU y si es interactivo (es decir, acepta y responde a la entrada de los humanos), aumentando la prioridad de los procesos interactivos y limitados por E/S y disminuyendo la de los procesos limitados por CPU, para aumentar la capacidad de respuesta de las aplicaciones interactivas. ^{[ 11 ]} El planificador se modificó en Windows Vista para usar el registro del contador de ciclos de los procesadores modernos para llevar un registro exacto de cuántos ciclos de CPU ha ejecutado un hilo, en lugar de solo usar una rutina de interrupción de temporizador de intervalo. ^{[ 12 ]} Vista también usa un planificador de prioridad para la cola de E/S para que los desfragmentadores de disco y otros programas similares no interfieran con las operaciones en primer plano. ^{[ 13 ]}

Mac OS 9 utiliza la planificación cooperativa para los subprocesos, donde un proceso controla varios subprocesos cooperativos, y también proporciona planificación preventiva para las tareas de multiprocesamiento. El núcleo planifica las tareas de multiprocesamiento mediante un algoritmo de planificación preventiva. Todos los procesos del Administrador de procesos se ejecutan dentro de una tarea de multiprocesamiento especial, denominada tarea azul . Estos procesos se planifican de forma cooperativa, utilizando un algoritmo de planificación round-robin ; un proceso cede el control del procesador a otro proceso llamando explícitamente a una función de bloqueo como WaitNextEvent. Cada proceso tiene su propia copia del Administrador de subprocesos que planifica los subprocesos de ese proceso de forma cooperativa; un subproceso cede el control del procesador a otro subproceso llamando a YieldToAnyThreado YieldToThread. ^{[ 14 ]}

macOS utiliza una cola de retroalimentación multinivel, con cuatro bandas de prioridad para los subprocesos : normal, prioridad alta del sistema, solo modo kernel y tiempo real. ^{[ 15 ]} Los subprocesos se programan de forma preventiva; macOS también admite subprocesos programados de forma cooperativa en su implementación del Administrador de subprocesos en Carbon . ^{[ 14 ]} 

En AIX versión 4 existen tres valores posibles para la política de planificación de subprocesos:

• Primero en entrar, primero en salir: Una vez que se programa un hilo con esta política, se ejecuta hasta su finalización a menos que se bloquee, ceda voluntariamente el control de la CPU o un hilo de mayor prioridad se vuelva disponible. Solo los hilos de prioridad fija pueden tener una política de programación FIFO.
• Round Robin: Este método es similar al esquema round-robin del planificador de AIX versión 3, basado en  intervalos de tiempo de 10 ms. Cuando un hilo RR toma el control al final del intervalo de tiempo, se mueve al final de la cola de hilos despachables de su prioridad. Solo los hilos de prioridad fija pueden tener una política de planificación Round Robin.
• OTRO: Esta política está definida por POSIX1003.4a como definida por la implementación. En AIX Versión 4, esta política se define como equivalente a RR, excepto que se aplica a subprocesos con prioridad no fija. El recálculo del valor de prioridad del subproceso en ejecución en cada interrupción de reloj implica que un subproceso puede perder el control porque su valor de prioridad ha superado el de otro subproceso despachable. Este es el comportamiento de AIX Versión 3.

Los hilos son de interés principalmente para aplicaciones que actualmente constan de varios procesos asíncronos. Estas aplicaciones podrían generar una carga menor en el sistema si se convierten a una estructura multihilo.

AIX 5 implementa las siguientes políticas de planificación: FIFO, round robin y round robin equitativo. La política FIFO tiene tres implementaciones diferentes: FIFO, FIFO2 y FIFO3. La política round robin se denomina SCHED_RR en AIX, y la round robin equitativa se denomina SCHED_OTHER. ^{[ 16 ]}

FreeBSD utiliza una cola de retroalimentación multinivel con prioridades que van de 0 a 255. De 0 a 63 están reservadas para interrupciones, de 64 a 127 para la mitad superior del kernel, de 128 a 159 para subprocesos de usuario en tiempo real, de 160 a 223 para subprocesos de usuario compartidos y de 224 a 255 para subprocesos de usuario inactivos. Además, al igual que Linux, utiliza la configuración de cola activa, pero también tiene una cola inactiva. ^{[ 25 ]}

NetBSD utiliza una cola de retroalimentación multinivel con prioridades que van de 0 a 223. De 0 a 63 están reservados para subprocesos compartidos en el tiempo (predeterminado, política SCHED_OTHER), de 64 a 95 para subprocesos de usuario que entraron en el espacio del kernel , de 96 a 128 para subprocesos del kernel, de 128 a 191 para subprocesos de usuario en tiempo real (políticas SCHED_FIFO y SCHED_RR) y de 192 a 223 para interrupciones de software .

Solaris utiliza una cola de retroalimentación multinivel con prioridades que van de 0 a 169. Las prioridades 0 a 59 están reservadas para subprocesos de tiempo compartido, 60 a 99 para subprocesos del sistema, 100 a 159 para subprocesos en tiempo real y 160 a 169 para interrupciones de baja prioridad. A diferencia de Linux, ^{[ 25 ]} cuando un proceso termina de usar su cuanto de tiempo, se le asigna una nueva prioridad y se vuelve a colocar en la cola. Solaris  9 introdujo dos nuevas clases de planificación: la clase de prioridad fija y la clase de reparto equitativo. Los subprocesos con prioridad fija tienen el mismo rango de prioridad que la clase de tiempo compartido, pero sus prioridades no se ajustan dinámicamente. La clase de planificación equitativa utiliza las cuotas de CPU para priorizar los subprocesos en las decisiones de planificación. Las cuotas de CPU indican el derecho a los recursos de CPU. Se asignan a un conjunto de procesos, que se conocen colectivamente como un proyecto. ^{[ 7 ]}