A RESERVATION-BASED ALGORITHM FOR SCHEDULING BOTH PERIODIC AND APERIODIC REAL-TIME TASKS

被引:12
作者
SHIN, KG [1 ]
CHANG, YC [1 ]
机构
[1] QUICKTURN DESIGN SYST INC,MT VIEW,CA
基金
美国国家科学基金会;
关键词
REAL-TIME SYSTEMS; TASK SCHEDULING; PERIODIC AND APERIODIC TASKS; DEADLINE GUARANTEES;
D O I
10.1109/12.477246
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
This paper considers the problem of scheduling both periodic and aperiodic tasks in real-time systems, A new, called reservation-based (RE), algorithm is proposed for ordering the execution of real-time tasks, This algorithm can guarantee all periodic-task deadlines while minimizing the probability of missing aperiodic-task deadlines. Periodic tasks are scheduled according to the rate monotonic priority algorithm (RMPA), and aperiodic tasks are scheduled by utilizing the processor time left unused by periodic tasks in each unit cycle, The length, u, of a unit cycle is defined as the greatest common divisor of all task periods, and a task is assumed to be invoked at the beginning of a unit cycle, For a set S of periodic tasks, the RE algorithm reserves a fraction R(s) of processor time in each unit cycle for executing aperiodic tasks without missing any periodic-task deadline. The probability of meeting aperiodic-task deadlines is proved to be a monotonic increasing function of R(s). We derive the value of R(s) that maximizes the processor time reservable for the execution of aperiodic tasks without missing any periodic-task deadline, We also show that if the ratio of the computation time to the deadline of each aperiodic task is bounded by R(s), the RE algorithm can meet the deadlines of all periodic and aperiodic tasks. Our analysis and simulation results show that the RE algorithm outperforms all other scheduling algorithms in meeting aperiodic-task deadlines.
引用
收藏
页码:1405 / 1419
页数:15
相关论文
共 19 条
[11]   SCHEDULING ALGORITHMS FOR MULTIPROGRAMMING IN A HARD-REAL-TIME ENVIRONMENT [J].
LIU, CL ;
LAYLAND, JW .
JOURNAL OF THE ACM, 1973, 20 (01) :46-61
[12]  
Mok A. K., 1983, THESIS MIT
[13]   DISTRIBUTED SCHEDULING OF TASKS WITH DEADLINES AND RESOURCE REQUIREMENTS [J].
RAMAMRITHAM, K ;
STANKOVIC, JA ;
ZHAO, W .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (08) :1110-1123
[14]   UNIFIED METHOD FOR EVALUATING REAL-TIME COMPUTER CONTROLLERS AND ITS APPLICATION. [J].
Shin, Kang G. ;
Krishna, C.M. ;
Lee, Yann-Hang .
IEEE Transactions on Automatic Control, 1985, AC-30 (04) :357-366
[15]   LOAD SHARING IN DISTRIBUTED REAL-TIME SYSTEMS WITH STATE-CHANGE BROADCASTS [J].
SHIN, KG ;
CHANG, YC .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (08) :1124-1142
[16]  
SPRUNT B, 1988, 9TH P REAL TIM SYST, P251
[17]   EVALUATION OF A FLEXIBLE TASK-SCHEDULING ALGORITHM FOR DISTRIBUTED HARD REAL-TIME SYSTEMS [J].
STANKOVIC, JA ;
RAMAMRITHAM, K ;
CHENG, SC .
IEEE TRANSACTIONS ON COMPUTERS, 1985, 34 (12) :1130-1143
[18]  
WOODBURY MH, 1988, 9TH P REAL TIM SYST, P222
[19]  
ZHU J, 1993, 936016 OR STAT U COM