Hardware Reference
In-Depth Information
Theorem 9.4
A set of preemptive periodic tasks with relative deadlines less than or
equal to periods can be scheduled by EDF, under a reservation characterized by a
supply function
Z
k
(
t
)
, if and only if
U<α
k
and
∀
t>
0
dbf
(
t
)
≤
Z
k
(
t
)
.
(9.20)
In the specific case in which
Z
k
(
t
) is lower bounded by the supply bound function,
the test become only sufficient and the set of testing points can be better restricted as
stated in the following theorem [BFB09]:
Theorem 9.5
A set of preemptive periodic tasks with relative deadlines less than or
equal to periods can be scheduled by EDF, under a reservation characterized by a
supply function
Z
k
(
t
)=max[0
,α
k
(
t
−
Δ
k
)]
,if
U<α
k
and
∀
t
∈D
dbf
(
t
)
≤
max[0
,α
k
(
t
−
Δ
k
)]
.
(9.21)
where
min[
H,
max(
D
max
,L
∗
)]
D
{
d
k
|
d
k
≤
}
=
and
α
k
Δ
k
+
i
=1
(
T
i
−
D
i
)
U
i
L
∗
=
.
α
k
−
U
9.3.3
HANDLING WRONG RESERVATIONS
As already mentioned, under resource reservations, the system performance heavily
depends on a correct bandwidth allocation to the various activities. In fact, if the
bandwidth is under allocated, the activities within that reservation will progress more
slowly than expected, whereas an over-allocated bandwidth may waste the available
resources. This problem can be solved by using capacity sharing mechanisms that can
transfer unused budgets to the reservations that need more bandwidth.
Capacity sharing algorithms have been developed both under fixed priority servers
[BB02, BBB04] and dynamic priority servers [CBS00]. For example, the CASH algo-
rithm [CBT05] extends CBS to include a slack reclamation. When a server becomes
idle with residual budget, the slack is inserted in a queue of spare budgets (CASH
queue) ordered by server deadlines. Whenever a new server is scheduled for execu-
tion, it first uses any CASH budget whose deadline is less than or equal to its own.
The bandwidth inheritance (BWI) algorithm [LLA01] applies the idea of priority in-
heritance to CPU resources in CBS, allowing a blocking low-priority process to steal
Search WWH ::
Custom Search