Question

Which of the following systems of periodic tasks are schedulable by the rate-monotonic algorithm?
By the earliest-deadline-first algorithm? Explain your answer.
(a) T = {(8, 3), (9, 3), (15, 3)}
(b) T = {(8, 4), (12, 4), (20, 4)}
(c) T = {(8, 4), (10, 2), (12, 3)}

Answer 1

Answer on Question #53575, Engineering / Software Engineering

Task: Which of the following systems of periodic tasks are schedulable by the rate-monotonic algorithm? By the earliest-deadline-first algorithm? Explain your answer.

(a) $T = \{(8,3), (9,3), (15,3)\}$

(b) $T = \{(8,4), (12,4), (20,4)\}$

(c) $T = \{(8, 4), (10, 2), (12, 3)\}$

Answer:

a) $T = \{(8,3), (9,3), (15,3)\}$

$$U_{RM}(3) \approx 0.780$$ $$U = \frac{3}{8} + \frac{3}{9} + \frac{3}{15} = 0.908 > URM$$

schedulable utilization test is indeterminate for RM, shortest period is highest priority

w1(t) = 3, W1 = 3 <= 8, T1 is schedulable
w2(t) = 3 + floor(t/8) * 3 = t
W2 = 6 <= 9, T2 is schedulable
w3(t) = 3 + floor(t/8) * 3 + floor(t/9) * 3 = t
W3 = 15 <= 15, T3 is schedulable.

All tasks are schedulable under RM, therefore the system is schedulable under RM.

$U \leq 1 \rightarrow$ the system is schedulable under EDF

b) $T = \{(8,4), (12,4), (20,4)\}$

The total utilization of tasks $= \frac{4}{8} + \frac{4}{12} + \frac{4}{20} = 1.033$

A system of independent, preemptable tasks with relative deadlines equal to their periods is schedulable if and only if their total utilization is less than or equal to 1. Therefore, T is not schedulable by RM or EDF.

Use TDA:

$$\begin{array}{l} \text{Check } t = 8, 12, 16, 20 \\ W_i(t) \leq t \\ W1(t) = 4 \leq t, \quad t = 8, 12, 16, 20 \rightarrow \text{Schedulable} \\ W2(t) = 4 + ceil(t/8) * 4 \\ W2(8) = 4 + 4 = 8 \leq 8 \rightarrow \text{Schedulable} \\ W3(t) = 4 + ceil(t/8) * 4 + ceil(t/12) * 4 \\ W3(8) = 4 + 4 + 4 = 12 \\ W3(12) = 4 + 8 + 4 = 16 \\ W3(16) = 4 + 8 + 8 = 20 \\ W3(20) = 4 + 12 + 8 = 24 \rightarrow \text{Not schedulable by RM} \\ \end{array}$$

Schedulability test of EDF algorithm: Since $Dk = Pk$, $U = 1.033 > 1$ therefore, it is not schedulable by EDF.

c) $T = \{(8, 4), (10, 2), (12, 3)\}$

The total utilization of tasks $= 4/8 + 2/10 + 3/12 = 0.95$

For RM:

The tasks are schedulable if the total utilization of tasks, U, is less or equal to $n(n^{\wedge}(1/n)-1)$ , where $n$ is the number of tasks.

$\mathrm{Urm} = n(n^{\wedge}(1 / n) - 1) = 3(2^{\wedge}(1 / 3) - 1) = 0.78 < U = 0.95 \rightarrow \text{No conclusion.}$

Use TDA:

Check $t = 8,10,12$

Wi(t) <= t

W1(t) = 4 <= t, t = 8, 10, 12 → Schedulable

W2(t) = 2 + ceil(t / 8) * 4
W2(8) = 2 + 4 = 6 <= 8 → Schedulable
W3(t) = 3 + ceil(t / 8) * 4 + ceil(t / 10) * 2
W3(8) = 3 + 4 + 2 = 9
W3(10) = 3 + 8 + 2 = 13
W3(12) = 3 + 8 + 4 = 15 → Not schedulable

Therefore, it is not schedulable by using RM.

For EDF:

According to the schedulability Test for EDF algorithm:

$$\sum_ {k = 1} ^ {n} e _ {k} / \min \left(D _ {k}, p _ {k}\right) \leq 1$$

In the case that $\mathrm{Dk} = \mathrm{Pk}$ , the expression represents the total utilization of the tasks, which we have calculated. $\mathrm{U} = 0.95$ less than one. Therefore, the periodic tasks are schedulable by EDF algorithm.

https://www.AssignmentExpert.com