멀티프로세서 실시간 시스템에서 스케줄 가능성을 향상시킨 변형된 LLF 스케줄링 알고리즘 = Improving the Schedulability of LLF Scheduling Algorithm in Multiprocessor Real-Time Systems

국문 초록 (Abstract)

LLF(Least Laxity First) 스케줄링 알고리즘은 작은 여유시간을 가진 태스크가 높은 우선순위를 갖는 동적 우선순위 실시간 스케줄링 알고리즘이다. LLF는 단일프로세서에서 최적임이 알려져 있지만, 멀티프로세서에서는 최적의 아니다. 본 논문은 LLF를 변형한 LazyLLF(Lazy Least Laxity First) 스케줄링 알고리즘을 제시한다. 이 알고리즘은 실시간 태스크의 우선순위를 일시적으로 역전시킴으로써 프로세서의 유휴시간을 줄여 스케줄 가능성을 향상시킨다. 본 논문은 증명을 통해 LazyLLF가 LLF보다 강 우월(strictly dominate)함을 보이고, 모의실험을 통해 LazyLLF와 LLF의 스케줄 성공률을 비교한다.

다국어 초록 (Multilingual Abstract)

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.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 시스템 모델
• 4. LazyLLF(Lazy Least Laxity First) 스케줄링 알고리즘
• 5. LazyLLF 알고리즘의 특성
• 6. 모의 실험
• 7. 결론
• 참고문헌

참고문헌 (Reference)

• 1 조성제, "산발적인 경성 실시간 태스크를 위한 온라인 스케줄링 알고리즘" 26 (26): 443-454, 1999
• 2 박민규, "다중처리기 상의 실시간 스케줄링 알고리즘의 우월 관계 및 성능" 한국정보과학회 32 (32): 368-376, 2005
• 3 오성흔, "다중 프로세서 시스템에서 문맥교환을 줄이기 위한 변형된 LLF 스케줄링 알고리즘" 한국정보과학회 30 (30): 68-77, 2003
• 4 Liu, J. W., "Real-Time Systems" Prentice Hall 70-, 2000
• 5 S. Han, "Predictability of Least Laxity First Scheduling Algorithm on Multiprocessor Real-Time Systems" 4097 : 755-764, 2006
• 6 Dertouzos, M. L., "Multiprocessor On-line Scheduling of Hard Real-Time Tasks" 15 (15): 1497-1506, 1989
• 7 J. Goossens, "Limitation of the Hyper-period in Realtime Periodic Task Set Generation" 133-148, 2001
• 8 신인식, "LLF schedulability analysis on multiprocessor platforms" IEEE 25-36, 2010
• 9 조성제, "Efficient real-time scheduling algorithms for multiprocessor systems" Oxford University Press E85-B (E85-B): 2859-2867, 200212
• 10 Leung, J., "A New Algorithm for Scheduling Periodic Real-Time Tasks" 4 : 209-219, 1989