Page 101 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes 3.6.11 Monotonic Absolute Deadlines
A task requesting service is guaranteed to have a deadline that is at least as late as all other
tasks that have previously requested service. This is essentially a first-come, first-served system,
such as might occur in a process control system where the processing steps are strictly ordered.
3.6.12 Equal Relative Deadlines
All tasks in this model have the same relative deadlines. This is similar to the offer by a well
known pizza delivery company that your pizza will be there in 30 minutes or it is free.
3.6.13 Equal Absolute Deadlines

In this case, all tasks have the same absolute deadline. An example is a banking system in which
transactions occur at random times during the day and require varying amounts of processing
but must all be completed by the end of the business day. Algorithms of this class have the
advantage of being very flexible in dealing with a varying system environment and being able
to deal with overload conditions without total failure. In fact, except for the condition of Equal
Request Times and Equal Absolute Deadlines, the efficiency of the schedule generated by a
Dynamic Best Effort scheduling algorithm is only one half to two-thirds that of an optimal
scheduler. In the most general terms, the Dynamic Best Effort scheduling algorithms differ only
in the way they assign priorities. For example, the Earliest Deadline First algorithm attempts to
minimize task failures by scheduling the task with the earliest deadline to execute first.
Unfortunately, this algorithm suffers from the domino effect, where the failure of one task
dominos and causes other tasks further down the line to also miss their deadline. Because of
this, its performance rapidly degrades under overload conditions. Another approach is to
schedule the task with the highest value first. In this case, the task that has the most importance
to the system is the first to run. A third approach is to prioritize task dispatching by task density,
where density is the importance value of the task divided by the cost to execute the task. This
approach tends to maximize the cumulative value of the tasks that complete by their deadlines.
A mixed approach has also been used. Here the importance value of a task and its deadline are
both used to compute a weighted sum of the importance and the deadline which is then used
to determine the task’s priority. Unfortunately, none of these algorithms as presented provide
any form of guarantee of task completion. Because of this, they are all prone to the domino
effect described earlier since they have no awareness of the current processor loading and
therefore if scheduling a new task will cause a problem. Buttazzo, et al. have proposed and
characterized a class of extensions to the previous algorithms they refer to as guaranteed. These
extensions perform an acceptance test before accepting a new task for execution. If a processor
overload will occur by accepting the newly arrived task, it is rejected. Unfortunately, this
extension does not consider the importance of the task so an extremely important task may be
rejected so that a task of low importance can run. To counter this problem they have proposed
a robust extension. This extension performs by applying the acceptance test to each arriving
task similar to the guaranteed extension. However, if an overload condition is detected, the least
valued task that will remove the overload is rejected rather than blindly rejecting the newest
task. Additionally, rejected tasks are temporarily maintained in a reject queue from which they
can possibly be executed at a later point in time. Another Dynamic Best Effort algorithm, for
situations such as voice or video, where m of n tasks must complete by their deadline has been
proposed by Hamdaoui and Ramanathan. This system model is more m restrictive than a system
in which percent of the tasks must complete by n their deadline. The latter model allows failing
tasks to group together which still meets the percentage of task completion criteria but can
severely degrade system performance. As an example, consider live video. Missing two frames
out of every 20 may only cause a little static or jerkiness in the picture. However, missing the
middle 40 frames out of a 400 frame sequence is clearly unacceptable. In the former model,
where the errors are required to be spread out, the Distance Based Priority (DBP) algorithm

94 LOVELY PROFESSIONAL UNIVERSITY