Page 90 - DCAP403_Operating System

Unit 5: Scheduling

Figure 5.7: Real-time Scheduling Notes
Sampling Sampling
Highest Priority
HWI

Background
Processing
Frame

Idle

Lowest Priority

5.3.8 Earliest Deadline First

The EDF scheduling algorithm is a preemptive and dynamic priority scheduler that executes
tasks in order of the time remaining before their corresponding deadlines. Tasks with the least
time remaining before their deadline are executed before tasks with more remaining time. At
each invocation of the scheduler, the remaining time is calculated for each waiting task, and the
task with the least remaining time is dispatched. If a task set is schedulable, the EDF algorithm
results in a schedule that achieves optimal resource utilization. However, EDF is shown to be
unpredictable if the required utilization exceeds 100%, known as an overload condition. EDF is
useful for scheduling periodic tasks, since the dynamic priorities of tasks do not depend on the
determinism of request periods.

5.3.9 Rate Monotonic

Under the static-priority rate monotonic scheduling algorithm, tasks are ordered according to the
value of their request period, T. Tasks with shorter request periods are assigned higher priority
than those with longer periods. Liu and Layland proved that a feasible schedule is found under
rate monotonic scheduling if the total requested utilization is less than or equal to ln, which is
approximately 69.3%.
RM scheduling is optimal with respect to maximum utilization over all static-priority schedulers.
However, this scheduling policy only supports tasks that fit the periodic task model, since

priorities depend upon request periods. Because the request times of a periodic tasks are not
always predictable, these tasks are not supported by the RM algorithm, but are instead typically
scheduled using a dynamic priority scheduler such as EDF.

Characteristics of Scheduling Algorithms

FCFS Round Robin SJF SRT HRRN Feedback
Selection max[w] constant Min[s] min[s-e] max[(w+s)/s] see text
Function
Decision Non-preemptive preemptive Non- preemptive Non- preemptive
mode preemptive preemptive at time
quantum
Contd...

LOVELY PROFESSIONAL UNIVERSITY 83