Page 85 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes 3.6 Scheduling Algorithms

Real-time systems are systems in which correctness depends not only upon the logical correctness
of the system but also upon the temporal correctness. If the system produces the correct
logical results, but at the wrong time it has failed. Laplante defines a real-time system as
“a system that must satisfy explicit (bounded) response-time constraints or risk severe
consequences, including failure”. Examples of real-time systems are robotics controls,
weapons guidance systems, anti-lock brakes, flight control systems, and engine and emissions
controls. Characteristically, these systems have rigid time requirements on the operation of
the processor or the flow of data. The system is normally multi-tasking and uses periodic
or aperiodic tasking (or some combination of the two). A real-time system usually has
requirements for bounded response time and typically does not utilize secondary storage or
virtual memory because of the non-determinism introduced by these techniques. Failure to
meet response time constraints results in system failure. In the literature, real-time tasks are
usually referred to as having either hard or soft constraints. These are differentiated by the
criticality of their on-time completion. A task with hard timing constraints must complete
within these constraints or the system fails. Tasks with soft timing constraints that do not
complete within their constraints degrade the system but do not cause system failure.

In hard real-time systems, there are two types of processes—periodic and aperiodic
(asynchronous). A periodic process is one which is repeatedly executed once each period.
An aperiodic process is one that occurs in response to some internal or external event. They
are unpredictable in nature but generally have some form of constraint that will allow them
to be modeled. Xu and Parnas state that periodic processes with hard deadlines dominate
most hard real-time systems. Aperiodic processes are minimal in number and require only
minimal CPU time. Additionally, although precise request times for aperiodic processes
are not known, usually a minimum amount of time between two consecutive requests can
be defined. Today’s real-time systems have several drawbacks. Even though timing errors
(missed deadlines) are among the most difficult and costly errors to find and correct, many
safety-critical hard real-time systems are built using techniques and methodologies that
provide no guarantees that timing constraints will be met. The systems are generally based
on static designs if the system is predictable. This makes the designs inflexible in operation
and difficult and expensive to change. If the systems are not based on static designs, then
they tend to lack predictability except under strict conditions that are usually not realistic in
real world applications. Next generation real-time systems must be designed and constructed
to be dynamic in operation to adjust to changing conditions, predictable in performance
so that correctness can be guaranteed and flexible so that changes can be made easily and
inexpensively.

1 Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9

4 3 5
FCFS

78 LOVELY PROFESSIONAL UNIVERSITY