DYNAMIC PRIORITY SERVERS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 200

R i

4 T s − Q s +

3 T s

3 T s − Q s +

2 T s

2 T s − Q s +

T s

T s − Q s +

C i

Q s −

Figure 6.22 Worst-case response time of a CBS as a function of the job execution time.

We now consider the problem of selecting the best CBS parameters, such that the
average task response time R i is minimized. For this purpose we suppose to have
the probability density function (p.d.f.) f C ( c ) of the task execution time, and the
respective cumulative distribution function (c.d.f.) F C ( c ), representing the probability
that the execution time is smaller than or equal to c . That is,
F C ( c )= c
0

f C ( x )d x. (6.12)

Since the minimization of the average R i can in general be too complex, we con-
sider the problem of minimizing its linear upper bound R ub
i

. In this case, the average

response time R avg
i

is computed as follows:

= + ∞
0

T s −

x f C ( x )d x

T s
Q s −

R avg
i

Q s + +

T s
Q s − C avg

= T s − Q s + +

T s
T s U s − C avg

= T s (1 − U s )+ + (6.13)