Skip to main content

Embedded Systems · Serial buses and communication protocols

A brushless-DC commutation computer runs two independent implicit-deadline periodic…

Problem

Embedded Systems practice problem

A brushless-DC commutation computer runs two independent implicit-deadline periodic tasks on a fully preemptive uniprocessor under either rate-monotonic or earliest-deadline-first (EDF) scheduling. Zero jitter, zero blocking, and zero overhead are assumed. Times:τ1: C1=2.00 ms, T1=5.00 ms,τ2: C2=4.00 ms, T2=7.00 ms.\tau_1:\ C_1=2.00\,\mathrm{ms},\ T_1=5.00\,\mathrm{ms},\qquad \tau_2:\ C_2=4.00\,\mathrm{ms},\ T_2=7.00\,\mathrm{ms}.For implicit-deadline independent periodic tasks, EDF on a uniprocessor is schedulable if and only if U≤1U\le 1. RM uses the Liu--Layland sufficient bound Ulub(2)=2(2−1)U_{\mathrm{lub}}(2)=2(\sqrt{2}-1) and the exact recurrenceRi(0)=Ci,Ri(k+1)=Ci+∑h∈hp(i)⌈Ri(k)Th⌉Ch,R_i^{(0)}=C_i,\qquad R_i^{(k+1)}=C_i+\sum_{h\in hp(i)}\Bigl\lceil\frac{R_i^{(k)}}{T_h}\Bigr\rceil C_h,with a pass only if the least fixed point satisfies Ri≤TiR_i\le T_i.

(a) Compute UU as an exact rational and as a decimal to four places. Compute Ulub(2)U_{\mathrm{lub}}(2) to four places. Decide the Liu--Layland RM test and the EDF utilization test.

(b) Under RM, with τ1\tau_1 strictly higher priority, compute R1R_1 and the iterates of R2R_2. Decide both RM deadlines.

(c) Under EDF, construct the synchronous schedule over one hyperperiod H=lcm(T1,T2)H=\mathrm{lcm}(T_1,T_2). For every job, report release time, absolute deadline, execution intervals, and completion time. Decide every deadline.

(d) A third implicit-deadline task τ3\tau_3 with C3=0.20 msC_3=0.20\,\mathrm{ms} and T3=35.0 msT_3=35.0\,\mathrm{ms} is added. Recompute UU. Decide EDF. Under RM with priorities by period (τ1>τ2>τ3\tau_1>\tau_2>\tau_3), decide whether τ2\tau_2 can become schedulable merely because a lower-priority task was added, and recompute R2R_2 to confirm.

Hint

Hint

Implicit-deadline EDF is a utilization test; RM needs either Liu--Layland or an exact response-time fixed point.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Embedded Systems sample problem: Try the free sample problem.

More Embedded Systems practice problems

Back to Embedded Systems

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.