Real-Time Systems

Real-Time Systems: A real-time system is any information processing system which has to
respond to externally generated input stimuli within a finite and specified period


 A real-time system is one in which the correctness of the computations not only  depends
on their logical correctness, but also on the time at which the result is produced.
  Failure to respond is as bad as the wrong response.

A real-time system changes its state as a function of physical time, e.g., a chemical
reaction 
continues to change its state even after its controlling computer system has
 stopped.

 Real-Time systems are becoming pervasive. Many embedded systems are referred to as
real-time systems.

Telecommunications, flight control and electronic engines, Networked Multimedia
Systems, Command Control Systems etc are some of the popular real-time system
applications where as computer simulation,  user interface and Internet video are
categorized as non-real time applications.


  often are comprised of a controlling system, controlled system and
Real-time systems
environment.
Controlling system: acquires information about environment using sensors and controls
the environment with actuators.
 
  derived from physical impact of controlling systems activities. Hard and
Timing constraints
soft constraints.
Periodic Tasks : Time-driven recurring at regular intervals.

Aperiodic Tasks : event-driven

Needs of the Real-Time Systems:

• Fast context switches?
– should be fast anyway(Must be fast response time)
• Small size?
– should be small anyway(Portable)
• Quick response to external triggers?
– not necessarily quick but predictable
• Multitasking?
– often used, but not necessarily
• “Low Level” programming interfaces?
– might be needed as with other embedded systems
• High processor utilisation?
– desirable in any system (avoid oversized system)

Typical Real-Time Applications: A real-time system is required to complete its work and
deliver its services on a timely basis. Examples of real-time systems include digital control,
command and control, signal processing, and telecommunication systems.

Digital Control: Many real-time systems are digital control, systems, they are embedded in
sensors and actuators and function as digital controllers (shown in fig ). The term plant in the
block diagram refers to a controlled system, for example, an engine, a brake, an aircraft, a
patient. The state of the plant is monitored by sensors and can be changed by actuators.
  The real-time (computing) system estimates from the sensor readings the current state of
the plant and computes a control output based on the difference between the current state
and the desired state (called reference input in the figure).

 We call this computation the control-law computation of the controller. The output thus
generated activates the actuators, which bring the plant closer to the desired state.

A Simple Example:

Consider an analog single-input/single-outputPID (Proportional, Integral, and Derivative)

controller. This simple kind of controller is com-monly used in practice. The analog sensor
reading y(t) gives the measured state of the plant at time t .

 Let e(t)=r(t)−y(t) denote the difference between the desired state r(t) and the
measured state y(t) at time t . The output u(t) of the controller consists of three terms.

 During any sampling period (say the kth), the control output uk depends on the current
and past measured values yi for i≤k. The future measured values yi ’s for i>k in turn
depend on uk . Such a system is called a (feedback) control loop or simply a loop. We
 can implement it as an infinite timed loop:
set timer to interrupt periodically with period T ;

at each timer interrupt, do

do analog-to-digital conversion to get y;

 compute control output u;

outputu and do digital-to-analog conversion;

end do;
Sampling Period: The length T of time between any two consecutive instants at which y(t) and
r(t) are sampled is called the sampling period. T is a key design choice. The behavior of the
resultant digital controller critically depends on this parameter.

 We consider two factors. The first is the perceived responsiveness of the overall system.
The second factor is the dynamic behavior of the plant.

High-level Control: Controllers in a complex monitor and control system are typically organized
hierarchically. One or more digital controllers at the lowest level directly control the physical plant.
Each output of a higher-level controller is a reference input of one or more lower-level controllers.
With few exceptions, one or more of the higher-level controllers interfaces with the operator.

Examples of Control Hierarchy

A patient care system may consist of microprocessor-based controllers that monitor and control
the patient’s blood pressure, respiration, glucose, and so forth. There may be a higher-level
controller (e.g., an expert system) which interacts with the operator (a nurse or doctor) and
chooses the desired values of these health indicators.
 The computation done by each digital controller is simple and nearly deterministic; the
 computation of a high-level controller is likely to be far more complex and variable.
 While the period of a low-level control-law computation ranges from milliseconds to
seconds, the periods of high-level control-law computations may be minutes, even hours.
Flight Control System:
Below figure shows hierarchy of flight control, flight management and air traffic control
systems.
  The Air Traffic Control (ATC) system is at the highest level.
  It regulates the flow of flights to each destination airport.
 It does so by assigning to each aircraft an arrival time at each metering fix (known
 geographical point, adjacent points are 40-60 miles apart) in the route to destination.
  The aircraft is supposed to arrive at the metering fix at the assigned time.
 At any time while in flight, the assigned arrival time to the next metering fix is a reference
input to the on-board flight management system.

 The flight management system chooses a time-referenced flight path that brings the
 aircraft to the next metering fix at the assigned arrival time.
 The cruise speed, turn radius, descend/ascend rates and so for required to the chosen time-
referenced flight path are the reference inputs to the flight controller at the lowest level of
hierarchy.

  The controller at the highest level of a control hierarchy is a command and control system.
  An Air Traffic Control (ATC) system is an excellent example.
 The ATC system monitors the aircraft in its coverage area and the environment (e.g,
 weather condition) and generates and presents the information needed by the operators.
 Outputs from the ATC system include the assigned arrival times to metering fixes for
individual aircraft.
  These outputs are reference inputs to on-board flight management systems. Thus, the ATC
 system indirectly controls the embedded components in low levels of the control hierarchy.
  In addition, the ATC system provides voice and telemetry links to on-board avionics.
 Thus it supports the communication among the operators at both levels (i.e., the pilots and
 air traffic controllers).
 The ATC system gathers information on the “state” of each aircraft via one or more active
radars. Such a radar interrogates each aircraft periodically. When interrogated, an aircraft
responds by sending to the ATC system its “state variables”: identifier, position, altitude,
heading, and so on.

 The ATC system processes messages from aircraft and stores the state information thus
 obtained in a database.
 This information is picked up and processed by display processors. At the same time, a
surveillance system continuously analyzes the scenario and alerts the operators whenever it
detects any potential hazard (e.g., a possible collision).

 Again, the rates at which human interfaces (e.g., keyboards and displays) operate must be
 at least 10 Hz. The other response times can be considerably larger.
 For example, the allowed response time from radar inputs is one to two seconds, and the
period of weather updates is in the order of ten seconds. And we can see that a command
and control system bears little resemblance to low-level controllers.
  In contrast to a low-level controller whose workload is either purely or mostly periodic, a
command and control system also computes and communicates in response to sporadic
events and operators’ commands.

 Furthermore, it may process image and speech, query and update databases, simulate
various scenarios, and the like. The resource and processing time demands of these tasks
can be large and varied.

 A low-level control system typically runs on one computer or a few computers connected
by a small network or dedicated links, a command and control system is often a large
distributed system containing tens and hundreds of computers and many different kinds of
networks.

SIGNAL PROCESSING:
Anything that carries information is called as signals. It is a real or complex value function
of one or more variables. For example: temperature is one dimensional signal, image is 2-
dimensional.Processing means operating in some fashion on a signal to extract some useful
information. The signal is processed by system which can be electronic, mechanical or a
program.

Most signal processing applications have some kind of real-time requirements. We focus
here on those whose response times must be under a few milliseconds to a few seconds.
Examples are digital filtering, video and voice compressing/decompression, and radar
signal processing.

Processing Bandwidth Demands:

Typically, a real-time signal processing application computes in each sampling period
one or more outputs. Each output x(k) is a weighted sum of n inputs y(i)’s

In the simplest case, the weights, a(k,i)’s, are known and fixed. In essence, this
computation transforms the given representation of an object (e.g., a voice, an image or
a radar signal) in terms of the inputs, y(i)’s, into another representation in terms of the
outputs, x(k)’s. Different sets of weights, a(k,i)’s, give different kinds of transforms.
This expression tells us that the time required to produce an output is O(n).

Radar System

 A signal processing application is typically a part of a larger system.

  The system consists of an Input/Output (I/O) subsystem that samples and
digitizes the echo signal from the radar and places the sampled values in a shared
 memory.
  An array of digital signal processors processes these sampled values.
 The data thus produced are analyzed by one or more data processors, which not
only interface with the display system, but also generate commands to control
the radar and select parameters to be used by signal processors in the next cycle
of data collection and analysis.
Radar Signal Processing:

 To search for objects of interest in its coverage area, theradar scans the area
 by pointing its antenna in one direction at a time.
 During the time the antenna dwells in a direction, it first sends a short radio
frequency pulse. It then collects and examines the echo signal returning to the
antenna.

 The echo signal consists solely of background noise if the transmitted pulse
 does not hit any object.
 On the other hand, if there is a reflective object (e.g., an airplane or storm cloud)
 at a distance x meters from the antenna, the echo signal reflected by the
object returns to the antenna at approximately 2x/c seconds after the
transmitted pulse, where c= 3 × 108 meters per second is the speed of light.

Tracking:
  Noise and man-made interferences, including electronic countermeasure (i.e.,
jamming), can lead the signal processing and detection process to wrong
conclusions about the presence of objects.

 A track record on a non existing object is called a false return. An application
that examines all the track records in order to sort out false returns from real
ones and update the trajectories of detected objects is called a tracker.
 
 Gating:

  Typically, tracking is carried out in two steps: gating and data association.
 Gating is the process of putting each measured value into one of two categories
depending on whether it can or cannot be tentatively assigned to one or more
established trajectories.

 The gating process tentatively assigns a measured value to an established
trajectory if it is within a threshold distance G away from the predicted current
position and velocity of the object moving along the trajectory.

 The threshold G is called the track gate. It is chosen so that the probability of a
valid measured value falling in the region bounded by a sphere of radius G
centered around a predicted value is a desired constant.
Process:

 At the start, the tracker computes the predicted position (and velocity) of the
 object on each established trajectory.
 In this example, there are two established trajectories, L1 and L2. We also call
the predicted positions of the objects on these tracks L1 and L2. X1, X2, and X3
are the measured values given by three track records.

 X1 is assigned to L1 because it is within distance G from L1. X3 is assigned to
 both L1 and L2for the same reason.
  On the other hand, X2is not assigned to any of the trajectories.
 Itrepresents either a false return or a new object. Since it is not possible to
distinguish between these two cases, the tracker hypothesizes that X2 is the
position of a new object.

 Subsequent radar data will allow the tracker to either validate or invalidate this
hypothesis. In the latter case, the tracker will discard this trajectory from further
consideration.
  
 Data Association:

 The tracking process completes if, after gating, every measuredvalue is assigned
to at most one trajectory and every trajectory is assigned at most one measured
value.

 This is likely to be case when (1) the radar signal is strong and interference is
low (and hence false returns are few) and (2) the density of objects is low. Under
adverse conditions, the assignment produced by gating may be ambiguous, that
is, some measured value is assigned to more than one trajectory or a trajectory
is assigned more than one measured value.

 The data association step is then carried out to complete the assignments and
resolve ambiguities.

Other Real-Time Applications:

  Real-time databases:
  Transactions must complete by deadlines.
 Main dilemma: Transaction scheduling algorithms and real-time scheduling
 algorithms often have conflicting goals.
  Data may be subject to absolute and relative temporal consistency requirements.
 Overall goal: reliable responses
  
Multimedia:
  Want to process audio and video frames at steady rates.
  TV video rate is 30 frames/sec. HDTV is 60 frames/sec.
 Telephone audio is 16 Kbits/sec. CD audio is 128 Kbits/sec
Hard versus Soft Real-Time Systems:


A real-time system can be further divided into soft and hard real-time system on the basis
of severity of meeting its deadlines, timing constraints ( response time , release time)
  A hard real-time system cannot afford missing even a single deadline. That is, it
 has to meet all the deadlines to be branded as a hard one.
 Soft real-time system takes the middle path between a non-real-time system and
a hard real-time system. That is, it can allow occasional miss.
  Real-time systems can be predictable and deterministic. 

 A predictable real-time system is one whose behavior is always within an

acceptable range.

 A deterministic system is a special case of a predictable system. Not only is the
timing behavior within a certain range, but that timing behavior can be predictable.

Hard real-time systems: A Real-Time System in which all deadlines are hard.Hard Real-Time
System guarantees that critical tasks complete on time. This goal requires that all delays in the
system be bounded from the retrieval of the stored data to the time that it takes the to finish any
request made of it.

 The requirement that all hard timing constraints must be validated invariably places many
re-strictions on the design and implementation of hard real-time applications as well as on
 the architectures of hardware and system software used to support them.
  An overrun in response time leads to potential loss of life and big financial damage.
 Many of these systems are considered to be safety critical. Sometimes they are “only”
 mission critical, with the mission being very expensive.
 In a hard real-time system, the peak-load performance must be predictable and should not
 violate the predefined deadlines.
  Hard real-time systems are often safety critical even load is very high.
  Hard real-time systems have small data files and real-time databases.
  In general there is a cost function associated with the system.
  Strict about each task and its deadline.
  The preemption period (the delay it can handle max ) should be very less( micro second)
 For example: Rocket launching, Nuclear Power Plant control, Flight Control System.
1
Some Reasons for Requiring Timing Guarantees:


Many embedded systems are hard real-time systems. Deadlines of jobs in an embedded
system are typically derived from the  required responsiveness of the sensors and
 actuators monitored and controlled by it.
 As an example, consider an automatically controlled train. It cannot stop
instantaneously. When the signal is red (stop), its braking action must be activated
a certain distance away from the signal post at which the train must stop.

 This braking distance depends on the speed of the train and the safe value of
deceleration. From the speed and safe deceleration of the train, the controller can
compute the time for the train to travel the braking distance.

 This time in turn imposes a constraint on the response time of the jobs which sense
and process the stop signal and activate the brake. No one would question that this
 timing constraint should be hard and that its satisfaction must be guaranteed.

Jobs in some non-embedded systems may also have hard deadlines. An example is a
  must be highly available: The system must never be
critical information system that
down for more than a minute.

In recent years, this observation motivated a variety of approaches to soften hard dead-
 deadlines or premature terminations as long
lines. Examples are to allow a few missed
as they occur in some acceptable way.
More on Hard Timing Constraints:

There may be no advantage in completing a job with a hard deadline early. As long as the
job completes by its deadline, its response time is not important. In fact, it is often
advantageous, sometimes even essential, to keep the response times of a stream of jobs
small. Hard and soft timing constraints allow a hard timing constraint to be specified in
any terms. Examples are
 • Hard: failure to meet constraint is a fatal fault. Validation system always meets
timing constraints.
  
Deterministic constraints
  
Probabilistic constraints
 
 Constraints in terms of some usefulness function.
• Soft: late completion is undesirable but generally not fatal. No validation or only
demonstration job meets some statistical constraint. Occasional missed deadlines or
aborted execution is usually considered tolerable. Often specified in probabilistic
terms
Soft real-time systems: A real-time system in which some deadlines are soft. A Soft Real-
Time Systems,in which jobs have soft deadlines is. The developer of a soft real-time system
is rarely required to prove rigorously that the system surely meet its real-time performance
objective. Examples of such systems include on-line transaction systems and telephone
switches, as well as electronic games.

 In a soft real-time system, a degraded operation in a rarely occurring peak load can be
tolerated. A hard real-time system must remain synchronous with the state of the
 environment in all cases.
  Soft real-time systems will slow down their response time if the load is very high.
  Deadline overruns are tolerable, but not desired.
  There are no catastrophic consequences of missing one or more deadlines.
  There is a cost associated to overrunning, but this cost may be abstract.
 The task and its deadline is manageable but we should met the condition most of the all
 the time.
  The preemption period for this can be more (around milisecond ).
 For example : Washing machine , Stock price quotation System Mobile phone, digital
cameras and orchestra playing robots.

A Reference Model of Real-Time Systems:

 • Modeling the system to focus on timing properties and resource requirements. Composed
of three elements:
  
Workload model - describes applications supported by system
  Temporal parameters
 Functional parameters
  
Resource model - describes system resources available to applications
  Modeling resources (Processors and Resources)
 Resource parameters
  
Algorithms - defines how application uses resources at all times.
 Scheduling Hierarchy

  Task (Ti): Set of related jobs jointly provide function.


 of work, scheduled and executed by system. characterized by the following
Job (Jij): Unit
parameters:
i. Temporal parameters: timing constraints and behavior
ii. Functional parameters: intrinsic properties of the job.
iii. Interconnection parameters: how it depends on other jobs and how other jobs
depend on it.
iv. Resource parameters: resource requirements.


Processors and Resources: we can divide the system resources into two major types:
 processors and resources. Processors are often called servers and active resources.

Computers, transmission links, disks, and database server are examples of processors.
They carry out machine instructions, move data from one place to another, retrieve
files, process queries, and so on. Every job must have one or more processors in order
to execute and make progress toward completion
• Resources can be divided into passive and active:
• Active resources = Processors (Pi): they execute jobs.
  
Every job must have one or more processors
  
Same type if functionally identical and used interchangeably.
• Passive resource = Resource (Ri):
  
Job may require Resources in addition to processor.
 
Reusable resources are not consumed
Task Temporal Parameters:
 Hard real-time: Number and parameters of tasks are known at all
time. for Job Ji:

Release time (ri) : is the time at which the job becomes ready for execution.
Absolute deadline( di): is the time at which the job should be completed.
Relative deadline(Di): is the time length between the arrival time and the
absolute deadline.
Start time (sj): is the time at which the job starts its execution.
Finishing time (fj): is the time at which the job finishes its execution.
Execution time (ei): May know range [e-, e+]. Most deterministic models use e+.

 Periodic Task Model: In periodic task, jobs are released at regular intervals. A periodic
task is one which repeats itself after a fixed time interval. A periodic task is denoted by five
 tuples: Ti = < Φi, Pi, ei, Di >
 Where,
Task Ti is a serious of periodic Jobs Jij.
i - phase of Task Ti, equal to ri1.
pi - period, minimum inter-release interval between jobs in Task Ti. Must be bounded
from below.
ei - maximum execution time for jobs in task Ti.
Di – is the relative deadline of the task.
rij - release time of the jth Job in Task i (Jij in Ti).
H –Hyperperiod = Least Common Multiple of pi for all i:
H = lcm(pi), for all i.
ui - utilization of Task Ti.
U - Total utilization = Sum over all ui.
1. Aperiodic Tasks: In this type of task, jobs are released at arbitrary time intervals i.e.
randomly. Aperiodic tasks have soft deadlines or no deadlines.
2. Sporadic Tasks: They are similar to aperiodic tasks i.e. they repeat at random instances. The
only difference is that sporadic tasks have hard deadlines. A sporadic task is denoted by three
tuples: Ti =(ei, gi, Di)
Where
ei – the execution time of the task.
gi – the minimum separation between the occurrence of two consecutive instances of the
task. Di – the relative deadline of the task.

Jitter: Sometimes actual release time of a job is not known. Only know that ri is in a range [ ri-,
ri+ ]. This range is known as release time jitter. Here ri– is how early a job can be released and ri+
is how late a job can be released. Only range [ ei-, ei+ ] of the execution time of a job is known.
Here ei– is the minimum amount of time required by a job to complete its execution and ei+ the
maximum amount of time required by a job to complete its execution.

Functional Parameters:
While scheduling and resource access control decision are being made certain functional
parameters do affect the job.
o Preemptivity

Preemption: suspend job then dispatch different job to processor. Cost includes
context switch overhead.
  
Non-preemptable task - must be run from start to completion.
o Criticalness - positive integer indicating the relative importance of a job. Useful during
overload.
o Optional Executions - jobs or portions of jobs may be declared optional. Useful during
overload. In contrast, jobs and portions of jobs that are not optional are mandatory;
they must be executed to completion.
o Laxity - Laxity type of a job indicates whether its timing constraints are soft or hard.
Supplemented by a usefulness function. Useful during overload.
Resource Parameters: Job resource parameters indicate processor and resource requirements.
1. Preemptivity of resources
2. Resource Graph
Preemptivity of resources:
  A resource in non-preemptable if each unit of resource is constrained to be used serially.

 Once the unit of non-preemptable resource is allocated to a job, the other job needing the unit
must wait until the job completes its use.

every resource in an interleaved manner, then the resource is called
If a job can use
preemptable.

Resource Graph:
  Resource graph is used to describe the configuration of the resources.
 
 In a resource graph, there is a vertex for every processor or resource Ri in the system.
  
The attributes of the vertex are the parameter of the resources.

resource is processor or passive resource and number
Resource type of a resource tell if the
gives the available number of units.


 An edge from vertex Ri to Rk can mean Rk is component of Ri(memory is a part of
computer).
  This edge is an is-a-part-of-edge.
  
Some edges in resource graph represent the connectivity between the components.
 
These edges are called accessibility edges.(Connection between two CPUs)