Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems

In this paper we study hard real-time systems com-posed of independent periodic preemptive tasks where we assume that tasks are scheduled by using Liu & Layland’s pioneering model following the Rate Monotonic Analy-sis (RMA). For such systems, the designer must guaran-tee that all the deadlines of all the tasks are met, other-wise dramatic consequences occur. Certainly, guarantee-ing deadlines is not always achievable because the pre-emption is approximated when using this analysis, and this approximation may lead to a wrong real-time exe-cution whereas the schedulability analysis concluded that the system was schedulable. To cope with this problem the designer usually allows margins which are difcult to assess, and thus in any case lead to a waste of resources. This paper makes multiple contributions. First, we show that, when considering the cost of the preemption during the analysis, the critical instant does not occur upon si-multaneous release of all tasks. Second, we provide a technique which counts the exact number of preemptions of each instance for all the tasks of a given system. Fi-nally, we present an RMA extension which takes into ac-count the exact cost due to preemption in the schedulabil-ity analysis rather than an approximation, thus yielding a new and stronger schedulability condition which elimi-nates the waste of resources since margins are not neces-sary.