상세정보
학술대회
An Optimal Real-Time Scheduling Algorithm for Multiprocessors
- 저자
- 조현중, Binoy Ravindran, E. Douglas Jensen
- 발행일
- 200612
- 출처
- International Real-Time Systems Symposium (RTSS) 2006, pp.101-110
- 협약과제
- 06MD1500, RFID/USN용 센서 태그 및 센서 노드 기술 개발, 표철식
- 초록
- We present an optimal real-time scheduling algorithm for multiprocessors - one that satisfies all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. The algorithm called LLREF, is designed based on a novel abstraction for reasoning about task execution behavior on multiprocessors: the Time and Local Execution Time Domain Plane (or T-L plane). LLREF is based on the fluid scheduling model and the fairness notion, and uses the T-L plane to describe fluid schedules without using time quanta, unlike the optimal Pfair algorithm (which uses time quanta). We show that scheduling for multiprocessors can be viewed as repeatedly occurring T-L planes, and feasibly scheduling on a single T-L plane results in the optimal schedule. We analytically establish the optimality of LLREF. Further, we establish that the algorithm has bounded overhead, and this bound is independent of time quanta (unlike Pfair). Our simulation results validate our analysis on the algorithm overhead. © 2006 IEEE.
- KSP 제안 키워드
- Local execution, Optimal real-time scheduling, Scheduling algorithm, Scheduling model, execution time, optimal schedule, simulation results, task execution, time-domain