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

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 (digamos 1 unidad cada uno) para verificar si llegó otro proceso con más tiempo de ráfaga hasta ese 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