Page 102 - DCAP103_Principle of operating system

Unit 3: Process Management-II

determines the priority of a task by calculating how close the associated processing stream is Notes
to failure. Streams that are close to dynamic failure are accorded higher priority than streams
that are relatively safe. To illustrate, suppose we have three concurrent streams, S, S, and S,1 2
3 that each have an 8 of 10 constraint. Suppose that in the current window, S 1 has processed
six tasks of which one failed to complete, S has processed 2 nine tasks of which two have failed
to complete, and S has processed seven 3 tasks with no failures. Under these conditions,
S, will receive the highest 2 priority since even one more task failure will cause a stream failure.
S, will 1 receive the next highest priority, and S will receive the lowest priority since it 3 is the
farthest from stream failure. One issue that arises for this algorithm is the effect of finite priority
levels. Although many systems have 256 or more priority levels available, many backplanes
and communication processors, where this algorithm is particularly appropriate, have a limited
number of priority levels. In general, a stream with (m, n)-firm deadlines needs n-m+ 2 priority
levels to fully implement the algorithm. However, simulation studies performed by Hamdaoui
and Ramanathan have shown that there is a substantial reduction in dynamic stream failures
with as few as three priority levels. Adaptive Best Effort scheduling has been proposed by Wang
and Lin to handle repetitive tasks. These tasks differ from periodic tasks in that there is normally
no control over the spacing between task instances. The spacing between two instances of a
specific task can vary from zero to twice the period of the task, depending upon the current
workload of the system. In this situation, rather than accepting or rejecting tasks, or just letting
certain tasks fail, the system attempts to adjust the period of these tasks. The difficulty associated
with this form of scheduling is that the standard periodic task model does not comprehend
dynamically varying periods. This requires developing an adaptive task model. The primary
difference between the periodic task model and the adaptive task model is in selecting the task
ready times. In the periodic model, a task’s next ready time coincides with its last completion
time. In the adaptive model, the ready time can be set to anytime prior to the task deadline,
dependent upon task execution requirements. This way the task ready time and deadline can
be considered the minimum and maximum spacing from the previous execution of the task.
Although several different scheduling policies could be used with Adaptive Best Effort
scheduling, Wang and Lin confined their studies to the Earliest-Deadline-First (EDF) and Rate-
Monotonic (RM) policies since they have both been studied extensively and are relatively common
in many commercial real-time operating systems. To carry out their study, they ( ) rc-I I j defined
a ready ratio, R , for the j-th instance of the task t I as R = - 1 I I j F j j i where r is the ready time,
or earliest time that the J -th instance of task t can I j run, c is the time the task completes, and
F is the frame time, or period of ii j the task. An adaptive system with fixed ready ratios is one
in which all ready ratios are set to a constant value. An adaptive system with rate monotonic
ready ratios is one in which the ready ratios are set according to the system workload indexes,
which are the total execution times of a task divided by its period, and the task periods. The
results of their studies showed that under a normal workload, the adaptive EDF scheduler with
rate-monotonic ready ratios clearly provided the best performance. However, as the workload
on the system increased, periodic EDF (non-adaptive) provided a better scheduling alternative.
Fixed ready ratio EDF simply did not perform well. For use in real world applications, Adaptive
Best Effort algorithms have several drawbacks that need to be overcome. Adding task importance
parameters to the algorithm could allow it to more gracefully degrade under heavy workload
conditions by allowing it to discard tasks of low importance, rather than selecting tasks essentially
at random. However, this algorithm appears to need significant further study before it would
be applicable to real world systems.
Future Research

Future work in Dynamic Best Effort algorithms should include developing algorithms that
have more deterministic performance under overload conditions. Additionally, investigation of
other periodic scheduling policies for the adaptive period algorithm might provide improved
performance.

LOVELY PROFESSIONAL UNIVERSITY 95