Maximum Schedulable Utilization

Maximum Schedulable Utilization

Any system is schedulable by an algorithm if the algorithm always produces a feasible schedule of the system. It is possible to schedule (and feasible) only if the feasible schedule of the system exists. Maximum total utilization means the maximum total utilization of the system in order for the system to be surely schedulable.

Schedulable Utilization of EDF Algorithm

We know that a periodic task T_i is denoted by 4-tuple (φ_i, P_i, e_i, D_i) with utilization u_i = e_i/P_i.

The total utilization of the system

A scheduling algorithm can feasibly schedule any system of periodic tasks on a processor if U is equal to or less than the maximum schedulable utilization of the algorithm (U_ALG) and if U_ALG = 1, then the algorithm is optimal.

U_ALG id important because it gives a schedulability test where a system can be validated by showing that U <= U_ALG.

Theorem:

A system of independent, preemptable periodic tasks with relative deadlines equal to their respective periods (i.e. D_i=P_i) can be feasibly scheduled on one processor if and only if its total utilization is equal to or less than 1 (U <= 1).

Proof:

Consider that the relative deadline of every task is equal to its period, then according to the theorem any such system can be feasibly scheduled if its total utilization is equal to or less than 1, regardless of number of tasks. On the other hand, if any system fails to meet some deadlines, then obviously the total utilization is greater than 1.

Based on above theorem and the discussion, we can say that the periodic tasks with D_i = P_i.

The corollary of above theorem states that, the result also holds true if the relative deadline is longer than the period. That means U_EDF for independent preemptable periodic tasks with D_i >= P_i.

Note: above result is independent of Pi and the result can also be applied to strict LST.

Schedulability Test for the EDF Algorithm

A test that is used to validate that the given systems can indeed meet all its hard deadlines when scheduled according to a chosen scheduling algorithm is called a schedulability test. If this test is efficient, then it is can be used as an on-line acceptance test.

Schedulability test is used to check whether a set of periodic tasks meet all their deadlines.

Suppose,

1. The periodic (P_i), execution time (e_i), and their relative deadline (D_i) of every task T_i in a system T = {T₁, T₂, . . . . , T_n} and
2. A priority driven algorithm used to schedule the tasks in T preemptively on one processor are given.

In the above given conditions if the phases are also given and if the values of all the given parameters do not vary, the problem can be solved by simulation. For this, we can construct a segment of schedule (time line) of these tasks according to given algorithm. The length of the segment will be equal to 2H + maxi P_i+ maxi D_i. If we do not find any missed deadlines in this segment, then T_i will certainly meet its deadlines. But, this method doesn’t work if the parameters vary.

To determine whether the given system of n independent periodic tasks surely meet all the deadlines when scheduled according to preemptive EDF algorithm on one processor, check the following inequality condition called schedulability condition.

If this condition is satisfied, then the system is scheduled according to EDF algorithm. But if this condition is not satisfied, then the following two conclusions can be made which depends on the relative deadline (Di).

1. If D_k>=P_k for all k from 1 to n, eq. i becomes U<=1, which is both a necessary and sufficient condition for a system to be feasible.
2. If D_k<P_k for some k, eq. i is only a sufficient condition and so the system may not be schedulable when the condition is not satisfied.

If the actual inter-release times are sometimes longer than P_k, the total demand for processor time will be smaller. Therefore, if according to eq. i the system is schedulable on one EDF basis, it remains schedulable when the inter-release times of jobs in some tasks are sometimes longer than the respective periods of the tasks.

Optimality of RM and DM

RM and DM algorithms assigns fixed priorities to the tasks. So, they can’t be optimal. They may fail to schedule some systems, even though feasible schedule exists. For example, consider two tasks T₁ = (2, 1) and T₂ = (5, 2.5).

Total utilization (U) = 1/2 + 2.5/5 = 1

Since, U = 1, the task are feasible.

Here, J_1,1 and J_2,2 can complete in time only if they have a higher priority than J_2,1. It means between t = 0 to 4, it must have a higher priority than T₂. But at time 4 when J_1,3 release, J_2,1 can complete in time only if T₂(or J_2,1) has a higher priority than T₁ (or J_1,3). This change in the relative priorities of the tasks is not allowed by any fixed priority algorithm.

Any fixed priority algorithm can be optimal in restricted system. RM (DM) algorithm is not optimal for tasks with arbitrary periods. But it is optimal in a special case when the periodic tasks in the system or simply periodic and deadlines of the tasks are not less than their respective periods.

A system of periodic tasks is said to be simply periodic if the period of each is an integer multiple of the periods of the other tasks. That is,

P_k = nP_i

Where, P_i<P_k and n is a positive integer for all T_i and T_k.

The following theorem, states that the RM algorithm is optimal for scheduling a system having above condition.

Theorem for optimality of RM Algorithm:

A system of simply periodic independent, preemptable tasks whose relative deadlines are equal to larger than their periods (i.e. D_i>=P_i) is schedulable on one processor according to RM algorithm if and only if its total utilization is equal to or less than 1.

Proof:

Assume that in a simple periodic system, all the tasks are in phase (worst case execution time occurs when tasks are in phase). Also, consider that the processor never remains idle before the task Ti misses a deadline at t for the first time, where t is an integer multiple of P_i.

Since, the system is simply periodic, t is also an integer multiple of periods (P_k) of all higher priority tasks (T_k) for k = 1, 2, . . . . , i-1. Therefore, the total time required to complete jobs with deadlines before and at t is

of the highest priority task. It means, T_i misses a deadline at t means that the demand for time exceeds t. in other words, RM fails when U_i>1.

Theorem for Optimality of DM Algorithm.

Generally, fixed priority scheduling is not optimal. But, it gives more predictable and stable system. Among the fixed priority algorithms, DM algorithm is the best and optimal.

Theorem:

A system T of independent preemptable tasks that are in phase and have D_i<=P_i can be feasibly scheduled on one processor according to DM algorithm whenever it can be feasibly scheduled according to any fixed priority algorithm.

Proof:

This theorem is true because we can always transform a feasible fixed priority schedule which is not DM into DM schedule.

For example, consider a system having feasible fixed priority schedule which is not a DM schedule.

Now, arrange all the tasks starting from T_i with the shortest D_i in order of increasing D_i. If there are two tasks T_i and T_i+1 with D_i<D_i+1 and priority of T_i+1 higher than T_i. In such case, we can switch the priorities of these two tasks and modify the schedulable of two tasks that are assigned on the DM basis relative to one another. By repeating this process, the given schedule can be transformed into DM schedule.

When D_i of every task T_i is equal to dP_i for some constant 0<d where d is density, then the DM and RM algorithms are same. In this case, the corollary of above theorem can be stated as “the RM algorithm is optimal among all fixed priority algorithms whenever the relative deadlines of the tasks are proportional to their periods.”

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.