Static priority scheduling of event-triggered real-time embedded systems

摘要

Real-time embedded systems are often specified as a collection of independent tasks, each generating a sequence of event-triggered code blocks. The goal of scheduling tasks in this domain is to find an execution order which satisfies all real-time constraints. Within the context of recurring real-time tasks, all previous work either allowed preemptions, or only considered dynamic scheduling, and generally had exponential complexity. However, for many embedded systems running on limited resources, preemptive scheduling may be very costly due to high context switching and memory overheads, and dynamic scheduling can be less desirable due to high CPU overhead. In this paper, we study static priority scheduling of recurring real-time tasks. We focus on and obtain schedule-theoretic results for the non-preemptive uniprocessor case. To achieve this, we derive a sufficient (albeit not necessary) condition for schedulability under static priority scheduling and show that this condition can be efficiently tested in practice. The latter technique is demonstrated with examples, where in each case, an optimal solution for a given problem specification is obtained within reasonable time, by first detecting good candidates using meta-heuristics, and then by testing them for schedulability.