The limited-preemption uniprocessor scheduling of sporadic task systems

Although preemptive uniprocessor scheduling algorithms are able to successfully schedule some systems that cannot be scheduled by any non-preemptive scheduling algorithm, the run-time overhead associated with implementing preemptive algorithms is often higher than for non-preemptive algorithms. In choosing between preemptive and non-preemptive scheduling algorithms on uniprocessors, the tradeoff is therefore between enhanced feasibility on the one hand, and increased overheads on the other. Hybrid scheduling schemes are proposed and evaluated here: these schemes permit preemption where necessary for feasibility, but attempt to avoid unnecessary preemptions during run-time. This is done by determining, for each task in the system, the longest amount of time for which the task may execute non-preemptively without compromising the feasibility of the system.