FIXED-PRIORITY SERVERS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 124

C s C s

PS

C 1 C 1

τ 1

T 1

C 2 C 2

τ 2

T 2

C n

τ n

0 T s T n

Figure 5.4 Worst-case scenario for n periodic tasks and a Polling Server (PS) with the
highest priority.

tasks is schedulable by RM if

m

U p + U s j ≤ U lub ( n + m ) .

j =1

A more precise schedulability test can be derived using the same technique adopted
for the Liu and Layland bound, by assuming that PS is the highest-priority task in the
system. To simplify the computation, the worst-case relations among the tasks are first
determined, and then the lower bound is computed against the worst-case model.

Consider a set of n periodic tasks, τ 1 ,...,τ n , ordered by increasing periods, and a
PS server with a highest priority. The worst-case scenario for a set of periodic tasks
that fully utilize the processor is the one illustrated in Figure 5.4, where tasks are
characterized by the following parameters:
⎧
⎨

C s = T 1 − T s

C 1 = T 2 − T 1

C 2 = T 3 − T 2

...
C n− 1

⎩

= T n − T n− 1

C s − n− 1 C n = T s − C i =2 T s − T n .

i =1