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

U LUB FOR N 4.3.3 CALCULATION OF TASKS

From the previous computation, the conditions that allow to compute the least upper
bound of the processor utilization factor are
⎧
⎨

F =1
C 1 = T 2 − FT 1

C 2 =( T 1 −

⎩

C 1 ) F,

which can be rewritten as

⎧
⎨ T 1 <T 2 < 2 T 1

C 1 T 1

C 2 =2 T 1 −

= T 2 −

⎩

T 2 .
Generalizing for an arbitrary set of n tasks, the worst conditions for the schedulability
of a task set that fully utilizes the processor are
⎧
⎨ T 1 <T n < 2 T 1

C 1 = T 2 − T 1

C 2 = T 3 − T 2

...
C n− 1 = T n −

⎩

T n− 1

C n = T 1 −

( C 1 + C 2 + ... + C n− 1 )=2 T 1 −

T n .

Thus, the processor utilization factor becomes

T 2 − T 1

+ T 3 −

T 2

+ ... + T n −

T n− 1
T n− 1

+ 2 T 1 −

T n

U = .

T 1 T 2 T n

Defining

R i = T i +1
T i

and noting that

T n
T 1

R 1 R 2 ...R n− 1 = ,

the utilization factor may be written as

n− 1

2
R 1 R 2 ...R n− 1 −

U = R i + n.

i =1

To minimize U over R i , i =1 ,...,n − 1,wehave

∂U
∂R k

2
R i ( n− 1

=1 − .

R i )

i = k