RealTime Scheduling (182.086)
[TISSSeite] [TISS syllabus] [TUWEL course] [Background info] [Enrolling] [Grading] [Homework] [SCHEDULE] [Other resources]
News
Aim
Realtime 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) worstcase response time and feasibility analysis of tasks under scheduling algorithms like earliest deadline first is hence of great importance. This graduatelevel optional course provides an introduction into theory and mathematical analysis of scheduling algorithms for realtime 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 "angloamerican 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 problemsolving skills are trained.
ECTSBreakdown (3 ECTS = 75 hours):
24 Lecture time
6 Student presentations
9 Preparation time for student presentations
36 Preparation time for 2 homework assignments (23 exercises each): Single version (in LaTeX)
Subject
Realtime 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) worstcase response time and feasibility analysis of tasks under scheduling algorithms like earliest deadline first is hence of great importance.
This graduatelevel optional course provides an introduction into theory and mathematical analysis of scheduling algorithms for realtime 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.
Lecturer
Prof. Ulrich Schmid
Homepage
https://ti.tuwien.ac.at/ecs/teaching/courses/rt_sched
This is a graduatelevel theoretical course on realtime scheduling, primarily based on the textbook John A. Stankovic, Marco Spuri, Krithi Ramamritham, Giorgio C. Buttazzo: Deadline Scheduling for RealTime Systems, Kluwer Academic Publishers (now Springer Verlag), 1998, ISBN 0792382692. [A number of copies is available in the in the Lehrbuchsammlung of the TU library.] The emphasis is on the mathematical analysis of realtime scheduling algorithms. A nice "practical" overview of the topics dealt with in this course can be found in C. J. Fidge. Realtime scheduling theory. SVRC Services (UniQuest Pty Ltd) Consultancy Report 00362, April 2002. Prepared for the Air Operations Division, Defence Science and Technology Organisation. A general account on realtime computing is John A. Stankovic: Misconceptions About RealTime Computing. IEEE Computer 21(10): 1019 (1988).
Recommended prerequisites are realtime systems basics (level of 182.713 RealTime Systems), basic discrete mathematics (level of 104.271 Discrete Mathematics) and elementary complexity theory (level of 185.291 Formale Methods in Computer Science).
The syllabus can be found here, and here are the slides. Note that my slides also provide quite some material not found in the textbook, and define the actual content of the course. The textbook is sufficient for the advance reading, though (see below).
Aims & scope and requirements are quite different from undergraduate courses. It has a clear focus on scientific education and thus contribute to the development the required analytical skills and knowledge. In contrast to undergraduate courses where knowledge acquisition is more or less "pushbased", it is essentially "pullbased": You should view this course an an opportunity to develop a coherent and indepth understanding of realtime scheduling issues  it is up to you to make the best use of it!
You are encouraged to do advance reading of the textbook [and any additional material listed in the schedule below]. In fact, it is difficult to really benefit from the lectures without any advance knowledge.
Since your grade will also depend upon participation in discussions, presence in the online classes is expected.
Collaboration: Discussion of concepts with others is encouraged, but any homework must be done on your own and written up in your own words, unless otherwise instructed. If you use any source other than the textbook or my slides, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever.
[To understand the rationale of the above, it is very instructive to see how rigidly top US universities handle the issue of academic integrity, plagiarism, etc. Consult the Texas A&M University Code of Honors for an example.]
Please enrol in TISS, which will also assign you to the TUWEL course RTSCHED2022S.
Grading will be based on the following components:
 Homework assignments (45%): There will be 2 paper exercises, to be worked out in LaTeX and presented in class; the details can be found below.
 Quizzes (45%): There will be 2 short quizzes in class (1520 min.), consisting of a few simple questions (for example, short answer, truefalse, or multiple choice) concerning the material covered in the lectures since the last quiz. A sample quiz can be found here. There will be no makeup quizzes, but you can compensate one missed quiz upon taking the final exam.
 Final exam (10%): There is a final exam [optional], with questions similar to the ones in the standard quizzes, but covering all the material taught in the course. Depending on the number of participants, it can be either written (3040 min.) or oral.
You will find all grades (.pdf and the generating Excel sheet) in TUWEL. Note that participation in discussions in class etc. is also taken into account (at most +/ 10% of total points) when assigning the final grade, which will be assigned according to the following scale:
1 for 90% or above of the total points,
2 for 80 to 89%,
3 for 70 to 79%,
4 for 60 to 69%,
5 for less than 60%.
All homework assignments are to be worked out in LaTeX using our resources (hw.tex, firstpage.tex). The LaTeX source files of the assignments will be provided in TUWEL  just compile hw.tex or hwnotitle.tex (with the macro \homeworknumber set accordingly).
For every homework assignment, the procedure is as follows:
 Download the current assignment as soon as it is announced. There will be a clarification meeting in class soon after the announcement.
 Work out all the exercises in LaTeX (in English):
 Upload your solution (.pdf) in the appropriate folder in TUWEL by the scheduled time.
 Bring along a paper copy, which must be duly signed, in the next class after the deadline.
 Present your solutions, on my request, on blackboard in class at the scheduled presentation time [please make sure that you bring your own copy of your solutions along, since I will need "my" copy for taking notes!]. This presentation shall primarily give you an (additional) opportunity to find out whether your solution is OK. Therefore, the grade assigned for presentations will not be lowered when your solution contains errors. [Incorrect solutions will of course lower the grade assigned for the homework itself, however.]
SCHEDULE (UNDER CONSTRUCTION!!!)
The tentative schedule is shown in the table below. All lectures are usually on Tuesday 14:1515:45 in the lecture room EI 8 (Pötzl HS, Neues EI, Gußhaustraße 2729).
Day  Date  :  Time  :  Topic  Reading material 

Tue  01.03.2022  14:15  Lecture Introduction  Intro slides  
Tue  08.03.2022  15:15  Lecture Basic Model, Fundamentals of EDF scheduling  Ch. 2, Ch. 3  
Tue  15.03.2022  14:15  Lecture Fundamentals of EDF scheduling (cont.)  Ch. 3  
Tue  22.03.2022  14:15  Lecture Fundamentals of EDF scheduling (cont.)  Ch. 3  
Wed  25.03.2022  23:59  Announce Homework 1  
Tue  29.03.2022  14:15  Lecture Fundamentals of EDF scheduling (cont.)  Ch. 3  
Tue  05.04.2022  14:15  Lecture Response time analysis of EDF  Ch. 4  
Tue  26.04.2022  14:15  Lecture Response time analysis of EDF (cont.)  Ch. 4  
Sun  01.05.2022  23:59  Homework 1 due  
Tue  03.05.2022  14:15  Quiz1: Ch.2  Ch.4  
Presentation Homework 1  
Sun  08.05.2022  23:59  Announce Homework 2  
Tue  10.05.2022  14:15  Lecture EDF under overloads  Ch. 5.1  
Tue  17.05.2022  14:15  Lecture EDF under overloads (cont.)  Ch. 5.1  
Tue  24.05.2022  14:15  Lecture EDF scheduling with shared resources  Ch. 6  
Tue  31.05.2022  14:15  Lecture EDF scheduling with shared resources (cont.)  Ch. 6  
Tue  14.06.2022  14:15  Lecture EDF scheduling with shared resources (cont.)  Ch. 6  
Sun  19.06.2022  23:59  Homework 2 due  
Tue  21.06.2022  14:15  Quiz 2: Ch.4  Ch.6  
Presentation Homework 2 

Tue  28.06.2022  14:15  Final exam [optional] 
Recommended additional books/papers:
 Giorgio Buttazzo, HARD REALTIME COMPUTING SYSTEMS: Predictable Scheduling Algorithms and Applications, 2nd ed., Springer, 2005.
 Joseph Y.T. Leung. Handbook of Scheduling: Algorithms, models, and performance analysis. Chapman & Hall/CRC, 2004
Some selected places to look for realtime systems papers:
 Journals:
 RealTime Systems
 Journal of Scheduling
 Conference proceedings:
 IEEE RealTime Systems Symposium (RTSS)
 IEEE RealTime and Embedded Technology and Applications Symposium (RTAS)
 IEEE Int. Symposium on Objectoriented Realtime distributed Computing (ISORC)
 RealTime and Embedded Computing Systems and Applications (RTCSA)
 Euromicro Conference on RealTime Systems

The worldwideweb: Most papers are available online, freely accessible for academic institutions like TU Vienna. Here are some very useful links:
Miscellaneous: