¿Qué es la programación más corta del trabajo primero?
El trabajo más corto primero (SJF) es un algoritmo en el que se elige el proceso que tiene el menor tiempo de ejecución para la siguiente ejecución. Este método de programación puede ser preventivo o no preventivo. Reduce significativamente el tiempo medio de espera de otros procesos en espera de ejecución. La forma completa de SJF es Shortest Job First.
Básicamente, existen dos tipos de métodos SJF:
- SJF no preventivo
- SJF preventivo
En este tutorial del sistema operativo, aprenderá:
- ¿Qué es la programación más corta del trabajo primero?
- Características de la programación SJF
- SJF no preventivo
- SJF preventivo
- Ventajas de SJF
- Desventajas / Contras de SJF
Características de la programación SJF
- Está asociado con 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 fundamental.
- Puede mejorar el rendimiento del proceso asegurándose de que los trabajos más cortos se ejecuten primero, por lo que posiblemente tengan un tiempo de respuesta corto.
- Mejora la producción de trabajos al ofrecer trabajos más cortos, que deben ejecutarse primero, 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 tiempo = 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 tiempo = 4, llega el proceso P5 y se agrega a la cola de espera. P1 continuará la ejecución.
Paso 5) En el tiempo = 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 timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
SJF preventivo
En la programación SJF preventiva, los trabajos se colocan en la cola de listas a medida que llegan. Un proceso con el tiempo de ráfaga más corto comienza la ejecución. Si llega un proceso con un tiempo de ráfaga incluso más corto, el proceso actual se elimina o se evita la 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á ejecutándose.
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. El proceso P1 tiene preferencia.
| 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 mínimo. El proceso P5 tiene preferencia.
| 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 tiempo = 7, P2 termina 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. El proceso P1 se ejecuta porque su tiempo de ráfaga es menor.
Paso 9) En el tiempo = 15, P1 finaliza su ejecución. P3 es el único proceso que queda. Comenzará la 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 timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Ventajas de SJF
Estos son los beneficios / ventajas de usar el método SJF:
- SJF se utiliza con frecuencia para la 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 los 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 con respecto 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 la programación de CPU a corto plazo. 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 la inanición 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 más sobrecarga en el procesador.
Resumen
- SJF es un algoritmo en el que se elige el proceso que tiene el menor tiempo de ejecución para la siguiente ejecución.
- La programación SJF está asociada con 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 fundamental.
- 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 SJF preventiva, los trabajos se colocan en la cola de listas a medida que llegan.
- Aunque comienza un proceso con un tiempo de ráfaga corto, el proceso actual se elimina o se evita la ejecución, y el trabajo que es más corto se ejecuta primero.
- SJF se utiliza con frecuencia para la 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. Se debe a que no existe un método específico para predecir la duración de la próxima ráfaga de CPU.