Calendarización

1. Introducción
1.1 La necesidad de calendarizar
Comúnmente, en una computadora que aplica la multiprogramación existen procesos que se disputan el uso de la CPU. Por lo cual, es necesario arbitrar el acceso de los mismos, por medio de políticas y algoritmos.  La parte del sistema operativo que se encarga de esto se denomina calendarizador, y el algoritmo que éste utiliza, algoritmo decalendarización.

1.2 Evolución de la calendarización
En un principio, con la programación por lotes, las cosas eran sencillas: se ejecutaba el siguiente trabajo de la cinta luego de terminar el trabajo actual. Siguiendo así, hasta terminar el lote. Por lo cual, la calendarización consistía únicamente en despachar los procesos en cinta uno tras otro. Luego, con la aparición de los sistemas de tiempocompartido, se presentaba otra complejidad de calendarización, dado que por lo general había varios usuarios esperando para ser atendidos, es decir, compitiendo por el uso de tiempo sobre la CPU.  Esto, impulsó la necesidad de generar algoritmos ingeniosos y eficientes para intentar cumplir en tiempo y forma con todos esos usuarios expectantes.

Posteriormente, con la llegada de las computadoraspersonales básicas, el problema de la calendarización volvía a ser cosa secundaria, dado que era muy poco probable que un usuario estuviese ejecutando más de un proceso a la vez. Y además, los tiempos de reloj de las CPU eran cada vez más cortos (por tanto, se obtenían ejecuciones más rápidas). Pero en la actualidad, con computadoras superiores como las estaciones de trabajo o los servidores, lasituación es bastante distinta. En este tipo de equipos, es muy común que existan varios procesos compitiendo por el uso de la CPU. Por ejemplo, se presentan situaciones en que se debe elegir entre ejecutar un refresco de pantalla luego de cerrar una ventana o ejecutar el proceso de actualización de vacunas del antivirus. En dicho caso, se debe considerar qué es más importante. Lógicamente, es másurgente actualizar la pantalla, para que el usuario no piense que la maquina se cuelga o funciona mal. Esta decisión es una de muchas que debe tomar el calendarizador del sistema para lograr un mejor rendimiento general.  Además, el calendarizador debe preocuparse de ejecutar los procesos de manera tal que el costo de overhead sea el menor posible.

1.3 ¿Cómo se comportan los procesos?
Acontinuación se muestra un diagrama que muestra los distintos comportamientos que puede tomar un proceso a lo largo de su vida, seguido de una explicación complementaria.

Nuevo Termina

Listo

Ejecución

Bloqueo

1.1.1 Diagrama básico de estados de un proceso

Explicación:
Cuando un proceso Nuevo es creado, inmediatamente pasa a la lista de procesos en estado de Listo, que son procesosque están preparados para hacer uso de la CPU. Cuando es su turno, un proceso Listo entra en Ejecución sobre la CPU. En caso de que se agote su tiempo y no haya terminado (no siempre se maneja dicha opción), vuelve al estado de Listo y espera a que le toque nuevamente. Cuando un proceso en Ejecución genera una interrupción de entrada/salida, entra en el estado de Bloqueo esperando a que seresuelva dicho evento. Luego, pasa al estado de Listo, para esperar nuevamente su turno y acceder al uso del CPU. Cuando un proceso en Ejecución termina de ejecutar todo su código, se Termina y es desechado.

1.4 Cardinalidad de los estados
La Cardinalidad, en este caso, se refiere a la cantidad de procesos que pueden estar en un mismo estado al mismo tiempo. Veamos la siguiente tabla con los tresestados útiles:
Estado Listo Ejecución Bloqueo Cardinalidad Tantos como permita albergar la memoria del sistema. Tantos como CPUs se dispongan, uno por CPU. Tantos como permita albergar la memoria del sistema.

1.1.2 Tabla de Cardinalidad de los estados listo, ejecución y bloqueo

2. El calendarizador
2.1 ¿Cuándo puede actuar el calendarizador?
La primera situación es cuando se crea un...