Programación (informática)

En informática , la programación es la acción de asignar recursos para realizar tareas . Los recursos pueden ser procesadores , enlaces de red o tarjetas de expansión . Las tareas pueden ser subprocesos , procesos o flujos de datos .

La actividad de programación se lleva a cabo mediante un proceso denominado planificador . Los planificadores suelen estar diseñados para mantener ocupados todos los recursos del equipo (como en el caso del equilibrio de carga ), permitir que varios usuarios compartan los recursos del sistema de manera eficaz o lograr una calidad de servicio objetivo .

La programación es fundamental para la computación en sí y una parte intrínseca del modelo de ejecución de un sistema informático; el concepto de programación permite que una computadora pueda realizar múltiples tareas con una única unidad central de procesamiento (CPU).

Un programador puede apuntar a uno o más objetivos, por ejemplo:

• maximizar el rendimiento (la cantidad total de trabajo completado por unidad de tiempo);
• minimizar el tiempo de espera (tiempo desde que el trabajo está listo hasta el primer punto en que comienza su ejecución);
• minimizar la latencia o el tiempo de respuesta (tiempo desde que el trabajo está listo hasta que está terminado en caso de actividad por lotes, ^{[1] [2] [3]} o hasta que el sistema responde y entrega la primera salida al usuario en caso de actividad interactiva); ^[4]
• maximizar la equidad (tiempo de CPU igual para cada proceso o, de manera más general, tiempos apropiados según la prioridad y la carga de trabajo de cada proceso).

En la práctica, estos objetivos suelen entrar en conflicto (por ejemplo, rendimiento versus latencia), por lo que un programador implementará un compromiso adecuado. La preferencia se mide en función de cualquiera de las preocupaciones mencionadas anteriormente, según las necesidades y los objetivos del usuario.

En entornos de tiempo real , como los sistemas integrados para el control automático en la industria (por ejemplo, la robótica ), el planificador también debe garantizar que los procesos puedan cumplir con los plazos ; esto es crucial para mantener la estabilidad del sistema. Las tareas programadas también se pueden distribuir a dispositivos remotos a través de una red y gestionarse a través de un back end administrativo.

El planificador es un módulo del sistema operativo que selecciona los próximos trabajos que se admitirán en el sistema y el próximo proceso que se ejecutará. Los sistemas operativos pueden tener hasta tres tipos distintos de planificadores: un planificador de largo plazo (también conocido como planificador de admisión o planificador de alto nivel), un planificador de mediano plazo y un planificador de corto plazo . Los nombres sugieren la frecuencia relativa con la que se realizan sus funciones.

El planificador de procesos es una parte del sistema operativo que decide qué proceso se ejecuta en un momento determinado. Normalmente tiene la capacidad de pausar un proceso en ejecución, moverlo al final de la cola de ejecución e iniciar un nuevo proceso; un planificador de este tipo se conoce como planificador preemptivo , de lo contrario es un planificador cooperativo . ^[5]

Distinguimos entre programación a largo plazo , programación a mediano plazo y programación a corto plazo en función de la frecuencia con la que se deben tomar decisiones. ^[6]

El planificador a largo plazo , o planificador de admisión , decide qué trabajos o procesos se admitirán en la cola de trabajos listos (en la memoria principal); es decir, cuando se intenta ejecutar un programa, el planificador a largo plazo autoriza o retrasa su admisión al conjunto de procesos que se están ejecutando en ese momento. Por lo tanto, este planificador dicta qué procesos se ejecutarán en un sistema, el grado de concurrencia que se admitirá en un momento dado (si se ejecutarán muchos o pocos procesos simultáneamente) y cómo se manejará la división entre procesos intensivos en E/S y procesos intensivos en CPU. El planificador a largo plazo es responsable de controlar el grado de multiprogramación.

En general, la mayoría de los procesos pueden describirse como limitados por E/S o limitados por CPU . Un proceso limitado por E/S es aquel que pasa más tiempo haciendo E/S que haciendo cálculos. Un proceso limitado por CPU, por el contrario, genera solicitudes de E/S con poca frecuencia, utilizando más tiempo para hacer cálculos. Es importante que un planificador a largo plazo seleccione una buena combinación de procesos limitados por E/S y limitados por CPU. Si todos los procesos están limitados por E/S, la cola de procesos listos casi siempre estará vacía y el planificador a corto plazo tendrá poco que hacer. Por otro lado, si todos los procesos están limitados por CPU, la cola de espera de E/S casi siempre estará vacía, los dispositivos no se utilizarán y nuevamente el sistema estará desequilibrado. El sistema con el mejor rendimiento tendrá una combinación de procesos limitados por CPU y limitados por E/S. En los sistemas operativos modernos, esto se utiliza para asegurarse de que los procesos en tiempo real obtengan suficiente tiempo de CPU para finalizar sus tareas. ^[7]

La programación a largo plazo también es importante en sistemas a gran escala, como sistemas de procesamiento por lotes , clústeres de computadoras , supercomputadoras y granjas de renderizado . Por ejemplo, en sistemas concurrentes , a menudo se requiere la programación conjunta de procesos que interactúan para evitar que se bloqueen debido a que esperan entre sí. En estos casos, se suele utilizar un software de programación de tareas de propósito especial para ayudar a estas funciones, además de cualquier soporte de programación de admisión subyacente en el sistema operativo.

Algunos sistemas operativos sólo permiten que se agreguen nuevas tareas si se tiene la certeza de que se cumplirán todos los plazos en tiempo real. El algoritmo heurístico específico que utiliza un sistema operativo para aceptar o rechazar nuevas tareas es el mecanismo de control de admisión . ^[8]

El planificador a medio plazo elimina temporalmente procesos de la memoria principal y los coloca en la memoria secundaria (como una unidad de disco duro ) o viceversa, lo que comúnmente se conoce como intercambio hacia afuera o intercambio hacia adentro (también incorrectamente como paginación hacia afuera o paginación hacia adentro ). El planificador a medio plazo puede decidir intercambiar un proceso que no ha estado activo durante algún tiempo, un proceso que tiene una prioridad baja, un proceso que falla la página con frecuencia o un proceso que está ocupando una gran cantidad de memoria para liberar memoria principal para otros procesos, intercambiando el proceso nuevamente más tarde cuando haya más memoria disponible o cuando el proceso se haya desbloqueado y ya no esté esperando un recurso.

En muchos sistemas actuales (aquellos que admiten la asignación de espacio de direcciones virtuales a un almacenamiento secundario distinto del archivo de intercambio), el planificador de mediano plazo puede, en realidad, desempeñar el papel del planificador de largo plazo, al tratar los binarios como procesos que se intercambian al momento de su ejecución. De esta manera, cuando se requiere un segmento del binario, se puede intercambiar a pedido, o cargar de forma diferida , también llamada paginación a demanda .

El planificador a corto plazo (también conocido como planificador de CPU ) decide cuál de los procesos listos en memoria se va a ejecutar (asignar una CPU) después de una interrupción de reloj , una interrupción de E/S, una llamada del sistema operativo u otra forma de señal . Por lo tanto, el planificador a corto plazo toma decisiones de planificación con mucha más frecuencia que los planificadores a largo o mediano plazo: como mínimo, se deberá tomar una decisión de planificación después de cada intervalo de tiempo, y estos son muy cortos. Este planificador puede ser preventivo , lo que implica que es capaz de eliminar a la fuerza procesos de una CPU cuando decide asignar esa CPU a otro proceso, o no preventivo (también conocido como voluntario o cooperativo ), en cuyo caso el planificador no puede forzar la salida de los procesos de la CPU.

Un programador preventivo se basa en un temporizador de intervalo programable que invoca un controlador de interrupciones que se ejecuta en modo kernel e implementa la función de programación.

Otro componente que interviene en la función de planificación de la CPU es el despachador, que es el módulo que otorga el control de la CPU al proceso seleccionado por el planificador de corto plazo. Recibe el control en modo kernel como resultado de una interrupción o llamada al sistema. Las funciones de un despachador incluyen lo siguiente:

• Cambios de contexto , en los que el despachador guarda el estado (también conocido como contexto ) del proceso o hilo que se estaba ejecutando previamente; luego, el despachador carga el estado inicial o previamente guardado del nuevo proceso.
• Cambiar al modo de usuario.
• Saltar a la ubicación adecuada en el programa de usuario para reiniciar ese programa indicado por su nuevo estado.

El despachador debe ser lo más rápido posible, ya que se lo invoca durante cada cambio de proceso. Durante los cambios de contexto, el procesador está prácticamente inactivo durante una fracción de tiempo, por lo que se deben evitar los cambios de contexto innecesarios. El tiempo que tarda el despachador en detener un proceso e iniciar otro se conoce como latencia de despacho . ^{[7] : 155}

Una disciplina de programación (también llamada política de programación o algoritmo de programación ) es un algoritmo utilizado para distribuir recursos entre las partes que los solicitan de forma simultánea y asincrónica. Las disciplinas de programación se utilizan en enrutadores (para gestionar el tráfico de paquetes), así como en sistemas operativos (para compartir el tiempo de CPU entre subprocesos y procesos ), unidades de disco ( programación de E/S ), impresoras ( spooler de impresión ), la mayoría de los sistemas integrados, etc.

Los principales objetivos de los algoritmos de programación son minimizar la escasez de recursos y garantizar la equidad entre las partes que utilizan los recursos. La programación se ocupa del problema de decidir a cuál de las solicitudes pendientes se le asignarán recursos. Existen muchos algoritmos de programación diferentes. En esta sección, presentamos varios de ellos.

En las redes informáticas con conmutación de paquetes y otros sistemas de multiplexación estadística , se utiliza el concepto de algoritmo de programación como alternativa a la puesta en cola de paquetes de datos por orden de llegada .

Los algoritmos de programación de mejor esfuerzo más simples son round-robin , cola justa (un algoritmo de programación justa de máximo-mínimo ), programación proporcional-justa y máximo rendimiento . Si se ofrece una calidad de servicio diferenciada o garantizada , en lugar de una comunicación de mejor esfuerzo, se puede utilizar cola justa ponderada .

En redes inalámbricas de paquetes avanzadas, como el sistema celular HSDPA (High-Speed ​​Downlink Packet Access) 3.5G , se puede utilizar la programación dependiente del canal para aprovechar la información del estado del canal . Si las condiciones del canal son favorables, se puede aumentar el rendimiento y la eficiencia espectral del sistema . En sistemas aún más avanzados, como LTE , la programación se combina con la asignación dinámica de canales paquete por paquete dependiente del canal , o mediante la asignación de portadoras múltiples OFDMA u otros componentes de ecualización del dominio de frecuencia a los usuarios que mejor pueden utilizarlos. ^[9]

Primero en entrar, primero en salir ( FIFO ), también conocido como primero en llegar, primero en ser atendido (FCFS), es el algoritmo de programació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 paracola de tareas , por ejemplo como se ilustra en esta sección.

• Dado que los cambios de contexto solo ocurren al finalizar el proceso y no se requiere reorganizar la cola de procesos, la sobrecarga de programación es mínima.
• El rendimiento puede ser bajo debido a que los procesos largos pueden retener la CPU, provocando que los procesos cortos esperen durante mucho tiempo (lo que se conoce como efecto convoy).
• No hay hambre, porque cada proceso tiene la oportunidad de ejecutarse después de un tiempo definido.
• El tiempo de entrega , el tiempo de espera y el tiempo de respuesta dependen del orden de llegada y pueden ser altos por las mismas razones mencionadas anteriormente.
• No se produce ninguna priorización, por lo que este sistema tiene problemas para cumplir con los plazos del proceso.
• La falta de priorización significa que, siempre que todos los procesos se completen, no habrá inanición. En un entorno en el que algunos procesos podrían no completarse, puede haber inanición.
• Se basa en colas.

El algoritmo de programación dinámica que se utiliza en los sistemas operativos en tiempo real para colocar procesos en una cola de prioridad es el de fecha límite más temprana (EDF, por sus siglas en inglés) o el de menor tiempo restante . Siempre que se produce un evento de programación (finaliza una tarea, se lanza una nueva tarea, etc.), se buscará en la cola el proceso más cercano a su fecha límite, que será el siguiente en programarse para su ejecución.

Similar a la estrategia de poner primero el trabajo más corto (SJF). Con esta estrategia, el programador organiza los procesos con el menor tiempo de procesamiento restante estimado para que sean los siguientes en la cola. Esto requiere conocimientos avanzados o estimaciones sobre el tiempo necesario para que se complete un proceso.

• Si llega un proceso más corto durante la ejecución de otro proceso, el proceso que se está ejecutando en ese momento se interrumpe (lo que se conoce como interrupción), lo que divide ese proceso en dos bloques de computación separados. Esto crea una sobrecarga excesiva a través de cambios de contexto adicionales. El programador también debe colocar cada proceso entrante en un lugar específico de la cola, lo que crea una sobrecarga adicional.
• Este algoritmo está diseñado para lograr el máximo rendimiento en la mayoría de los escenarios.
• El tiempo de espera y el tiempo de respuesta aumentan a medida que aumentan los requisitos computacionales del proceso. Dado que el tiempo de respuesta se basa en el tiempo de espera más el tiempo de procesamiento, los procesos más largos se ven afectados significativamente por esto. Sin embargo, el tiempo de espera total es menor que el del 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, el programador sólo puede intentar hacer que los procesos con plazos sean lo más breves posible.
• La inanición es posible, especialmente en un sistema ocupado con muchos procesos pequeños en ejecución.
• Para utilizar esta política deberíamos tener al menos dos procesos de diferente prioridad

El sistema operativo asigna un rango de prioridad fijo a cada proceso y el programador organiza los procesos en la cola de procesos listos según su prioridad. Los procesos de menor prioridad se ven interrumpidos por la llegada de procesos de mayor prioridad.

• Los gastos generales no son mínimos ni significativos.
• FPPS no tiene ninguna ventaja particular en términos de rendimiento sobre la programación FIFO.
• Si el número de clasificaciones es limitado, se puede caracterizar como una colección de colas FIFO, una para cada clasificación de prioridad. Los procesos en 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 con mayor prioridad tienen tiempos de espera y de respuesta más cortos.
• Los plazos se pueden cumplir dando mayor prioridad a los procesos con plazos.
• La inanición de procesos de menor prioridad es posible cuando una gran cantidad de procesos de alta prioridad hacen cola para consumir tiempo de CPU.

El programador asigna una unidad de tiempo fija por proceso y los recorre en ciclos. Si un proceso se completa dentro de ese intervalo de tiempo, se termina; de lo contrario, se reprograma después de darles una oportunidad a todos los demás procesos.

• La programación de RR implica muchos 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 del proceso.
• Debido a los largos tiempos de espera, en un sistema RR puro los plazos rara vez se cumplen.
• Nunca puede producirse una inanición, ya que no se da prioridad. El orden de asignación de la unidad de tiempo se basa en el tiempo de llegada del proceso, de forma similar al método FIFO.
• 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 en las que los procesos se pueden dividir fácilmente en diferentes grupos. Por ejemplo, se realiza una división comú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 programación. Es muy útil para problemas de memoria compartida .

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

Hay varios problemas de programación en los que el objetivo es decidir qué trabajo va a qué estación y a qué hora, de modo que se minimice el tiempo total de realización :

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

Un método muy común en los sistemas integrados es programar tareas manualmente. Esto se puede hacer, por ejemplo, de forma multiplexada en el tiempo. A veces, el núcleo se divide en tres o más partes: programación manual, preemptiva y a nivel de interrupción. Los métodos exactos para programar tareas suelen ser propietarios.

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

Al diseñar un sistema operativo, un programador debe considerar qué algoritmo de programación funcionará mejor para el uso que se le va a dar al sistema. No existe un algoritmo de programación universal que sea el mejor y muchos sistemas operativos utilizan combinaciones o extensiones de los algoritmos de programación anteriores.

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

El algoritmo utilizado puede ser tan simple como el de round-robin , en el que a cada proceso se le asigna el mismo tiempo (por ejemplo, 1 ms, normalmente entre 1 ms y 100 ms) en una lista cíclica. De este modo, el proceso A se ejecuta durante 1 ms, luego el proceso B, luego el proceso C y luego vuelve al proceso A.

Los algoritmos más avanzados tienen en cuenta la prioridad del proceso, o la importancia del mismo. Esto permite que algunos procesos utilicen más tiempo que otros. El núcleo siempre utiliza los recursos que necesita para garantizar el funcionamiento adecuado del sistema, por lo que se puede decir que tiene una prioridad infinita. En los sistemas SMP , se considera que la afinidad del procesador aumenta el rendimiento general del sistema, incluso si puede hacer que un proceso se ejecute más lentamente. Esto generalmente mejora el rendimiento al reducir el uso indebido de la memoria caché .

IBM OS/360 estaba disponible con tres programadores diferentes. Las diferencias eran tales que las variantes solían considerarse tres sistemas operativos diferentes:

• La opción Programador 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 Multiple Sequential Scheduler , conocida como Multiprogramming with a Fixed Number of Tasks (MFT) (Multiprogramación con un número fijo de tareas) permitía la ejecución de múltiples trabajos simultáneos. La ejecución se regía por una prioridad que tenía un valor predeterminado para cada secuencia o que podía solicitarse por separado para cada trabajo. La versión II de MFT agregó subtareas (subprocesos), que se ejecutaban con una prioridad basada en la del trabajo principal. Cada secuencia de trabajo definía la cantidad máxima de memoria que podía utilizar cualquier trabajo de esa secuencia.
• La opción de Programadores de Prioridad Múltiple , o Multiprogramación con un Número Variable de Tareas (MVT) , presentó subtareas desde el inicio; cada trabajo solicitaba la prioridad y la memoria que necesitaba antes de su ejecución.

Las versiones posteriores de almacenamiento virtual de MVS agregaron una función de Administrador de carga de trabajo al programador, 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 tenían 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 terminara o le dijera al sistema operativo que no necesitaba el procesador para poder pasar a otro proceso. Esto se suele llamar multitarea cooperativa. Windows 95 introdujo un planificador preemptivo rudimentario; sin embargo, para brindar compatibilidad con versiones anteriores, optó por permitir que las aplicaciones de 16 bits se ejecutaran sin preempción. ^[10]

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

El núcleo puede cambiar el nivel de prioridad de un hilo dependiendo de su uso de E/S y CPU y de si es interactivo (es decir, acepta y responde a la entrada de 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 programador fue modificado en Windows Vista para usar el registro del contador de ciclos de los procesadores modernos para realizar un seguimiento de exactamente cuántos ciclos de CPU ha ejecutado un hilo, en lugar de simplemente usar una rutina de interrupción de temporizador de intervalo. ^[12] Vista también usa un programador 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 una programación cooperativa para subprocesos, donde un proceso controla varios subprocesos cooperativos y también proporciona una programación preferente para tareas de multiprocesamiento. El núcleo programa las tareas de multiprocesamiento utilizando un algoritmo de programación preferente. Todos los procesos del Administrador de procesos se ejecutan dentro de una tarea de multiprocesamiento especial, llamada tarea azul . Esos procesos se programan de forma cooperativa, utilizando un algoritmo de programació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 programa los subprocesos de ese proceso de forma cooperativa; un subproceso cede el control del procesador a otro subproceso llamando YieldToAnyThreado YieldToThread. ^[14]

macOS utiliza una cola de retroalimentación de varios niveles, con cuatro bandas de prioridad para los subprocesos: normal, alta prioridad 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 hay tres valores posibles para la política de programación de subprocesos:

• Primero en entrar, primero en salir: una vez que se programa un subproceso con esta política, se ejecuta hasta completarse a menos que se lo bloquee, ceda voluntariamente el control de la CPU o se pueda enviar un subproceso con mayor prioridad. Solo los subprocesos con prioridad fija pueden tener una política de programación FIFO.
• Round Robin: es similar al esquema round-robin del programador de AIX versión 3 basado en intervalos de tiempo de 10 ms. Cuando un subproceso de RR tiene el control al final del intervalo de tiempo, se mueve al final de la cola de subprocesos despachables de su prioridad. Solo los subprocesos de prioridad fija pueden tener una política de programación Round Robin.
• OTROS: Esta política está definida por POSIX1003.4a como definida por la implementación. En AIX versión 4, esta política está definida 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 del reloj significa que un subproceso puede perder el control porque su valor de prioridad ha aumentado por encima del de otro subproceso despachable. Este es el comportamiento de AIX versión 3.

Los subprocesos son de interés principalmente para las aplicaciones que actualmente constan de varios procesos asincrónicos. Estas aplicaciones podrían imponer una carga más liviana en el sistema si se convierten a una estructura multiproceso.

AIX 5 implementa las siguientes políticas de programación: FIFO, round robin y round robin justo. 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 política round robin justa se denomina SCHED_OTHER. ^[16]

Linux 1.2 utilizó una política de programación por turnos . ^[17]

Linux 2.2 agregó clases de programación y soporte para multiprocesamiento simétrico (SMP). ^[17]

En Linux 2.4, ^[17] se utilizó un planificador O(n) con una cola de retroalimentación multinivel con niveles de prioridad que van de 0 a 140; 0 a 99 están reservados para tareas en tiempo real y 100 a 140 se consideran niveles de tarea agradable . Para tareas en tiempo real, el quantum de tiempo para cambiar de proceso fue de aproximadamente 200 ms, y para tareas agradables de aproximadamente 10 ms. ^{[ cita requerida ]} El planificador corrió a través de la cola de ejecución de todos los procesos listos, dejando que los procesos de mayor prioridad vayan primero y se ejecuten a través de sus franjas de tiempo, después de lo cual se colocarán en una cola expirada. Cuando la cola activa está vacía, la cola expirada se convertirá en la cola activa y viceversa.

Sin embargo, algunas distribuciones empresariales de Linux como SUSE Linux Enterprise Server reemplazaron este programador con una versión retroactiva del programador O(1) (que fue mantenido por Alan Cox en su serie Linux 2.4-ac Kernel) al kernel Linux 2.4 utilizado por la distribución.

En las versiones 2.6.0 a 2.6.22, el núcleo utilizó un planificador O(1) desarrollado por Ingo Molnar y muchos otros desarrolladores de núcleos durante el desarrollo de Linux 2.5. Para muchos núcleos de la época, Con Kolivas desarrolló conjuntos de parches que mejoraron la interactividad con este planificador o incluso lo reemplazaron con sus propios planificadores.

El trabajo de Con Kolivas, más significativamente su implementación de una programación justa llamada Rotating Staircase Deadline (RSDL), inspiró a Ingo Molnár a desarrollar el Completely Fair Scheduler (CFS) como reemplazo del planificador O(1) anterior , dando crédito a Kolivas en su anuncio. ^[18] CFS es la primera implementación de un planificador de procesos de cola justa ampliamente utilizado en un sistema operativo de propósito general. ^[19]

El CFS utiliza un algoritmo de programación clásico y bien estudiado llamado cola justa , inventado originalmente para redes de paquetes . La cola justa se había aplicado anteriormente a la programación de CPU con el nombre de programación por pasos . El planificador de cola justa CFS tiene una complejidad de programación de , donde N es el número de tareas en la cola de ejecución . La elección de una tarea se puede realizar en tiempo constante, pero la reinserción de una tarea después de que se haya ejecutado requiere operaciones, porque la cola de ejecución se implementa como un árbol rojo-negro .${\displaystyle O(\log N)}$${\displaystyle O(\log N)}$

El Brain Fuck Scheduler , también creado por Con Kolivas, es una alternativa al CFS.

En 2023, Peter Zijlstra propuso reemplazar CFS con un programador de procesos de programación de fecha límite virtual elegible más temprana (EEVDF). ^{[20] [21]} El objetivo era eliminar la necesidad de parches de latencia CFS. ^[22]

FreeBSD utiliza una cola de retroalimentación multinivel con prioridades que van de 0 a 255. 0 a 63 están reservadas para interrupciones, 64 a 127 para la mitad superior del núcleo, 128 a 159 para subprocesos de usuario en tiempo real, 160 a 223 para subprocesos de usuario de tiempo compartido y 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. ^[23]

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

Solaris utiliza una cola de retroalimentación de varios niveles 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, ^[23] cuando un proceso termina de usar su quantum de tiempo, se le da una nueva prioridad y se vuelve a poner en la cola. Solaris 9 introdujo dos nuevas clases de programación, a saber, la clase de prioridad fija y la clase de reparto justo. Los subprocesos con prioridad fija tienen el mismo rango de prioridad que el de la clase de tiempo compartido, pero sus prioridades no se ajustan dinámicamente. La clase de programación justa utiliza cuotas de CPU para priorizar los subprocesos para las decisiones de programació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]

• Sistemas operativos: tres piezas sencillas de Remzi H. Arpaci-Dusseau y Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Capítulos relevantes: Programación: Introducción Cola de retroalimentación de varios niveles Programación de reparto proporcional Programación de varios procesadores
• Breve discusión de los algoritmos de programación de tareas
• Comprensión del núcleo de Linux: Capítulo 10 Programación de procesos
• Kerneltrap: artículos sobre el programador del kernel de Linux
• Monitoreo y ajuste de CPU AIX
• Introducción de Josh Aas a la implementación del programador de CPU de Linux 2.6.8.1
• Peter Brucker, Sigrid Knust. Resultados de complejidad para problemas de programación [2]
• TORSCHE Scheduling Toolbox para Matlab es una caja de herramientas de algoritmos de programación y gráficos.
• Una encuesta sobre la programación de paquetes en redes celulares
• Gestión de clústeres a gran escala en Google con Borg