SJF(Shortest Job First) – Algoritmo de planificación de procesos

SJF(Shortest Job First) – Primero el trabajo mas corto

SJF (Shortest Job First, «primero el trabajo más corto») es un algoritmo de planificación de procesos que, entre los procesos que están listos para ejecutarse, elige primero el que necesita menos tiempo de CPU. En su forma clásica es no apropiativo: cuando un proceso empieza a ejecutarse, no se interrumpe hasta que termina. Su versión apropiativa se conoce como SRTF (Shortest Remaining Time First), y la explicamos más abajo. En algunos libros aparece como SPN (Shortest Process Next, «proceso más corto a continuación»).

Para entender por qué existe hay que partir de una situación muy común en un sistema operativo: varios procesos quieren usar la CPU al mismo tiempo. Los que ya están preparados esperan en la cola de listos, y el planificador decide cuál pasa primero. SJF resuelve esa decisión con una regla sencilla: atender antes el trabajo más corto.

Piensa en la fotocopiadora de una biblioteca. Una persona necesita copiar una sola página y otra, un libro entero. Si pasa primero la de una página, termina en segundos, y la otra apenas espera un poco más. Repetida con muchas personas, esa regla reduce la espera promedio de toda la fila. Esa es la idea de SJF.

¿Cómo funciona el algoritmo SJF?

1. Cada proceso tiene asociada su ráfaga de CPU: el tiempo de CPU que necesita. En los ejercicios se da como dato.
2. Cuando la CPU queda libre, el planificador revisa los procesos que ya llegaron y esperan en la cola de listos. Un proceso que todavía no ha llegado no puede elegirse.
3. Elige el de menor ráfaga.
4. Si hay empate, en este artículo usamos el orden de llegada: pasa primero el que llegó antes (FCFS).
5. El proceso elegido se ejecuta hasta terminar —porque SJF es no apropiativo— y se vuelve al paso 2.

¿Cómo sabe el sistema cuánto va a durar un proceso?

Es la gran limitación de SJF: el sistema operativo no conoce de antemano cuánto durará la próxima ráfaga de CPU de un proceso. En un sistema real se estima a partir de las ráfagas anteriores del mismo proceso, normalmente con un promedio exponencial:

τ_n+1 = α · t_n + (1 − α) · τ_n

• t_n es la duración real de la última ráfaga.
• τ_n es la estimación anterior.
• α, entre 0 y 1, decide cuánto pesa lo más reciente frente al historial.

Por eso SJF encaja mejor donde las duraciones se pueden prever con bastante seguridad, como en el procesamiento por lotes.

Características  – SJF(Shortest Job First)

• Asocia a cada proceso su ráfaga de CPU: las unidades de tiempo de CPU que necesita. En teoría es la duración de su próxima ráfaga; en los ejercicios coincide con el tiempo que necesita para terminar.
• Selecciona el proceso con menor ráfaga de CPU entre los que ya están en la cola de listos.
• En caso de empate aplica FIFO (FCFS): si dos o más procesos tienen la misma ráfaga, pasa primero el que llegó antes.
• Algoritmo no expulsivo (no apropiativo): una vez que un proceso empieza a ejecutarse, no se interrumpe hasta finalizar. Si buscas la versión que sí interrumpe, mira SJF apropiativo (SRTF).
• Minimiza el tiempo de espera promedio cuando todos los procesos están disponibles a la vez: es su gran ventaja (ver ventajas y desventajas).

Ejemplo aplicado al sistema operativo – SJF(Shortest Job First)

Supongamos que en el sistema operativo se van a ejecutar 4 procesos: Word, Excel, Paint y la Calculadora. De cada uno conocemos:

• su ráfaga de CPU, las unidades de tiempo que necesita para ejecutarse (pueden ser milisegundos o cualquier otra unidad);
• su tiempo de llegada, el instante en que entra en la cola de listos.

Representación gráfica del algoritmo el trabajo mas corto

Si nos fijamos en el tiempo de llegada, los procesos entran en este orden: Word (0), Excel (2), Paint (4) y la Calculadora (6).

Sin embargo, el orden de ejecución no es el mismo, porque SJF elige la ráfaga más corta entre los procesos que ya han llegado:

1. t = 0: solo ha llegado Word, así que se ejecuta Word. Como SJF es no apropiativo, sigue hasta terminar en t = 8, aunque mientras tanto lleguen procesos más cortos.
2. t = 8: en la cola de listos están Excel (6), Paint (4) y la Calculadora (2). Se elige la Calculadora, que termina en t = 10.
3. t = 10: quedan Excel (6) y Paint (4). Se elige Paint, que termina en t = 14.
4. t = 14: solo queda Excel, que termina en t = 20.

El mismo resultado en un diagrama de Gantt:

Nota: el tiempo de llegada sí influye en SJF. El algoritmo solo puede elegir entre los procesos que ya están en la cola de listos. Por eso Word, que es el más largo, se ejecuta primero: en t = 0 es el único que ha llegado. Además, el orden de llegada decide los empates.

Calculo tiempo del sistema

El tiempo del sistema —también llamado tiempo de retorno o turnaround time— es el tiempo total que un proceso pasa en el sistema, desde que llega hasta que termina:

Tiempo del sistema = tiempo de salida − tiempo de llegada

El tiempo de salida es el instante en que el proceso termina de ejecutarse. Para nuestro ejemplo:

Tiempo promedio del sistema: (8 + 18 + 10 + 4) / 4 = 10

Ojo con los nombres. Según el libro, el mismo concepto cambia de nombre. En Fundamentos de sistemas operativos (UNAM), el tiempo total se llama «tiempo de respuesta». En otros textos, como OSTEP, «tiempo de respuesta» es otra cosa: lo que tarda un proceso en ejecutarse por primera vez desde que llega.

Calculo tiempo de espera

El tiempo de espera es el tiempo que el proceso pasa en la cola de listos sin usar la CPU. En un algoritmo no apropiativo como SJF se calcula así:

Tiempo de espera = instante en que empieza a ejecutarse − tiempo de llegada

Existe una fórmula equivalente que también sirve para algoritmos apropiativos, donde un proceso puede empezar, parar y volver:

Tiempo de espera = tiempo del sistema − ráfaga de CPU

Por ejemplo, para Excel: 18 − 6 = 12.

Calculo tiempo promedio de espera

Se suman los tiempos de espera y se dividen entre el número de procesos:

(0 + 12 + 6 + 2) / 4 = 5

Con los mismos procesos, el algoritmo FCFS daría un tiempo promedio de espera de 7. Lo comparamos en la diferencia entre SJF y FCFS.

SJF apropiativo: SRTF (Shortest Remaining Time First)

La versión apropiativa (también llamada expropiativa o con desalojo) de SJF se conoce como SRTF, Shortest Remaining Time First: «primero el de menor tiempo restante». En algunos libros aparece como STCF o PSJF (Preemptive Shortest Job First).

La diferencia está en cuándo se decide. Cada vez que llega un proceso nuevo, el planificador compara su ráfaga con lo que le falta al proceso que se está ejecutando. Si el recién llegado necesita menos, interrumpe al actual, que vuelve a la cola de listos con su tiempo restante.

Dos formas de nombrarlo. En unos textos (OSTEP, por ejemplo) «SJF» es siempre no apropiativo, y la versión apropiativa tiene nombre propio: STCF/PSJF o SRTF. En otros (el libro de Silberschatz) se dice que SJF «puede ser apropiativo o no apropiativo», y a su versión apropiativa se la llama SRTF. Es el mismo algoritmo con distinto nombre.

¿Por qué con el ejemplo anterior SRTF no cambia nada?

Si aplicamos SRTF a Word, Excel, Paint y la Calculadora, el resultado es idéntico al de SJF. Cada vez que llega un proceso, su ráfaga empata con lo que le queda a Word:

Como ninguno necesita menos que lo que le falta a Word, no hay expropiación y Word termina en t = 8. Para ver SRTF en acción necesitamos otros datos.

Ejercicio resuelto de SRTF paso a paso

1. t = 0: solo ha llegado el Navegador (7) y empieza a ejecutarse.
2. t = 1: llega Spotify (4). Al Navegador le quedan 6. Como 4 < 6, Spotify expropia al Navegador.
3. t = 2: llega el Bloc de notas (1). A Spotify le quedan 3. Como 1 < 3, el Bloc de notas expropia a Spotify y termina en t = 3.
4. t = 3: llega el Antivirus (2). En la cola están el Navegador (6), Spotify (3) y el Antivirus (2). Se ejecuta el Antivirus, que termina en t = 5.
5. t = 5: quedan Spotify (3) y el Navegador (6). Se ejecuta Spotify, que termina en t = 8.
6. t = 8: solo queda el Navegador, que termina en t = 14.

Diagrama de Gantt:

Tiempos, con tiempo del sistema = salida − llegada y espera = tiempo del sistema − ráfaga:

Los mismos procesos con los tres algoritmos:

SRTF consigue los mejores promedios, pero fíjate en el Navegador, el proceso más largo: con FCFS y con SJF empezaba en t = 0 y no esperaba nada, y con SRTF espera 7. Es el precio de dar siempre preferencia a los cortos, y lleva directamente a su principal problema: la inanición.

Ventajas y desventajas del algoritmo SJF

Ventajas

• Minimiza el tiempo de espera promedio. Si todos los procesos están disponibles a la vez, SJF es óptimo: ningún otro orden consigue una espera promedio menor ni, por lo tanto, un tiempo del sistema promedio menor.
• Los procesos cortos terminan muy rápido, lo que mejora la sensación de agilidad con los trabajos breves.
• Su versión apropiativa (SRTF) mejora aún más los promedios cuando los procesos llegan en momentos distintos, siempre que se conozca su duración.

Desventajas

• Necesita conocer la duración de la ráfaga, y en un sistema real solo se puede estimar. En un sistema operativo de propósito general, el sistema suele saber muy poco de antemano sobre la duración de cada trabajo. Por eso planificadores más elaborados, como las colas multinivel con retroalimentación, intentan comportarse como SJF usando el pasado reciente para predecir el futuro.
• Puede provocar inanición de los procesos largos (lo vemos a continuación).
• En la versión no apropiativa, un proceso largo que ya empezó bloquea a los cortos que lleguen después. En nuestro ejemplo, la Calculadora llega en t = 6 con una ráfaga de solo 2, pero tiene que esperar a que Word termine en t = 8.

Inanición (starvation)

La inanición ocurre cuando un proceso espera indefinidamente porque siempre hay otros a los que el planificador da preferencia. En SJF, un proceso más largo que el promedio está en desventaja: si no dejan de llegar procesos más cortos, puede quedarse esperando indefinidamente.

La solución clásica es el envejecimiento (aging): aumentar la prioridad de un proceso cuanto más tiempo lleva esperando, para que tarde o temprano pase delante. Tiene sentido porque SJF es, en el fondo, un caso particular de planificación por prioridades, donde la prioridad la da la duración de la ráfaga.

Diferencia entre SJF y FCFS

FCFS (First Come, First Served, «primero en llegar, primero en ser servido», también llamado FIFO) atiende los procesos en el orden en que llegan. SJF atiende primero el más corto de los que ya llegaron. La relación entre ambos es directa: SJF usa FCFS para deshacer los empates.

Con FCFS el orden sería Word (0-8), Excel (8-14), Paint (14-18) y Calculadora (18-20).

Fuentes

• R. H. Arpaci-Dusseau y A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, capítulo 7, «Scheduling: Introduction».
• A. Silberschatz, P. B. Galvin y G. Gagne, Operating System Concepts, capítulo 6, «CPU Scheduling» (apuntes de curso de la University of Illinois at Chicago).
• G. Wolf, E. Ruiz, F. Bergero y E. Meza, Fundamentos de sistemas operativos, capítulo «Planificación de procesos», UNAM.

Por último, si este post te fue de ayuda, te invitamos a que comentes y a que lo compartas con personas que lo necesiten.