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

Abstract

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.

Appendix A: task systems

Original task graphs for tasks used in the experiments are given in Fig. 9. In all task graphs, a vertex with no incoming edge is a source vertex, and similarly a vertex with no outgoing edge is a sink vertex. In the recurring real-time task model, tasks have single source and sink vertices in their task graphs and transforming such a task graph was already shown in Fig. 2. However as seen in Fig. 9, a number of tasks taken from the literature were defined in earlier task models and they have multiple source and/or sink vertices. In Fig. 8, we show how these task graphs are transformed so that the transformed task graphs have single source and sink vertices. There exist three different cases: (1) tasks with multiple sink vertices, (2) tasks with multiple source vertices, and (3) tasks with multiple source and sink vertices. In Figs. 8(a)–(c), one example of a transformed task graph is given for each case.

Alternative to the examples in Fig. 8, we could also add dummy vertices to original task graphs and subsequently use the standard procedure (explained in Section 2.2) to transform them. However, this would unnecessarily increase the number of dummy vertices in the transformed task graphs, which in turn would increase run-times for T.rbf(t) calculations.

Although not explicitly mentioned previously, it should be clear from its input that Algorithm 2 actually operates on the original task graphs. Hence, the schedulability condition is tested only once for all vertices (i.e. subtasks) on each iteration of the algorithm.

Finally, in Table 3 we provide values used in the experiments for each task system that we have synthesized using tasks in Fig. 9. The values are given with respect to original task graphs rather than transformed task graphs. In addition, we should also note that during all experiments, inter-triggering separations were set equal to deadlines, i.e. p(u, v) = d(u) for all u, v ∈T in all task systems.