SME
Embedded Systems · Problem type
Earliest deadline first
Use this for “Tasks (C, T) = (2, 5), (2, 7), (1, 10) ms: can EDF schedule them? Can rate-monotonic promise to?”
Diagram
U = 2/5 + 2/7 + 1/10 = 0.7857 ≤ 1: EDF meets every deadline.
The job with the earliest deadline runs first.
Each arrow is a release and the last job’s deadline.
The pattern repeats every hyperperiod, 70 ms.
This is an example. Type your own values to start a new problem.
U
=
C₁
T₁
+
C₂
T₂
+
C₃
T₃
URM
Rate-monotonic bound
worked out (not typed)
S
Rate-monotonic verdict
worked out (not typed)
E
EDF verdict
worked out (not typed)
Formulas
U
=
C₁
T₁
+
C₂
T₂
+
C₃
T₃
0.7857
=
2
5
+
2
7
+
1
10
E
:
compare
U
with
1
0.7857 ≤ 1, so schedulable
URM
=
3
×
(
2
1
3
−
1)
0.7798
=
3
×
(
2
1
3
−
1)
S
:
compare
U
with
URM
and
1
0.7857 > 0.7798, so no guarantee
Assumptions
•
Independent periodic tasks, each due by its next release (deadline = period).
•
EDF runs the waiting job whose deadline is nearest, so any set with U ≤ 1 meets every deadline.
•
Rate-monotonic promises only up to n(21/n − 1), 0.780 for 3 tasks.
Step-by-step
WE KNOW
C₁ = 2 ms, T₁ = 5 ms, C₂ = 2 ms, T₂ = 7 ms, C₃ = 1 ms, T₃ = 10 ms
FIND
utilization (U), EDF verdict (E), rate-monotonic bound (URM), rate-monotonic verdict (S)
Step 1 · Find utilization (U)
Use U = C₁ ÷ T₁ + C₂ ÷ T₂ + C₃ ÷ T₃
Each task’s share of the processor is its run time over its period; the shares add.
U
=
2
5
+
2
7
+
1
10
U
=
0.4
+
0.2857
+
0.1
U
=
0.7857
Step 2 · Find EDF verdict (E)
Use E: compare U with 1
The tasks fit in the processor’s time, so EDF meets every deadline.
0.7857 ≤ 1: schedulable
E
=
compare
0.7857
with
1
E
=
schedulable
Step 3 · Find rate-monotonic bound (URM)
Use URM = 3 × (21/3 − 1)
Liu and Layland’s bound with n = 3 tasks: at or below it, rate-monotonic meets every deadline.
URM = 0.7798
Step 4 · Find rate-monotonic verdict (S)
Use S: compare U with URM and 1
U
is
above
the
bound
but
within
1:
the
bound
promises
nothing,
so
check
the
response
times.
0.7857 > 0.7798: no guarantee
S
=
compare
0.7857
with
0.7798
and
1
S
=
no
guarantee
Check
Put the numbers back in. Both sides should match.
0.7857
=
2
5
+
2
7
+
1
10
✓
0.7857 ≤ 1, so schedulable ✓
0.7798
=
3
×
(
2
1
3
−
1)
✓
0.7857 > 0.7798, so no guarantee ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.