El trabajo más corto primero (SJF): ejemplo preventivo y no preventivo

⚡ Resumen inteligente

El algoritmo de planificación de tareas SJF (Shortest Job First) selecciona el proceso con el menor tiempo de ejecución para que se ejecute a continuación. Puede ser preventivo o no preventivo y reduce significativamente el tiempo de espera promedio de los procesos.

🇧🇷 Definición: Se elige el proceso con el menor tiempo de ejecución para la siguiente ejecución.
🔀 Dos tipos: SJF puede ser no preferente o preferente (tiempo restante más corto primero).
📉 Beneficio clave: Proporciona el menor tiempo de espera promedio para un conjunto determinado de procesos.
🏭 Mejores usos: Ideal para sistemas por lotes donde los tiempos de ejecución de las tareas se conocen de antemano.
❓ Limitación principal: Es necesario conocer de antemano el tiempo de ráfaga, lo cual es difícil de predecir.
⚠️ Riesgo: Los procesos largos pueden verse afectados si siguen llegando trabajos cortos.

Descubre más

¿Qué es la programación del primer trabajo más corto?

Trabajo más corto primero (SJF) Es un algoritmo en el que el proceso que tiene el menor tiempo de ejecución se elige para la siguiente ejecución. Este método de programación puede ser preventivo o no preventivo. Reduce significativamente el tiempo promedio de espera de otros procesos en espera de ejecución. La forma completa de SJF es el trabajo más corto primero.

Básicamente existen dos tipos de métodos SJF:

SJF no preventivo
SJF preventivo

Características de la programación SJF

Está asociado a cada trabajo como una unidad de tiempo para completar.
Este método de algoritmo es útil para el procesamiento por lotes, donde esperar a que se completen los trabajos no es crítico.
Puede mejorar el rendimiento del proceso al garantizar que las tareas más cortas se ejecuten primero, lo que posiblemente resulte en un tiempo de respuesta más corto.
Mejora la productividad al ofrecer tareas más cortas, que deben ejecutarse primero y que, en general, tienen un plazo de entrega más breve.

SJF no preventivo

En la planificación no preferente, una vez que se asigna el ciclo de CPU a un proceso, este lo retiene hasta que alcanza un estado de espera o finaliza.

Consideremos los siguientes cinco procesos, cada uno con su propio tiempo de ráfaga y tiempo de llegada únicos.

Cola de proceso	Tiempo quemado	Hora de llegada
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Paso 0) En el instante t = 0, P4 llega y comienza su ejecución.

Paso 1) En el instante t = 1, llega el proceso P3. Pero P4 aún necesita 2 unidades de ejecución para completarse. Continuará su ejecución.

Paso 2) En el momento = 2, llega el proceso P1 y se agrega a la cola de espera. P4 continuará la ejecución.

Paso 3) En el tiempo = 3, el proceso P4 finalizará su ejecución. Se compara el tiempo de ráfaga de P3 y P1. El proceso P1 se ejecuta porque su tiempo de ráfaga es menor en comparación con P3.

Paso 4) En el momento = 4, llega el proceso P5 y se agrega a la cola de espera. P1 continuará la ejecución.

Paso 5) En el momento = 5, llega el proceso P2 y se agrega a la cola de espera. P1 continuará la ejecución.

Paso 6) En el tiempo = 9, el proceso P1 finalizará su ejecución. Se compara el tiempo de ráfaga de P3, P5 y P2. El proceso P2 se ejecuta porque su tiempo de ráfaga es el más bajo.

Paso 7) En el tiempo = 10, P2 se está ejecutando y P3 y P5 están en la cola de espera.

Paso 8) En el tiempo = 11, el proceso P2 finalizará su ejecución. Se compara el tiempo de ráfaga de P3 y P5. El proceso P5 se ejecuta porque su tiempo de ráfaga es menor.

Paso 9) En el tiempo = 15, el proceso P5 finalizará su ejecución.

Paso 10) En el tiempo = 23, el proceso P3 finalizará su ejecución.

Paso 11) Calculemos el tiempo de espera promedio para el ejemplo anterior.

Wait time
P4 = 0 - 0 = 0
P1 = 3 - 2 = 1
P2 = 9 - 5 = 4
P5 = 11 - 4 = 7
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

SJF preventivo

En la planificación SJF preventiva, los trabajos se colocan en la cola de listos a medida que llegan. El proceso con el tiempo de ráfaga más corto comienza su ejecución. Si llega un proceso con un tiempo de ráfaga aún más corto, el proceso actual se elimina o se interrumpe su ejecución, y se asigna un ciclo de CPU al trabajo con el tiempo de ráfaga más corto.

Consideremos los siguientes cinco procesos:

Cola de proceso	Tiempo quemado	Hora de llegada
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Paso 0) En el instante t = 0, P4 llega y comienza su ejecución.

Cola de proceso	Tiempo quemado	Hora de llegada
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Paso 1) En el instante t = 1, llega el proceso P3. Pero P4 tiene un tiempo de ejecución más corto. Continuará su ejecución.

Paso 2) En el tiempo = 2, el proceso P1 llega con un tiempo de ráfaga = 6. El tiempo de ráfaga es mayor que el de P4. Por lo tanto, P4 continuará su ejecución.

Paso 3) En el tiempo = 3, el proceso P4 finalizará su ejecución. Se compara el tiempo de ráfaga de P3 y P1. El proceso P1 se ejecuta porque su tiempo de ráfaga es menor.

Paso 4) En el tiempo = 4 llegará el proceso P5. Se compara el tiempo de ráfaga de P3, P5 y P1. El proceso P5 se ejecuta porque su tiempo de ráfaga es el más bajo. Se adelanta el proceso P1.

Cola de proceso	Tiempo quemado	Hora de llegada
P1	Quedan 5 de 6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Paso 5) En el instante t = 5, llegará el proceso P2. Se compara el tiempo de ráfaga de P1, P2, P3 y P5. El proceso P2 se ejecuta porque su tiempo de ráfaga es el menor. El proceso P5 es interrumpido.

Cola de proceso	Tiempo quemado	Hora de llegada
P1	Quedan 5 de 6	2
P2	2	5
P3	8	1
P4	3	0
P5	Quedan 3 de 4	4

Paso 6) En el tiempo = 6, P2 se está ejecutando.

Paso 7) En el instante t = 7, P2 finaliza su ejecución. Se compara el tiempo de ráfaga de P1, P3 y P5. El proceso P5 se ejecuta porque su tiempo de ráfaga es menor.

Cola de proceso	Tiempo quemado	Hora de llegada
P1	Quedan 5 de 6	2
P2	2	5
P3	8	1
P4	3	0
P5	Quedan 3 de 4	4

Paso 8) En el tiempo = 10, P5 finalizará su ejecución. Se compara el tiempo de ráfaga de P1 y P3. Se ejecuta el proceso P1 porque su tiempo de ráfaga es menor.

Paso 9) En el tiempo = 15, P1 finaliza su ejecución. P3 es el único proceso restante. Comenzará su ejecución.

Paso 10) En el tiempo = 23, P3 finaliza su ejecución.

Paso 11) Calculemos el tiempo de espera promedio para el ejemplo anterior.

Wait time
P4 = 0 - 0 = 0
P1 = (3 - 2) + 6 = 7
P2 = 5 - 5 = 0
P5 = 4 - 4 + 2 = 2
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

Ventajas del SJF

Estos son los beneficios/ventajas de utilizar el método SJF:

SJF se utiliza frecuentemente para programación a largo plazo.
Reduce el tiempo de espera promedio en comparación con el algoritmo FIFO (primero en entrar, primero en salir).
El método SJF proporciona el menor tiempo de espera promedio para un conjunto específico de procesos.
Es apropiado para trabajos que se ejecutan por lotes, donde los tiempos de ejecución se conocen de antemano.
Para el sistema por lotes de programación a largo plazo, se puede obtener una estimación del tiempo de ráfaga a partir de la descripción del trabajo.
Para la programación a corto plazo, necesitamos predecir el valor del próximo tiempo de ráfaga.
Probablemente sea óptimo en lo que respecta al tiempo medio de respuesta.

Desventajas/contras de SJF

A continuación se presentan algunos inconvenientes/desventajas del algoritmo SJF:

El tiempo de finalización del trabajo debe conocerse antes, pero es difícil de predecir.
A menudo se utiliza en un sistema por lotes para la programación a largo plazo.
SJF no se puede implementar para programación de la CPU para el corto plazo. Esto se debe a que no existe un método específico para predecir la duración de la próxima ráfaga de CPU.
Este algoritmo puede provocar tiempos de respuesta muy largos o inanición.
Requiere conocimiento de cuánto tiempo se ejecutará un proceso o trabajo.
Esto provoca una escasez de recursos que no reduce el tiempo medio de respuesta.
Es difícil saber la duración de la próxima solicitud de CPU.
Se debe registrar el tiempo transcurrido, lo que supone una mayor carga para el procesador.

Preguntas Frecuentes

SRTF (Shortest Remaining Time First) es simplemente la versión con prioridad de SJF. En SJF, un trabajo en ejecución finaliza antes de que se elija el siguiente. En SRTF, un trabajo recién llegado con un tiempo restante menor puede interrumpir el proceso en ejecución.

SJF siempre prioriza la tarea más corta. Si siguen llegando procesos cortos, un proceso largo podría no obtener nunca la CPU y esperar indefinidamente. Esto se conoce como inanición. El envejecimiento, que aumenta gradualmente la prioridad de una tarea en espera, se utiliza para evitarlo.

Sí. SJF es demostrablemente óptimo porque produce el tiempo de espera promedio mínimo posible para un conjunto dado de procesos. Sin embargo, esto solo es cierto si se conocen de antemano los tiempos de ráfaga, lo cual rara vez es posible en la práctica.

La IA y el aprendizaje automático pueden analizar el historial de un proceso, las características del código y las ejecuciones anteriores para estimar su tiempo de ráfaga de CPU. Unas predicciones más precisas hacen que SJF sea más exacto, reduciendo el tiempo de espera en comparación con las estimaciones tradicionales de promedio exponencial.

Potencialmente. SJF tiene dificultades para la planificación a corto plazo debido a que los tiempos de ráfaga son desconocidos. Una IA que prediga las ráfagas en tiempo real podría hacer que SJF sea utilizable, pero la sobrecarga de predicción y los errores deben mantenerse lo suficientemente bajos para que la decisión de planificación siga siendo útil.