Hardware Reference
In-Depth Information
When
job
J
j
arrives at time
r
j
enqueue the request in the server queue;
n=n+1;
if
(n == 1) /* (the server is idle) */
if
(
r
j
+(c/
Q
s
)*
T
s
>=
d
k
)
/*---------------Rule 1---------------*/
k=k+1;
a
k
=
r
j
;
d
k
=
a
k
+
T
s
;
c=
Q
s
;
else
/*---------------Rule 2---------------*/
k=k+1;
a
k
=
r
j
;
d
k
=
d
k−
1
;
/* c remains unchanged */
When
job
J
j
terminates
dequeue
J
j
from the server queue;
n=n-1;
if
(n != 0) serve the next job in the queue with deadline
d
k
;
When
job
J
j
executes for a time unit
c=c-1;
When
(c == 0)
/*---------------Rule 3---------------*/
k=k+1;
a
k
= actual time();
d
k
=
d
k−
1
+
T
s
;
c=
Q
s
;
Figure 6.15
The CBS algorithm.
6.9.4
CBS PROPERTIES
The proposed CBS service mechanism presents some interesting properties that make
it suitable for supporting applications with highly variable computation times (e.g.,
continuous media applications). The most important one, the
isolation property
,is
formally expressed by the following theorem and lemma. See the original work by
Abeni and Buttazzo [AB98] for the proof.
Q
s
Theorem 6.8
The CPU utilization of a CBS S with parameters
(
Q
s
,T
s
)
is
U
s
=
T
s
,
independently from the computation times and the arrival pattern of the served jobs.
Search WWH ::
Custom Search