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 mecanismo 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:
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 un 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 cargarlo de forma diferida , también llamado 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:
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.
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.
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.
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.
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 :
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.
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:
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:
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 .
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]
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.
un cliente que requiere x segundos de servicio, su tiempo de respuesta será igual a su tiempo de servicio x más su tiempo de espera.
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 .
el tiempo de respuesta puede no ser el mejor criterio. A menudo, un proceso puede producir algún resultado con bastante rapidez y puede continuar calculando nuevos resultados mientras se envían los resultados anteriores al usuario. Por lo tanto, otra medida es el tiempo desde el envío de una solicitud hasta que se produce la primera respuesta. Esta medida, llamada tiempo de respuesta, es el tiempo que tarda en comenzar a responder, no el tiempo que tarda en generar la respuesta.
{{cite web}}: CS1 maint: copia archivada como título ( enlace )