Schedulability of Fixed Priority Tasks with Short Response Time

Schedulability of fixed-priority tasks with short response time

The fixed priority algorithms are predictable and do not suffer from scheduling anomalies. The worst case execution time of the system occurs with the worst case execution time of the jobs, unlike dynamic priority algorithm which can exhibit anomalous behavior. Pseudo-polynomial time schedulability test can be used for the tasks scheduled according to the fix priority algorithms. In this, the response times of the jobs should be smaller than or equal to their respective periods and the total utilization should be less than or equal to 1. It means, every job completes execution before the next job if the same task is released.

The above fact can be used for general schedulability test of fixed-priority tasks with short response time. The methods used for the test are,

1. Find the critical instant when the system is most loaded and has its worst response time.
2. Use time demand analysis to determine whether the system is schedulable at that instant.
3. Prove that if a fixed priority system is schedulable at the critical instant then it is always schedulable.

Time Demand Analysis

The time demand analysis is used to determine the system behavior at the critical instant. For each job J_i,e released at a critical instant if J_i,e and all higher priority tasks complete executing before their D_i, then the system can be scheduled. To prove this we can compute the total demand for processor time by a job released at a critical instant and all the higher priority tasks as a function of time from the critical instant. A test is conducted to check whether this demand can be met before the deadline.

Consider one task T_i at a time starting from highest priority and working down to lowest priority. Consider a job J_i in T_i where the release time are 0 of that job is a critical instant of T_i. At time t₀ + t for t>=0, the processor time demand w_i for this job and all the higher priority jobs released between t₀ and t

Where, e_i = execution time of job

Compare the time demand w_i(t) with the available time t then

1. If w_i(t) <=t, then the job J_i meets its deadline.
2. If w_i(t)>t, for all 0<=t<=D_i then the task may not complete by its deadline and the system may not be scheduled using a fixed priority algorithm.

The above two cases are sufficient conditions but not necessary condition. We can use this method to check that all the tasks can be scheduled if they are released at their critical instant and we can conclude that the entire system can be scheduled.

Consider three tasks T₁ = (3, 1), T₂ = (5, 2) and T₃ = (10, 2) scheduled according to rate monotonic algorithm. The total utilization U = 0.933. For these tasks, we can draw a graph for time demand function as shown below:

The time demand function is a staircase function. The steps in the time demand for a task occurs at multiples of the period for higher priority task. The value of w_i(t) and t linearly decreases from a step until the next step. In the figure, the time demand function w₁(t), w₂(t) and w₃(t) are not above the timeline t at their deadlines. Therefore, all the tasks in the system meet their deadlines and can be feasibly scheduled.

Critical Instant

A critical instant of a task T_i is a time instant in which

1. The job in T_i released at this instant has the maximum response time of every job in T_i is equal to or less than the relative deadline D_i of T_i and
2. The response time of the job released at the instant is greater that D_i if the response time of some jobs in T_i exceeds D_i.

Therefore, a critical instant for a job is the worst case release time for that job taking into account all jobs that have higher priority. It means, the job released at the same instant as all jobs that have higher priority are released and must wait for all those to complete before it executes. The response time of a job in T_i released at a critical instant is called the maximum (possible) response time and is denoted by w_i.

The schedulability test involves checks each task, in turn, to verify that it can be scheduled when started at a critical instant. If it is schedulable at all critical instants, then it will work at other times as well.

Now, we can say that a critical instant of a task T_i is a time instant such that:

If W_i,k<=D_i,k for every J_i,k in T_i, then the job released at that instant has the maximum response time of all jobs in T_i and W_i=W_i,k.

Else if,

∃J_i,k:W_i,k>D_i,k

Then the job released at that instant has response time > D where W_i,k is the response time of job.

THEOREM

In a fixed-priority system where every job completes before the next job in the same task is released, a critical instant of any task Ti occurs when one of its job J_i,c is released at the same time with a job in every higher-priority task, that is, r_i,c =r_k,l_k for some lk for every k =1,2,...,i −1.

Schedulability Test for Fixed Priority Tasks with Arbitrary Response Time

Busy Intervals

Consider a term level-π_i busy interval. A level-π_i busy interval (t₀,t] begins at the instant to when

1. All the jobs in T_i released before the instant have completed and
2. A job in T_i is released.

The interval ends at the first instant t after t₀ when all the jobs in T_i­ released since t0 are completed. It means, in the interval [t0, t], the processor is busy all the time executing jobs with priorities π_i or higher. All the jobs executed in the busy interval are released in the interval and at the end of the interval, there is no backlog of jobs to be executed afterwards. Therefore, while computing the response time of jobs in T_i, we can consider every level-π_i busy intervals.

Consider the schedule of three tasks T1 = (2, 1), T2 = (3, 1.25) and T3 = (5, 0.25)

Using the RM algorithm, the timing diagram is as follows:

General Schedulability Test

The general schedulability test is described below. It relies on the fact that when determining the schedulability of a task T_i in a system in which the response times of jobs can be larger than their respective periods, it still suffices to confine our attention to the special case where the tasks are in phase. However, the first job J_i,1 may no longer have the largest response time among all jobs in T_i. Consequently, we must examine all the jobs of T_i that are executed in the first level-π_i busy interval. If the response times of all these jobs are no greater than the relative deadline of T_i, T_i is schedulable; else, T_i may not be schedulable.

General Time-Demand Analysis Method

Test one task at a time starting from the highest priority task T₁ in the order of decreasing priority. To determine whether a task T_i is schedulable, let us assume that all the tasks are in phase and the first level-π_i busy interval begins at time 0.

While testing whether all the jobs in T_i can meet their deadlines (that is, whether T_i is schedulable), consider the subset T_i of tasks with priorities π_i or higher.

1. If the first job of every task in T_i completes by the end of the first period of the task, check whether the first job J_i,1 in T_i meets its deadline or not. T_i is schedulable if J_i,1 completes in time. Else, T_i is not schedulable.
2. If the first job of some task in T_i does not complete by the end of the first period of the task, do the following:
3. Compute the length of the in phase level-π_i busy interval by solving the equation

iteratively, starting from

until t^(l+1) = t^(l). The solution t⁽¹⁾ is the length of the level-π_i busy interval.

1. Compute the maximum response times of all ⌈t^(l)/p_i⌉ jobs of Ti in the in=phase level- π_i busy intervals in the manner described below and determine whether they complete in time.

Ti is schedulable if all these jobs complete in time; else, T_i is not schedulable.(Liu 141-142)

Sufficient Schedulability Condition for RM and DM algorithm Schedulable Utilization of RM Algorithm when D_i = P_i

Theorem

A system of n independent, preemptable periodic tasks with relative deadlines equal to their respective periods can be feasibly scheduled on a processor according to the RM algorithm if its total utilization U is less than or equal to

U_RM(n) =n(2^1/n −1)

Example,

T₁ = (1.0, 0.25), T₂ = (1.25, 0.1), T₃ = (1.5, 0.3), T₄ = (1.75, 0.07), and T₅ = (2.0, 0.1).

Utilizations are: 0.25, 0.08, 0.2, 0.04, and 0.05

Total utilization = U = 0.62

U_RM (5) = 0.743

Practical Factors

It includes the following:

1. Non-preemptable
2. Self-suspension
3. Context switch
4. Tick scheduling