Course Code: CST 551
Real Time Operating System
1
Course Overview
L T P : 3 0 0 Credits: 3
Text Books:
An Embedded Software Prime r, David E. Simon Pearson
Education Asia Publication ISBN-13: 978020161569
Real Time Systems, C.M. Krishna and Kang G. Shin, TMH
Publication ISBN 13:9780070701151
Refrences:
Real-time Operating Systems: Book 1 – The Theory (The
engineering of real-time embedded systems)‖ by Jim Cooling
Latest Relevant Research Papers
2
Course Objectives
Syllabus deals with issues in real time operating systems,
importance of deadlines and concept of task scheduling.
Student will be able to understand and design real time
operating systems which are backbone of embedded industry
3
Course Outcomes
CO1. Student will be able to explain and give examples of real
time operating systems.
CO2. Student will be able to solve scheduling problems and can
apply them in real time applications in industry.
CO3. Student can also design an RTOS and will be able to
interpret the feasibility of a task set to accomplish or not.
CO4. Analyse the situation of fault occurrence and will be able
to apply solutions accordingly.
4
Course Outcomes
CO1. Student will be able to explain and give examples of real
time operating systems.
CO2. Student will be able to solve scheduling problems and can
apply them in real time applications in industry.
CO3. Student can also design an RTOS and will be able to
interpret the feasibility of a task set to accomplish or not.
CO4. Analyse the situation of fault occurrence and will be able
to apply solutions accordingly.
5
Syllabus
6
Syllabus
7
Introduction to Real Time Systems
Real-time systems play a considerable role in our society, and they cover a
spectrum from the very simple to the very complex.
Examples of current real-time systems include:
the control of domestic appliances like washing machines and televisions
the control of automobile engines, telecommunication switching systems,
military command and control systems,
industrial process control, flight control systems, and space shuttle and
aircraft avionics.
8
Introduction to Real Time Systems
All of these involve gathering data from the environment, processing of
gathered data, and providing timely response.
A concept of time is the distinguishing issue between real-time and non-
real-time systems.
When a usual design goal for non- real-time systems is to maximize system's
throughput, the goal for real-time system design is to guarantee, that all
tasks are processed within a given time.
Real-time operating systems are an integral part of real-time systems.
Future systems will be much larger, widely distributed and will be expected
to perform a constantly changing set of duties in dynamic environments.
This also sets more requirements for future real-time operating systems.
9
Introduction to Real Time Systems
A real-time system is able to reliably execute programs with very specific
timing requirements. A real-time system is one Whose correctness involves
both the logical correctness of outputs and their timeliness.
As defined by Donald Gillies “A real-time system is one in which the
correctness of the computations not only depends upon the logical
correctness of the computation but also upon the time in which the result is
produced. If the timing constraints are not met, system failure is said to
have occurred.”
The design of a real-time system must specify the timing requirements of the
system and ensure that the system performance is both correct and timely.
10
Three Types of Time Constraints:
Hard: Degree of tolerance for missed deadlines is extremely small or zero. A late
response is incorrect and implies a system failure.
Soft: Deadlines may be missed and can be recovered from. Reduction in system quality
is acceptable. If a single computation is late, it is not usually significant, although
repeated late computation can result in system failures.
Hard real-time systems guarantee (When programmed correctly) that a deadline will be
consistently met, while soft real-time systems may periodically exceed the deadline.
Firm: This is a combination of both hard and soft timeliness requirements. The
computation has a shorter soft requirement and a longer hard requirement.
For example, a patient ventilator must mechanically ventilate the patient a certain
amount in a given time period. A few seconds‘ delay in the initiation of breath is allowed,
but not more than that. 11
Components that make up Real Time
Systems
12
Introduction to Real Time Systems
Real-time systems are defined as those systems in which the correctness of
the system depends not only on the logical result of computation, but also on
the time at which the results are produced.
A common misconception is to consider, that real-time computing is
equivalent to fast computing.
ln traditional non-real-time computer systems, the performance goal is
throughput: as many tasks should be processed as possible in given time
period.
Real-time systems have a different goal to meet: as many tasks as possible
should be executed so, that they will complete and produce results before
their time limit expires.
ln other Words, the behavior of real-time system must be predictable in all
situations.
13
Real Time Operating Systems
A Real-Time Operating System (RTOS) comprises of two components, viz.
Real-Time and Operating System
Real-time systems are those systems in which the correctness of the system
depends on the logical result of computation, and on the time at which the
results are produced.
An Operating system is nothing but a collection of system calls providing an
interface between hardware and application programs
RTOS is therefore an operating system that supports real-time applications by
providing logically correct result Within the required deadline.
A multitasking operating system proposed for real-time applications is known
as real- time operating system.
Basic Structure is similar to regular OS but, in addition, it provides
mechanisms to allow real time scheduling of tasks.
14
Difference: RTOS v/s GPOS
Determinism — The key difference between general-computing operating
systems and real-time operating systems is the —deterministic “timing behavior
in the real-time operating systems.” Deterministic" timing means that OS
consume only known and expected amounts of time. RTOS have their worst
case latency defined. Latency is not of a concern for General Purpose OS.
Task Scheduling - GPOSare optimized to run a variety of applications and
processes simultaneously, thereby ensuring that all tasks receive at least some
processing time. As a consequence, low-priority tasks may have their priority
boosted above other higher priority tasks, which the designer may not want.
However, RTOS uses priority-based preemptive scheduling, which allows high-
priority threads to meet their deadlines consistently.
15
Difference: RTOS v/s GPOS
Preemptive kernel -ln RTOS, all kernel operations are preemptible
Priority Inversion - RTOS have mechanisms to prevent priority inversion
Usage - RTOS are typically used for embedded applications, While General
Purpose OS are used for Desktop PCs or other generally purpose PCs.
16
A Car and Driver Example
To understand the major issues of real-time computing, consider a familiar
problem of human control-driving a car.
Driver is real-time controller, the car is the controlled process, and the other
cars together with the road conditions make up the operating environment.
By understanding what is required of the driver, we can understand
something of the major issues in real-time computing.
17
A Car and Driver Example
The main actuators in a car are the wheels, the engine, and the brakes. The
controls are the accelerator, the steering wheel, the brake-pedal, and other
elements (such as the switches for the lights, radio, wipers, etc.)
What are the constraints that the driver must meet? She must get from her
starting point to the destination without colliding with other vehicles or
stationary objects and keep her speed within designated limits.
The driver is on the mission.
How can we quantify the driver’s performance? We measure the outcome of
the driver’s actions, taken in the context of the operating environment.
18
A Car and Driver Example
One obvious outcome is getting to the destination.
Secondary consideration is the time it takes to get there.
However, our assessment of the time taken must be weighted by a
consideration of the road conditions. For example:
A driver may be performing very well if she maintains an average speed of 15
mph in a snowstorm (and gets to her destination without killing or maiming
herself or anyone else);
If the weather is dry and the roads are clear, however, the same speed of 15
mph represents an abject failure.
19
A Car and Driver Example
Let us consider now the tasks that the driver must perform.
Some of them are critical to the success of the mission, and some are not.
Steering and braking are critical tasks; tuning the radio is a noncritical task.
Steering and braking are real-time tasks with varying deadlines that depend
on the operating environment.
20
A Car and Driver Example
The deadlines associated with driving down a quiet street at 6 o'clock on a
Sunday morning are very different from those associated with driving along a
busy highway at the height of the rush hour.
Therefore, task deadlines in real time systems are not constant; they vary with
the operating environment.
21
Issues in Real Time Computing
A real-time computer must be much more reliable than its individual
hardware and software components.
It must be capable of working in harsh environments, and rapidly changing
computation loads.
The field of real-time computing is especially rich in research problems.
Because all problems in computer architecture, fault-tolerant computing, and
operating systems are also problems in real-time computing, with the added
complexity that real-time constraints must be met.
For example, take task scheduling. The purpose of task scheduling in a
general-purpose system is fairness, by which we mean that the computer's
resources must be shared out equitably among the users. (Round Robin)
22
Issues in Real Time Computing
Example: Consider a computer controlling an aircraft.
Among its tasks are maintaining stability and keeping the cabin
temperature within acceptable limits.
Suppose the aircraft encounters turbulence that makes it momentarily
unstable. The computer is then supposed to adjust the control surfaces to
regain stability.
If we use round-robin scheduling for this application, the computer may
switch context partway through making the control adjustments in order to
spend time making sure the cabin temperature is just right.
23
Issues in Real Time Computing
Example: Consider a computer controlling an aircraft.
The result may well be a crash and the fact that the cabin is being maintained
at optimum temperature will be scant consolation to the passengers as the
airliner falls out of the sky.
What we want is to give the stability-maintenance task a very high priority.
Which ensures that when stability is threatened, all other interfering tasks are
elbowed out of the way to allow this all-important task enough computer
cycles.
24
Issues in Real Time Computing
Real-time computer systems differ from their general-purpose counterparts
in two important ways. First, they are much more specific in their
applications,
And, second, the consequences of their failure are more drastic.
A real-time computer is typically designed for a specific application, for
example, to control a particular aircraft.
The advantage of this is that the characteristics of the application and its
operating environment are more precisely known than for general-purpose
machines.
As a result, it is possible to fine-tune real-time systems more precisely for
optimum performance.
25
Issues in Real Time Computing
Since the consequences of failure are more severe in real-time systems than
in their general-purpose counterparts, such systems need to be specified more
carefully and their performance better validated;
that is, we need specification languages and performance measures that are
capable of expressing timing requirements.
We require, among other things, means by which:
To predict the execution times of programs; to model the reliability of
software and of hardware; to assign tasks to processors and schedule them so
that deadlines are met;
And to develop mechanisms by which the system can quickly recover from
the failure of an individual component.
26
Structure of Real Time System
A schematic block diagram of real time system
27
Task Classes
Tasks can be classified in two ways: by the predictability of their arrival and
by the consequences of their not being executed on time.
Periodic and Aperiodic tasks: There are many tasks in real-time systems
that are done repetitively.
For example, one may wish to monitor the speed, altitude, and attitude of an
aircraft every 100 ms. This sensor information will be used by periodic tasks
that control the control surfaces of the aircraft (e.g., the ailerons, elevator,
rudder and engine thrusts), in order to maintain stability and other desired
characteristics. The periodicity of these tasks is known to the designer. and
so such tasks can be prescheduled.
28
Task Classes
In contrast, there are many other tasks that are aperiodic, that occur only
occasionally.
For instance, when the pilot wishes to execute a tum, a large number of
subtasks associated with that action are set off. By their very nature,
aperiodic tasks cannot be predicted and sufficient computing power must be
held in reserve to execute them in a timely fashion. Aperiodic tasks with a
bounded interarrival time are called sporadic tasks.
29
Task Classes
Critical and noncritical tasks: Real-time tasks can also be classified
according to the consequences of their not being executed on time. Critical
tasks are those whose timely execution is critical; if deadlines are missed,
catastrophes occur.
Examples include life-support systems and the stability control of aircraft.
Despite their critical nature, it is not always essential that every iteration of
the critical tasks be executed successfully and within a given deadline.
Critical tasks are often executed at a higher frequency than is absolutely
necessary. This constitutes time redundancy and ensures one successful
computation every n-ith iterations of critical periodic task i, which is
sufficient to keep the system alive.
the actual value of n, will depend on the application, the nature of the task
itself, and the number of times the task is invoked over a given interval.
30
Task Classes
Noncritical real-time (or soft real-time) tasks are, as the name implies, not
critical to the application.
However, they do deal with time-varying data and hence they are useless if
not completed within a deadline.
The goal in scheduling these tasks is thus to maximize the percentage of
jobs successfully executed within their deadlines.
31
Performance Measures For Real-Time Systems
We consider two questions:
1. Which performance measures are the most appropriate for real-time
systems? (Do these have to be different from those used for general-purpose
computers (such as throughput and reliability)?
2. How can engineers estimate the worst-case run time of a program,
given the source code and the target architecture? (In order to determine
whether a real-time computer can meet task deadlines, we must be able to
estimate how long individual programs take to run.)
32
Performance Measures For Real-Time Systems
Real-time systems are often used in critical applications, and must therefore
be carefully designed and validated before being put into operation.
The validation process includes checking design correctness using formal
and informal methods and characterizing performance and reliability.
The choice of appropriate performance measures is crucial to the correct
characterization of performance.
Performance measures are yardsticks by which performance is expressed.
33
Performance Measures For Real-Time Systems
To be useful, a performance measure must be concise.
That is, it must encapsulate in very few numbers (preferably a single
number) the performance of a system.
In other words, it must convey what is important about the performance of a
system and leave out what is not.
If, for instance, we use the mean response time of a computer for a given
task as a performance measure, we are, deliberately, laying down that it is the
average that is important, not the variance.
34
Performance Measures For Real-Time Systems
Example 1: Consider two systems A and B. A and B have system response
times with the probability density functions shown in Figure below. System A
is clearly more predictable than system B and is only slightly slower. However.
if the mean response time is our performance measure, we rank B higher than A.
Figure: Comparison of systemsA and B
35
Performance Measures For Real-Time Systems
Example 2: Consider a user typing at a terminal. He sees the echo on the
display. If the delay between typing a character and seeing it on the display is
not noticeable, the system is performing perfectly as far as the user is concerned.
For instance, the user cannot distinguish between a delay of 5 its and l0 its, so
both response times yield the same performance from his point of view. One
might posit the performance-response time characteristic shown in below
Figure.
36
Performance Measures For Real-Time Systems
Example 3: Computers used in pocket pagers have relatively simple functions,
so speed of response is not the critical performance determinant. Rather, since
pagers operate on battery power, the computer's power consumption becomes a
more important performance measure.
37
Performance Measures For Real-Time Systems
Example 4: Consider two systems, C and D. System C has a special array-
processing unit that makes it possible to multiply two matrices of up to 256 x
256 in size in four clock cycles; System D, on the other hand, has no such unit.
The cycles per instruction are the same on both machines for all other
instructions. However, System D has a clocking frequency of 10 MHz, which is
twice that of System C. Both systems cost roughly the same. We have chosen
mean response time as our measure of performance.
There is, in this case, no "better" system in an absolute sense; which system is
better depends on the application. if the application software consists of a
large number of array multiplications, system C is better, despite having a much
slower clock rate than D; if the software is largely scalar, D is better.
38
Properties of Performance Measures
A good performance measure must:
1. Represent an efficient encoding of relevant information.
2. Provide an objective basis for the ranking of candidate controllers for a
given
application.
3. Provide objective optimization criteria for design.
4. Represent verifiable facts.
39
Properties of Performance Measures
Efficient Encoding: One of the problems of dealing with complex systems is
the volume of information that is available about them and their interactions
with the environment. Determining the relevance of individual pieces of data is
impossible unless the data are viewed within a certain context or framework.
Such a context suppresses the irrelevant and highlights the relevant.
To be an efficient encoding for what is relevant about a system, the measures
must be congruent to the application. The application is as important to
performance as the computer itself—while it is the computer that is being
assessed.
40
Properties of Performance Measures
Objective basis for Ranking :
Performance measures must, by definition. quantify the goodness of computer
systems in a given application or class of applications. It follows from this that
they should permit the ranking of computers for the same application. It should
be emphasized that the ranking must always depend on the application for the
reasons given above.
41
Properties of Performance Measures
Objective optimization criteria :
The more complex a system, the more difficult it is to optimize or to fine-
tune its structure. There are numerous side effects of even simple actions. for
example, changing the number of buses in the computer.
Multiprocessors are among the most complex computers. They provide, due
to their complexity, a wealth of configurations of varying quality; this
complexity can be used to advantage or ignored with danger.
Multiprocessors that adapt or reconfigure themselves (e.g., by changing their
structure) in response to their current environment (e.g., current job mix,
expected time-to-go in a mission-oriented system, etc.) to enhance
productivity are likely to become feasible soon.
42
Traditional Performance Measures
Reliability, availability. and throughput, together with related measures,
are the focus of this section. These measures are widely used for general-
purpose systems.
Reliability is the probability that the system will not undergo failure over
any part of a prescribed interval.
Availability is the fraction of time for which the system is up.
Throughput is the average number of instructions per unit time that the
system can process.
43
Performability
Performability is a concept that combines two key aspects: performance and
reliability.
It refers to the ability of a system or entity to deliver consistent and reliable
performance over time, even under varying or challenging conditions.
Performability improves upon the traditional measures by explicitly and
formally accounting for the fact that the performance of a real-time computer
should be tied to the consequent performance of the process that it controls.
The controlled process is defined as having several accomplishment levels,
which are different levels of performance as seen by the user.
44
Performability
Every such level of performance is associated with the execution of a certain
set of control tasks.
To accomplish each control task requires the real-time computer to run a set
of control algorithms.
The performability of the real-time computer is defined as the probability
that the computer system will allow each accomplishment level to be met.
45
Performability
More formally, if there are n accomplishment levels A1, A2, . . . An, the
performability of the real- time system is given by the vector (P(A1), P(42). .
. . , P(An)),
where P(Ai) is the probability that the computer functions in such a way as to
have the controlled process reach accomplishment level Ai.
Thus, the quality of performance of the controlled process as seen by the
user is linked to the performance of the real-time system.
46
Performability
Figure below shows four views of a hierarchical view of performability.
47
Performability
Each view is driven by the requirements of the one above it and receives
input from the one below it. Each view is more detailed than the one above
it.
View 0 specifies in terms of the state variables of the controlled process just
what enables the user to distinguish one grade of performance from another.
View 1 is more detailed in specifying the controlled-process tasks.
View 2 is even more detailed in specifying which algorithms must be run to
meet each of the controlled-process tasks in View l.
Finally, View 3 considers the hardware structure, the operating system, and
the applications software attributes needed to meet the requirements of View
2.
48
Performability
Example: Consider the landing portion of the flight of a civilian aircraft. The
aircraft has an automatic landing system, which allows it to land even in zero-
visibility weather at suitably equipped airports. If the automatic-landing feature
on the aircraft is not working when the landing phase begins, and if the
destination airport has low-visibility weather, the aircraft is diverted to another
airport. It is assumed that an alternative airport with sufficient visibility to
permit a manual landing can always be found within the range of the aircraft.
We assume that whenever a manual landing is possible. the automatic-landing
feature is dispensed with and the aircraft is landed manually. If the automatic-
landing feature fails during automatic landing. there is a crash. Pilot errors are
not accounted for.
As far as the user is concerned, the accomplishment levels are:
A0: Safe arrival at the designated destination
A1: Diversion to another airport, but safe landing there
A2 : Crash 49
Performability
50