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 hilos , procesos o flujos de datos .
La actividad de programación se lleva a cabo mediante un proceso llamado planificador . Los programadores a menudo están diseñados para mantener ocupados todos los recursos de la computadora (como en el equilibrio de carga ), permitir que múltiples usuarios compartan recursos del sistema de manera efectiva 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 la computadora realice múltiples tareas con una sola unidad central de procesamiento (CPU).
Un planificador puede apuntar a uno o más objetivos, por ejemplo:
En la práctica, estos objetivos suelen entrar 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 en tiempo real , como los sistemas integrados para el control automático en la industria (por ejemplo, robótica ), el planificador también debe garantizar que los procesos puedan cumplir con los plazos ; Esto es crucial para mantener estable el sistema. Las tareas programadas también se pueden distribuir a dispositivos remotos a través de una red y administrarse a través de un back-end administrativo.
El programador 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 relativa frecuencia con la que se realizan sus funciones.
El programador 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 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 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 actualmente. Por lo tanto, este programador dicta qué procesos se ejecutarán en un sistema, el grado de concurrencia que se admitirá en cualquier momento (si muchos o pocos procesos se ejecutarán simultáneamente y cómo se dividirá entre los de uso intensivo de E/S y los de CPU). se deben gestionar procesos intensivos. 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 vinculados a E/S o vinculados a la CPU . Un proceso vinculado a E/S es aquel que dedica más tiempo a realizar E/S que a realizar cálculos. Por el contrario, un proceso vinculado a la CPU genera solicitudes de E/S con poca frecuencia y utiliza más tiempo para realizar cálculos. Es importante que un planificador a largo plazo seleccione una buena combinación de procesos vinculados a E/S y a CPU. Si todos los procesos están vinculados a E/S, la cola lista casi siempre estará vacía y el planificador 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 utilizarán y nuevamente el sistema estará desequilibrado. Por lo tanto, el sistema con el mejor rendimiento tendrá una combinación de procesos vinculados a la CPU y a las E/S. En los sistemas operativos modernos, esto se utiliza para garantizar 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 de gran escala, como sistemas de procesamiento por lotes , grupos de computadoras , supercomputadoras y granjas de procesamiento . 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 la espera mutua. En estos casos, normalmente se utiliza un software de programación de trabajos 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 solo permiten agregar nuevas tareas si están seguros de que aún se pueden cumplir 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 programador de mediano 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 de entrada o salida (también incorrectamente como salida o entrada de paginación ) . . El planificador de mediano plazo puede decidir cambiar un proceso que no ha estado activo durante algún tiempo, un proceso que tiene una prioridad baja, un proceso que presenta fallas de página con frecuencia o un proceso que está ocupando una gran cantidad de memoria en el proceso. para liberar memoria principal para otros procesos, intercambiando el proceso nuevamente más tarde cuando haya más memoria disponible, o cuando el proceso haya sido 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 programador de mediano plazo puede en realidad desempeñar el papel del programador de largo plazo, al tratar los archivos binarios como procesos intercambiados 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 pedido .
El programador a corto plazo (también conocido como programador de 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 planificador a corto plazo toma decisiones de programación con mucha más frecuencia que los planificadores a largo o mediano plazo: como mínimo, se deberá tomar una decisión de programación después de cada intervalo de tiempo, y estos son muy cortos. Este programador puede ser preventivo , lo que implica que es capaz de eliminar procesos de una CPU por la fuerza cuando decide asignar esa CPU a otro proceso, o no preventivo (también conocido como voluntario o cooperativo ), en cuyo caso el programador es incapaz de forzar 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.
Otro componente involucrado en la función de programación de la CPU es el despachador, que es el módulo que 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 involucran lo siguiente:
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 se deben evitar 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 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. Existen muchos algoritmos de programación diferentes. En esta sección presentamos varios de ellos.
En redes informáticas de conmutación de paquetes y otras multiplexaciones estadísticas , la noción de algoritmo de programación se utiliza como alternativa a la 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 justa proporcional y el rendimiento máximo . Si se ofrece una calidad de servicio diferenciada o garantizada , en lugar de una comunicación de mejor esfuerzo, se pueden utilizar colas justas ponderadas .
En redes inalámbricas de radio por paquetes avanzadas, como el sistema celular HSDPA (acceso a paquetes de enlace descendente de alta velocidad) 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 mediante la asignación dinámica de canales paquete por paquete dependiente del canal , o mediante la asignación de multiportadoras OFDMA u otros componentes de ecualización en el 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 salir (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 para uncola de tareas , por ejemplo como se ilustra en esta sección.
La fecha límite más temprana primero (EDF) o el menor tiempo restante es un algoritmo de programación dinámica que se utiliza en sistemas operativos en tiempo real para colocar procesos en una cola de prioridad. Cada vez que ocurre 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 programarse para su ejecución.
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 completar un proceso.
El sistema operativo asigna un rango de prioridad fija a cada proceso y el programador organiza los procesos en la cola de listos en orden de prioridad. Los procesos de menor prioridad son interrumpidos por procesos entrantes de mayor prioridad.
El programador asigna una unidad de tiempo fija por proceso y los recorre en ciclos. Si el proceso se completa dentro de ese intervalo de tiempo, se finaliza; de lo contrario, se reprograma después de darle una oportunidad a todos los demás procesos.
Esto 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 .
Un programador que conserva el trabajo es un programador que siempre intenta mantener ocupados los recursos programados, si hay trabajos enviados listos para programarse. 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 programarse.
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 manera que se minimice el tiempo total de producción :
Un método muy común en sistemas integrados es programar trabajos manualmente. Esto puede realizarse, por ejemplo, de forma multiplexada en el tiempo. A veces, el núcleo 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.
Al diseñar un sistema operativo, un programador debe considerar qué algoritmo de programación funcionará mejor para el uso que se le dará al sistema. No existe un mejor algoritmo de programación universal y muchos sistemas operativos utilizan algoritmos de programación extendidos o combinaciones de los anteriores.
Por ejemplo, Windows NT /XP/Vista utiliza una cola de retroalimentación multinivel , una combinación de algoritmos de programación preventiva 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 sido atendidos o si han estado esperando mucho. Cada nivel de prioridad está representado por su propia cola, con programación por turnos 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 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 subprocesos más largos de alta prioridad.
El algoritmo utilizado puede ser tan simple como una operación por turnos en la 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. Entonces, el proceso A se ejecuta durante 1 ms, luego el proceso B, luego el proceso C y luego regresa 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. El kernel siempre utiliza todos los recursos que necesita para garantizar el funcionamiento adecuado del sistema, por lo que se puede decir que tiene 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 la destrucción de caché .
IBM OS/360 estaba disponible con tres programadores diferentes. Las diferencias eran tales que a menudo se consideraban las variantes como 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 de acuerdo con un esquema elaborado definido por la instalación.
Los primeros sistemas MS-DOS y Microsoft Windows no eran multitarea y, como tales, no incluían un programador. Windows 3.1x utilizó un programador no preventivo, lo que significa que no interrumpía los programas. Dependía del programa para finalizar o decirle al sistema operativo que no necesitaba el procesador para poder pasar a otro proceso. Esto suele denominarse multitarea cooperativa. Windows 95 introdujo un programador preventivo rudimentario; sin embargo, para el soporte heredado se optó por permitir que las aplicaciones de 16 bits se ejecutaran sin preferencia. [10]
Los sistemas operativos basados en Windows NT utilizan una cola de comentarios de varios niveles. Se definen 32 niveles de prioridad, del 0 al 31, donde las prioridades del 0 al 15 son prioridades normales y las prioridades del 16 al 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 del proceso, que luego el sistema combina en el nivel de prioridad absoluta.
El kernel puede cambiar el nivel de prioridad de un subproceso dependiendo de su uso de E/S y CPU y si es interactivo (es decir, acepta y responde a entradas de humanos), aumentando la prioridad de los procesos interactivos y limitados de E/S y disminuyendo 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 del contador de ciclos de los procesadores modernos para realizar un seguimiento de exactamente cuántos ciclos de CPU ha ejecutado un subproceso, en lugar de simplemente usar una rutina de interrupción de temporizador de intervalos. [12] Vista también utiliza un programador de prioridades 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 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 tareas de multiprocesamiento utilizando un algoritmo de programación preventiva. Todos los procesos de Process Manager se ejecutan dentro de una tarea multiprocesamiento especial, llamada tarea azul . Esos 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 hilo cede el control del procesador a otro hilo llamando YieldToAnyThreada o YieldToThread. [14]
macOS utiliza una cola de retroalimentación multinivel, con cuatro bandas de prioridad para los subprocesos: normal, alta prioridad del sistema, solo modo kernel y en tiempo real. [15] Los hilos se programan de forma preventiva; macOS también admite subprocesos programados de forma cooperativa en su implementación de Thread Manager 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 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 la política de round robin justo se denomina SCHED_OTHER. [dieciséis]
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 programador O(n) con una cola de retroalimentación multinivel con niveles de prioridad que van de 0 a 140; Del 0 al 99 están reservados para tareas en tiempo real y del 100 al 140 se consideran buenos niveles de tarea. Para tareas en tiempo real, el cuanto de tiempo para los procesos de conmutación fue de aproximadamente 200 ms, y para tareas agradables de aproximadamente 10 ms. [ cita necesaria ] El programador ejecutó la cola de ejecución de todos los procesos listos, dejando que los procesos de mayor prioridad fueran primero y se ejecutaran durante sus intervalos de tiempo, después de lo cual se colocarán en una cola caducada. 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) para el kernel Linux 2.4 utilizado por la distribución. .
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 núcleos en el tiempo, Con Kolivas desarrolló conjuntos de parches que mejoraron la interactividad con este programador o incluso lo reemplazaron con sus propios programadores.
El trabajo de Con Kolivas, más significativamente su implementación de programación justa llamada Fecha Límite de Escalera Rotativa (RSDL), inspiró a Ingo Molnár a desarrollar el Programador Completamente Justo (CFS) como reemplazo del programador O(1) anterior , dando crédito a Kolivas en su anuncio. [18] CFS es la primera implementación de un programador 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 . Las colas justas se habían aplicado anteriormente a la programación de la CPU con el nombre de programación con zancadas . El programador CFS de cola justa 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 reinsertar 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 primera programación de fecha límite virtual (EEVDF) elegible más temprano . [20] [21] El objetivo era eliminar la necesidad de parches agradables de latencia de CFS . [22]
FreeBSD utiliza una cola de comentarios de varios niveles con prioridades que van del 0 al 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, al igual que Linux, utiliza la configuración de cola activa, pero también tiene una cola inactiva. [23]
NetBSD utiliza una cola de comentarios multinivel con prioridades que van del 0 al 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 utiliza una cola de retroalimentación multinivel con prioridades que oscilan entre 0 y 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 se realiza utilizando su cuanto de tiempo, se le asigna una nueva prioridad y se lo devuelve a la cola. Solaris 9 introdujo dos nuevas clases de programación: la clase de prioridad fija y la clase de participación justa. 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 recursos compartidos 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 en conjunto se conocen como 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.
Para 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 en que realmente se ejecuta por t r , entonces el tiempo de respuesta es r = t w + t r .
En un sistema interactivo, el tiempo de respuesta puede no ser el mejor criterio. A menudo, un proceso puede producir algún resultado bastante temprano y puede continuar calculando nuevos resultados mientras los resultados anteriores se envían al usuario. Así, otra medida es el tiempo transcurrido desde que se presenta una solicitud hasta que se produce la primera respuesta. Esta medida, llamada tiempo de respuesta, es el tiempo que lleva comenzar a responder, no el tiempo que lleva generar la respuesta.
{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )