SME
Embedded Systems · Problem type
Worst-case response time
Use this for “Find the worst-case response time of task 3 in (1, 4), (2, 8), (3, 12) ms.”
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. τ₃’s first job, released with all the others, ends at 7 ms ≤ its period 12 ms.
The pattern repeats every hyperperiod, 24 ms.
This is an example. Type your own values to start a new problem.
C₁
Run time of task 1
example
T₁
Period of task 1
example
C₂
Run time of task 2
example
T₂
Period of task 2
example
C₃
Run time of task 3
example
T₃
Period of task 3
example
R₃
Response time of task 3
worked out (not typed)
k₁
Runs of task 1 within R₃
worked out (not typed)
k₂
Runs of task 2 within R₃
worked out (not typed)
Formulas
R₃
=
C₃
+
⌈
R₃
T₁
⌉
×
C₁
+
⌈
R₃
T₂
⌉
×
C₂
7
=
3
+
⌈
7
4
⌉
×
1
+
⌈
7
8
⌉
×
2
k₁
=
⌈
R₃
T₁
⌉
2
=
⌈
7
4
⌉
k₂
=
⌈
R₃
T₂
⌉
1
=
⌈
7
8
⌉
Assumptions
•
Rate-monotonic priorities: task 1 has the shortest period, task 3 the longest.
•
All three tasks are released together at 0, the worst case for task 3.
•
Start from R = C₁ + C₂ + C₃ and repeat the formula until R stops changing.
•
Task 3 meets its deadline when R₃ ≤ T₃, its period.
Step-by-step
WE KNOW
C₁ = 1 ms, T₁ = 4 ms, C₂ = 2 ms, T₂ = 8 ms, C₃ = 3 ms, T₃ = 12 ms
FIND
response time of task 3 (R₃), runs of task 1 within R₃ (k₁), runs of task 2 within R₃ (k₂)
Step 1 · Find response time of task 3 (R₃)
Use R₃ = C₃ + ⌈R₃ ÷ T₁⌉ × C₁ + ⌈R₃ ÷ T₂⌉ × C₂
Task
3’s
own
run
plus
each
job
of
tasks
1
and
2
released
before
it
ends.
Start
from
R
=
C₁
+
C₂
+
C₃
and
repeat
until
R
stops
changing;
the
line
above
is
the
last
pass.
R₃
=
3
+
⌈
7
4
⌉
×
1
+
⌈
7
8
⌉
×
2
R = 1 + 2 + 3 = 6
R
=
3
+
⌈
6
4
⌉
×
1
+
⌈
6
8
⌉
×
2
=
7
R
=
3
+
⌈
7
4
⌉
×
1
+
⌈
7
8
⌉
×
2
=
7
R₃
=
7
ms
Step 2 · Find runs of task 1 within R₃ (k₁)
Use k₁ = ⌈R₃ ÷ T₁⌉
Count
task
1’s
releases
from
0
up
to
R₃
:
each
one
runs
before
task
3
can
finish.
k₁
=
⌈
7
4
⌉
k₁
=
2
Step 3 · Find runs of task 2 within R₃ (k₂)
Use k₂ = ⌈R₃ ÷ T₂⌉
Count
task
2’s
releases
from
0
up
to
R₃
the
same
way.
k₂
=
⌈
7
8
⌉
k₂
=
1
Check
Put the numbers back in. Both sides should match.
7
=
3
+
⌈
7
4
⌉
×
1
+
⌈
7
8
⌉
×
2
✓
2
=
⌈
7
4
⌉
✓
1
=
⌈
7
8
⌉
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.