혼합 우선순위 시스템에서 경성 비주기적 태스크 스케쥴링 알고리즘 = A hard-Aperiodic Task Scheduling Algorithm in Hybrid Priority Systems

국문 초록 (Abstract)

본 논문은 주기적 태스크와 경성 비주기적 태스크가 혼합된 단일 처리기 실시간 시스템 에서 중단형 (preemptive) 경성 비주기적 태스크의 스케쥴링 기법인 자유지역 지시 (Free Region Indicating. FRI) 알고리즘을 제안한다. FRI 알고리즘은 온라인에서 경성 비주기적 태스크에 대하여 할당여부를 판단하며, 주기적 태스크와 비주기적 태스크들에 대하여 고정 우선순위와 가변 우선순위를 혼합한 스케쥴링 기법으로 저자가 개발한 임계 태스크 지시 (Critical Task Indicating: CTI) 알고리즘 [4] 을 확장한 것이다. CTI 알고리즘은 연성 비주기적 태스크 스케쥴링 알고리즘으로, 모의 실험 연구에 의하면 slack stealing 알고리즘 [6] 보다 성능 개선을 이루었으며 특히 시스템 과부하 시에도 잘 작동하였다.FRI 알고리즘은 모든 주기적 태스크의 마감시간을 보장할 뿐 아니라 오프라인에서 작성된 CTI 테이블과 스케쥴링 변동 사항에 대한 정보를 가지고 있는 FRI 테이블을 사용하므로써 알고리즘 수행시간 복잡도를 감소시켰으며 스케쥴링 예측성도 높였다.

다국어 초록 (Multilingual Abstract)

In this paper, we present a preemptive scheduling of hard-aperiodic task. so called the Free Region Indicating (FRI) algorithm. in jointly scheduling the periodic tasks and hard-aperiodic tasks on a uniprocessor real-time system in which hard deadlines of periodic and aperiodic tasks are scheduled in such a way of mixed scheduling of a fixed and dynamic priority algorithm. The algorithm executes an on-line acceptance test for the hard aperiodic tasks and it has extended the Critical Task Indicator (CTI) algorithm [4]of which simulation study shows a considerable performance improvement over the other soft-aperiodic task scheduling algorithms. such a slack-stealing algorithm [6], especially under a heavy transient overload. The FRI algorithm is not only to guarantee all the deadline of periodic tasks. but also to reduce time complexity and improve scheduling predictability since it maintains both the CTI and FRI tables which have scheduling informations and built off-line.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. CTI 알고리즘
• 3. 경성 비주기적 태스크 스케쥴링 알고리즘
• 4. 결론 및 앞으로의 연구 방향
• 참고문헌