Page 99 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes • If there are no periodic or aperiodic tasks waiting to execute the capacity of C is consumed
in idle time. In order to implement the algorithm, the capacity of the server and the periodic
process capacity must be updated every time there is an exchange and the server must be
checked to ensure that its capacity has not been exhausted. The Dual Priority algorithm is
an example of the class of algorithms that identify and exploit spare processing capacity in
the system. Under this algorithm, hard periodic tasks execute at either an upper or lower
band priority level. At their ready time, the tasks assume the lower band priority. After
a fixed time from their ready time, they are promoted to the high priority band. Other
soft deadline tasks are assigned a medium priority in between the two bands. This way
soft deadline tasks are given preferential scheduling until hard priority tasks undergo
promotion. The offset from the ready time in which promotion takes place is determined
for each task via off-line analysis, using worst case arrivals and execution times. The spare
capacity reclamation is accomplished by identifying spare capacity that becomes available
when tasks do not arrive at their maximum rate. The Polling Server (PS) algorithm schedules
a periodic task, the polling server that is used to provide relative high priority services to
aperiodic tasks. Every time it executes, it is available to service existing or newly arriving
aperiodic tasks during its execution period. The server is subject to preemption by higher
priority tasks and runs until it either its period ends or until there is no aperiodic tasks left
to execute. In the latter instance, it looses any time that was left in its period and is unable
to service aperiodic tasks until the beginning of its next execution period. The Deferrable
Server (DS) algorithm, a derivation of the rate-monotonic algorithm, is designed to improve
the response time of the system to aperiodic tasks by deferring the completion time of hard
periodic tasks while ensuring that their deadlines are still met. This algorithm is another
instance of dynamic algorithms that utilize a special server process to service aperiodic
tasks. The Deferrable Server algorithm schedules a periodic task to service aperiodic tasks
with high priority. Like the Polling Server, it is ready to service aperiodic tasks that are
waiting or arrive during its period unless it is preempted or runs out of execution time.
Aperiodic tasks that arrive outside of its period are scheduled as background tasks. Unlike
the Polling Server, however, it does not lose its remaining execution time once no more
aperiodic tasks are pending. It remains able to service aperiodic tasks until the end of
its period, at which time any unused execution time is lost. It is important to note that
the Deferrable Server (DS) task is different from the other periodic tasks in the system.
It is demand driven and does not run unless there is an aperiodic task to service. This
means that it does not necessarily begin execution at the beginning of its period. It defers
its execution until needed. The DS task is assigned a priority based on its period. If it is
given the highest priority by making its period no longer than the period of the shortest
periodic task, then it can guarantee responsiveness to aperiodic tasks. At lower priority
levels, the system response to aperiodic tasks begins to degrade. The Reservation-Based
algorithm was designed to guarantee all periodic task deadlines while minimizing the
chances of missing an aperiodic task’s deadline. The algorithm schedules all periodic tasks
using the rate-monotonic technique. Aperiodic tasks are assumed to have lower priorities
than periodic tasks and are scheduled First-Come, First-Served by using processor time
that is left over after all the periodic tasks have been executed. This is accomplished by
designating a unit cycle, which is the greatest common divisor of all task periods. The
time left over in each unit cycle is reserved for the execution of aperiodic tasks. The
Reservation-Based algorithm differs from the Polling and Deferrable server algorithms
in that it does not create a periodic server to deal with the aperiodic tasks. This makes
it much simpler to implement. It also has the goal of ensuring that aperiodic tasks meet
their deadline, in contrast to the PS and DS goal of quick response. The largest drawback
of dynamic priority-based algorithms is the overhead required to identify spare capacity
in the system. Along with this overhead, there is a processor utilization issue. Several
of the algorithms sacrifice some portion of useable CPU time in order to rapidly service
aperiodic tasks. This can require a more powerful processor in order to provide the extra
computing capacity or there may be other periodic tasks that could have been incorporated
into the design that were eliminated to provide the extra capacity.

92 LOVELY PROFESSIONAL UNIVERSITY