The Global Limited Preemptive Earliest Deadline First Feasibility of Sporadic Real-time Tasks

• The feasibility of preemptive and non-preemptivescheduling has been well investigated on uniprocessor and multiprocessor platforms under both Fixed Priority Scheduling(FPS) and Earliest Deadline First (EDF) paradigms. While feasibility of limited preemptive scheduling under FPS has been addressed on both uniprocssor and multiprocessor platforms,under EDF it has been investigated only on uniprocessors, and a similar analysis for multiprocessor platforms is still missing.In this paper, we introduce global Limited Preemptive Earliest Deadline First (g-LP-EDF) scheduling, and propose the associated feasibility analysis to complete the above described feasibility analysis spectrum. Specifically, we derive a sufficient condition that guarantees g-LP-EDF feasibility of sporadic real timetasks which directly provides a global Non-Preemptive Earliest Deadline First (g-NP-EDF) feasibility test. We then study the interplay between g-LP-EDF feasibility and processor speed, in order to quantify the sub-optimality of g-NP-EDF in terms of the minimum speed-up required to guarantee g-NP-EDF feasibility of all feasible tasksets. The results presented in this paper complement our previous results on uniprocessors, and provide a unified result on the sub-optimality of non-preemptive EDF on both uniprocessor and multiprocessor platforms.

Subject headings

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering (hsv//eng)

Publication and Content Type

ref (subject category)

kon (subject category)