Rate Monotonic Analysis in the RMADriver Application Nate Forman EE382c Embedded Software Systems 1 Introduction For a person consequences for late task completion may include a bad grade or performance review In hard real time systems such as medical systems factory control systems and travel control systems late task completion can be far more disastrous Developers of these systems must guarantee that each task meets its deadline When a real time system adheres to rate monotonic conditions static analysis can be performed to confirm that each task meets its deadline This paper reviews rate monotonic theory and describes software that has been written to perform rate monotonic schedulability tests 2 Rate Monotonic Assumptions Rate monotonic analysis confirms schedulability for tasks in a single processor real time system with hard deadlines It assumes that each task repeats periodically and requires a fixed amount of processor execution time within that period Figure 1 shows a graphical example of the behavior of two rate monotonic tasks Reasoning with rate monotonic analysis requires the system to conform to the following assumptions 4 Task switching is instantaneous Tasks account for all processor execution time 1 Task interactions are not allowed Tasks become ready to execute precisely at the beginning of their periods and relinquish the CPU only when execution is complete Task deadlines are always at the end of the current period Tasks with shorter periods are assigned higher priorities no other criteria are considered for priority assignment Task execution is always consistent with rate monotonic priority a lower priority task never executes when a higher priority task is ready to execute The rate monotonic conditions as specified above allow static schedulability tests to be performed on task sets given each period and execution time Section 3 explains these tests in detail This set of assumptions is highly restrictive and few real systems if any actually conform to all of them Section 4 explains extensions to the assumptions and adjustments to the tests to include the extensions Section 5 describes an application that implements the extended rate monotonic analysis tests Task 1 Task 2 Time Executing Task C Task Switching Period End Beginning T Figure 1 Two tasks executing in a system under rate monotonic conditions 2 3 Schedulability Tests A rate monotonic task i has a period length Ti and an execution time Ci The processor utilization for a set of n tasks is given by the following equation 2 Ui Ci Ti The processor utilization for a set of n tasks is the sum of each individual task s utilization If the utilization for a set of tasks is over 100 that set of tasks is clearly unschedulable The asymptotic processor utilization bound for a set of n rate monotonic tasks is given by the following equation 2 1 U n n 2 n 1 As the number of tasks approaches infinity U n converges on 69 Although some runtime schedulers such as earliest deadline offer much higher utilization industry shows a strong preference for the static analysis offered by scheduling under rate monotonic conditions 4 The utilization bound test compares the processor utilization for a set of tasks with the utilization bound for that number of tasks If the utilization falls below the bound the tasks will all meet their hard deadlines under rate monotonic conditions If the utilization is above 100 the tasks are not schedulable If the utilization falls between the bound and 100 the test is inconclusive and a more precise test is required 3 For a set of independent periodic tasks if a task meets its deadline with worst case task phasing the deadline will always be met 2 The response time test compares the response time of a task with worst case task phasing to its deadline to see if the task is schedulable The response time for a task can be calculated as the least fixed point of the following recurrence a0 Cj j H i an 1 Ci j H an C Tj j In the recurrence H represents the subset of the set of tasks whose priorities are higher than the task in question i If the task s response time is less than its deadline the task is schedulable otherwise it is unschedulable 4 Extensions As mentioned above the rate monotonic assumptions are highly restrictive and few real systems if any conform to all of them The interplay between research and application has resulted in the extension of rate monotonic theory in several ways to make it more broadly applicable These extensions include Handling for aperiodic tasks Preperiod task deadlines Nonzero task switching times Interrupt handling for top priority tasks Tasks blocking each other because of shared resources This section focuses on how the schedulability tests are affected by these extensions to rate monotonic theory 4 Aperiodic tasks are handled by a process called a sporadic server Sporadic servers are assigned a period and execution budget like other rate monotonic tasks These servers operate at their rate monotonic priority and execute aperiodic tasks as needed until their execution budget is depleted The execution budget is replenished at the beginning of a period after the budget has run out Because sporadic servers operate under the original rate monotonic assumptions no adjustments need to be made to the schedulability tests For the rest of the above extensions the response time test does not change drastically Preperiod task deadlines are handled by comparing the response time to the deadline instead of the end of the period An extra term for blocking is added into each generation of the recurrence and twice the task switching delay is added into each task execution time The extended response time test is as follows a0 Bi Cj 2S an 1 Bi Ci 2S j H j H i an Cj 2S Tj In the above recurrence S is the amount of task switching time for tasks in the system and Bi is the time that task i spends blocked For detail on how tasks can block each other without inducing deadlock or unbounded priority inversion see 4 For an example of problems caused by unbounded priority inversion see 3 These extensions change the utilization bound test much more drastically First preperiod deadlines make it necessary to change the utilization bound calculation and perform it for each task separately U n i n 2 i 1 n 1 1 i 0 5 i 1 0 i i 0 5 5 i in the above equation is the ratio of the preperiod deadline of task i Di to its period length Ti Interrupt servers tasks which maintain high priority regardless