Che materia stai cercando?

State Machines Appunti scolastici Premium

Describing embedded system’s processing behavior can be extremely difficult. Common computation models are sequential program model, communicating process model, state machine model, dataflow model, object-oriented model. We might consider a Finite-state machine (FSM)... Vedi di più

Esame di Sistemi embedded docente Prof. L. Pomante

Anteprima

ESTRATTO DOCUMENTO

Embedded Systems Design: A Unified

Hardware/Software Introduction

Chapter 8: State Machine and

Concurrent Process Model 1

Outline

• Models vs. Languages

• State Machine Model

– FSM/FSMD

– HCFSM and Statecharts Language

– Program-State Machine (PSM) Model

• Dataflow Model

• Concurrent Process Model

– Communication

– Synchronization

– Implementation

Embedded Systems Design: A Unified 2

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

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...

Embedded Systems Design: A Unified 3

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

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

Embedded Systems Design: A Unified 4

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

Models vs. languages

Poetry Recipe Story State Sequent. Data-

Models machine program flow

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 models

Embedded Systems Design: A Unified 5

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

Text versus Graphics

• Models versus languages not to be confused with text

versus graphics

– Text and graphics are just two types of languages

• Text: letters, numbers

• Graphics: circles, arrows (plus some letters, numbers)

X = 1

X = 1;

Y = X + 1; Y = X + 1

Embedded Systems Design: A Unified 6

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

Introductory example: An elevator controller

System interface

Partial English description

• Simple elevator up

“Move the elevator either up or down Unit

Control

controller to reach the requested floor. Once at down

the requested floor, open the door for open

at least 10 seconds, and keep it open

– Request Resolver floor

until the requested floor changes.

resolves various floor req

Ensure the door is never open while

moving. Don’t change directions Request

requests into single Resolver

unless there are no higher requests buttons

b1 inside

when moving up or no lower requests

requested floor b2

... elevator

when moving down…” bN

– Unit Control moves up1 up/down

up2 buttons

elevator to this requested on each

dn2

up3 floor

floor dn3

...

• Try capturing in C... dnN

Embedded Systems Design: A Unified 7

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

Elevator controller using a sequential

program model System interface

Sequential program model Partial English description

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

Unit

Outputs: bit up, down, open; Control

“Move the elevator either up or down

Global variables: int req; down

to reach the requested floor. Once at

void UnitControl() void RequestResolver() open

the requested floor, open the door for

{ {

up = down = 0; open = 1; while (1) floor

at least 10 seconds, and keep it open

while (1) { ... req

until the requested floor changes.

while (req == floor); req = ... Ensure the door is never open while

open = 0; ... Request

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

moving. Don’t change directions buttons

b1

else {down = 1;} void main() unless there are no higher requests inside

while (req != floor); b2

...

{ elevator

when moving up or no lower requests

up = down = 0; Call concurrently: bN

open = 1; when moving down…”

UnitControl() and

delay(10); RequestResolver() up1 up/down

} } up2 buttons

} on each

dn2

up3 floor

dn3

You might have come up with something having ...

even more if statements. dnN

Embedded Systems Design: A Unified 8

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

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...

Embedded Systems Design: A Unified 9

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

Finite-state machine (FSM) model

UnitControl process using a state machine

req > floor

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

GoingUp timer < 10

req > floor !(timer < 10)

u,d,o,t = 0,0,1,0 Idle DoorOpen u,d,o,t = 0,0,1,1

req == floor 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

Embedded Systems Design: A Unified 10

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

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)

Embedded Systems Design: A Unified 11

Hardware/Software Introduction, (c) 2000 Vahid/Givargis

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...

Embedded Systems Design: A Unified 12

Hardware/Software Introduction, (c) 2000 Vahid/Givargis


PAGINE

27

PESO

177.02 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

Describing embedded system’s processing behavior can be extremely difficult. Common computation models are sequential program model, communicating process model, state machine model, dataflow model, object-oriented model. We might consider a Finite-state machine (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).


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria delle telecomunicazioni
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Sistemi embedded e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Pomante Luigi.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Sistemi embedded

Programmazione concorrente
Dispensa
Sistemi Embedded
Dispensa
SystemC
Dispensa
Real-time and embedded operating systems
Dispensa