Page 131 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes
Did u know? RM and DM are optimal in simply periodic systems.
Theorem: A system of simply periodic, independent, preemptible tasks with D e” p is schedulable
i i
on one processor using the RM algorithm if and only if U d” 1
Corollary: The same is true for the DM algorithm

 To prove that this theorem is true, suppose that the tasks are in phase (they have identical
phases) and the processor never idles before the task T misses a deadline for the first time
i
at t.
 T is an integer multiple of p .
i
 Because the tasks are simply periodic, t is also an integer multiple of the period p of every
k
higher-priority task T , for k = 1,2,…, i-1
k
 Hence the total time required to complete all the jobs with deadlines before and at t is
equal to Ó i (e t p ) which is equal to t times the total utilization Ó n u of the I highest
k=1 k / k k=1 k
priority tasks.
 That Ti misses a deadline at t means that this demand for time exceeds t or in other words,
Ui > 1

Self Assessment

Fill in the blanks:
1. ……………… algorithms can be optimal in restricted systems.
2. If a system can be arranged such that every ……………… can be fulfilled, this system is
fulfilled by earliest deadline first.
3. ……………… will schedule in order to fulfil every deadline.

13.2 Schedulability Test

A test for the purpose of validating that the given application system can indeed meet all its hard
deadlines when scheduled according to the chosen scheduling algorithm is called a Schedulability
test.

 Checking whether a set of periodic tasks meet all their deadlines is a special case of the
following validation problem
We are given
1. The period p , execution time e , and the relative deadline D of every task T in a
i i i i
system T = {T , T , …T } of independent periodic tasks and
1 2 n
2. A priority-driven algorithm used to schedule the tasks in T preemptively on one
processor
We are asked to determine whether all the deadlines of every tasks Ti are always met.
 To determine whether the given system of independent periodic tasks surely meets all the
deadlines when scheduling according to preemptive EDF algorithm on one processor, we
check whether  <= 1, if it is, the system is schedulable, if not exhaustive simulation
required.

126 LOVELY PROFESSIONAL UNIVERSITY