PERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 96

n U lub n U lub

1 1.000 6 0.735

2 0.828 7 0.729

3 0.780 8 0.724

4 0.757 9 0.721

5 0.743 10 0.718

Table 4.2 Values of U lub as a function of n .

Thus, defining P = R 1 R 2 ...R n− 1 , U is minimum when
⎧
⎨

R 1 P =2
R 2 P =2
...
R n− 1 P =2 .

⎩

That is, when all R i have the same value:

R 1 = R 2 = ... = R n− 1 =2 1 /n .

Substituting this value in U we obtain

2
2 (1 − 1 /n ) −

1)2 1 /n + U lub = n − n =

n 2 1 /n 2 1 /n +2 1 /n = − − n =

n (2 1 /n = − 1) .

Therefore, for an arbitrary set of periodic tasks, the least upper bound of the processor
utilization factor under the Rate Monotonic scheduling algorithm is

= n (2 1 /n U lub − 1) . (4.9)

This bound decreases with n , and values for some n are shown in Table 4.2.

For high values of n , the least upper bound converges to

U lub =ln2 0 . 69 .

In fact, with the substitution y =(2 1 /n

ln 2
ln( y +1)

− 1), we obtain n = , and hence

y
ln( y +1)

n (2 1 /n lim

n→∞

− 1) = (ln 2) lim

y→ 0