CS-321: Real-time systems
"Is it possible to pass an exam by starting to study three days before the exam? Lets find out" - Every student ever
This compendium is made for the course CS-321 Real-time systems at École Polyteqnique Fédérale de Lausanne (EPFL) and is a summary of the lectures and lecture notes. Is is not the complete curriculum, but rather a list of reading material.
Scheduling
Task taxonomy
$C_i$ : Max computation time$D_i$ : Relative deadline$T_i$ : Period / Minimum interarrival time
Rate monotonic - Guaranty function
- Necessary condition:
$$\sum_{i=1}^{n} \Big( \frac{C_i}{T_i} \Big) \leq 1$$ - Sufficient condition:
$$\sum_{i=1}^{n} \Big( \frac{C_i}{T_i} \Big) \leq n \Big( 2^{1/n} - 1 \Big)$$
Jacksone rule:
Any sequence is optimal that puts the jobs in order of non decreasing due dates.
Deadline monotonic
TODO
Algorithms
Earliest deadline first (EDF)
Assumptions:
- Task deadlines
$D_i$ are arbitrary - Tasks are preemptive and independent
- Task cannot block or suspend themselves
- The worst execution time
$C_i$ of a task$i$ is known
Algorithm: At each instant, execute a ready task with the closest deadline.
Mutual exclusion
Stack Resourse Policy (SRP)
To aovid deadlocks, a task should not be allowed to start unless the resources available at this instant are sufficion to staisgu all its needs.
Jitter
Variation in execution period for periodic tasks.
Possible solutions:
- Give highest priority to the task that has jitter constraints
- Use periods that are in harmonic relationship and all other taks with lower priorities
- Separate task IO from processing and five higher priority to IO