Page 100 - DCAP103_Principle of operating system

Unit 3: Process Management-II

Future Research Notes
The overhead required to identify spare system capacity needs to be incorporated into the
models that are currently used to study Dynamic Priority-Based algorithms. Until this is done,
the results lack real-world validity. There also needs to be an effort directed at adapting these
algorithms or developing new ones for distributed systems. Identifying spare capacity on a
global instead of local scale should introduce many new challenges.
3.6.8 Dynamic Best Effort Algorithms

In many real-time systems, there are a set of tasks which absolutely must complete by their
deadlines or catastrophic system failure occurs. These systems often also have another set of
tasks in which it is not necessary for every instance of the task to meet its deadline or in which
the repetition rate of some set of tasks can be varied as system load varies. Examples are packet
audio and packet video. As long as most of the packets arrive by their deadlines, the requisite
information will be conveyed with minimal degradation. Another example is in a radar system
where the sample rate for a target can be varied dependent upon its course and speed. In this case,
the number of targets being tracked can dynamically vary as a function of the target parameters.
In these kinds of systems, Dynamic Best Effort algorithms provide a means to cope with the
situation where not every task can complete by its deadline. In particular, when a system begins
to overload, dynamic best effort scheduling can provide a graceful and orderly degradation of
performance for all task groups rather then randomly letting some fail while others randomly
succeed. Unfortunately, many scheduling algorithms that work well under normal conditions
fail miserable when the system begins to overload. As an example, the Earliest Deadline First
algorithm, which has been shown to be optimal under non-overload conditions, has also been
shown to perform even worse than random scheduling under overload conditions. The system
model for dynamic best effort scheduling is the system with multiple processing streams where
the failure of some quantity of the repetitive tasks within the stream can fail without causing
catastrophic failure of the stream or in which the repetition rate of some periodic task can be
varied as some function of the system processing parameters. Dynamic Best Effort scheduling
has several advantages. Most important is the ability of most of these algorithms to provide
relatively good performance in overload conditions in comparison to other scheduling techniques.
By using this scheduling paradigm, a system can maximize the likelihood of the maximum
possible number of tasks completing by their deadlines, or the most critical tasks completing
by their deadlines, or the highest value tasks to the system completing by their deadlines. This
gives the designer significant latitude in determining how the system will respond in overload
conditions. Additionally, Dynamic Best Effort scheduling can maximize processor utilization
when tasks have periods which vary dynamically.

The task model for Dynamic Best Effort scheduling varies depending upon the assumptions made
about the tasks in the system. Task models that have been used for analysis are given below:

3.6.9 Equal Request Times
All tasks in the interval under study request execution at the same time. An example of a system
for which this would hold is a communications switch which periodically polls its incoming
lines for packets to forward. All packets that have arrived since the last poll request immediate
service even though the processing time and deadlines for the packets may vary.
3.6.10 Equal Execution Times

In this case, all tasks have identical execution times, even though they may be ready for execution
at different times and have different deadlines. An example is a fire-control system where all
targets take an identical amount of time to process but may arrive at different times and have
different deadlines for the targeting solution dependent upon target speed and location.

LOVELY PROFESSIONAL UNIVERSITY 93