Real Time System

A system is said to be Real Time if it is

required to complete it’s work & deliver
it’s services on time.
Example – Flight Control System
 All tasks in that system must execute on
time.
Non Example – PC system
Hard and Soft Real Time Systems
Hard Real Time System
 Failure to meet deadlines is fatal
 example : Flight Control System
Soft Real Time System
 Late completion of jobs is undesirable but not
fatal.
 System performance degrades as more & more
jobs miss deadlines
 Online Databases
Qualitative Definition.
Hard and Soft Real Time Systems
(Operational Definition)

Hard Real Time System

 Validation by provably correct procedures or
extensive simulation that the system always meets
the timings constraints
Soft Real Time System
 Demonstration of jobs meeting some statistical
constraints suffices.
Example – Multimedia System
 25 frames per second on an average
Misconception of RTOS
RTOS must be fast
The responsiveness of an RTOS depends
on its deterministic behavior and not on
its processing speed.
The ability of RTOS to response to events
within a timeline does not imply it is
fast.
Features of RTOS’s

Multitasking and Preemptibility

Task Priority
Reliable and Sufficient Inter Task
Communication Mechanism
Priority Scheduling
Interrupt Handling
Resource Allocation
General RTOS Architecture
Kernel
An operating system generally consists
of two parts: kernel space (kernel
mode) and user space (user mode).
Kernel is
The smallest and central component of
an operating system
Broad categories of Kernel
Monolithic kernel
Microkernel
Exokernel
Monolithic kernel
Eg : Linux
Windows
Microkernel
AmigaOS and
QNX
Exokernel
It runs only services protecting the
resources (i.e. tracking the ownership,
guarding the usage, revoking
access to resources, etc) by providing low-level interface for library operating
systems and leaving the
management to the application.
An RTOS generally avoids implementing the
kernel as a large monolithic program. The
kernel is developed instead as a micro-kernel
with added configurable functionalities.
This implementation gives resulting benefit in
increase system configurability, as each
embedded application requires a specific set
of system services with respect to its
characteristics.
The kernel of an RTOS provides an
abstraction layer between the
application software and hardware.
This abstraction layer comprises of six
main types of common services
provided by the kernel to the
application software
Task Management
Task management allows programmers
to design their software as a number of
separate “chunks” of codes with each
handling a distinct goal and deadline.
This service encompasses mechanism
such as scheduler and dispatcher that
creates and maintain task objects
A task object is defined by the following
set of components:
• Task Control block (Task data structures
residing in RAM and only accessible by RTOS)
• Task Stack (Data defined in program residing
in RAM and accessible by stack pointer)
• Task Routine (Program code residing in ROM)
In real-time context, task is the basic
unit of execution and is governed by
three time-critical properties; release
time, deadline and execution time.
Task Categories
 Periodic (time-triggered)
 Aperiodic (event-triggered)
 Static
 Dynamic
Multi-Tasking System
 Preemptive: higher-priority process taking
control of the processor from a lower-priority
 Non-Preemptive : Each task can control the
CPU for as long as it needs it.
Why we need scheduling ?!
Each computation (task) we want to execute needs resources
resources: processor, memory segments, communication, I/O
devices etc.)
The computation must be executed in particular order (relative
to each other and/or relative to time)
The possible ordering is either completely or statistically a priori
known (described)
scheduling: assignment of processor to computations;
allocation: assignment of other resources to computations;
Real-time Scheduling
Taxonomy
Job (Jij): Unit of work, scheduled and executed by system.
Jobs repeated at regular or semi-regular intervals modeled as
periodic
Task (Ti): Set of related jobs.
Jobs scheduled and allocated resources 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: All jobs meet their deadline
Scheduling Periodic Tasks
 In hard real-time systems, set of tasks are known apriori
 Task Ti is a series of periodic Jobs Jij. Each task has the following parameters
 ti - period, minimum interrelease interval between jobs in Task T i.
 ci - maximum execution time for jobs in task Ti.
 rij - release time of the jth Job in Task i (Jij in Ti).
 i - phase of Task Ti, equal to ri1.
 ui - utilization of Task Ti = ci / ti
 In addition the following parameters apply to a set of tasks
 H - Hyperperiod = Least Common Multiple of pi for all i:
 U - Total utilization = Sum over all ui.
 Schedulable utilization of an algorithm Us
 If U < Us the set of tasks can be guaranteed to be scheduled
 Real-Time Scheduling Algorithms

Fixed Priority Algorithms Dynamic Priority Algorithms Hybrid algorithms

Rate Deadline Earliest Maximum

Least
Monotonic Monotonic Deadline Urgency
Laxity First
scheduling scheduling First First
Scheduling Algorithm
Static vs. Dynamic

Static Scheduling:
 All scheduling decisions at compile time.
Temporal task structure fixed.
Precedence and mutual exclusion satisfied by
the schedule (implicit synchronization).
One solution is sufficient.
Any solution is a sufficient schedulability test.
Benefits
 Simplicity
Scheduling Algorithm
Static vs. Dynamic

Dynamic Scheduling:
 All scheduling decisions at run time.
 Based upon set of ready tasks.
 Mutual exclusion and synchronization enforced by
explicit synchronization constructs.
 Benefits
 Flexibility.
 Only actually used resources are claimed.
 Disadvantages
 Guarantees difficult to support
 Computational resources required for scheduling
Scheduling Algorithm
Preemptive vs. Nonpreemptive

Preemptive Scheduling:
 Event driven.
 Each event causes interruption of running tasks.
 Choice of running tasks reconsidered after each
interruption.
 Benefits:
 Can minimize response time to events.
 Disadvantages:
 Requires considerable computational resources
for scheduling
Rate Monotonic scheduling
Simplest type of real time scheduling
- Tasks are periodic, with hard deadlines
- Tasks are completely independent and do not
communicate with each other
- Tasks are scheduled according to priority and
task priorities are fixed
- Computation time is known and constant
Rate Monotonic scheduling
Priority assignment based on rates of tasks
Higher rate task assigned higher priority
Schedulable utilization = 0.693

Where Ci is the computation time, and Ti is the release period

If U < 0.693, schedulability is guaranteed

Tasks may be schedulable even if U > 0.693
RM example
Process Execution Time Period

P1 1 8
P2 2 5
P3 2 10
The utilization will be:

The theoretical limit for processes, under which we

can conclude that the system is schedulable is

Since the system is

schedulable!
Deadline Monotonic
scheduling
Priority assignment based on relative
deadlines of tasks
Shorter the relative deadline, higher the
priority
Earliest Deadline First (EDF)
Dynamic Priority Scheduling
Priorities are assigned according to deadlines:
 Earlier deadline, higher priority
 Later deadline, lower priority
The first and the most effectively widely used
dynamic priority-driven scheduling algorithm.
Effective for both preemptive and non-preemptive
scheduling.
Two Periodic Tasks
Execution profile of two periodic tasks
 Process A

 Arrives 0 20 40 …
 Execution Time 10 10 10 …
 End by 20 40 60 …
 Process B

 Arrives 0 50 100 …
 Execution Time 25 25 25 …
 End by 50 100 150 …
Question: Is there enough time for the execution of two periodic
tasks?
Exercise :Five Periodic Tasks
Execution profile of five periodic tasks
Least Laxity First
It assigns priority based on the slack
time of a process.
Slack time is the amount of
time left after a job if the job was
started now.
Its most common use is in embedded
systems, especially those with multiple
processors
Scheduling Algorithms in RTOS

Clock Driven Scheduling

Weighted Round Robin Scheduling

Priority Scheduling
(Greedy / List / Event Driven)
Scheduling Algorithms in RTOS (contd)

Clock Driven
 All parameters about jobs (release time/
execution time/deadline) known in
advance.
 Schedule can be computed offline or at
some regular time instances.
 Minimal runtime overhead.
 Not suitable for many applications.
Scheduling Algorithms in RTOS (contd)

Weighted Round Robin

 Jobs scheduled in FIFO manner
 Time quantum given to jobs is proportional to it’s
weight
 Example use : High speed switching network
 QOS guarantee.
 Not suitable for precedence constrained jobs.
 Job A can run only after Job B. No point in giving time
quantum to Job B before Job A.
Scheduling Algorithms in RTOS (contd)

Priority Scheduling
(Greedy/List/Event Driven)
 Processor never left idle when there are
ready tasks
 Processor allocated to processes according
to priorities
 Priorities
 static - at design time
 Dynamic - at runtime
Priority Scheduling

Earliest Deadline First (EDF)

 Process with earliest deadline given highest
priority
Least Slack Time First (LSF)
 slack = relative deadline – execution left
Rate Monotonic Scheduling (RMS)
 For periodic tasks
 Tasks priority inversely proportional to it’s period
Resource Allocation in RTOS
Resource Allocation
 The issues with scheduling applicable here.
 Resources can be allocated in
 Weighted Round Robin
 Priority Based

Some resources are non preemptible

 Example : semaphores
Priority Inversion if priority scheduling is used
Solutions to Priority Inversion
Non Blocking Critical Section
 Higher priority Thread may get blocked by
unrelated low priority thread
Priority Ceiling
 Each resource has an assigned priority
 Priority of thread is the highest of all priorities of
the resources it’s holding
Priority Inheritance
 The thread holding a resource inherits the priority
of the thread blocked on that resource
Other RTOS issues
Interrupt Latency should be very small
 Kernel has to respond to real time events
 Interrupts should be disabled for minimum
possible time
For embedded applications Kernel Size should
be small
 Should fit in ROM
Sophisticated features can be removed
 No Virtual Memory
 No Protection
Linux for Real Time Applications
Scheduling
 Priority Driven Approach
 Optimize average case response time
 Interactive Processes Given Highest Priority
 Aim to reduce response times of processes
 Real Time Processes
 Processes with high priority
 No notion of deadlines
Resource Allocation
 No support for handling priority inversion
Interrupt Handling in Linux
Interrupts are disabled in ISR/critical
sections of the kernel
No worst case bound on interrupt
latency avaliable
 eg: Disk Drivers may disable interrupt for
few hundred milliseconds
Not suitable for Real Time Applications
 Interrupts may be missed
Why Linux
Coexistence of Real Time Applications
with non Real Time Ones
 Example http server
Device Driver Base
Stability
RTLinux
Real Time Kernel at the lowest level
Linux Kernel is a low priority thread
 Executed only when no real time tasks
Interrupts trapped by the Real Time
Kernel and passed onto Linux Kernel
 Software emulation to hardware interrupts
 Interrupts are queued by RTLinux
 Software emulation to disable_interrupt()
RTLinux (contd)
Real Time Tasks
 Statically allocate memory
 No address space protection
Non Real Time Tasks are developed in
Linux
Communication
 Queues
 Shared memory
RTLinux Framework
rtker – Our RTOS
Motivation
 Our own OS
 Full grasp over source code – Easily modifiable, portable
Features
 Modular Design
 Isolation of Architecture/CPU dependent and independent
code – Easy to Port
 Pluggable Scheduler
 Two level Interrupt Handling
 Small footprint
 Oskit’s Device Driver Framework
Pluggable Scheduler
Scheduler - part of the Application
Kernel interacts with the scheduler
through an API
Application developer needs to
implement the scheduler API
 Can optimize on Data Structures &
Algorithms for implementing the scheduler
rtker – Block Diagram
Two Level Interrupt Handling
Two level Interrupt Handling
 Top Half Interrupt Handler
 Called Immediately – Kernel never disables interrupts
 Cannot invoke thread library functions - Race Conditions
 Bottom Half Interrupt Handler
 Invoked when kernel not in Critical Section
 Can invoke thread library functions

Very Low Response time (as compared to

Linux)
Other Features
Footprint
 Small footprint (~50kb)
Oskit’s Device Driver Framework
 Allows direct porting of existing drivers
from Linux.
 Example – Ethernet Driver of Linux
Other RTOS’s

LynxOS
 Microkernel Architecture
 Kernel provides scheduling/interrupt handling
 Additional features through Kernel Plug Ins(KPIs)
 TCP/IP stack , Filesystem
 KPI’s are multithreaded
 Memory Protection/ Demand Paging Optional
 Development and Deployment on the same host
 OS support for compilers/debuggers
Other RTOS’s (contd)

VxWorks
 Monolithic Architecture
 Real Time Posix compliant
 Cross development System
pSOS
 Object Oriented OS
Peripheral devices and protocols
• Interfacing
Serial/parallel ports, USB, I2C, PCMCIA, IDE
• Communication
Serial, Ethernet, Low bandwidth radio, IrDA,
802.11b based devices
• User Interface
LCD, Keyboard, Touch sensors, Sound, Digital
pads, Webcams
• Sensors
A variety of sensors using fire, temperature,
pressure, water level, seismic, sound, vision
TASK WITH RTOS – WORKING EXAMPLE TO DO

Say you have a robot that is exploring an area.

The computer controlling the robot has a number of tasks to do:
getting sensor input, driving the wheels, and running a navigational
program that may have a fairly high computational load.
One key issue in such an environment is to ensure that all the tasks are
done in a timely way.
On a microcontroller you might use a timer to generate interrupts that
regularly address the motors and sensors while having the navigational
task running as the main program. But that fairly simple model breaks
down in a number of situations.

For example, what if the navigational program is actually a collection of

programs each of which need to run at different intervals for different
durations (perhaps image processing, routing, and mapping programs)? It
would be quite possible to write code to handle this, but having libraries
(or an OS) which provides APIs for scheduling would be very helpful. A
real-time operating system (RTOS) provides tools that allow us to
schedule these tasks. - CAN DO BY FreeRTOS , VX Works.
Worst-Case Execution Time
Analysis
Characteristics of Real-Time
Systems
•Concurrent control of separate system
components
•Constrained resources
•Guaranteed response times
•Often have to be extremely dependable
•Interaction with special purpose
hardware
What is the “Execution Time”
of a program?
 62

The Timing Problem

Probability

Unsafe: Safe Worst Case

Best Case Execution Time Execution Time
Execution Time Measurement Estimate
Exact Worst Case
Execution Time

Execution Time
 Hard Real-Time Systems

 Schedulability analysis must be performed

 Hence, it is essential that an upper bound on the execution times of all tasks is
known
 Commonly called the Worst-Case Execution Time (WCET)

 Controllers in planes, cars, plants, … are expected to finish their tasks within
reliable time bounds.
 Why may we care about the WCET?
Worst case executime time

• perform schedulability anaylsis

• ensure meeting deadlines
• assess resource needs for real-time systems
• WCET accuracy may be safety-critical!
And why may we care about the
BCET? Best Case execution time

• benchmark hardware
• assess code quality
• assess resource needs for non/soft real-time
systems
• ensure meeting livelines (new starting points)
Measuring WCET/BCET
Execution time may depend on program inputs
• In this case, quality of measurements depends on judicious
choice of
inputs
• Execution time may depend on execution context
(cache content, state of pipeline, ...)
• Typically need to add safety margin to best/worst result
measured
• Extensive testing/measurement still common
practice
Analysing WCET/BCET
Instead of measuring execution times, compute
them
• Advantages
• Can ensure safety of result
• Saves testing effort
• Disadvantages
• Try to be as tight as possible—may not always
succeed
• Typically requires extensive analysis effort
• Accuracy depends on
• Complexity of hardware
• Program structure
• Quality of hardware model
 Flow Analysis
Analyse dynamic behaviour of program
• Number of loop iterations, Recursion depth, Input
dependences, Infeasible paths, Function instances, ...

• Get information from

Static Analysis
Manual Annotation

• Analysis level
Object code
•Source code (may need non-trivial mapping to object code)
Flow analysis
 Cont….
The set of structurally possible flows for a program, i.e. those given by the
structure of the program, is usually infinite, since e.g. loops can be taken an
arbitrary number of times

• The executions are made finite by bounding all loops with some upper limit
on the number of executions (basic finiteness)

• Adding even more information, e. g. about the input data, allows the set of
executions to be narrowed down further, to a set of statically allowed paths.
This is the “optimal” outcome of the flow analysis.
Loop bounds: Easy to find in this example; in general, very
difficult to
determine
• Infeasible paths: Can we exclude a path, based on data
analysis?
A-B-C-E-F-G is infeasible—since if x>5, it is not possible that x *
2 < 0.
Well, really? What about integer overflows? Must be sure that
these do not
happen in the example...
Mapping !!!
Flow Info Graph
Mapping Problem exists!!!
Embedded compilers often do a lot of code optimizations

- Important to fit code and data into limited memory resources

- Optimizations may significantly change code (and data) layout
- After optimizations flow info may no longer be valid

Solutions:
- Use special compiler also mapping flow info (not common)
- Use compiler debug info for mapping (only works with little/no
optimizations)
- Perform flow analysis on binaries (most common)
Provides bounds on the number of times different program parts may be
executed

- Valid for all possible executions

- Examples of provided info:

" Bounds of loop iterations
" Bounds on recursion depth
" Infeasible paths

- Info provided by:

" Static program analysis
" Manual annotations
Cont.
Low-Level Analysis
 Low-Level Analysis
Global Low-Level Analysis
• Considers execution time effects of machine features that reach across
entire program

• Instruction/data caches, branch predictors, translation lookaside buffers

(TLBs)

Local Low-Level Analysis

• Considers machine features that affect single instruction & its neighbours
• Scalar/superscalar pipelines
Local Low-Level Analysis -
Pipelining
Local Low-Level Analysis -
Pipelining