You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.
The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.
For the reports in this repository we specifically note that
- the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
- the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
- technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
- in other cases, please contact the copyright owner for detailed information
By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.
If you are in doubt, feel free to contact webmaster@ide.mdh.se
Quantifying the Sub-Optimality of Non-Preemptive Real-time Scheduling
Abstract
Many preemptive real-time scheduling algorithms, such as the Earliest
Deadline First (EDF), are known to be optimal on a uni-processor. However, no such
algorithms exist under the non-idling non-preemptive scheduling paradigm. Hence
preemptive schemes strictly dominate non-preemptive schemes with respect to feasibility.
However, the ’goodness’ of non-preemptive schemes in successfully scheduling
feasible task sets when compared to uni-processor optimal preemptive scheduling
schemes such as the EDF, which can also be referred to as its sub-optimality, is
unknown. In this paper, we apply resource augmentation, specifically the processor
speed-up, to quantify the sub-optimality of non-preemptive scheduling with respect
to an optimal uni-processor scheduling scheme such as the EDF. We also present a
method to guarantee user specified upper-bounds on the preemption related costs in
the schedule.We prove that the speed-up required to guarantee the feasibility of a non-preemptive
execution of any task ti, for a duration of Li, is upper-bounded by 4Li/Dmin
, where Dmin is
the smallest relative deadline in the task set. Consequently, we show that the upperbound
on the processor speed that guarantees the feasibility of a non-preemptive
schedule for the task set is 4Cmax/Dmin
, where Cmax is the largest execution time in the task
set. The derived upper-bound is used in a sensitivity analysis based method to calculate
the optimal processor speed that guarantees a specified upper-bound on the preemption
related costs in the schedule. For this, we first present a method to translate the system-level requirements of meeting specified upper bounds on the preemption
related costs to task level non-preemption requirements.We then use sensitivity analysis
technique to calculate the optimal processor speed that guarantees the feasibility
of the derived task level non-preemption requirements, which in its turn guarantees
the desired bounds on the preemption related overheads.Our contribution quantifies the sub-optimality of non-preemptive scheduling in
terms of the processor speed-up required to successfully schedule all the uni-processor
feasible task sets. It also enables a system designer to use a faster processor to guarantee
specified upper-bounds on the preemption related overheads.
Bibtex
@techreport{Thekkilakattil2652,
author = {Abhilash Thekkilakattil and Radu Dobrin and Sasikumar Punnekkat},
title = {Quantifying the Sub-Optimality of Non-Preemptive Real-time Scheduling},
month = {November},
year = {2012},
url = {http://www.es.mdu.se/publications/2652-}
}
