🎯 Conceptos Fundamentales
- Multiprogramación: El objetivo central de la planificación. Busca maximizar la utilización de la CPU y la productividad del sistema, asegurando que siempre haya un proceso en estado de ejecución para que la CPU no permanezca inactiva (ej. mientras otro proceso espera por E/S).
- Planificación de CPU: Es la tarea de determinar, entre todos los procesos que están en estado Listo (o en la cola de listos), cuál es el proceso que el *dispatcher* debe seleccionar para que pase a ejecución en la CPU. Se realiza por el módulo llamado Planificador.
- Ráfaga de CPU: Período de tiempo durante el cual un proceso utiliza la CPU de forma ininterrumpida. La ejecución de un proceso es un ciclo continuo de ráfagas de CPU y ráfagas de E/S. Los programas se clasifican a menudo como limitados por CPU o limitados por E/S.
- Ráfaga de E/S: Período de tiempo en el que un proceso espera a que finalice una operación de Entrada/Salida (ej. lectura de disco, recepción de red). Durante este tiempo, la CPU puede ser utilizada por otro proceso.
- Despachador (*Dispatcher*): El módulo que se encarga de dar el control de la CPU al proceso seleccionado por el planificador. La función del *dispatcher* incluye cambiar de contexto, cambiar al modo de usuario y saltar a la dirección de memoria adecuada para reanudar el programa. El tiempo que lleva realizar esta tarea se denomina latencia del *dispatcher*.
📊 Criterios de Optimización y Evaluación
Los algoritmos de planificación se evalúan basándose en varios criterios, los cuales generalmente buscan maximizar la eficiencia y minimizar los tiempos de espera y respuesta:
- Criterios de Planificación: Son las métricas que definen el éxito de un algoritmo de planificación. En general, se busca maximizar los criterios relacionados con la eficiencia (Utilización, Rendimiento) y minimizar los relacionados con el tiempo (Retorno, Espera, Respuesta).
- % del Tiempo de Utilización de CPU (*CPU Utilization*): $$ U = \frac{\text{Tiempo que la CPU está ocupada}}{\text{Tiempo total}} $$ Se define como la fracción de tiempo que el procesador está realizando trabajo útil (ejecutando procesos de usuario o del sistema) y no está inactivo. Objetivo: Maximizar.
- Rendimiento (*Throughput*): $$ \text{Rendimiento} = \frac{\text{Número de procesos completados}}{\text{Unidad de tiempo}} $$ Mide el número de procesos que completan su ejecución por unidad de tiempo. Es una medida de la productividad general del sistema. Objetivo: Maximizar.
- Tiempo de Retorno (*Turnaround Time* - $T_r$): $$ T_r = \text{Tiempo de finalización} - \text{Tiempo de llegada} $$ Es el intervalo total de tiempo transcurrido desde que un proceso entra al sistema (llega a la cola de listos) hasta que completa su ejecución (tiempo de finalización). Incluye el tiempo de ejecución, el tiempo de espera en cola y el tiempo de E/S. Objetivo: Minimizar.
- Tiempo de Espera (*Waiting Time* - $T_e$): $$ T_e = \text{Tiempo total que el proceso pasa en la cola de listos} $$ Es el tiempo total que un proceso pasa esperando en la cola de procesos listos por el planificador. No incluye el tiempo dedicado a E/S. Objetivo: Minimizar.
- Tiempo de Respuesta (*Response Time* - $T_{res}$): $$ T_{res} = \text{Tiempo de la primera respuesta} - \text{Tiempo de llegada} $$ Especialmente relevante en sistemas interactivos o de tiempo compartido. Mide el tiempo que transcurre desde que se envía una solicitud hasta que se produce la primera respuesta. Este tiempo es crítico para la percepción de interactividad del usuario. Objetivo: Minimizar.
⏳ Algoritmos de Planificación
| Algoritmo | Descripción Detallada | Propiedad Clave | Uso Común / Nota |
|---|---|---|---|
| FIFO (*First-Come, First-Served*) | El proceso que solicita la CPU primero es el primero en obtenerla. Los procesos se ejecutan hasta que terminan o se bloquean por E/S. Es no apropiativo. | Simple de implementar. Puede sufrir del Efecto de Caravana (*Convoy Effect*) donde un proceso muy largo bloquea a muchos procesos cortos que están detrás de él. | Principalmente en sistemas de procesamiento por lotes antiguos. |
| SJF (*Shortest Job First*) | Asigna la CPU al proceso con la ráfaga de CPU más corta a continuación. Puede ser no apropiativo (se completa la ráfaga actual) o apropiativo (*Shortest-Remaining-Time-First*). | Teóricamente Óptimo en cuanto a la minimización del tiempo medio de espera y del tiempo medio de retorno. El desafío es que es imposible conocer la duración exacta de la próxima ráfaga de CPU. | Se utiliza a menudo mediante predicción exponencial del tiempo de la próxima ráfaga. |
| Prioridad | Cada proceso tiene asignada una prioridad, y el planificador ejecuta el proceso con la prioridad más alta. La prioridad puede ser interna (basada en el uso de recursos) o externa (basada en políticas). | Puede ser Apropiativo o No Apropiativo. El principal problema es la Inanición (*Starvation*), donde un proceso de baja prioridad nunca llega a ejecutarse. Esto se mitiga con el Envejecimiento (*Aging*). | Común en sistemas en tiempo real y sistemas por lotes con diferentes niveles de servicio. |
| RR (*Round Robin*) | Similar a FIFO, pero con apropiación. Cada proceso recibe un pequeño intervalo de tiempo de CPU fijo llamado ***quántum***. Si el proceso no termina dentro del *quántum*, es apropiado y se coloca al final de la cola de listos. | Apropiativo. Es el algoritmo más utilizado en sistemas de tiempo compartido e interactivos debido a su equidad. El rendimiento depende drásticamente del tamaño del *quántum*. | Tiempo compartido, sistemas interactivos (Windows, Linux). |
| Multinivel de Colas | Clasifica los procesos en diferentes colas de listos (ej. una cola para procesos interactivos, otra para procesos por lotes), y a cada cola se le asigna un algoritmo de planificación distinto (ej. RR para la interactiva y FIFO para la de lotes). | Muy flexible, pero el diseño y la implementación son complejos. Se utiliza una planificación entre colas (ej. prioridad estricta entre colas o reparto de tiempo). | La base de los planificadores más sofisticados en sistemas operativos modernos. |