Máquina de estado finito do sistema de negociação

Impacto Social da Engenharia.
Impacto Social da Engenharia.
Máquina de estados finitos acionada por eventos para um sistema comercial distribuído.
Um problema que tive ao criar meu sistema comercial distribuído é gerenciar estados de forma assíncrona a partir de vários gatilhos. Por exemplo, quando o mecanismo alfa diz comprar, ele precisa da confirmação do mecanismo de posição para ver se é seguro entrar em uma nova posição. Eu poderia encadear um cheque após o outro de forma imperativa ou via callbacks. No entanto, a restrição subjacente é que esses gatilhos:
são intensivos em recursos para gerar, podem precisar compor muitos deles, não sequenciais ou ter uma dependência individual e, o mais importante, estão em programas separados ou em máquinas diferentes.
Assim, optei por abstrair esse problema em seu próprio módulo do sistema como uma máquina de estados finitos (FSM) acionada por eventos para acompanhar as transições de estado. Termo intimidante, mas a minha primeira implementação foi apenas if-else declarações para se qualificar como tal. O benefício é que cada um dos componentes do meu sistema só precisa enviar sinais e puxar estados de uma interface central sem ter que se preocupar com o que deve chamar em seguida ou pesquisar qualquer outra coisa para ver se as estrelas estão alinhadas. Isso simplificou drasticamente o desenvolvimento e a manutenção.
As responsabilidades do meu módulo FSM são:
ouça todos os sinais, descubra todas as transições e publique os estados mais recentes para o resto do sistema.
Manipulando eventos assíncronos.
Eu uso o RabbitMQ como a camada de transporte de mensagens entre os módulos do meu sistema. Tudo o que preciso fazer aqui é associar um manipulador de mensagens apropriado a cada entrada de acionamento do FSM. Aqui está um exemplo dos manipuladores de eventos usando a biblioteca Clojure RabbitMQ, Langohr. O restante desta parte é apenas material padrão de publicação / assinatura do RabbitMQ.
Isso é chamado quando um evento de posição é recebido com informações como usuário, instrumento e quantidade. Esse manipulador iria encadear essas informações, buscando estados atuais para esse usuário, avaliar o próximo estado com entrada e, em seguida, armazenar em cache os novos estados para o usuário.
Transições de estado.
Abaixo está um dos diagramas de transição de estado do meu sistema.
Existem 4 estados representados por 4 cores com 4 triggers que sinalizam a transição de estado. Espera-se que o programa manipule até centenas de estados independentes concomitantemente com gatilhos de eventos que chegam em algumas vezes por segundo.
Como eu estava dizendo, minha primeira implementação é apenas um conjunto de métodos if-else. Por exemplo, um acionador de ativação chamaria o método de engate para determinar o próximo estado, dado o envolvimento implícito da entrada e o estado atual.
Havia um punhado desses códigos clichê. Então, depois que eu implantei meu sistema, voltei para refatorá-los. Eu estive querendo dar core. logic uma tentativa por um tempo, então isso parece ser um bom lugar para começar a usá-lo.
Antes de podermos fazer a pergunta do solucionador lógico, precisamos definir relações. Aqui eu defino uma relação de transição para especificar toda a definição de transição de estado convenientemente em um só lugar.
E os métodos manipuladores de eventos são apenas invólucros para uma expressão lógica de uma linha perguntando a questão - dado estágio atual, estado-final, e acionador de entrada, entrada, qual estado pode q tomar para satisfazer essa restrição?
Não é o exemplo mais ilustrativo de core. logic, mas faz o trabalho.
Começar com o core. logic é surpreendentemente fácil. Eu passei pelo Primer e tutorial e comecei a trabalhar em uma tentativa.
Estado de cache e compartilhamento.
Agora que a transição de estado foi resolvida, os estados são armazenados em cache e servidos no Redis para outras partes do sistema. Eu uso o Redis para isso porque é rápido e fácil. Os valores são armazenados no formato edn em vez de algo mais popular, como o JSON, para manter a estrutura de dados por meio do fio.
Esta é a primeira vez que uso o edn em produção. Todas as mensagens entre processos neste sistema de negociação são formatadas edn. Ele funciona perfeitamente com o Clojure simplesmente usando str para escrever e clojure. edn / read-string para leitura. Além dos meus outros componentes do Clojure no sistema, minha interface de corretor de negócios é escrita em Java. Meu programa Java usa o edn-java para analisar e unparar estruturas de dados complexas do Clojure (por exemplo, mapas aninhados com palavras-chave).
Acho que o acoplamento com Redis é uma escolha fantástica, pois é quase como trabalhar com estruturas de dados de concorrência nativa do Clojure, como o atom, mas também permitir que programas externos acessem os dados.
Simples e rápido
Todo o programa FSM orientado a eventos tem menos de 200 linhas de código Clojure e não levou mais do que algumas horas para fazer. No entanto, eu dei algum tempo ponderando por alguns dias. Eu não fiz nenhum benchmark para estimar o resultado do desempenho. Então, tudo o que posso dizer é que essa configuração pode lidar com meu caso de uso simplista com quase nenhuma carga no servidor, então estou feliz com isso.
Alguns anos atrás, eu teria definido um monte de bandeiras para mudar de estado. Na verdade, foi o que eu fiz. A maior satisfação aqui para mim não é a implementação ou tecnologias, é ver através do problema subjacente e resolvê-lo com um padrão comum que tornou o meu trabalho mais simples.

Máquinas de estado para negociação.
Uma máquina de estados finitos é um modelo de um sistema que mostra os diferentes estados possíveis que o sistema pode atingir e as transições que ocorrem à medida que o sistema se move de um estado para outro. Você pode usá-lo na modelagem do seu sistema de negociação.
Uma máquina de estado pode ser o mecanismo que você precisa para organizar seu modelo de mercado em um sistema vencedor. Vou explicar como funciona uma máquina de estados finitos (FSM) e mostrar um modelo para um sistema de negociação. Máquinas de estado podem ser facilmente criadas na maioria das linguagens de programação para automatizar suas decisões de negociação. Você também pode operar a estratégia manualmente, se desejar.
Máquinas de estado explicadas.
Uma máquina de estados finitos, também chamada de autômato finito, é um modelo de um sistema que mostra os diferentes estados possíveis que o sistema pode atingir e as transições que ocorrem à medida que o sistema se move de um estado para outro. Os FSMs são usados ​​por engenheiros para modelar sistemas de hardware e software. Eles também podem ser usados ​​para modelar seu sistema de negociação.
Um semáforo simples será usado para ilustrar os principais elementos de uma máquina de estados finitos. A Figura 1 ilustra o diagrama da máquina de estado do semáforo. Existem três estados válidos para a luz & # 8212; vermelho, amarelo e verde. A luz pode estar em apenas um desses estados a qualquer momento. Os estados são representados pelos círculos e as setas mostram as transições de um estado para o próximo. Os estados só podem passar de vermelho para verde, de verde para amarelo e de amarelo para vermelho.
Figura 1: Diagrama de estado do semáforo.
Um evento inicia um movimento do estado atual para um próximo estado válido. Para o nosso semáforo, definimos dois tipos de eventos que podem causar transições. O evento de transição mais comum ocorre após a luz estar acesa por um período especificado. A luz vermelha e a luz verde têm períodos de 30 segundos cada e a luz amarela tem um tempo de cinco segundos. Um temporizador registra quanto tempo uma luz está acesa e iniciará uma transição quando o período de tempo tiver passado.
Um segundo tipo de evento é definido pelo acionamento de um botão de faixa de pedestres. Se uma pessoa apertar o botão da faixa de pedestres enquanto a luz estiver vermelha e a luz estiver acesa por menos de 25 segundos, o cronômetro avançará para 25 segundos do tempo decorrido. Isso faz com que a transição de vermelho para verde ocorra mais cedo para permitir que o pedestre atravesse.
Este é um modelo muito simples que assume que o sistema está sendo executado eternamente, já que não há estado inicial ou estado de parada mencionado. O diagrama mostrado na Figura 1 não nos diz nada sobre os eventos que causam transições. O programa que implementa a máquina de estados finitos deve incluir as regras que acionam eventos. As regras podem ser simples, como mostrado, ou bastante complexas. A barra lateral, "Programação de uma máquina de estado" mostra como o semáforo pode ser implementado usando uma linguagem semelhante ao BASIC. Dê uma olhada no exemplo de código para ver como as regras são implementadas para mudar de um estado para outro.
Uma máquina de estado para negociação.
A Figura 2 ilustra um diagrama de uma máquina de estados finitos para um possível sistema de negociação. Um estado inicial e um estado de parada foram incluídos para representar a entrada de uma posição e a saída dela. Vamos percorrer o diagrama de estados para descrever os diferentes estados e os eventos que podem desencadear uma transição.
Figura 2: Diagrama de estado do sistema de negociação.
Esse sistema de negociação pressupõe que uma série de negociações começará por acionar uma ordem de compra. As transições entre estados são iniciadas pelas regras usadas para tomar decisões de investimento. Assumiremos que um conjunto de indicadores técnicos foi escolhido para ser avaliado em cada estado para decidir qual ação tomar. As regras normalmente seriam avaliadas sempre que recebêssemos um novo conjunto de dados. Um sistema diário seria avaliado com dados do final do dia. Se o sistema estiver conectado a uma fonte de dados em tempo real, as regras de estado atuais serão avaliadas com cada novo ponto de dados.
Um sistema diário seria avaliado com dados do final do dia. O design da máquina de estado incorpora em sua estrutura as dependências entre as regras para cada estado. As ações resultantes dependem não apenas do que os indicadores do sistema mostram, mas de onde o sistema está (ou seja, o estado atual). O sistema não precisa ser projetado para usar as mesmas regras ou indicadores em cada estado, portanto, as regras e os indicadores podem ser otimizados para cada estado. Essa combinação de flexibilidade e disciplina de negociação que pode ser programada na máquina de estado pode trazer poder para sua negociação.
Vamos usar um exemplo simples baseado em médias móveis. Um sinal para vender ocorre quando o preço de fechamento cai abaixo da média móvel. Um sinal para comprar ocorre quando o preço de fechamento cai acima da média móvel. Além disso, adicionaremos à posição se o preço cair novamente em 5% e, em seguida, recuperar sem penetrar na média móvel. Se você vendeu e o preço se recupera em 5% sem penetrar na média móvel, você pode usar isso como uma oportunidade para colocar um curto.
Suponha que você comece com uma decisão de negociar um determinado problema. Nesse modelo, a regra inicial aciona o evento que move o sistema para o estado de compra. A regra para o estado de compra é bem simples: faça uma compra e faça a transição para o estado de compra de compra. A compra é um estado transitório e o sistema passa para o estado de compra assim que a compra é concluída. O sistema pode permanecer no estado de espera de compra, desde que as regras não indiquem uma mudança para um novo estado.
As regras para um novo ponto de dados estipulam que nenhuma mudança no estado é exigida, desde que o preço de fechamento permaneça acima da média móvel. Isso é ilustrado pela seta de transição que retorna ao estado de compra.
À medida que observamos o mercado e mapeamos a média móvel, vemos a queda do preço de volta, mas não o suficiente para acionar uma transição para o estado de venda. Nossas regras de modelo indicam que esse recuo excede 5%, de forma que o sistema aciona uma transição para o estado de adição de compra. Como a compra, esse é um estado transitório e o sistema volta ao estado de compra quando a compra é concluída.
Em algum momento, o preço de fechamento cai abaixo da média móvel, indicando que o movimento chegou ao topo e ocorre uma transição para o evento de venda. Este evento move o sistema para o estado de venda transitório. Do estado de venda, duas decisões são possíveis. Podemos decidir parar de negociar completamente essa questão, ou podemos decidir continuar rastreando esse estoque e passar para o estado de venda quando a venda estiver concluída. A partir do estado de espera de venda, o sistema espera por uma penetração da média móvel para um sinal de compra. Uma oportunidade curta também pode ocorrer se o preço subir 5% sem penetrar na média móvel.
A Figura 3 mostra um gráfico e os diferentes estados desse modelo durante um período de tempo selecionado, como pode ser indicado pelas regras, conforme descrevi. Como você pode ver, a maior parte do tempo é gasto nos estados buy (B) ou sell hold (E).
Figura 3: Preço de fechamento das ações com média móvel.
Este é um modelo representativo de um sistema simples de negociação de ações. Outros sistemas, como a negociação de opções, podem ser mais complexos devido aos vários tipos possíveis de posições que podem ser tomadas, resultando em mais estados e possíveis transições. A máquina de estado fornece uma estrutura de controle lógico para organizar as regras do seu sistema de negociação e um método facilmente programado para automatizar essas regras. É então fácil fazer backtest do sistema aplicando os dados históricos à máquina de estado.
Uma máquina de estado pode ser usada para fornecer disciplina ao seu sistema de negociação. Você pode incorporar qualquer número de regras de decisão para cada estado. A estrutura que você projeta pode incorporar automaticamente relacionamentos de dependência que podem não ser óbvios ou facilmente modelados por outras abordagens. Como mostrei na barra lateral, a programação de uma máquina de estados não é difícil depois de definir as regras que você deseja usar. No entanto, a idéia da máquina de estado pode ser facilmente aplicada a um método de negociação discricionário.
Glenn Barlis é consultor de design de sistemas. Ele tem um mestrado em administração de empresas e um mestrado em ciência da computação.
Programando uma Máquina de Estado.
Uma máquina de estados pode ser implementada em qualquer linguagem que forneça a estrutura de controle IF-THEN-ELSE. O idioma também deve fornecer uma variável que possa conter o estado atual da máquina entre os eventos. Aqui está o exemplo do semáforo mostrado em uma linguagem semelhante ao BASIC. Estamos assumindo que a máquina de estado é executada uma vez por segundo e a máquina é iniciada em um estado válido conhecido.
Máquina de estado do semáforo.
Static Current_State; mantém o estado da máquina.
Temporizador Estático; mantém o controle de quanto tempo o.
a luz está acesa.
Green_time constante = 30; defina no tempo para luzes.
IF Current_State = Verde ENTÃO.
IF Timer & gt; = green_time ENTÃO.
Timer = Timer + 1.
ELSE IF Current_State = Amarelo ENTÃO.
IF Timer & gt; = yellow_time ENTÃO.
Timer = Timer + 1.
ELSE IF Current_State = Vermelho ENTÃO.
Temporizador IF & lt; (red_time - 5) E Cross_Button_Pushed THEN.
Timer = red_time - 5.
IF Timer & gt; = red_time ENTÃO.
Timer = Timer + 1.
Máquina de estados usando instrução CASE.
Manter o controle de todas as instruções IF-THEN-ELSE pode ficar confuso e torna o programa mais propenso a erros. Muitas linguagens de programação oferecem uma forma de instrução Case para simplificar a escrita desse tipo de código. Aqui está o mesmo exemplo usando uma instrução CASE com a sintaxe Visual BASIC.
Selecione o caso Current_State.
IF Timer & gt; = green_time ENTÃO.
Timer = Timer + 1.
IF Timer & gt; = yellow_time ENTÃO.
Timer = Timer + 1.
Temporizador IF & lt; (red_time - 5) E.
Timer = red_time - 5.
IF Timer & gt; = red_time ENTÃO.
Timer = Timer + 1.
A estrutura Select Case selecionará apenas um dos casos com base no valor de Current_State. Como você pode ver, este segmento de programa é muito mais fácil de entender do que o exemplo IF-THEN-ELSE e menos provável de ter bugs.
Uma terceira opção para implementar uma máquina de estados finitos é usar um mecanismo de máquina de estado orientado por tabela. Este é um método mais sofisticado que seria usado para máquinas complexas ou para software comercial que precisa fornecer um método fácil para regras de estado definidas pelo usuário.

Aprenda alguns Erlang.
Raiva Contra As Máquinas De Estado Finito.
O que eles são?
Uma máquina de estado finito (FSM) não é realmente uma máquina, mas tem um número finito de estados. Eu sempre achei as máquinas de estados finitos mais fáceis de entender com gráficos e diagramas. Por exemplo, o seguinte seria um diagrama simplista para um cão (muito burro) como uma máquina de estado:
Aqui o cão tem 3 estados: sentado, latindo ou abanando o rabo. Eventos ou entradas diferentes podem forçá-lo a mudar seu estado. Se um cachorro estiver sentado calmamente e vir um esquilo, ele começará a latir e não parará até você acariciá-lo novamente. No entanto, se o cão estiver sentado e você acariciá-lo, não temos idéia do que pode acontecer. No mundo de Erlang, o cão pode colidir (e eventualmente ser reiniciado pelo seu supervisor). No mundo real, seria um evento estranho, mas seu cachorro voltaria depois de ser atropelado por um carro, então nem tudo é ruim.
Aqui está o diagrama de estado de um gato para uma comparação:
Este gato tem um único estado e nenhum evento pode mudá-lo.
Implementar a máquina de estado do gato em Erlang é uma tarefa divertida e simples:
Podemos tentar o módulo para ver que o gato realmente nunca dá uma porcaria:
O mesmo pode ser feito para o cão FSM, exceto que mais estados estão disponíveis:
Deve ser relativamente simples combinar cada um dos estados e transições com o que estava no diagrama acima. Aqui está o FSM em uso:
Você pode acompanhar o esquema se quiser (eu geralmente faço, isso ajuda a ter certeza de que nada está errado).
Esse é realmente o núcleo dos FSMs implementados como processos Erlang. Existem coisas que poderiam ter sido feitas de maneira diferente: poderíamos ter passado o estado nos argumentos das funções de estado de maneira similar ao que fazemos com o loop principal dos servidores. Também poderíamos ter adicionado um init e finalizar funções, manipulado atualizações de código, etc.
Outra diferença entre os FSMs de cães e gatos é que os eventos do gato são síncronos e os eventos do cão são assíncronos. Em um FSM real, ambos poderiam ser usados ​​de uma maneira mista, mas eu fui para a representação mais simples de pura preguiça inexplorada. Existem outras formas de eventos que os exemplos não mostram: eventos globais que podem acontecer em qualquer estado.
Um exemplo de tal evento poderia ser quando o cão fica com cheiro de comida. Uma vez que o evento do cheiro do alimento é acionado, não importa em que estado o cão esteja, ele irá procurar a fonte de alimento.
Agora, não gastaremos muito tempo implementando tudo isso em nosso FSM "escrito em um guardanapo". Em vez disso, nos moveremos diretamente para o comportamento gen_fsm.
Máquinas de estados finitos genéricos.
O comportamento gen_fsm é um pouco semelhante ao gen_server, pois é uma versão especializada dele. A maior diferença é que, em vez de lidar com chamadas e conversões, estamos lidando com eventos síncronos e assíncronos. Assim como nossos exemplos de cachorros e gatos, cada estado é representado por uma função. Mais uma vez, vamos passar pelos callbacks que nossos módulos precisam implementar para funcionar.
Este é o mesmo init / 1 usado para servidores genéricos, exceto que os valores de retorno aceitos são, e. A tupla de parada funciona da mesma maneira que para gen_server s, e a hibernação e o Tempo limite mantêm a mesma semântica.
O que há de novo aqui é essa variável StateName. StateName é um átomo e representa a próxima função de retorno de chamada a ser chamada.
As funções StateName / 2 e StateName / 3 são nomes de espaços reservados e você deve decidir o que eles serão. Vamos supor que a função init / 1 retorne a tupla. Isso significa que a máquina de estados finitos estará em um estado sentado. Este não é o mesmo tipo de estado que vimos com gen_server; é bastante equivalente aos estados sit, bark e wag_tail do cão anterior FSM. Esses estados ditam um contexto no qual você manipula um determinado evento.
Um exemplo disso seria alguém ligando para você no seu telefone. Se você está no estado "dormindo em uma manhã de sábado", sua reação pode ser gritar no telefone. Se o seu estado está "esperando por uma entrevista de emprego", é provável que você escolha o telefone e responda educadamente. Por outro lado, se você está no estado 'morto', então eu estou surpreso que você possa até mesmo ler este texto.
De volta ao nosso FSM. A função init / 1 disse que deveríamos estar no estado sentado. Sempre que o processo gen_fsm receber um evento, a função sitting / 2 ou sitting / 3 será chamada. A função sitting / 2 é chamada para eventos assíncronos e sentados / 3 para eventos síncronos.
Os argumentos para sitting / 2 (ou geralmente StateName / 2) são Event, a mensagem real enviada como um evento e StateData, os dados que foram transportados pelas chamadas. sentado / 2 pode então retornar as tuplas, e.
Os argumentos para sitting / 3 são semelhantes, exceto que há uma variável From entre Event e StateData. A variável From é usada exatamente da mesma maneira que era para gen_server s, incluindo gen_fsm: reply / 2. As funções StateName / 3 podem retornar as seguintes tuplas:
Observe que não há limite para quantas dessas funções você pode ter, contanto que sejam exportadas. Os átomos retornados como NextStateName nas tuplas determinarão se a função será chamada ou não.
handle_event.
Na última seção, eu mencionei eventos globais que desencadeariam uma reação específica, não importando em que estado estivéssemos (o cachorro cheirando a comida vai cair o que estiver fazendo e, ao invés disso, procurar por comida). Para esses eventos que devem ser tratados da mesma maneira em todos os estados, o retorno de chamada handle_event / 3 é o que você deseja. A função aceita argumentos semelhantes a StateName / 2 com a exceção de que aceita uma variável StateName entre eles, informando qual era o estado quando o evento foi recebido. Ele retorna os mesmos valores que StateName / 2.
handle_sync_event.
O retorno de chamada handle_sync_event / 4 é para StateName / 3 que handle_event / 2 é para StateName / 2. Ele manipula eventos globais síncronos, usa os mesmos parâmetros e retorna o mesmo tipo de tuplas que StateName / 3.
Agora pode ser um bom momento para explicar como sabemos se um evento é global ou se é para ser enviado para um estado específico. Para determinar isso, podemos observar a função usada para enviar um evento ao FSM. Eventos assíncronos destinados a qualquer função StateName / 2 são enviados com send_event / 2, eventos síncronos para serem escolhidos por StateName / 3 devem ser enviados com sync_send_event / 2-3.
As duas funções equivalentes para eventos globais são send_all_state_event / 2 e sync_send_all_state_event / 2-3 (um nome bem longo).
code_change.
Isso funciona exatamente da mesma forma que para gen_server s, exceto pelo fato de que é necessário um parâmetro de estado extra quando chamado como code_change (OldVersion, StateName, Data, Extra) e retorna uma tupla do formulário.
Isso deve, novamente, agir um pouco como o que temos para servidores genéricos. terminate / 3 deve fazer o oposto de init / 1.
Uma especificação do sistema de negociação.
É hora de colocar tudo isso em prática. Muitos tutoriais Erlang sobre máquinas de estados finitos usam exemplos contendo comutadores de telefone e coisas semelhantes. Acredito que a maioria dos programadores raramente terá que lidar com comutadores telefônicos para máquinas de estado. Por isso, vamos ver um exemplo que é mais adequado para muitos desenvolvedores: vamos projetar e implementar um sistema de negociação de itens para algum videogame fictício e não existente.
O design que escolhi é um pouco desafiador. Em vez de usar um corretor através do qual os jogadores roteiam itens e confirmações (o que, francamente, seria mais fácil), vamos implementar um servidor onde ambos os jogadores falam diretamente um com o outro (o que teria a vantagem de ser distribuível).
Como a implementação é complicada, passo um bom tempo descrevendo, o tipo de problema a ser enfrentado e as maneiras de corrigi-los.
Primeiro de tudo, devemos definir as ações que podem ser feitas pelos nossos jogadores durante a negociação. A primeira é pedir uma negociação para ser configurada. O outro usuário também deve ser capaz de aceitar esse comércio. Nós não lhes daremos o direito de negar um negócio, porque queremos manter as coisas simples. Será fácil adicionar esse recurso quando a coisa toda estiver concluída.
Uma vez que o comércio está configurado, nossos usuários devem poder negociar entre si. Isso significa que eles devem ser capazes de fazer ofertas e depois retratá-las, se quiserem. Quando ambos os jogadores estão satisfeitos com a oferta, cada um deles pode se declarar pronto para finalizar a negociação. Os dados devem ser salvos em algum lugar dos dois lados. A qualquer momento, também deve fazer sentido para qualquer um dos jogadores cancelar o trade inteiro. Alguns pleb poderiam estar oferecendo apenas itens considerados indignos para a outra parte (que pode estar muito ocupada) e, portanto, deve ser possível fazer um cancelamento com um merecido cancelamento.
Em suma, as seguintes ações devem ser possíveis:
pedir um comércio aceitar uma oferta de comércio itens retrair uma oferta declarar auto como pronto cancelar brutalmente o comércio.
Agora, quando cada uma dessas ações é executada, o FSM do outro jogador deve estar ciente disso. Isso faz sentido, porque quando Jim diz ao seu FSM para mandar um item para Carl, o FSM de Carl tem que estar ciente disso. Isso significa que ambos os jogadores podem falar com o seu próprio FSM, que falará com o FSM do outro. Isso nos dá algo um pouco assim:
A primeira coisa a notar quando temos dois processos idênticos se comunicando entre si é que temos que evitar chamadas síncronas o máximo possível. A razão para isso é que, se o FSM de Jim envia uma mensagem para o FSM de Carl e aguarda sua resposta, enquanto o FS de Carl envia uma mensagem ao FSM de Jim e aguarda sua resposta específica, ambos acabam esperando pelo outro. sem nunca responder. Isso efetivamente congela os dois FSMs. Nós temos um impasse.
Uma solução para isso é esperar por um tempo limite e, em seguida, seguir em frente, mas depois haverá mensagens de sobras nas caixas de correio de ambos os processos e o protocolo será confuso. Isso certamente é uma lata de vermes, e por isso queremos evitá-lo.
A maneira mais simples de fazer isso é evitar todas as mensagens síncronas e ir totalmente assíncrono. Observe que Jim ainda pode fazer uma chamada síncrona para seu próprio FSM; não há risco aqui porque o FSM não precisará ligar para Jim e, portanto, nenhum bloqueio pode ocorrer entre eles.
Quando dois desses FSMs se comunicam juntos, toda a troca pode parecer um pouco assim:
Ambos os FSMs estão em um estado inativo. Quando você pede para Jim negociar, Jim tem que aceitar antes que as coisas mudem. Então vocês dois podem oferecer itens ou retirá-los. Quando ambos estiverem se declarando prontos, a negociação pode acontecer. Esta é uma versão simplificada de tudo o que pode acontecer e veremos todos os casos possíveis com mais detalhes nos próximos parágrafos.
Aí vem a parte difícil: definir o diagrama de estados e como as transições de estado acontecem. Geralmente, um bom raciocínio é necessário, porque você precisa pensar em todas as pequenas coisas que poderiam dar errado. Algumas coisas podem dar errado, mesmo depois de revê-lo muitas vezes. Por isso, vou simplesmente colocar o que decidi implementar aqui e depois explicá-lo.
Inicialmente, ambas as máquinas de estado finito começam no estado inativo. Neste ponto, uma coisa que podemos fazer é pedir a outro jogador para negociar conosco:
Entramos no modo idle_wait para aguardar uma eventual resposta após o FSM ter enviado a demanda. Quando o outro FSM enviar a resposta, o nosso pode mudar para negociar:
O outro jogador também deve estar em negociação depois disso. Obviamente, se podemos convidar o outro, o outro pode nos convidar. Se tudo correr bem, isso deve ficar assim:
Então, isso é basicamente o oposto dos dois diagramas de estado anteriores agrupados em um. Note que esperamos que o jogador aceite a oferta neste caso. O que acontece se por pura sorte, pedirmos ao outro jogador que troque conosco ao mesmo tempo em que ele nos pede para negociar?
O que acontece aqui é que ambos os clientes pedem ao seu próprio FSM para negociar com o outro. Assim que as mensagens de solicitação de negociação são enviadas, ambas as FSMs mudam para o estado idle_wait. Então eles poderão processar a questão de negociação. Se revisarmos os diagramas de estado anteriores, veremos que essa combinação de eventos é a única vez que receberemos a solicitação de negociar mensagens enquanto estiver no estado idle_wait. Conseqüentemente, sabemos que a obtenção dessas mensagens em idle_wait significa que atingimos a condição de corrida e podemos supor que ambos os usuários desejam conversar entre si. Podemos mover os dois para negociar o estado. Viva.
Então agora estamos negociando. De acordo com a lista de ações que listei anteriormente, devemos oferecer suporte aos usuários que oferecem itens e, depois, recolher a oferta:
Tudo isso faz encaminhar a mensagem do nosso cliente para o outro FSM. Ambas as máquinas de estado finito precisarão manter uma lista de itens oferecida por qualquer um dos jogadores, para que possam atualizar essa lista quando receberem tais mensagens. Ficamos no estado de negociação depois disso; talvez o outro jogador também queira oferecer itens:
Aqui, nosso FSM basicamente age de maneira semelhante. Isto é normal. Quando nos cansamos de oferecer as coisas e achamos que somos suficientemente generosos, temos que dizer que estamos prontos para oficializar o negócio. Como temos que sincronizar os dois jogadores, teremos que usar um estado intermediário, como fizemos para o idle e o idle_wait:
O que fazemos aqui é que, assim que o nosso player estiver pronto, o nosso FSM perguntará ao FSM do Jim se ele estiver pronto. Enquanto aguarda sua resposta, nosso próprio FSM entra em seu estado de espera. A resposta que receberemos dependerá do estado de FS do Jim: se estiver no estado de espera, isso nos dirá que está pronto. Caso contrário, nos dirá que ainda não está pronto. Isso é precisamente o que o nosso FSM automaticamente responde a Jim se ele nos perguntar se estamos prontos quando negociarmos:
Nossa máquina de estados finitos permanecerá em modo de negociação até que o jogador diga que está pronto. Vamos supor que ele fez e agora estamos no estado de espera. No entanto, Jim não está lá ainda. Isso significa que, quando nos declararmos prontos, teremos perguntado a Jim se ele também estava pronto e seu FSM terá respondido "ainda não":
Ele não está pronto, mas nós somos. Nós não podemos fazer muito, mas continuamos esperando. Enquanto espera por Jim, que ainda está negociando, é possível que ele tente nos enviar mais itens ou talvez cancelar suas ofertas anteriores:
Claro, queremos evitar que Jim remova todos os seus itens e, em seguida, clique em "Estou pronto!", Estragando-nos no processo. Assim que ele muda os itens oferecidos, voltamos ao estado de negociação para que possamos modificar nossa própria oferta ou examinar a atual e decidir que estamos prontos. Enxague e repita.
Em algum momento, Jim estará pronto para finalizar o negócio também. Quando isso acontecer, sua máquina de estado finito perguntará a nós se estivermos prontos:
O que nosso FSM faz é responder que, de fato, estamos prontos. Nós permanecemos no estado de espera e nos recusamos a nos mudar para o estado pronto. Por que é isso? Porque há uma condição de corrida em potencial! Imagine que a seguinte sequência de eventos ocorra, sem fazer este passo necessário:
Isso é um pouco complexo, então vou explicar. Devido ao modo como as mensagens são recebidas, poderíamos apenas processar a oferta de itens depois de nos declararmos prontos e também depois que Jim se declarasse pronto. Isso significa que, assim que lemos a mensagem de oferta, voltamos ao estado de negociação. Durante esse tempo, Jim nos disse que está pronto. Se ele mudasse os estados e se preparasse (como ilustrado acima), ele seria pego esperando indefinidamente enquanto nós não saberíamos o que diabos fazer. Isso também pode acontecer ao contrário! Ugh.
Uma maneira de resolver isso é adicionando uma camada de indireção (graças a David Wheeler). É por isso que ficamos no modo de espera e enviamos 'pronto!' (como mostrado no nosso diagrama de estado anterior). Veja como lidamos com isso 'pronto!' mensagem, assumindo que já estávamos no estado pronto porque dissemos ao nosso FSM que estávamos prontos de antemão:
Quando recebemos 'pronto!' do outro FSM, enviamos 'pronto!' de volta. Isso é para ter certeza de que não teremos a "condição de corrida dupla" mencionada acima. Isto irá criar um supérfluo 'pronto!' mensagem em um dos dois FSMs, mas vamos ter que ignorá-lo neste caso. Em seguida, enviamos uma mensagem 'ack' (e o FSM do Jim fará o mesmo) antes de passar para o estado pronto. A razão pela qual esta mensagem "ack" existe é devido a alguns detalhes de implementação sobre a sincronização de clientes. Eu coloquei no diagrama para ser correto, mas não vou explicá-lo até mais tarde. Esqueça isso por enquanto. We finally managed to synchronise both players. Whew
So now there's the ready state. This one is a bit special. Both players are ready and have basically given the finite-state machines all the control they need. This lets us implement a bastardized version of a two-phase commit to make sure things go right when making the trade official:
Our version (as described above) will be rather simplistic. Writing a truly correct two-phase commit would require a lot more code than what is necessary for us to understand finite-state machines.
Finally, we only have to allow the trade to be cancelled at any time. This means that somehow, no matter what state we're in, we're going to listen to the 'cancel' message from both sides and quit the transaction. It should also be common courtesy to let the other side know we're gone before leaving.
Alright! It's a whole lot of information to absorb at once. Don't worry if it takes a while to fully grasp it. It took a bunch of people to look over my protocol to see if it was right, and even then we all missed a few race conditions that I then caught a few days later when reviewing the code while writing this text. It's normal to need to read it more than once, especially if you are not used to asynchronous protocols. If this is the case, I fully encourage you to try and design your own protocol. Then ask yourself "what happens if two people do the same actions very fast? What if they chain two other events quickly? What do I do with messages I don't handle when changing states?" You'll see that the complexity grows real fast. You might find a solution similar to mine, possibly a better one (let me know if this is the case!) No matter the outcome, it's a very interesting thing to work on and our FSMs are still relatively simple.
Once you've digested all of this (or before, if you're a rebel reader), you can go to the next section, where we implement the gaming system. For now you can take a nice coffee break if you feel like doing so.
Game trading between two players.
The first thing that needs to be done to implement our protocol with OTP's gen_fsm is to create the interface. There will be 3 callers for our module: the player, the gen_fsm behaviour and the other player's FSM. We will only need to export the player function and gen_fsm functions, though. This is because the other FSM will also run within the trade_fsm module and can access them from the inside:
So that's our API. You can see I'm planning on having some functions being both synchronous and asynchronous. This is mostly because we want our client to call us synchronously in some cases, but the other FSM can do it asynchronously. Having the client synchronous simplifies our logic a whole lot by limiting the number of contradicting messages that can be sent one after the other. We'll get there. Let's first implement the actual public API according to the protocol defined above:
This is rather standard; all these 'gen_fsm' functions have been covered before (except start/3-4 and start_link/3-4 which I believe you can figure out) in this chapter.
Next we'll implement the FSM to FSM functions. The first ones have to do with trade setups, when we first want to ask the other user to join us in a trade:
The first function asks the other pid if they want to trade, and the second one is used to reply to it (asynchronously, of course).
We can then write the functions to offer and cancel offers. According to our protocol above, this is what they should be like:
So, now that we've got these calls done, we need to focus on the rest. The remaining calls relate to being ready or not and handling the final commit. Again, given our protocol above, we have three calls: are_you_ready , which can have the replies not_yet or ready! :
The only functions left are those which are to be used by both FSMs when doing the commit in the ready state. Their precise usage will be described more in detail later, but for now, the names and the sequence/state diagram from earlier should be enough. Nonetheless, you can still transcribe them to your own version of trade_fsm:
Oh and there's also the courtesy function allowing us to warn the other FSM we cancelled the trade:
We can now move to the really interesting part: the gen_fsm callbacks. The first callback is init/1 . In our case, we'll want each FSM to hold a name for the user it represents (that way, our output will be nicer) in the data it keeps passing on to itself. What else do we want to hold in memory? In our case, we want the other's pid, the items we offer and the items the other offers. We're also going to add the reference of a monitor (so we know to abort if the other dies) and a from field, used to do delayed replies:
In the case of init/1 , we'll only care about our name for now. Note that we'll begin in the idle state:
The next callbacks to consider would be the states themselves. So far I've described the state transitions and calls that can be made, but We'll need a way to make sure everything goes alright. We'll write a few utility functions first:
And we can start with the idle state. For the sake of convention, I'll cover the asynchronous version first. This one shouldn't need to care for anything but the other player asking for a trade given our own player, if you look at the API functions, will use a synchronous call:
A monitor is set up to allow us to handle the other dying, and its ref is stored in the FSM's data along with the other's pid, before moving to the idle_wait state. Note that we will report all unexpected events and ignore them by staying in the state we were already in. We can have a few out of band messages here and there that could be the result of race conditions. It's usually safe to ignore them, but we can't easily get rid of them. It's just better not to crash the whole FSM on these unknown, but somewhat expected messages.
When our own client asks the FSM to contact another player for a trade, it will send a synchronous event. The idle/3 callback will be needed:
We proceed in a way similar to the asynchronous version, except we need to actually ask the other side whether they want to negotiate with us or not. You'll notice that we do not reply to the client yet. This is because we have nothing interesting to say, and we want the client locked and waiting for the trade to be accepted before doing anything. The reply will only be sent if the other side accepts once we're in idle_wait .
When we're there, we have to deal with the other accepting to negotiate and the other asking to negotiate (the result of a race condition, as described in the protocol):
This gives us two transitions to the negotiate state, but remember that we must use gen_fsm:reply/2 reply to our client to tell it it's okay to start offering items. There's also the case of our FSM's client accepting the trade suggested by the other party:
Again, this one moves on to the negotiate state. Here, we must handle asynchronous queries to add and remove items coming both from the client and the other FSM. However, we have not yet decided how to store items. Because I'm somewhat lazy and I assume users won't trade that many items, simple lists will do it for now. However, we might change our mind at a later point, so it would be a good idea to wrap item operations in their own functions. Add the following functions at the bottom of the file with notice/3 and unexpected/2 :
Simple, but they have the role of isolating the actions (adding and removing items) from their implementation (using lists). We could easily move to proplists, arrays or whatever data structure without disrupting the rest of the code.
Using both of these functions, we can implement offering and removing items:
This is an ugly aspect of using asynchronous messages on both sides. One set of message has the form 'make' and 'retract', while the other has 'do' and 'undo'. This is entirely arbitrary and only used to differentiate between player-to-FSM communications and FSM-to-FSM communications. Note that on those coming from our own player, we have to tell the other side about the changes we're making.
Another responsibility is to handle the are_you_ready message we mentioned in the protocol. This one is the last asynchronous event to handle in the negotiate state:
As described in the protocol, whenever we're not in the wait state and receive this message, we must reply with not_yet . Were also outputting trade details to the user so a decision can be made.
When such a decision is made and the user is ready, the ready event will be sent. This one should be synchronous because we don't want the user to keep modifying his offer by adding items while claiming he's ready:
At this point a transition to the wait state should be made. Note that just waiting for the other is not interesting. We save the From variable so we can use it with gen_fsm:reply/2 when we have something to tell to the client.
The wait state is a funny beast. New items might be offered and retracted because the other user might not be ready. It makes sense, then, to automatically rollback to the negotiating state. It would suck to have great items offered to us, only for the other to remove them and declare himself ready, stealing our loot. Going back to negotiation is a good decision:
Now that's something meaningful and we reply to the player with the coordinates we stored in S#state. from . The next set of messages we need to worry about are those related to with synchronising both FSMs so they can move to the ready state and confirm the trade. For this one we should really focus on the protocol defined earlier.
The three messages we could have are are_you_ready (because the other user just declared himself ready), not_yet (because we asked the other if he was ready and he was not) and ready! (because we asked the other if he was ready and he was).
We'll start with are_you_ready . Remember that in the protocol we said that there could be a race condition hidden there. The only thing we can do is send the ready! message with am_ready/1 and deal with the rest later:
We'll be stuck waiting again, so it's not worth replying to our client yet. Similarly, we won't reply to the client when the other side sends a not_yet to our invitation:
On the other hand, if the other is ready, we send an extra ready! message to the other FSM, reply to our own user and then move to the ready state:
You might have noticed that I've used ack_trans/1 . In fact, both FSMs should use it. Por que é isso? To understand this we have to start looking at what goes on in the ready! Estado.
When in the ready state, both players' actions become useless (except cancelling). We won't care about new item offers. This gives us some liberty. Basically, both FSMs can freely talk to each other without worrying about the rest of the world. This lets us implement our bastardization of a two-phase commit. To begin this commit without either player acting, we'll need an event to trigger an action from the FSMs. The ack event from ack_trans/1 is used for that. As soon as we're in the ready state, the message is treated and acted upon; the transaction can begin.
Two-phase commits require synchronous communications, though. This means we can't have both FSMs starting the transaction at once, because they'll end up deadlocked. The secret is to find a way to decide that one finite state machine should initiate the commit, while the other will sit and wait for orders from the first one.
It turns out that the engineers and computer scientists who designed Erlang were pretty smart (well, we knew that already). The pids of any process can be compared to each other and sorted. This can be done no matter when the process was spawned, whether it's still alive or not, or if it comes from another VM (we'll see more about this when we get into distributed Erlang).
Knowing that two pids can be compared and one will be greater than the other, we can write a function priority/2 that will take two pids and tell a process whether it's been elected or not:
And by calling that function, we can have one process starting the commit and the other following the orders.
Here's what this gives us when included in the ready state, after receiving the ack message:
This big try . catch expression is the leading FSM deciding how the commit works. Both ask_commit/1 and do_commit/1 are synchronous. This lets the leading FSM call them freely. You can see that the other FSM just goes and wait. It will then receive the orders from the leading process. The first message should be ask_commit . This is just to make sure both FSMs are still there; nothing wrong happened, they're both dedicated to completing the task:
Once this is received, the leading process will ask to confirm the transaction with do_commit . That's when we must commit our data:
And once it's done, we leave. The leading FSM will receive ok as a reply and will know to commit on its own end afterwards. This explains why we need the big try . catch : if the replying FSM dies or its player cancels the transaction, the synchronous calls will crash after a timeout. The commit should be aborted in this case.
Just so you know, I defined the commit function as follows:
Pretty underwhelming, eh? It's generally not possible to do a true safe commit with only two participants—a third party is usually required to judge if both players did everything right. If you were to write a true commit function, it should contact that third party on behalf of both players, and then do the safe write to a database for them or rollback the whole exchange. We won't go into such details and the current commit/1 function will be enough for the needs of this book.
We're not done yet. We have not yet covered two types of events: a player cancelling the trade and the other player's finite state machine crashing. The former can be dealt with by using the callbacks handle_event/3 and handle_sync_event/4 . Whenever the other user cancels, we'll receive an asynchronous notification:
When we do it we must not forget to tell the other before quitting ourselves:
And voilà! The last event to take care of is when the other FSM goes down. Fortunately, we had set a monitor back in the idle state. We can match on this and react accordingly:
Note that even if the cancel or DOWN events happen while we're in the commit, everything should be safe and nobody should get its items stolen.
Note: we used io:format/2 for most of our messages to let the FSMs communicate with their own clients. In a real world application, we might want something more flexible than that. One way to do it is to let the client send in a Pid, which will receive the notices sent to it. That process could be linked to a GUI or any other system to make the player aware of the events. The io:format/2 solution was chosen for its simplicity: we want to focus on the FSM and the asynchronous protocols, not the rest.
Only two callbacks left to cover! They're code_change/4 and terminate/3 . For now, we don't have anything to do with code_change/4 and only export it so the next version of the FSM can call it when it'll be reloaded. Our terminate function is also really short because we didn't handle real resources in this example:
We can now try it. Well, trying it is a bit annoying because we need two processes to communicate to each other. To solve this, I've written the tests in the file trade_calls. erl, which can run 3 different scenarios. The first one is main_ab/0 . It will run a standard trade and output everything. The second one is main_cd/0 and will cancel the transaction halfway through. The last one is main_ef/0 and is very similar to main_ab/0 , except it contains a different race condition. The first and third tests should succeed, while the second one should fail (with a crapload of error messages, but that's how it goes). You can try it if you feel like it.
That Was Quite Something.
If you've found this chapter a bit harder than the others, I must remind you that it's entirely normal. I've just gone crazy and decided to make something hard out of the generic finite-state machine behaviour. If you feel confused, ask yourself these questions: Can you understand how different events are handled depending on the state your process is in? Do you understand how you can transition from one state to the other? Do you know when to use send_event/2 and sync_send_event/2-3 as opposed to send_all_state_event/2 and sync_send_all_state_event/3 ? If you answered yes to these questions, you understand what gen_fsm is about.
The rest of it with the asynchronous protocols, delaying replies and carrying the From variable, giving a priority to processes for synchronous calls, bastardized two-phase commits and whatnot are not essential to understand . They're mostly there to show what can be done and to highlight the difficulty of writing truly concurrent software, even in a language like Erlang. Erlang doesn't excuse you from planning or thinking, and Erlang won't solve your problems for you. It'll only give you tools.
That being said, if you understood everything about these points, you can be proud of yourself (especially if you had never written concurrent software before). You are now starting to really think concurrently.
Fit for the Real World?
In a real game, there is a lot more stuff going on that could make trading even more complex. Items could be worn by the characters and damaged by enemies while they're being traded. Maybe items could be moved in and out of the inventory while being exchanged. Are the players on the same server? If not, how do you synchronise commits to different databases?
Our trade system is sane when detached from the reality of any game. Before trying to fit it in a game (if you dare), make sure everything goes right. Test it, test it, and test it again. You'll likely find that testing concurrent and parallel code is a complete pain. You'll lose hair, friends and a piece of your sanity. Even after this, you'll have to know your system is always as strong as its weakest link and thus potentially very fragile nonetheless.
Don't Drink Too Much Kool-Aid:
While the model for this trade system seems sound, subtle concurrency bugs and race conditions can often rear their ugly heads a long time after they were written, and even if they've been running for years. While my code is generally bullet proof (yeah, right), you sometimes have to face swords and knives. Beware the dormant bugs.
Fortunately, we can put all of this madness behind us. We'll next see how OTP allows you to handle various events, such as alarms and logs, with the help of the gen_event behaviour.
Except where otherwise noted, content on this site is licensed under a Creative Commons Attribution Non-Commercial No Derivative License.

Trading system finite state machine

Use a state machine to represent a (real or logical) object that can exist in a limited number of conditions (" states ") and progresses from one state to the next according to a fixed set of rules.
Why would I use a state machine?
A state machine is often a very compact way to represent a set of complex rules and conditions, and to process various inputs. You'll see state machines in embedded devices that have limited memory. Implemented well, a state machine is self-documenting because each logical state represents a physical condition. A state machine can be embodied in a tiny amount of code in comparison to its procedural equivalent and runs extremely efficiently. Moreover, the rules that govern state changes can often be stored as data in a table, providing a compact representation that can be easily maintained.
How can I implement one?
The example uses a switch() with explicit case / break states for simplicity. In practice, a case will often "fall through" to the next state.
For ease of maintaining a large state machine, the work done in each case can be encapsulated in a "worker" function. Get any input at the top of the while() , pass it to the worker function, and check the return value of the worker to compute the next state.
For compactness, the entire switch() can be replaced with an array of function pointers. Each state is embodied by a function whose return value is a pointer to the next state. Warning: This can either simplify the state machine or render it totally unmaintainable, so consider the implementation carefully!
An embedded device may be implemented as a state machine that exits only on a catastrophic error, after which it performs a hard reset and re-enters the state machine.
Some great answers already. For a slightly different perspective, consider searching a text in a larger string. Someone has already mentioned regular expressions and this is really just a special case, albeit an important one.
Consider the following method call:
How would you implement find_in_string ? The easy approach would use a nested loop, something like this:
Apart from the fact that this is inefficient, it forms a state machine ! The states here are somewhat hidden; let me rewrite the code slightly to make them more visible:
The different states here directly represent all different positions in the word we search for. There are two transitions for each node in the graph: if the letters match, go to the next state; for every other input (i. e. every other letter at the current position), go back to zero.
This slight reformulation has a huge advantage: it can now be tweaked to yield better performance using some basic techniques. In fact, every advanced string searching algorithm (discounting index data structures for the moment) builds on top of this state machine and improves some aspects of it.
Any task but from what I have seen, Parsing of any sort is frequently implemented as a state machine.
Parsing a grammar is generally not a straightforward task. During the design phase it is fairly common that a state diagram is drawn to test the parsing algorithm. Translating that to a state machine implementation is a fairly simple task.
Well, you are limited only by your imagination.
I have seen it done with labels and goto statements.
I have even seen it done with structures of function pointers which represent the current state. When the state changes, one or more function pointer is updated.
I have seen it done in code only, where a change of state simply means that you are running in a different section of code. (no state variables, and redundent code where necessary. This can be demonstrated as a very simply sort, which is useful for only very small sets of data.
There are no state variables, but the code itself represents the state.
The State design pattern is an object-oriented way to represent the state of an object by means of a finite state machine. It usually helps to reduce the logical complexity of that object's implementation (nested if's, many flags, etc.)
Most workflows can be implemented as state machines. For example, processing leave applications or orders.
If you're using. NET, try Windows Workflow Foundation. You can implement a state machine workflow quite quickly with it.
If you're using C#, any time you write an iterator block you're asking the compiler to build a state machine for you (keeping track of where you are in the iterator etc).
Here is a tested and working example of a state machine. Say you are on a serial stream (serial port, tcp/ip data, or file are typical examples). In this case I am looking for a specific packet structure that can be broken into three parts, sync, length, and payload. I have three states, one is idle, waiting for the sync, the second is we have a good sync the next byte should be length, and the third state is accumulate the payload.
The example is purely serial with only one buffer, as written here it will recover from a bad byte or packet, possibly discarding a packet but eventually recovering, you can do other things like a sliding window to allow for immediate recovery. This would be where you have say a partial packet that is cut short then a new complete packet starts, the code below wont detect this and will throw away the partial as well as the whole packet and recover on the next. A sliding window would save you there if you really needed to process all the whole packets.
I use this kind of a state machine all the time be it serial data streams, tcp/ip, file i/o. Or perhaps tcp/ip protocols themselves, say you want to send an email, open the port, wait for the server to send a response, send HELO, wait for the server to send a packet, send a packet, wait for the reply, etc. Essentially in that case as well as in the case below you may be idling waiting for that next byte/packet to come in. To remember what you were waiting for, also to re-use the code that waits for something you can use state variables. The same way that state machines are used in logic (waiting for the next clock, what was I waiting for).
Just like in logic, you may want to do something different for each state, in this case if I have a good sync pattern I reset the offset into my storage as well as reset the checksum accumulator. The packet length state demonstrates a case where you may want to abort out of the normal control path. Not all, in fact many state machines may jump around or may loop around within the normal path, the one below is pretty much linear.
I hope this is useful and wish that state machines were used more in software.
The test data has intentional problems with it that the state machine recovers from. There is some garbage data after the first good packet, a packet with a bad checksum, and a packet with an invalid length. My output was:
good packet:FA0712345678EB Invalid sync pattern 0x12 Invalid sync pattern 0x34 Invalid sync pattern 0x56 Checksum error 0xBF Invalid packet length 0 Invalid sync pattern 0x12 Invalid sync pattern 0x34 Invalid sync pattern 0x56 Invalid sync pattern 0x78 Invalid sync pattern 0xEB good packet:FA081234567800EA no more test data.
The two good packets in the stream were extracted despite the bad data. And the bad data was detected and dealt with.

Finite State Machines.
Relevante para.
Computer Science >
A finite state machine (sometimes called a finite state automaton) is a computation model that can be implemented with hardware or software and can be used to simulate sequential logic and some computer programs. Finite state automata generate regular languages. Finite state machines can be used to model problems in many fields including mathematics, artificial intelligence, games, and linguistics.
Finite State Machines.
There are two types of finite state machines (FSMs): deterministic finite state machines, often called deterministic finite automata, and nondeterministic finite state machines, often called nondeterministic finite automata. There are slight variations in ways that state machines are represented visually, but the ideas behind them stem from the same computational ideas. By definition, deterministic finite automata recognize, or accept, regular languages, and a language is regular if a deterministic finite automaton accepts it. FSMs are usually taught using languages made up of binary strings that follow a particular pattern. Both regular and non-regular languages can be made out of binary strings. An example of a binary string language is: the language of all strings that have a 0 as the first character. In this language, 001, 010, 0, and 01111 are valid strings (along with many others), but strings like 111, 10000, 1, and 11001100 (along with many others) are not in this language.
You can walk through the finite state machine diagram to see what kinds of strings the machine will produce, or you can feed it a given input string and verify whether or not there exists a set of transitions you can take to make the string (ending in an accepting state).
Formal Definition.
Deterministic Finite Automata.
A deterministic finite automaton (DFA) is described by a five-element tuple: \((Q, \Sigma, \delta, q_0, F)\).
\(Q\) = a finite set of states.
\(\Sigma\) = a finite, nonempty input alphabet.
\(\delta\) = a series of transition functions.
\(q_0\) = the starting state.
\(F\) = the set of accepting states.
There must be exactly one transition function for every input symbol in \(\Sigma\) from each state.
DFAs can be represented by diagrams of this form:
Write a description of the DFA shown above. Describe in words what it does.