LLF(Least Laxity First) 스케줄링 알고리즘은 작은 여유시간을 가진 태스크가 높은 우선순위를 갖는 동적 우선순위 실시간 스케줄링 알고리즘이다. LLF는 단일프로세서에서 최적임이 알려져 있지만, 멀티프로세서에서는 최적의 아니다. 본 논문은 LLF를 변형한 LazyLLF(Lazy Least Laxity First) 스케줄링 알고리즘을 제시한다. 이 알고리즘은 실시간 태스크의 우선순위를 일시적으로 역전시킴으로써 프로세서의 유휴시간을 줄여 스케줄 가능성을 향상시킨다. 본 논문은 증명을 통해 LazyLLF가 LLF보다 강 우월(strictly dominate)함을 보이고, 모의실험을 통해 LazyLLF와 LLF의 스케줄 성공률을 비교한다.
LLF(Least Laxity First) is a dynamic priority scheduling algorithm that gives higher priority to an active job with less laxity. It is known that LLF is optimal on uniprocessor but not on multiprocessor. This paper presents LazyLLF(Lazy Least Laxity First) scheduling algorithm which is a modification of LLF. LazyLLF reduces processor idle time by allowing temporary priority inversion, so that it improves the schedulability of LLF. This paper proves that LazyLLF strictly dominates LLF, and compares the schedulability of LazyLLF and LLF through simulation.
