Home | Legals | Sitemap | KIT

Scheduling Theory in Real-Time Systems

Scheduling Theory in Real-Time Systems
type: Vorlesung (V)
chair: Chair of Micro Hardware Technologies for Automation
semester: WS 12/13
place:

50.34 Raum -108

time:

Mondays, 14:00-15:30 weekly

lecturer: Prof.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, Third Edition, 2011.  ISBN: 978-1-4614-0675-4 (Print) 978-1-4614-0676-1 (Online)  http://link.springer.com/book/10.1007/978-1-4614-0676-1/page/1 (You can download the e-copy from KIT network)

 

Schedule:

Date Description Material
15.10.2012 0. Organization and Introduction  slides
22.10.2012 1. Task Models and Scheduling  slides
29.10.2012 no lecture (conference trip)  
05.11.2012 no lecture (conference trip)  
12.11.2012 2. Worst-Case Execution Time Analysis

 slides, handout

 reference

19.11.2012

3. Schedulability Analysis for Uniprocessor Systems I

4. Schedulability Analysis for Uniprocessor Systems II

(Exercises in Chapter 4 in Buttazzo's textbook)

 slides, handout

26.11.2012 5. Resource Augmentation  slides, handout
03.12.2012 6. Resource Sharing and Servers  slides, handout
10.12.2012 no lecture (conference trip)  
17.12.2012 7. Real-Time Calculus

 slides, handout,
 reference1, reference2

24.12.2012 no lecture (holiday)  
31.12.2012 no lecture (holiday)  
07.01.2013 8. Multiprocessor Scheduling I  slides, handout
14.01.2013 9. Multiprocessor Scheduling II  slides
21.01.2013 10.Multiprocessor Scheduling III  slides, handout
28.01.2013

11. Advanced Topics: Mixed Criticality, Timed Automata, Multicore

 slides (updated on 30/01/13)

 slides, slides (excluded for exams)

04.02.2013 12. Further Topics and Conclusion  slides