1. Primera fecha límite más temprana (EDF) :
en el algoritmo de programación Primera fecha límite más temprana, en cada punto de programación se programa la ejecución de la tarea que tiene la fecha límite más corta. Es un algoritmo de programación óptimo basado en prioridades dinámicas utilizado en sistemas en tiempo real. Utiliza las prioridades de las tareas para la programación. En EDF, las prioridades a la tarea se asignan de acuerdo con la fecha límite absoluta. La tarea que tiene la fecha límite más corta obtiene la prioridad más alta.
Ejemplo:
suponga que aquí hay dos procesos P1 y P2.
Sea el período de P1 p1 = 50
Sea el tiempo de procesamiento de P1 t1 = 25
Sea el período de P2 p2 = 75
Sea el tiempo de procesamiento de P2 t2 = 30
Explicación :
- La fecha límite para P1 es anterior, por lo que la prioridad de P1>P2.
- Inicialmente, P1 se ejecuta y completa su ejecución de 25 veces.
- Después de 25 veces, P2 comienza a ejecutar hasta 50 veces, cuando P1 puede ejecutar.
- Ahora, comparando la fecha límite de (P1, P2) = (100, 75), P2 continúa ejecutándose.
- P2 completa su procesamiento en el tiempo 55.
- P1 comienza a ejecutarse hasta el tiempo 75, cuando P2 puede ejecutarse.
- Ahora, comparando nuevamente la fecha límite de (P1, P2) = (100, 150), P1 continúa ejecutándose.
- Repita los pasos anteriores.
- Finalmente, en el tiempo 150, tanto P1 como P2 tienen el mismo plazo, por lo que P2 continuará ejecutándose hasta su tiempo de procesamiento, luego de lo cual P1 comenzará a ejecutarse.
2. Tiempo de holgura mínima (LST) :
en el algoritmo de programación de tiempo de holgura mínima, en cada punto de programación se ejecuta primero la tarea que tiene la holgura mínima. También es un algoritmo de programación dinámico basado en prioridades que se utiliza en sistemas en tiempo real. Asigna cierta prioridad a todas las tareas del sistema de acuerdo con su tiempo de holgura. La tarea que tiene el menor tiempo de holgura (laxitud) obtiene la prioridad más alta.
Ejemplo:
Proceso P1:
Hora de llegada=0, Duración=10, Fecha límite=33
Proceso P2:
Hora de llegada=4, Duración=3, Fecha límite=28
Proceso P3:
Hora de llegada=5, Duración=10, Fecha límite=29
Explicación :
- En el tiempo t=0:
Sólo ha llegado el proceso P1.
P1 se ejecuta hasta el tiempo t=4. - En el tiempo t=4: P2 ha llegado.
Tiempo de holgura de P1: 33-4-6=23 Tiempo de
holgura de P2: 28-4-3=21
Por lo tanto, P2 comienza a ejecutarse hasta el tiempo t=5 cuando llega P3. - En el tiempo t=5:
Tiempo de holgura de P1: 33-5-6=22
Tiempo de holgura de P2: 28-5-2=21
Tiempo de holgura de P3: 29-5-10=12
Por lo tanto, P3 comienza a ejecutarse hasta el tiempo t =13 - En el tiempo t=13:
Tiempo de holgura de P1: 33-13-6=14
Tiempo de holgura de P2: 28-13-2=13
Tiempo de holgura de P3: 29-13-2=14
Por lo tanto, P2 comienza a ejecutarse hasta el tiempo t =15 - En el tiempo t=15:
Tiempo de holgura de P1: 33-15-6=12
Tiempo de holgura de P3: 29-15-2=12
Por lo tanto, P3 comienza a ejecutarse hasta el tiempo t=16 - En el tiempo t=16:
Tiempo de holgura de P1: 33-16-6=11
Tiempo de holgura de P3:29-16-=12
Por lo tanto, P1 comienza a ejecutarse hasta el tiempo t=18 y así sucesivamente.
Diferencia entre los algoritmos de programación EDF y LST:
| FED | LST |
|---|---|
| La tarea que tiene la fecha límite más corta se programa primero en ella. | La tarea que tiene un tiempo de inactividad mínimo se programa primero en ella. |
| Asigna prioridad a las tareas según sus plazos. | Asigna tareas de acuerdo a su tiempo de holgura. |
| Se puede utilizar como programación estática y dinámica. | Se utiliza sólo como programación dinámica. |
| No se requiere el tiempo de ejecución de una tarea. | Requiere tiempo de ejecución de una tarea. |
| Es un algoritmo simple y óptimo. | Es un algoritmo complejo. |
| Se puede implementar en cualquier conjunto de tareas. | Solo se puede implementar en un conjunto de tareas que tienen su tiempo de ráfaga. |
| Utiliza completamente la CPU (incluso a veces al 100%). | Puede subutilizar la CPU. |
| Aumenta la eficiencia y el rendimiento del procesador. | Puede disminuir la eficiencia y el rendimiento del procesador. |