On Optimal, Non-Preemptive Scheduling of Periodic and Sporadic Tasks
TR90-019
Kevin Jeffay, Richard Anderson, Charles U. Martel
Periodic and sporadic tasks are central components in 
both the analysis and implementation of real-time 
systems.  A periodic task makes requests for execution at 
precise intervals while a sporadic task makes execution 
requests at arbitrary times but with a bounded minimum 
duration between requests.  This paper examines the 
problem of scheduling a set of periodic or sporadic tasks 
on a uniprocessor using a non-preemptive discipline.  We 
derive a set of conditions to guarantee the correctness of 
non-preemptive deadline driven scheduling algorithm.  
We then show that for scheduling sporadic tasks this 
discipline is optimal over the class of non-preemptive 
algorithms which do not use inserted idle time.  The 
problem of determining feasibility  for our algorithm can 
be decided in pseudo-polynomial time.  This scheduling 
discipline is also optimal for scheduling periodic tasks 
when all possible    release times are considered.  Lastly, 
we show that if there exists an optimal polynomial time 
scheduling algorithm for periodic tasks with arbitrary 
release times, then P = NP.