Interrupted EDF Scheduling

Steven Sommer

Technical Report C/TR96-06

Microsoft Research Institute & Department of Computing

School of MPCE

Macquarie University

NSW 2109 Australia

October 1996

1. Introduction

In this paper we extend the results for the mixed scheduling algorithm of Liu and Layland in [3]. It is the seminal paper for the basic real-time scheduling algorithms: Rate Monotonic Scheduling (RMS) and Earliest Deadline First (EDF) Scheduling, and for their corresponding schedulability tests [1,2,4,5,7]. In a final section of the paper the authors also investigate the mixed scheduling algorithm which is a combination of both EDF and RMS. Their motivation for looking at this combined algorithm is the observation that conventional interrupt hardware behaves in a fixed priority manner and does not appear compatible with a hardware EDF scheduler. On the other hand the overhead in implementing EDF in software for the slower paced tasks would not be great.

The necessary and sufficient scheduling test given in [3] for n tasks scheduled using the mixed scheduler algorithm has a worst case complexity which is unbounded in n (as discussed in section 5).

In our Dreams system [6] the scheduled tasks are scheduled using EDF, yet the interrupts and the scheduler itself, whilst periodic in nature, cause themselves to be immediately scheduled. Given this environment we endeavoured to find a sufficient, and as close to necessary as possible, computationally realistic schedulability test for determining if a task set could be run. Liu?s exact test was not satisfactory due to its computational complexity.

In this paper we offer a simple O(n) test (for n tasks) which is sufficient for all task sets and which provides a tight lower bound for a constructed task set. We calculate the bound on the additional utilisation available for specific task sets that could be scheduled, but for which the test fails. We also remove Liu?s assumption that the periods of the tasks which interrupt are shorter than the periods of the tasks which are EDF scheduled. Our schedulability test is analogous to Liu?s RMS scheduling bound of ln(2), the most cited result in real-time literature.

In our environment there are two types of real-time tasks: interrupt tasks and scheduled tasks. Both of these have a period, denoted Tj for task j, and a maximum computation time required during each period, denoted Cj. Scheduled tasks will be scheduled using the EDF algorithm in which the runnable task with the earliest deadline is allocated the processor (the deadline is assumed to be at the end of the period). Interrupt tasks may steal the processor at the beginning of their period by causing themselves to be immediately scheduled. An interrupt can start while another interrupt is running, in which case it may be queued or it may preempt. Queued and preempted interrupts will run before any real-time task. There is no assumption that the interrupt tasks are scheduled in a RMS fashion or that the periods of the interrupt tasks are less than that of the real-time tasks. Interrupt tasks do not have deadlines.