Page 132 - DCAP608_REAL TIME SYSTEMS

Unit 13: Working of Priority-driven Scheduling of Periodic Tasks

13.2.1 A Schedulability Test for Fixed-Priority Tasks with Short Notes
Response Times

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 algorithms which can exhibit anomalous behaviour.
 Use this as the basis for a general Schedulability test:
 Find the critical instant when the system is most loaded, and has its worst response time
 Use time demand analysis to determine if the system is schedulable at that instant

 Prove that, if a fixed-priority system is schedulable at the critical instant, it is always
schedulable

Critical Instants

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. The response time of a
job in Ti released at a critical instant is called the maximum (possible) response time, and is denoted by Wi.
The schedulability test involves checking each task in turn, to verify that it can be scheduled
when started at a critical instant. If schedulable at all critical instants will work at other times.
More work than the test for maximum schedulable utilization, but less than an exhaustive
simulation.

!
Caution An important problem that is addressed during the design of a uniprocessor
based real time system id to check whether a set of periodic real time tasks can feasibly be
scheduled under RMA.
Theorem: In a fixed priority system where every job completes before the next job in the same
tasks is released, a critical instant of any tasks Ti occurs when one of its job J is released at the
i,c
same time with a job in every higher priority task, that is, r = r for some l for every k =
i,c k,lk k
1,2,…i-1

Example: 3 tasks scheduled using rate-monotonic
Response times of jobs in T2 are:
r2,1 = 0.8, r2,3 = 0.3, r2,3 = 0.2, r2,4 = 0.3, r2,5 = 0.8, …
Therefore critical instants of T2 are t = 0 and t = 10

LOVELY PROFESSIONAL UNIVERSITY 127