Hardware Reference
In-Depth Information
Workload Analysis.
Similarly, using the workload analysis, a task set with blocking
factors is schedulable by a fixed priority assignment if
∀
i
=1
,...,n
∃
t
∈TS
i
:
B
i
+
W
i
(
t
)
≤
t.
(7.23)
where set
TS
i
has been defined by equation (4.21).
Processor Demand Criterion.
The Processor Demand Criterion in the presence of
blocking terms has been extended by Baruah [Bar06], using the concept of
Blocking
Function
B
(
L
), defined as the largest amount of time for which a task with relative
deadline
≤
L
may be blocked by a task with relative deadline
>L
.
If
δ
jh
denotes the maximum length of time for which
τ
j
holds a resource that is also
needed by
τ
h
, the blocking function can be computed as follows:
B
(
L
)=max
{
δ
j,h
|
(
D
j
>L
) and (
D
h
≤
L
)
}
.
(7.24)
Then, a task set can be scheduled by EDF if
U<
1 and
∀
L
∈D
B
(
L
)+
g
(0
,L
)
≤
L.
(7.25)
where
is the set of all absolute deadlines no greater than a certain point in time,
given by the minimum between the hyperperiod
H
and the following expression:
max
D
max
,
i
=1
(
T
i
−
D
.
D
i
)
U
i
1
−
U
where
D
max
=max
{
D
1
,...,D
n
}
.
7.10
SUMMARY
The concurrency control protocols presented in this chapter can be compared with
respect to several characteristics. Table 7.5 provides a qualitative evaluation of the
algorithms in terms of priority assignment, number of blocking, level of pessimism,
instant of blocking, programming transparency, deadlock prevention, and implemen-
tation complexity. Here, transparency refers to the impact of the protocol on the
programming interface. A transparent protocol (like NPP and PIP) can be imple-
mented without modifying the task code, that is, exploiting the same primitives used
by classical semaphores. This means that legacy applications developed using classi-
cal semaphores (prone to priority inversion) can also be executed under a transparent
protocol. This feature makes such protocols attractive for commercial operating sys-
tems (like VxWorks), where predictability can be improved without introducing new
kernel primitives. On the contrary, protocols that use resource ceilings (as HLP, PCP
and SRP) need an additional system call to specify such values in the application.
Search WWH ::
Custom Search