Algoritmos de planificación

Los algoritmos de planificación son las estrategias y reglas matemáticas que implementa el planificador (scheduler) del sistema operativo para decidir el orden en el que los procesos listos accederán a los ciclos de reloj de la CPU.

Para un profesional técnico, dominar estos algoritmos es fundamental para entender cómo se optimiza el rendimiento del sistema, cómo se minimizan los tiempos de espera y cómo se gestionan las prioridades en entornos multitarea complejos.

Algoritmos Principales de Planificación de CPU

Los algoritmos organizan las colas de procesos aplicando diferentes criterios de optimización temporal y de recursos:

    FIFO (First In, First Out - Primero en entrar, primero en salir): El algoritmo más sencillo. Los procesos se atienden estrictamente en el orden de llegada a la cola de listos. Es un sistema no expropiativo (non-preemptive): una vez que un proceso toma la CPU, la mantiene hasta que finaliza o se bloquea, lo que puede provocar el llamado efecto convoy (donde procesos cortos quedan atrapados detrás de un proceso muy largo).
    Round Robin (Rueda de la Fortuna): Diseñado específicamente para sistemas operativos de tiempo compartido y multitarea. A cada proceso se le asigna un intervalo de tiempo equitativo y reducido llamado quantum (ej. 10 a 100 milisegundos). Si el proceso no termina en ese tiempo, es interrumpido y colocado al final de la cola. Es un algoritmo expropiativo (preemptive) que garantiza una excelente interactividad.
    Prioridades: A cada proceso se le asigna un valor numérico de prioridad. La CPU se le entrega siempre al proceso con mayor prioridad (puede ser expropiativo o no). Su principal riesgo técnico es la inanición (starvation), un fenómeno donde los procesos con baja prioridad nunca llegan a ejecutarse si constantemente llegan tareas más importantes.
    SJF (Shortest Job First - El trabajo más corto primero): Asigna la CPU al proceso que requiera el tiempo de ejecución más breve. Puede ser no expropiativo o expropiativo (conocido como SRTF - Shortest Remaining Time First). Minimiza de forma teórica el tiempo medio de espera, pero presenta el problema práctico de que es imposible conocer con certeza absoluta la duración exacta de una tarea antes de ejecutarla.

Comparación entre Algoritmos de Planificación

La selección de un algoritmo depende de los objetivos operativos del sistema y del tipo de carga de trabajo:

    Rendimiento e Interactividad: Round Robin y algoritmos basados en prioridades garantizan una gran fluidez en sistemas interactivos de escritorio, mientras que FIFO y SJF buscan optimizar el tiempo de retorno (turnaround time) en procesamiento por lotes (batch).
    Expropiación (Preemption): FIFO y SJF clásico no expropian la CPU, lo que simplifica la gestión del núcleo pero reduce la capacidad de respuesta ante eventos urgentes. Round Robin y las prioridades expropiativas aseguran un control dinámico del procesador.
    Equidad: Round Robin es el modelo más equitativo al repartir el tiempo en partes iguales, a diferencia de los esquemas por prioridades puras, que requieren mecanismos correctivos como el envejecimiento (aging) para evitar la inanición de los procesos relegados.

Analogía: Imagina la ventanilla de atención al cliente en una oficina pública. El método FIFO equivale a la clásica cola de números estricta donde el primero que llega es el primero en ser atendido sin importar lo que tarde su gestión; el Round Robin es como un límite estricto de 3 minutos por ventanilla: si no has terminado tu trámite, debes volver a formarte al final de la cola para que todos tengan su turno rápido; el sistema de prioridades atiende primero a personas con necesidades urgentes o autoridades; y el SJF atiende primero a los ciudadanos que tienen una consulta exprés de diez segundos para vaciar la cola lo antes posible.

Actividad práctica

Objetivo:

Comparar el comportamiento teórico y la eficiencia de los diferentes algoritmos de planificación ante un conjunto de procesos.

Tareas:

  1. Calcula el tiempo medio de espera de tres procesos (A, B y C) con duraciones de 24, 3 y 3 milisegundos respectivamente, si se utiliza un algoritmo FIFO.
  2. Repite el cálculo anterior utilizando el algoritmo SJF (atendiendo primero al proceso más corto). Analiza la diferencia en el tiempo medio de espera.
  3. Investiga en qué consiste la técnica de envejecimiento (aging) y cómo evita el problema de la inanición (starvation) en los algoritmos basados en prioridades.
  4. Reflexiona sobre por qué el tamaño del quantum elegido en un algoritmo Round Robin influye drásticamente en el rendimiento del procesador y en la sobrecarga por cambios de contexto.

Preguntas de reflexión:

  1. ¿Por qué el algoritmo FIFO provoca el llamado "efecto convoy" y cómo afecta negativamente a los procesos interactivos que requieren una respuesta rápida?
  2. ¿Qué dilema técnico afronta un administrador de sistemas o diseñador de núcleos al elegir la duración óptima del quantum en un algoritmo Round Robin?
  3. ¿Por qué el algoritmo SJF (Shortest Job First) es teóricamente el más eficiente para minimizar el tiempo de espera, pero extremadamente difícil de implementar en un sistema operativo de propósito general?
  4. ¿Cómo manejan los sistemas operativos modernos las prioridades dinámicas para evitar que los procesos en segundo plano sufran de inanición permanente?
  5. ¿Qué diferencia crítica existe entre un algoritmo de planificación expropiativo (preemptive) y uno no expropiativo frente a la llegada repentina de un proceso de alta prioridad?
Haz clic aquí para ver las soluciones y explicaciones

1. ¿Cuál es el tiempo medio de espera con FIFO para procesos de 24, 3 y 3 ms?

Si llegan en orden A (24), B (3), C (3): el proceso A espera 0 ms; B espera 24 ms; C espera $24 + 3 = 27$ ms. El tiempo medio de espera es $(0 + 24 + 27) / 3 = 17$ milisegundos.

2. ¿Cómo cambia el tiempo medio de espera utilizando SJF?

Ordenando los procesos por duración ascendente: B (3), C (3) y A (24). B espera 0 ms; C espera 3 ms; A espera $3 + 3 = 6$ ms. El tiempo medio de espera se reduce drásticamente a $(0 + 3 + 6) / 3 = 3$ milisegundos, demostrando la eficiencia del SJF.

3. ¿En qué consiste la técnica de envejecimiento (aging)?

Es un mecanismo corrector que incrementa progresivamente la prioridad de los procesos que llevan demasiado tiempo esperando en la cola de listos. De este modo, un proceso con baja prioridad inicial ve cómo su prioridad aumenta con el tiempo hasta asegurar su ejecución, previniendo eficazmente la inanición.

4. ¿Por qué el tamaño del quantum en Round Robin influye en el rendimiento?

Si el quantum es excesivamente corto, el sistema realiza cambios de contexto masivos, saturando la CPU con tareas administrativas (sobrecarga). Si el quantum es demasiado largo, el algoritmo pierde su naturaleza interactiva y se comporta prácticamente como un FIFO, empeorando la respuesta para los usuarios.

5. ¿Qué diferencia hay entre un algoritmo expropiativo y uno no expropiativo?

En un algoritmo no expropiativo, una vez que un proceso recibe la CPU, la retiene obligatoriamente hasta que termina voluntariamente o se bloquea. En un algoritmo expropiativo, el núcleo tiene la facultad de interrumpir y desbancar a un proceso en ejecución antes de que termine si surge una tarea de mayor prioridad o si se agota su turno asignado.