Goal
After introducing the two most widely used scheduling algorithms for real-time tasks, the course will enter into the optimal design problem. While the feasiblity problem requires to check whether or not the real-time constraints can be guaranteed assuming that all task set parameters are known, in the optimal design problem the task set is only partially specified and the unknown parameters are set after solving an optimization procedure. One of the earliest examples of optimal design problem is due to Seto [1].
[1] D. Seto, J. P. Lehoczky, L. Sha, and K. G. Shin. "On task schedulability in real-time control systems." In Proceedings of the 17th IEEE Real-Time Systems Symposium, pages 13-21, Washington (DC), U.S.A., Dec. 1996.
Prerequisites
Familiarity with optimization tecniques (Lagrange multipliers, KKT conditions, branch and bound) is certainly helpful.
Course organization
The course will be held in Seminarierummet (M2498) on the following dates:
Some notes are available (last update: 11/11/2012). They are mostly the same as the slide plus all the references to the literature.
The course is worth 7.5 ECTS credits. To be granted such credits, students will have to complete the homeworks, plus to illustrate the homeworks with the teacher. Homeworks must be written in LaTeX.
- homework 1 to be submitted by email not later than Thursday Nov. 1st at 10:00
- homework 2 to be submitted by email not later than Thursday Nov. 8th at 10:00
- homework 3 to be submitted by email not later than Sunday Nov. 18th at 23:59
The topics covered by the course are reported below:
- Real-time task model. Fixed Priorities (FP) and Rate Monotonic (RM) scheduling rules. Response time analysis. Guarantee tests are unfit for design optimization.
- Space of feasible computation times. Using sufficient tests. Space of FP-feasible periods. Optimal period assignment.
- Earliest Deadline First (EDF) scheduling rule. Exact and only-sufficient guarantee tests. Space of EDF-feasible computation times. Space of EDF feasible periods and deadlines.
- Optimal period/deadline assignment to EDF task sets.
- Hierarchical scheduling over virtual processors. Interface of virtual processors. FP and EDF schedulability conditions over virtual processors. Optimal design of interfaces.
Contacts
For further information or for receiving updates about the course, please contact the lecturer at ahmh@bnmsqnk.ksg.rd after replacing each letter with the next one in alphabetic orderd.