Page 98 - DCAP103_Principle of operating system

Unit 3: Process Management-II

each task with a later deadline is computed. When this is complete, if no overloads are predicted, Notes
the task with the earliest deadline is removed from the queue and begins execution. If an
overload is predicted, the algorithm scans the ready queue and removes the lowest priority task.
It then re-computes the execution sums. This process continues until there is either no overload
predicted or until the ready queue is empty. One obvious drawback to this algorithm is that
under overload conditions, the processor can spend a significant amount of time attempting to
perform scheduling, which adds to the overload problem by using up CPU resources.

Another algorithm that is based upon the EDF algorithm is the Total Bandwidth server. This
algorithm is based on the concept that many real-time systems consist of both hard periodic
tasks and firm aperiodic tasks. To guarantee the timely completion of the hard periodic tasks
in overload conditions, it is sometimes necessary to reject some of the aperiodic tasks. A special
Server task is included in the system whose computation time, or capacity, is used to service these
aperiodic tasks. This way, aperiodic tasks can be serviced in a more predictable fashion without
jeopardizing the completion of hard periodic tasks. In this algorithm, a value is assigned to each
aperiodic task. This value is only received if the task completes by its deadline. It is also used to
determine which tasks should be rejected during overload conditions. During overload conditions,
the algorithm has to make choices on which tasks will complete and which will not in order
to maximize the value of the system. The original Total Bandwidth server algorithm works by
assigning a suitable deadline to each aperiodic task when it arrives and then scheduling it with
the periodic tasks using the EDF algorithm. The deadline for the aperiodic task is determined
as follows. When the k-th aperiodic task arrives at time t=r, it is given the deadline d where:
k k( ) drd C=+ max , k U kkk1 –S where d is the deadline of the k-1-th task,C is the maximum
execution time k-1kof the task and Uis the server utilization factor (its bandwidth in terms of S
CPU execution time). The task is then placed in the ready queue as defined by EDF.
The algorithm has been extended to add resource reclamation and to provide a robust guarantee
mechanism to provide graceful degradation of the system under overload conditions. The original
algorithm used the maximum execution time of the task to schedule a portion of the server’s
bandwidth. Not all tasks take the maximum amount of time to complete. In order to reclaim
the server bandwidth that was scheduled for a task, the actual execution time of a task that
completes early is used to compute the deadline that could have been assigned to it if its actual
execution time had been known. This adjusted value is then used to compute the deadline of the
following request. Graceful degradation during overload conditions is added to the algorithm
by calculating the deadline as shown above and comparing it to the task’s actual deadline. If
the computed deadline is less than or equal to the actual deadline, the task is accepted and
scheduled. If the computed deadline is later, the algorithm searches for the lowest value task
that has been scheduled and rejects it in the hope that the newly arrived task can be scheduled
with guaranteed completion. This search continues until the task has either been scheduled or
the ready queue is empty. Another server algorithm is the Dynamic Priority Exchange (DPE)
server. This algorithm trades the server execution with lower priority periodic tasks (those
with later deadlines) when there are no aperiodic tasks to be serviced. This way no CPU time
is wasted, it is only exchanged between tasks, unless the system is idle.
The server has a period T and a capacity C. At the beginning of each S S period, the server’s
capacity is set to C . Each periodic task that has a S deadline within the current period is assigned
an aperiodic capacity which is initially set to 0. All tasks are then assigned priorities via the
EDF algorithm. When the highest priority in the system is an aperiodic capacity of C units of
time, the following occurs:
• If there are aperiodic tasks waiting to be serviced, they are executed until they either
complete or the capacity of the server has been exhausted. If there are no aperiodic tasks
awaiting service, the periodic task with the earliest deadline is executed and a capacity
equal to the execution time of that task is added to the aperiodic capacity of the task’s
deadline and subtracted from C. This has the effect of exchanging the deadlines of the
highest priority capacity and the periodic task.

LOVELY PROFESSIONAL UNIVERSITY 91