Question

Can you guarantee that a feasible schedule exists without a simulation of the schedule or time demand analysis, if
(a) The set of tasks T = {(5, 2),(8, 3),(10, 1)} is scheduled by the rate-monotonic algorithm.
(b) The set of tasks T = {(3, 1),(6, 1),(18, 6),(36, 4)} is scheduled by the least-slack-time-first algorithm.
(c) The set of tasks T = {(3, 1),(0, 6, 1, 4),(18, 6),(36, 4)} is scheduled by the earliest-deadline-first algorithm.
(d) The set of tasks T = {(3, 1),(6, 1),(18, 6),(36, 4)} is scheduled by the deadline-monotonic algorithm

Answer 1

Answer on Question #53582, Engineering / Software Engineering

Task:

1. Can you guarantee that a feasible schedule exists without a simulation of the schedule or time demand analysis, if

(a) The set of tasks $T = \{(5, 2), (8, 3), (10, 1)\}$ is scheduled by the rate-monotonic algorithm.

(b) The set of tasks $T = \{(3, 1), (6, 1), (18, 6), (36, 4)\}$ is scheduled by the least-slack-time-first algorithm.

(c) The set of tasks $T = \{(3, 1), (0, 6, 1, 4), (18, 6), (36, 4)\}$ is scheduled by the earliest-deadline-first algorithm.

(d) The set of tasks $T = \{(3, 1), (6, 1), (18, 6), (36, 4)\}$ is scheduled by the deadline-monotonic algorithm

Answer:

(a) Since the utilization $U = 2/5 + 3/8 + 1/10 = 0.875 > U_{\text{RM}}(3)$, there is no guarantee that there is a feasible schedule.

(b) Since the utilization $U = 0.944 \leq U_{\text{LST}} = 1$, there exists a feasible schedule.

(c) Since the relative deadline of the task $(0, 6, 1, 4)$ is smaller than the period, we have to calculate the density $\Delta = \sum_{i=1}^{3} \frac{e_i}{\min(p_i, D_i)}$ of the set of tasks, which is $\Delta = 1.027 > 1$. Thus there is no guarantee that there is a feasible schedule.

(d) Since this is a set of simply periodic tasks and $U = 0.944 \leq 1$, there exists a feasible schedule.

https://www.AssignmentExpert.com