Hardware Reference
In-Depth Information
Each served job
J
i,j
is assigned a dynamic deadline
d
i,j
equal to the current
server deadline
d
s,k
.
Whenever a served job executes, the budget
c
s
is decreased by the same amount.
When
c
s
=0, the server budget is recharged at the maximum value
Q
s
and a new
server deadline is generated as
d
s,k
+1
=
d
s,k
+
T
s
. Note that there are no finite
intervals of time in which the budget is equal to zero.
A CBS is said to be active at time
t
if there are pending jobs (remember the
budget
c
s
is always greater than 0); that is, if there exists a served job
J
i,j
such
that
r
i,j
≤
t<f
i,j
. A CBS is said to be idle at time
t
if it is not active.
When a job
J
i,j
arrives and the server is active the request is enqueued in a queue
of pending jobs according to a given (arbitrary) discipline (e.g., FIFO).
When a job
J
i,j
r
i,j
)
U
s
the server
generates a new deadline
d
s,k
+1
=
r
i,j
+
T
s
and
c
s
is recharged at the maximum
value
Q
s
, otherwise the job is served with the last server deadline
d
s,k
arrives and the server is idle, if
c
s
≥
(
d
s,k
−
using the
current budget.
When a job finishes, the next pending job, if any, is served using the current
budget and deadline. If there are no pending jobs, the server becomes idle.
At any instant, a job is assigned the last deadline generated by the server.
6.9.2
SCHEDULING EXAMPLE
τ1 (4,7)
HARD
t
c1=4
c2=3
d1
d2
τ2
SOFT
H
1,1
H
1,2
H
2,1
H
2,2
r1
r2
t
CBS
(3,8)
t
12345
6
789
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Figure 6.14
An example of CBS scheduling.
Search WWH ::
Custom Search