Real-Time Scheduling
Kluwer Academic Publishers eBooks · 2006
OverviewMany thousands of research papers have been written about how to schedule a set of tasks in a system with a limited amount of resources such that all tasks will meet their deadlines. This chapter tries to summarize some important results that are relevant to the designer of real-time systems. The chapter starts by introducing the notion of a schedulability test to determine whether a given task set is schedulable or not. It distinguishes between a sufficient, an exact, and a necessary schedulability test, A scheduling algorithm is effective if it will find a schedule whenever there is a solution. The adversary argument shows that in the general case it is not possible to design an effective on-line scheduling algorithm.Section 11.3 covers the topic of dynamic scheduling. It starts with looking at the problem of scheduling a set of independent tasks by the rate-monotonic algorithm. Next, the problem of scheduling a set of dependent tasks is investigated. After the kernelized monitor, the priority-ceiling protocol is discussed and a schedulability test for the priority ceiling protocol is presented. Finally, the scheduling problem in distributed systems is touched.The final section elaborates on static scheduling. The concept of the schedule period is introduced and an example of a simple search tree that covers a schedule period is given. A heuristic algorithm has to examine the search tree to find a feasible schedule. If it finds one, the solution can be considered a constructive schedulability test. The flexibility of static schedules can be increased by introducing a periodic server task to service sporadic requests. Finally, the topic of mode changes to adapt the temporal control structure even further is discussed.