Hardware Reference
In-Depth Information
Figure 6.14 illustrates an example in which a hard periodic task,
τ
1
, with computation
time
C
1
=4and period
T
1
=7, is scheduled together with a soft task,
τ
2
, served
by a CBS having a budget
Q
s
=3and a period
T
s
=8. The first job of
τ
2
(
J
2
,
1
),
requiring 4 units of execution time, arrives at time
r
1
=3, when the server is idle.
Being
c
s
≥
r
1
)
U
s
, the job is assigned a deadline
d
1
=
r
1
+
T
s
=11and
c
s
is
recharged at
Q
s
=3. At time
t
=7, the budget is exhausted, so a new deadline
d
2
=
d
1
+
T
s
=19is generated and
c
s
is replenished. Since the server deadline is postponed,
τ
1
becomes the task with the earliest deadline and executes until completion. Then,
τ
2
resumes and job
J
2
,
1
(having deadline
d
2
=19) is finished at time
t
=12, leaving
a budget
c
s
=2.
(
d
0
−
The second job of task
τ
2
arrives at time
r
2
=13and requires
3 units of time.
r
2
)
U
s
, the last server deadline
d
2
can be used
to serve job
J
2
,
2
. At time
t
=15, the server budget is exhausted, so a new server
deadline
d
3
=
d
2
+
T
s
=27is generated and
c
s
is replenished at
Q
s
. For this reason,
τ
1
becomes the highest priority task and executes until time
t
=19, when job
J
1
,
3
finishes and
τ
2
can execute, finishing job
J
2
,
2
at time
t
=20leaving a budget
c
s
=2.
Since
c
s
<
(
d
2
−
It is worth noting that under a CBS a job
J
j
is assigned an absolute time-varying dead-
line
d
j
that can be postponed if the task requires more than the reserved bandwidth.
Thus, each job
J
j
can be thought as consisting of a number of chunks
H
j,k
, each
characterized by a release time
a
j,k
and a fixed deadline
d
j,k
. An example of chunks
produced by a CBS is shown in Figure 6.14. To simplify the notation, we will indicate
all the chunks generated by the server with an increasing index
k
(in the example of
Figure 6.14,
H
1
,
1
=
H
1
,
H
1
,
2
=
H
2
,
H
2
,
1
=
H
3
, and so on).
6.9.3
FORMAL DEFINITION
In order to provide a formal definition of the CBS, let
a
k
and
d
k
be the release time
and the deadline of the
k
th
chunk generated by the server, and let
c
and
n
be the actual
server budget and the number of pending requests in the server queue (including the
request currently being served). These variables are initialized as follows:
d
0
=0
,
c
=0
,
n
=0
,
k
=0
.
Using this notation, the server behavior can be described by the algorithm shown in
Figure 6.15.
Search WWH ::
Custom Search