Deadline Monotonic Analysis (DMA)

What is Deadline Monotonic Analysis?

• DMA is a fixed-priority scheduling algorithm used for real-time systems.
• The priority of each task is assigned based on its deadline: tasks with shorter deadlines have higher priority.
• Only cases where the deadline $D_i$ is less than or equal to the task period $T_i$ are considered: $D_i\le T_i$.
• DMA is suitable for periodic and sporadic tasks, but not for aperiodic tasks since they do not have a fixed $T_i$.

Types of Tasks

1. Periodic Task: Has a known, fixed period $T_i$, with a repeating pattern.
2. Sporadic Task: Requests are not periodic, but there is a minimum time $T_i$ between two subsequent requests.
3. Aperiodic Task: No specified $T_i$; requests can occur at any time without a known pattern.

Worst-Case Response Time Calculation

To calculate the worst-case response time of a task $i$, the iterative formula used is:

$$R_i^{(n+1)}=C_i+I_i=C_i+\sum _{k\in hp(i)}\lceil \frac{R_i^{(n)}}{T_k}\rceil C_k$$

Where:

• $R_i^{(n+1)}$ is the response time in the $n+1$ iteration.
• $C_i$ is the computation time of task $i$.
• $I_i$ is the total interference time from higher priority tasks.
• $hp(i)$ represents the set of tasks with higher priority than task $i$.
• $T_k$ is the period of a higher priority task $k$.
• $C_k$ is the computation time of a higher priority task $k$.

Explanation of Terms

• The term $\lceil \frac{R_i^{(n)}}{T_k}\rceil$ calculates how many times the higher priority task $k$ will execute within the response time of task $i$.
• The sum adds the computation times of all these executions to determine the interference $I_i$.

Iterative Calculation Steps

1. Initialize: Set $R_i^{(0)}=C_i$.
2. Iterate: Calculate $R_i^{(n+1)}$ using the above formula.
3. Convergence Check: If $R_i^{(n+1)}=R_i^{(n)}$, the iteration stops.
4. Deadline Check: Verify if $R_i\le D_i$. If true, the task meets the deadline.

Jitter Calculation

Jitter is the variability in the response time or delay for a task.

$$\text{Jitter}=d_{\text{max}}-d_{\text{min}}$$

Where:

• $d_{\text{max}}$ is the maximum delay.
• $d_{\text{min}}$ is the minimum delay.

With and Without Global Time

• With Global Time: The jitter calculation remains as above.
• Without Global Time: The formula changes to: $$\text{Jitter}=2d_{\text{max}}-d_{\text{min}}$$

Priority Assignment

If two tasks have equal deadlines, secondary conditions such as computation time or laxity can be used to determine priority:

• Laxity is defined as $L_i=D_i-C_i$.
• A task with smaller laxity is typically assigned higher priority.

Interference Time Calculation

The interference time $I_i$ for a task $i$ is calculated as:

$$I_i=\sum _{j\in hp(i)}\lceil \frac{R_i}{T_j}\rceil C_j$$

Where:

• $hp(i)$ denotes the set of higher-priority tasks than task $i$.