https://www.embarcados.com.br/maquina-de-estado/

Máquina de estado

ÍNDICE DE CONTEÚDO

Este artigo visa explicar os conceitos e algumas aplicações práticas de uma máquina de estado.

Pré-requisitos

Para uma boa compreensão deste artigo, existem os seguintes pré-requisitos de conhecimento em linguagem C:

Uso de switch/case;
Construção e uso de funções;
Construção e uso de macros / defines.

Máquina de estado: o que é?

No desenvolvimento de software (seja ele embarcado ou não), frequentemente nos deparamos com situações em que é necessário que uma certa seqüência de comandos / ações / dados seja obedecida para o software poder agir / tomar uma decisão. Um exemplo disto seria a recepção de dados via um canal serial, onde é necessário que o buffer tenha sido recebido no formato correto antes de seu tratamento. Para resolver estas questões de forma computacionalmente satisfatória, existe o conceito de máquina de estado.

Uma máquina de estado se fundamenta, como o próprio nome diz, em direcionar o funcionamento de um software em um número finito de estados, sendo cada um desses estados uma situação relevante do sistema. É possível avançar, recuar ou permanecer em um estado, e o mecanismo deste fluxo da máquina de estado é definido pelo desenvolvedor e sua complexidade é tão grande quanto a complexidade do sistema desenvolvido.

Logo, utilizar máquina de estado é direcionar o funcionamento de um software, fazendo com que uma ordem de execução seja obedecida. Ah, é muito importante ressaltar: somente um estado é executado por vez (não é correto, nem possível, que uma máquina de estado esteja em dois estados simultaneamente).

Parece complexo, não? Nada como um código-exemplo para esclarecer

No geral, conclui-se que a máquina de estado tem como fundamento assegurar uma seqüência de execução de um programa. Ok, máquina de estado realmente é um recurso poderoso, mas quais seriam as formas de implementá-la em linguagem C?

Primeiramente, uma máquina de estado deve, obrigatoriamente, ter um estado inicial. Afinal, se é necessário que uma sequência de execução seja obedecida, deve haver um começo.

Para implementar uma máquina de estado em linguagem C há duas formas: via switch/case e via ponteiro de função. Ambas as formas são válidas, porém a necessidade / problema a ser resolvido vai dar pistas de qual delas é a melhor solução. Veremos em detalhes cada uma delas.

a) Via switch/case:

Trata-se da forma mais utilizada para implementar máquinas de estado, pois trata-se da forma mais simples e intuitiva para isso. Nela, há uma variável de controle (responsável por armazenar o estado atual) e cada case corresponde a um estado diferente. É importante ressaltar que a variável de controle de um switch/case deve, obrigatoriamente, ser do tipo caractere ou numérico sem ponto flutuante (long ou int).

Para maior facilidade e rapidez de leitura e compreensão de código, costuma-se ter os estados representados em macros/defines. Assim, pode-se ter uma palavra ou frase representando um estado (numérico, devido ao tipo da variável de controle do switch/case). Isto facilita muito a leitura e, em tempo de compilação, esta representação é substituída pelos números correspondentes, não exigindo então esforço computacional adicional nenhum em tempo de execução.

Segue abaixo um exemplo de aplicação desta máquina de estado. Neste exemplo, é criada uma máquina de estado que busca que o usuário digite a sequência “abcd” no teclado. Ao fazer a sequência correta, a mensagem “OK” é exibida (mecanismo semelhante a sistemas que aceitam comandos textuais, como comandos AT, por exemplo). Se qualquer letra for digitada fora da ordem desejada, volta-se ao estado inicial (aguardar a letra ‘a’) novamente. O programa foi elaborado no Dev-Cpp versão 4.9.9.2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <stdlib.h>
 
#define ESTADO_INICIAL 0           //define que representa o estado inicial
#define ESTADO_DIGITOU_LETRA_A 1   //define que representa o estado no qual a letra 'a' foi digitada
#define ESTADO_DIGITOU_LETRA_B 2   //define que representa o estado no qual a letra 'b' foi digitada
#define ESTADO_DIGITOU_LETRA_C 3   //define que representa o estado no qual a letra 'c' foi digitada
 
//variaveis globais:
volatile char ControleMaquinaEstado;  //variável responsável por armazenar o estado atual da máquina de estados
 
//prototypes:
void ExecutaMaquinaDeEstados(void);   //função que contém o switch/case com a máquina de estados
 
//função de execução da máquina de estados via switch/case
void ExecutaMaquinaDeEstados(void)
{
  char TeclaLida;
  //faz a leitura da tecla pressionada
  fflush(stdin); //limpa o buffer de teclado
 
  TeclaLida = getche();
 
  //executa a máquina de estados
  switch(ControleMaquinaEstado)
  {
    case ESTADO_INICIAL:
    {
      //somente muda de estado se for digitada a letra 'a'
      if (TeclaLida == 'a')
        ControleMaquinaEstado = ESTADO_DIGITOU_LETRA_A;
      else
        printf("\n\n- Caracter esperado: a. Permanece no estado inicial\n\n"); 
      break; 
    }
 
    case ESTADO_DIGITOU_LETRA_A:
    {
      //Vai para proximo estado se for digitada a letra 'b'. Caso contrario, volta ao estado inicial (aguardar letra 'a')
      if (TeclaLida == 'b')
        ControleMaquinaEstado = ESTADO_DIGITOU_LETRA_B;
      else
      {
        printf("\n\n- Caracter esperado: b. Caracter lido: %c. Voltando ao estado inicial\n\n",TeclaLida);
        ControleMaquinaEstado = ESTADO_INICIAL;
      }
      break; 
    }
 
    case ESTADO_DIGITOU_LETRA_B:
    {
      //Vai para proximo estado se for digitada a letra 'c'. Caso contrario, volta ao estado inicial (aguardar letra 'a')
      if (TeclaLida == 'c')
        ControleMaquinaEstado = ESTADO_DIGITOU_LETRA_C;
      else
      {
        printf("\n\n- Caracter esperado: c. Caracter lido: %c. Voltando ao estado inicial\n\n",TeclaLida);
        ControleMaquinaEstado = ESTADO_INICIAL;
      }
      break; 
    }
 
    case ESTADO_DIGITOU_LETRA_C:
    {
      //Valida seqüência se se for digitada a letra 'd'. Caso contrario, volta ao estado inicial (aguardar letra 'a')
      if (TeclaLida != 'd')
        printf("\n\n- Caracter esperado: d. Caracter lido: %c. Voltando ao estado inicial\n\n",TeclaLida);
      else
        printf("OK\n\n"); //a seqüência de letras digitada é correta. Escreve "OK" na tela e volta ao estado inicial
 
      ControleMaquinaEstado = ESTADO_INICIAL;
      break; 
    } 
  }
}
 
//programa principal
int main(int argc, char *argv[])
{
  ControleMaquinaEstado = ESTADO_INICIAL; //estado inicial da variável de estado (Nunca esquecer de definir um estado inicial em uma máquina de estados!!!)
 
  while(1)
  {
    ExecutaMaquinaDeEstados();    //executa "para sempre" a máquina de estados
  }
 
  system("PAUSE"); 
  return 0;
}

Importante: Pelo fato da variável de controle da máquina de estado (ou switch/case) ser fundamental no andamento dos estados, esta deve ser global. Logo, deve-se ter cuidado redobrado com a integridade desta variável (nada deverá modificar seu valor, caso contrário o funcionamento do software será seriamente comprometido).

b) Via ponteiro de função

Nesta forma de se fazer máquina de estado, cada estado será representado por uma função, sendo que estas são chamadas através de uma atribuição de ponteiro de função (que aponta sempre para a função/estado que deve ser executado no momento). Ou seja, ao invés de se utilizar uma variável de controle para se orientar pelos estados, utiliza-se um ponteiro de função e chamadas do mesmo.

As vantagens deste tipo de metodologia de máquina de estado são:

chamada da execução da máquina em apenas uma linha de código;
maior modularização e;
por fim, mas não menos importante, contribui para um código mais limpo (fácil leitura).

Vejamos o mesmo exemplo anterior utilizando uma máquina de estado por ponteiro de função:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <stdlib.h>
 
 
//variaveis globais:
void (*PonteiroDeFuncao)(); //ponteiro de função da máquina de estados. Ele aponta sempre para a função da máquina de estados que deve ser executada
 
//prototypes:
void EstadoInicial(void);       //função que representa o estado inicial da máquina de estados
void CaracterDigitadoA(void);   //função que representa o estado ao qual já foi digitada a letra 'a'
void CaracterDigitadoB(void);   //função que representa o estado ao qual já foi digitada a letra 'b'
void CaracterDigitadoC(void);   //função que representa o estado ao qual já foi digitada a letra 'c'
 
//Estado inicial da máquina de estados. Somente muda de estado se for digitada a letra 'a'
void EstadoInicial(void)
{
  char TeclaLida;
  //faz a leitura da tecla pressionada
  fflush(stdin); //limpa o buffer de teclado
  TeclaLida = getche();
 
  if (TeclaLida == 'a')
    PonteiroDeFuncao = CaracterDigitadoA;
  else 
    printf("\n\n- Caracter esperado: a. Permanece no estado inicial\n\n"); 
}
 
//Vai para proximo estado se for digitada a letra 'b'. Caso contrario, volta ao estado inicial (aguardar letra 'a')
void CaracterDigitadoA(void)
{
  char TeclaLida;
  //faz a leitura da tecla pressionada
  fflush(stdin); //limpa o buffer de teclado
  TeclaLida = getche();
 
  if (TeclaLida == 'b')
    PonteiroDeFuncao = CaracterDigitadoB;
  else
  {
    printf("\n\n- Caracter esperado: b. Caracter lido: %c. Voltando ao estado inicial\n\n",TeclaLida);
    PonteiroDeFuncao = EstadoInicial;
  }
}
 
//Vai para proximo estado se for digitada a letra 'c'. Caso contrario, volta ao estado inicial (aguardar letra 'a')
void CaracterDigitadoB(void)
{
  char TeclaLida;
  //faz a leitura da tecla pressionada
  fflush(stdin); //limpa o buffer de teclado
  TeclaLida = getche(); 
 
  if (TeclaLida == 'c')
    PonteiroDeFuncao = CaracterDigitadoC;
  else
  {
    printf("\n\n- Caracter esperado: c. Caracter lido: %c. Voltando ao estado inicial\n\n",TeclaLida);
    PonteiroDeFuncao = EstadoInicial;
  } 
}
 
//Valida seqüência se se for digitada a letra 'd'. Caso contrario, volta ao estado inicial (aguardar letra 'a')
void CaracterDigitadoC(void)
{
  char TeclaLida;
  //faz a leitura da tecla pressionada
  fflush(stdin); //limpa o buffer de teclado
  TeclaLida = getche(); 
 
  if (TeclaLida != 'd')
    printf("\n\n- Caracter esperado: d. Caracter lido: %c. Voltando ao estado inicial\n\n",TeclaLida);
  else
    printf("OK\n\n"); //a seqüência de letras digitada é correta. Escreve "OK" na tela e volta ao estado inicial
 
  PonteiroDeFuncao = EstadoInicial;
}
 
 
int main(int argc, char *argv[])
{
  PonteiroDeFuncao = EstadoInicial; //aponta para o estado inicial. Nunca esquecer de informar um estado inicial (senão, nesse caso em específico, pode haver um erro fatal / hard fault).
 
  while(1)
  {
    (*PonteiroDeFuncao)();    //chama a função apontada pelo ponteiro de função (logo, chama o estado corrente)
  }
  system("PAUSE"); 
  return 0;
}

Este tipo de máquina de estado, pela clareza de código, é muito utilizado em sistemas embarcados.

Boas práticas, dicas e truques

Vimos que máquinas de estado são recursos muito bons em se tratando de organização e garantia de funcionamento de software. Porém, há algumas boas práticas, dicas e truques no seu uso:

Em máquina de estado via switch/case, uma boa prática é a variável de controle ser volatile (sobretudo quando se fala de sistemas embarcados compilados com alto grau de otimização). Não se deve correr risco algum na atualização desta variável;
Ainda em máquina de estado via switch/case, quando aplicada em sistemas complexos (com muitos estados), é uma boa prática colocar um estado default (o default do switch/case). Isso é uma boa prática pois, caso haja o corrompimento da variável de controle (ou até mesmo um bug no software quanto ao gerenciamento desta variável), o software poderá se restabelecer (e não ficar “perdido em um estado” por muito tempo ou pra sempre);
Em máquinas de estado via ponteiro de função, deve-se priorizar uso de variáveis locais. Devido ao fato de o número de estados / funções poder ser grande, se as variáveis forem declaradas como globais será alocada desnecessariamente uma quantidade significativa de memória RAM, algo ruim em sistemas embarcados com microcontroladores com pouca memória desse tipo. Aliás, evite sempre muitas variáveis globais, isso só gera dor de cabeça!;
E o mais importante: quando for planejar sua máquina de estado, seja SIMPLES! Evite ao máximo utilizar numerosos estados e/ou máquinas de estado a perder de vista. Em software embarcado, quanto mais simples for para entender e debugar, melhor.

Conclusão

Um software, seja embarcado ou não, necessita muitas vezes que uma determinada ordem de acontecimentos seja obedecida, e aí entra o conceito de máquina de estado. Trata-se de um recurso muito poderoso e que garante o correto funcionamento de softwares simples ou complexos.

Referências

Post do Sérgio Prado sobre máquinas de estado: http://sergioprado.org/maquina-de-estados-em-c/
Conteúdo sobre ponteiros de função: http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node144.html
Figura destacada obtida de: http://ces22.wdfiles.com/local–files/relas%3Alab3-francisco-germano/MotorFoguete2.jpg
Para mais detalhes sobre máquinas de estados finitos (FSM), acesse o site: http://users.ece.utexas.edu/~valvano/Volume1/E-Book/C10_FiniteStateMachines.htm

Diseño Electrónico

martes, 10 de mayo de 2022

Máquina de estado con Switch Case, y con Punteros