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

and since (by the Hospital's rule)

y
ln( y +1)

1
1 / ( y +1)

lim
y→ 0

= lim
y→ 0

= lim
y→ 0

( y +1) = 1 ,

we have that

lim
n→∞

U lub ( n )=ln2 .

4.3.4 HYPERBOLIC BOUND FOR RM

The feasibility analysis of the RM algorithm can also be performed using a different
approach, called the Hyperbolic Bound [BBB01, BBB03]. The test has the same
complexity as the original Liu and Layland bound but it is less pessimistic, as it accepts
task sets that would be rejected using the original approach. Instead of minimizing
the processor utilization with respect to task periods, the feasibility condition can be
manipulated in order to find a tighter sufficient schedulability test as a function of the
individual task utilizations.

The following theorem provides a sufficient condition for testing the schedulability of
a task set under the RM algorithm.

Theorem 4.1 Let Γ= be a set of n periodic tasks, where each task τ i

is characterized by a processor utilization U i . Then, Γ is schedulable with the RM
algorithm if

{ τ 1 ,...,τ n }

n

( U i +1)

≤

2 . (4.10)

i =1

Proof. Without loss of generality, we may assume that tasks are ordered by increasing
periods, so that τ 1 is the task with the highest priority and τ n is the task with the
lowest priority. In [LL73], as well as in [DG00], it has been shown that the worst-case
scenario for a set on n periodic tasks occurs when all the tasks start simultaneously
(e.g., at time t =0) and periods are such that

∀ i =2 ,...,n T 1 <T i < 2 T 1 .

Moreover, the total utilization factor is minimized when computation times have the
following relations:

⎧
⎨

C 1 = T 2 − T 1

C 2 = T 3 − T 2

(4.11)

···
C n− 1

⎩

= T n − T n− 1