SJF: el trabajo más corto primero

1. Qué es SJF

SJF (Shortest Job First) es el algoritmo de planificación que, cada vez que la CPU queda libre, elige el proceso listo con la rornecedor de CPU más corta. Si hay empate, se desempata por orden de llegada (FIFO).

SJF es el algoritmo «ideal» en el sentido de que minimiza el tiempo de espera promedio (y con él el de retorno) cuando todos los procesos llegan en cero. Es el algoritmo que cualquier planificador querría usar si pudiera, pero tiene un problema fundamental: para saber cuál es el proceso más corto, hay que conocer las ráfagas de CPU antes de ejecutarlas, y en la práctica eso es casi imposible.

SJF se conoce también como SPF (Shortest Process First) o, en su versión apropiativa, SRTF (Shortest Remaining Time First). En este tema nos centramos en la versión no apropiativa; la apropiativa se estudia en el tema 14.

2. Cómo funciona

SJF funciona así:

1. Llega un proceso. Se añade a la cola de listos. Si la CPU está ociosa, se evalúa si este proceso es el más corto entre los listos. llegada
2. La CPU queda libre. Se examina la cola de listos y se elige el proceso con la ráfaga más corta. decisión
3. El proceso se ejecuta. Conserva la CPU hasta que termina su ráfaga (SJF no apropiativo) o hasta que se le acaba el turno (en SRTF). ejecución
4. Se repite. Cuando el proceso termina, se vuelve al paso 2. bucle

La diferencia clave con FCFS es el paso 2: FCFS toma el primero de la cola (FIFO); SJF toma el más corto. La cola de listos ya no es FIFO: hay que buscar el mínimo cada vez que la CPU queda libre.

La búsqueda del mínimo tiene un costo: O(n) si se recorre la cola, o O(log n) si se mantiene un heap. En la práctica, ese costo es pequeño comparado con el tiempo de las ráfagas, pero es un overhead que FCFS no tiene.

3. Un ejemplo desarrollado

Cuatro procesos, todos llegando en 0, con ráfagas 8, 4, 2 y 1 (el mismo conjunto del tema 7):

SJF ejecuta primero el más corto (P4), luego el siguiente más corto (P3), luego P2, y finalmente P1:

Las métricas:

Comparado con FCFS para el mismo conjunto (ráfagas 8, 4, 2, 1 en ese orden), que daba espera promedio 8,50 y retorno 12,25, SJF reduce la espera a 2,75 (un 68 % menos) y el retorno a 6,50. El proceso largo (P1) espera 7 en lugar de 0, pero los tres cortos esperan mucho menos.

4. Por qué minimiza la espera: la demostración

SJF minimiza el tiempo de espera promedio (y con él el de retorno) cuando todos los procesos llegan en cero. La demostración se basa en un argumento de intercambio: si en una planificación hay dos procesos adyacentes donde el más largo va primero, intercambiarlos reduce (o no aumenta) la suma de esperas.

Sea una planificación donde dos procesos adyacentes A y B se ejecutan en ese orden, con ráfagas a y b, y a > b. Supongamos que antes de ellos ya se han ejecutado procesos que suman T unidades de tiempo. Entonces:

• Orden A, B: la espera de A es T; la espera de B es T + a. Suma: 2T + a.
• Orden B, A: la espera de B es T; la espera de A es T + b. Suma: 2T + b.

Como b < a, la suma en el segundo caso es menor: 2T + b < 2T + a. Los demás procesos no se ven afectados porque la suma de las ráfagas de A y B es la misma en ambos órdenes. Por lo tanto, intercambiar A y B (poner el más corto primero) reduce la suma de esperas.

Si en una planificación hay algún par de procesos adyacentes con el más largo primero, se puede intercambiarlos y reducir la suma. Repitiendo este proceso, se llega a la planificación donde los procesos están ordenados por ráfaga creciente: SJF. Y como cada intercambio reduce (o no aumenta) la suma, SJF es óptimo.

5. El argumento de intercambio en detalle

La demostración anterior se puede expresar como un algoritmo que convierte cualquier planificación en SJF:

1. Busca un par adyacente invertido. Recorre la planificación de izquierda a derecha buscando dos procesos consecutivos donde el primero tenga ráfaga mayor que el segundo. buscar
2. Intercámbialos. Pon el más corto primero. La suma de esperas disminuye (o se mantiene si son iguales). intercambiar
3. Repite. Sigue buscando pares invertidos. Cada intercambio reduce la suma, así que el proceso termina. iterar
4. Resultado: SJF. Cuando no hay más pares invertidos, los procesos están ordenados por ráfaga creciente. SJF

Este proceso es similar al ordenamiento por burbuja (bubble sort): cada intercambio reduce el número de inversiones, y el resultado final es la lista ordenada. Por eso SJF también se llama «ordenamiento por ráfaga».

La optimalidad se refiere al tiempo de espera promedio (y al de retorno, que difiere por una constante). No se refiere al tiempo de respuesta (que puede ser peor que Round Robin) ni a la equidad (que puede ser muy mala para procesos largos).

6. Propiedades de SJF

SJF es óptimo para el promedio, pero no es justo ni evita la inanición. Es un algoritmo que optimiza una métrica a costa de otras.

7. Ventajas

• Minimiza el tiempo de espera promedio: es el algoritmo óptimo cuando se conocen las ráfagas y todos llegan en 0.
• Minimiza el tiempo de retorno promedio: por la misma razón.
• Reduce el efecto convoy: los procesos cortos no esperan detrás de los largos.
• Buen tiempo de respuesta para procesos cortos: los procesos cortos se ejecutan primero, así que responden rápido.
• Bajo overhead: la búsqueda del mínimo es barata comparada con el tiempo de las ráfagas.

8. Desventajas

• Necesita conocer las ráfagas: en la práctica, las ráfagas no se conocen de antemano. Hay que predecirlas (tema 15).
• Inanición: un flujo continuo de procesos cortos puede postergar indefinidamente a uno largo.
• No es justo: un proceso largo puede esperar mucho más que los cortos.
• No minimiza el tiempo de respuesta: Round Robin es mejor para interactividad.
• Sensible a la predicción: si la predicción de la ráfaga es incorrecta, el algoritmo puede elegir mal.

9. Inanición

La inanición (starvation) ocurre cuando un proceso espera indefinidamente porque siempre hay otros procesos más cortos que se ejecutan antes. En SJF, un proceso largo puede esperar para siempre si llega un flujo continuo de procesos cortos.

Ejemplo: un proceso con ráfaga 100 llega en 0. Después llegan procesos con ráfaga 1 cada 0,5 unidades. Cada vez que el proceso largo va a ejecutarse, hay un proceso corto nuevo que se ejecuta antes. El proceso largo espera indefinidamente.

La solución es el envejecimiento (aging): aumentar la prioridad (o reducir la ráfaga estimada) de los procesos que llevan mucho tiempo esperando. Con envejecimiento, un proceso largo que espera suficiente tiempo se vuelve «más corto» que los nuevos y se ejecuta. El envejecimiento se estudia en el tema 18.

10. SJF no apropiativo

En este tema nos hemos centrado en SJF no apropiativo: una vez que un proceso recibe la CPU, la conserva hasta que termina su ráfaga. El planificador no puede interrumpirlo.

Esto tiene una consecuencia importante: si un proceso largo ya se está ejecutando y llega un proceso más corto, SJF no apropiativo no puede interrumpir al largo. El proceso corto debe esperar. Por eso, SJF no apropiativo no es tan bueno como SRTF (con apropiación) cuando las llegadas son distintas.

En el tema 14 se estudia SRTF, que sí interrumpe al proceso largo cuando llega uno más corto. SRTF es todavía mejor que SJF no apropiativo en términos de tiempo de espera promedio, pero tiene más overhead (más cambios de contexto).

11. SJF vs FCFS

FCFS es más simple y más justo, pero SJF es más eficiente. La elección depende de si se conocen las ráfagas y de si la optimización del promedio es más importante que la equidad.

12. Simulador interactivo

Este simulador ejecuta SJF sobre una carga de trabajo generada aleatoriamente. Compara las métricas con las de FCFS para el mismo conjunto:

13. Resumen

• SJF ejecuta primero el proceso con la ráfaga de CPU más corta.
• Minimiza el tiempo de espera y de retorno promedio cuando todos llegan en cero y se conocen las ráfagas.
• La optimalidad se demuestra con el argumento de intercambio: poner el más corto primero reduce la suma de esperas.
• Los intercambios no afectan a los procesos que van después, porque la suma de ráfagas es la misma.
• SJF no es justo: los procesos largos pueden esperar mucho (inanición).
• Necesita conocer las ráfagas de antemano, lo que es difícil en la práctica.
• La versión no apropiativa no interrumpe a un proceso largo que ya se ejecuta.
• Con envejecimiento se evita la inanición.
• SJF se usa en combinación con predicción y apropiación (SRTF).

14. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Calcula las métricas para ráfagas 6, 4, 2, 1 en SJF y compara con FCFS.
2. Demuestra el argumento de intercambio con un ejemplo de tres procesos adyacentes.
3. Dibuja el Gantt de SJF para P1(0,8), P2(1,4), P3(2,2), P4(3,1) y compara con FCFS.
4. Explica por qué SJF no minimiza el tiempo de respuesta.
5. Diseña un conjunto de procesos donde SJF sufra inanición y explica cómo el envejecimiento la evita.
6. Modifica el simulador para mostrar SJF y FCFS uno encima del otro para la misma carga.