Hardware Reference
In-Depth Information
4.7
COMPARISON BETWEEN RM AND EDF
In conclusion, the problem of scheduling a set of independent and preemptable peri-
odic tasks has been solved both under fixed and dynamic priority assignments.
The major advantage of the fixed priority approach is that it is simpler to implement.
In fact, if the ready queue is implemented as a multi-level queue with
P
priority levels
(where
P
is the number of different priorities in the system), both task insertion and
extraction can be achieved in
O
(1). On the other hand, in a deadline driven scheduler,
the best solution for the ready queue is to implement it as a heap (i.e., a balanced
binary tree), where task management requires an
O
(log
n
) complexity.
Except for such an implementation issue, which becomes relevant only for very large
task sets (consisting of hundreds of tasks), or for very slow processors, a dynamic
priority scheme has many advantages with respect to a fixed priority algorithm. A
detailed comparison between RM and EDF has been presented by Buttazzo [But03,
But05].
In terms of schedulability analysis, an exact guarantee test for RM requires a pseudo-
polynomial complexity, even in the simple case of independent tasks with relative
deadlines equal to periods, whereas it can be performed in
O
(
n
) for EDF. In the gen-
eral case in which deadlines can be less than or equal to periods, the schedulability
analysis becomes pseudo-polynomial for both algorithms. Under fixed-priority as-
signments, the feasibility of the task set can be tested using the response time analysis,
whereas under dynamic priority assignments it can be tested using the processor de-
mand criterion.
As for the processor utilization, EDF is able to exploit the full processor bandwidth,
whereas the RM algorithm can only guarantee feasibility for task sets with utilization
less than 69%, in the worst case. In the average case, a statistical study performed by
Lehoczky, Sha, and Ding [LSD89] showed that for task sets with randomly generated
parameters the RM algorithm is able to feasibly schedule task sets with a processor
utilization up to about 88%. However, this is only a statistical result and cannot be
taken as an absolute bound for performing a precise guarantee test.
In spite of the extra computation needed by EDF for updating the absolute deadline
at each job activation, EDF introduces less runtime overhead than RM, when context
switches are taken into account. In fact, to enforce the fixed priority order, the number
of preemptions that typically occur under RM is much higher than under EDF.
Search WWH ::
Custom Search