Introduction
• What is an Embedded System?
– Application-specific computer system
– Built into a larger system
– Often with real-time computing constraints
• Why add a computer to the larger system?
– Better performance
– More functions and features
– Lower cost
– More dependability
• Economics
– Microcontrollers (used for embedded computers) are high-volume, so
recurring cost is low
– Nonrecurring cost dominated by software development
• Networks
– Often embedded system will use multiple processors communicating across
a network to lower parts and assembly costs and improve reliability
Example Embedded System: Bike Computer
• Functions
– Speed and distance measurement
Input:
• Constraints Wheel rotation
– Size Mode key
– Cost
– Power and Energy
– Weight
• Inputs
– Wheel rotation indicator
– Mode key
• Output
– Liquid Crystal Display
Output:
• Use Low Performance Display speed
Microcontroller and distance
– 8-bit, 10 MIPS
Gasoline Automobile Engine Control Unit
• Functions § Many Inputs and Outputs
– Fuel injection § Discrete sensors & actuators
– Air intake setting § Network interface to rest of car
– Spark timing
– Exhaust gas circulation § Use High Performance
– Electronic throttle control Microcontroller
– Knock control § E.g. 32-bit, 3 MB flash memory, 150 -
300 MHz
• Constraints
– Reliability in harsh environment
– Cost
– Weight
Example Analog Sensor - Depth Gauge
V_ref
// Your software
Analog to ADC_Code = adc_read();
Pressure
Digital V_sensor = ADC_code * V_ref / ADC_MASK;
Sensor
Converter Pressure_kPa = 250 * (V_sensor / V_supply
+ 0.04);
Pressure Depth_ft = 33 * (Pressure_kPa –
Atmos_Press_kPa) / 101.3;
V_sensor ADC_Code Voltages
ADC
Output Codes
V_ref 111..111
111..110
111..101
111..100
Typical Absolute Pressure vs. V_sensor ADC_Code
Ouput 000..001
Ground 000..000
5.0
• Sensor detects pressure and generates a
4.0 proportional output voltage V_sensor
Output [V]
3.0 • ADC generates a proportional digital integer
2.0 (code) based on V_sensor and V_ref
1.0 • Code can convert that integer to a
0.0 something more useful
0 20 40 60 80 100 120 140 160 180 200 220 240 260 – first a float representing the voltage,
Pressure [kPa]
– then another float representing pressure,
– finally another float representing depth
Motor Control Unit
• Functions
– Motor control
– System communications
– Current monitoring
– Rotation speed detection
• Constraints
– Reliability in
harsh environment
– Cost
– Weight
• Many Inputs and Outputs
– Discrete sensors & actuators
Options for Building Embedded Systems
Implementation Design Unit Upgrades Size Weight Power System
Cost Cost & Bug Speed
Fixes
Discrete Logic low mid hard large high ? very fast
Dedicated Hardware
ASIC high very low hard tiny - 1 die very low low extremely
($500K/ fast
mask set)
Programmable logic low to mid easy small low medium to very fast
– FPGA, PLD mid high
Microprocessor + low to mid easy small to low to medium moderate
memory + mid med. moderate
peripherals
Software Running on
Generic Hardware
Microcontroller (int. low mid to easy small low medium slow to
memory & low moderate
peripherals)
Embedded PC low high easy medium moderate to medium to fast
high high
Benefits of Embedded Systems
• Greater performance and efficiency
– Software makes it possible to provide sophisticated control
• Lower costs
– Less expensive components can be used
– Manufacturing costs reduced
– Operating costs reduced
– Maintenance costs reduced
• More features
– Many not possible or practical with other approaches
• Better dependability
– Adaptive system which can compensate for failures
– Better diagnostics to improve repair time
Functions of Embedded Systems
• Closed-loop control system
– Monitor a process, adjust an output to maintain
desired set point (temperature, speed, direction, etc.)
• Sequencing
– Step through different stages based on environment
and system
• Signal processing
– Remove noise, select desired signal features
• Communications and networking
– Exchange information reliably and quickly
Attributes of Embedded Systems
• Interfacing with larger system and environment
– Analog signals for reading sensors
• Typically use a voltage to represent a physical value
– Power electronics for driving motors, solenoids
– Digital interfaces for communicating with other digital
devices
• Simple - switches
• Complex – displays
• Concurrent, reactive behaviours
– Must respond to sequences and combinations of events
– Real-time systems have deadlines on responses
– Typically must perform multiple separate activities
concurrently
Attributes of Embedded Systems
• Fault handling
– Many systems must operate independently for
long periods of time, requiring them to handle
likely faults without crashing
– Often fault-handling code is larger and more
complex than the normal-case code
• Diagnostics
– Help service personnel determine problems
quickly
Constraints of Embedded Systems
• Cost
– Competitive markets penalize products which don’t
deliver adequate value for the cost
• Size and weight limits
– Mobile (aviation, automotive) and portable (e.g.
handheld) systems
• Power and energy limits
– Battery capacity
– Cooling limits
• Environment
– Temperatures may range from -40°C to 125°C, or even
more
Impact of Constraints
• Microcontrollers used (rather than microprocessors)
– Include peripherals to interface with other devices, respond
efficiently
– On-chip RAM, ROM reduce circuit board complexity and cost
• Programming language
– Programmed in the C language rather than the Java language
(resulting in smaller and faster code, so less expensive MCU)
– Some performance-critical code may be in assembly language (a
lower level language)
• Operating system
– Typically no OS, but instead simple scheduler (or even just
interrupts + main code (foreground/background system)
– If OS is used, likely to be a lean RTOS
MCU Hardware & Software for
Concurrency Peripheral Bus
• CPU executes instructions from one
or more thread of execution Timers
• Specialized hardware peripherals
add dedicated concurrent
processing ADC
– Watchdog timer Cortex-M
Core
– Analog interfacing
Interrupt GPIO
– Timers Controlle
– Communications with other devices r
– Detecting external signal events
UART
– LCD driver
• Peripherals use interrupts to notify
CPU of events I2C
The MCU has extra hardware (besides the CPU core) to allow it to interface with the outside
world more easily, and to simplify processing multiple tasks concurrently.
Concurrent Hardware & Software
Operation
Software Hardware Software Hardware Software
Timer A/D Converter
Main Peripheral
Timer ISR
Peripheral ADC ISR
Start timer Timer interrupt Start ADC
ADC interrupt
ADC interrupt
ADC interrupt
ADC_done = 1 ADC interrupt
Timer interrupt Start ADC
ADC interrupt
Time
ADC interrupt
ADC interrupt
ADC_done = 1 ADC interrupt
Timer interrupt Start ADC
ADC interrupt
ADC interrupt
ADC interrupt
ADC_done = 1 ADC interrupt
• Embedded systems rely on both MCU hardware
peripherals and software to get everything done
on time
CPU Scheduling
• MCU’s Interrupt system provides a basic scheduling approach for
CPU
– “Run this subroutine every time this hardware event occurs”
– Is adequate for simple systems
• More complex systems need to support multiple concurrent
independent threads of execution
– Use task scheduler to share CPU
– Different approaches to task scheduling
• How do we make the processor responsive? (How do we make it do
the right things at the right times?)
– If we have more software threads than hardware threads, we need to
share the processor.
How do we get the processor to run the right software at the right time? This is called
scheduling. The better we are at scheduling, the slower a processor we can use, or the
more the processor can do and still meet our timing requirements.
TRelease
Definitions
Other
processing
Ttask
Scheduler
Task or ISR Code
Latency
Response
Time
Time
– TRelease(i) = Time at which task (or interrupt) i requests service/is
released/is ready to run
– TLatency (i) = Delay between release and start of service for task i
– TResponse(i) = Delay between request for service and completion of
service for task i
– TTask(i) = Time needed to perform computations for task i
– TISR(i) = Time needed to perform interrupt service routine i
We define some terms to represent the individual steps the system takes in response to an
event. We will use these terms later to determine worst-case response time in a system with
many such events (and the corresponding handler code).
Scheduling Approaches
• Rely on MCU’s hardware interrupt system to
run right code
– Event-triggered scheduling with interrupts
– Works well for many simple systems
• Use software to schedule CPU’s time
– Static cyclic executive
– Dynamic priority
• Without task-level preemption
• With task-level preemption
Event-Triggered Scheduling using Interrupts
• Basic architecture, useful for simple low-power devices
– Very little code or time overhead
• Leverages built-in task dispatching of interrupt system
– Can trigger ISRs with input changes, timer expiration, UART
data reception, analog input level crossing comparator
threshold
• Function types
– Main function configures system and then goes to sleep
• If interrupted, it goes right back to sleep
– Only interrupts are used for normal program operation
• Example: bike computer
– Int1: wheel rotation
– Int2: mode key
– Int3: clock
– aOutput:
Let’s take Liquid Crystal
look at scheduling Display code using the MCU’s interrupt system.
the bike computer
Bike Computer Functions
Reset ISR 1: ISR 2: ISR 3:
Wheel rotation Mode Key Time of Day Timer
Configure rotations++; mode++; cur_time ++;
timer, if(rotations> mode = mode % lcd_refresh--;
inputs and R_PER_MILE/10) { NUM_MODES; if
outputs tenth_miles++; return from (lcd_refresh==0) {
rotations = 0; interrupt; convert
cur_time = 0; } tenth_miles
rotations = speed = and display
0; circumference / convert speed
tenth_miles = (cur_time – and display
0; prev_time); if (mode == 0)
compute avg_speed; convert
while (1) { prev_time = cur_time
sleep; cur_time; and display
} return from else
interrupt convert
avg_speed
and display
lcd_refresh =
LCD_REF_PERIOD
}
A More Complex Application
• GPS-based Pothole Alarm and Moving Map
– Sounds alarm when approaching a pothole
– Display’s vehicle position on LCD
– Also logs driver’s position information
– Hardware: GPS, user switches, speaker, LCD, flash memory
This system is more complicated. It has to warn us when we are approaching a pothole,
display information, and record vehicle position information. This involves a lot of processing,
which we examine next.
Application Software Tasks
– Dec: Decode GPS sentence to find current vehicle position.
– Check: Check to see if approaching any pothole locations.
Takes longer as the number of potholes in database
increases.
– Rec: Record position to flash memory. Takes a long time if
erasing a block.
– Sw: Read user input switches. Run 10 times per second
– LCD: Update LCD with map. Run 4 times per second
Dec
Check
Rec
Sw
LCD
Time
We break the software into five tasks in order to simplify its design and construction.
How do we schedule these tasks?
Dec
• Task scheduling: Deciding which
Check task should be running now
Rec
• Two fundamental questions:
– Do we run tasks in the same
Sw order every time?
• Yes: Static schedule (cyclic
executive, round-robin)
LCD
• No: Dynamic, prioritized
schedule
– Can one task preempt another,
or must it wait for completion?
• Yes: Preemptive
• No: Non-preemptive
(cooperative, run-to-
completion)
Any scheduling approach we use will have to address two basic issues: task ordering and
preemption.
Static Schedule (Cyclic Executive)
Dec Check Rec Sw LCD Dec
• Pros while (1){
– Very simple Dec();
• Cons Check();
– Always run the same schedule, Rec();
regardless of changing conditions and Sw();
relative importance of tasks.
– All tasks run at same rate. Changing LCD();
rates requires adding extra calls to the }
function.
– Maximum delay is sum of all task run
times. Polling/execution rate is
1/maximum delay.
Static Schedule Example
GPS Data Arrives Checking
complete
Response Time
Rec Sw LCD Dec Check
• What if we receive GPS position right after Rec starts
running?
• Delays
– Have to wait for Rec, Sw, LCD before we start decoding position
with Dec.
– Have to wait for Rec, Sw, LCD, Dec, Check before we know if we
are approaching a pothole!
This approach doesn’t work so well in the worst case, since we have to do a lot of less
important processing before we get the pothole warning.
Dynamic Scheduling
• Allow schedule to be computed on-the-fly
– Based on importance or something else
– Simplifies creating multi-rate systems
• Schedule based on importance
– Prioritization means that less important tasks don’t delay more
important ones
• How often do we decide what to run?
– Coarse grain – After a task finishes. Called Run-to-Completion
(RTC) or non-preemptive
– Fine grain – Any time. Called Preemptive, since one task can
preempt another.
Instead of always running the tasks in the same order, we can change the order of the tasks
based on what’s more important.
Dynamic RTC Schedule
GPS Data Arrives Checking
complete
Response Time
Rec De Check
c
• What if we receive GPS position right after Rec starts
running?
• Delays
– Have to wait for Rec to finish before we start decoding
position with Dec.
– Have to wait for Rec, Dec, Check before we know if we are
approaching a pothole
Let’s start deciding which task to run next, and then running it to completion (RTC). After the
task finishes we check to see which task to run next, repeating the process.
Task State and Scheduling Rules
• Scheduler chooses
among Ready tasks for Ready
execution based on Task is released
priority (ready to run)
• Scheduling Rules
Start
– If no task is running,
scheduler starts the highest
highest priority ready Waiting priority
task ready task
– Once started, a task runs
until it completes
– Tasks then enter waiting
state until triggered or Task completes Running
released again
Dynamic Preemptive Schedule
GPS Data Arrives Checking
complete
Response Time
Dec Check Rec
• What if we receive GPS position right after Rec starts
running?
• Delays
– Scheduler switches out Rec so we can start decoding position
with Dec immediately
– Have to wait for Dec, Check to complete before we know if we
are approaching a pothole
Let’s change the rules by allowing preemption. Instead of allowing a task to run to completion,
we allow it to be preempted if a higher-priority task is ready to run. This will improve response
time quite a bit.
Comparison of Response Times
Static
Rec Sw LCD Dec Check
Dynamic Run-to-Completion
Rec Dec Check
Dynamic Preemptive
Dec Check
• Pros
– Preemption offers best response time
• Can do more processing (support more potholes, or higher vehicle speed)
• Or can lower processor speed, saving money, power
• Cons
– Requires more complicated programming, more memory
– Introduces vulnerability to data race conditions
Here we see that as we change the scheduling rules we reduce the response time for higher
priority tasks. This is done by deferring less important work until later. However, we need to be
more careful using the more responsive schedulers as they introduce possible bugs and use
more memory.
Common Schedulers
• Cyclic executive - non-preemptive and static
• Run-to-completion - non-preemptive and
dynamic
• Preemptive and dynamic
Cyclic Executive with Interrupts
BOOL DeviceARequest,
• Two priority levels DeviceBRequest,
– main code – foreground DeviceCRequest;
– Interrupts – background void interrupt HandleDeviceA()
{
• Example of a foreground / /* do A’s urgent work */
background system ...
DeviceARequest = TRUE;
}
• Main user code runs in foreground void main(void) {
while (TRUE) {
• Interrupt routines run in if (DeviceARequest) {
background (high priority) FinishDeviceA();
– Run when triggered }
– Handle most urgent work if (DeviceBRequest) {
FinishDeviceB();
– Set flags to request processing by
main loop }
if (DeviceCRequest) {
FinishDeviceC();
The first scheduling approach is easy to code }
for small systems. }
Run-To-Completion Scheduler
• Use a scheduler function to run task functions at the right rates
– Table stores information per task
• Period: How many ticks between each task release
• Release Time: how long until task is ready to run
• ReadyToRun: task is ready to run immediately
– Scheduler runs forever, examining schedule table which indicates tasks which are
ready to run (have been “released”)
– A periodic timer interrupt triggers an ISR, which updates the schedule table
• Decrements “time until next release”
• If this time reaches 0, set that task’s Run flag and reload its time with the
period
• Follows a “run-to-completion” model
– A task’s execution is not interleaved with any other task
– Only ISRs can interrupt a task
– After ISR completes, the previously-running task resumes
• Priority is typically static, so can use a table with highest priority tasks first for a
fast, simple scheduler implementation.
The RTC scheduler is more complex but makes
the application design much easier.
Preemptive Scheduler
• Task functions need not run to completion, but
can be interleaved with each other
– Simplifies writing software
– Improves response time
– Introduces new potential problems
• Worst case response time for highest priority task
does not depend on other tasks, only ISRs and
scheduler
– Lower priority tasks depend only on higher priority
tasks
A preemptive scheduler makes application design easier (mostly) and offers better
performance (response time).
Task State and Scheduling Rules
• Scheduler chooses among
Ready tasks for execution What the Ready
based on priority task needs
happens
• Scheduling Rules
– A task’s activities may lead This is This isn’t
it to waiting (blocked) highest highest
– A waiting task never gets Waiting priority priority
the CPU. It must be ready task ready task
signaled by an ISR or
another task.
– Only the scheduler moves
tasks between ready and Task needs
running something Running
to happen
What’s an RTOS?
• What does Real-Time mean?
– Can calculate and guarantee the maximum response time for each task
and interrupt service routine
– This “bounding” of response times allows use in hard-real-time systems
(which have deadlines which must be met)
• What’s in the RTOS
– Task Scheduler
• Preemptive, prioritized to minimize response times
• Interrupt support
– Core Integrated RTOS services
• Inter-process communication and synchronization (safe data sharing)
• Time management
– Optional Integrated RTOS services
• I/O abstractions?
• memory management?
• file system?
• networking support?
• GUI??
Comparison of Timing Dependence
Non-preemptive Non-preemptive Preemptive Dynamic
Static Dynamic
Device A ISR
Device A ISR Device A ISR
Device B ISR
Device B ISR Device B ISR
Device ... ISR
Device ... ISR
Device ... ISR Device Z ISR
Device Z ISR
Device Z ISR
Slowest Task
Task 1 Code
Task 5 Code Task 1 Code
Task 1 Code Task 4 Code
Task 2 Code Task 6 Code
Task 3 Code Task 2 Code
Task 2 Code
Task 3 Code Task 3 Code
• Code can be delayed Task 4 Code Task 4 Code
by everything at
same level (in oval) Task 5 Code Task 5 Code
or above
Task 6 Code Task 6 Code
Comparison of RAM Requirements
Task 4 Max
Non-preemptive Non- Preemptiv
Stack
Static preemptive e Dynamic
Dynamic
Task 3 Max
Stack
Task 2 Max Stack
Task 4 Max Stack
Task 2 Max Stack
Task 3 Max Stack
Task 3 Max Stack
Task 4 Max Stack
Task 1 Max Stack
Task 1 Max Stack
Task 2 Max Stack
Task 1 Statics Task 1 Statics
Task 2 Statics Task 2 Statics
Task 3 Statics Task 3 Statics
Task 4 Statics Task 4 Statics
Task 1 Max
• Preemption requires space for each stack*
Stack
• Need space for all static variables (including globals)
Task 1 Statics
*except for certain special cases Task 2 Statics
Task 3 Statics
The different schedulers also require different amounts of read/write Task 4 Statics
memory for the activation record (call) stack.
Consider a system with the following tasks. We wish to minimize the response time for task C.
For each type of scheduler, describe the sequence of processing activities which will lead to
the minimum and the maximum response times for task C. Assume that each task is ready to
run and there are no further task releases.
a. Static, non-preemptive scheduler
Best Case: Task C starts immediately (at time 0). Tr = 0 + 2 = 2
Worst Case: Task A and Task B run first. Tr = 0 + 3 + 1 + 2 = 6
b. Dynamic, non-preemptive scheduler
Best Case: Task C starts immediately (at time 0).
Worst Case: Longest task (A) just started running ε time units ago, so C won’t
run until it finishes. Tr = 0 + 3 – ε + 2 = 5 - ε
c. Dynamic, preemptive scheduler
Best Case: Task C starts immediately (at time 0).
Worst Case: Longest task (A) just started running ε time units ago, but it is
preempted by C.
Tr = 0 + 2 = 2
