Hardware Reference
In-Depth Information
The algorithm is defined as follows:
The DPE server has a specified period T s and a capacity C s .
At the beginning of each period, the server's aperiodic capacity is set to C S ,
where d is the deadline of the current server period.
Each deadline d associated to the instances (completed or not) of the i th periodic
task has an aperiodic capacity, C S i , initially set to 0.
Aperiodic capacities (those greater than 0) receive priorities according to their
deadlines and the EDF algorithm, like all the periodic task instances (ties are
broken in favor of capacities; that is, aperiodic requests).
Whenever the highest-priority entity in the system is an aperiodic capacity of C
units of time the following happens:
- if there are aperiodic requests in the system, these are served until they
complete or the capacity is exhausted (each request consumes a capacity
equal to its execution time);
- if there are no aperiodic requests pending, the periodic task having the short-
est deadline is executed; a capacity equal to the length of the execution is
added to the aperiodic capacity of the task deadline and is subtracted from
C (that is, the deadlines of the highest-priority capacity and the periodic
task are exchanged);
- if neither aperiodic requests nor periodic task instances are pending, there is
an idle time and the capacity C is consumed until, at most, it is exhausted.
An example of schedule produced by the DPE algorithm is illustrated in Figure 6.1.
Two periodic tasks, τ 1 and τ 2 , with periods T 1 =8and T 2 =12and worst-case
execution times C 1 =2and C 2 =3, and a DPE server with period T s =6and
capacity C s =3, are present in the system.
At time t =0, the aperiodic capacities C S 1
(with deadline
12) are set to 0, while the server capacity (with deadline 6) is set to C s = C S =3.
Since no aperiodic requests are pending, the two first periodic instances of τ 1 and τ 2
are executed and C s is consumed in the first three units of time. In the same interval,
two units of time are accumulated in C S 1
(with deadline 8) and C 1 S 2
and one unit in C 1 S 2
.
At time t =3, C S 1
is the highest-priority entity in the system. Again, since no aperi-
odic requests are pending, τ 2 keeps executing and the two units of C S 1
are consumed
and accumulated in C 1 S 2
. In the following three units of time the processor is idle and
Search WWH ::




Custom Search