Planificación de hilos

La planificación de hilos (thread scheduling) es el proceso mediante el cual el sistema operativo decide qué hilo se ejecutará en un momento dado. La planificación de hilos es una tarea crítica en la programación concurrente, ya que determina cómo se asignan los recursos del sistema a los diferentes hilos y cómo se garantiza un comportamiento justo y eficiente.

Aquí veremos diferentes algoritmos de planificación de hilos que se utilizan en los sistemas operativos modernos.

Thread Scheduling en Java

Si hay más de un hilo esperando a ejecutarse, el Thread Scheduler determinará cuál hilo debe ejecutarse. El algoritmo exacto seguido por el Thread Scheduler puede variar según el sistema operativo y la implementación de Java. Por lo cual, en multithreading, no podemos garantizar la salida exacta, cada vez que ejecutamos el cóðigo, obtendremos diferentes salidas.

Preemptive Scheduling vs Non-Preemptive Scheduling

En la planificación de hilos, existen dos enfoques principales: Preemptive Scheduling y Non-Preemptive Scheduling. Estos enfoques difieren en cómo se asignan los recursos del sistema a los diferentes hilos.

Preemptive Scheduling

La Preemptive Scheduling es una técnica donde las asignaciones se otorgan con sus preferencias o prioridades. En el caso de la Preemptive Scheduling, es crucial ejecutar una tarea de mayor preferencia, incluso si la tarea con menor prioridad aún se está ejecutando. Cuando se trata de ejecutar el trabajo de mayor prioridad, la tarea con menor prioridad espera un tiempo y continúa su proceso de ejecución cuando se completa el trabajo de primera prioridad.

Non-Preemptive Scheduling

La Non-Preemptive Scheduling es una técnica donde las asignaciones se otorgan sin sus preferencias o prioridades. En el caso de la Non-Preemptive Scheduling, es crucial ejecutar una tarea de menor prioridad, incluso si la tarea con mayor prioridad aún se está ejecutando. Cuando se trata de ejecutar el trabajo de menor prioridad, la tarea con mayor prioridad espera un tiempo y continúa su proceso de ejecución cuando se completa el trabajo de menor prioridad.

Conceptos Clave en la Planificación de Hilos

Al trabajar con estos algoritmos, es importante comprender algunos conceptos clave:

• Burst Time: El tiempo que un hilo necesita para completar su ejecución.
• Arrival Time: El tiempo en el que un hilo llega al sistema.
• Priority: La prioridad asignada a un hilo, que determina su orden de ejecución.
• Quantum: El intervalo de tiempo asignado a un hilo en un algoritmo de planificación de hilos.

Por otro lado también es importante tener en cuenta los siguientes conceptos:

Tiempo de Finalización (o completion time)

El tiempo en el que un hilo termina su ejecución y sale del sistema.

Tiempo de Retorno (o turnaround time)

El tiempo total que un hilo pasa en el sistema, desde su llegada hasta su finalización.

Se puede calcular usando dos fórmulas diferentes:

1. Tiempo de Retorno = Tiempo de Finalización - Tiempo de Llegada
2. Tiempo de Retorno = Tiempo de Espera + Tiempo de Ejecución

En general usaremos la segunda fórmula.

Tiempo de Espera (o waiting time)

El tiempo de espera de un hilo es el tiempo que transcurre entre su llegada a la cola de espera y el momento en que se ejecuta por completo. Por tanto, el tiempo de espera nos queda como:

Tiempo de Espera = Tiempo de Retorno - Tiempo de Ejecución

Algoritmos de Planificación de Hilos

Round-Robin (RR)

En este algoritmo, cada hilo recibe un intervalo de tiempo fijo (un cuanto) para ejecutarse. Cuando este tiempo expira, el scheduler interrumpe el hilo y lo mueve al final de la cola de ejecución. Así, el siguiente hilo tiene la oportunidad de ejecutarse durante su intervalo de tiempo.

Ejecución de ejemplo de Round-Robin

En la siguiente visualización mostramos un ejercicio de ejemplo.

Scheduling basado en Prioridades

Se asigna niveles de prioridad a cada hilo, y el scheduler selecciona el hilo con mayor prioridad para ejecutarse. Este enfoque puede llevar a una inversión de prioridad, en donde los hilos de baja prioridad bloquean los hilos de alta prioridad, impactando el rendimiento. Para mitigar este problema, se usan técnicas como herencias de prioridad y protocolos de techo de prioridad.

Consideremos el siguiente ejemplo:

Proceso	Prioridad	Burst Time (ejecución)	Arrival Time (llegada)
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

0. En el tiempo=0, llegan los procesos P1 y P2. Como P1 tiene una prioridad más alta, se ejecuta primero con un burst time de 4.

   Timer=0: P1 P2 (ambos llegan en tiempo cero)

1. En tiempo=1, no llegan nuevos procesos. Continúa ejecutándose P1.

   Timer=1:
   Esperando en cola: P2
   Ejecución: P1

2. En tiempo=2, no llegan nuevos procesos. Continúa ejecutándose P1. P2 sigue esperando en cola.

   Timer=2:
   Esperando en cola: P2
   Ejecución: P1 P1

3. En tiempo=3, no llegan nuevos procesos. Continúa ejecutándose P1. P2 sigue esperando en cola.

   Timer=3:
   Esperando en cola: P2
   Ejecución: P1 P1 P1

4. En tiempo=4, P1 termina su ejecución. P2 inicia su ejecución.

   Timer=4:
   Esperando en cola: P2
   Ejecución: P1 P1 P1 P1 (terminado)

5. En tiempo=5, no llegan nuevos procesos. Continúa ejecutándose P2.

   Timer=5:
   Esperando en cola: P2
   Ejecución: P1 x4 P2

6. En tiempo=6, llega el proceso P3. P3 tiene mayor prioridad (1) comparado con P2 (2). P2 pasa a espera, y P3 comienza su ejecución.

   Proceso	Prioridad	Burst Time (ejecución)	Arrival Time (llegada)
   P1	1	4	0
   P2	2	1 de 3 pendiente	0
   P3	1	7	6
   P4	3	4	11
   P5	2	2	12

   Timer=6:
   Esperando en cola: P3
   Ejecución: P1 x4 P2 P2

7. En tiempo=7, no llegan nuevos procesos. Continuamos con P3, P2 sigue esperando en cola.

   Timer=7:
   Esperando en cola: P2
   Ejecución: P1 x4 P2 P2 P3

8. En tiempo=8, no llegan nuevos procesos. Continuamos con P3.

   Timer=8:
   Esperando en cola: P2
   Ejecución: P1 x4 P2 P2 P3 P3

9. En tiempo=9, no llegan nuevos procesos. Continuamos con P3.

   Timer=9:
   Esperando en cola: P2
   Ejecución: P1 x4 P2 P2 P3 P3 P3

10. En tiempo=10, no llegan nuevos procesos. Continuamos con P3.

    Timer=10:
    Esperando en cola: P2
    Ejecución: P1 x4 P2 P2 P3 P3 P3 P3

11. En tiempo=11, llega el proceso P4. P3 tiene mayor prioridad, así que continúa su ejecución.

    Proceso	Prioridad	Burst Time (ejecución)	Arrival Time (llegada)
    P1	1	4	0
    P2	2	1 de 3 pendiente	0
    P3	1	2 de 7 pendiente	6
    P4	3	4	11
    P5	2	2	12

    Timer=11:
    Esperando en cola: P2 P4
    Ejecución: P1 x4 P2 P2 P3 P3 P3 P3 P3

12. En tiempo=12, llega el proceso P5. P3 tiene mayor prioridad, así que continúa su ejecución.

    Timer=12:
    Esperando en cola: P2 P4 P5
    Ejecución: P1 x4 P2 P2 P3 P3 P3 P3 P3 P3

13. En tiempo=13, P3 completa su ejecución. Tenemos P2, P4 y P5 en cola. P2 tiene igual prioridad que P5. Como P2 llegó primero que P5, comienza su ejecución.

    Proceso	Prioridad	Burst Time (ejecución)	Arrival Time (llegada)
    P1	1	4	0
    P2	2	1 de 3 pendiente	0
    P3	1	7	6
    P4	3	4	11
    P5	2	2	12

    Timer=13:
    Esperando en cola: P2 P4 P5
    Ejecución: P1 x4 P2 P2 P3 x7

14. En tiempo=14, el proceso P2 termina su ejecución. P4 y P5 están en espera. P5 tiene mayor prioridad así que empieza su ejecución.

    Timer=14:
    Esperando en cola: P4 P5
    Ejecución: P1 x4 P2 P2 P3 x7 P2

15. En tiempo=15, no llegan nuevos procesos. Continuamos con P5.

    Timer=15:
    Esperando en cola: P4
    Ejecución: P1 x4 P2 P2 P3 x7 P2 P5

16. En tiempo=16, P5 finaliza su ejecución. Solo queda P4, que comienza su ejecución.

    Timer=16:
    Esperando en cola: P4
    Ejecución: P1 x4 P2 P2 P3 x7 P2 P5 P5

17. En tiempo=20, P5 finaliza su ejecución. No hay más procesos en cola.

    Timer=20:
    Esperando en cola: -
    Ejecución: P1 x4 P2 P2 P3 x7 P2 P5 P5 P4 x4

Visualización Animada

A continuación se brinda una animación del mismo ejercicio.

Shortest Job Next (SJN)

También se conoce como Shortest Job First (SJF). En este algoritmo, el scheduler selecciona el hilo con el menor tiempo de ejecución restante para ejecutarse a continuación. Esto puede minimizar el tiempo de espera y mejorar la eficiencia del sistema.

Consideremos el siguiente ejemplo para trabajar este algoritmo:

Proceso	Burst Time	Arrival Time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

0. En tiempo=0, llega P4 y comienza su ejecución.

   Timer=0:
   En espera: P4
   Ejecución: -

1. En tiempo=1, llega P3. Pero P4 necesita 2 unidades de tiempo más para completar su ejecución. Así que continuará su ejecución.

   Timer=1:
   En espera: P3
   Ejecución: P4

2. En tiempo=2, llega P1 y se agrega a la cola. P4 continuará su ejecución.

   Timer=2:
   En espera: P3 P1
   Ejecución: P4 P4

3. En tiempo=3, P4 termina su ejecución. Se compara el burst time de P3 y P1. Se ejecuta P1 ya que tiene un burst time menor.

   Timer=3:
   En espera: P3 P1
   Ejecución: P4 P4 P4

4. En tiempo=4, llega P5 y se agrega a la cola. P1 continúa su ejecución.

   Timer=4:
   En espera: P3 P5
   Ejecución: P4 P4 P4 P1

5. En tiempo=5, llega P2 y se agrega a la cola. P1 continúa su ejecución.

   Timer=5:
   En espera: P3 P5 P2
   Ejecución: P4 P4 P4 P1 P1

6. En tiempo=9, P1 termina su ejecución. Se compara el burst time de P3, P5 y P2. Se ejecuta P2 ya que tiene un burst time menor.

   Timer=9:
   En espera: P3 P5 P2
   Ejecución: P4 P4 P4 P1 x6

7. En tiempo=10, P2 está en ejecución. Mientras que P3 y P5 están en espera.

   Timer=10:
   En espera: P3 P5
   Ejecución: P4 P4 P4 P1 x6 P2

8. En tiempo=11, P2 termina su ejecución. Se compara el burst time de P3 y P5. Se ejecuta P5 ya que tiene un burst time menor.

   Timer=11:
   En espera: P3 P5
   Ejecución: P4 P4 P4 P1 x6 P2 P2

9. En tiempo=15, P5 termina su ejecución. Solo queda P3 en la cola.

   Timer=15:
   En espera: P3
   Ejecución: P4 P4 P4 P1 x6 P2 P2 P5 x4

10. En tiempo=23, P3 termina su ejecución. No hay más procesos en cola.

    Timer=23:
    En espera: -
    Ejecución: P4 P4 P4 P1 x6 P2 P2 P5 x4 P3 x8

First-Come First-Served (FCFS)

En este algoritmo, los hilos se ejecutan en el orden en que llegan al sistema. El hilo que llega primero se ejecuta primero, y los hilos restantes esperan en una cola de ejecución. Este enfoque puede llevar a la inanición de hilos de baja prioridad si los hilos de larga duración evitan que los hilos de baja duración se ejecuten.

Ejemplo de FCFS:

Proceso	Burst Time	Arrival Time
P1	24	0
P2	3	0
P3	4	0

Gráfico de Gantt:

P1 (24) P2 (3) P3 (4)

Tiempo de espera de P1: 0 Tiempo de espera de P2: 24 Tiempo de espera de P3: 27

Tiempo de espera promedio: (0 + 24 + 27) / 3 = 17

Multi-Level Queue Scheduling

Los hilos se dividen en múltiples colas de prioridad, y cada cola tiene su propio algoritmo de planificación. Los hilos se asignan a una cola en función de su prioridad, y el scheduler selecciona la cola con mayor prioridad para ejecutarse. Este enfoque es eficaz para sistemas con múltiples tipos de hilos y requisitos de rendimiento.

Completely Fair Scheduler (CFS)

Este algoritmo se utiliza en el kernel de Linux y se basa en el tiempo de ejecución justo. Cada hilo recibe una cuota de tiempo de CPU proporcional a su prioridad y carga de trabajo. El scheduler ajusta dinámicamente las cuotas de tiempo para garantizar un rendimiento equitativo entre los hilos.

Acá vemos un árbol balanceado.

• Siguiente tarea a ejecutar: Tomar el nodo más a la izquierda.
• La tarea contabiliza su tiempo con la CPU añadiendo su tiempo de ejecución al tiempo de ejecución virtual y, a continuación, se vuelve a insertar en el árbol si es ejecutable