Printer Friendly

The design of a finite state machine engine with safe operation used in embedded systems design.

1. INTRODUCTION

Finite state machines are a model largely used for embedded software design and development processes. Finite state machines allow for an abstract representation of systems behavior using state charts, are easy to understand by many people with different backgrounds and do not require any prior knowledge of a specific programming language (Harel, 2009). The custom implementation of finite state machines consumes time and is prone to error. A better approach is to design an abstract engine (kernel or core) that runs a finite state machine based on an appropriate description. By using an engine, an embedded designer would have only to specify the actions, checks and transitions in terms of simple functions and tables and let the engine to take care of all the housekeeping work needed to run the finite state machine. In (Stan, 2009) such an engine is built and evaluated taking into consideration the execution time and the memory size of the implementation. Other approach can be found in (Sukittanon, 2006).

This paper continues the previous work by modifying the finite state machine model in order to provide additional support for implementing a safety mechanism. Safe operation is a special issue in complex embedded systems. In order to achieve a high level of safety, one method is to provide a timeout for the inputs given to the system and for the outputs generated by the system. The proposed implementation of a finite sate machine includes a timeout for every state. This fact prevents the finite state machine to indefinitely wait for a condition to trigger a state transition and consequently to keep outputs active longer than is safe or needed.

The implementation must be efficient in terms of memory footprint and execution time.

2. IMPLEMENTATION

The translation of a finite state machine diagram into C source code is a simple process if a specific template is used. In this article we propose such a template (abstract engine) that is implemented as a library of functions using C programming language. The C language is a well known and mature programming language and is widely used for embedded systems programming.

The proposed model for a safe finite state machine engine is defined by states, events or conditions that trigger transitions between states, action functions that activates or deactivate outputs, and timeout values for each state.
Fig. 1. State structure type

// function pointer type--for action (output) functions
typedef void (*FSME_PF) (void);
// function pointer type--for transition checking
typedef uint8 (*FSME_PF) (void);
// state type--describes a FSM state using the following fields:
// Action--a pointer to an action (output) function
// Event--a pointer to function that checks the conditions that
may trigger a transition from the current state;
// TimeOut--the maximum ammount of time that the FSM is
allowed to stay in the current state
typedef struct {
 FSME_PF Action;
 FSME_PF_EV Event;
 uint16 TimeOut;
} FSME_STATE;


Each state is described by the FSME_STATE structure type, presented in figure 1, which contains information about the action function, transitions from this state and a timeout value that limits the amount of time that the finite state machine may stay in the current state. The action function information is represented by a pointer to function, taking into account that this is a Moore model of a finite state machine.

The transitions from the current state are implemented by the Event member of the FSME_STATE structure. This member is a pointer to a function that checks all the events and conditions that may trigger a transition from current state. If a transition is triggered by the occurrence of an event or a true condition, then the Event function returns the code for the next state that the finite state machine will go to.

The specific structure type for the finite state machine model is FSME_FSM structure presented in figure 2. The structure holds data that describes an instance of a finite state machine that runs on an embedded system. It consists of a flag that indicates if the finite state machine is stopped or it is running, a flag that indicates a change in the state of the finite state machine and fields that hold the current state, the fail safe state in case of a timeout, a reference to an array that contains the states and an index to a timer used to check for the timeout.
Fig. 2. State machine structure

// FSM type--describes a FSM using the following fields:
// Enable--a flag that indicates the state of FSM
// StateChanged--flag that indicates a state change
// CurrentState--the current state of the FSM
// SafeState--the safe state of the FSM
// States--an array that contains the states of the FSM
// TimerIdx--the index of the software timer
typedef struct {
 uint8 Enable;
 uint8 StateChanged;
 uint8 CurrentState;
 uint8 SafeState;
 FSME_STATE * States;
 uint8 TimerIdx;
} FSMEFSM;


The main function of the proposed model for the finite state machine is presented in figure 3.
Fig. 3. FSME_Run function

void FSME_Run( FSMEFSM * F )
{
 uint8 _n;
 if ( FSMEDISABLE == F->Enable )
 {
 return;
 }
 _n = F->States[F->CurrentState ].Event();
 if (_n!= FSME_NO_STATE_CHANGE )
 {
 F->CurrentState = _n;
 F->StateChanged = FSME_STATE_CHANGED;
 timer_RestartTimer10ms( F->TimerIdx, F->States[ F-
 >CurrentState].TimeOut );
 }
 else if ( timer_CheckTimer10ms( F->TimerIdx ))
 {
 F->CurrentState= F->SafeState;
 F->StateChanged = FSME_STATE_CHANGED;
 timer_RestartTimer10ms( F->TimerIdx, F->States[ F-
 >CurrentState].TimeOut );
 }
 F->States[ F->CurrentState ].Action();
}


Every call to the FSME_Run function checks first if the finite state machine is enabled or not. If it is not enabled, the function simply returns. If it is enabled, the function FSME_Run checks further if the state changed by calling the Event function for the current state. If the state of the finite state machine has changed then the current state is updated accordingly and the timeout timer is reset to the value corresponding to the new state. If the state of the finite state machine remains unchanged, the FSME_Run function checks if the timeout for the current state has expired. If so, the finite state machine goes into the fail safe state. In this state a safe shutdown cycle may be initiated. At the end of the FSME_Run function it is called the Action function for the current state.

There are two auxiliary functions FSME_Disable that are used to individually enable and disable finite state machines in a multi FSM embedded system environment. In this way it is enabled the efficient design with multiple finite state machines, allowing, for example, the design of hierarchical state machines.

3. EVALUATION

In order to evaluate the proposed model for a finite state machine an environment was set up for this purpose. The evaluation environment is targeted to 8-bit embedded microcontrollers, specifically the ATMega family of microcontrollers from Atmel.

The evaluation environment uses the following components: a finite state machine module built using the proposed model, a C compiler for the ATMega microcontrollers - IAR Embedded Workbench, and the simulator integrated in the IAR IDE.

In order to evaluate the execution time of the finite state machine model, a basic script for the IAR simulator was developed. The script measures the number of cycles between successive calls of the function FSME_Run. The input sequence has values that activate all possible transitions of this finite state machine.

A sequence detector is implemented using the proposed model for a finite state machine. This type of sequential system is an abstraction for many practical problems that may be solved using the finite state machine approach.

[FIGURE 4 OMITTED]

The simulation script also computes the number of cycles necessary for each transition that occurred while running the simulation process. The number of cycles for each transition for the finite state machine is presented in table 1. This table may also be used to verify to correctness of the implementation.

The implemented library occupies only 156 bytes of code memory. For implementation of the sequence detector the memory usage is: 147 bytes of code memory (plus 156 bytes for the library) and 7 bytes of data memory.

4. CONCLUSIONS

By using the proposed model, all finite state machines from a design have uniform treatment. They are instances of the same structure type which abstracts and encapsulates the characteristics of a finite state machine. All finite state machines from a design share the common code for state update function, for running function and for action function calling. Only specific information must be specified and described for a finite state machine: states, transitions tables, condition check functions and action functions.

5. FURTHER WORK

The proposed further work is aimed at porting the C code to 16 bit and 32 bit microcontroller architectures: MSP430 or HCS12 for 16 bit and STM32 for 32 bit. An evaluation environment will be created in order to measure the performance.

The structure of the finite state machine may be altered to fit various application needs.

6. REFERENCES

Harel, D. (2009). Statecharts in the Making: A Personal Account, Communications of ACM, Vol. 52, No. 3, (03/2009), 67-75, ISSN 0001-0782

Stan, A.; Botezatu, N.; Panduru, L. & Lupu, R. G. (2009). The Design and Evaluation of a Finite State Machine Engine Used in Embedded Systems Design, Buletinul Institului Politehnic din Iasi, Tome LV, ISSN 1220-2169

Sukittanon, S. & Dame S. G. (2006). Algorithm--Embedded State Machine Design for PSoC using C Programming, AN2329, Cypress, http://www.cypress.com, Accessed on: 2009-07-01

*** (2009) http://www.atmel.com--ATMEL Corporation, ATMega16 8-bit Microcontroller Datasheet, Accessed on: 2009-07-01

*** (2009) http://www.iar.com--IAR Systems, AVR IAR C/C++ Compiler Reference Guide, Accessed on: 2009-0701
Tab. 1. The cycle count for the execution of FSME_Run

Current state / S0 S1 S2 S3 S4
Next state

S0 126 146 0 0 179
S1 147 0 146 0 0
S2 0 0 126 147 0
S3 147 146 0 0 0
S4 0 0 0 0 121
COPYRIGHT 2009 DAAAM International Vienna
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Stan, Andrei; Botezatu, Nicolae; Vieriu, George
Publication:Annals of DAAAM & Proceedings
Article Type:Report
Geographic Code:4EUAU
Date:Jan 1, 2009
Words:1636
Previous Article:Remote control of electrical appliances via power line 230V.
Next Article:Realization of reliable knives for mechanical cutting using modulated element cladded through welding.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters