Shown below are two sets of real-time, periodic tasks. For (a), will the schedul

Question

Shown below are two sets of real-time, periodic tasks. For (a), will the schedule produced by the Earliest Deadline First algorithm meet all the deadlines? For (b), will the scheduled produced by the Deadline Monotonic algorithm meet all the deadlines?

Ti si di pi ei
T1 3 4 4 1
T2 1 5 6 2
T3 2 3 3 1
(a)

Ti si di pi ei
T1 0 3 4 1
T2 3 4 4 1
T3 2 2 2 1
(b)

Explanation / Answer

(a) Earliest Deadline First can guarantee that all deadlines are met if CPU utilization is not more than 100% = 1/4 + 2/6 + 1/3 = 0.916 = 91.6% Since the CPU utilization is < 100%, all the deadlines are met. (b) The priority ordering of the tasks is Pr(T3) > pr(T1) > pr(T1) Checking for T3: 1 msec < 2 msec. Hence, T3 will meet its first deadline. Checking for T1: (1 + 1) < 3 Hence T1 will meet its first deadline. Checking for T2: We consider (2e1 + e2 + 2e3) since T3 and T1 occur twice within the first deadline of T2. (2(1) + 1 + 2(1)) > 4 Therefore, T2 will not meet its deadline. Therefore, the given task set is not schedulable under Deadline Monotonic Algorithm

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.