A scheduling test is required to schedule the fixed priority task with shortest response time which is smaller than or equal to respective periods and total utilization is less than 1. Generally fixed priority algorithms are not suffers from the scheduling anomalies and requires following task to generate a schedule without anomalies.
- Find the critical instant when the system is most loaded and its worst response
- Use time demand analysis to determine if the system is schedulable at that
Critical Instant:
A critical instant for a job is the worst-case release time for that job, taking into account all jobs that have higher priority i.e. a job released at the same instant as all jobs with higher priority are released, and must wait for all those jobs to complete before it executes.
A critical instant of a task Ti is a time instant such that:
- the job of Ti released at this instant has the maximum response time of all jobs in Ti, if the response time of every job of Ti is at most Di, the relative deadline of Ti and
- the response time of the job released at this instant is greater than Di of the response time of some jobs in Ti exceeds Di
The schedulability test involves for checking each task as it is scheduable or not in the critical instant. The critical instant theorem states that, a fixed-priority system where every job completes before the next job of the same task is released, a critical instant of any task Ti occurs when one of its job Ji,c is released at the same time with a job of every higher priority task.
For example: Consider three tasks T1 (2, 0.6), T2 (2.5, 0.2), T3 (3, 1.2) Here T1>T2>T3
The RM schedule table be
|
Time |
Ready to Run |
Scheduled |
|
0 |
J11, J21, J31 |
J11 |
|
0.6 |
J21,J31 |
J21 |
|
0.8 |
J31 |
J31 |
|
2 |
J12, |
J12 |
|
2.5 |
J12, J22 |
J12 |
|
2.6 |
J22 |
J22 |
|
2.8 |
---------------------- |
------------------------ |
|
3 |
J32 |
J32 |
|
4 |
J13,J32 |
J13 |
|
4.6 |
J32 |
J32 |
|
4.8 |
|
|
|
5 |
J23 |
J23 |
|
5.2 |
|
|
|
6 |
J14, J33 |
J14 |
|
6.6 |
J33 |
J33 |
|
7.5 |
J24, J33 |
J24 |
|
7.7 |
J33 |
J33 |
|
8 |
J15 |
J15 |
|
8.6 |
|
|
|
9 |
J34 |
J34 |
|
10 |
J16, J25,J34 |
J16 |
|
10.6 |
J25, J34 |
J25 |
|
10.8 |
J34 |
J34 |
|
11 |
|
|
The corresponding schedule be constructed as below
Response time for all jobs of Task T1 = 0.6 Response time for Job J21 of task T2 = r21= 0.8
Response time for Job J22 of task T2 = r22 = 2.8 - 2.5 = 0.3 Response time for Job J23 of task T2 = r23 = 5.2 – 5 = 0.2 Response time for Job J24 of task T2 = r24 = 7.7 -7.5 = 0.2 Response time for Job J25 of task T2 = r25= 0.8
The response time all jobs of task T2 never exceed the response time of first job. Hence the critical instant is equal to t=0 and t=10.
Response time for Job J31 of task T3 = r31 = 2 Response time for Job J32 of task T3 = r32 = 1.8 Response time for Job J33 of task T3 = r33 = 2 Response time for Job J34 of task T3 = r34 = 2
Here the response time for jobs in T3 never exceed the response time of first job in T3. Hence critical instant of T3 are t= 0, 6 and 9.
Time- Demand Analysis:
The process used to determine whether a task can meet its deadline is called time demand analysis. Methods to time-demand analysis are:
- Compute the total demand for processor time by job released at a critical instant of task and by higher priority task as a function of time from the critical instant.
- Check weather tis demand can be met before the deadline of job as follows:
-Consider the scanning is done one task at a time from higher priority and working down to lowest priority.
-Focused on a job in Ti where the released at time t0 of that job is a critical instant of Ti.
-At time t0+t for𝑡 ≥ 0, compute the processor time demand wi (t) of this job and all higher priorities job released in [t0, t] using
3. Compare the time demand wi (t) with available time t as
-If 𝑤𝑖(𝑡) ≤ 𝑡 𝑓𝑜𝑟 𝑡 ≤ 𝐷𝑖 , the job meets its deadline 𝑡0 + 𝐷𝑖
-If 𝑤𝑖(𝑡) > 𝑡 𝑓𝑜𝑟 0 ≤ 𝑡 ≤ 𝐷𝑖 , the task may not complete by its deadline and system cannot scheduled by using fixed priority algorithms.