Hardware Reference
In-Depth Information
Algorithm: Compute the Longest Non-Preemptive Intervals
Input:
A task set
T
with
{
C
i
,T
i
,D
i
,P
i
}
,
∀
τ
i
∈T
Output:
Q
i
,
∀
τ
i
∈T
//
Assumes
T
is preemptively feasible and
D
i
≤
T
i
begin
(1)
β
1
=
D
1
−
C
1
;
(2)
Q
1
=
∞
;
(3)
for
(
i
:= 2
to
n
)
do
(4)
Q
i
=min
{
Q
i−
1
,β
i−
1
+1
}
;
(5)
Compute
β
i
using Equation (8.20) or (8.21);
(6)
end
(7)
end
(8)
Figure 8.12
Algorithm for computing the longest non-preemptive intervals.
8.5
TASK SPLITTING
According to this model, each task
τ
i
is split into
m
i
non-preemptive chunks (subjobs),
obtained by inserting
m
i
−
1 preemption points in the code. Thus, preemptions can
only occur at the subjobs boundaries.
All the jobs generated by one task have the
The
k
th
subjob has a worst-case execution time
q
i,k
; hence
same subjob division.
C
i
=
m
i
k
=1
q
i,k
.
Among all the parameters describing the subjobs of a task, two values are of particular
importance for achieving a tight schedulability result:
q
max
i
=max
k∈
[1
,m
i
]
{
q
i,k
}
(8.24)
q
last
i
=
q
i,m
i
In fact, the feasibility of a high priority task
τ
k
is affected by the size
q
ma
j
of the
longest subjob of each task
τ
j
with priority
P
j
<P
k
. Moreover, the length
q
last
i
of the final subjob of
τ
i
directly affects its response time. In fact, all higher priority
jobs arriving during the execution of
τ
i
's final subjob do not cause a preemption, since
their execution is postponed at the end of
τ
i
. Therefore, in this model, each task will
be characterized by the following 5-tuple:
C
i
,D
i
,T
i
,q
max
,q
last
i
{
}
.
i
Search WWH ::
Custom Search