Introduction to Real-Time Systems

Prof. Gaurav Mitra

Organization

Introduction Example Applications of Real-Time Systems Basic Model of a Real-Time System

Introduction
Real-time systems are finding increasing applications According to a recent estimate,

the number of computers deployed in real-time applications vastly out number those in ordinary applications. Many of these computers are embedded.

What is Real-time?
Real-time is a quantitative notion of time measured using a physical clock.

e.g after an event occurs (temperature exceeds 500 degrees) the corresponding action (coolant shower) must complete within 100mSec. Expressed using notions such as before, after, sometime, eventually, etc.

This is in contrast to the qualitative notion of time

What is a Real-Time System?

A system is called real-time

Whenever we need to quantitatively express time in order to describe its behaviour. Remember that the behavior of a system is described by listing the inputs to the system and the corresponding response of the systems.

Example Applications of Real-Time Systems

Industrial applications

process control systems, industrial automation systems, SCADA applications, test and measurement equipments, and robotic equipments

Example Applications of Real-Time Systems cont

Telecommunication Applications:

cellular systems, video conferencing, and cable modems

Example Applications of Real-Time Systems cont

Aerospace:

avionics, flight simulation, Airline cabin management systems, satellite tracking systems, computer on-board an aircraft

Example Applications of Real-Time Systems cont

Consumer electronics:

set-top boxes, audio equipment, Internet telephony, microwave ovens, intelligent washing machines, home security systems, air conditioning and refrigeration, toys, and cell phones

Other Applications
Medical
Robot Used in Recovery of Displaced Radioactive Material

Peripheral Equipments
Laser Printer

Transportation
Multi-Point Fuel Injection (MPFI) System

Other Applications
Computers and Internet Multimedia Applications
Video Conferencing

Defence Applications
Missile Guidance System

Basic Model of a Real-Time System

Sensors
A sensor converts some physical characteristic of its environment into electrical signals. Example sensors:

a photo-voltaic cell converts light energy into electrical energy. A temperature sensor typically operates based on the principle of a thermocouple A pressure sensor typically operates based on the piezoelectricity principle.

Actuators
An actuator takes converts electrical signals from a computer into some physical actions. The physical actions may be

motion, change of thermal, electrical, pneumatic, or physical characteristics of some objects. Motors Heaters Hydraulic and pneumatic actuators

Example actuators are:

Signal Conditioning
Analog signals generated by a photo-voltaic cell are normally in the milli volts range

need to be conditioned before they can be processed by a computer Voltage Amplification Voltage Level Shifting Frequency Range Shifting and Filtering Signal Mode Conversion

Important types of conditioning:

Characteristics of Real-Time System

Time Constraints
Every real-time task is associated with some time constraints ex. deadline

Correctness Criterion
Correctness implies not only logical correctness of results but the time at which it is produced

Embedded
Large number of real-time systems are embedded in its environment and often controls it

Safety and Task Criticality

For many real-time systems, safety and reliability are bound together which makes them safety-critical

Characteristics of Real-Time System

Concurrency
RT system needs to respond to several independent events

Distributed and Feedback Structure Custom Hardware

A RT system is often implemented on custom H/W that is specially designed and developed for the purpose

Reactive
On-going interaction between computer and environment

Stability
Work under overload conditions for important tasks

Exception Handling

Characteristics of Real-Time System

Feedback structure of real-time systems

Safety and Reliability in RT System

Independent concepts in traditional system Interrelated in safety-critical systems
Safety critical system is one for which any failure of the system would result in damage.

Safety can be ensured through increased reliability Safety-critical system should be highly reliable Example: A navigation system on-board an aircraft. Such system does not have fail-safe states

Fail-safe State
A fail-safe state of a system is one which if entered when the system fails,

no damage would result

The fail-safe state of a word processing program:

the document being processed has been saved onto the disk

fail-safe states help separate the issues of safety and reliability

even if a system is known to be unreliable, it can always be made to fail in a fail-safe state,

Safety-Critical System
A safety-critical system is one whose failure can cause severe damages A safety-critical system does not have any failsafe states:

safety can only be ensured through increased reliability

Achieving High Reliability in RealTime System

Error Avoidance Error Detection and Removing Fault Tolerance

Types of Real-Time Systems

Real-time systems are different from the traditional systems Tasks have deadlines associated with them

Hard real-time systems Soft real-time systems Firm real-time systems

Hard Real-Time Systems

If a deadline is not met,

then the system is said to have failed The task deadlines are of the order of micro or milliseconds Many hard real-time systems are safety-critical Industrial control applications On-board computers Robots

Examples

Firm Real-Time Systems

Tasks have deadlines

If a deadline is missed occasionally, the system does not fail The results produced by a task after the deadline are rejected

Utility

D Time

Firm Real-Time Systems

Examples

A video conferencing application A telemetry application Satellite-based suveillance applications

Soft Real-Time Systems

Tasks have deadlines

If a deadline is missed, the system does not fail. The performance of the system is said to have degraded The utility of a result decreases with time after the deadline

Utility

D Time

Soft Real-Time Systems

Examples of soft real-time systems:

Railway reservation system Web browsing In fact, all interactive applications

Summary
A system is said to be real-time when

quantitative expressions of time are necessary to describe the behavior of the system

A real-time task is one that is associated with some time constraints A real-time task is classified into hard, firm, or soft real-time type

depending on the consequences of a task failing to meet its timing constraints

Summary
A safety-critical system is one which does not have a fail-safe state

any failure of the system can cause severe damage. Many hard real-time systems are safety-critical in nature

The typical characteristic features of a hard realtime system include

embedded, feedback and distributed structure, and safety-criticality.

What is RTOS? 1) A real time operating system (RTOS) is an operating system that guarantees a certain capability within a specified time constraint. 2) An OS is a system program that provides an interface between application programs and the computer system (hardware) 3) The applications where dependability that a certain task will finish before a particular deadline is just as obtaining the correct results. 4) Besides meeting deadlines RTOS must also be able to respond predictably to unpredictable events and process multiple events concurrently.

5) A system application/computer/operating system operates in real time to the degree that those of its actions which have time constraints are performed with acceptable timeliness. 6) A system is real time the degree that it employs real time resource management.The resources are explicitly managed for the purpose of operating in real time. 7) The system operating in real time needs an appropriate balance of real time resource management & hardware resource capacity.

Basic definitions
A task is the basic unit of execution. Each task has three important properties: 1. release time: the point in time from which the task can be executed. 2. deadline: the point in time by which the task must complete. 3. execution time: the time the task takes to execute E.g. brakes controller

Process (task) management

Components of an RTOS

Scheduler Synchronization mechanism

Interprocess communication (IPC) Semaphores Memory management

Interrupt service mechanism I/O management , H.A.Layer Development Environments Communication subsystems (Option) Board Support Packages (BSP)

OS Basics
Four main tasks of OS
Process Management

   

Process creation Process loading Process execution control Interaction of the process with signal events  Process monitoring  CPU allocation  Process termination

OS Basics

Interprocess Communication
   

Synchronization and coordination Deadlock detection Process Protection Data Exchange Mechanisms Services for file creation, deletion, reposition and protection Handles requests and release subroutines for a variety of peripherals and read, write and reposition programs

Memory Management


Input/Output Management


4) Control Of Memory Management :an OS should provide way for task to lock its code and data into real memory so that it can guarantee predictable response to a interrupt. 5) Proper scheduling : OS must provide facility to schedule properly time constrained tasks. 6) Fine granularity Timer Services : Millisecond resolution is bare minimum . Microseconds resolution is required in some cases. 7) Rich set of Inter Task Communication Mechanism : Message queues,shared memory , Synchronisation Semaphores,event flags

Fundamental RTOS capabilities : a) RTOS vendor must provide worst case execution times for all times for all OS routines. b) RTOS must include scheduling and resource sharing algorithms that enables deterministic behavior. c) Effective RTOS must also be able to handle preemptive scheduling.It enables high priority tasks to execute without being blocked by lower priority tasks.

RTOS Concepts
1) Scheduling and Dispatching : a) Scheduling is the creation of a schedule ie. A ordered list specifying how contending accesses to one or more sequentially reusable resources will be granted. b) A schedule is some criteria such as timeliness. c) Dispatching is granting access to the currently most eligible contending entity. d) Eligibility is the entities position in a schedule or in the absence of schedule , other eligibility parameters such as priority and deadline.

e) More commonly RTOS/OS they can be used for dispatching from a heap of unscheduled contending entities (highest prority or earliest deadline) this is called dispatching rule. 2) Schedulable and Non-Schedulable Entities : A computing system has a mixture has schedulable & Non-schedulable entities. a) Schedulable Entities : Threads, tasks, processes in application and system s/w are scheduled by scheduler. b) Non-Schedulable Entities: Interrupt handlers,OS commands,packet level N/W communication services ,OS scheduler. They execute continuously , periodically or in response to events,their timeliness is the responsibility of the system design and implementation not of the scheduler.

3) Timeliness Specification : There are two levels a) For Individual Entities : Schedulable ones such as threads ,non schedulable ones such as interrupt routines. b) For sets of Entities : For sets of entities have collective timeliness specification. 4) Schedulable Entity Timeliness Specifications a) First level of timeliness specification for a schedulable entity (thread) is that it may have one or more completion time constraints(deadlines). b) Second level of timeliness specification is that currently runnable set of such threads is scheduled such that to optimize collective timeliness.ie.to meet all deadlines.

5) Completion Time Constraint : It is predicate which applies to some portion(frequently all) of a threads locus of execution, that portion is called the time constraints scope.It is the part of the logic of the application. 6) Deadline : It is the completion time constraint which specifies the timeliness of the threads transit through the deadline scope whether the threads execution point reaches the end of the scope before the deadline time has occurred ie.whether the deadline is met.

7) Hard Deadline: It is completion time constraint ie.the threads execution point reaches the end of the deadline scope before the deadline time occurs,then time constrained portion of threads execution is timely otherwise that portion is not timely. 8) Soft Deadline: It is completion time constraint ie.the threads execution point reaches the end of the deadline scope before the deadline time occurs,then time constrained portion of threads execution is more timely otherwise that portion is less timely. 9) Soft Time Constraint : a) It is any relationship between the time when the threads execution point reaches the end of the that time constraints scope and the utility to the system of when it does so. b) A thread for which there is no relationship between the timing of its execution and its utility to the system is a non realtime system.

10) Non-schedulable Entity Timeliness Specifications : a) The completion time constraints of non-schedulable entities are Hard & soft upper bounds on their execution latencies(duration) which correspond to hard and soft deadlines of schedulable entities. 11) Upper Bound: An upper bound is completion time constraint.It specifies the timeliness of Non-schedulable entitys execution point reaches the end of the scope before the upper bound time has occurred in which case the upper bound is satisfied.

Process Scheduling Types



Types of Scheduling Policies

Deadline driven ideal but not available Cooperative relies on current process to give up the CPU Pre-emptive priority scheduling higher priority tasks may interrupt lower priority tasks
 Static

priorities are set before the system begins execution  Dynamic priorities can be redefined at run time

Process Scheduling Types



Many priorities levels in a RTOS is better to have for complex systems with many threads  At least 128 levels  A different priority level can be set for each task or thread

Round Robin give each task an equal share of the processor

 Implemented

when all tasks or threads have the same priority level  May be implemented within a priority range

Commercial Real-time Operating Systems An Introduction

Outline
Introduction LynxOS QNX/Neutrino VRTX VxWorks Spring Kernel

Commercial RTOS OS gives Commercial RTOSes different from traditional

more predictability Used in the following areas such as:

Embedded Systems or Industrial Control Systems Parallel and Distributed Systems

E.g. LynxOS, VxWorks, pSoS, QNX , bluecat Traditionally these systems can be classified into a Uniprocessor, Multiprocessor or Distributed Real-Time OS

Microkernel design Lynx

OS

Means the kernel footprint is small Only 28 KB in size

The small kernel provides essential services in scheduling, interrupt dispatching and synchronization The other services are provided by kernel lightweight service modules, called Kernel Plug-Ins (KPIs) New KPIs can be added to the microkernel and can be configured to support I/O, file systems, TCP/IP, streams and sockets Can function as a multipurpose UNIX OS

Lynx OS (contd..)
Here KPIs are multi-threaded, which means each KPI can create as many threads as it want There is no context switch when sending a message to a KPI

For example, when a RFS (Request for Service) message is sent to a File System KPI, this does not request a context switch Hence run-time overhead is minimum Further, inter KPI communication incurs minimal overhead with it consuming only very few instructions

Lynx OS is a self hosted system wherein development can be done in the same system

In such a system, there is a need for protecting the OS from such huge memory consuming applications (compilers, debuggers) LynxOS offers memory protection through hardware MMUs Applications make I/O requests to I/O system through system calls Kernel directs I/O request to the device driver Each device driver has an interrupt handler and kernel thread

Lynx OS (contd..)

Lynx OS (contd..)
The interrupt handler carries the first step of interrupt handling If it does not complete the processing, it sets an asynchronous trap to the kernel Later, when kernel can respond to the software interrupt, it schedules an instance of the kernel thread to complete the interrupt processing

QNX/ Neutrino
POSIX-compliant Unix-like real-time operating system. Microkernel design kernel provides essential threads and real-time services use of a microkernel allows users (developers) to turn off any functionality they do not require without having to change the OS itself. The system is quite small, fitting in a minimal fashion on a single floppy, and is considered to be both very fast and fairly "complete." The footprint of microkernel is 12kb.

QNX/ Neutrino (contd..)

Every driver, application, protocol stack, and file system runs outside the kernel, in the safety of memory-protected user space. As a result, virtually any component can fail - and be automatically restarted -without affecting other components or the kernel. Maximize application portability with extensive support for the POSIX standard, which lets you quickly migrate Linux, Unix, and other open source programs

QNX is a message passing operating system

QNX/ Neutrino (contd..)

Messages are basic means of interprocess communication among all threads Follows a message based priority tracking feature

VRTX ( Virtual Real-Time Executive )

VRTX has two multitasking kernels

VRTXsa (scalable architecture )

designed for performance Provides priority inheritance, POSIX compliant libraries Supports multiprocessing System calls fully preemptable and deterministic

VRTXmc (micro-controller)
Designed for low memory consumption Used for cellular phones and hand-held devices

Rather than providing optional components provides hooks for extensibility application can add its own system calls

VxWorks
Created by Wind River. Current Version: VxWorks 6.0 VxWorks is the most established and most widely deployed device software operating system. Currently there are more than 300 million devices that are VxWorks enabled. The core attributes of VxWorks, include high performance, reliability, determinism, low latency and scalability.

Enhanced error management

VxWorks (contd..)

Backward compatibility to previous verison features for exception handling and and template support Extensive POSIX 1003.1, .1b, .1c compatibility (including pthreads ) Scheduling

Uses preemptive priority with round robin scheduling to accommodate for both Real time processes Non-real time processes

VxWorks (contd..)
Memory Protection

MMU based memory protection.

Reduced Context Switch time

Saves only those register windows that are actually in use (on a Sparc) When a tasks context is restored, only the relevant register window is restored To increase response time, it saves the register windows in a register cache useful for recurring tasks

VxWorks (contd..)
Distinguishing features

efficient POSIX-compliant memory management multiprocessor facilities shell for user interface symbolic and source level debugging capabilities performance monitoring

Mars Exploration Rovers Spirit and Opportunity and the Mars Reconnaissance Orbiter use the VxWorks operating system

Open Source Real-time Operating Systems An Introduction

Outline
Introduction eCos Free RTOS RTLinux RTAI MicroC/OSII

eCos ( Embedded Configurable OS )

open source, royalty-free

 Highly Configurable nature  Small footprint  Application specific  Multiple implementation of kernel functions including
scheduling, allocating memory and interrupt handling

 Easily Portable  Hardware Abstraction Language (HAL)

Native API, POSIX API, ITRON API, C API

eCos ( Contd )
eCos is targeted at high-volume applications in consumer electronics, telecommunications, automotive, and other deeply embedded applications. Ecos has kernel mode

No user mode

Implemented using C++ GNU debugger (GDB) support

eCos ( Contd )
Features

Choice of scheduling algorithms Choice of memory-allocation strategies Timers and counters Support for interrupts and DSRs Exception handling ISO C library , Math library Rich set of synchronization primitives Host debug and communications support

eCos ( Contd )

http://www.cotsjournalonline.com/home/article.php?id=100164

FreeRTOS
Simple , Portable , Royalty free , Concise Mini Realtime Kernel Cross development from a standard Windows host Choice of RTOS scheduling policy

Pre-emptive: Always runs the highest available task. Tasks of identical priority share CPU time (fully pre-emptive with round robin time slicing). Cooperative: Context switches only occur if a task blocks, or explicitly calls taskYIELD(). Messages Queue

Semaphores [via macros]

FreeRTOS ( Contd )

Majority of source code common to all supported development tools RTOS kernel uses multiple priority lists FreeRTOS supports 8, 16 and 32bit microcontrollers including ARM7, AVR, 8051, MSP430 and x86. It offers a smaller and easier real-time processing alternative for applications where eCos and embedded Linux (or Real Time Linux) won't fit, are not appropriate, or are not available.

FreeRTOS ( Contd )
Smaller than RTLinux or eCos but want to stick with software that protects your freedoms? Ports are available for the Philips ARM7, TI MSP430, Renesas (Hitachi) H8/S, Atmel AVR, Motorola/Freescale HCS12, Motorola/Freescale ColdFire, and others.

Available as a patch to the regular Linux kernel Provides an RT API for developers RTLinux is a hybrid OS that runs a Linux kernel as an idle thread (lowest priority) of the real-time kernel. Predictable delays.

RTLinux

By its small size and limited operations.

Finer timer resolution. RT kernel and RT applications are kept as simple as possible and non-time critical applications (GUIs, file systems) are handled by the standard Linux.

RTLinux handlers never ) ( Contd delayed by nonReal time threads and interrupt
realtime operations Preemptible kernel.

Its routines are very small and fast, this does not cause big delays. Interrupts from Linux are disabled. FIFO.
Used to pass information between real-time process and ordinary Linux process. Designed to never block the real-time task.

 RT-Linux has many kinds of Schedulers.

The earliest deadline first scheduler. Rate-monotonic scheduler.

Linux Kernel

RTLinux Kernel

RTAI (Real Time Application Interface)

Hard real-time extension to the Linux kernel A patch to the Linux kernel which introduces a hardware abstraction layer A broad variety of services which make realtime programmers' lifes easier RTAI provides deterministic response to interrupts, POSIX compliant and native RTAI realtime tasks. Linux application is able to execute without any modification RTAI considers Linux as a background task running when no real time activity occurs.

RTAI is very much module oriented real time scheduler module

RTAI ( Contd )

Task functions Timing functions Semaphore functions Mailbox functions Intertask communication functions

Fifo services Shared memory Posix pthread and pqueue(msg queue)

Comparison of Linux implementations RTLinux and RTAI RTAI provides better real-time support than RTLinux

soft real-time in user space along with hard real-time in kernel space excellent performance in terms of low jitter and low latency better C++ support and more complete feature set availability of LXRT which allows user space applications in kernel space

RTAI has the better open source approach with frequent feedback from developers

MicroC/OSII Also known as C/OS II or uC/OSII

MicroC/OS has been designed as a small footprint real time preemptive OS that was designed for embedded use on 8 bit platforms upwards highly portable, ROMable, very scalable, preemptive real-time, multitasking kernel has ports for most popular processors and boards in the market suitable for use in safety critical embedded systems such as aviation, medical systems and nuclear installations Over 100 microprocessors are supported approved for use in a DO-178B aerospace system and is (apparently) MISRA-C compliant

C/OS II features

MicroC/OSII ( Contd )

reentrant functions and is portable to different processors

kernel is preemptive real time, managing up to 64 tasks, with up to 56 tasks for each application Each task has a unique priority and its own stack Round robin scheduling is not supported operating system uses semaphores to restrict access to resources shared by multiple elements of the system Memory management is performed using fixed size partitions.

MicroC/OSII ( Contd )
C/OS II is a multitasking operating system Each task is an infinite loop and can be in any one of the following 5 states

Dormant, Ready, Running, Waiting, ISR

services such as mailboxes, queues, and semaphores

Other RTOS
* Opensource
* Nut/OS [1] * TRON Project

* Commercial
* BeOS * ChorusOS * MicroC/OS-II * OS-9 * OSEKtime * pSOS * nOS * RMX * RSX-11 * RT-11 * RTOS-UH * VRTX

Comparison of RTOS
VXWorks
Scheduler Synchronizatio n mechanism POSIX support Scalable Custom hw support Kernel size Multiprocessor support

pSOS
Preemptive

eCos
Preemptive

Preemptive
No condition variable

Y Y Y
BSP

Y Linux Y
HAL, I/O package -

Y Y
BSP

16KB

VxMP/ VxFusion PSOS+m kernel (accessories)

Y/only basic
support

(SMP)

Thank You