선점 가능한 실시간 태스크들의 동적인 스케쥴링을 위한 최적 알고리즘 = An Optimal Algorithm for Dynamic Scheduling of Preemptable Real - Time Tasks

국문 초록 (Abstract)

실시간 시스템에서 태스크들은 올바른 응답을 해야함과 동시에 각각 제한된 시간 내에 주어진 작업을 완료해야하는 요구 조건을 만족해야한다. 본 논문에서는 실시간 시스템에서, 선점 가능하며 (preemptable), 생성 시간 (creation time), 수행 준비 완료 시간 (ready time)과 수행 종료 시한 (deadline), 및 수행 소요 시간 (execution time)을 임의로 갖는 태스크들을 동적으로 스케쥴링하기 위한 최적 알고리즘을 제시하였다. 총 n 개의 태스크들을 스케쥴링하는 경우에 시간 복잡도를 기존에는 O(n² log n) 이었던 데 비해 이 알고리즘은 O(n log n)으로 향상 시켰다. 또한, O(n log n)이 그 하한선임도 보여 주었다. 각 태스크의 예상 소요 시간은 최악의 경우의 예상 소요 시간이므로 항상 실제 소요 시간보다 크게 주어진다. 이 알고리즘에서는 각 태스크에 대해 실제 수행 기회가 왔을 때 수용 또는 거부 여부를 결정하므로 예상 소요 시간에 의하면 거부될 태스크들도 수용될 수 있는 기능성이 많게되고 따라서, 가능한 한 많은 태스크들을 수용할 수 있게 된다.

다국어 초록 (Multilingual Abstract)

In real-time systems, each task has to be executed not only correctly but also in a timely fashion. In this paper, an optimal algorithm is presented for dynamic scheduling of preemptable real-time tasks where tasks are dynamically created and each task has arbitrary creation time, ready time, execution time, and deadline. The time complexity of the algorithm is O(n log n) for n tasks which improves the previous result of O(n² log n). It is also shown that the time complexity of the algorithm, O(n log n), is the lower bound. Since the execution time of each task is the expected time of the worst case, it is longer than the actual execution time. Therefore, the presented algorithm may accept tasks which should be rejected if we use expected time only.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 동적인 스케쥴링 알고리즘
• 3. 알고리즘의 분석
• 4. 결론
• 참고문헌
• 저자소개