Real-time scheduling, i.e., determining the sequence of execution of tasks with deadlines, is a central problem in critical embedded systems. Their design must ensure that the timing constraints imposed by the surrounding physical system can be guaranteed. The (inherentily complex) worst-case response time and feasibility analysis of tasks under scheduling algorithms like earliest deadline first is hence of great importance. This graduate-level optional course provides an introduction into theory and mathematical analysis of scheduling algorithms for real-time systems. It allows its attendees to: (1) become familiar with task models, scheduling algorithms, feasibility and optimality results and associated proof techniques, (2) be able to apply existing results in new situations, (3) be able to devise and analyze new scheduling algorithms for special purposes.
The course is organized in the "anglo-american style", which is based on continuous engagement during the whole semester: Quizzes and homework assignments ensure (1) that the topics taught in the lecture are efficiently acquired, and (2) that the individual analytic problem-solving skills are trained.
Earliest Deadline First (EDF) scheduling: Optimality and complexity analysis, feasibility analysis, response time analysis, competitive analysis under overloads, EDF scheduling with shared resources and precedence constraints.
ECTS-Breakdown (3 ECTS = 75 hours):
24 Lecture time
2 2-3 Quizzes
4 2 Homework presentations
9 Preparation time for 2-3 Quizzes
36 Preparation time for 2 homework assignments (2-3 exercises each): Single version (in LaTeX)
Textbook: John A. Stankovic, Marco Spuri, Krithi Ramamritham, Giorgio C. Buttazzo: Deadline Scheduling for Real-Time Systems, Kluwer Academic Publishers (now Springer Verlag), 1998, ISBN 0-7923-8269-2