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

This paper considers the problem of scheduling both periodic and aperi odic 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 minimiz ing the probability of missing aperiodic-task deadlines. Periodic task s are scheduled according to the rate monotonic priority algorithm (RM PA), 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 peri ods, and a task is assumed to be invoked at the beginning of a unit cy cle, For a set S of periodic tasks, the RE algorithm reserves a fracti on R(s) of processor time in each unit cycle for executing aperiodic t asks without missing any periodic-task deadline. The probability of me eting aperiodic-task deadlines is proved to be a monotonic increasing function of R(s). We derive the value of R(s) that maximizes the proce ssor time reservable for the execution of aperiodic tasks without miss ing 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 aper iodic tasks. Our analysis and simulation results show that the RE algo rithm outperforms all other scheduling algorithms in meeting aperiodic -task deadlines.