Máquinas de estados en C

Question

¿Cuál es la mejor forma de escribir una máquina de estados en C?
Normalmente escribo una gran declaración de mayúsculas y minúsculas en a para (;;), con devoluciones de llamadas para volver a ingresar a la máquina de estados cuando finaliza una operación externa.
¿Conoces una manera más eficiente?

Answer 1

Me gusta el enfoque Quantum Leaps.

El estado actual es un puntero a una función que toma un objeto de evento como argumento. Cuando ocurre un evento, solo llame a la función de estado con ese evento; La función puede hacer su trabajo y pasar a otro estado simplemente configurando el estado en otra función.

ej .:

// State type and variable, notice that it's a function pointer. 
typedef void (*State)(int); 
State state; 

// A couple of state functions. 
void state_xyz(int event) { /*...*/ } 
void state_init(int event) { 
    if (event == E_GO_TO_xyz) { 
     // State transition done simply by changing the state to another function. 
     state = state_xyz; 
    } 
} 

// main contains the event loop here: 
int main() { 
    int e; 
    // Initial state. 
    state = state_init; 
    // Receive event, dispatch it, repeat... No 'switch'! 
    while ((e = wait_for_event()) != E_END) { 
     state(e); 
    } 
    return 0; 
} 

Los marcos QL proporciona ayudantes de cosas adicionales como acciones de entrada/salida/init, máquinas de estados jerárquicos, etc. recomiendo encarecidamente the book para una explicación más profunda y la buena ejecución de este.

Answer 2

Ese es prácticamente el enfoque estándar. Si usted está interesado en el estudio de una biblioteca bien considerado y comparando detalles, echar un vistazo a Ragel:

Ragel compila máquinas de estados finitos ejecutables de los lenguajes regulares. Ragel apunta a C, C++, Objective-C, D, Java y Ruby. Las máquinas de estado Ragel no solo pueden reconocer secuencias de bytes como lo hacen las máquinas de expresión regular, sino que también pueden ejecutar código en puntos arbitrarios en el reconocimiento de un lenguaje normal. La incrustación de código se realiza utilizando operadores en línea que no interrumpen la sintaxis del lenguaje habitual.

Answer 3

La mejor manera es en gran medida subjetiva, pero una forma común es usar un enfoque "basado en tablas" donde se asignan códigos de estado (enumeraciones u otro tipo integral) a los punteros de función. La función devuelve su próximo estado y otros datos asociados y realiza un bucle hasta que se alcanza el estado del terminal. De hecho, esto podría ser lo que está describiendo como su enfoque anterior.

Answer 4

Un enfoque alternativo es una matriz 2D que describe, para cada combinación de estado/evento, las acciones que se ejecutarán y el siguiente estado al que se dirigirán. Esto puede ser más complicado de administrar cuando necesita hacer la transición a diferentes estados dependiendo de 'circunstancias', pero puede funcionar bien. Usted tiene una función de reconocimiento de eventos que devuelve el próximo evento; tiene la tabla en la que cada entrada de la tabla identifica la función para llamar al recibir el evento y el siguiente estado al que debe dirigirse, a menos que la función llamada anule ese estado.

En realidad, la generación de dicho código es más antigua, depende de cómo se describa el FSM en primer lugar. Detectar acciones duplicadas a menudo es importante. A menudo, puede confiar en las técnicas de "matriz dispersa" que no registran el manejo de errores explícitamente: si la entrada existe lógicamente en la matriz dispersa, actúa sobre esa información de evento/estado, pero si la entrada no existe, recurra a la información apropiada informe de errores y código de resincronización.

Una matriz 2D de punteros a estructuras se puede pasar a una función FSM genérica; el hecho de que escriba un triple puntero es suficiente para que tenga cuidado con lo que está sucediendo. (Escribí uno de ellos en marzo de 1986; ya no tengo la fuente para eso en el disco, aunque todavía tengo una copia impresa del documento que lo describió).

Answer 5

Las declaraciones de cambio son una buena manera para comenzar, pero tienden a ser difíciles de manejar cuando la FSM se hace más grande.

Un par relacionado (o duplicada) SO preguntas con gran información e ideas:

• state machines tutorials
• C state-machine design

Answer 6

que utilizan este patrón. Is there a typical state machine implementation pattern? (marque la respuesta correcta).

Pero también agrego algunas características
1. Información sobre el estado anterior.
2. Parámetro que pasa
3. Adición de eventos externos como el tiempo de espera global y "SM resseting"

me encontré con máquinas de estado poco menos críptica y fácil de mantener.
De todos modos, sigo pensando que las máquinas de estados son tarea de programación más difícil y molesto (que tengo hasta ahora)

Answer 7

un vistazo aquí:. http://code.google.com/p/fwprofile/

Es una versión de código abierto (GNU GPLv3) de la máquina de estados implementado en C. El concepto y la implementación son adecuados para usar en las aplicaciones de misión crítica . Hay implementaciones en aplicaciones industriales .

Answer 8

Utilizo punteros de función y una tabla de búsqueda 2D donde utilizo el estado de un parámetro y el evento como el otro.

Utilizo excel (o cualquier herramienta de hoja de cálculo) para asignar una función a cada combinación de estado/evento.

Cuando ocurre un evento, I Que hacia arriba, por lo que entonces tengo algo que se parece a esto

int main(void) 
{ 
    StateList currentState = start_up; 
    EventList currentEvent; 

    uint8_t stateArray[STATE_COUNT][EVENT_COUNT]; 

    InitializeStateArray(stateArray); 
    InitializeEventQue(); 

    while(1) 
    { 
     currentEvent = GetPriorityEvent(); 
     currentState = (StateList)(*(stateArray[currentState][currentEvent]))(); 
    } 
    return 1; //should never get here 
} 

Este método fuerza esencialmente el desarrollador de considerar todos los eventos posibles en cada estado, y en mi experiencia hace la depuración es un poco más fácil.