Page 91 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes aa a( )
into a corresponding periodic process
rc d prd,, , that satisfies the pp p p( )
following conditions:

ccddcprd dd r=== = — =, , min , min ,10 p aa pa p a p ap
where cis the worst case computation time, dis the deadline, ris the release time,prd is the
period and min is the minimum time between invocations of the aperiodic task. A major
advantage of pre-run-time scheduling is a significant reduction in run-time resources required
for scheduling. However, it is inflexible. Any change requires re-computing the entire
schedule. Additionally, it cannot handle an environment that is not completely predictable.
Its real advantage is that in a predictable environment it can guarantee system performance.
In many cases, it is the only practical way to provide absolute predictability in a complex
real-time system Although pre-run-time scheduling has several advantageous characteristics,
there are also several concerns that must be addressed. A pre-run-time schedule is of little
use if it does not satisfying the system timing constraints. Using pre-run-time scheduling,
this can be guaranteed for sets of periodic and aperiodic functions if aperiodic functions are
translated to periodic functions and a feasible schedule can be found where every process
starts after its release time and completes before its deadline within a period that is contained
within the least common multiple of their periods. In systems using pre-run-time scheduling,
there is generally (if not always) a required ordering of the execution of processes. This can
be accommodated by using precedence relations that are enforced during the pre-run-time
scheduling. Preventing simultaneous access to shared resources and devices is another
function that pre-run-time scheduling must enforce. This can be accomplished by defining
which portion of a process cannot be preempted by another and then defining exclusion
constraints and enforcing them during the pre-run-time scheduling. Another goal that may
be desired for pre-run-time schedules is reducing the cost of context switches caused by
preemption. This can be accomplished by choosing algorithms that do not result in a large number
of preemptions, such as Earliest Deadline First. It is also desirable to increase the chances that a
feasible schedule can be found. If the input to the chosen pre-run-time scheduling algorithm is
exactly the input to the real system and not an approximation, then the mathematical pre-run-
time algorithms are more likely to find a feasible schedule. As an example of a pre-run-time
algorithm, their systems consist of a set of semi-preemptable activities that is modeled as a set
of non-preemptible beads. These beads have four types of constraints:
1. Absolute timing constraints, where each bead must be scheduled between an earliest start
time and its deadline.
2. Relative timing constraints, consisting of precedence relations between the beads.
3. Consistency constraints, which require an order between subsets of beads to enforce
consistent usage of shared resources.
4. Independency constraints, which are used to exploit knowledge that only one alternative of
a conditional is executed at run-time. The algorithm uses a heuristic scheduling approach,
where the application designer specifies processes, resources, and constraints. Processes
are then divided into non-preemptible beads based on pre-defined preemption points
and functional constraints are derived. At this stage, each process and all its resources
are assigned to an individual processor. Now all communication paths are known so
communication beads are added and functional constraints are adjusted as necessary. Beads
are then grouped into non-preemptible blocks to decrease context switching overhead and
to reduce the number of discrete items that need to be scheduled. Windows are defined
in which if all beads in a block complete within the window, all constraints have been
met. Blocks are assigned a sequence so each falls within its window and no blocks overlap
(on any discrete processor). If a feasible schedule can not be found, the non-preemptible

84 LOVELY PROFESSIONAL UNIVERSITY