하드웨어 기술이 발전하고 실시간 시스템들의 작업 부하가 커지면서 다중처리기를 실시간 시스템에 사용하는 것이 요구되고 있지만, 단일처리기와는 달리 다중처리기 실시간 스케줄링 문제는 대부분 효율적인 해결 방안이 알려져 있지 않다. 따라서 단일처리기 스케줄링 알고리즘을 다중처리기에 그대로 적용하는 연구와 단일처리기 스케줄링 알고리즘을 변형한 다중처리기 스케줄링 알고리즘에 관한 연구가 활발히 이루어지고 있다. 대표적인 알고리즘으로는 EDF(Earliest Deadline First), LLF(Least Laxity First), EDF-US[m/(2m-1)], EDZL(Earliest Deadline Zero Laxity) 알고리즘 등이 있으며, 이들 간의 비교 연구가 필요하다. 본 논문에서는 스케줄 가능성 측면에서 이 알고리즘들 사이의 우월(dominance) 관계를 밝혔다. EDF, LLF, EDF-US[m/(2m-1)] 간에는 우월 관계가 없으나, EDZL은 EDF보다 우월함을 증명하였다. 또한 모의실험을 통하여 EDZL은 선점을 적게 유발하고 처리기 이용률이 높음을 보였다.
하드웨어 기술이 발전하고 실시간 시스템들의 작업 부하가 커지면서 다중처리기를 실시간 시스템에 사용하는 것이 요구되고 있지만, 단일처리기와는 달리 다중처리기 실시간 스케줄링 문제는 대부분 효율적인 해결 방안이 알려져 있지 않다. 따라서 단일처리기 스케줄링 알고리즘을 다중처리기에 그대로 적용하는 연구와 단일처리기 스케줄링 알고리즘을 변형한 다중처리기 스케줄링 알고리즘에 관한 연구가 활발히 이루어지고 있다. 대표적인 알고리즘으로는 EDF(Earliest Deadline First), LLF(Least Laxity First), EDF-US[m/(2m-1)], EDZL(Earliest Deadline Zero Laxity) 알고리즘 등이 있으며, 이들 간의 비교 연구가 필요하다. 본 논문에서는 스케줄 가능성 측면에서 이 알고리즘들 사이의 우월(dominance) 관계를 밝혔다. EDF, LLF, EDF-US[m/(2m-1)] 간에는 우월 관계가 없으나, EDZL은 EDF보다 우월함을 증명하였다. 또한 모의실험을 통하여 EDZL은 선점을 적게 유발하고 처리기 이용률이 높음을 보였다.
Multiprocessor architecture becomes increasingly common on real-time systems as computer hardware technology rapidly progresses and the workload of real-time systems increases. However, efficient solutions for many real-time multiprocessor scheduling problems are not known. Hence many researchers ap...
Multiprocessor architecture becomes increasingly common on real-time systems as computer hardware technology rapidly progresses and the workload of real-time systems increases. However, efficient solutions for many real-time multiprocessor scheduling problems are not known. Hence many researchers apply uniprocessor scheduling algorithms to multiprocessor scheduling or devise new algorithms based on these algorithms. Such algorithms are EDF (Earliest Deadline First), LLF (Least Laxity First), EDF-US[m/(2m-1)], and EDZL (Earliest Deadline Zero Laxity), and comparative studies on them are necessary. In this paper, we show the dominance relation of these algorithms with respect to schedulability, and we prove EDZL strictly dominates EDF. The simulation results show that EDZL has high processor utilization and it causes a small number of preemptions.
Multiprocessor architecture becomes increasingly common on real-time systems as computer hardware technology rapidly progresses and the workload of real-time systems increases. However, efficient solutions for many real-time multiprocessor scheduling problems are not known. Hence many researchers apply uniprocessor scheduling algorithms to multiprocessor scheduling or devise new algorithms based on these algorithms. Such algorithms are EDF (Earliest Deadline First), LLF (Least Laxity First), EDF-US[m/(2m-1)], and EDZL (Earliest Deadline Zero Laxity), and comparative studies on them are necessary. In this paper, we show the dominance relation of these algorithms with respect to schedulability, and we prove EDZL strictly dominates EDF. The simulation results show that EDZL has high processor utilization and it causes a small number of preemptions.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문은 주기 태스크 집합에 대해서, EDF와 LLF, EDF-US[m/(2m-l)], EDZL 알고리즘 간의 우월(domi nance) 관계를 밝혔다. LLF와 EDF-US[m/(2m-l)] 알고리즘은 EDF 알고리즘보다 우월하지 않지만 EDZL 알고리즘은 EDF 알고리즘보다 우월하다.
본 실험에서는 무작위로 생성한 태스크 집합에 대하여 성능을 평가하였다. 태스크 집합은 5개의 군(群)으로 나누어 생성하였으며, 각 군은 이용률이 3, u+U인 1600개의 태스크 집합으로 구성하였다#.
본 실험의 목적은 주기와 태스크의 수를 제한했을 때 주어진 범위에서 최악의 경우를 포함한 모든 경우에 대해 성능을 비교하는 것이다. 일반적으로 무작위로 생성한 태스크 집합을 대상으로 하는 실험은 최악의 경우가 포함되지 않을 수 있으며, 또한 다중처리기 상에서는 최악의 경우를 알기 어렵다.
가설 설정
또한, 각 작업은 독립적이라고 가정한다. 즉, 각 작업은 같은 태스크에 속하거나 다른 태스크에 속한 작업과 데이타 의존성(data dependency), 선행제약(prece dence constraints) 둥을 가지지 않는다.
제안 방법
실패할 확률이 높다. EDF 기반 스케줄링 알고리즘인 EDF-US[m/(2m-l)] 알고리즘은 태스크의 이용률에 따라 우선순위 부여 방식을 다르게 함으로써 이러한 EDF의 단점을 보완하였다. EDF-US[m/(2mT)]은 이용률이 外>— 인 모든 태스크 写 의 모든작업에게 가장 높은 우선순위를 동일하게 부여하고, 이용률이 #)인 모든 태스크 弓의 모든 작업에게는 EDF 방식으로 우선순위를 부여한다.
이 범위에서 가능한 모든 태스크 집합을 생성하여 모의실험을 수행하였다. 두 개 이상의 작업이 같은 우선순위를 가질 때는 선점이 발생하지 않는 작업을우선적으로 스케줄 하였다.
즉, EDZL 알고리즘은 EDF 알고리즘이 스케줄 할 수 있는 모든 태스크 집합을 스케줄 할 수 있다. 또한 모의실험을 통하여 스케줄 가능한 태스크 집합의 비율, 스케줄 보장 이용률(schedulable utilization bound), 선점 횟수 측면에서 위의 스케줄링 알고리즘들을 비교하였다. 실험 결과, EDZL 알고리즘은 스케줄 가능한 태스크 집합과 스케줄 보장 이용률 측면에서 LLF 알고리즘에 필적하였으며, 선점 횟수는 EDF 알고리즘과 비슷하였다.
본 논문은 개의 동일한 처리기(identical processor) 상에서 주기 태스크 집합을 대상으로 하는 선점 가능 (preemptive) 경성 실시간(hard real-time) 스케줄링을 다룬다. 태스크 집합 丁 = {幻, 孩 …, 珏}은 门개의 주기 태스크로 구성되며 (口 > m), 각 태스크 昏는 (R, Ci, Di, Pi)로 표현되는데, 이는 각각 태스크의 도착 시간 (release time), 수행시간(worst-case execution time), 상대적 마감시간(relative deadline), 주기(period)를 의미한다.
본 논문은 다중처리기 상에서 스케줄 가능성 측면에서 알고리즘 간의 우월 관계, 스케줄 보장 이용률, 스케줄 가능한 태스크 집합의 비율, 선점 횟수의 관점에서 EDF, LLF, EDF-US[m/(2m-l)], EDZL 알고리즘을 비교하였다. 스케줄 가능성 측면에서 EDZL은 EDF보다 우월하였다.
본 장에서는 EDZL 알고리즘을 기술하고, 스케줄 가능성 측면에서 EDF, LLF, EDF-US[m/(2m-D], EDZL 알고리즘을 비교한다.
본 장에서는 모의실험을 통해 EDF, LLF, EDF-US [m/(2m-D], EDZL 알고리즘의 성능을 비교 및 평가한다. 실험 I 에서는 무작위로 생성한 태스크 집합을 대상으로 실험하였고 실험II에서는 일정 범위 안에서 생성 가능한 모든 태스크 집합을 대상으로 실험하였다.
각 태스크의 주기는 2~10이며 수행시간은 1~(주기T)이다. 이 범위에서 가능한 모든 태스크 집합을 생성하여 모의실험을 수행하였다. 두 개 이상의 작업이 같은 우선순위를 가질 때는 선점이 발생하지 않는 작업을우선적으로 스케줄 하였다.
대상 데이터
본 논문에서는 태스크 집합이 동기적이고, 모든 태스크들이 묵시적 마감시간을 가지는 경우를 대상으로 한다. 또한, 각 작업은 독립적이라고 가정한다.
실험 I 에서는 무작위로 생성한 태스크 집합을 대상으로 실험하였고 실험II에서는 일정 범위 안에서 생성 가능한 모든 태스크 집합을 대상으로 실험하였다.
성능/효과
이용률이다. LLF와 EDZL의 스케줄 보장 이용률은 이론적으로 알려지지 않았지만 본 실험 결과 EDF와 EDF-US[m/ (2mT)]보다 높음을 알 수 있다. EDZL의 스케줄 보장이용률은 LLF와 대등하며, 두 알고리즘 사이의 우열관계는 명확하지 않다.
문맥교환 횟수를 비교하였다[8]. 그러나 주기 태스크 스케줄링 알고리즘인 EDF-US[m/(2m~L)]과 성능을 비교하지 않았으며, 스케줄 가능한 태스크 집합의 측면과 스케줄 보장 이용률의 측면에서 EDZL이 EDF 보다 우수함을 보이지 못하였다.
즉, EDF로 스케줄 가능한 모든 태스크 집합은 EDZL로 스케줄 가능하다. 또한 무작위로 생성한 태스크 집합을 대상으로 한 모의실험 결과, EDZL의 스케줄 보장 이용률과 스케줄 가능한 태스크 집합의 비율은 EDFTJS[m/(2mT)l보다 높고 LLF와 대등하였으며, EDZL의 선점 횟수는 LLF보다 적고 EDF-US [m/(2m-D]과 거의 동일하였다 일정 범위에서 생성 가능한 모든 태스크 집합을 대상으로 한 모의실험에서도 유사한 경향을 보였다. 향후 연구과제로서 EDZL의 스케줄 가능성(feasibility) 검사를 위한 스케줄 보장 이용률, 예측가능성(predictability), 과부하에서의 특성, 자원공유를 위한 프로토콜 등에 대한 연구가 필요하다
또한 모의실험을 통하여 스케줄 가능한 태스크 집합의 비율, 스케줄 보장 이용률(schedulable utilization bound), 선점 횟수 측면에서 위의 스케줄링 알고리즘들을 비교하였다. 실험 결과, EDZL 알고리즘은 스케줄 가능한 태스크 집합과 스케줄 보장 이용률 측면에서 LLF 알고리즘에 필적하였으며, 선점 횟수는 EDF 알고리즘과 비슷하였다.
변경되므로 많은 선점이 발생한다. 실험 결과, 태스크 수가 8개일 때 LLF의 평균 선점 횟수는 EDF, EDF-US, EDZL의 평균 선점 횟수의 약 10배이다. EDF-US[m/(2m-l)]의 경우, 평균 선점 횟수가 EDF보다 다소 높다.
일정 범위 안에서 가능한 모든 태스크 집합에 대한 실험 결과가 무작위로 생성한 태스크 집합에 대한 실험 결과와 부합하므로 EDZL은 임의의 태스크 집합에 대해서도 유사한 성능을 보일 것으로 예상된다.
후속연구
또한 무작위로 생성한 태스크 집합을 대상으로 한 모의실험 결과, EDZL의 스케줄 보장 이용률과 스케줄 가능한 태스크 집합의 비율은 EDFTJS[m/(2mT)l보다 높고 LLF와 대등하였으며, EDZL의 선점 횟수는 LLF보다 적고 EDF-US [m/(2m-D]과 거의 동일하였다 일정 범위에서 생성 가능한 모든 태스크 집합을 대상으로 한 모의실험에서도 유사한 경향을 보였다. 향후 연구과제로서 EDZL의 스케줄 가능성(feasibility) 검사를 위한 스케줄 보장 이용률, 예측가능성(predictability), 과부하에서의 특성, 자원공유를 위한 프로토콜 등에 대한 연구가 필요하다
참고문헌 (10)
C. L. Liu and J. W. Layland, 'Scheduling Algorithm for Multiprogramming in Hard Real Time Environment,' Journal of ACM, Vol. 20, pp. 46-61, Jan., 1973
Liu, J. W., Real-Time Systems, p.70, Prentice Hall,2000
Dertouzos, M. L. and Mok, A. K., 'Multiprocessor On-line Scheduling of Hard Real-Time Tasks,' IEEE Trans. on Software Eng., Vol.15, No.12, pp. 1497-1506, 1989
Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., and Baruah, S., 'A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms,' In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y-T Leung (ed). Chapman Hall/ CRC Press. 2004
Srinivasan, A and Baruah, S., 'Deadline-based seheduling of Periodic Task Systems on Multiprocessors,' Information Processing Letters, Vol.84, No.2, pp. 93-98, 2002
Cho, S., Lee, S., Ahn, S., and Lin, K., 'Efficient Real-Time Scheduling Algorithms for Multiprocessor Systems,' IEICE Trans. Commun., Vol. E85-B, No.12, pp, 2859-2867, 2002
Mok, A., 'Task Management Techniques for Enforcing ED Scheduling on a Periodic Task Set,' Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems, Washington, DC, pp. 42-46. May 1988
Kalyanasundaram, B., Pruhs, K. P., and Torng, E., 'Errata: A New Algorithm for Scheduling Periodic, Real-Time Tasks,' Algorithmica, Vo1.28, pp. 269-270, 2000
※ AI-Helper는 부적절한 답변을 할 수 있습니다.