IA158 Real Time Systems
Exam manual
This manual specifies the knowledge demanded at the IA158 exam. Please keep
in mind that the knowledge described below is mandatory even for the E grade.
Missing a single part automatically means an F. You may repeat the exam as
often as you wish (at the official exam dates); only the best grade goes into the
information system.
• Slides 42 - 59: You must know all definitions formally, using the mathematical
notation if present. In particular, you need to be able to specify
all components of the abstract real-time system’s model. The definition
of the schedule from the slide 97 does not have to be completely formal,
you just have to know, what is assigned to what.
• Slides 60 - 70. You must know the algorithms (EDD/EDF) and that
the non-preemptive case is NP-hard in general. You must be able to
explain intuitively why they are optimal (using, e.g., a picture from the
whiteboard). No need to present the formal proof (slides 63 and 68-69).
• Slides 77 - 87. You must know all definitions (especially slide 80). You
do not have to memorize the 4-tuple notation. Note that you must know
the difference between clock-driven and priority-driven scheduling, offline
vs online, etc.
• Slides 88 - 98. You must know and understand all definitions here. In
particular, you must understand the basic algorithms, the definition of
(maximum) schedulable utilization, etc.
• Slides 100 (optimality of EDF) and 108-109 (density and schedulability
test for EDF): You must know this. The rest of the interval between
slides 99 and 109 is omitted.
• Slides 111 - 120. You must know all definitions and formulations of theorems.
You may omit proofs.
• Slides 126 - 133. You have to know and understand everything in detail.
In particular, the critical instants, the time-demand analysis algorithm
(note that the formula for wi(t) is not a complete algorithm), etc.
• Slides 134 - 148. You have to know everything in detail. In particular,
both servers (polling and deferrable), the time demand analysis for the
deferrable server, including the critical instant and the algorithm itself,
etc.
• Slides 156 - 167. Everything is in detail except the proof of Thm 24
(slide 161).
1
• Slides 168 - 198 except the slide 190. You have to know and understand everything
in detail. In particular, all the issues with resources (unbounded
priority inversion, deadlock, timing anomalies), all three algorithms. In
the case of the blocking time (slide 188), you may assume that the critical
sections are not nested. You do not need to know the proof of Theorem 29,
just the formulation (first three lines).
• Slides 204 - 229. Everything here except that you do not have to memorize
the examples on slides 213 and 215 (you may, of course, be asked to
provide your examples illustrating simpler phenomena). In particular, the
scheduling taxonomy, the fundamental limit, the Dhall’s effect, etc.
2