Transcript Real-Time Operating Systems

Real-Time Operating Systems
Raquel S. Whittlesey-Harris
Contents
What is a real-time OS?
 OS Structures
 OS Basics
 RTOS Basics
 Basic Facilities
 Interrupts
 Memory
 Development Methodologies
 Summary
 References
7/16/2015

2
What is a Real-time OS?

A RTOS (Real-Time Operating System)


Is an Operating Systems with the necessary
features to support a Real-Time System
What is a Real-Time System?


7/16/2015
A system where correctness depends not only on the
correctness of the logical result of the computation, but
also on the result delivery time
A system that responds in a timely, predictable way to
unpredictable external stimuli arrivals
3
Real-Time OS

What a Real-Time System is NOT

A Transactional system


Average # of transactions per second
A Good RTOS is one that has a bounded
(predictable) behavior under all system
load scenarios

Just a building Block

7/16/2015
Does not guarantee system correctness
4
Type of Real-Time Systems

Hard Real-Time


Missing a deadline has catastrophic results
for the system
Firm Real-Time

7/16/2015
Missing a deadline causes an unacceptable
quality reduction
5
Types of Real-Time Systems

Soft Real-Time



Reduction in system quality is acceptable
Deadlines may be missed and can be
recovered from
Non Real-Time

7/16/2015
No deadlines have to be met
6
OS Structures

Monolithic OS

OS is composed of one piece of code
divided into different modules

Problem: Difficult to debug



7/16/2015
Changes may impact other modules substantially
Corrections may cause other bugs to show up
“Spaghetti Software” - many interconnections
between modules
7
OS Structures
7/16/2015
8
OS Structures

Layered OS

Better approach than the Monolithic



Example: OSI Layer
Problem: OS technology not as orthogonal
with its layers

7/16/2015
However still chaotic
You can skip layers in OS model
9
OS Structures
7/16/2015
10
OS Structures
7/16/2015
11
OS Structures

Client-Server OS

Newer Model



7/16/2015
Limit Basics of OS to a minimum (scheduler
and synchronization primitive)
Other functionality is implemented as system
threads or tasks
Applications are clients requesting services via
system calls to these server tasks
12
OS Structures

Benefits




Easier to Debug and scale
Distribution over multiple processors is simpler
Possible to dynamically load and Unload
modules
Problems

Overhead is high due to memory protection

7/16/2015
Server processes must be protected
 Increased time to switch from application’s to
server’s memory space
13
OS Structures
7/16/2015
14
OS Basics

An OS is a system program that
provides an interface between
application programs and the computer
system (hardware)

Primary Functions


7/16/2015
Provide a system that is convenient to use
Organize efficient and correct us of system
resources
15
OS Basics

Four main tasks of OS

Process Management







7/16/2015
Process creation
Process loading
Process execution control
Interaction of the process with signal events
Process monitoring
CPU allocation
Process termination
16
OS Basics

Interprocess Communication





Memory Management


Services for file creation, deletion, reposition and
protection
Input/Output Management

7/16/2015
Synchronization and coordination
Deadlock and Livelock detection
Process Protection
Data Exchange Mechanisms
Handles requests and release subroutines for a
variety of peripherals and read, write and reposition
programs
17
RTOS Basics
7/16/2015
18
RTOS Basics

Central Purpose of a RTOS

Scheduling of the CPU


Applications are structured as a set of
processes
Processes consist of


7/16/2015
Code
State
 Register values
 Memory values
19
RTOS Basics

At least 3 states are needed to allow the CPU
to schedule



7/16/2015
Ready – waiting to run (in ready list)
Running – process (thread or task) is utilizing the
processor to execute instructions
Blocked – waiting for resources (I/O, memory, critical
section, etc.)
20
RTOS Basics
7/16/2015
21
RTOS Basics

Threads are lightweight processes




Inherits only part of process
Belongs to the same environment as other threads
making up the process
May be stopped, started and resumed
Tasks are a set of processes with data
dependencies between them
7/16/2015
22
RTOS Basics
Max number of threads, tasks or processes


7/16/2015
Definition space part of system
 A system parameter
Definition space part of task
 Available memory
23
Basic Facilities

Multitasking is required to develop a
good Real-time application


7/16/2015
“Pseudo parallelism” - to handle multiple
external events occurring simultaneously
Rate Monotonic Scheduling (RMS) - is
utilized to compute in advance the
processor power required to handle the
simultaneous events
24
Basic Facilities

Algorithms (scheduling mechanism) are
needed to decide which task or thread will
run at a given time

Function is to switch from one task, thread, or
process to another (Context Switching)



7/16/2015
Overhead – should be completed as quickly as possible
Dispatch time should be independent of the number of
threads in the ready list
Ready list should be organized each time an element is
added to the list
25
Basic Facilities
7/16/2015
26
Basic Facilities
7/16/2015
27
Basic Facilities

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


7/16/2015
Static – priorities are set before the system begins
execution
Dynamic – priorities can be redefined at run time
28
Basic Facilities


Round Robin – give each task an equal share of
the processor


7/16/2015
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
Implemented when all tasks or threads have the
same priority level
May be implemented within a priority range
29
Basic Facilities

Synchronization and exclusion objects

Required so that threads and tasks can execute
critical code and to guarantee access in a
particular order





7/16/2015
Semaphores – synchronization and exclusion
Mutexes - exclusion
Conditional variables – exclusion based on a condition
Event flags – synchronization of multiple events
Signals – asynchronous event processing and exception
handling
30
Basic Facilities

Communications

Data may be exchanged between threads
and tasks via



Most RTOSs pass data by pointer


7/16/2015
Queues – mulitple messages
Mailboxes – single messages
Copying data structure would be less efficient
Pointer must be valid while receiving thread or
task makes use of it
31
Interrupts

RT systems respond to external events

External events are translated by the hardware
and interrupts are introduced to the system

Interrupt Service Routines (ISRs) handle system
interrupts



7/16/2015
May be stand alone or part of a device driver
RTOSs should allow lower level ISRs to be preempted by
higher lever ISRs
ISRs must be completed as quickly as possible
32
Interrupts

RTOSs vary in model of interrupt
handling to task run
7/16/2015
33
Interrupts

Interrupt Dispatch Time


Interrupt Routine


Time needed for managing each simultaneous pending
interrupt
Pre-emption

7/16/2015
ISR execution time
Other Interrupt


time the hardware needs to bring the interrupt to the
processor
Time needed to execute critical code during which no
pre-emption may happen
34
Interrupts

Scheduling


Context Switch


Time to switch from one context to another
Return from System Call

7/16/2015
Time needed to make the decision on which
thread to run
Extra time needed when the interrupt occurred
while a system call was being executed
35
Interrupts

System calls cause software interrupts
(SWIs)

Portable Operating System Interface
(POSIX) defines the syntax of many of the
library calls that execute the SWIs

7/16/2015
Attempts to make applications portable
36
Memory

RAM

Holds changing parts of the task control
block, stack, heap


Minimum number of RAM required varies by
vendor
Maximum addressable space will vary
depending on the memory model

7/16/2015
E.g., backward compatibility (x86) will limit to 64K
segments
37
Memory

Predictability

The need to make memory access
“predictable” (bound) prohibits the use of
virtual memory


Systems should have locking capability –
prevent swapping by locking the process into
main memory
Paging map should be part of the process
context (loaded onto the processor or MMU)

7/16/2015
Larger page sizes may be required to fit it all in 2k
38
Memory

7/16/2015
Segments may be used to avoid 2k limit
 Non-variable segment sizes may be used
 Prohibit deallocation to prevent garbage
collection (prevents displaced tasks from running
which leads to unpredictability)
39
Memory

Static memory allocation

All memory allocated to each process at
system startup



Expensive
Desirable solution for Hard-RT systems
Dynamic memory allocation

Memory requests are made at runtime


7/16/2015
Should know what to do upon allocation failure
Some RTOSs support a timeout function
40
Development Methodology

RTOS differ in development
configurations supported


7/16/2015
Host – machine on which the application is
developed
Target – machine on which the application
is to execute
41
Development Methodology

Host = Target


Host and target are on the same machine
RTOS has its own development environment
(compiler, debugger, and perhaps IDE)


Host  Target


7/16/2015
Usually of lesser quality
Two different machines linked together (serial,
LAN, bus, etc.)
Host generally machine with a proven General
Purpose Operating System (GPOS)
42
Development Methodology
Better development environment
Debugger is on host while application is executed on
target
 Debug agents are stored on target to
communicate with host
Simulator should be provided to execute prototype
application on the host




Hybrid

Host and target on same machine but on
different OSs

7/16/2015
Communicate via shared memory
43
Development Methodology

7/16/2015
Resource and hardware shared
 May prevents RTOS from predictable behavior
 May prevent GPOS from housekeeping duties
 Multiprocessor environment should improve
performance
44
Summary



A RTOS should be predictable
regardless of the system load and size
of queues/lists
RTOS should always support preemptive priority scheduling
The memory model utilized is very
important to the performance and
predictability of your RT system
7/16/2015
45
Summary
HRT
SRT
Mem
Allocation
Static
Dynamic/Static Dynamic
Virtual
Memory
No
No
Yes
Compaction
No
No
Yes
7/16/2015
NRT
46
Summary
VxWorks
QNX
Development Methodology
Host  Target
Host = Target
POSIX Compatibility
Most 1003.1b
API for C – POSIX.1
File Systems
MS-DOS, RT-11, raw disk, SCSI,
CD-ROM
Ramdisk (Unixlike), MS-DOS
Shared Memory Objects
VxMP (semaphores, message
queues, memory regions between
tasks on different processors)
Shared memory between
processes, shared files
Virtual Memory
VxVMI – support for boards with
MMU
???
Debugging
Target Agent – remote debugging
GNU
7/16/2015
47
Summary
Multitasking
VxWorks
QNX
Process-task based
Process-thread based
Interrupt-driven, priority-based
task scheduling, round-robin
Priority-based, round-robin,
FIFO (cooperative), adaptive
(decaying)
256 priority levels (0-255); 0
highest, 255 lowest
May be set dynamically
32 priority levels (0-31); 0
lowest, 31 highest
May be set dynamically
Semaphores
Counting, binary, mutual-exclusion
(recursive), and POSIX, timeouts
Memory based
Intertask Communications
Message queues (priority or FIFO),
pipes, sockets, signals, RPCs
Messages (copied), queues
(FIFO), pipes, sockets,
signals, proxies
7/16/2015
48
Summary
VxWorks
QNX
Priority inversion
Yes – tasks that owns a resource
executes at the priority of the
highest priority task blocked on
that resource
Yes – receiving processes
will float to higher level
priority of sending processes
Asynchronous I/O
Yes
“Yes” – FIFO queue/pipe
7/16/2015
49
Summary
Context
VxWorks
QNX
Task Program counter
CPU registers (optional Floating point)
Stack
I/O assignments (STD Out, In, Err)
Delay Timer
Timeslice timer
Kernel Control Structures
Signal Handlers
Debugging and performance monitoring
values
Process Program counter
CPU registers
Stack
I/O assignments
Memory address space is not part of
context (VxVMI is required for separate
address space per task – virtual to
physical memory mapping
7/16/2015
50
Summary
States
7/16/2015
VxWorks
QNX
Ready – Not waiting for any
resource except CPU
Pend – Blocked, waiting on
resource
Delay – Asleep for some duration
Suspend – Unavailable for
execution
Delay + S – Delayed & suspended
Pend + S – Pended & suspended
Pend + T – Pended with timeout
value
Pend + S + T – Pended,
suspended with timeout value
State + I – state plus an inherited
priority
Ready – Running or waiting to run
Blocked – waiting on resource
- Send Blocked – sent message not
received yet
- Receive Blocked – waiting to receive
- Reply Blocked – waiting on reply
- Signal Blocked – reply-blocked
process is interrupted by a signal
- Semaphore Blocked – waiting on a
semaphore
Wait – Waiting on child to terminate
Dead – Terminated but has not sent
status to parent
Held – Suspended by another process
51
Summary
Interrupts
VxWorks
QNX
Run in special context outside of
task (no task context switch)
SWI – signals
Share single stack if architecture
allows (must be large enough for
all possible nested interrupt
combinations)
HWI – ISRs implemented in
device drivers which are a
part of the system kernel
Must not invoke routines that may
cause the caller to block (taking
semaphores, I/O calls, malloc, and
free)
Must not call routines that use FPcoprocessor (floating point
registers are not saved and
restored); otherwise must explicitly
save and restore FP registers
7/16/2015
52
References




“What Makes A Good RTOS”, RTOS Evaluation Program, Real-Time
Magazine, Version 2.0, 28 February 2000.
Y. Li, M. Potkonjak and W. Wolf, “Real-Time Operating Systems for
Embedded Computing”, Department of Electrical Engineering, Princeton
University, Department of Computer Science, UCLA, IEEE 1997.
F. Kolnick, QNX 4 Real-time Operating System: Programming with
Messages in a Distributed Environment, Basic Computer Systems Inc.,
1998.
“VxWorks Guide”, WindRiver Systems.
7/16/2015
53