A New Approach for Limited Preemptive Scheduling in Systems with Preemption Overhead
Ref: CISTER-TR-160504 Publication Date: 5 to 8, Jul, 2016
A New Approach for Limited Preemptive Scheduling in Systems with Preemption Overhead
Ref: CISTER-TR-160504 Publication Date: 5 to 8, Jul, 2016Abstract:
This paper considers the problem of reducing the
number of preemptions in a system with periodic tasks and
preemption overhead. The proposed solution is based on the key
observation that for periodic task sets, the task with the smallest
period plays an important role in determining the maximum
interval of time during which a lower priority task can be
executed without being preempted. We use this property to
build a new limited preemptive scheduling algorithm, named RSLP, based on fixed-priority scheduling. In RS-LP, the length of
each task’s non-preemptive region is varying during the system
execution so as to keep the preemptions aligned with the releases
of the highest priority task. This simple mechanism allows us
to reduce the overall number of preemptions. The proposed
algorithm, decides whether or not to preempt the currently
executing task based on the maximum blocking tolerance of the
higher priority tasks. In any case, the preemptions are authorized
only at release instants of the task with the smallest period,
thereby limiting the maximum number of preemptions to the
number of releases of the highest priority task. Moreover, in
this paper, we provide two different preemption overhead aware
schedulability tests for periodic and loose-harmonic task sets
(i.e., where each period is an integer multiple of the smallest
period), together with a lower bound on the maximum number
of preemptions. To conclude, extensive experiments comparing
RS-LP with the state of the art limited preemptive scheduling
algorithms are finally presented.
Mitra Nasri
Geoffrey Nelissen
Gerhard FohlerDocument:
View
Download28th Euromicro Conference on Real-Time Systems (ECRTS 2016).
Toulouse, France.
Record Date: 9, May, 2016