LIMITED PREEMPTIVE SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 256

To better understand the different limited preemptive approaches, the task set reported
in Table 8.1 will be used as a common example throughout this chapter.

C i T i D i

τ 1 1 6 4

τ 2 3 10 8

τ 3 6 18 12

Table 8.1 Parameters of a sample task set with relative deadlines less than periods.

Figure 8.3 illustrates the schedule produced by Deadline Monotonic (in fully preemp-
tive mode) on the task set of Table 8.1. Notice that the task set is not schedulable,
since task τ 3 misses its deadline.

1

τ 1

3

τ 2

deadline miss

6

τ 3

0 2 4 6 8 10 12 14 16 18 20

Figure 8.3 Schedule produced by Deadline Monotonic (in fully preemptive mode) on the
task set of Table 8.1.

8.1.1 TERMINOLOGY AND NOTATION

Throughout this chapter, a set of n periodic or sporadic real-time tasks will be consid-
ered to be scheduled on a single processor. Each task τ i is characterized by a worst-
case execution time (WCET) C i , a relative deadline D i , and a period (or minimum
inter-arrival time) T i . A constrained deadline model is adopted, so D i is assumed to
be less than or equal to T i . For scheduling purposes, each task is assigned a fixed
priority P i , used to select the running task among those tasks ready to execute. A
higher value of P i corresponds to a higher priority. Note that task activation times
are not known a priori and the actual execution time of a task can be less than or
equal to its worst-case value C i . Tasks are indexed by decreasing priority, that is,

∀ i | 1 ≤ i<n : P i >P i +1 . Additional terminology will be introduced below for

each specific method.