Addis Ababa University

College of Natural and Computational Sciences

DEPARTMENT OF COMPUTER SCIENCE

Real time and Embedded System(CoSc6016)

Ayalew Belay (PhD)

email:[Link]@[Link]
 Chapter Four:

Embedded Systems Programming

Models of Computation
 Introduction
Describing embedded system’s processing
behavior
− Can be extremely difficult
⚫ Complexity increasing with increasing IC capacity
− Past: washing machines, small games, etc.
⚫ Hundreds of lines of code

− Today: TV set-top boxes, Cell phone, etc.

⚫ Hundreds of thousands of lines of code

⚫ Desired behavior often not fully understood in

beginning
− Many implementation bugs due to description
mistakes/omissions
− English (or other natural language) common
starting point
⚫ Precise description difficult to impossible
⚫ Example: Motor Vehicle Code – thousands of
pages long...
 Models and languages
How can we (precisely) capture behavior?
− We may think of languages (C, C++), but computation model is the
key
Common computation models:
− Sequential program model
⚫ Statements, rules for composing statements,
semantics for executing them
− Communicating process model
⚫ Multiple sequential programs running concurrently
− State machine model
⚫ For control dominated systems, monitors control
inputs, sets control outputs
− Dataflow model
⚫ For data dominated systems, transforms input data
streams into output streams
− Object-oriented model
⚫ For breaking complex software into simpler, well-
defined pieces
 Models vs. languages
Poetry Recipe Story State Sequent. Data-
machine program flow
Models

Languages English Spanish Japanese C C++ Java

Recipes vs. English Sequential programs vs. C

⚫ Computation models describe system behavior

− Conceptual notion, e.g., recipe, sequential program
⚫ Languages capture models
− Concrete form, e.g., English, C
⚫ Variety of languages can capture one model
− E.g., sequential program model → C,C++, Java
⚫ One language can capture variety of models
− E.g., C++ → sequential program model, object-oriented model,
state machine model
⚫ Certain languages better at capturing certain computation
 Introductory example: An elevator controller

Partial English description System interface

⚫ Simple elevator Unit up

“Move the elevator either up or down
controller
Control down
to reach the requested floor. Once at
the requested floor, open the door for open
− Request Resolver at least 10 seconds, and keep it open floor

resolves various floor until the requested floor changes.

Ensure the door is never open while
req
Request
requests into single moving. Don’t change directions Resolver
buttons
unless there are no higher requests b1
requested floor when moving up or no lower requests ... b2
inside
elevator
bN
− Unit Control moves when moving down…”
up1 up/down
elevator to this up2 buttons on
dn2 each
requested floor up3 floor
dn3
⚫ Try capturing in C... ...
dnN
Elevator controller using a sequential program
model
Sequential program model

Inputs: int floor; bit b1..bN; up1..upN-1; dn2..dnN;

Outputs: bit up, down, open; Partial English description
Global variables: int req; System interface

void UnitControl() void RequestResolver()

{ {
“Move the elevator either up or down Unit up
up = down = 0; open = 1; while (1) to reach the requested floor. Once at Control down
while (1) { ... the requested floor, open the door for
while (req == floor); req = ... open
open = 0; ...
at least 10 seconds, and keep it open
if (req > floor) { up = 1;} } until the requested floor changes. floor
else {down = 1;} Ensure the door is never open while req
while (req != floor);
up = down = 0;
moving. Don’t change directions Request
void main()
open = 1; {
unless there are no higher requests Resolver
b1 buttons
delay(10); Call concurrently: when moving up or no lower requests inside
} b2
UnitControl() and when moving down…” ... elevator
} RequestResolver() bN
}
up1 up/down
up2 buttons on
dn2 each
up3 floor
dn3
You might have come up with something having ...
even more if statements. dnN
 Finite-state machine (FSM) model
⚫ Trying to capture this behavior as sequential program is a
bit awkward
⚫ Instead, we might consider an FSM model, describing the
system as:
− Possible states
⚫ E.g., Idle, GoingUp, GoingDn, DoorOpen
− Possible transitions from one state to another based on input
⚫ E.g., req > floor
− Actions that occur in each state
⚫ E.g., In the GoingUp state, u,d,o,t = 1,0,0,0 (up = 1, down, open, and
timer_start = 0)
⚫ Try it...
Finite-state machine (FSM) model
UnitControl process using a state machine

req > floor

u,d,o, t = 1,0,0,0 GoingUp !(req > floor)

req > floor timer < 10

u,d,o,t = 0,0,1,0 !(timer < 10)

Idle DoorOpen
req == floor u,d,o,t = 0,0,1,1
req < floor

!(req<floor)
u,d,o,t = 0,1,0,0
GoingDn

u is up, d is down, o is open

req < floor
t is timer_start
 Finite-state machine with data path
model (FSMD)
⚫ FSMD extends FSM: complex data types and variables for storing data
− FSMs use only Boolean data types and operations, no variables
⚫ FSMD: 7-tuple <S, I , O, V, F, H, s0> We described UnitControl as an FSMD
− S is a set of states {s0, s1, …, sl}
req > floor
− I is a set of inputs {i0, i1, …, im}
− O is a set of outputs {o0, o1, …, on} u,d,o, t = 1,0,0,0 GoingUp !(req > floor)

− V is a set of variables {v0, v1, …, vn} req > floor timer < 10
!(timer < 10)
− F is a next-state function (S x I x V → S) u,d,o,t = 0,0,1,0
Idle DoorOpen
− H is an action function (S → O + V) req == floor
req < floor
u,d,o,t = 0,0,1,1

− s0 is an initial state u,d,o,t = 0,1,0,0 GoingDn

!(req<floor)

⚫ I,O,V may represent complex data types (i.e., integers, floating point, etc.)
u is up, d is down, o is open
⚫ F,H may include arithmetic operations req < floor t is timer_start

⚫ H is an action function, not just an output function

− Describes variable updates as well as outputs
⚫ Complete system state now consists of current state, si, and values of all variables
 Describing a system as a state
machine
1. List all possible states 2. Declare all variables (none in this example)
3. For each state, list possible transitions, with conditions, to other states
4. For each state and/or transition, req > floor
list associated actions
5. For each state, ensure exclusive u,d,o, t = 1,0,0,0 GoingUp !(req > floor)
and complete exiting transition
conditions req > floor timer < 10

• No two exiting conditions can u,d,o,t = 0,0,1,0

Idle !(timer < 10) DoorOpen
be true at same time req == floor u,d,o,t = 0,0,1,1
– Otherwise nondeterministic req < floor

state machine !(req<floor)

• One condition must be true at u,d,o,t = 0,1,0,0
GoingDn

any given time u is up, d is down, o is open

– Reducing explicit transitions req < floor
should be avoided when first t is timer_start

learning
State machine vs. sequential program model
⚫ Different thought process used with each model
⚫ State machine:
− Encourages designer to think of all possible states and transitions
among states based on all possible input conditions
⚫ Sequential program model:
− Designed to transform data through series of instructions that may be
iterated and conditionally executed
⚫ State machine description excels in many cases
− More natural means of computing in those cases
− Not due to graphical representation (state diagram)
⚫ Would still have same benefits if textual language used (i.e., state table)
⚫ Besides, sequential program model could use graphical representation (i.e.,
flowchart)
 Capturing state machines in
sequential programming language
⚫ Despite benefits of state machine model, most popular development tools use
sequential programming language
− C, C++, Java, Ada, VHDL, Verilog, etc.
− Development tools are complex and expensive, therefore not easy to adapt or
replace
⚫ Must protect investment
⚫ Two approaches to capturing state machine model with sequential
programming language
− Front-end tool approach
⚫ Additional tool installed to support state machine language
− Graphical and/or textual state machine languages
− May support graphical simulation
− Automatically generate code in sequential programming language that is input to main development
tool
⚫ Drawback: must support additional tool (licensing costs, upgrades, training, etc.)
− Language subset approach
⚫ Most common approach...
 Language subset approach
⚫ Follow rules (template) for #define IDLE0
#define GOINGUP1
capturing state machine #define GOINGDN2
#define DOOROPEN3
constructs in equivalent sequential void UnitControl() {
int state = IDLE;
language constructs while (1) {
⚫ Used with software (e.g.,C) and switch (state) {
IDLE: up=0; down=0; open=1; timer_start=0;
hardware languages (e.g.,VHDL) if
if
(req==floor) {state = IDLE;}
(req > floor) {state = GOINGUP;}
⚫ Capturing UnitControl state if (req < floor) {state = GOINGDN;}
break;
machine in C GOINGUP: up=1; down=0; open=0; timer_start=0;
if (req > floor) {state = GOINGUP;}
− Enumerate all states (#define) if (!(req>floor)) {state = DOOROPEN;}
− Declare state variable initialized to break;
GOINGDN: up=1; down=0; open=0; timer_start=0;
initial state (IDLE) if (req < floor) {state = GOINGDN;}
− Single switch statement branches if (!(req<floor)) {state = DOOROPEN;}
break;
to current state’s case DOOROPEN: up=0; down=0; open=1; timer_start=1;
− Each case has actions if (timer < 10) {state = DOOROPEN;}
if (!(timer<10)){state = IDLE;}
⚫ up, down, open, timer_start break;
}
− Each case checks transition }
}

conditions to determine next state

⚫ if(…) {state = …;}

UnitControl state machine in sequential programming language

 Role of appropriate model and language
⚫ Finding appropriate model to capture embedded system is an important step
− Model shapes the way we think of the system
⚫ Originally thought of sequence of actions, wrote sequential program
− First wait for requested floor to differ from target floor
− Then, we close the door
− Then, we move up or down to the desired floor
− Then, we open the door
− Then, we repeat this sequence
⚫ To create state machine, we thought in terms of states and transitions among states
− When system must react to changing inputs, state machine might be best model
⚫ HCFSM described FireMode easily, clearly
⚫ Language should capture model easily
− Ideally should have features that directly capture constructs of model
− FireMode would be very complex in sequential program
⚫ Checks inserted throughout code
− Other factors may force choice of different model
⚫ Structured techniques can be used instead
− E.g., Template for state machine capture in sequential program language
 HCFSM and the State charts language
• Hierarchical/concurrent state machine model
(HCFSM) With hierarchy
– Extension to state machine model to support Without hierarchy
hierarchy and concurrency A
– States can be decomposed into another state A1 z A1 z
machine x w x
• With hierarchy has identical functionality as Without y B y B
w
hierarchy, but has one less transition (z)
• Known as OR-decomposition A2 z A2
– States can execute concurrently
• Known as AND-decomposition
Concurrency
• Statecharts
– Graphical language to capture HCFSM B
– timeout: transition with time limit as condition C D
– history: remember last substate OR-decomposed C1 D1
state A was in before transitioning to another x u
y v
state B
• Return to saved substate of A when returning from C2 D2
B instead of initial state
 Program-state machine model (PSM): HCFSM
plus sequential program model
ElevatorController
int req;
• Program-state’s actions can be FSM or UnitControl RequestResolver
sequential program NormalMode
up = down = 0; open = 1; ...
– Designer can choose most appropriate while (1) { req = ...
• Stricter hierarchy than HCFSM used in while (req == floor);
open = 0;
...

Statecharts if (req > floor) { up = 1;}

else {down = 1;}
– transition between sibling states only, single while (req != floor);
open = 1;
entry delay(10);
– Program-state may “complete” }
}
• Reaches end of sequential program code, OR !fire fire
• FSM transition to special complete substate FireMode
• PSM has 2 types of transitions up = 0; down = 1; open = 0;
while (floor > 1);
– Transition-immediately (TI): taken regardless of up = 0; down = 0; open = 1;
source program-state
– Transition-on-completion (TOC): taken only if
condition is true AND source program-state is
complete • NormalMode and FireMode described
– SpecCharts: extension of VHDL to capture as sequential programs
PSM model • Black square originating within
– SpecC: extension of C to capture PSM model FireMode indicates !fire is a TOC
transition
– Transition from FireMode to NormalMode
only after FireMode completed
 Concurrent process model
⚫ Describes functionality of system in terms of two or more
concurrently executing subtasks
ConcurrentProcessExample() { ⚫ Many systems easier to describe with concurrent process
x = ReadX()
y = ReadY() model because inherently multitasking
Call concurrently:
PrintHelloWorld(x) and
⚫ E.g., simple example:
PrintHowAreYou(y) − Read two numbers X and Y
}
PrintHelloWorld(x) { − Display “Hello world.” every X seconds
while( 1 ) { − Display “How are you?” every Y seconds
print "Hello world."
delay(x); ⚫ More effort would be required with sequential program or
}
} state machine model
PrintHowAreYou(x) {
while( 1 ) {
print "How are you?"
delay(y);
} Enter X: 1
} Enter Y: 2
Hello world. (Time = 1 s)
PrintHelloWorld
Hello world. (Time = 2 s)
Simple concurrent process example ReadX ReadY How are you? (Time = 2 s)
Hello world. (Time = 3 s)
PrintHowAreYou
How are you? (Time = 4 s)
Hello world. (Time = 4 s)
time ...

Subroutine execution over time Sample input and output

 Dataflow model
⚫ Derivative of concurrent process model
⚫ Nodes represent transformations
− May execute concurrently Z = (A + B) * (C - D)
⚫ Edges represent flow of tokens (data) from one node to
another A B C D

− May or may not have token at any given time

⚫ When all of node’s input edges have at least one token, + –
t1 t2
node may fire
*
⚫ When node fires, it consumes input tokens processes
transformation and generates output token Z
⚫ Nodes may fire simultaneously Nodes with arithmetic
⚫ Several commercial tools support graphical languages for transformations
capture of dataflow model A B C D
− Can automatically translate to concurrent process model for
implementation modulate convolve
− Each node becomes a process t1 t2

transform

Z
Nodes with more complex
transformations
 Synchronous data flow
⚫ With digital signal-processors (DSPs), data flows at fixed
rate
⚫ Multiple tokens consumed and produced per firing
⚫ Synchronous dataflow model takes advantage of this
− Each edge labeled with number of tokens A B C D
consumed/produced each firing
− Can statically schedule nodes, so can easily use sequential mA mB mC mD
program model
⚫ Don’t need real-time operating system and its overhead modulate convolve

⚫ How would you map this model to a sequential mt1 t1 t2 ct2

programming language? Try it... tt1 tt2
⚫ Algorithms developed for scheduling nodes into “single- transform
appearance” schedules
− Only one statement needed to call each node’s associated tZ
procedure
⚫ Allows procedure inlining without code explosion, thus Z
reducing overhead even more
⚫
Synchronous dataflow
Concurrent processes and real-time
systems
 Concurrent processes ⚫ Heartbeat Monitoring System
⚫ Task 1: ⚫ Task 2:
⚫ B[1..4] ⚫ Read pulse ⚫ If B1/B2 pressed then
⚫ Consider two examples ⚫

⚫
⚫

⚫
If pulse < Lo then
Activate Siren
⚫

⚫
Lo = Lo +/– 1
If B3/B4 pressed then

having separate tasks

⚫
⚫
⚫ If pulse > Hi then ⚫ Hi = Hi +/– 1
⚫ Heart-beat ⚫ Activate Siren ⚫ Sleep 500 ms
Sleep 1 second Repeat
running independently but pulse ⚫ ⚫

⚫ Repeat

sharing data
⚫ Difficult to write system
using sequential program
Set-top Box
model
⚫

Task 1: Task 2:
Concurrent process model
⚫ ⚫

⚫ ⚫ Read Signal ⚫ Wait on Task 1

⚫ Separate ⚫ Decode/output ⚫ Vid
easier ⚫
Audio/Video
Send Audio to ⚫
Audio
Repeat
eo

Separate sequential
⚫
In Task 2
− ⚫

pu ⚫ Send Video to
⚫

Task 3: Au
programs (processes) for
⚫ ⚫
t Task 3
⚫ Wait on Task 1 dio
Si ⚫ Repeat
Decode/output
each task
⚫

gn Video
al Repeat
Programs communicate
⚫

−
with each other
 Implementation
The choice of
⚫ Mapping of system’s functionality ⚫

computational
onto hardware processors: ⚫ State ⚫ Sequ ⚫ Data- ⚫ Concur
rent
model(s) is
based on
mach ent. flow
captured using computational
⚫ ⚫

− ine ⚫ progr ⚫ proces whether it

am ses allows the
model(s) ⚫

⚫ ⚫ designer to
− written in some language(s) describe the
system.
⚫ Implementation choice
independent from language(s) ⚫ The choice of
language(s) is
choice ⚫ Pasc ⚫ C/C+ ⚫ Java ⚫ VHD based on
al + L whether it
Implementation choice based on
⚫

⚫ ⚫ ⚫ ⚫
captures the
power, size, performance, timing computational
model(s) used
and cost requirements by the
designer.
⚫ Final implementation tested for
The choice of
feasibility ⚫

implementation
− Also serves as is based on
whether it
blueprint/prototype for mass ⚫ Implementati
on A
⚫ Implementati
on
⚫ Implementati
on
meets power,
size,
manufacturing of final product ⚫ ⚫ B ⚫ C
performance
⚫ ⚫
and cost
requirements.
 Concurrent process model:
implementation
⚫ Process

Communication
⚫ Can use single and/or general-purpose ⚫ Proc
or A
Process
processors
⚫
ess1
⚫ Proc or B
ess2
⚫ (a) Multiple processors, each executing one ⚫ ( Proc ⚫ Process

Bus
⚫

a ess3 or C
process ) ⚫ Proc
ess4
⚫ Process
or D
True multitasking (parallel processing)

⚫
−
− General-purpose processors
⚫ Use programming language like C and compile to ⚫ Proc
instructions of processor ⚫
ess1
Proc ⚫

⚫ Expensive and in most cases not necessary ess2 ⚫ General Purpose

( Proc Processor
Custom single-purpose processors
⚫

−
⚫

b ess3
Proc
More common
⚫
⚫ ) ess4
⚫ (b) One general-purpose processor running all
processes
− Most processes don’t use 100% of processor ⚫ Process

Communication
or A
time ⚫ Proc
ess1
Can share processor time and still achieve
⚫
− ⚫ Proc ⚫ General
( ess2
necessary execution rates ⚫
Proc Purpose

Bus
⚫
c ess3 Process
⚫ (c) Combination of (a) and (b) ) ⚫ Proc or
ess4
Multiple processes run on one general-purpose

⚫
−
⚫

processor while one or more processes run on

own single_purpose processor
Testing and Debugging Tools For
Embedded Systems
 Introduction
Why?
◼ Identify the problems associated with test case

execution for Embedded Systems

◼ To propose solutions for making embedded

testing more effective at revealing errors.
 Introduction...
Currently: Testing and Debugging of Embedded Real
Time Systems: A black art - ad hoc methods and
techniques.

- Ineffective and inadequate.

Huge costs associated with validation of embedded
applications.
Despite this, most difficult errors are discovered
extremely late in the testing process, making them even
more costly to repair.

Requirement: Formal methods, development of

architectural and software capabilities which support
testing and debugging with minimal intrusion on the
executing system. This is critical for testing Embedded applications.
Introduction...
• Testing: Executing a piece of software in order to reveal
errors-
• A substantial portion of the validation process include:
◼ Development of test procedures, generation and
execution of test cases.

◼ Debugging: This is concerned with locating and correcting

the cause of an error once it has been revealed.
◼ Developer must recreate exact execution scenario.
◼ Apply same instruction sequences
◼ All environmental variants must be accounted for.
 Introduction...
◼ Correct execution of embedded applications absolutely
critical.
◼ Testing and Debugging: Greatly restricted by embedded
systems, with constraints such as:
◼ Concurrent Designs

◼ Real-time constraints

◼ Embedded target environments

◼ Distributed hardware architectures

◼ Device control dependencies

◼ These restrict execution visibility and control.

◼ Target environment: grossly inadequate computing
resources.
 Embedded Software Testing
Embedded Software testing for embedded systems:4 basic
stages
-Module level testing
◼ -Integration testing
◼ -System testing
◼ -Hardware/Software Integration testing – This is unique to
embedded systems.

Techniques :
-Testing Concurrent Systems
-Non-intrusive testing
 Embedded Software Testing...
⚫ Concurrency increases the difficulty of s/w testing.
⚫ Unmanageably large set of legal execution sequences
that a concurrent program may take.
⚫ Subsequent execution could lead to different-yet correct
results.
⚫ Dealing with abstraction
⚫ Static and Dynamic testing
⚫ Non-intrusive testing
⚫ For host based- intrusion is acceptable.
⚫ Embedded applications have strict timing requirements.
Absolutely imperative that there is no intrusions on a test
execution.

Embedded tools: ROM/Bus monitors, Emulators

 Embedded Software Testing...
⚫ Most often it is best to keep as much testing as possible
on the host machine because:
− the embedded environment is not stable ( the
hardware is buggy).
− a richer set of debugging tools and capabilities
exist on the host system (i.e. file system, real-
time debugger, simulator, terminal, user I/O,
etc.).
− it is easier to create reproducible test
procedures and simulate “hazard” situations.
− the main algorithms and flow control can be
tested without dependencies on the underlying
hardware.
 Embedded Software Testing...

⚫ Embedded systems have critical issues/concerns

− Typically developed on custom h/w
configurations, each would require own set of
tools and techniques.
− Errors discovered during Hw/Sw integration
testing are most difficult of all. Often require
significant modifications to the s/w system.
− There are two environments: Host and the
Target. Target has little support for s/w
development tools.
 Problems with Embedded Testing

1. Expense of testing process - Little reuse, expensive custom

validation facilities required for every project. Retests extremely costly.
2. Level of functionality on target
Very little, hence a lot of effort to discover errors.
3. Late discovery of errors - s/w modified to rectify h/w
errors, delays error discovery.
4. Poor test selection criteria
Test case selection rarely on theoretical criteria
5. Potential use in advancing architectures
Little chance of current methods remaining applicable to
future architectures..
 Debugging...
⚫ Some effective techniques for testing embedded systems
include:
⚫ scaffolding - allows you to verify the overall correctness of
the program and “abstract” the hardware as working
properly.
⚫ event simulation – allows you to simulate program events
(i.e. timers, interrupts, etc.) to insure that responder
routines are executing properly.
⚫ scripting – provides a general way of testing program flow
and simulating hazard conditions.
⚫ real-time debugger/simulator – allows you to execute the
program on the host as if it were running on the
embedded system.
 Robustness Testing
Once the correctness of the system has been verified, its
robustness can be tested by:
◼ erroneous input – purposefully try to crash/disrup
system operation. Find the “what ifs” and try them out.
◼ overloading – determine conditions that are unlikely to

exist and subject your code to them. Does the system

respond gracefully?
◼ field-testing – put the system into its actua
environment and test it for some fixed length of time
(a.k.a. “burn-in” period).
◼ extension – place the system into an environment for

which it was not originally designed. Does the system

still function? If not, can the algorithms used be made
more general to handle this situation?
Source
Frank Vahid and Tony Givargis, Embedded System Design–A Unified
Hardware/Software Introduction, John Wiley and Sons, Inc., MA, 2002.
 Thank You !
Questions, Comments ?