# 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