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 | P2 | |||||
| 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 |
| 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 |
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 |
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 | P2 | |||||
| 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 |
| P4 | 4ms | 0ms | 8ms | 8ms | ||
| 9-17ms | P2 | 2ms | P2 | 0ms | 4ms | 4ms |
| 17-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,
Producción :
Tiempo de respuesta total = 40 ms
Entonces, Tiempo de respuesta promedio = 40/4 = 10,00 msY, 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 msY, Tiempo total de espera = 24 ms
Entonces, Tiempo promedio de espera = 24/5 = 4.8 ms