Hardware Reference
In-Depth Information
Considering a fixed cost ξ i for each preemption, then the number of preemptions can
be upper bounded using the following recurrent relation:
= C NP
ν i
1
i
q i
= C NP
+ ξ i ν s− 1
i
ν i
1
i
q i
= ν s− 1
i
where the iteration process converges when ν i
.
Finally, under cooperative scheduling, the number of preemptions can be simply upper
bounded by the number of effective preemption points inserted in the task code.
Simulations experiments with randomly generated task sets have been carried out by
Yao, Buttazzo, and Bertogna [YBB10b] to better evaluate the effectiveness of the con-
sidered algorithms in reducing the number of preemptions. Figures 8.17(a) and 8.17(a)
show the simulation results obtained for a task set of 6 and 12 tasks, respectively, and
report the number of preemptions produced by each method as a function of the load.
Each simulation run was performed on a set of n tasks with total utilization U varying
from 0.5 to 0.95 with step 0.05. Individual utilizations U i were uniformly distributed
in [0,1], using the UUniFast algorithm [BB05]. Each computation time C i was gener-
ated as a random integer uniformly distributed in [10, 50], and then T i
was computed
as T i
= C i /U i . The relative deadline D i
was generated as a random integer in the
range [ C i +0 . 8
C i ) ,T i ]. The total simulation time was set to 1 million units of
time. For each point in the graph, the result was computed by taking the average over
1000 runs.
·
( T i
All the task sets have been generated to be preemptive feasible. Under preemption
thresholds (PT), the algorithm proposed by Saksena and Wang [SW00] was used to
find the maximum priority threshold that minimizes the number of preemptions. Un-
der deferred preemptions (DP) and task splitting (TS), the longest non-preemptive re-
gions were computed according to the methods presented in Sections 8.4.2 and 8.5.2,
respectively. Finally, under task splitting, preemption points were inserted from the
end of task code to the beginning.
As expected, fully preemptive scheduling (PR) generates the largest number of pre-
emptions, while DP and TS are both able to achieve a higher reduction. PT has an
intermediate behavior. Note that DP can reduce slightly more preemptions than TS,
since, on the average, each preemption is deferred for a longer interval (always equal
to Q i , except when the preemption occurs near the end of the task).
Search WWH ::




Custom Search