El trabajo más corto primero (SJF): ejemplo preventivo y no preventivo
¿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 asegurándose de que los trabajos más cortos se ejecuten primero y, por lo tanto, posiblemente tengan un tiempo de respuesta corto.
- Mejora la producción de trabajos al ofrecer trabajos más cortos, que deben ejecutarse primero y que en su mayoría tienen un tiempo de respuesta más corto.
SJF no preventivo
En la programación no preventiva, una vez que el ciclo de la CPU se asigna al proceso, el proceso lo retiene hasta que alcanza un estado de espera o finaliza.
Considere 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 tiempo = 0, llega P4 y comienza la ejecución.
Paso 1) En el momento = 1, llega el Proceso P3. Pero P4 todavía necesita 2 unidades de ejecución para completarse. Continuará la 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 momento = 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 programación preventiva SJF, los trabajos se colocan en la cola de listos a medida que llegan. Un proceso con el tiempo de ráfaga más corto comienza a ejecutarse. Si llega un proceso con un tiempo de ráfaga incluso más corto, el proceso actual se elimina o se adelanta su ejecución, y al trabajo más corto se le asigna un ciclo de CPU.
Considere 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 tiempo = 0, llega P4 y comienza la 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 momento = 1, llega el Proceso P3. Pero P4 tiene un tiempo de ráfaga más corto. Continuará la 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 tiempo = 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 menor. Se adelanta el proceso P5.
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 momento =6, se está ejecutando P2.
Paso 7) En el momento =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 momento =10, P5 finalizará su ejecución. Se compara el tiempo de ráfaga de P1 y P3. El proceso P1 se ejecuta porque su tiempo de ráfaga es menor.
Paso 9) En el momento =15, P1 finaliza su ejecución. P3 es el único proceso que queda. Comenzará la ejecución.
Paso 10) En el momento =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 usar el método SJF:
- SJF se utiliza frecuentemente para programación a largo plazo.
- Reduce el tiempo de espera promedio sobre el algoritmo FIFO (primero en entrar, primero en salir).
- El método SJF proporciona el tiempo de espera promedio más bajo 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 óptimo en cuanto al tiempo medio de respuesta.
Desventajas/contras de SJF
Aquí hay algunos inconvenientes/contras 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.
- Conduce a una hambruna 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 genera una mayor sobrecarga en el procesador.
Resum
- SJF es un algoritmo en el que el proceso que tiene el menor tiempo de ejecución se elige para la siguiente ejecución.
- La programación SJF está asociada 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.
- Básicamente, existen dos tipos de métodos SJF: 1) SJF no preventivo y 2) SJF preventivo.
- En la programación no preventiva, una vez que el ciclo de la CPU se asigna al proceso, el proceso lo retiene hasta que alcanza un estado de espera o finaliza.
- En la programación preventiva SJF, los trabajos se colocan en la cola de listos a medida que llegan.
- Aunque comienza un proceso con un tiempo de ráfaga corto, el proceso actual se elimina o se adelanta en su ejecución y el trabajo que es más corto se ejecuta primero.
- SJF se utiliza frecuentemente para programación a largo plazo.
- Reduce el tiempo de espera promedio sobre el algoritmo FIFO (primero en entrar, primero en salir).
- En la programación SJF, el tiempo de finalización del trabajo debe conocerse antes, pero es difícil de predecir.
- SJF no se puede implementar para la programación de CPU a 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.