Algoritmo de programación Least Slack Time (LST) en sistemas en tiempo real

Least Slack Time (LST) es un algoritmo de programación dinámico basado en prioridades que se utiliza en sistemas en tiempo real.

En LST, a todas las tareas del sistema se les asigna cierta prioridad de acuerdo con su tiempo de holgura. La tarea que tiene menos tiempo de holgura tiene la mayor prioridad y viceversa.

Las prioridades a las tareas se asignan dinámicamente.

El tiempo de holgura se puede calcular usando la ecuación:

slack_time = ( D - t - e' )

Aquí D : Fecha límite de la tarea
        t : Tiempo real cuando comienza el ciclo.
        e’ : Tiempo de ejecución restante de la tarea.

La tarea que tiene el tiempo de holgura mínimo se envía a la CPU para su ejecución, ya que tiene la prioridad más alta.

Hyper Period (HP) es el período de tiempo del diagrama de Gantt que es igual al LCM de los períodos de todas las tareas en el sistema.

En el tiempo t, la holgura de una tarea es equivalente a (dt) menos el tiempo requerido para completar la parte restante de la tarea.

Es un algoritmo complejo, y por eso requiere información extra como tiempos de ejecución y plazos. El algoritmo de programación Least Slack Time funciona de manera óptima solo cuando se permite la preferencia. Puede producir un cronograma factible si y solo si existe un cronograma factible para el conjunto de tareas que se pueden ejecutar.

Es diferente de la fecha límite más temprana primero porque requiere tiempos de ejecución de la tarea que se programará. Por lo tanto, a veces no es práctico implementar el algoritmo de programación Least Slack Time porque el tiempo de ráfaga de las tareas en los sistemas en tiempo real es difícil de predecir.

A diferencia del algoritmo de programación EDF (Earliest Deadline First), LST puede subutilizar la CPU, lo que reduce la eficiencia y el rendimiento.

Si hay dos o más tareas que están listas para ejecutarse en LST, y las tareas tienen el mismo tiempo de holgura o valor de laxitud, entonces se envían al procesador de acuerdo con la base FCFS (First Come First Serve).

Ejemplo:

• En el tiempo t=0: Sólo ha llegado la tarea T1. T1 se ejecuta hasta el tiempo t=4.
• En el tiempo t=4: T2 ha llegado.
  Tiempo de holgura de T1: 33-4-6=23 Tiempo de
  holgura de T2: 28-4-3=21
  Por lo tanto, T2 comienza a ejecutarse hasta el tiempo t=5 cuando llega T3.
• En el tiempo t=5:
  Tiempo de holgura de T1: 33-5-6=22
  Tiempo de holgura de T2: 28-5-2=21
  Tiempo de holgura de T3: 29-5-10=12
  Por lo tanto, T3 comienza a ejecutarse hasta el tiempo t =13
• En el tiempo t=13:
  Tiempo de holgura de T1: 33-13-6=14
  Tiempo de holgura de T2: 28-13-2=13
  Tiempo de holgura de T3: 29-13-2=14
  Por lo tanto, T2 comienza a ejecutarse hasta el tiempo t =15
• En el tiempo t=15:
  Tiempo de holgura de T1: 33-15-6=12
  Tiempo de holgura de T3: 29-15-2=12
  Por lo tanto, T3 comienza a ejecutarse hasta el tiempo t=16
• En el tiempo t=16:
  Tiempo de holgura de T1: 33-16-6=11
  Tiempo de holgura de T3:29-16-=12
  Por lo tanto, T1 comienza a ejecutarse hasta el tiempo t=18 y así sucesivamente.