Real-Time Scheduling (182.086)

[TISS-Seite] [TISS Syllabus] [Background info] [Enrolling] [Grading] [Homework] [SCHEDULE] [Other resources]

News

March 2, 2021: Due to a hardware breakdown in a central switch, neither our webpage nor our LAN has been working today, when the introductory lecture should have happened. I hence dave to defer it to next week and have updated the schedule accordingly. Sorry for the inconvenience.

March 1, 2021: Unfortunately, like in SS2020, the Corona restrictions do not allow me to teach this lecture in the only format that is adequate for advanced academic teaching, namely, interactively in a lecture room: It is absolutely impossible to simulate the level of interaction achievable with presence lectures and classroom homework presentations on-line, and online quizzes and exams are ineffective and a pain in the ass for everybody. I hence had to change the organization of the course, and apologize in advance for the inevitable degradation of quality. More specifically, all homework presentations and quizzes have been dropped. To encourage you to also master the material taught in the lectures, however, students presentations have been added.

Note that I will do live streaming of my lecture (that will take place exactly as given in the schedule below) NOT from HS17 via LectureTube Live, as originally planned, but rather from the library of the ECS group E191-02, which allows me to use ZOOM. Unfortunately, I am not allowed to permit "ordinary" students to join me in the lecture room :-), as only TU Wien employees are allowed to enter and use our facilities.

On-line participation details

Aim

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.

ECTS-Breakdown (3 ECTS = 75 hours):

  24       Lecture time

   6        Student presentations
   9        Preparation time for student presentations
 36        Preparation time for 2 homework assignments  (2-3 exercises each): Single version (in LaTeX)

Subject

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.


Lecturer

Prof. Ulrich Schmid

Homepage

https://ti.tuwien.ac.at/ecs/teaching/courses/rt_sched

 

BACKGROUND INFO

This is a graduate-level theoretical course on real-time scheduling, primarily based on the 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. [A number of copies is available in the in the Lehrbuchsammlung of the TU library.] The emphasis is on the mathematical analysis of real-time scheduling algorithms. A nice "practical" overview of the topics dealt with in this course can be found in C. J. Fidge. Real-time scheduling theory. SVRC Services (UniQuest Pty Ltd) Consultancy Report 0036-2, April 2002. Prepared for the Air Operations Division, Defence Science and Technology Organisation. A general account on real-time computing is John A. Stankovic: Misconceptions About Real-Time Computing. IEEE Computer 21(10): 10-19 (1988).

Recommended prerequisites are real-time systems basics (level of 182.713 Real-Time 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 "push-based", it is essentially "pull-based": You should view this course an an opportunity to develop a coherent and in-depth understanding of real-time 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 on-line 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.]

ENROLLING

Please enrol in TISS, which will also assign you to the TUWEL course RTSCHED-2021S.

GRADING

Grading will be based on the following components:

  • Homework assignments (65%): There will be 2 paper exercises, to be worked out in LaTeX; the details can be found below.
  • Presentations (35%): For the lecture parts Fundamentals of EDF scheduling, Busy period + Response time analysis of EDF, and EDF under Overloads, there will be a student presentation event where I will ask students, selected on the spot, to present some topic from the already given lectures (on the respective chapter) and ask related questions. These presentations shall encourage you to really master the things that have been taught :-). You can either use my slides in your presentation, which must be in English, but can also prepare your own slides or use any other suitable form of on-line presentation.

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

HOMEWORK

All homework assignments are to be worked out in LaTeX using our resources (hw.texfirstpage.tex). The LaTeX source files of the assignments will be provided in the appropriate task in TUWEL course RTSCHED-2021S  - just compile hw.tex or hwnotitle.tex (with the macro \homeworknumber set accordingly).

For every homework assignment, the procedure is as follows:

  1. Download the current assignment as soon as it is announced. There will be a clarification meeting in class soon after the announcement.
  2. Work out all the exercises in LaTeX (in English) and upload your solutions (.pdf) in TUWEL by the scheduled time.

SCHEDULE

The tentative schedule is shown in the table below. All lectures will be streamed from the library of the ECS Group E191-02 via ZOOM; the link is available in the TUWEL course RTSCHED-2021S (requires registration via TISS).

 

Day Date :   Time :   Topic Reading material
Tue 02.03.2021   14:15   Lecture Introduction - canceled due to hardware breakdown Intro slides
Tue 09.03.2021   14:15   Lecture Introduction, Basic Model Intro slides, Ch. 2
Tue 16.03.2021   14:15   Lecture Fundamentals of EDF scheduling Ch. 3
Mon 22.03.2021 23:59 Announce Homework 1
Tue 23.03.2021   14:15   Clarification Homework 1 Ch. 3
Lecture Fundamentals of EDF scheduling  (cont.)
Tue 13.04.2021   14:00   Student presentations 1 (Fundamentals of EDF) Ch. 3
Tue 20.04.2021 14:00 Busy period analysis
Ch. 3
Tue 27.04.2021   14:15   Lecture Response time analysis of EDF Ch. 4
Sun 02.05.2021   23:59   Homework 1 due  
Tue 04.05.2021   14:15   Lecture Response time analysis of EDF (cont.) Ch. 4
Tue 11.05.2021 14:00 Student presentations 2 (Busy period and response time analysis)
Fri 14.05.2021   23:59   Announce Homework 2  
Tue 18.05.2021   14:15   Clarification Homework 2 Ch. 5.1
Lecture EDF under overloads
Tue 25.05.2021   14:15   Lecture EDF under overloads (cont.)

Ch. 5.1

Tue 01.06.2021 14:15 Lecture EDF under overloads (cont.) Ch. 5.1
Tue 08.06.2021   14:15   Student presentations 3 (EDF under overloads)
Tue 15.06.2021   14:15   Lecture EDF scheduling with shared resources Ch. 6
Sun 20.06.2021   23:59   Homework 2 due  
Tue 22.06.2021   14:15   Lecture EDF scheduling with shared resources (cont.) Ch. 6
Tue 29.06.2021   14:15   Lecture EDF scheduling with shared resources (cont.) Ch. 6
         

OTHER RESOURCES

Recommended additional books/papers:

  • Giorgio Buttazzo, HARD REAL-TIME 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 real-time systems papers:

  • Journals:
    • Real-Time Systems
    • Journal of Scheduling
  • Conference proceedings:
    • IEEE Real-Time Systems Symposium (RTSS)
    • IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
    • IEEE Int. Symposium on Object-oriented Real-time distributed Computing (ISORC)
    • Real-Time and Embedded Computing Systems and Applications (RTCSA)
    • Euromicro Conference on Real-Time Systems
    • International Conference on Principles of Distributed Systems (OPODIS)
  • The world-wide-web: Most papers are available on-line, freely accessible for academic institutions like TU Vienna. Here are some very useful links:

Miscellaneous: