El algoritmo de programación de CPU de prioridad preventiva es un método preventivo de algoritmo de programación de CPU que funciona en función de la prioridad de un proceso. En este algoritmo, el programador programa las tareas para que funcionen según la prioridad, lo que significa que primero se debe ejecutar un proceso de mayor prioridad. En caso de conflicto, es decir, cuando hay más de un proceso con las mismas prioridades, el algoritmo de programación de CPU de prioridad preventiva funciona sobre la base del algoritmo FCFS (primero en llegar, primero en servir) .
¿Cómo el algoritmo de programación de CPU de prioridad preventiva decide la prioridad de un proceso?
El algoritmo de programación de CPU de prioridad preventiva utiliza un sistema basado en rangos para definir un rango para cada proceso, donde los procesos de menor rango tienen mayor prioridad y los procesos de mayor rango tienen menor prioridad. Por ejemplo, si hay 10 procesos para ejecutar con este algoritmo preventivo, entonces el proceso con el rango 1 tendrá la prioridad más alta, el proceso con el rango 2 tendrá una prioridad comparativamente menor y el proceso con el rango 10 tendrá la prioridad más baja.
¿Cómo funciona el algoritmo de programación de CPU de prioridad preventiva?
- Paso 1: seleccione el primer proceso cuya hora de llegada será 0, debemos seleccionar ese proceso porque ese proceso solo se está ejecutando en el momento t = 0.
- Paso 2: Verifique la prioridad del próximo proceso disponible. Aquí tenemos que verificar 3 condiciones.
- si prioridad (proceso_actual) > prioridad (proceso_prior) : – entonces ejecute el proceso actual.
- si la prioridad (proceso_actual) > prioridad (proceso_anterior) : – entonces ejecute el proceso anterior.
- si la prioridad (proceso_actual) > prioridad (proceso_prior) : – luego ejecute el proceso que llega primero, es decir, la hora de llegada debe ser la primera.
- Paso 3: Repita el paso 2 hasta llegar al proceso final.
- Paso 4: cuando llegue al proceso final, elija el proceso que tenga la prioridad más alta y ejecútelo. Repita el mismo paso hasta que todos los procesos completen su ejecución.
Programa para la programación de CPU de prioridad preventiva
Ejemplos para mostrar el funcionamiento del algoritmo de programación de CPU de prioridad preventiva
Ejemplo-1: considere la siguiente tabla de tiempo de llegada, prioridad y tiempo de ráfaga para cinco procesos P1, P2, P3, P4 y P5 .
| Proceso | Hora de llegada | Prioridad | Tiempo quemado |
|---|---|---|---|
| P1 | 0 ms | 3 | 3ms |
| P2 | 1 ms | 2 | 4 ms |
| P3 | 2 ms | 4 | 6ms |
| P4 | 3ms | 6 | 4 ms |
| P5 | 5ms | 10 | 2 ms |
El algoritmo de programación de CPU de prioridad preventiva funcionará sobre la base de los pasos que se mencionan a continuación:
- En el tiempo t = 0,
- El proceso P1 es el único proceso disponible en la cola de procesos listos, ya que su tiempo de llegada es de 0 ms.
- Por lo tanto, el Proceso P1 se ejecuta primero durante 1 ms, de 0 ms a 1 ms, independientemente de su prioridad.
- Tiempo de ráfaga restante (BT) para P1 = 3-1 = 2 ms.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 0 ms – 1 ms | P1 | 0 ms | 3 | 1ms | 3ms | 2 ms |
- En el tiempo t = 1 ms,
- Hay 2 procesos disponibles en la cola de listos: P1 y P2.
- Dado que la prioridad del proceso P2 es mayor que la prioridad del proceso P1, el proceso P2 se ejecutará primero.
- Por lo tanto, el proceso P2 se ejecuta durante 1 ms, de 1 ms a 2 ms.
- Tiempo de ráfaga restante (BT) para P2 = 4-1 = 3 ms.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 1 ms – 2 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P2 | 1 ms | 2 | 1 | 4 ms | 3ms |
- En el tiempo t = 2 ms,
- Hay 3 procesos disponibles en la cola de listos: P1, P2 y P3.
- Dado que la prioridad del proceso P2 es mayor que la prioridad de los procesos P1 y P3, el proceso P2 se ejecutará primero.
- Por lo tanto, el proceso P2 se ejecuta durante 1 ms, de 2 ms a 3 ms.
- Tiempo de ráfaga restante (BT) para P2 = 3-1 = 2 ms.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 2 ms – 3 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P2 | 1 ms | 2 | 1 | 3ms | 2 ms | |
| P3 | 2 ms | 4 | 0 | 6ms | 6ms |
- En el tiempo t = 3ms,
- Hay 4 procesos disponibles en la cola de listos: P1, P2, P3 y P4.
- Dado que la prioridad del proceso P2 es la más alta entre la prioridad de los procesos P1, P2, P3 y P4, el proceso P2 se ejecutará primero.
- Por lo tanto, el proceso P2 se ejecuta durante 1 ms, de 3 a 4 ms.
- Tiempo de ráfaga restante (BT) para P2 = 1-1 = 0 ms.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 3 ms – 4 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P2 | 1 ms | 2 | 1 | 2 ms | 1 ms | |
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms |
- En el tiempo t = 4ms,
- Hay 5 procesos disponibles en la cola de listos: P1, P2, P3, P4 y P5.
- Dado que la prioridad del proceso P2 es la más alta entre la prioridad de los procesos P1, P2, P3, P4 y P5, el proceso P2 se ejecutará primero.
- Por lo tanto, el Proceso P2 se ejecuta durante 1 ms, de 4 ms a 5 ms.
- Tiempo de ráfaga restante (BT) para P2 = 1-1 = 0 ms.
- Dado que el tiempo de ráfaga del proceso P2 se ha convertido en 0, está completo y se eliminará de la cola del proceso.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 4 ms – 5 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms |
- En el tiempo t = 5 ms,
- Hay 4 procesos disponibles en la cola de listos: P1, P3, P4 y P5.
- Dado que la prioridad del proceso P1 es la más alta entre las prioridades de los procesos P1, P3, P4 y P5, el proceso P1 se ejecutará primero.
- Por tanto, el Proceso P1 se ejecuta durante 2ms, de 5ms a 7ms.
- Tiempo de ráfaga restante (BT) para P1 = 2-2 = 0 ms.
- Dado que el tiempo de ráfaga del proceso P1 se ha convertido en 0, está completo y se eliminará de la cola del proceso.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 5 ms – 7 ms | ||||||
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms |
- En el tiempo t = 7ms,
- Hay 3 procesos disponibles en la cola de listos: P3, P4 y P5.
- Dado que la prioridad del proceso P3 es la más alta entre las prioridades de los procesos P3, P4 y P5, el proceso P3 se ejecutará primero.
- Por lo tanto, el proceso P3 se ejecuta durante 6 ms, de 7 ms a 13 ms.
- Tiempo de ráfaga restante (BT) para P3 = 6-6 = 0 ms.
- Dado que el tiempo de ráfaga del proceso P3 se ha convertido en 0, está completo y se eliminará de la cola del proceso.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 7 ms – 13 ms | ||||||
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms |
- En el tiempo t = 13 ms,
- Hay 2 procesos disponibles en la cola de listos: P4 y P5.
- Dado que la prioridad del proceso P4 es la más alta entre la prioridad de los procesos P4 y P5, el proceso P4 se ejecutará primero.
- Por lo tanto, el proceso P4 se ejecuta durante 4 ms, de 13 a 17 ms.
- Tiempo de ráfaga restante (BT) para P4 = 4-4 = 0 ms.
- Dado que el tiempo de ráfaga del proceso P4 se ha convertido en 0, está completo y se eliminará de la cola del proceso.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 13 ms – 17 ms | ||||||
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms |
- En el tiempo t = 17 ms,
- Solo hay 1 proceso disponible en la cola lista: P5.
- Por lo tanto, el proceso P5 se ejecuta durante 2 ms, de 17 a 19 ms.
- Tiempo de ráfaga restante (BT) para P5 = 2-2 = 0 ms.
- Dado que el tiempo de ráfaga del proceso P5 se ha convertido en 0, está completo y se eliminará de la cola del proceso.
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 17 ms – 19 ms | P5 | 5ms | 10 | 2 | 2 ms | 0 ms |
- En el tiempo t = 19 ms,
- No hay más procesos disponibles en la cola de listos. Por lo tanto, el procesamiento ahora se detendrá.
- La ejecución global de los procesos será como se muestra a continuación:
| Instancia de tiempo | Proceso | Hora de llegada | Prioridad | Tiempo de ejecución | Tiempo de ráfaga inicial | Tiempo de ráfaga final |
|---|---|---|---|---|---|---|
| 0 ms – 1 ms | P1 | 0 ms | 3 | 1 | 3ms | 2 ms |
| 1 ms – 2 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P2 | 1 ms | 2 | 1 | 4 ms | 3ms | |
| 2 ms – 3 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P2 | 1 ms | 2 | 1 | 3ms | 2 ms | |
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| 3 ms – 4 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P2 | 1 ms | 2 | 1 | 2 ms | 1 ms | |
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| 4 ms – 5 ms | P1 | 0 ms | 3 | 0 | 2 ms | 2 ms |
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms | |
| 5 ms – 7 ms | ||||||
| P3 | 2 ms | 4 | 0 | 6ms | 6ms | |
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms | |
| 7 ms – 13 ms | ||||||
| P4 | 3ms | 6 | 0 | 4 ms | 4 ms | |
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms | |
| 13 ms – 17 ms | ||||||
| P5 | 5ms | 10 | 0 | 2 ms | 2 ms | |
| 17 ms – 19 ms | P5 | 5ms | 10 | 2 | 2 ms | 0 ms |
Diagrama de Gantt para la ejecución anterior:
Ahora necesitamos calcular el tiempo de finalización (CT) y la primera hora de llegada (FAT) de cada proceso a través del diagrama de Gantt, según las siguientes relaciones:
Tiempo de vuelta (TAT) = (Tiempo de finalización) – (Hora de llegada)
Tiempo de espera (WT) = (Tiempo de respuesta) – (Tiempo de ráfaga)
Tiempo de respuesta (RT) = (Primera hora de llegada) – (Hora de llegada)
Después de calcular los campos anteriores, la tabla final parece
Aquí, H: máxima prioridad y L: menor prioridad
Algunas otras relaciones importantes para este ejemplo incluyen:
- Tiempo de respuesta total = 7 + 4 + 11 + 14 + 14 = 50 ms
- Tiempo medio de respuesta = (Tiempo total de respuesta)/(número de procesos) = 50/5 = 10,00 ms
- Tiempo total de espera = 4 + 0 + 15 + 10 + 12 = 41 ms
- Tiempo de Espera Promedio = (Tiempo de Espera Total)/(n° de procesos) = 41/5 = 8.20 ms
- Tiempo de respuesta total = 0 + 0 + 5 + 10 + 12 = 27 ms
- Tiempo de respuesta medio = (Tiempo de respuesta total)/(nº de procesos) = 27/5 = 5,40 ms
Ejemplo 2:
Considere la siguiente tabla de tiempo de llegada, prioridad y tiempo de ráfaga para siete procesos P1, P2, P3, P4, P5, P6 y P7
| Proceso | Hora de llegada | Prioridad | Tiempo quemado |
| P1 | 0 ms | 3 | 8ms |
| P2 | 1 ms | 4 | 2 ms |
| P3 | 3ms | 4 | 4 ms |
| P4 | 4 ms | 5 | 1 ms |
| P5 | 5ms | 2 | 6ms |
| P6 | 6ms | 6 | 5ms |
| P7 | 10 ms | 1 | 1 ms |
- En el tiempo t = 0 ,
- El proceso P1 está disponible en la cola de procesos listos, ejecutando P1 durante 1 ms
- BT restante para P1 = 8-1 = 7 ms.
- En el tiempo t = 1 ,
- La prioridad de P1 es mayor que la de P2, por lo que ejecutamos P1 durante 2 ms, de 1 ms a 3 ms.
- BT restante para P1 = 7-2 = 5 ms.
- En el tiempo t = 3 ,
- La prioridad de P1 es mayor que la de P3, por lo que ejecutamos P1 durante 1 ms.
- BT restante para P1 = 5-1 = 4 ms.
- En el tiempo t = 4 ,
- La prioridad de P1 es mayor que la de P4, por lo que ejecutamos P1 durante 1 ms.
- BT restante para P1 = 4-1 = 3 ms.
- En el tiempo t = 5 ,
- La prioridad de P5 es mayor que P1, por lo que ejecutamos P5 durante 1 ms.
- BT restante para P5 = 6-1 = 5 ms.
- En el tiempo t = 6 ,
- La prioridad de P5 es mayor que la de P6, por lo que ejecutamos P5 durante 4 ms.
- BT restante para P5 = 5-4 = 1 ms.
- En el tiempo t = 10 ,
- La prioridad de P7 es mayor que P5, por lo que ejecutamos P7 durante 1 ms.
- BT restante para P7 = 1-1 = 0 ms.
- Aquí el Proceso P7 completa su ejecución.
- En el tiempo t = 11 ,
- Ahora tomamos el proceso que tiene la prioridad más alta.
- Aquí encontramos que P5 tiene la prioridad más alta y ejecutamos P5 completamente
- BT restante de P5 = 1-1 = 0 ms.
- Aquí el Proceso P5 completa su ejecución.
- En el tiempo t = 12 ,
- Ahora tomamos el proceso que tiene la prioridad más alta.
- Aquí encontramos que P1 tiene la prioridad más alta y ejecutamos P1 completamente
- BT restante de P1 = 3-3 = 0 ms.
- Aquí el Proceso P1 completa su ejecución.
- En el tiempo t = 15 ,
- Ahora tomamos el proceso que tiene la prioridad más alta.
- Aquí encontramos que P2 tiene la prioridad más alta y ejecutamos P2 completamente
- BT restante de P2 = 2-2 = 0 ms.
- Aquí el Proceso P2 completa su ejecución.
- En el tiempo t = 17 ,
- Ahora tomamos el proceso que tiene la prioridad más alta.
- Aquí encontramos que P3 tiene la prioridad más alta y ejecutamos P3 completamente
- BT restante de P3 = 4-4 = 0 ms.
- Aquí el Proceso P3 completa su ejecución.
- En el tiempo t = 21 ,
- Ahora tomamos el proceso que tiene la prioridad más alta.
- Aquí encontramos que P4 tiene la prioridad más alta y ejecutamos P4 completamente
- BT restante de P4 = 1-1 = 0 ms.
- Aquí el Proceso P4 completa su ejecución.
- En el tiempo t = 22 ,
- Ahora tomamos el proceso que tiene la prioridad más alta.
- Aquí encontramos que P6 tiene la prioridad más alta y ejecutamos P6 completamente
- BT restante de P6 = 5-5 = 0 ms.
- Aquí el Proceso P6 completa su ejecución.
Gráfico de gantt:
Aquí, H: mayor prioridad, L: menor prioridad
Inconvenientes del algoritmo de programación de prioridad preventiva:
Uno de los inconvenientes más comunes del algoritmo de programación de CPU de prioridad preventiva es el problema de inanición .Este es el problema en el que un proceso tiene que esperar más tiempo para programarse en la CPU. Esta condición se llama el problema de la inanición.
Ejemplo: En el Ejemplo 2, podemos ver que el proceso P1 tiene Prioridad 3 y hemos reemplazado el proceso P1 y asignado la CPU a P5. Aquí solo tenemos 7 procesos.
Ahora, supongamos que tenemos muchos procesos cuya prioridad es más alta que P1, entonces P1 necesita esperar más tiempo para que la CPU anule y programe el otro proceso. Esta condición se llama como problema de inanición.
Solución: La solución para este problema de inanición es el envejecimiento . Esto se puede hacer disminuyendo el número de prioridad por un cierto número de un proceso en particular que espera un período de tiempo más largo después de un cierto intervalo.
Después de cada 3 unidades de tiempo, todos los procesos que están en estado de espera, la prioridad de esos procesos se reducirá en 2, por lo tanto, si hay un proceso P1 que tiene prioridad 5, después de esperar 3 unidades de tiempo su prioridad se reducirá de 5 a 3, de modo que si hay algún proceso P2 que tiene prioridad como 4, ese proceso P2 esperará y P1 se programará y ejecutará.
Publicación traducida automáticamente
Artículo escrito por devasishakula503 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA