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 | P2, P3, P4 | |||||
| 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 | P3, P4 | |||||
| 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 | P4 | |||||
| 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 |
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 | P2, P3, P4 | |||||
| P2 | 2ms | 0ms | 1ms | 1ms | ||
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 0ms | 1ms | 1ms | ||
| 18-19ms | P3, P4 | |||||
| P3 | 3ms | 0ms | 1ms | 1ms | ||
| P4 | 4ms | 0ms | 1ms | 1ms | ||
| 19-20ms | P4 | |||||
| P4 | 4ms | 0ms | 1ms | 1ms | ||
| 20-21ms |
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 msY, 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 msY, 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