Page 125 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes
Example: Consider 3 periodic processes scheduled using EDF, the following acceptance
test shows that all deadlines will be met.

Process Execution Time = C Period = T
P1 1 8
P2 2 5
P3 4 10

The utilization will be:

1 2 4
0.925 92.5%
8 5 10
The theoretical limit for any number of processes is 100% and so the system is schedulable.
Self Assessment

State whether the following statements are True or False:
6. Fixed Priority algorithm assigns the different priority to all the jobs in each task.
7. A priority driven scheduler is an off-line scheduler.
8. FIFO and LIFO algorithms are also dynamic priority algorithms.

9. The rate monotonic algorithm assigns priorities to tasks based on their periods.
10. The rate of (job releases) of a task is the inverse of its period so the higher the rate, the
higher its priority.

12.3 Maximum Schedulable Utilization

The schedulable utilization UALG of a scheduling algorithm is defined as follows:
A scheduling algorithm can feasibly schedule any set of periodic tasks on a processor if the total
utilization of the tasks is equal to or less than the schedulable utilization of that algorithm.

A periodic task is defined as a tuple ( , p , e , D ) where u = e / p
i i i i i i i
 Total utilization of the system U =  n u where 0  U  1
i=1 i
 The ratio of the execution time e of a task T to the minimum of its relative deadline D
k k k
and period p is called the density of the task
k
 Density of T = e /min(D ,p )
k k i i
 The sum of the densities of all tasks in a system is the density of the system and is denoted
by 
 If the density of a system is larger than 1, the system may not be feasible

120 LOVELY PROFESSIONAL UNIVERSITY