Algoritmos de Planificación de CPU en Sistemas de Tiempo Compartido: Optimización del Rendimiento Interactivo

Procesamiento en Sistemas de Tiempo Compartido

Los sistemas de tiempo compartido, también conocidos como sistemas interactivos, permiten que múltiples usuarios o procesos compartan los recursos de la CPU de manera concurrente. Muchas de sus soluciones de planificación pueden aplicarse también en el procesamiento por lotes (batch). Sin embargo, en estos sistemas, el procesamiento en tres niveles (3 LVL) no es típicamente posible.

Round Robin (RR)

Es el algoritmo de planificación más antiguo, sencillo, equitativo y ampliamente utilizado en sistemas de tiempo compartido. A cada proceso se le asigna un quantum (o rebanada de tiempo), durante el cual se le permite ejecutarse. La magnitud del quantum es crucial para el rendimiento del sistema.

Realizar cambios de proceso (cambios de contexto) requiere tiempo para tareas administrativas, lo que se conoce como costo administrativo adicional. Este costo incluye:

• Tiempo que demora la conmutación de mapas de memoria.
• Vaciado de la caché de disco.
• Carga de la caché de CPU.

Planificación por Prioridades

Este algoritmo elimina la suposición implícita del Round Robin de que todos los procesos tienen la misma importancia. En su lugar, se asigna una prioridad a cada proceso. El proceso listo con la prioridad más alta es el que se ejecuta.

Un riesgo potencial es que un proceso de alta prioridad podría no dejar de ejecutarse, causando inanición a otros procesos. Para evitar esto, se le puede reducir la prioridad a un proceso después de ejecutarse (envejecimiento o aging).

La prioridad se asigna de forma dinámica o estática. Por ejemplo, Unix permite modificar la prioridad de forma interactiva con el comando nice. Las prioridades suelen agruparse por clase, y dentro de cada clase se puede aplicar un algoritmo como Round Robin.

Planificación Multinivel

Es una modificación de la planificación por prioridades. Este enfoque favorece a los procesos interactivos y desfavorece a los procesos en segundo plano (background). Una característica común es que, cuantos menos bloqueos por I/O posea un proceso (es decir, más intensivo en CPU), menor será su prioridad.

Shortest Job First (SJF)

Aunque obtiene resultados óptimos en sistemas por lotes, SJF también puede aplicarse en sistemas de tiempo compartido. Los procesos interactivos, por lo general, esperan un comando (bloqueo de I/O), lo ejecutan y luego esperan. Para reducir el tiempo de respuesta, se puede tratar cada comando como un trabajo individual, ejecutando primero el más corto.

Planificación por Lotería

En este algoritmo, a cada proceso se le asignan varios boletos de lotería. Cada uno de esos boletos representa una oportunidad de acceso a distintos recursos del sistema, como tiempo de CPU o acceso a I/O. Cada vez que se toma una decisión de planificación, se escoge un boleto al azar.

Cada proceso tiene una probabilidad de "ganar la lotería" proporcional a la cantidad de boletos que posea. Una característica interesante es que los procesos pueden intercambiar boletos entre sí. Este enfoque puede resolver problemas de planificación difíciles de manejar con otros algoritmos.