Page 133 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes Using Critical Instance

Having determined the critical instants, show that for each job Ji, c released at a critical instant,
that job and all higher priority tasks complete executing before their relative deadlines
 If so, the entire system is schedulable.

 That is don’t simulate the entire system, simply show that it has correct characteristics
following a critical instant.
– This process is called time demand analysis.

Time Demand Analysis

 Schedulability test is more complex than the schedulable utilization test, but more general.

 Works for any fixed-priority scheduling algorithm, provided the tasks have short response
time (i.e. pi < Di).
 Can be extended to tasks with arbitrary deadlines.

 Only a sufficient test: guarantees that schedulable results are correct, but requires further
testing to validate a result of not schedulable.
 Alternative approach: simulate the behaviour of tasks released at the critical instants, up
to the largest period of the tasks.
 Still involves simulation, but less complex than an exhaustive simulation of the system
behaviour.
Self Assessment

State whether the following statement are True or False:
4. A critical instant for a job is the worst-case release time for that job, taking into account all
jobs that have higher priority.
5. The worst case execution time of the system does not occur with the worst case execution
time of the jobs, unlike dynamic priority algorithms which can exhibit anomalous
behaviour.

13.2.2 A Schedulability Test for Fixed-Priority Tasks with Arbitrary
Response Times

When a group of tasks share a common resource (such as a processor, a communication
medium,. . . ), a scheduling policy is necessary to arbitrate access to the shared resource. One of
the most intuitive policies consists of assigning Fixed Priorities (FP) to the tasks, so that at each
instant in time the resource is gr anted to the highest priority task requiring it at that instant. De
pending on the assigned priority, a task can have longer or shorter response time, which is the
time elapsed from request of the resource to the completion of the task.
Critical applications often require that the worst-case response times (i.e. the maximum possible
response time) do not exceed a given deadline. Hence it is necessary to perform the Response
Time Analysis (RTA) to compute exactly the worst-case response time of each task in the task
system.

128 LOVELY PROFESSIONAL UNIVERSITY