The Limited-Preemption Uniprocessor Scheduling of Sporadic Task Systems

Although preemptive uniprocessor scheduling algorithms are ableto successfully schedule some systems that cannot be scheduledby any non-preemptive scheduling algorithm, the run-time overheadassociated with implementing preemptive algorithms is often higherthan for non-preemptive algorithms.In choosing between preemptiveand non-preeemptive scheduling algorithms and uniprocessors, thetradeoff is therefore between enhanced feasibility on the one hand,and increased overheads on the other.Hybrid Scheduling schemesare proposed and evaluated here:these schemes permit preemptionwhere necessary for feasibility, but attempt to avoid unnecessarypreemptions during run-time.This is done by determining, for eachtask in the system, the longest amount of time for which the task mayexecute non-preemptively without compromising the feasibility of thesystem.