Hardware Reference
In-Depth Information
is the smallest value for which
L
(
s
)
i
=
L
(
s−
1)
i
In particular,
L
i
. This means that the
response time of
τ
i
must be computed for all jobs
τ
i,k
with
k
∈
[1
,K
i
], where
K
i
=
L
i
T
i
.
(8.27)
For a generic job
τ
i,k
, the start time
s
i,k
of the last subjob can be computed considering
the blocking time
B
i
, the computation time of the preceding (
k
−
1) jobs, those subjobs
q
last
i
preceding the last one (
C
i
−
), and the interference of the tasks with priority higher
than
P
i
. Hence,
s
i,k
can be computed with the following recurrent relation:
⎧
⎨
+
h
:
P
h
>P
i
s
(0)
i,k
q
last
i
=
B
i
+
C
i
−
C
h
s
(
−
1)
i,k
T
h
+1
C
h
.
(8.28)
+
h
:
P
h
>P
i
⎩
s
(
)
i,k
q
last
i
=
B
i
+
kC
i
−
Since, once started, the last subjob cannot be preempted, the finishing time
f
i,k
can be
computed as
f
i,k
=
s
i,k
+
q
last
.
(8.29)
i
Hence, the response time of task
τ
i
is given by
R
i
=max
k∈
[1
,K
i
]
{
f
i,k
−
(
k
−
1)
T
i
}
.
(8.30)
Once the response time of each task is computed, the task set is feasible if
∀
i
=1
,...,n
R
i
≤
D
i
.
(8.31)
Assuming that the task set is preemptively feasible, the analysis can be simplified to
the first job of each task, after the critical instant, as shown by Yao et al. [YBB10a].
Hence, the longest relative start time of
τ
i
can be computed as the smallest value
satisfying the following recurrent relation:
⎧
⎨
+
h
:
P
h
>P
i
S
(0)
i
q
last
i
=
B
i
+
C
i
−
C
h
S
(
−
1)
i
T
h
+1
C
h
.
(8.32)
+
h
:
P
h
>P
i
⎩
S
(
)
i
q
last
i
=
B
i
+
C
i
−
Then, the response time
R
i
is simply:
R
i
=
S
i
+
q
last
.
(8.33)
i
Search WWH ::
Custom Search