Page 93 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes The flexibility of on-line scheduling makes up for most of the deficiencies when it comes to
implementing a real world system.

The flexibility of on-line scheduling makes up for most of the deficiencies
when it comes to implementing a real world system.

3.6.5 Non-Preemptive Static Priority Algorithms
Many real-time systems have the characteristic in which the order of task execution
is known a priori and each task must complete before another task can start. These
systems can be scheduled non-preemptively. This scheduling technique avoids
the overhead associated with multiple context switches per task and can achieve
very high processor utilization. These systems are modelled as systems of mutually
constrained, sequential tasks. These constraints are of the form—Static non-preemptive
run-time scheduling has the advantage of high efficiency since the only context switches
performed are to initiate a new task. Additionally, tasks are guaranteed of meeting execution
deadlines. Two non-preemptive algorithms will be examined—the parametric dispatching
algorithm. Both of these algorithms attempt to provide high processor utilization while
preserving task deadline guarantees and system schedulability. The parametric dispatching
algorithm uses a calendar of functions, which maintains for each task functions, F min and F
max, describing the upper and lower bounds on the allowable start times for the task. During an
off-line component, the timing constraints between tasks are analyzed to generate the calendar
of functions. During system execution, a calendar evaluator determines the upper and lower
bounds for the start times for each task. These bounds are then passed to a dispatcher which then
determines when within the window to start execution of the task. This decision can be based
on whether there are other non-real-time tasks waiting to execute. Singh’s predictive algorithm
depends upon known a priori task execution and arrival times. When it is time to schedule a
task for execution, the scheduler not only looks at the first task in the ready queue, but also
looks at the deadlines for tasks that are predicted to arrive prior to the first task’s completion.
If a later task is expected to arrive with an earlier deadline then the current task, the scheduler
may insert CPU idle time and wait for the pending arrival if this will produce a better schedule.
In particular, the insertion of idle time may keep the pending task from missing its deadline.
Suppose there is a task t with deadline D currently at the head of the queue 11 and there is
another task, t with deadline D whose predicted arrival time, r,222 is later then the current time.
If t and t’s execution times result in t 12 2 completing later than t’s deadline, then t will miss its
deadline if t is 221 dispatched first. In this case, the only feasible schedule requires that the CPU
idle while waiting for t’s arrival2. These algorithms both have drawbacks when applied to real-
world systems. Both algorithms require significant a priori knowledge of the system tasks, both
execution times and ordering. Because of this, they are quite rigid and inflexible. Even minor
task changes require significant rework of the scheduler. Additionally, the parametric algorithm
is not a scheduling algorithm in its own right since it requires a predetermined task ordering. It
is best used in conjunction with another scheduling technique. Future areas of development in
non-preemptive scheduling include determining necessary and sufficient conditions for a task
set to be schedulable. Additionally, neither of these algorithms has any technique for handling
aperiodic tasks. Further work needs to go into incorporating non-preemptive scheduling with
some other scheduling algorithm to handle aperiodic tasking and thus be useful for other than
severely constrained systems.

3.6.6 Preemptive Static Priority-based Algorithms
In the early days of real-time computing, real-time systems were built around a cyclic executive,
similar to a very rudimentary off-line scheduler, and constructed in a fairly undisciplined

86 LOVELY PROFESSIONAL UNIVERSITY