| Introduction
Definition of Real-Time Systems:
-
Real-time systems have been defined as: "those systems in which the correctness
of the system depends not only on the logical result of the computation,
but also on the time at which the results are produced"; (J. Stankovic,
Misconceptions About Real-Time Computing, IEEE Computer, 21(10), October
1988.)
Features of Real-Time Systems:
-
Real-Time Systems can be described as systems that respond in a timely
predictable way to unpredictable external stimuli arrivals. A
Real-Time System has to fulfill its purpose under unpredictable and often extreme load conditions including:
-
Timeliness: the application has to finish tasks within
time boundaries (deadlines).
-
Simultaneous processing: in a real-time system, more than one event may
happen simultaneously, and all deadlines must be met.
-
Predictability: the real-time system has to react to all possible events
in a predictable way.
-
Dependability or trustworthiness: the real-time system environment must be stable and reliable.
- Real-time (software) was defined by (IEEE 610.12 - 1990) as:
Pertaining to a system or mode of operation in which computation is performed
during the actual time that an external process occurs, in order that the
computation results can be used to control, monitor or respond in a timely
manner to the external process.
Some Further Definitions:
-
Timing constraint: Constraint imposed on timing behavior of a job:
hard or soft.
-
Release Time: Instant of time in which a job becomes available for execution.
If all jobs are released when the system begins execution, then there is
said to be no release time
-
Deadline: Instant of time in which a job's execution is required to be completed.
If the deadline is infinity, then the job has no deadline. Absolute deadline is
equal to the release time plus the relative deadline.
-
Response time: Length of time from release time to the instant job completes.
Hard versus Soft Constraints
-
Hard: Failure to meet the constraint is a fatal fault. Validation system always
meets timing constraints, which may be in the form of:
- Deterministic constraints
- Probabilistic constraints
-
Constraints in terms of some usefulness function.
-
Soft: Late completion is undesirable but generally not fatal. There may be no validation
or only the demonstration job meets some statistical constraint. Occasional
missed deadlines or aborted executions are usually considered tolerable.
Constraints are often specified in probabilistic terms such as:
-
Validation: Demonstration by a provably correct, efficient procedure or
by exhaustive simulation and testing. Involves three steps:
-
Timing constraints of each application, corresponding components are
consistent,
-
Each component can meet its timing constraints if executed alone and required
resources are available,
-
The underlying scheduling algorithms timing constraints are met.
Real-Time Versus Conventional Software:
Real-time software differs significantly from conventional software
in a number of ways:
-
The dominant role of timing constraints. A program must not only produce
the correct answer or output, but it must compute the answer "on time".
A qualitative distinction can be made between hard and soft real-time systems.
-
Concurrency. Computers use concurrency to improve performance, for example,
by employing several processors running in parallel. Real-time software must deal
with the inherent physical concurrency. Real-time systems design becomes
especially difficult when one combines the problems of concurrency with
those related to time. The most complex level are those real-time programs which
include the parallel features of multiprograms but are also execution-time
dependent.
-
Reliability and fault tolerance: Reliability is a measure of how often
a system will fail. Fault tolerance is concerned with the recognition and
handling of failures.
-
A final difference between real-time software and conventional software relates
to testing and certification. Because of the high cost associated with failure,
it is usually not feasible to test and debug systems in their actual
complete environments. Instead, one must rely upon simulations, testing
of subsystems, careful specifications, comprehensive analysis of designs,
and extensive run-time procedures for fault detection and handling.
Periodic and Sporadic Processes:
Real-time systems generally contain two types of processes: periodic
and sporadic.
-
Periodic processes are activated on a regular basis between fixed time
intervals. They are used typically for monitoring, polling, or sampling information
from sensors over a long time interval.
-
Sporadic processes are event driven; they are activated by an external
signal or change of some relationship. A sporadic process may also be used to
react to an event indicating a fault of some piece of equipment.
Aperiodic and Sporadic Tasks
-
A periodic or sporadic task is a stream of aperiodic or sporadic jobs.
-
Jobs within a task have similar statistical behavior and timing requirements.
-
It is assumed the system is stationary within the hyperperiod.
-
Aperiodic jobs have soft or no deadlines.
-
Sporadic jobs have hard deadlines.
-
Job: Unit of work, scheduled and executed by system. characterized by the
following parameters:
-
Temporal parameters: timing constraints and behavior.
-
Functional parameters: intrinsic properties of the job.
-
Resource parameters: resource requirements.
-
Interconnection parameters: how it depends on other jobs and how other
jobs depend on it.
-
Task: Set of related jobs which jointly provide function.
Cyclic Executive (CE) Method:
-
Historically, one of most widely used methods for organizing real-time
software is the cyclic executive approach. The method handles only periodic jobs
or those treated on an ad hoc basis, by assuming that they take
negligible processing time and executing them immediately after their triggering
events are received.
-
In the CE approach, a program code for a period process is broken into sequential
scheduling blocks or actions, each of which has a computation time. Each
such block is scheduled as a unit by the CE, and is nonpreemptible. The Scheduler
will allocate each block to the processor such that the deadlines and
periods of all processes are met.
-
The CE approach has many attractive features, and is simple and efficient, but
also has several limitations and disadvantages. One problem is
how to divide each process into a sequence of actions or scheduling blocks.
The use of the CE method seems to imply that a low-level programming style
is necessary, since modern concurrent programming technologies are incompatible
with the need to break code into predictable blocks and preschedule these
blocks. The method is also inflexible and brittle with respect to changes.
Schedules and Scheduling
-
Job scheduling and the allocation of resources are based on a set of scheduling algorithms
and access control protocols.
-
Scheduler: Module implementing scheduling algorithms.
-
Schedule: Assignment of all jobs to available processors, produced by scheduler.
-
Valid schedule:
-
every processor assigned to at most one job at a time.
-
every job assigned to at most one processor at a time.
-
no job scheduled before its release time.
-
total amount of processor time assigned to every job is equal to its maximum
or actual execution time.
Section Notes
Text readings for this unit are based on:
-
Real-time by E. Douglas Jensen, 2003
-
Introduction
to Real Time by By David B. Stewart, Embedded Systems Programming,
Nov 1, 2001
-
The Challenges of Real-Time
Programming by Jack G. Ganssle
-
Earliest Deadline First Scheduling for Real-Time Java by Markus Pilz, Esmertec, Inc.
|
