Máquina de Estados em C

- por Sergio Prado

Categorias: Linguagem C Tags: ,

Desenvolvedor de software é um ser muito ansioso. Quer logo colocar a mão na massa. E depois de 2.000 linhas de código ele resolve começar os testes. O código nem compila. E quando ele se prepara para corrigir o problema, percebe que o código está um caos total. Funções com mais de 200 linhas e mais de 5 if’s aninhados. O que parecia ser fácil no começo (e poderia ter sido) já não é mais. Tudo porque ele não tinha um plano. Nunca comece nada sem um plano, principalmente quando se trata de desenvolvimento de software. E uma boa estratégica é o uso de design patterns.

Design patterns, ou padrões de projeto, são soluções para problemas normalmente encontrados em projetos de software. São independentes de linguagem, e oferecem uma descrição ou template de como resolver determinado problema. Um design pattern muito conhecido e utilizado no desenvolvimento de software para sistemas embarcados é a Máquina De Estados Finita, ou Finite State Machine (FSM), a qual chamaremos aqui apenas de máquina de estados.

Mas qual o problema que este design pattern pretende resolver?

Muitos dos dispositivos usados em sistemas embarcados, principalmente os de automação e controle, são dispositivos passivos. Respondem a determinadas ações do ambiente. E a saída gerada por estas ações são dependentes de seu estado atual. É exatamente aí que entra a implementação deste design pattern: qualquer dispositivo, físico ou conceitual, que possue um conjunto finito de estados e aceita um finito numero de entradas, pode produzir um finito numero de diferentes saidas. Este dispositivo deve ter uma memória que possa armazenar a sequencia de entradas recebidas, de forma que a saida seja dependente destas entradas.

OK, está um pouco confuso, não é? Vamos então tentar analisar um caso prático.

A entrada de um típico sistema de automação de estacionamentos é composta pelos seguintes elementos: um emissor de tickets, uma cancela e um ou mais loops de detecção de veículos. O loop é um sensor de chapa metálica localizado no chão e utilizado para identificar o veiculo. Para o nosso exemplo existem dois loops, um em frente ao emissor de tickets (loop A) e outro abaixo da cancela (loop B).

As seguintes ações são realizadas na entrada de um veículo:

  1. O usuário posiciona o veículo em frente ao emissor de tickets, o loop A será acionado e uma mensagem “Pressione o botão” é emitida.
  2. O usuário pressiona o botão para emitir o ticket, o sistema realiza a emissão e levanta a cancela.
  3. O usuario passa pela cancela (loop B) e entra no estacionamento. O sistema aguarda e abaixa a cancela.

Pelas ações listadas acima, podemos identificar basicamente os estados abaixo, na ordem em que são executados:

  1. Aguardando veículo no loop A.
  2. Aguardando usuário pressionar o botão para emitir ticket.
  3. Aguardando veiculo sair do loop A.
  4. Aguardando veiculo passar pelo loop B.

O importante aqui é perceber que, para qualquer um dos estados acima, dependendo da entrada, a saida será diferente. Por exemplo, se você esta no estado 2 e recebe como entrada o botão pressionado você vai para o estado 3. Porém, se ao invés do botão pressionado você receber como entrada a saida de veiculo do loop A (usuário deu ré e desistiu de estacionar), você deve voltar para o estado 1.

Este é um exemplo simples de aplicação onde cabe perfeitamente a implementação de uma máquina de estados. Além desta, existem muitas outras aplicações, como por exemplo interpretadores de comando, processadores de linguagem, tratamento de protocolos de comunicação, etc.

Agora que conhecemos um pouco da teoria, vamos à prática.

Implementação

Um problema que resolvo frequentemente com máquina de estados são rotinas de tratamento de protocolos de comunicação.

No nosso exemplo, o protocolo de comunicação tem o seguinte formato:

|STX|QTD_DADOS|DADOS|CHK|ETX|
 
STX       (1 Byte)  -> Inicio da transmissão (0x02)
QTD_DADOS (1 Byte)  -> Quantidade de dados
DADOS     (N Bytes) -> Dados
CHK       (1 Byte)  -> Checksum da transmissão
ETX       (1 Byte)  -> Fim da transmissão (0x03)

Vamos implementar aqui dois modelos diferentes, um com switch/case e outro com ponteiro para função.

Implementação 1: Switch/case

Esta implementação é simples e composta de apenas uma função, listada abaixo:

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
/* possiveis estados */
typedef enum {
    ST_STX = 0, ST_QTD, ST_DATA, ST_CHK, ST_ETX
} States;
 
/* maquina de estados */
void handleRx(unsigned char *data, int qtd)
{
    static States state = ST_STX;
    static unsigned char buffer[MAX_BUFFER];
    static int indBuffer = 0, qtdBuffer = 0;
    static unsigned char chkBuffer = 0;
    int i;
 
    for (i = 0; i < qtd; i++) {
 
        switch (state) {
 
            case ST_STX:
                if (data[i] == STX) {
                    indBuffer = qtdBuffer = 0;
                    chkBuffer = 0;
                    state = ST_QTD;
                }
                break;
 
            case ST_QTD:
                qtdBuffer = data[i];
                state = ST_DATA;
                break;
 
            case ST_DATA:
                buffer[indBuffer++] = data[i];
                chkBuffer ^= data[i];
                if (--qtdBuffer == 0) {
                    state = ST_CHK;
                }
                break;
 
            case ST_CHK:
                if (data[i] == chkBuffer) {
                    state = ST_ETX;
                }
                else {
                    state = ST_STX;
                }
                break;
 
            case ST_ETX:
                if (data[i] == ETX) {
                    handlePackage(buffer, indBuffer);
                }
                state = ST_STX;
                break;
        }
    }
}

O uso da máquina de estados é simples. Basta chamar a função handleRx() para cada stream recebido do buffer de comunicação. Veja que ela possui algumas variáveis static para que seja possivel armazenar seu estado atual.

A principal deficiência desta solução é que a função pode ficar grande e complexa demais dependendo da quantidade de estados. A melhor forma de resolver este problema é implementar usando ponteiros para função.

Implementação 2: Ponteiros de função

Nesta forma de implementação da máquina de estados, cada ação é implementada através de uma função. Veja um trecho da implementação abaixo:

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
/* possiveis estados */
typedef enum {
    ST_STX = 0, ST_QTD, ST_DATA, ST_CHK, ST_ETX
} States;
 
struct StateMachine {
    States state;
    unsigned char buffer[MAX_BUFFER];
    unsigned char chkBuffer;
    int indBuffer;
    int qtdBuffer;
    Action action[5];
} sm;
 
void stSTX(unsigned char data)
{
    if (data == STX) {
        sm.indBuffer = sm.qtdBuffer = 0;
        sm.chkBuffer = 0;
        sm.state = ST_QTD;
    }
}
 
void stQtd(unsigned char data)
{
    sm.qtdBuffer = data;
    sm.state = ST_DATA;
}
 
void stData(unsigned char data)
{
    sm.buffer[sm.indBuffer++] = data;
    sm.chkBuffer ^= data;
    if (--sm.qtdBuffer == 0) {
        sm.state = ST_CHK;
    }
}
 
void stChk(unsigned char data)
{
    if (data == sm.chkBuffer) {
        sm.state = ST_ETX;
    }
    else {
        sm.state = ST_STX;
    }
}
 
void stETX(unsigned char data)
{
    if (data == ETX) {
        handlePackage(sm.buffer, sm.indBuffer);
    }
    sm.state = ST_STX;
}
 
void handleRx(unsigned char *data, int qtd)
{
    int i;
 
    for (i = 0; i < qtd; i++)
        sm.action[sm.state](data[i]);
}

A forma de usar a máquina de estados continua a mesma. Basta chamar a função handleRx() para cada stream recebido do buffer de comunicação. Mas veja que a função diminuiu para apenas 2 linhas! O estado atual da máquina de estados fica armazenado na estrutura StateMachine. E cada trecho de código dentro de um case, no exemplo anterior, se transformou em uma função neste exemplo. O código ficou muito mais modular e de fácil manutenção.

Espero que estes dois exemplos tenham ajudado vocês a entender o mecanismo de implementação de uma máquina de estados e como esse design pattern pode ser útil no nosso dia-a-dia. Se vocês tiverem alguma outra sugestão de implementação de máquinas de estado, deixem seus comentários.

Um abraço a todos,

Sergio Prado

Faça um Comentário

Navegue
Creative Commons Este trabalho de Sergio Prado é licenciado pelo
Creative Commons BY-NC-SA 3.0.