Page 90 - DCAP103_Principle of operating system

Unit 3: Process Management-II

now the principal concerns. The algorithms used, or proposed for use; in real-time scheduling Notes
vary from the relatively simple to the extremely complex. They try to provide deterministic
performance while meeting the timing constraints of the system. Real-time algorithms can be
divided into several classes of algorithm. The two major classes are off-line algorithms, which
generate scheduling information prior to system execution which is then utilized by the system
during runtime, and online algorithms, which generate scheduling information while the
system is running. Online algorithms can be subdivided into static priority based and dynamic
priority based algorithms. Static priority based algorithm’s are relatively simple to implement
but lack flexibility. Dynamic priority based algorithms have the flexibility to cope with changing
environments but are typically complicated to implement and require a large amount of system
resources to execute. Off-line algorithms are theoretically fully predictable since they are fully
deterministic if the system is properly constrained. They are good for applications where all
characteristics are known a priority and change very infrequently. Off-line algorithms require
a fairly complete characterization of all processes involved, such as execution times, deadlines,
and ready times. They typically require large amounts of off-line processing time to produce
the final schedule and due to this they are quite inflexible. Any change to the system processes,
either adding or deleting processes or changing the characteristics of one or more processes
requires starting the scheduling problem over from the beginning. In its favor off-line scheduling
requires minimal run-time processing time. Online Static Priority Based algorithms are arguably
the most common in practice. They have a fairly complete theoretical base and they may be
either preemptive or non-preemptive. They work well with fixed periodic tasks but do not
handle aperiodic tasks particularly well, although there are methods to adapt the algorithms
so that they can also effectively handle aperiodic tasks. A severe problem that can occur with
Static Priority Based algorithms is priority inversion. This occurs when a higher priority task is
blocked by a lower priority task which is using a resource required by the higher priority task.
Dynamic Priority Based algorithms require the largest amount of on-line resources. However,
this allows them to be extremely flexible. Many Dynamic Priority Based algorithms also contain
an off-line component. This reduces the amount of online resources required while still retaining
the flexibility of a dynamic algorithm. There are two subsets of dynamic algorithms—planning
based for guaranteed performance and best effort to maximize performance in overload
conditions. Planning based algorithms guarantee that if a task is accepted for execution, it and
all other previously accepted tasks will meet their time constraints. On the other hand, best effort
algorithms attempt to provide better response to aperiodic tasks or soft tasks while still meeting
the timing constraints of the hard periodic tasks. This is often accomplished by utilizing spare
processor capacity to service these soft or aperiodic tasks.

3.6.3 Real-time Scheduling AlgorithmsOff-line/Pre-run-time Scheduling

In systems using pre-run-time scheduling, the schedule is computed off-line. This requires a
fairly complete characterization of all processes, such as ready times, deadlines, and execution
time requirements. However, it does allow consideration of many different schedule possibilities
since the only time constraint in generating the schedule is the amount of time the developer is
willing to invest. If different system modes or some form of error handling is desired, multiple
schedules can be computed, one for each alternate situation. At run-time, a small run-time
scheduler can choose proper one. This scheduler can also be used for a limited number of
aperiodic processes. Although a strict pre-run-time scheduler has no provisions for handling
aperiodic tasks, it is possible to translate an aperiodic process into a periodic one, thus allowing
aperiodic processes to be scheduled using pre-run-time scheduling.
( )
One way to do this is to translate each aperiodic process
cd,,min

LOVELY PROFESSIONAL UNIVERSITY 83