A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling.
Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.
INTRODUCTION
Hard real-time systems have been defined as those containing processes that have
deadlines that cannot be missed [Bur89a]. Such deadlines have been termed hard: they
must be met under all circumstances otherwise catastrophic system failure may result
To meet hard deadlines implies constraints upon the way in which system resources
are allocated at runtime. This includes both physical and logical resources.
Conventionally, resource allocation is performed by scheduling algorithms whose purpose
is to interleave the executions of processes in the system to achieve a pre-determined goal.
For hard real-time systems the obvious goal is that no deadline is missed.
One scheduling method that has been proposed for hard real-time systems is the rate
monotonic algorithm [Liu73a]. This is a static priority based algorithm for periodic
processes in which the priority of a process is related to its period. Whilst this algorithm
has several useful properties, including a schedulability test that is sufficient and necessary
[Leh89a], the constraints that it imposes on the process system are severe: processes must
be periodic, independent and have deadline equal to period.
Many papers have successively weakened the constraints imposed by the rate-monotonic
algorithm and have provided associated schedulability tests. Reported work
includes a test to allow aperiodic processes to be scheduled [Sha89a], and a test to
schedule processes that synchronise using semaphores [Sha88a]. One constraint that has
remained is that the deadline and period of a process must be equal.
The weakening of this latter constraint would benefit the application designer by
providing a more flexible process model for implementing the system. The increased
flexibility is seen by observation: processes with deadline = period are expressible within a
process model permitting deadline - period . For example, process systems whose timing
characteristics are suitable for rate-monotonic scheduling would also be accepted by a
scheduling scheme permitting deadlines and periods of a process to differ.
This paper relaxes this constraint and so transforms the rate-monotonic algorithm into
the deadline-monotonic algorithm. Schedulability tests are developed which guarantee the
deadlines of periodic processes. This approach is then shown to be applicable for
guaranteeing the deadlines for arbitrary mixtures of periodic and sporadic processes.
The following sub-section gives a brief description of the symbols and terminology
used in the remainder of the paper. Section 2 gives an overview of the rate-monotonic
scheduling algorithm and associated schedulability tests. Section 3 introduces the
deadline-monotonic scheduling algorithm. New schedulability constraints for the algorithm
are developed. Section 4 outlines some previously proposed methods of guaranteeing
sporadic process deadlines within the context of the rate-monotonic algorithm. The
section then proposes a simpler method guaranteeing the deadlines of arbitrary mixtures of
sporadic and periodic processes using the deadline-monotonic scheduling algorithm.
1.1. Notation
A process is periodic if it is released for execution in a periodic manner. When this is
not the case, and a maximum release frequency can be defined, the process is termed
sporadic. If no such maximum can be defined the process is termed aperiodic [Aud90a].
A process is given by t i , where i identifies the process. The subscript i is defined to
be the priority of that process, where priorities are unique. Priorities are assigned
numerically, taken from the interval #
# where 1 is the highest priority and n (the
number of processes in the system) the lowest.
The process t i has timing characteristics T i , C i and D i . These refer to the value of the
period, computation time and deadline of t i .
2. THE RATE-MONOTONIC SCHEDULING ALGORITHM
Rate-monotonic scheduling is a static priority based mechanism [Liu73a]. Priorities
assigned to processes are inversely proportional to the length of the period. That is, the
process with the shortest period is assigned the highest priority. Processes are executed in
preemptive manner: at any time, the highest priority process with outstanding computation
requirement is executed.
Amongst the class of static priority scheduling schemes, it has been shown that rate-monotonic
priority assignment is optimal [Liu73a]. This implies that if a given static
priority scheduling algorithm can schedule a process system, the rate-monotonic algorithm
is also able to schedule that process system. In the case of the rate-monotonic scheduling
algorithm, optimality implies the imposition of constraints upon the process system. These
include:
# fixed set of processes;
all processes are periodic;
# all processes have deadline equal to period;
# one instance of a process must be complete before subsequent instances are run;
# all processes have known worst-case execution times;
no synchronisation is permitted between processes;
# all processes have an initial release at time 0.
The last of these constraints is fundamental in determining the schedulability of a
given process system. When all processes are released simultaneously, we have the worst-case
demand for the processor. The times at which all processes are released
simultaneously are termed critical instants[Liu73a] (thus the first critical instant occurs at
time 0). This leads to the observation that if all processes can meet their deadline in the
executions starting at the critical instant, then all process deadlines will be met during the
lifetime of the system.
Schedulability tests for the rate-monotonic algorithm are based upon the critical
instant concept. In [Liu73a] the concept is developed into a schedulability test based upon
process utilisations +. The test is given by:
(1)
where the utilisation U i of process t i is given by:
The utilisation converges on 69% for large n . Thus if a process set has utilisation of
less than 69% it is guaranteed to be scheduled by the rate-monotonic algorithm. That is,
all deadlines are guaranteed to be met.
Whilst test (1) is sufficient, it is also not necessary. That is, the test may indicate
falsely that a process system is not schedulable. For example, consider two processes with
the following periods and computational requirements:
For these processes, equation (1) evaluates to false, as the utilisation of two processes is
100%, greater than the allowable bound of 83%. However, when run, neither process will
ever miss a deadline. Hence, the test is sufficient but not necessary.
A necessary and sufficient schedulability constraint has been found [Sha88a,
Leh89a]. For a set of n processes, the schedulability test is given by ++:
min
l T k
l T k
where
The equations take into account all possible process phasings.
2.1.

Summary

In summary, schedulability tests are available for an optimal static priority scheduling
scheme, the rate-monotonic scheduling algorithm, with processes limited by the following
fundamental constraints:
all processes are periodic;
Utilisation is a measure of the ratio of required computation time to period of a process. The
summation of these ratios over all processes yields the total processor utilisation.
# evaluates to the smallest integer - x
# evaluates to the largest integer - x
# all processes have period equal to deadline;
no synchronisation is permitted between processes.
The first schedulability test (equation (1)) is sufficient and not necessary; the second
test (equation (2)) is sufficient and necessary. One difference between the two
schedulability tests lies in their computational complexities. The first test is of O (n ) in the
number of processes. The second test is far more complicated: its complexity is data
dependent. This is because the number of calculations required is entirely dependent on
the values of the process periods. In the worst-case, the test can involve enumeration of the
schedule for each process in the system, upto the period of that process. Hence, a trade-off
exists between accuracy and computational complexity for these schedulability tests.
The following section removes the second of the three constraints (i.e.
allows processes to be sporadic thus relaxing the first of
the above constraints. The third constraint is beyond the scope of this paper but as was
noted earlier, Sha et al have considered this [Sha88a, Sha90a, Sha87a].
3. DEADLINE MONOTONIC SCHEDULING
We begin by observing that the processes we wish to schedule are characterised by
the following relationship:
computation time - deadline - period
Leung et al[Leu82a] have defined a priority assignment scheme that caters for
processes with the above relationship. This is termed inverse-deadline or deadline
monotonic priority assignment.
Deadline monotonic priority ordering is similar in concept to rate monotonic priority
ordering. Priorities assigned to processes are inversely proportional to the length of the
deadline [Leu82a]. Thus, the process with the shortest deadline is assigned the highest
priority, the longest deadline process the lowest priority. This priority ordering defaults to
a rate monotonic ordering when period =deadline .
Deadline monotonic priority assignment is an optimal static priority scheme for
processes that share a critical instant. This is stated as Theorem 2.4 in [Leu82a]:
"The inverse-deadline priority assignment is an optimal priority assignment for
one processor."
To generate a schedulability constraint for deadline monotonic scheduling the behaviour of
processes released at a critical instant is fundamental: if all processes are proved to meet
their deadlines during executions beginning at a critical instant these processes will always
their deadlines [Liu73a, Leu82a].
Using the results of Leung et al stated above as a foundation, new schedulability tests
are now developed. Initially, two processes are considered, then we generalise to allow any
number of processes.
3.1. Schedulability Of Two Processes
Consider two processes: t 1 and t 2 . Process t 1 has a higher priority than process t 2
and so by deadline monotonic priority assignment,
Consider the following case.
Case (i) : both processes are always released simultaneously.
This occurs if the following holds:
This is illustrated in Figure 1.
time
time

Figure

1.
has the highest priority, it claims the processor whenever it has an
outstanding computational requirement. This will occur for the first C 1 units of each
period T 1 . The schedulability of this system is given by:
(a) check schedulability of
the deadline must be sufficiently large to contain the computation demand,
i.e.
(b) check schedulability of
all higher priority processes (i.e. t 1 ) have prior claim on the processor.
Hence, in any interval #
can utilise the processor in the
interval #
# . Therefore, t 2 can have a maximum
computation time defined by:
that is t 2 is schedulable if
The second term of equation (3) relates to the maximum time that t 2 is prevented from
executing by higher priority processes, in this case t 1 . This time is termed the interference
time, I.
Definition 1: I i is the interference that is encountered by t i between the release
and deadline of any instance of t i . The interference is due to the execution
demands of higher priority processes. The maximum interference on process t i
occurs during a release of t i beginning at a critical instant (by definition of critical
instant [Liu73a] ).
Considering the processes in Case (i), I 2 equates to the time that t 1 executes whilst t 2 has
outstanding computational requirement. Thus I 2 is equal to one computation of t 1 . That is:
I
In Case (i) I 1 is zero, as t 1 is the highest priority process:
I
The schedulability for Case (i) can be restated:
"i
I i
where
I
I
We now consider cases where the periods of the two processes are not equal.
Case is released many times before the second release of t 1
time
time

Figure

2.
In

Figure

2, the maximum interference I 2 is equal to one computation time of t 1 . The
schedulability equations (4) will hold for this case.
Case is released many times before the second release of t 2
Consider Figure 3.
time
time

Figure

3.
Clearly, t 2 is prevented from running by releases of process t 1 . The number of
releases of t 1 within the interval #
# is given by:
Therefore, schedulability is expressed by:
"i
I i
where
I
I
In equation (5), the value of I 2 above could be larger than the exact maximum
interference. This is because I 2 includes computation time required by t 1 for its (i
release, some of which may occur after the value of I 2 is at least as great
as the maximum interference, the test must hold since the it is based upon the exact
maximum interference.
An example using schedulability equation (5) is now given.
Example
Consider the following process system.
The schedulability of the process system can be determined by equation (5).
(a) check process t 1
I 1
Hence t 1 is schedulable.
(b) check process t 2
I 2
I 2
where
I
substituting6
Hence t 2 is schedulable. An example run of the system is given in Figure
4+.

Figure

4.
The construction of I 2 is sufficient but not necessary as the following example shows.
Consider the effect of increasing D 2 to 11. This should not affect the schedulability of the
system.
(c) recheck process t 2
I 2
I 2
where
I
substituting6
Hence t 2 is now unschedulable by equation (5). However, the process
system is schedulable (Figure 4 above).
Simulation diagrams are discussed in Appendix 1.
The schedulability constraint in equation (5) is too strong due to the value of I 2 . An
exact expression for I 2 is now developed. Consider Figure 5.
time
time

Figure

5.
A critical instant has occurred (iT with the interference on t 2 a maximum. We note
that the interference consists of executions of t 1 that have deadlines before D 2 , and the
execution of t 1 that has a release before D 2 and a deadline after D 2 . We can restate I 2 as
I
where b represents the interference due to complete executions of t 1 and k the incomplete
executions.
The number of complete executions in the interval #
# is equal to the
number of deadlines t 1 has in this interval. The number is given by:
Hence, the interference due to complete executions is given by:
The number of incomplete executions of t 1 is given by the number of releases of t 1
minus the number of deadlines of t 1 in #
# . This evaluates to either 0 or 1. The
number of releases is given by:
Note that if a release of t 1 coincides with D 2 , then it is deemed to occur fractionally after
. Hence the number of incomplete executions in #
# is given by:
The start of the incomplete execution is given by:
Hence, the length of the interval utilised by the incomplete execution before D 2 is:
The maximum time t 1 can use during the interval is given by the length of the
interval. However, the interval may be longer than C 1 . Therefore the maximum
interference due to incomplete executions is given by:
Substituting b and k into equation (6) gives the following schedulability constraint:
"i
I i
where
I
I
Consider the following theorems which relate to the sufficient and necessary properties of
equation (7).
Theorem 1: the schedulability test given in equation (7) is sufficient for two
processes.
The proof is by contradiction. We assume there is a process system that passes
the test but is not schedulable and show that if the system is not schedulable
then it must fail the test.
Consider a process system containing t 1 and t 2 . Let process t 1 pass the test.
pass the test, but not be schedulable. To pass the test, the following
must hold:
For t 2 not to be schedulable, it must miss its deadline during an instance of the
process starting at the critical instant of all processes. At this point t 2 suffers its
maximum interference, I 2 , due to the higher priority process. Therefore for t 2 to
miss its deadline and not be schedulable we have:
This gives
I 2
A clear contradiction exists between (a) and (b). Therefore, if t 2 passes the test,
it is schedulable.
The proof for Theorem 1 relies upon I 2 being exact (this is given by Theorem 2).
Theorem 1 will still hold if I 2 is greater than the exact value. This merely represents a
worse than worse-case. Therefore, by implication of Theorem 1, the schedulability test
given by equation (5) is also sufficient.
Theorem 2: the schedulability test is necessary if values of I i are exact.
For process t 2 to pass the schedulability test requires:
I - 2
where I - 2 represents the exact value of I 2 . When comparing I - 2 and I 2 we have
three cases:
(i) I - 2 > I 2 - this is clearly impossible as we know that I 2 is at least I - 2 from the
above discussion.
occurs when we have made a pessimistic calculation for I 2 .
As I 2 increases, the computation time that could be guaranteed for t 2 decreases
since:
occurs when the calculation of I 2 is precise. The allowable
computation time for t 2 is maximised (by above inequality).
In summary, we have the greatest amount of time for t 2 if I 2 is exact. There-
fore, the schedulability test is necessary if I 2 is exact.
Therefore, the schedulability test given by equation (7) is necessary as the values for
I i are exact. By implication, the schedulability test given by equation (5) is also necessary
if I i is exact. However, I i values in equation (7) are exact in more instances than in
equation (5): the former will declare more process systems schedulable than the latter.
The following example illustrates this point.
Example
We return to the process system that failed equation (5) but was illustrated to meet all
deadlines.
The schedulability of the system can be determined by equation (7).
(a) check process
I 1
Hence t 1 is schedulable.
(b) check process t 2
I 2
I 2
where
I
##
I
substituting,6
Hence t 2 is schedulable.
The system is schedulable by equation (7). A simulated run of the system was given in

Figure

previously.
3.1.1.

Summary

Noting the results stated in [Leu82a] that deadline monotonic priority assignment is
optimal, two schedulability tests for two-process systems have been developed. The test in
equation (5) is sufficient but not necessary, whilst the test in equation (7) is sufficient and
necessary (and hence optimal).
One difference between the tests is that the former is of computational complexity
O #
# and the latter O #
# . A trade-off again exists between accuracy and computational
complexity.
3.2. Schedulability Of Many Processes
The schedulability test given by equations (5) and (7) are now generalised for
systems with arbitrary numbers of processes. Firstly, equation (5) is expanded. Consider

Figure

6.
time
time
time

Figure

6.
The interference I i that is inflicted upon process t i by all higher priority processes
corresponds to the computation demands by those processes in the interval of time from
the critical instant to the first deadline of t i .
The interference on t i by t j can be given by:
This may include part of an execution of t j that occurs after D i . The total interference on
t i can be expressed by:
I
Therefore to feasibly schedule all processes:
"i
I i
where
I
Equation (8), like equation (5), is sufficient but not necessary. This is illustrated by the
following example.
Example
Consider the following process system.
The schedulability of the process system can be determined by equation (8).
(a) check process t 1
I 1
Hence t 1 is schedulable.
(b) check process t 2
I 2
I 2
where
I
substituting2
Hence t 2 is schedulable.
(c) check process t 3
I 3
I 3
where
I
I
substituting4
Hence t 3 is schedulable.
Consider the effect of increasing D 3 to 11. This should not affect the schedulability of the
system.
(d) recheck process t 3
where
I
I
substituting4
Hence t 3 is unschedulable by equation (8).
The process system is unschedulable by equation (8). However, when the system is
run all deadlines are met (see Figure 7).

Figure

7.
In the above example, the process system is not schedulable by equation (8) because the
values of I i are greater than exact values. Each I i can contain parts of executions that
occur after D i . This is similar to the drawback of equation (5) when a two-process system
was being considered. To surmount this problem we generalise equation (7) for many
processes. Consider Figure 8.
time
time
time
time

Figure

8.
From

Figure

8, it can be seen that in the general case with n processes, I i is equal to the
interference of all the processes t 1 to t i-1 in the interval #
# . Thus, equation (7)
can be rewritten to provide a schedulability test for an n process system:
"i
I i
where
I
To show that the above constraint is more accurate than equation (8) consider the
following example.
Example
We return to the process system that failed equation (8) but was shown to meet all
deadlines (see Figure 7).
(a) check process t 1
Hence t 1 is schedulable.
(b) check process t 2
I 2
I 2
where
I
I
##
substituting2
Hence t 2 is schedulable.
(c) check process t 3
I 3
I 3
where
I
I
##
##
I
substituting3
Hence t 3 is schedulable. An example run was given in Figure 7.
The expression for I i in equation (9) is not exact. This is because the interference on t i due
to incomplete executions of t 1 to t i-1 given by (9) is greater than or equal to the exact
interference. Consider the interference on t i by incomplete executions of t 1 and t i-1

Figure

8). Within I i , allowance is made for t 1 using all of #
# , and for t i-1
using all of #
# . Since only one of these processes can execute at a time, I i is
greater than a precise value for the interference.
Consider the following theorems.
Theorem 3: the schedulability test given by equation (9) is sufficient.
The proof follows from Theorem (1).
Theorem 4: the schedulability test given by equation (9) is necessary if values
of I i are exact.
The proof follows from Theorem (2).
Theorems (3) and (4) show that both equations (9) and (8) (by implication) are
sufficient and not necessary. When no executions of higher priority processes overlap the
deadline of t i then I i will be exact with both tests (8) and being necessary. Indeed, if
the I i values in both equations (8) and are exact, the two equations are equivalent.
However, when executions do overlap the deadline of t i test (9) will pass more process
systems than test (8) as it contains a more precise measurement of I i .
To obtain an exact value for I i under all cases requires the exact interleaving of all
higher priority processes to be considered upto the deadline D i . This could involve the
enumeration of the schedule upto D i with obvious computational expense. The following
section outlines an alternative strategy for improving the schedulability constraint.
3.3. Unschedulability of Many Processes
The previous section developed a sufficient and not necessary test for the schedulability of
a process system. We note that whilst this test identifies some of the schedulable process
systems, a sufficient and not necessary unschedulability test will identify some of the
unschedulable systems. This approach is illustrated by Figure 9.
Schedulable Systems Unschedulable Systems
Systems Found By Sufficient and
Not Necessary Schedulability Test
Systems Found By Sufficient and
Not Necessary Unschedulability Test
Exact Division Given By Sufficient and Necessary
Schedulability or Unschedulability Test
Domain of Process Systems

Figure

9.
A sufficient and not necessary unschedulability test identifies some unschedulable
process systems in the same manner as the test in the previous sub-section identifies
schedulable systems. The combination of the two tests enables the identification of many
schedulable and unschedulable process systems without resorting to a computationally
expensive sufficient and necessary test. A sufficient and not necessary unschedulability
test is now presented.
Consider the interference of higher priority processes upon t i . This is at a minimum
when any incomplete executions of higher priority processes occur as late as possible. This
maximises the time utilised by higher priority processes after D i and minimises the time
utilised before D i .
Theorem 5 : I i is at a minimum when incomplete executions of higher priority
processes perform their execution as late as possible.
time
time

Figure

10.
Consider Figure 10. The execution of t j in #
# is
decreased by moving the execution towards the deadline of t j (which is after
movement decreases I i . I i will be at a minimum when the execution
has been moved as close as possible to the deadline of t j .
Consider the schedulability of t i . When I i is a minimum, we have the best possible
scenario for scheduling t i . If t i cannot be scheduled with I i a minimum, it cannot be
scheduled with an exact I i since this value is as least as large as the minimum value.
Therefore, to show the unschedulability of a process system, it is sufficient to show the
unschedulability of the system with minimum values of I i .
An unschedulability test is now developed using minimum interference. In Figure
10, the interference on t i is the sum of complete executions of higher priority processes,
and the parts of incomplete executions that must occur before b be the
complete executions and k the incomplete executions. The total interference is stated as:
I
Complete executions occur in the interval #
# and are given by:
The incomplete executions number either 0 or 1 for each of the processes with a higher
priority than t i . Hence, the interference due to incomplete executions can be stated as
Substituting into equation (10) we generate an unschedulability test:
"i
I i
where
I
We note that only one process need pass the unschedulability test for the process
system to be unschedulable.
The converse of Theorem 3 proves equation (11) to be a sufficient condition for
unschedulability. This follows from the observation that since I i is a minimum (by
Theorem 5), then by Theorem 5 if a process system cannot be scheduled with I i less than
an exact value, the process system cannot be scheduled with exact values of I i . By
Theorem 4, we note that equation (11) is a not necessary condition for unschedulability
since the values used for I i are less than or equal to the exact value for I i .
Equations and (11) can be used together. Consider a process system that fails
equation (9). Since this is test is not necessary it does not prove the process system
unschedulable. The same process system can be submitted to equation (10). If the system
equation (10) we have determined the unschedulability of the process system.
However, if the process system failed both schedulability and unschedulability tests we
note that it could still be schedulable.
We illustrate the use combined use of equations (9) and (11) with the following
example.
Example
Consider the following process system.
We can show the unschedulability of the system by using equation (11).
(a) check process
I 1
Hence t 1 fails the test and is therefore not unschedulable.
(b) check process
I 2
I 2
where
I
I
substituting3
Hence t 2 fails the test and is therefore not unschedulable.
(c) check process
I 3
I 3
where
I
I
substituting7
Therefore t 3 passes the unschedulability test. The process system is therefore
unschedulable. An example run of the system is given in Figure 11. Process t 3 misses its
deadline at time 13.

Figure

11.
We now reduce the computation time of process t 3 to 5:
By observation, we can see that t 3 now fails the unschedulability test:
I 3
Since the characteristics of the first two processes are identical, the process system as
a whole fails the unschedulability test. However, the system is not necessarily
unschedulable. Now we try to prove the process system schedulable using equation (9).
(a) check process t 1
I 1
Hence t 1 is schedulable.
(b) check process t 2
where
I
I
substituting3
Hence t 2 is schedulable.
(c) check process t 3
I 3
I 3
where
I
I
substituting5
Hence t 2 is not schedulable by equation (9).
In the above, we have shown the process system failing both the schedulability and
unschedulability tests. Since both tests are sufficient and not necessary we have not
decisively proved the process system schedulable or unschedulable.
The above example illustrated the combined use of unschedulability and
schedulability tests. The first part of the example utilised the unschedulability test to
prove the test unschedulable. Then, by decreasing the computation time of t 3 , the system
fails the unschedulability test. However, after application of equation (9), the system was
shown to fail the schedulability test also. Indeed, by examining the example we can see
that when C 3 lies in #
# the system can be proved schedulable. When C 3 lies in #
# the
system can be proved unschedulable. When C 3 lies in #
# we can not prove the system
schedulable nor unschedulable. This requires a more powerful schedulability test. Such a
test is presented in the next sub-section.
3.4. Exact Schedulability of Many Processes
The schedulability and unschedulability constraints for systems containing many
processes, given by equations (9) and (11) respectively, are sufficient and not necessary in
the general case. To form a sufficient and necessary schedulability test requires exact
values for I i (by Theorems 2 and 4). To achieve this, the schedule has to be evaluated so
that the exact interleaving of higher priority process executions is known. This is costly if
the entire interval between the critical instant and the deadline of process t i is evaluated as
this would require the solution of D i equations.
The number of equations can be reduced by observing that if t i meets its deadline at
lies in #
# , we need not evaluate the equations in #
# . Further
reductions in the number of equations requiring solution can be made by considering the
behaviour of the processes in the interval #
# .
Consider the interaction of processes t 1 to t i-1 on process t i in the interval #
# .
For process t i to meet its deadline at D i we require the following condition to be met:
I i
We wish to consider only the points in D i upto and including t - i . Therefore, we need to
refine the definition of interference on t i so that we can reason about the interval #
rather than the single point in time D i .
Definition 2: I i
t is the interference that is encountered by t i between the release
of t i and time t , where t lies in the interval #
# . This is equal to the quantity
of work that is created by releases of higher priority processes in the interval
between the release of t i and time t .
At t - i the outstanding work due to higher priority processes must be 0 since t i can
only execute if all higher priority processes have completed. Hence, the point in time at
which t i actually meets its deadline is given by:
I i
Therefore, we can state the following condition for the schedulability of
I i
where
I i
We note that the definition of I i
t includes parts of executions that may occur after t .
However, since the outstanding workload of all processes is 0 at t - i then when the
expression I i
t is exact.
The above equations require a maximum of D i calculations to be made to determine
the schedulability of t i . For an n process system the maximum number of equations that
need to be evaluated is:
The number of equations that need to be evaluated can be reduced. This is achieved
by limiting the points in #
# that are considered as possible solutions for t - i . Consider
the times within #
# that t i could possibly meet its deadline. We note that I i
t is
monotonically increasing within the time interval #
# . The points in time that the
interference increases occur when there is a release of a higher priority process. This is
illustrated by Figure 12.
(D 4 )
I 4
Release
Release
Release t 3
Release
Release

Figure

12.
In

Figure

12, there are three processes with higher priority than t 4 . We see that as the
higher priority processes are released, I 4
increases monotonically with respect to t . The
graph is stepped with plateaus representing intervals of time in which no higher priority
processes are released. It is obvious that only one equation need be evaluated for each
plateau as the interference does not change.
To maximise the time available for the execution of t i we choose to evaluate at the
right-most point on the plateau. Therefore, one possible reduction in the number of
equations to evaluate schedulability occurs by testing t i at all points in #
# that
correspond to a higher priority process release. Since as soon as one equation identifies the
process system as schedulable we need test no further equations. Thus, the effect is to
evaluate equations in #
# .
The number of equations has been reduced in most cases. We note that no reduction
will occur if for each point in time in #
# a higher priority process is released with t i
meeting its deadline at D i .
The number of equations is reduced further by considering the computation times of
the processes. Consider Figure 13.
(D 4 )
Time 0: Release t 1 , t 2 , t 3 and t 4 .
Time 4: Release t 1
Time 5: Release t 2
Time
Time 8: Release t 1

Figure

13.
In

Figure

13 the total computation requirement of the system (C s ) is plotted against time.
At the first point in time when the outstanding computation is equal to the time elapsed, we
have found t - 4 (by equation (12)). In the above diagram this point in time coincides with
the deadline of t 4 .
Considering Figure 13, there is no point in testing the schedulability of t i in the
interval #
# . Also, since time 0 corresponds with a critical instant (a simultaneous
release of all processes) the first point in time that t i could possibly complete is:
This gives a schedulability constraint of:
I i
Since the value of t 1 assumes that only one release of each process occurs in #
# , the
constraint will fail if there have been any releases of higher priority processes within the
interval #
# . The exact amount of work created by higher priority processes in this
interval is given by:
I i
The next point in time at which t i may complete execution is:
This gives a schedulability constraint of:
I i
Again, the constraint will fail if releases have occurred in the interval #
# . Thus, we
can build a series of equations to express the schedulability of t i .
I i
I i
I i
I i
tk
If any of the equations hold, t i is schedulable. The series of equations above is
encapsulated by the following algorithm:
Algorithm
foreach t i do
while #
do
if
I i
else
endif
exit /* t i is unschedulable * /
endif
endwhile
endfor
The algorithm terminates as the following relation always holds.
When t i is greater than D i the algorithm terminates since t i is unschedulable. Thus we have
a maximum number of steps of D i . This is a worst-case measure.
The number of equations has been reduced from the method utilising plateaus in

Figure

11. This is because we consider only the points in time where it is possible for t i to
complete, rather than points in time that correspond to higher priority process releases.
An example use of the above algorithm is now given:
Example
We return to the process system which could not be proved schedulable nor unschedulable:
proved schedulable in the previous example so we confine
attention to t 3 . We use the successive equations to show unschedulability.
I 3
where
where
I 3
substituting14
The process is unschedulable at time 12, so we proceed to the next equation.
I 3
where
Since we now have t 1 > D 3 we terminate with t 3 unschedulable.
We reduce the computation time of t 3 to 3:
We use the successive equations to show t 3 schedulable.
I 3
where
where
I 3
substituting7
Hence t 3 is schedulable, meeting its deadline at time 10. An example run of the
system is seen in Figure 14.

Figure

14.
The successive equations (13) have shown the process system to be schedulable. The
solution of a single equation was required.
3.5.

Summary

This section has introduced a number of schedulability and unschedulability tests for
the deadline monotonic algorithm:
# a O (n ) schedulability test that is sufficient and not necessary;
# a O (n 2 ) schedulability test that is sufficient and not necessary;
# a O (n 2 ) unschedulability test that is sufficient and not necessary;
# a sufficient and necessary schedulability test that has data-dependent
complexity.
The first test provides the coarsest level. The second and third tests combine to provide a
finer grain measure of process systems that are definitely schedulable or definitely
unschedulable. The sufficient and necessary test is able to differentiate schedulable and
unschedulable systems to provide the finest level of test.
One constraint on the process systems is that they must have a critical instant. This is
ensured as all processes have an initial release at time 0.
4. SCHEDULING SPORADIC PROCESSES
Non-periodic processes are those whose releases are not periodic in nature. Such
processes can be subdivided into two categories [Aud90a]: aperiodic and sporadic. The
difference between these categories lies in the nature of their release frequencies.
Aperiodic processes are those whose release frequency is unbounded. In the extreme, this
could lead to an arbitrarily large number of simultaneously active processes. Sporadic
processes are those that have a maximum frequency such that only one instance of a
particular sporadic process can be active at a time.
When a static scheduling algorithm is employed, it is difficult to introduce non-periodic
process executions into the schedule: it is not known before the system is run when non-periodic
processes will be released. More difficulties arise when attempting to guarantee
the deadlines of those processes. It is clearly impossible to guarantee the deadlines of
aperiodic processes as there could be an arbitrarily large number of them active at any
time. Sporadic processes deadlines can be guaranteed since it is possible, by means of the
maximum release frequency, to define the maximum workload they place upon the system.
One approach is to use static periodic polling processes to provide sporadics with
executions time. This approach is reviewed in section 4.1. Section 4.2 illustrates how to
utilise the properties of the deadline monotonic scheduling algorithm to guarantee the
deadlines of sporadic processes without resorting to the introduction of polling processes.
4.1. Sporadic Processes: the Polling Approach
To allow sporadic processes to execute within the confines of a static schedule (such as
that generated by the rate-monotonic algorithm) computation time must be reserved within
that schedule. An intuitive solution is to set up a periodic process which polls for sporadic
processes [Leh87a]. Strict polling reduces the bandwidth of processing as
processing time that is embodied in an execution of the polling process is
wasted if no sporadic process is active when the polling process becomes
occurring after the polling process's computation time in one
period has been exhausted or just passed have to wait until the next period for
service.
A number of bandwidth preserving algorithms have been proposed for use with the rate-monotonic
scheduling algorithm. One such algorithm is the deferrable server [Leh87a,
Sha89b, Sha89a]. The server is a periodic process that is allotted a number of units of
computation time per period. These units can be used by any sporadic process with
outstanding computational requirements. When the server is run with no outstanding
sporadic process requests, the server does not execute but defers its assigned computation
time. The server's time is preserved at its initial priority. When a sporadic request does
occur, the server has maintained its priority and can thus run and serve the sporadic
processes until its allotted computation time within the server period has been exhausted.
The computation time for the server is replenished at the start of its period.
Problems arise when sporadic processes require deadlines to be guaranteed. It is difficult to
accommodate these with a deferrable server due to the rigidly defined points in time at
which the server computation time is replenished. The sporadic server [Sha89a] provides
a solution to this problem. The replenishment times are related to when the sporadic uses
computation time rather than merely at the period of the server process.
The sporadic server is used by Sha et al [Sha89a] in conjunction with the rate-monotonic
scheduling algorithm to guarantee sporadic process deadlines. Since the rate-monotonic
algorithm is used, a method is required to map sporadic processes with timing
characteristics given by
computation time - deadline - period
onto periodic server processes that have timing characteristics given by
computation time - deadline = period
The method adopted in [Sha89a] lets the computation time, period and deadline of the
server be equal to the computation time, minimum inter-arrival time and deadline of the
sporadic process. The rate-monotonic scheduling algorithm is then used to test the
schedulability of the process system, with runtime priorities being assigned in a deadline
monotonic manner.
The next section details a simpler approach to guaranteeing sporadic deadlines based upon
the deadline monotonic scheduling algorithm.
4.2. Sporadic Processes: the Deadline Monotonic Scheduling Approach
Consider the timing characteristics of a sporadic process. The demand for
computation time is illustrated in Figure 15.
Process
Released
Deadline
Released
Deadline
Released

Figure

15.
The minimum time difference between successive releases of the sporadic process is
the minimum inter-arrival time m . This occurs between the first two releases of the
sporadic. At this point, the sporadic is behaving exactly like a periodic process with period
the sporadic is being released at its maximum frequency and so is imposing its
maximum workload.
When the releases do not occur at the maximum rate (between the second and third
releases in Figure 15) the sporadic behaves like a periodic process that is intermittently
activated and then laid dormant. The workload imposed by the sporadic is at a maximum
when the process is released, but falls when the next release occurs after greater than m
time units have elapsed.
In the worst-case the sporadic process behaves exactly like a periodic process with
period m and deadline D (D - m ). The characteristic of this behaviour is that a maximum
of one release of the process can occur in any interval #
# where release time t is at
least units after the previous release of the process. This implies that to guarantee
the deadline of the sporadic process the computation time must be available within the
interval #
# noting that the deadline will be at least m after the previous deadline of
the sporadic. This is exactly the guarantee given by the deadline-monotonic schedulability
tests in section 3.
For schedulability purposes only, we can describe the sporadic process as a periodic
process whose period is equal to m . However, we note that since the process is sporadic,
the actual release times of the process wil not be periodic, merely separated by at least m
time units.
For the schedulability tests given in section 3 to be effective for this process system,
all processes, both periodic and sporadic, have to be released simultaneously. We can
assume that all the processes are released simultaneously at time 0: a critical instant. This
forms the worst-case workload on the processor. If the deadline of the sporadic can be
guaranteed for the release at a critical instant then all subsequent deadlines are guaranteed.
An example is now given.
Example
Consider the following process system.
are periodic, whilst t 2 and t 4 are sporadic with minimum inter-arrival
times given by T 2 and T 4 respectively.
We check the schedulability of the system using the equations given in section 3. The
simplest test (equation (8)) is used.
(a) check process t 1
I 1
Hence t 1 is schedulable.
(b) check process t 2
I 2
I 2
where
I
substituting2
Hence t 2 is schedulable.
(c) check process t 3
I 3
I 3
where
I
substituting2
Hence t 3 is schedulable.
(d) check process t 4
I 4
I 3
where
I
I
substituting2
Hence t 4 is schedulable.
The process system is schedulable. An example run is given in Figure 16.

Figure

16.
In the example run (Figure 16) all deadlines are met. Each of the sporadic processes
are released at time 0. This forms a critical instant and thus the worst-possible scenario for
scheduling the process system. A combination of many periodic and many sporadic
processes was shown to be schedulable under this scheme without the need for server
processes which are required for scheduling sporadic processes with the rate-monotonic
scheduling algorithm (see section 4.1).
4.3.

Summary

The proposed method for guaranteeing the deadlines of sporadic processes using sporadic
servers within the rate-monotonic scheduling framework has two main drawbacks. Firstly,
one extra periodic server process is required for each sporadic process. Secondly, an extra
run-time overhead is created as the kernel is required to keep track of the exact amount of
time the server has left within any period.
The deadline-monotonic approach circumvents these problems since no extra
processes are required: the sporadic processes can be dealt with adequately within the
existing periodic framework.
5. CONCLUSIONS
The fundamental constraints of the rate-monotonic scheduling algorithm have been
weakened to permit processes that have deadlines less than period to be scheduled. The
resulting scheduling mechanism is the deadline-monotonic algorithm. Schedulability tests
have been presented for the deadline-monotonic algorithm.
Initially a simple sufficient and not necessary schedulability test was introduced.
This required a single equation per process to determine schedulability. However, to
achieve such simplicity meant the test was overly pessimistic.
The simplifications made to produce a single equation test were then partially
removed. This produced a sufficient and not necessary schedulability test which passed
more process systems than the simple test. The complexity of the second test was O (n 2 )
compared with O (n ) for the simple test. Again, the test was pessimistic.
To complement the second schedulability test, a similar unschedulability test was
developed. The combination of sufficient and not necessary schedulability and
unschedulability tests was shown to be useful for identifying some unschedulable systems.
However, it was still possible for a process system to fail both the schedulability and
unschedulability tests.
This problem was resolved with the development of a sufficient and necessary
schedulability test. This was the most complex of all the tests having a complexity related
to the periods and computation times of the processes in the system. The complexity was
reduced substantially when the number of equations required to determine the
schedulability of a process were minimised.
The problem of guaranteeing the deadlines of sporadic processes was then discussed.
Noting that schedulability tests proposed for sporadic processes and the rate-monotonic
algorithm require the introduction of special server processes, we then proposed a simple
method to guarantee the deadlines of sporadic processes within the confines of the
deadline-monotonic algorithm. The simplicity of the method is due to sporadic processes
being treated exactly as periodic processes for the purpose of determining the
schedulability. Using this scheme, any mixture of periodic and sporadic deadlines can be
scheduled subject to the process system passing the deadline-monotonic schedulability
constraint.
A number of issues raised by the work outlined in this paper require further
consideration. These include the effect of allowing processes to synchronise and vary their
timing characteristics. Another related issue is the effect of deadline-monotonic
scheduling upon system utilisation. These issues remain for further investigation.

ACKNOWLEDGEMENTS

The author thanks Mike Richardson, Alan Burns and Andy Wellings for their
valuable comments and diatribes.



--R


"Misconceptions About Real-Time Computing: A Serious Problem for Next Generati on Systems"
"Scheduling Real-Time Systems"
"Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment"
"The Rate-Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behaviour"
"Aperiodic Task Scheduling for Hard Real-Time Systems"
"Real-Time Scheduling Theory and Ada"
"Real-Time Scheduling Theory and Ada"
"Priority Inheritance Protocols: An Approach to Real-Time Synchronisation"
"On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks"
"Enhanced Aperiodic Responsiveness in Hard Real-Time Environments"
"An Analytical Approach to Real-Time Software Engineering"
--TR
deadline monotonic scheduling;priority inheritance protocol;rate monotonic scheduling;feasibility decision algorithm;periodic task