SME
Embedded Systems
Real-time constraints
Use this for “Can tasks (C, T) = (1, 4), (2, 8), (3, 12) ms be scheduled rate-monotonically?”
Diagram
U = 1/4 + 2/8 + 3/12 = 0.75 ≤ 0.780, the bound for 3 tasks: rate-monotonic meets every deadline.
The shorter period runs first and takes the processor whenever it is released.
Each arrow is a release and the last job’s deadline.
The pattern repeats every hyperperiod, 24 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)
Formulas
U
=
C₁
T₁
+
C₂
T₂
+
C₃
T₃
0.75
=
1
4
+
2
8
+
3
12
URM
=
3
×
(
2
1
3
−
1)
0.7798
=
3
×
(
2
1
3
−
1)
S
:
compare
U
with
URM
and
1
0.75 ≤ 0.7798, so guaranteed
Assumptions
•
Independent periodic tasks, each due by its next release (deadline = period).
•
Rate-monotonic: the shorter period has the higher priority and preempts at once.
•
U ≤ n(21/n − 1) guarantees every deadline; above it, the response-time test decides.
Step-by-step
WE KNOW
C₁ = 1 ms, T₁ = 4 ms, C₂ = 2 ms, T₂ = 8 ms, C₃ = 3 ms, T₃ = 12 ms
FIND
utilization (U), 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
=
1
4
+
2
8
+
3
12
U
=
0.25
+
0.25
+
0.25
U
=
0.75
Step 2 · 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 3 · Find rate-monotonic verdict (S)
Use S: compare U with URM and 1
U
is
within
the
bound,
so
rate-monotonic
meets
every
deadline.
0.75 ≤ 0.7798: guaranteed
S
=
compare
0.75
with
0.7798
and
1
S
=
guaranteed
Check
Put the numbers back in. Both sides should match.
0.75
=
1
4
+
2
8
+
3
12
✓
0.7798
=
3
×
(
2
1
3
−
1)
✓
0.75 ≤ 0.7798, so guaranteed ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.