Algoritmo de programación de CPU de trabajo más largo primero (LJF)

Requisito previo: gestión de procesos | Programación de CPU 

Longest Job First (LJF) es un algoritmo de programación no preventivo . Este algoritmo se basa en el tiempo de ráfaga de los procesos. Los procesos se colocan en la cola de espera en función de sus tiempos de ráfaga, es decir, en orden descendente de los tiempos de ráfaga. Como sugiere el nombre, este algoritmo se basa en el hecho de que el proceso con el mayor tiempo de ráfaga se procesa primero. Se considera el tiempo de ráfaga sólo de aquellos procesos que han llegado al sistema hasta ese momento. Su versión preventiva se llama algoritmo Longest Remaining Time First (LRTF)

 

Características del trabajo más largo primero (no preventivo)

  • Entre todos los procesos que esperan en una cola de espera, la CPU siempre se asigna al proceso que tiene el mayor tiempo de ráfaga.
  • Si dos procesos tienen el mismo tiempo de ráfaga, el empate se rompe usando FCFS , es decir, el proceso que llegó primero se procesa primero. 
  • LJF CPU Scheduling puede ser tanto de tipo preventivo como no preventivo.

Ventajas del trabajo más largo primero (LJF)

  • Ningún otro proceso puede ejecutarse hasta que el trabajo o proceso más largo se ejecute por completo.
  • Todos los trabajos o procesos finalizan al mismo tiempo aproximadamente.

Desventajas del algoritmo de programación de CPU de trabajo más largo primero

  • Este algoritmo proporciona un tiempo de espera promedio muy alto y un tiempo de respuesta promedio muy alto para un conjunto dado de procesos.
  • Esto puede conducir al efecto de convoy.
  • Puede suceder que un proceso corto nunca se ejecute y el sistema siga ejecutando los procesos más largos.
  • Reduce la velocidad de procesamiento y, por lo tanto, reduce la eficiencia y la utilización del sistema.

Algoritmo de programación de CPU de trabajo más largo primero

  • Paso 1: Primero, ordene los procesos en orden creciente de su hora de llegada. 
  • Paso 2:  elija el proceso que tenga el tiempo de ráfaga más alto entre todos los procesos que han llegado hasta ese momento. 
  • Paso 3: luego procéselo por su tiempo de ráfaga. Compruebe si llega algún otro proceso hasta que este proceso complete la ejecución. 
  • Paso 4:  Repita los tres pasos anteriores hasta que se ejecuten todos los procesos. 

Consideremos los siguientes ejemplos. 

Ejemplo-1: considere la siguiente tabla de tiempo de llegada y tiempo de ráfaga para cuatro procesos P1, P2, P3 y P4.  

Procesos Hora de llegada  Tiempo quemado
P1  

    1 ms   

  2 ms

P2            

2 ms

 4 ms

P3 

3ms

6ms

P4     

  4 ms  

  8ms  

El algoritmo de programación de CPU de trabajo más largo primero funcionará sobre la base de los pasos que se mencionan a continuación:

En el tiempo = 1, Proceso disponible: P1. Entonces, seleccione P1 y comience a ejecutar.

Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
1-2ms P1 1ms   1ms 2ms 1ms

En el tiempo = 2, 

  • Llega el proceso P2 
  • Mientras P1 se está ejecutando, el Proceso P2 esperará en la cola de espera.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
2-3ms P1 1ms P2 1ms 1ms 0ms
P2 2ms 0ms 4ms 4ms

En el tiempo = 3, 

  • P1 se ejecuta y llega el proceso P3
  • Proceso disponible: P2, P3. Entonces, seleccione P3 y ejecute 6 ms (ya que BT (P3) = 6 que es más alto que BT (P2) = 4) 
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
3-4ms P2 2ms P2 0ms 4ms 4ms
P3 3ms 1ms 6ms 5ms

En el tiempo = 4,

  • Llega el proceso P4,
  • Como P3 se está ejecutando, el Proceso P4 esperará en la cola de espera
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
4-5ms P2 2ms P2, P4 0ms 4ms 4ms
P3 3ms 1ms 5ms 4ms
P4 4ms 0ms 8ms 8ms

En el tiempo = 5,

  • El proceso P3 se está ejecutando y P2 y P4 están en la tabla de espera.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
5-9ms P2 2ms P2, P4 0ms 4ms 4ms
P3 3ms 4ms 4ms 0ms
P4 4ms 0ms 8ms 8ms

En el tiempo = 9, 

  • El proceso P3 completa su ejecución, 
  • Proceso disponible: P2, P4. Entonces, seleccione P4 y ejecute 8 ms (ya que, BT(P4) = 8, BT(P2) = 4) 
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
9-17ms P2 2ms P2 0ms 4ms 4ms
P4 4ms 8ms 8ms 0ms

En el tiempo = 17,

  • Finalmente ejecute el proceso P2 por 4 ms. 
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
17-21ms P2 2ms   4ms 4ms 0ms

En el tiempo = 21,

  • El proceso P2 terminará su ejecución.
  • La ejecución global de los procesos será como se muestra a continuación:
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
1-2ms P1 1ms   1ms 2ms 1ms
2-3ms P1 1ms P2 1ms 1ms 0ms
P2 2ms 0ms 4ms 4ms
3-4ms P2 2ms P2 0ms 4ms 4ms
P3 3ms 1ms 6ms 5ms
4-5ms P2 2ms P2, P4 0ms 4ms 4ms
P3 3ms 1ms 5ms 4ms
P4 4ms 0ms 8ms 8ms
5-9ms P2 2ms P2, P4 0ms 4ms 4ms
P3 3ms 4ms 4ms 0ms
P4 4ms 0ms 8ms 8ms
9-17ms P2 2ms P2 0ms 4ms 4ms
P4 4ms 8ms 8ms 0ms
17-21ms P2 2ms   4ms 4ms 0ms

Nota: 
la CPU estará inactiva durante 0 a 1 unidad de tiempo ya que no hay ningún proceso disponible en el intervalo dado. 

El diagrama de Gantt será el siguiente a continuación:

Dado que el tiempo de finalización (CT) se puede determinar directamente mediante el diagrama de Gantt, y  

Tiempo de vuelta (TAT)
= (Tiempo de finalización) – (Hora de llegada)

Además, Tiempo de espera (WT)
= (Tiempo de respuesta) – (Tiempo de ráfaga) 

Por lo tanto, la mesa final parece,  

Producción :  

Tiempo de respuesta total = 40 ms
Entonces, Tiempo de respuesta promedio = 40/4 = 10,00 ms

Y, Tiempo total de espera = 20 ms
Entonces, Tiempo promedio de espera = 20/4 = 5,00 ms 

Ejemplo-2: Considere la siguiente tabla de tiempo de llegada y tiempo de ráfaga para cuatro procesos P1, P2, P3, P4 y P5.  

Procesos       Hora de llegada     Tiempo quemado   
P1 0ms 2ms
P2 0ms 3ms
P3 2ms 2ms
P4 3ms 5ms
P5 4ms 4ms

Diagrama de Gantt para este ejemplo:

Dado que el tiempo de finalización (CT) se puede determinar directamente mediante el diagrama de Gantt, y 

Tiempo de vuelta (TAT)
= (Tiempo de finalización) – (Hora de llegada)

Además, Tiempo de espera (WT)
= (Tiempo de respuesta) – (Tiempo de ráfaga) 

Por lo tanto, la mesa final parece,  

Producción :  

Tiempo de respuesta total = 40 ms
Entonces, Tiempo de respuesta promedio = 40/5 = 8 ms

Y, Tiempo total de espera = 24 ms
Entonces, Tiempo promedio de espera = 24/5 = 4.8 ms 

Publicación traducida automáticamente

Artículo escrito por mohitg593 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *