Programación (informática)

Este artículo trata sobre la programación en general. Para redes, consulte Programador de red . Para otros usos, consulte Programación (desambiguación) .

En informática , la programación es el método mediante el cual el trabajo se asigna a los recursos que completan el trabajo. El trabajo puede ser elementos de computación virtual como subprocesos , procesos o flujos de datos , que a su vez se programan en recursos de hardware como procesadores , enlaces de red o tarjetas de expansión .

Un planificador es el que realiza la actividad de planificación. Los programadores a menudo se implementan para mantener ocupados todos los recursos de la computadora (como en el equilibrio de carga ), permitir que múltiples usuarios compartan los recursos del sistema de manera efectiva o para 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 hace posible que la computadora pueda realizar múltiples tareas con una sola unidad central de procesamiento (CPU).

Objetivos

Un planificador 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 la ejecución); minimizar la latencia o el tiempo de respuesta (tiempo desde que el trabajo está listo hasta que se termina 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] o maximizar la equidad(tiempo de CPU igual para cada proceso, o tiempos más generalmente apropiados según la prioridad y la carga de trabajo de cada proceso). En la práctica, estos objetivos a menudo entran en conflicto (por ejemplo, rendimiento frente a latencia), por lo que un planificador implementará un compromiso adecuado. La preferencia se mide por cualquiera de las preocupaciones mencionadas anteriormente, dependiendo de las necesidades y 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 asegurarse de que los procesos puedan cumplir con los plazos ; esto es crucial para mantener estable el sistema. Las tareas programadas también pueden distribuirse a dispositivos remotos a través de una red y administrarse a través de un backend administrativo.

Tipos de programadores del sistema operativo

Consulte también: Programador de red , Programación de E / S y Programador de trabajos

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

Programador de procesos

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

Distinguimos entre "programación a largo plazo", "programación a mediano plazo" y "programación a corto plazo" según la frecuencia con la que se deben tomar las decisiones. ^[6]

Programación a largo plazo

El programador a largo plazo , o programador de admisión , decide qué trabajos o procesos se admitirán en la cola lista (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 en ejecución. Por lo tanto, este programador dicta qué procesos se ejecutarán en un sistema y el grado de simultaneidad que se admitirá en un momento determinado: si se ejecutarán muchos o pocos procesos al mismo tiempo, y cómo se dividirá entre I / O intensivo y CPU. -Se deben manejar procesos intensivos. El planificador a largo plazo es responsable de controlar el grado de multiprogramación.

En general, la mayoría de los procesos se pueden describir como vinculados a E / S o vinculados a la CPU. Un proceso vinculado a E / S es aquel que pasa más tiempo haciendo E / S que haciendo cálculos. Un proceso vinculado a la CPU, por el contrario, genera solicitudes de E / S con poca frecuencia, y utiliza más tiempo para realizar cálculos. Es importante que un programador a largo plazo seleccione una buena combinación de procesos de procesos vinculados a E / S y vinculados a CPU. Si todos los procesos están vinculados a E / S, la cola lista casi siempre estará vacía y el programador a corto plazo tendrá poco que hacer. Por otro lado, si todos los procesos están vinculados a la CPU, la cola de espera de E / S casi siempre estará vacía, los dispositivos no se usarán y nuevamente el sistema estará desequilibrado. Por lo tanto, el sistema con el mejor rendimiento tendrá una combinación de procesos vinculados a CPU y vinculados a E / S. En los sistemas operativos modernos, esto se usa 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 los sistemas de procesamiento por lotes , los clústeres de computadoras , las supercomputadoras y las granjas de procesamiento . Por ejemplo, en los sistemas concurrentes , a menudo se requiere la programación conjunta de los procesos que interactúan para evitar que se bloqueen debido a que se esperan unos a otros. En estos casos, el software de programación de trabajos de propósito especial se usa típicamente para ayudar a estas funciones, además de cualquier soporte de programación de admisión subyacente en el sistema operativo.

Algunos sistemas operativos solo permiten que se agreguen nuevas tareas si está seguro de que aún se pueden cumplir todos los plazos en tiempo real. El algoritmo heurístico específico utilizado por un sistema operativo para aceptar o rechazar nuevas tareas es el mecanismo de control de admisión . ^[8]

Programación a mediano plazo

El programador de mediano plazo elimina temporalmente los 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 denomina "intercambio" o "intercambio" (también incorrectamente como " paginación out "o" paging in "). El planificador a medio plazo puede decidir cambiar un proceso que no ha estado activo durante algún tiempo, o un proceso que tiene una prioridad baja, o un proceso que tiene fallas en 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 más tarde cuando hay más memoria disponible, o cuando el proceso se ha desbloqueado y ya no está esperando un recurso. [Stallings, 396] [Stallings, 370]

En muchos sistemas actuales (los que admiten la asignación del espacio de direcciones virtuales a un almacenamiento secundario que no sea el archivo de intercambio), el programador a mediano plazo puede desempeñar el papel del programador a largo plazo, al tratar los binarios como "procesos intercambiados" en su ejecución. De esta manera, cuando se requiere un segmento del binario, se puede intercambiar a pedido, o "cargarlo en forma diferida", [Stallings, 394] también llamado paginación por demanda .

Programación a corto plazo

El programador a corto plazo (también conocido como programador de la CPU ) decide cuál de los procesos listos en memoria se ejecutará (se le asignará una CPU) después de una interrupción del reloj , una interrupción de E / S, una llamada al sistema operativo u otra forma. de señal . Por lo tanto, el programador a corto plazo toma decisiones de programación con mucha más frecuencia que los programadores a largo o medio plazo; una decisión de programación tendrá que tomarse como mínimo después de cada segmento de tiempo, y estas son muy breves. Este planificador puede ser preventivo, lo que implica que es capaz de eliminar por 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 programador no puede para "forzar" los procesos fuera 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.

Despachador

Otro componente que está involucrado en la función de programación de la CPU es el despachador, que es el módulo que le da control de la CPU al proceso seleccionado por el programador a corto plazo. Recibe control en modo kernel como resultado de una interrupción o llamada al sistema. Las funciones de un despachador trapean lo siguiente:

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

El despachador debe ser lo más rápido posible, ya que se 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 deben evitarse los cambios de contexto innecesarios. El tiempo que le toma al despachador detener un proceso e iniciar otro se conoce como latencia de despacho . ^{[7] : 155}

Programación de disciplinas

Las disciplinas de programación son algoritmos que se utilizan 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 manejar 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 ( cola de impresión ), la mayoría de los sistemas integrados, etc. .

Los objetivos principales 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 aborda el problema de decidir a cuál de las solicitudes pendientes se le asignarán recursos. Hay muchos algoritmos de programación diferentes. En esta sección, presentamos varios de ellos.

En las redes informáticas de conmutación de paquetes y otros multiplexados estadísticos , la noción de un algoritmo de programación se utiliza como una 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 el round-robin , la cola justa (un algoritmo de programación justa máximo-mínimo ), la programación proporcionalmente justa y el rendimiento máximo . Si se ofrece una calidad de servicio diferenciada o garantizada , a diferencia de la comunicación con el mejor esfuerzo, se pueden utilizar colas equitativas ponderadas .

En las redes inalámbricas de radio por paquetes avanzadas, como el sistema celular HSDPA (Acceso de paquetes de enlace descendente de alta velocidad) 3.5G , se puede usar 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 mediante la asignación dinámica de canales paquete por paquete dependiente del canal , o mediante la asignación de múltiples portadoras OFDMA u otros componentes de ecualización de dominio de frecuencia a los usuarios que mejor pueden utilizarlos.^[9]

Por orden de llegada

Artículo principal: FIFO (informática y electrónica)

Un grupo de subprocesos de muestra (cuadros verdes) con una cola (FIFO) de tareas en espera (azul) y una cola de tareas completadas (amarillo)

Primero en entrar, primero en salir ( FIFO ), también conocido como primero en llegar, primero en ser servido (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 lista. Esto se usa comúnmente para una cola 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 reorganización de la cola del proceso, la sobrecarga de programación es mínima.
• El rendimiento puede ser bajo, porque los procesos largos pueden contener la CPU, lo que hace que los procesos cortos esperen mucho tiempo (conocido como efecto convoy).
• Sin hambre, porque cada proceso tiene la oportunidad de ejecutarse después de un tiempo definido.
• El tiempo de respuesta, 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 da prioridad, por lo que este sistema tiene problemas para cumplir con los plazos del proceso.
• La falta de priorización significa que mientras todos los procesos se completen, no habrá hambre. En un entorno donde algunos procesos pueden no completarse, puede haber inanición.
• Se basa en hacer cola.

Programación prioritaria

Artículo principal: Primera programación de la fecha límite más temprana

Ver también: Programación monótona de fechas límite

La primera fecha límite primero (EDF) o el menor tiempo restante es un algoritmo de programación dinámica que se utiliza en los sistemas operativos en tiempo real para colocar los procesos en una cola de prioridad. Siempre que se produzca un evento de programación (finaliza una tarea, se libera una nueva tarea, etc.), se buscará en la cola el proceso más cercano a su fecha límite, que será el siguiente en ser programado para su ejecución.

El tiempo restante más corto primero

Artículo principal: menor tiempo restante

Similar al trabajo más corto primero (SJF). Con esta estrategia, el planificador organiza los procesos con el menor tiempo de procesamiento estimado restante para ser el siguiente 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 actualmente se interrumpe (lo que se conoce como preferencia), dividiendo ese proceso en dos bloques informáticos separados. Esto crea una sobrecarga excesiva a través del cambio de contexto adicional. El programador también debe colocar cada proceso entrante en un lugar específico de la cola, creando una sobrecarga adicional.
• Este algoritmo está diseñado para un rendimiento máximo 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 FIFO, ya que ningún proceso tiene que esperar la finalización del proceso más largo.
• No se presta especial atención a los plazos, el programador solo puede intentar que los procesos con plazos sean lo más cortos posible.
• La inanición es posible, especialmente en un sistema ocupado con muchos procesos pequeños en ejecución.
• Para utilizar esta política debemos tener al menos dos procesos de diferente prioridad

Programación preferente de prioridad fija

Artículo principal: Programación preferente de prioridad fija

El sistema operativo asigna un rango de prioridad fijo a cada proceso, y el programador organiza los procesos en la cola lista en orden de prioridad. Los procesos de menor prioridad son interrumpidos por los procesos entrantes de mayor prioridad.

• La sobrecarga no es mínima ni significativa.
• 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 de 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 respuesta más pequeños.
• Los plazos se pueden cumplir dando mayor prioridad a los procesos con plazos.
• La inanición de los procesos de menor prioridad es posible con una gran cantidad de procesos de alta prioridad en cola para el tiempo de la CPU.

Programación por turnos

Artículo principal: Programación por turnos

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

• La programación de RR implica una gran sobrecarga, 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 altos tiempos de espera, los plazos rara vez se cumplen en un sistema RR puro.
• El hambre nunca puede ocurrir, ya que no se le da prioridad. El orden de asignación de unidades de tiempo se basa en el tiempo de llegada del proceso, similar a FIFO.
• Si Time-Slice es grande, se convierte en FCFS / FIFO o si es corto, se convierte en SJF / SRTF.

Programación de colas de varios niveles

Artículo principal: cola multinivel

Se utiliza para situaciones en las que los procesos se dividen fácilmente en diferentes grupos. Por ejemplo, se hace 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 .

Programadores que conservan el trabajo

Artículo principal: Programador de conservación de trabajo

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.

Problemas de optimización de programación

Existen varios problemas de programación en los que el objetivo es decidir qué trabajo va a qué estación ya qué hora, de modo que se minimice la duración total :

• Programación del taller de trabajos  : hay n trabajos y m estaciones idénticas. Cada trabajo debe ejecutarse en una sola máquina. Por lo general, esto se considera un problema en línea.
• Programación de taller abierto  : hay n trabajos y m estaciones diferentes. Cada trabajo debe pasar algún tiempo en cada estación, en un pedido gratuito.
• Programación del taller de flujo  : hay n trabajos y m estaciones diferentes. Cada trabajo debe pasar algún tiempo en cada estación, en un orden predeterminado.

Programación manual

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

• Sin problemas de escasez de recursos
• Muy alta previsibilidad; permite la implementación de sistemas duros en tiempo real
• Casi sin gastos generales
• Puede que no sea óptimo para todas las aplicaciones
• La efectividad depende completamente de la implementación

Elegir un algoritmo de programación

Al diseñar un sistema operativo, un programador debe considerar qué algoritmo de programación funcionará mejor para el uso que verá el sistema. No existe un algoritmo de programación "mejor" universal, y muchos sistemas operativos utilizan ampliaciones o combinaciones de los algoritmos de programación anteriores.

Por ejemplo, Windows NT / XP / Vista utiliza una cola de retroalimentación multinivel , una combinación de programación preventiva de prioridad fija, round-robin y algoritmos de primero en entrar, primero en salir. En este sistema, los subprocesos pueden aumentar o disminuir dinámicamente su prioridad dependiendo de si ya se ha atendido o si ha estado esperando mucho tiempo. Cada nivel de prioridad está representado por su propia cola, con programación por turnos entre los subprocesos de alta prioridad y FIFOentre 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 más largos de alta prioridad.

Implementaciones del programador de procesos del sistema operativo

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

Los algoritmos más avanzados tienen en cuenta la prioridad del proceso o la importancia del proceso. Esto permite que algunos procesos utilicen más tiempo que otros procesos. El kernel siempre usa 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. Por lo general, esto mejora el rendimiento al reducir la eliminación de caché .

OS / 360 y sucesores

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

• La opción Planificador secuencial único , también conocida como Programa de control primario (PCP), proporcionó la ejecución secuencial de un único flujo de trabajos.
• La opción de Programador secuencial múltiple , conocida como Programación múltiple con un número fijo de tareas (MFT), proporcionó 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 flujo o podía solicitarse por separado para cada trabajo. La versión II de MFT agregó subtareas (subprocesos), que se ejecutaron con una prioridad basada en la del trabajo principal. Cada secuencia de trabajos definió la cantidad máxima de memoria que podrí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) , incluía subtareas desde el principio; cada trabajo solicitó la prioridad y la memoria que requería antes de la ejecución.

Las versiones posteriores de almacenamiento virtual de MVS agregaron una función de Workload Manager al programador, que programa los recursos del procesador de acuerdo con un esquema elaborado definido por la instalación.

Windows

Los primeros sistemas MS-DOS y Microsoft Windows no eran multitarea y, como tales, no contaban con un programador. Windows 3.1x usó un programador no preventivo, lo que significa que no interrumpió los programas. Dependía del programa para finalizar o decirle al sistema operativo que no necesitaba el procesador para poder pasar a otro proceso. A esto se le suele llamar multitarea cooperativa. Windows 95 introdujo un programador preventivo rudimentario; sin embargo, para el soporte heredado optó por permitir que las aplicaciones de 16 bits se ejecuten sin preferencia. ^[10]

Los sistemas operativos basados ​​en Windows NT utilizan una cola de comentarios de varios niveles. Se definen 32 niveles de prioridad, de 0 a 31, siendo las prioridades de 0 a 15 las prioridades "normales" y las prioridades de 16 a 31 son prioridades suaves en tiempo real, que requieren privilegios para asignar. 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 en el proceso, que luego el sistema combina en el nivel de prioridad absoluta.

El kernel puede cambiar el nivel de prioridad de un hilo dependiendo de su E / S y uso de CPU y si es interactivo (es decir, acepta y responde a la entrada de humanos), aumentando la prioridad de los procesos interactivos y limitados de E / S y reduciendo la de Procesos vinculados a la CPU, para aumentar la capacidad de respuesta de las aplicaciones interactivas. ^[11] El programador se modificó en Windows Vista para usar el registro de 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 del temporizador de intervalos. ^[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 y macOS clásicos

Mac OS 9 usa programación cooperativa para subprocesos, donde un proceso controla múltiples subprocesos cooperativos y también proporciona programación preventiva para tareas de multiprocesamiento. El kernel programa las tareas de multiprocesamiento mediante un algoritmo de programación preventiva. Todos los procesos de Process Manager se ejecutan dentro de una tarea especial de multiprocesamiento, denominada "tarea azul". Estos procesos se programan de forma cooperativa, utilizando un algoritmo de programación por turnos; 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 manera cooperativa; un subproceso cede el control del procesador a otro subproceso llamando YieldToAnyThreadoYieldToThread. ^[14]

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

AIX

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 su finalización a menos que esté bloqueado, ceda voluntariamente el control de la CPU o un subproceso de mayor prioridad se pueda enviar. Solo los subprocesos de prioridad fija pueden tener una política de programación FIFO.
• Round Robin: Esto es similar al esquema de round robin del programador AIX Versión 3 basado en intervalos de tiempo de 10 ms. Cuando un subproceso RR tiene el control al final del intervalo de tiempo, se mueve al final de la cola de subprocesos asignables de su prioridad. Solo los subprocesos de prioridad fija pueden tener una política de programación Round Robin.
• OTROS: POSIX1003.4a define esta política 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 del reloj significa que un subproceso puede perder el control porque su valor de prioridad ha aumentado por encima del de otro subproceso asignable. Este es el comportamiento de AIX Versión 3.

Los subprocesos son de interés principalmente para aplicaciones que actualmente constan de varios procesos asincrónicos. Estas aplicaciones pueden imponer una carga más ligera al 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 de round robin se denomina SCHED_RR en AIX y el round robin justo se denomina SCHED_OTHER. ^[dieciséis]

Linux

Una estructura muy simplificada del kernel de Linux, que incluye programadores de procesos, programadores de E / S y programadores de paquetes.

Linux 2.4

En Linux 2.4, se usó un programador O (n) con una cola de retroalimentación multinivel con niveles de prioridad que iban de 0 a 140; 0–99 están reservados para tareas en tiempo real y 100–140 se consideran niveles de tareas agradables . Para las tareas en tiempo real, el cuanto de tiempo para los procesos de conmutación fue de aproximadamente 200 ms y para las tareas agradables aproximadamente 10 ms. ^{[ cita requerida ]} El programador corrió a través de la cola de ejecución de todos los procesos listos, dejando que los procesos de mayor prioridad fueran primero y se ejecutaran en sus intervalos de tiempo, después de lo cual se colocarán en una cola vencida. Cuando la cola activa está vacía, la cola caducada se convertirá en la cola activa y viceversa.

Sin embargo, algunas distribuciones empresariales de Linux , como SUSE Linux Enterprise Server, reemplazaron este programador con un backport 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. .

Linux 2.6.0 a Linux 2.6.22

En las versiones 2.6.0 a 2.6.22, el kernel utilizó un programador O (1) desarrollado por Ingo Molnar y muchos otros desarrolladores del kernel durante el desarrollo de Linux 2.5. Para muchos kernel en el marco de tiempo, Con Kolivas desarrolló conjuntos de parches que mejoraron la interactividad con este programador o incluso lo reemplazó con sus propios programadores.

Desde Linux 2.6.23

El trabajo de Con Kolivas, más significativamente su implementación de " programación justa " llamada "Fecha límite de escalera giratoria", inspiró a Ingo Molnár a desarrollar el Programador Completamente Justo como reemplazo del programador O (1) anterior , acreditando a Kolivas en su anuncio. ^[17] CFS es la primera implementación de un programador de procesos de colas equitativo ampliamente utilizado en un sistema operativo de propósito general. ^[18]

El Programador Completamente Justo (CFS) utiliza un algoritmo de programación clásico bien estudiado llamado colas justas originalmente inventado para redes de paquetes . La cola justa se había aplicado previamente a la programación de CPU con el nombre de programación de pasos . El programador CFS de cola justa tiene una complejidad de programación de O ( log N), 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 volver a insertar una tarea después de que se haya ejecutado requiere operaciones O (log N), porque la cola de ejecución se implementa como un árbol rojo-negro .

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

FreeBSD

FreeBSD usa una cola de retroalimentación multinivel con prioridades que van de 0 a 255. 0–63 están reservados para interrupciones, 64–127 para la mitad superior del kernel, 128–159 para subprocesos de usuario en tiempo real, 160–223 para subprocesos de usuario de tiempo compartido y 224–255 para subprocesos de usuario inactivos. Además, como Linux, usa la configuración de cola activa, pero también tiene una cola inactiva. ^[19]

NetBSD

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

Solaris

Solaris utiliza una cola de retroalimentación multinivel con prioridades que oscilan entre 0 y 169. Las prioridades 0–59 están reservadas para subprocesos de tiempo compartido, 60–99 para subprocesos del sistema, 100–159 para subprocesos en tiempo real y 160–169 para interrupciones de baja prioridad. . A diferencia de Linux, ^[19] cuando un proceso se realiza utilizando su cuanto 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 acciones justas. 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 usa recursos compartidos de CPUpara priorizar subprocesos para la programación de decisiones. Los recursos compartidos de la CPU indican el derecho a los recursos de la CPU. Se asignan a un conjunto de procesos, que se conocen colectivamente como proyecto. ^[7]

Resumen

Sistema operativo	Derecho preferente de compra	Algoritmo
Amiga OS	sí	Programación priorizada por turnos
FreeBSD	sí	Cola de retroalimentación multinivel
Kernel de Linux anterior a 2.6.0	sí	Cola de retroalimentación multinivel
Kernel de Linux 2.6.0–2.6.23	sí	O (1) programador
Kernel de Linux posterior a 2.6.23	sí	Programador completamente justo
clásico Mac OS pre-9	Ninguno	Programador cooperativo
Mac OS 9	Algunos	Programador preventivo para tareas MP y cooperativo para procesos e hilos
Mac OS	sí	Cola de retroalimentación multinivel
NetBSD	sí	Cola de retroalimentación multinivel
Solaris	sí	Cola de retroalimentación multinivel
Windows 3.1x	Ninguno	Programador cooperativo
Windows 95 , 98 , Me	Mitad	Programador preventivo para procesos de 32 bits y cooperativo para procesos de 16 bits
Windows NT (incluidos 2000, XP, Vista, 7 y Server)	sí	Cola de retroalimentación multinivel

Ver también

• Problema de selección de actividad
• Envejecimiento (programación)
• Programador de Atropos
• Planificación y programación automatizadas
• Ejecutivo cíclico
• Programación de prioridad dinámica
• Fondo plano
• Sistema operativo interrumpible
• Programación del menor tiempo de inactividad
• Programación de loterías
• Inversión de prioridad
• Estados de proceso
• Teoría de colas
• Programación de tarifas monótona
• Red de recursos y tareas
• Programación (procesos de producción)
• Programación estocástica
• Función de utilidad de tiempo

Notas

1. CL, Liu; James W., Layland (enero de 1973). "Algoritmos de programación para multiprogramación en un entorno de tiempo real duro". Revista de la ACM . ACM. 20 (1): 46–61. doi : 10.1145 / 321738.321743 . S2CID  207669821 . Definimos el tiempo de respuesta de una solicitud para una determinada tarea como el lapso de tiempo entre la solicitud y el final de la respuesta a esa solicitud.
2. Kleinrock, Leonard (1976). Sistemas de colas, vol. 2: Aplicaciones informáticas (1 ed.). Wiley-Interscience. pag. 171 . ISBN 047149111X. Para un cliente que requiera x segundos de servicio, su tiempo de respuesta será igual a su tiempo de servicio x más su tiempo de espera.
3. Feitelson, Dror G. (2015). Modelado de cargas de trabajo para la evaluación del desempeño de sistemas informáticos . Prensa de la Universidad de Cambridge. Sección 8.4 (página 422) en la versión 1.03 del manuscrito disponible gratuitamente. ISBN 9781107078239. Consultado el 17 de octubre de 2015 . si denotamos el tiempo que un trabajo espera en la cola por t _w , y el tiempo que realmente se ejecuta por t _r , entonces el tiempo de respuesta es r = t _w + t _r .
4. Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2012). Conceptos del sistema operativo (9 ed.). Wiley Publishing. pag. 187. ISBN 978-0470128725. En un sistema interactivo, el tiempo de respuesta puede no ser el mejor criterio. A menudo, un proceso puede producir algo de salida bastante temprano y puede continuar calculando nuevos resultados mientras los resultados anteriores se envían al usuario. Así, otra medida es el tiempo desde la presentación de una solicitud hasta que se produce la primera respuesta. Esta medida, llamada tiempo de respuesta, es el tiempo que se tarda en empezar a responder, no el tiempo que se tarda en generar la respuesta.
5. Paul Krzyzanowski (19 de febrero de 2014). "Programación de procesos: ¿Quién va a ejecutar a continuación?" . cs.rutgers.edu . Consultado el 11 de enero de 2015 .
6. Raphael Finkel ."Un vademécum de sistemas operativos" . Prentice Hall. 1988. "Capítulo 2: Gestión del tiempo". pag. 27.
7. Abraham Silberschatz , Peter Baer Galvin y Greg Gagne (2013). Conceptos del sistema operativo . 9 . John Wiley & Sons, Inc. ISBN 978-1-118-06333-0.
8. Robert Kroeger (2004). "Control de admisión para aplicaciones en tiempo real de autor independiente" . UWSpace. http://hdl.handle.net/10012/1170 . Apartado "2.6 Control de admisión". pag. 33.
9. Guowang Miao ; Jens Zander; Ki Won Sung; Ben Slimane (2016). Fundamentos de las redes de datos móviles . Prensa de la Universidad de Cambridge . ISBN 978-1107143210.
10. Primeras ventanas en Wayback Machine (índice de archivo)
11. Sriram Krishnan. "Historia de dos programadores Windows NT y Windows CE" . Archivado desde el original el 22 de julio de 2012.
12. "Administración de Windows: dentro del kernel de Windows Vista: parte 1" . Technet.microsoft.com . 2016-11-14 . Consultado el 9 de diciembre de 2016 .
13. [1]
14. "Nota técnica TN2028: arquitecturas de subprocesamiento" . developer.apple.com . Consultado el 15 de enero de 2019 .
15. "Interfaces de subprocesos y programación de Mach" . developer.apple.com . Consultado el 15 de enero de 2019 .
16. [2] Archivado el 11 de agosto de 2011 en la Wayback Machine.
17. Molnár, Ingo (13 de abril de 2007). "[parche] Núcleo del programador modular y programador completamente justo [CFS]" . linux-kernel (lista de correo).
18. Tong Li; Dan Baumberger; Scott Hahn. "Programación equitativa de multiprocesador eficiente y escalable utilizando Round-Robin ponderado distribuido" (PDF) . Happyli.org . Consultado el 9 de diciembre de 2016 .
19. "Comparación de núcleos Solaris, Linux y FreeBSD" (PDF) . Archivado desde el original (PDF) el 7 de agosto de 2008.

Referencias

• Błażewicz, Jacek; Ecker, KH; Pesch, E .; Schmidt, G .; Weglarz, J. (2001). Programación de procesos informáticos y de fabricación (2 ed.). Berlín [ua]: Springer. ISBN 3-540-41931-4.
• Stallings, William (2004). Principios internos y de diseño de los sistemas operativos (cuarta ed.). Prentice Hall. ISBN 0-13-031999-6.
• Información sobre el programador Linux 2.6 O (1)

Lectura adicional

• Sistemas operativos: tres piezas fáciles de Remzi H. Arpaci-Dusseau y Andrea C. Arpaci-Dusseau. Libros de Arpaci-Dusseau, 2014. Capítulos relevantes: Programación: Introducción Cola de retroalimentación de varios niveles Programación de participación proporcional Programación de multiprocesador
• Breve discusión sobre los algoritmos de programación de trabajos
• Comprensión del kernel de Linux: Capítulo 10 Programación de procesos
• Kerneltrap: artículos del programador del kernel de Linux
• Monitoreo y ajuste de CPU de 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 [3]
• 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 de redes celulares
• Gestión de clústeres a gran escala en Google con Borg