Algoritmos de Planificación de CPU: Rendimiento y Políticas Operativas

Algoritmos de Planificación de Procesos en la CPU

FCFS (First-Come, First-Served)

El proceso que entra primero es el primero que se ejecuta (tipo FIFO).

• Política: No-apropiativa (Non-preemptive).
• Desventaja: Es ineficiente. En procesos cortos, pierde mucho tiempo debido a la espera de procesos largos (efecto convoy).

Round-Robin (RR)

Concede a cada uno de los procesos un tiempo de ejecución fijo denominado quantum (q), que es una unidad de tiempo asignada para realizar un trabajo.

• Política: Apropiativa (Preemptive).
• Índice de Servicio: Uniforme para todos los procesos.
• Ventajas: Baja sobrecarga general.
• Desventajas: Es poco eficiente cuando tiene que acceder constantemente a la memoria secundaria, lo que puede llevar a la sobrecarga del sistema. Requiere que los procesos estén en la memoria principal para un rendimiento óptimo.

SJN (Shortest Job Next)

El siguiente proceso en ejecutarse es el que necesita el menor tiempo de ejecución para completar su trabajo.

Determinación del Tiempo de Ejecución

Para aplicar SJN, es necesario conocer o estimar el tiempo de ejecución. Esto se puede obtener mediante:

• Tarjetas de control.
• Información proporcionada por el programa en ciertos lenguajes de programación.
• Historiales de ejecuciones previas.

• Política: No-apropiativa.
• Ventaja: Es una política buena para favorecer a los procesos cortos.

SRT (Shortest Remaining Time)

Es la versión apropiativa de SJN. El siguiente proceso en ejecutarse es aquel al que le quede el tiempo de ejecución más corto.

Cuando llega un proceso nuevo que requiere menos tiempo restante que el proceso que se está ejecutando, este último es desalojado de la CPU y se comienza a ejecutar el nuevo proceso.

• Política: Apropiativa.
• Eficiencia: Muy eficiente, resultando en un excelente tiempo medio de servicio.
• Riesgo: Posibilidad de asignar prioridades. Algunos procesos pueden sufrir una postergación indefinida (starvation), llegando a convertirse en procesos zombies.

HRN (Highest Response Ratio Next)

El próximo proceso a ejecutarse es aquel que posee el índice de respuesta más alto.

Fórmula de Prioridad

Prioridad = (Tiempo de Espera (W) + Tiempo de Servicio (T)) / Tiempo de Servicio (T)

• Política: No-apropiativa.
• Manejo de Interrupciones: Si un programa ejecuta una interrupción, pierde el turno, a menos que su prioridad calculada sea suficientemente alta para continuar.
• Desventaja: Sobrecarga el sistema debido a los cálculos constantes necesarios para determinar el índice de respuesta.
• Objetivo: Mitiga la larga espera de procesos largos.

Colas Múltiples con Retroalimentación (FB)

Este algoritmo utiliza múltiples colas de prioridad. El objetivo principal es favorecer a los procesos más cortos.

Mecanismo de Funcionamiento

1. Todas las colas tienen acceso al procesador, ejecutando procesos según la política asignada a cada cola.
2. Se asigna un tiempo (quantum) a las colas.
3. Retroalimentación (Feedback): Cuando un proceso incumple la regla (ej. consume todo su quantum sin terminar), pasa a una cola de nivel inferior (menor prioridad).
4. Cuando el proceso que está usando el procesador acaba su quantum, se selecciona un nuevo proceso de la cola de nivel más alto que contenga procesos listos.

Características Clave

• Asignación en Cascada: Los procesos que consumen mucho tiempo tienden a moverse hacia abajo en la jerarquía de colas.
• Política: Apropiativa.
• Ventajas: Soporta muy bien la sobrecarga y es altamente adaptable a las necesidades dinámicas del sistema.