El tiempo restante más largo primero (LRTF) o el trabajo más largo preventivo primero Algoritmo de programación de CPU – Part 1

El tiempo restante más largo primero (LRTF) es una versión preventiva del algoritmo de programación de trabajo más largo primero (LJF) . En este algoritmo de programación, encontramos el proceso con el tiempo restante máximo y luego lo procesamos, es decir, verificamos el tiempo restante máximo después de un intervalo de tiempo (por ejemplo, 1 unidad cada uno) para verificar si llegó otro proceso con más tiempo de ráfaga . tiempo. 

Características del tiempo restante más largo primero (LRTF) 

  • 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 tiempo restante más largo primero (LRTF) 

  • 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 tiempo restante más largo primero (LRTF) 

  • 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 tiempo restante más largo primero (LRTF)

  • Paso 1: Primero, ordene los procesos en orden creciente de su hora de llegada. 
  • Paso 2: elija el proceso que tenga el menor tiempo de llegada pero el mayor tiempo de ráfaga. 
  • Paso 3 : luego procéselo por 1 unidad. Comprobar si llega algún otro proceso hasta ese momento de ejecución o no. 
  • Paso 4: Repita los dos pasos anteriores hasta ejecutar todos los procesos. 
     

Ejemplos para mostrar el funcionamiento del algoritmo de programación de la CPU del primer trabajo más largo preventivo:

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 la CPU del primer tiempo restante más largo funcionará según los pasos que se mencionan a continuación:
 

En el tiempo = 1, 

  • Proceso Disponible : P1. Entonces, seleccione P1 y ejecute 1 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 
1-2ms P1 1ms   1ms 2ms 1ms

En el tiempo = 2, 

  • Proceso disponible: P1, P2. 
  • Entonces, seleccione P2 y ejecute 1 ms (ya que BT(P1) = 1 que es menor 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 
2-3ms P1 1ms P1 0ms 1ms 1ms
P2 2ms 1ms 4ms 3ms

En el tiempo = 3, 

  • Proceso disponible: P1, P2, P3. 
  • Entonces, seleccione P3 y ejecute 1 ms (ya que, BT(P1) = 1, BT(P2) = 3, BT(P3) = 6). 
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 P1 1ms P1, P2 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 1ms 6ms 5ms

En el tiempo = 4,

  • Procesos disponibles: P1, P2, P3, P4. 
  • Por lo tanto, seleccione P4 (ya que el tiempo de ráfaga de P4 es mayor) y ejecute 1 ms (ya que, BT(P1) = 1, BT(P2) = 3, BT(P3) = 6, BT(P4) = 8). 
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 P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 5ms 5ms
P4 4ms 1ms 8ms 7ms

En el tiempo = 5,

  • Procesos disponibles: P1, P2, P3, P4, 
  • El proceso P4 continuará su ejecución ya que ningún otro proceso ha tenido un tiempo de ráfaga mayor que el proceso P4
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-7ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 5ms 5ms
P4 4ms 2ms 7ms 5ms

En el tiempo = 7,

  • Los procesos P3 y P4 tienen el mismo tiempo de ráfaga restante, 
  • por lo tanto, 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. 
  • Por lo tanto, P3 se ejecutará durante 1 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 
7-8ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 1ms 5ms 4ms
P4 4ms 0ms 7ms 5ms

En el tiempo = 8,

  • Procesos disponibles: P1, P2, P3, P4, 
  • El proceso P4 volverá a continuar su ejecución ya que ningún otro proceso ha tenido un tiempo de ráfaga mayor que el proceso P4.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
8-9ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 4ms 4ms
P4 4ms 1ms 5ms 4ms

En el tiempo = 9,

  • Procesos disponibles: P1, P2, P3, P4, 
  • El proceso P3 continúa su ejecución sobre la base de la regla FCFS.
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-10ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 1ms 4ms 3ms
P4 4ms 0ms 4ms 4ms

En el tiempo = 10,

  • Procesos disponibles: P1, P2, P3, P4, 
  • Ahora, nuevamente, el tiempo de ráfaga de P4 es mayor, por lo que seguirá ejecutándose.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
10-11ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 3ms 3ms
P4 4ms 1ms 4ms 3ms

En el tiempo = 11,

  • Procesos disponibles: P1, P2, P3, P4, 
  • El proceso P2 continuará su ejecución ya que el tiempo de ráfaga de P2, P3, P4 es el mismo 
  • Por lo tanto, en este caso, la ejecución posterior se decidirá sobre la base de FCFS, es decir, el proceso que llegó primero se procesa primero. 
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
11-12ms P1 1ms P1, P3, P4 0ms 1ms 1ms
P2 2ms 1ms 3ms 2ms
P3 3ms 0ms 3ms 3ms
P4 4ms 0ms 3ms 3ms

En el tiempo = 12, 

  • Procesos disponibles: P1, P2, P3, P4, 
  • El proceso P3 continúa su ejecución sobre la base de la explicación anterior.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
12-13ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 2ms 2ms
P3 3ms 1ms 3ms 2ms
P4 4ms 0ms 3ms 3ms

En el tiempo = 13,

  • Procesos disponibles: P1, P2, P3, P4, 
  • Ahora, nuevamente, el tiempo de ráfaga de P4 es mayor, por lo que seguirá ejecutándose.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
13-14ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 2ms 2ms
P3 3ms 0ms 2ms 2ms
P4 4ms 1ms 3ms 2ms

En el tiempo = 14,

  • Procesos disponibles: P1, P2, P3, P4 
  • Ahora, el proceso P2 nuevamente comenzará a ejecutarse primero entre todos
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
14-15ms P1 1ms P1, P3, P4 0ms 1ms 1ms
P2 2ms 1ms 2ms 1ms
P3 3ms 0ms 2ms 2ms
P4 4ms 0ms 2ms 2ms

En el tiempo = 15,

  • Procesos disponibles: P1, P2, P3, P4, ahora se ejecutará P3
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
15-16ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 1ms 1ms
P3 3ms 1ms 2ms 1ms
P4 4ms 0ms 2ms 2ms

En el tiempo = 16,

  • Procesos disponibles: P1, P2, P3, P4, 
  • aquí, P4 se ejecutará ya que tiene el tiempo de ráfaga más grande entre todos
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
16-17ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 1ms 1ms
P3 3ms 0ms 1ms 1ms
P4 4ms 1ms 2ms 1ms

En el tiempo = 17,

  • Procesos disponibles: P1, P2, P3, P4, 
  • El proceso P1 se ejecutará aquí sobre la base de la explicación anterior
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-18ms P1 1ms P2, P3, P4 1ms 1ms 0ms
P2 2ms 0ms 1ms 1ms
P3 3ms 0ms 1ms 1ms
P4 4ms 0ms 1ms 1ms

En el tiempo = 18,

  • Procesos disponibles: P2, P3, P4,  
  • Se ejecutará el proceso P2.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
18-19ms P2 2ms P3, P4 1ms 1ms 0ms
P3 3ms 0ms 1ms 1ms
P4 4ms 0ms 1ms 1ms

En el tiempo = 19,

  • Procesos disponibles: P3, P4,  
  • Se ejecutará el proceso P3.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
19-20ms P3 3ms P4 1ms 1ms 0ms
P4 4ms 0ms 1ms 1ms

En el tiempo = 20,

  • El proceso P4 se ejecutará al final.
Instancia de tiempo Proceso Hora de llegada Mesa de espera Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
20-21ms P4 4ms   1ms 1ms 0ms

En el tiempo = 22,

  • El proceso P4 terminará su ejecución.

La ejecución general 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 P1 0ms 1ms 1ms
P2 2ms 1ms 4ms 3ms
3-4ms P1 1ms P1, P2 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 1ms 6ms 5ms
4-5ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 5ms 5ms
P4 4ms 1ms 8ms 7ms
5-7ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 5ms 5ms
P4 4ms 2ms 7ms 5ms
7-8ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 1ms 5ms 4ms
P4 4ms 0ms 7ms 5ms
8-9ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 4ms 4ms
P4 4ms 1ms 5ms 4ms
9-10ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 1ms 4ms 3ms
P4 4ms 0ms 4ms 4ms
10-11ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 3ms 3ms
P3 3ms 0ms 3ms 3ms
P4 4ms 1ms 4ms 3ms
11-12ms P1 1ms P1, P3, P4 0ms 1ms 1ms
P2 2ms 1ms 3ms 2ms
P3 3ms 0ms 3ms 3ms
P4 4ms 0ms 3ms 3ms
12-13ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 2ms 2ms
P3 3ms 1ms 3ms 2ms
P4 4ms 0ms 3ms 3ms
13-14ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 2ms 2ms
P3 3ms 0ms 2ms 2ms
P4 4ms 1ms 3ms 2ms
14-15ms P1 1ms P1, P3, P4 0ms 1ms 1ms
P2 2ms 1ms 2ms 1ms
P3 3ms 0ms 2ms 2ms
P4 4ms 0ms 2ms 2ms
15-16ms P1 1ms P1, P2, P4 0ms 1ms 1ms
P2 2ms 0ms 1ms 1ms
P3 3ms 1ms 2ms 1ms
P4 4ms 0ms 2ms 2ms
16-17ms P1 1ms P1, P2, P3 0ms 1ms 1ms
P2 2ms 0ms 1ms 1ms
P3 3ms 0ms 1ms 1ms
P4 4ms 1ms 2ms 1ms
17-18ms P1 1ms P2, P3, P4 1ms 1ms 0ms
P2 2ms 0ms 1ms 1ms
P3 3ms 0ms 1ms 1ms
P4 4ms 0ms 1ms 1ms
18-19ms P2 2ms P3, P4 1ms 1ms 0ms
P3 3ms 0ms 1ms 1ms
P4 4ms 0ms 1ms 1ms
19-20ms P3 3ms P4 1ms 1ms 0ms
P4 4ms 0ms 1ms 1ms
20-21ms P4 4ms   1ms 1ms 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, 

 

Tiempo de respuesta total = 68 ms
Entonces, Tiempo de respuesta promedio = 68/4 = 17,00 ms

Y, Tiempo total de espera = 48 ms Tiempo promedio de espera
= 48/4 = 12,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

Del mismo modo ejemplo-1, 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, 

Tiempo de respuesta total = 61 ms
Entonces, Tiempo de respuesta promedio = 61/5 = 12,20 ms

Y, Tiempo total de espera = 45 ms
Entonces, Tiempo promedio de espera = 45/5 = 9,00 ms 

Publicación traducida automáticamente

Artículo escrito por Rohit_ranjan 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 *