Home | Legals | Sitemap | KIT

Scheduling Theory in Real-Time Systems

Scheduling Theory in Real-Time Systems
type: lecture
chair: Chair of Micro Hardware Technologies for Automation
semester: >=5
place:

SR 119 at Faculty of Informatics, Gebäude 50.34

time:

Mondays, 14:00-15:45 weekly

start: 17.10.2011
lecturer:

Juniorprofessor Dr. Jian-Jia Chen

sws: 2
ects: 3
lv-no.: 24075

Course Description: 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
 

Prerequisite: Computer Operating Systems or equivalent.  A basic background in algorithm analysis, data structures, and discrete math will be assumed.

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

 

Schedule: 

Date Topic  Slides/handout
 17.10.2011 Introduction  slides
 24.10.2011 Task Models and Scheduling  slides, handout
 31.10.2011 Schedulability Analysis for Uniprocessor Systems I    see next
 07.11.2011 Schedulability Analysis for Uniprocessor Systems II  slides, handout
 14.11.2011

Schedulability Analysis for Uniprocessor Systems III
Resource Augmentation Analysis

 slides, handout
 21.11.2011 Worst-Case Execution Time Analysis

 slides, handout

 reference

 28.11.2011 Break  
 05.12.2011 Real-Time Calculus

 slides,

reference 1

reference 2

 12.12.2011 Resource Sharing and Servers  slides,
 19.12.2011 Multiprocessor Scheduling I: Partitioned Scheduling   slides, handout
 09.01.2011 Multiprocessor Scheduling II: Global Scheduling  slides
 16.01.2011 Multiprocessor Scheduling III: Semi-Partitioned Scheduling  slides
 23.01.2011 Formal Methods and Multiprocessor Resource Sharing

 slides-1

 slides-2

 30.01.2011 Further Topics and Conclusion  slides

Errata:

[updated on Dec. 04, 2012] (slides) Resource Sharing and Servers: Pages 26 and 29 - \tau_2 = (2, 6, 6) instead of (2, 4, 4)

[updated on Jan. 14, 2013] (slides) Global Scheduling: Page 29 - Global EDF instead of Global DM