After successful completion of the course, students are able to...

• become familiar with task models, scheduling algorithms, feasibility and optimality results and associated proof techniques,
• apply existing results in new situations,
• devise and analyze new scheduling algorithms for special purposes.

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 and has the following content:

• 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.

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.

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)

 Quizzes; Solution and presentation of homework assignments; participation in discussions in class

Ort: in 1. Vorlesung

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

Advantageous are real-time systems basics (e.g. 182.713 Real-Time Systems) and elementary complexity theory (e.g. in 185.291 Formale Methods in Computer Science).