Transcript Real-Time Operating Systems

Real Time Operating Systems
Michael Thomas
Date:
Date
Rev. 1.00
Objective
Identify embedded programming models
Understand basic RTOS definitions and concepts
Points to consider when you “Buy or roll your own”
2
Defining application requirements
Real time: Computing with a deadline
A required level of service has to be provided in a bounded response
time
Consequence of missing deadlines: “Hardness” of the
problem/application
Hard real-time - absolute deadlines must be met
Firm real-time - low occurrence of missing a deadline can be tolerated
Soft real-time - tolerance in the order of human reaction time (50ms)
3
Basic concepts and definitions
Task: Self contained code that handles a singular
functionality or semi-independent portion of the
application that handles a specific duty.
Threads: Access to entire memory space
Processes: Memory access area limited based on process
creation parameters
Priority
4
Basic concepts and definitions
Scheduler
Implements the scheduling policy
Real-time Scheduling
Soft
Hard
Dynamic
Preemptive
5
Static
Non-preemptive Preemptive
Non-preemptive
Basic concepts and definitions
Determinism
Exact time taken for each thread to execute is a constant
Kernel
(Scheduler + Memory management + IPC + Synchronization)
primitives
Kernel latency (microkernel, picokernel etc)
Kernel space
6
Context Switch and Task Control Block
Context
Program Counter
Register Contents
Task Status
Priority
Typical TCB
Task ID
Other Info
Save context to TCB1
Context switch time
Save context to TCB2
current CPU task
Load context from TCB2
7
Load context from TCB1
H8S Stack frames during a context switch
task1 ready
task2 ready
task1
Context
task2
running
running
Switch
LOCAL
VARIABLES
task1
8
LOCAL
VARIABLES
task2
Preemption
RUNNING
Priority
WAITING
ISR
RTOS Context-Switch service
task 2
Context Switch
task 1
Time
Clock Interrupts occur every ~10 ms (allow OS to run)
OS checks to see if any higher priority process available
in ready queue
If so, suspend current process and switch to new process
9
Embedded programming models
System designed around task scheduling policy
Endless loop
Simple cyclic executive
Time driven cyclic
Multi-rate cyclic
Multi-rate cyclic for periodic tasks
Multi-rate cyclic with interrupts (bg/fg programming)
Priority based pre-emptive
10
Timer Interrupt
Task1
Task1
Task1
Task1
Task2
Task2
Task2
Task2
Task3
Task1
Task1
Task3
Task4
Task3
Task3
Task4
Task5
Task1
Task1
Task5
Simple
cyclic
Multi-rate
Time
Multi-rate
cyclic
driven
cyclic
for
cyclic
periodic
11
Where does an RTOS fit in?
Task management viewpoint:
12
RTOS Services
13
Task Management & Scheduling
Task is considered as a scheduling unit which
implements a function
OS services that collectively move tasks from one state
to another
Provide context switching services
Task parameters like deadline, period, priority etc need to
be specified
14
Task Management
Task states in a typical RTOS:
Dormant
Waiting
Ready
Running
Interrupted
15
Task Management
State transitions of a task in a typical RTOS
Waiting for
resources
Resources
available
Interrupt
task
deleted
ISR done
Task resumed
Task preempted
16
Scheduler and Scheduling Policy
Scheduling algorithms generate a feasible execution
sequence based on
task priority
task deadlines
resource requirements
Round Robin
Earliest deadline First (EDF)
Maximum Urgency First (MUF)
Priority Ceiling Protocol (Resource based)
17
Interrupt Handling
RTOS Independent Interrupts
ISR preempts the RTOS and runs
Used for events that require accurate timing
• RTOS Dependant Interrupts:
ISR is run within the RTOS
• RTOS should allow lower level ISR to be pre-empted by
higher level ISR (RTOS Dependant Interrupts)
• ISR must complete as quickly as possible.
• Both Dependant and Independent ISRs can exist in one
system
18
Clocks and Timers
Tick timer
Decides granularity of system.
System response time limited by tick timer
Eg: 50 microsec motor control interrupt cannot be handled by a 1 millisec
tick timer OS.
Timer primitives
Allow user to specify “Run task every x unit of time” during task
creation. eg: scan keyboard
19
Synchronization
Synchronization primitive used to provide:
Mutual exclusion: Critical sections not accessed simultaneously
Conditional synchronization: Ensure tasks run in a specific order
• Synchronization constructs:
Mutex (Binary semaphore)
Semaphore (Counting semaphore)
20
Synchronization and Semaphores
Two tasks and single buffer
Producer task and consumer task
Consumer task to wait till producer task is done with buffer.
Synchronization and data integrity achieved by using a
semaphore to lock access to buffer.
Issues:
Deadlocks
Priority Inversion: Low priority thread obtains a lock that blocks a
higher priority thread
21
Priority Inversion
High priority task H
Medium priority task M
Preemption after
resource X released
preemption
X
Low priority task L
time
Tasks L & H both need access to resource X
Task L has locked this resource and hence delays H.
Task M preempts L causing further delay to H; this is priority inversion
Ready to run
Running
22
Inter Task Communication
Primary requirements/characteristics:
Non-blocking communication
Bounded latency
Asynchronous communication
Shared Memory
Mailbox/Message Queues
23
Mailbox/Message Queue
Task 1
Mailbox 1
Task 3
Task 2
24
Memory Management
Memory Management Unit (MMU)
Handles Virtual memory operations.
Memory protection esp. in process based OS
Dynamic memory allocation
Heap; non-fragmenting memory allocation techniques
“Pool” allocation mechanism
25
Dynamic Memory allocation: RTOS heap
31
62
127
255
511
Buffer size
Free buffer list
26
RTOS classification based on architecture
Soft, Firm and Hard real-time
Pre-emptive, Non pre-emptive
Thread based, Process based
Scheduling policy: RM, EDF, RR, MUF etc
Dynamic, Static
Cost structure
27
RTOS aware debugging
Standard source level debugging not sufficient in
multithreaded/multitasking environment.
Potential bugs:
Data corruption due to improper synchronization
Deadlock
Starvation
Stack Overflow
Memory leaks
RTOS-aware debuggers provide tools that help detect
such conditions for quicker debugging.
Extra windows showing state of all tasks (running, waiting etc), including
buffers currently used by each task, semaphores used etc.
28
Buy vs Roll your Own
Factors:
Cost Structure.
Support and documentation
Scalability
Portability
Debugging tools
Testing
29
Buy vs Roll your Own
Cost Structure.
Royalty per product/ one time payment
Overall development, debugging, testing and support resources
for in-house tool usually far outweigh investing in a commercial
RTOS
Support and documentation
Insufficient documentation
Small team responsible for R&D and maintenance
Commercial RTOSes are well documented with good support
30
Buy vs Roll your Own
Scalability
In-house tools are usually designed to meet exact specifications
so it might be a good fit
Commercial vendors allow significant customization of the kernel
(in some cases a GUI for this purpose), so the notion of too much
overhead code is unfounded
Some commercial vendors also provide source code to allay
engineer fears of “I cant see the code so I don’t know what’s
going on”
31
Buy vs Roll your Own
Portability
Porting an in-house solution to different hardware will require
significant re-investment of time and resources
Commercial vendors have ports for all major hardware targets
and will usually port to others as well
Debugging tools
Debugging tools have to be developed/ported for in house
RTOS; usually takes 4x time needed to develop the RTOS
Commercial vendors have readily available debuggers and will
port over desired features in most cases
32
Buy vs Roll your Own
Testing
In-house testing; takes 10x development time to properly test
RTOS
Commercial RTOSes are sufficiently tested and have also been
used by many customers so most bugs will have been ironed out.
33
Objectives: Recap
Identify embedded programming models
Understand basic RTOS definitions and concepts
Points to consider when you “Buy or roll your own”
34