Controlling preemption for better schedulability in multi-core systems

Interest in real-time multiprocessor scheduling has been rekindled as multi-core chips are increasingly used for embedded real-time systems. While tasks may be preemptive or non-preemptive (due to their transactional operations), deadline guarantees are usually made only for those task sets in each of which all tasks are preemptive or non-preemptive, not a mixture thereof, i.e., all or nothing. In this paper, we develop a schedulability analysis framework that guarantees the timing requirements of a given task set in which a task can be either preemptive or non-preemptive. As an example, we apply this framework to the prioritization policy of EDF (Earliest Deadline First), yielding schedulability tests of mpn-EDF (Mixed Preemptive/Non-preemptive EDF), which is a generalization of both fp-EDF (fully-preemptive EDF) and np-EDF (non-preemptive EDF). In addition to their deadline guarantees for any task set that is composed of a mixture of preemptive and non-preemptive tasks, the tests outperform the existing schedulability tests of np-EDF (a special case of mpn-EDF) by up to 109.1%. Using these tests, we also improve schedulability by disallowing preemptions of some preemptive tasks. For this, we develop an algorithm that optimally disallows preemption of a preemptive task under a certain assumption, and demonstrate via simulation that the algorithm discovers up to 30.9% additional task sets that are schedulable with the proposed scheduling scheme, but not with fp-EDF or np-EDF.