La programación de menor tiempo de holgura ( LST ) es un algoritmo para la programación de prioridades dinámicas . Asigna prioridades a los procesos en función de su tiempo de holgura . El tiempo de holgura es la cantidad de tiempo restante después de un trabajo si el trabajo se inició ahora. Este algoritmo también se conoce como el de menor laxitud primero . Su uso más común es en sistemas integrados , especialmente aquellos con múltiples procesadores. Impone la simple restricción de que cada proceso en cada procesador disponible posee el mismo tiempo de ejecución y que los procesos individuales no tienen afinidad con un procesador determinado. Esto es lo que le confiere una idoneidad para sistemas integrados.
Este algoritmo de programación selecciona primero aquellos procesos que tienen el menor "tiempo de holgura". El tiempo de holgura se define como la diferencia temporal entre la fecha límite, el tiempo de preparación y el tiempo de ejecución.
De manera más formal, el tiempo de holgura de un proceso se define como:
donde es la fecha límite del proceso, es el tiempo real desde el inicio del ciclo y es el tiempo de cálculo restante.
En los algoritmos de programación en tiempo real para trabajos periódicos, se necesita una prueba de aceptación antes de aceptar un trabajo esporádico con una fecha límite estricta. Una de las pruebas de aceptación más simples para un trabajo esporádico es calcular la cantidad de tiempo de inactividad entre el momento de lanzamiento y la fecha límite del trabajo.
La programación LST es más útil en sistemas que comprenden principalmente tareas aperiódicas, porque no se hacen suposiciones previas sobre la tasa de ocurrencia de los eventos. La principal debilidad de LST es que no mira hacia el futuro y solo funciona en el estado actual del sistema. Por lo tanto, durante una breve sobrecarga de los recursos del sistema, LST puede ser subóptima. También será subóptima cuando se use con procesos ininterrumpibles. Sin embargo, al igual que earliest deadline first , y a diferencia de la programación monotónica de tasa , este algoritmo se puede usar para una utilización del procesador de hasta el 100%.
