7/29/2019 Dhruva Rtos Iete 2.00pm
1/53
RR Dhruva, CVR College of Engg.
Real TimeOperating Systems
R R Dhruva
Sr. Asst. Professor E. C. E. Dept.
7/29/2019 Dhruva Rtos Iete 2.00pm
2/53
RR Dhruva, CVR College of Engg.
Contents
Introduction to RTOS
Tasks
Preemption
Scheduling
Scheduling algorithms
7/29/2019 Dhruva Rtos Iete 2.00pm
3/53
RR Dhruva, CVR College of Engg.
The Challenge
The Rising Software Intensity:
7/29/2019 Dhruva Rtos Iete 2.00pm
4/53
Mobile Terminals
> 10X
Software
Intensity
2 G 3 G
4 M bit Memory 64 M bit30MIPS Radio Channel 200MIPS
3-30MlPS Speech Codec 30MIPS-- Voice Control 50MIPS-- Video Codec 100MIPS
8-16 bits CTRL Processor 16-32bits10 M Hz Speed 50 M Hz
7/29/2019 Dhruva Rtos Iete 2.00pm
5/53
The Rising SoftwareIntensity:
Automobiles
7/29/2019 Dhruva Rtos Iete 2.00pm
6/53
How to meet it...
A more complex software architecture is
needed to handle multiple tasks,
coordination, communication, and
interrupt handling
an RTOS architecture
7/29/2019 Dhruva Rtos Iete 2.00pm
7/53
What Does Real-Time Mean?
Main difference to other computation: time time means that correctness of system depends
not only on logical results
but also on the time the results are produced real indicates: reaction to external events must
occur during their evolution.
system time ( internal time ) has to be measuredwith same time scale
as controlled environment ( external time )
7/29/2019 Dhruva Rtos Iete 2.00pm
8/53
RR Dhruva, CVR College of Engg.
Definition
A real-time Computer system is a computer
system in which the correctness of the
system behaviour depends not only on the
logical results of the computation, but also
on the physical instant at which these results
are produced.-Kopetz
7/29/2019 Dhruva Rtos Iete 2.00pm
9/53
RR Dhruva, CVR College of Engg.
What is RTOS?
A multitasking operating system intended for
real-time applications. Embedded systems, industrial robots, spacecraft,
industrial control and scientific researchequipment.
Facilitates the creation of a real-time system
Does not guarantee the final result will bereal-time; this requires correct development
of the software.
7/29/2019 Dhruva Rtos Iete 2.00pm
10/53
RR Dhruva, CVR College of Engg.
RTS: Why use a RTOS?
For many years small embedded RTS havenot used a RTOS
Profound (but not immediately apparent)
effects of using an RTOS - major impact onsoftware: Dependability productivity maintainability
Significantly simplifies development ofmedium/large RTS
7/29/2019 Dhruva Rtos Iete 2.00pm
11/53
Real-Time meanspredictable ! Main difference between real time and non-
real-time : deadline
Critical applications: result after deadline not
only late but wrong deadline to be met under all (even worst)
circumstances
real time means predictable
7/29/2019 Dhruva Rtos Iete 2.00pm
12/53
Hard RT vs. Firm vs. Soft RT
RT task is called hard if missing its deadline may cause catastrophic consequences on
the environment under control
RT task is called firm if missing its deadline makes the result useless, but missing does
not cause serious damage
RT task is called soft if meeting its deadline is desirable (e.g. for performance reasons)
but missing does not cause serious damage RTOS that is able to handle hard RT tasks is called hard
real-time operating system
7/29/2019 Dhruva Rtos Iete 2.00pm
13/53
Hard RT vs. Firm vs. Soft RT
7/29/2019 Dhruva Rtos Iete 2.00pm
14/53
RR Dhruva, CVR College of Engg.
Typical Application Areas
Hard RT systems: automotive : power-train control, air-bag control, steer by wire,
brake by wire
aircraft : engine control, aerodynamic control
Firm RT systems: Weather forecast
Decisions on stock exchange orders
Soft RT systems: communication systems (voice over IP!)
user interaction
comfort electronics (body electronics in cars)
7/29/2019 Dhruva Rtos Iete 2.00pm
15/53
Real-Time 'is NOT' Fast
7/29/2019 Dhruva Rtos Iete 2.00pm
16/53
Desirable Features of Real-Time Operating Systems Timeliness
OS has to provide kernel mechanisms for time management
handling tasks with explicit time constraints
Design for peak load
Predictability
Fault tolerance
Maintainability
7/29/2019 Dhruva Rtos Iete 2.00pm
17/53
RR Dhruva, CVR College of Engg.
Tasks
Basic SW entity handled by the OS:Process
Process = task in our context
One processor, concurrent tasks... CPU has to be assigned to tasks
with respect to predefined criterion:scheduling
policy
implementation of scheduling policy: schedulingalgorithm
allocation of selected task to CPU: dispatching
7/29/2019 Dhruva Rtos Iete 2.00pm
18/53
RR Dhruva, CVR College of Engg.
Introduction to Scheduling
We observe that processes require alternate
use of processor and I/O in a repetitive
fashion.
Each cycle consist of a CPU burst followed byan I/O burst.
7/29/2019 Dhruva Rtos Iete 2.00pm
19/53
RR Dhruva, CVR College of Engg.
Introduction to Scheduling
In multiprogramming systems, when there is more
than one runnable tasks (i.e., ready), the operating
system must decide which one to activate.
The decision is made by the part of the operatingsystem called the scheduler, using a scheduling
algorithm.
The scheduler is concerned with deciding policy, not
providing a mechanism.
7/29/2019 Dhruva Rtos Iete 2.00pm
20/53
RR Dhruva, CVR College of Engg.
Introduction to Scheduling
In general, a scheduling scheme provides two
features: An algorithm for ordering the use of system
resources (CPU) A means of predicting the worst-case behavior of
the system when the scheduling algorithm is
applied.
7/29/2019 Dhruva Rtos Iete 2.00pm
21/53
RR Dhruva, CVR College of Engg.
Types of Constraints
The following are general types of constraints:
Timing constraints meet your deadline
Precedence constraints respect pre-requisites
Resource constraints access only available resources
7/29/2019 Dhruva Rtos Iete 2.00pm
22/53
RR Dhruva, CVR College of Engg.
Task Scheduling
Three main states of tasks: active : can potentially execute
ready : is waiting for CPU
running : is executing on CPU
All ready tasks are kept in ready queue
Execution
scheduling
activation dispatching termination
7/29/2019 Dhruva Rtos Iete 2.00pm
23/53
RR Dhruva, CVR College of Engg.
Example for Schedule
Assume three tasks J1, J2, J3
At times t1, t2, t3, t4 the processor performs a
context switch
3
2
1
t1 t2 t3 t4t
J1 J2 J3idle
Scheduling obtained by executing threetasks J1, J2, and J3
(t)
7/29/2019 Dhruva Rtos Iete 2.00pm
24/53
RR Dhruva, CVR College of Engg.
Preemption
Running task may be interrupted at any point
to allow a more important task to gain the
processor immediately.
Execution
scheduling
activation dispatching termination
preemption
7/29/2019 Dhruva Rtos Iete 2.00pm
25/53
RR Dhruva, CVR College of Engg.
Importance of Preemption
Tasks performing exception handling may
need to preempt running tasks to ensure
timely reaction
Tasks may have different levels of criticalness.This can be mapped to a preemption scheme
More efficient schedules can be produced with
preemption
7/29/2019 Dhruva Rtos Iete 2.00pm
26/53
RR Dhruva, CVR College of Engg.
Scheduling Goals
All systems Fairness - giving each process a fair share of the CPU
Policy enforcement - seeing that stated policy is carried out
Balance - keeping all parts of the system busy
Interactive systems Response time - respond to requests quickly
Proportionality meet users expectations
Real-time systems Meeting deadlines - avoid losing data
Predictability avoid quality degradation in multimedia systems
7/29/2019 Dhruva Rtos Iete 2.00pm
27/53
RR Dhruva, CVR College of Engg.
Real-Time Scheduling Taxonomy
7/29/2019 Dhruva Rtos Iete 2.00pm
28/53
RR Dhruva, CVR College of Engg. 28
Basic Notations (1)
set of periodic tasks
i a generic periodic task
i j instance j of task i
i,j release time of i,j
i phase of i (= i,1, i.e. release time of first instance)
i periodof i (= interval between two consecutive activations)
7/29/2019 Dhruva Rtos Iete 2.00pm
29/53
RR Dhruva, CVR College of Engg. 29
Basic Notations (2)
Di relative deadline of i (relative to release time)
di,j absolute deadline of i,j
(di,j = i + (j - 1) Ti + Di)
si,j start time of
i,j(s
i,j r
i,j)
fi,j finishing timeof i,j (fi,j di,j )
7/29/2019 Dhruva Rtos Iete 2.00pm
30/53
RR Dhruva, CVR College of Engg.
Feasible and Schedulable Sets ofTasks Each interval [ti, ti+1) with (t) constant for t[ti, ti+1)
is called time slice
A preemptive schedule allows a running task to be
suspended at any time. tasks may be executed in disjoint intervals of time
A schedule is called feasible if all tasks can be
completed according to a set of specified constraints
A set of tasks is called schedulable if there exists atleast one algorithm that can produce a feasible
schedule
7/29/2019 Dhruva Rtos Iete 2.00pm
31/53
Example of PreemptiveSchedule
7/29/2019 Dhruva Rtos Iete 2.00pm
32/53
Ji
ai Si fi di
t
Ci
Typical parameters of a real-time task
Parameters to Characterize RT-task Ji Arrival time ai :
the time Ji becomes ready for execution
also called request time or release time, denoted by ri
Computation time Ci: time necessary for execution without interruption
7/29/2019 Dhruva Rtos Iete 2.00pm
33/53
Ji
ai Si fi di
t
Ci
Typical parameters of a real-time task
Parameters to Characterize RT-task Ji
Deadline di: time before which task has to be completed its execution
Start time Si: time at which Ji start its execution
Finishing time fi: time at which Ji finishes its execution
7/29/2019 Dhruva Rtos Iete 2.00pm
34/53
RR Dhruva, CVR College of Engg.
Real Time Scheduling
Aperiodic Scheduling Earliest Deadline First (EDF)
Modified EDF
Periodic Scheduling Rate Monotonic Priority Assignment (RM)
Earliest Deadline First (EDF)
Servers Fixed Priority
Dynamic Priority
7/29/2019 Dhruva Rtos Iete 2.00pm
35/53
Periodic and Aperiodic Tasks
Periodic task i consists of infinite sequence of identical activities, calledinstances or jobs regularly activated at a constant rate
Activation of first instance ofi is called phase i
activation time for the kth instance ofi is ai,k= i + (k-1) Ti
Ti is called period of the task
Note: activation time
7/29/2019 Dhruva Rtos Iete 2.00pm
36/53
Periodic and AperiodicTasks: Example
7/29/2019 Dhruva Rtos Iete 2.00pm
37/53
RR Dhruva, CVR College of Engg. 37
Processor Utilization Factor
Given a set of a periodic tasks the processorutilization factor U
is the fraction of processor time spent in the execution of the taks set.
Ci/Ti is the fraction of processor time spent in executing task i
U=i= 1
nC
i
Ti
7/29/2019 Dhruva Rtos Iete 2.00pm
38/53
RR Dhruva, CVR College of Engg. 38
Upper Bound of ProcessorUtilization Factor
U can be improved by
increasing tasks computation times
decreasing tasks periods
up to a maximum value below which is schedulableand above with is not schedulable
Limit depends on
task set (particular relations among tasks periods)
algorithm used to schedule the tasks
Uub(, A) = upper bound of processor utilization factor for a task set
under a given algorithm A
Least Upper Bound of
7/29/2019 Dhruva Rtos Iete 2.00pm
39/53
RR Dhruva, CVR College of Engg. 39
Least Upper Bound ofProcessor Utilization
FactorU = Uub (, A) => fully utilize the processor.
is schedulable using A but any increase of computation time in one of thetasks makes set infeasible.
For given A least upper bound Ulub (A) is the minimum of the utilization
factors over all task sets, that fully utilize the processor:
Ulub (A) = min Uub (, A)
7/29/2019 Dhruva Rtos Iete 2.00pm
40/53
RR Dhruva, CVR College of Engg. 40
Schedulability Test
Ulub allows to easily verify the schedulability of a task set:
Uub (i) Ulub (A) => i schedulable.
Uub (i) > Ulub (A) => i may be schedulable, if the periods of the
tasks are suitable related.
Uub (i) > 1 => i is not schedulable
7/29/2019 Dhruva Rtos Iete 2.00pm
41/53
RR Dhruva, CVR College of Engg. 41
Example for Least Upper Boundfor U
7/29/2019 Dhruva Rtos Iete 2.00pm
42/53
RR Dhruva, CVR College of Engg.
Rate Monotonic Scheduling
More precisely : Rate Monotonic Priority Assignment
Priorities are assigned to tasks according to their
request rates.
Tasks with higher request rates (i.e. shorter periods)get assigned higher priority.
Periods constant => RM is fixed-priority assignment
RM is intrinsically preemtive: currently executing
task is preempted by a newly released task withshorter period.
7/29/2019 Dhruva Rtos Iete 2.00pm
43/53
Rate Monotonic Scheduling:Example
7/29/2019 Dhruva Rtos Iete 2.00pm
44/53
RR Dhruva, CVR College of Engg. 44
Ulub for n Tasks
For an arbitrary set of periodic
tasks, the least upper bound of the processor utilization factor under RM :
Ulub = n (21/n - 1)
This value decreases with increasing n and converges to
Ulub = ln 2 0.69
7/29/2019 Dhruva Rtos Iete 2.00pm
45/53
RR Dhruva, CVR College of Engg. 45
Ulub for n Tasks
n Ulub
1.000
0.828
0.780
0.757
O.743
1
2
3
4
5
n Ulub
0.735
0.729
0.724
0.721
O.718
6
7
8
9
10
7/29/2019 Dhruva Rtos Iete 2.00pm
46/53
RR Dhruva, CVR College of Engg. 46
Concluding remarks on RM
RM is optimal among all fixed priority assignment
RM guarantees that an arbitrary set of periodic tasks is schedulable if
the total processor utilization U does not exceed the value of 0.69
Ulub = 0.69 is sufficient but not necessary to guarantee the feasibility of
a given task set.
7/29/2019 Dhruva Rtos Iete 2.00pm
47/53
RR Dhruva, CVR College of Engg.
Earliest Deadline First (EDF)
EDF algorithm: Dynamic scheduling rule Selects tasks according to their absolute deadlines
Tasks with earlier deadlines will be executed at
higher priorities Absolute deadline of periodic task depends on
current j-th instance:
di,j= i + (j - 1) Ti + Di
=> EDF is dynamic priority assignment Intrinsically preemptive Applicable also for aperiodic tasks
7/29/2019 Dhruva Rtos Iete 2.00pm
48/53
RR Dhruva, CVR College of Engg. 48
EDF SchedulabilityAnalysis
Schedulability of periodic task set handled by EDF can be verified
through the processor utilization factor
Ulub here is 1 , i.e. 100 % utilization achievable
Theorem
A set of periodic tasks is schedulable with EDF if and only if
i=1
n
ci
Ti
1
7/29/2019 Dhruva Rtos Iete 2.00pm
49/53
RR Dhruva, CVR College of Engg.
Example for EDF
7/29/2019 Dhruva Rtos Iete 2.00pm
50/53
RR Dhruva, CVR College of Engg.
Example: EDF vs RM
7/29/2019 Dhruva Rtos Iete 2.00pm
51/53
RR Dhruva, CVR College of Engg.
Survey of RTOS
LynxOS www.lynx.com Microkernel and plug in
modules. UNIX compatible.
pSOSystem www.windriver.com Iridium satellites.
VxWorks www.windriver.com Mars Pathfinder QNX www.qnx.com Suitable for multiprocessors on
big (shared memory) machines.
Symbian www.symbian.com Mobile phones
7/29/2019 Dhruva Rtos Iete 2.00pm
52/53
RR Dhruva, CVR College of Engg.
Suggested for FurtherReading Response Time
Priority Inversion
Priority Inheritance
Priority Ceiling
7/29/2019 Dhruva Rtos Iete 2.00pm
53/53
Questions Please...