Automatic Task Splitting for Uniprocessor Systems Scheduled with Non-Preemptive EDF | Chapter 03 | Theory and Applications of Mathematical Science Vol. 1
Although preemptive scheduling
dominates non-preemptive scheduling from a schedulability perspective, the
latter will often be chosen by developers of real-time systems with resource
constraints due to the inherently lower system overheads, easier code
implementation and timing analysis. This paper is concerned with the
uniprocessor scheduling of periodic and sporadic tasks with arbitrary relative
deadlines in real-time systems using the non-preemptive version of the Earliest
Deadline First (npEDF) algorithm. Although npEDF is known to be optimal among
the non-preemptive work-conserving schedulers, it can still be restrictive in
the sense that there exists uniprocessor-feasible task sets (with arbitrarily
low CPU utilization) that are not schedulable with npEDF. For such task sets,
system developers are forced to either consider the use of an alternate
scheduling strategy or refactor the task software in some beneficial way. One
such beneficial way is to apply a concept known as ‘task splitting’. However to
date, little guidance has been available to assist developers with the latter
process, and it is often performed on an ad-hoc basis. This paper will propose
the application of a fast and efficient task splitting technique to assist
developers with this software refactoring process, which can thus be used to
maximize the achievable CPU utilization whilst retaining the benefits of
non-preemption. Examples and experimental results are given to illustrate the
performance of the algorithm. For random but representative task sets, the
results also indicate that in the average case only a relatively small number
of tasks require the application of task splitting to become schedulable under
npEDF.
Author(s) Details
Michael Short
School of Computing,
Engineering and Digital Technologies, Teesside University, Middlesbrough, UK.
Comments
Post a Comment