Home | Legals | Sitemap | KIT

Scheduling Theory in Real-Time Systems

Scheduling Theory in Real-Time Systems
type: Vorlesung (V)
semester: WS 13/14

50.34 Raum -108


Mondays, 14:00-15:30

lecturer: Prof.Dr. Jian-Jia Chen
sws: 2
lv-no.: 24075

Real-time systems play a crucial role in many applications, such as avionic control systems, automotive electronics, telecommunications, industrial automation, and robotics. Such safety-critical applications require high reliability in timing assurance to prevent from serious damage to the environment and significant human loss.

In this course, we will study scheduling theories to provide formal design and verification of real-time systems. The main objectives are to introduce the basic concepts of real-time scheduling, illustrate the most significant and state-of-the-art results in the field, and provide the basic methodologies for designing predictable computing systems which can be used to support critical control applications. The following subjects will be covered in the course:

* Introduction to Task Models and Scheduling
* Uniprocessor Scheduling for Periodic/Sporadic Tasks
* Resource Sharing and Priority Inversion
* Resource Reservation Servers (TBS, CBS, PS, SS, and DS)
* Worst-Case Execution Time Analysis
* Multiprocessor Scheduling
* Real-Time Calculus
* Schedulability with Resource-Sharing for Multiprocessor
* Real-Time Kernel Design


A basic background in algorithm analysis, data structures, and discrete math will be assumed.


Giorgio C. Buttazzo, “Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications”, Springer, Second Edition, 2004. ISBN: 0-387-23137-4


Session Agenda
21.10.2013 Organization slides
28.10.2013 Worst-Case Execution Time Analysis

slides handout


04.11.2013 Task Models and Scheduling

slides handout

11.11.2013 Schedulability Analysis for Uniprocessor Systems I

slides handout


Schedulability Analysis for Uniprocessor Systems II

(contents related to arbitrary-deadlines were skipped)

12.11.2013 Resource Augmentation  

 The two sessions on 12.11.2013 will be hosted in Room 001, Building 40.28, from 2 pm to 5:15 pm.

18.11.2013 Real-Time Calculus slides, handout,
reference1, reference2

Resource Augmentation

Timed Automata and Its Application in Real-Time Systems

slides, handout
02.12.2013 Resource Sharing and Servers 

slides, handout

slides, handout

(update on Dec.16,2013 for

correcting C_n in Page 33)

09.12.2013 no lecture (conference trip)  
16.12.2013 Multiprocessor Scheduling (Introduction)

slides, handout

23.12.2013 no lecture (holiday)  
30.12.2013 no lecture (holiday)  
06.01.2014 no lecture (holiday)  
13.01.2014 Multiprocessor Scheduling – II

slides , handout 

27.01.2014 Multiprocessor Scheduling – III slides
27.01.2014 Advanced Topics: Mixed Criticality, Multicore, and Conclusion slides