Timing Analysis of Real-Time Scheduling Policies : A Trajectory Based Model

Timing analysis of real time scheduling policies is concerned with the analysis of response times, because real-time constraints impose that tasks must complete before their deadlines. For the well studied earliest deadline first (EDF) and the fixed priority preemptive (FPP) policy, results are known under various assumptions about tasks. In this report we propose a mathematical model based on trajectories to represent and analyze the scheduling of recurrent tasks on one processor. We identify generic ideas and concepts such as majorizing work arrival functions, which allows to study scheduling policies separately from assumptions on tasks. We develop in particular a common approach for deriving response times bounds under policies that can be defined by priorities which are assigned to instances of tasks. Not only FPP and EDF but also the classical first in first out or the last in first out policies fall in this category. By developing the model as general framework for timing analysis we have also obtained some extensions of existing results about EDF and FPP.