An Analysis of Deadline-Monotonic Schedulability on a Multiprocessor

This paper derives a simple sucient condition for schedulabilityofsystems of periodic or sporadic tasks in a multiprocessor preemptive xed-priorityscheduling environment. In 1973 Liu and Layland[13]showed that the optimal way of assigning priorities to periodic tasks in such a system is rate monotonic. With rate monotonic (RM) scheduling tasks are assigned priorities according to their rates, with higher prioritygoingtotasks with shorter periods. Liu and Layland showed further that there is a lower bound on the utilization at which systems of periodic tasks may miss deadlines under preemptiveRMscheduling, called the minimum achievable utilization. A set of # periodic tasks is guaranteed to to meet deadlines on a single processor under RM scheduling if the system utilization is no greater than #(2 # 1). This is a conservative but useful test for schedulabilit