ETRI-Knowledge Sharing Plaform



논문 검색
구분 SCI
연도 ~ 키워드


학술대회 An Optimal Real-Time Scheduling Algorithm for Multiprocessors
Cited 171 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
조현중, Binoy Ravindran, E. Douglas Jensen
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