Hardware Reference
In-Depth Information
5.5.2
PE VERSUS DS
The DS and the PE algorithms represent two alternative techniques for enhancing ape-
riodic responsiveness over traditional background and polling approaches. Here, these
techniques are compared in terms of performance, schedulability bound, and imple-
mentation complexity, in order to help a system designer select the most appropriate
method for a particular real-time application.
The DS algorithm is much simpler to implement than the PE algorithm, because it
always maintains its capacity at the original priority level and never exchanges its
execution time with lower-priority tasks, as does the PE algorithm. The additional
work required by PE to manage and track priority exchanges increases the overhead
of PE with respect to DS, especially when the number of periodic tasks is large. On the
other hand, DS does pay a schedulability penalty for its simplicity in terms of a lower
utilization bound. This means that, for a given periodic load
U
p
, the maximum size
of a DS server that can still guarantee the periodic tasks is smaller than the maximum
size of a PE server.
The maximum utilizations for DS and PE, as a function of task utilizations, have been
derived in Equations (5.15) and (5.8), respectively (since PE, like PS, behaves as a
periodic task in terms of utilization). Hence, the following:
2
−
P
U
max
DS
=
(5.19)
2
P
−
1
2
−
P
U
max
PE
=
(5.20)
P
where
n
P
=
(
U
i
+1)
.
i
=1
Note that if all the
n
periodic tasks have the same utilization
U
i
=
U
p
/n
, the
P
factor
can be expressed as a function of
U
p
as
P
=
U
p
n
+1
n
.
Note that the case in which all periodic tasks have the same utilization represents the
worst-case scenario for the task set, as clear from Figure 4.11, since the hyperbole is
tangent to the linear Liu and Layland bound.
A plot of the maximum server utilizations as a function of
U
p
(and for a large number
of tasks) is shown in Figure 5.16. Note that when
U
p
=0
.
6, the maximum utilization
Search WWH ::
Custom Search