Fila circular para sistemas embarcados

Caro leitor, como vai? Falamos há alguns dias sobre uma estrutura de dados simples e eficiente para armazenamento temporário de sequências de bytes, podendo ser usada em comunicações e processamento de dados, o buffer circular, um recurso com política de inserção e remoção de dados do tipo FIFO. Bem, neste artigo vamos aproveitar o uso da estrutura do buffer circular e transforma-lo em uma estrutura de dados ainda mais poderosa, uma fila circular, ou circular queue em inglês.

 

 

Qual a diferença entre Buffer Circular e Fila Circular?

 

Essencialmente, são idênticas, possuem políticas de inserção e remoção baseados em FIFO, controle de "wrap around", ou seja, em caso de estouro o índice de escrita ou leitura aponta para o início da memória alocada para os dados. A diferença essencial encontra-se na unidade do tamanho de dados. No buffer circular podemos inserir uma cadeia de bytes com tamanho variável entre 1 e o tamanho da memória alocada (desde que ela esteja livre), da mesma forma que podemos retirar uma cadeia de dados sob o mesmo intervalo.

 

Na mesma essência, a fila circular permite a retirada de cadeia de bytes, porém de tamanho limitado a uma subdivisão lógica da área de memória conhecida por slots, assim uma fila circular possui a capacidade de N slots onde cada slot comporta até B bytes. O leitor mais atento consegue perceber que isso já remete no uso da fila circular para armazenamento de volumes de dados maiores, podendo ser usado como um gerenciador de memória simples com tamanho de bloco fixo. Perfeito, por exemplo, para ordenar tipos de dados complexos como uma sequência de datagramas TCP ou UDP. Vejam a figura abaixo:

 fila-circular

 

 

Vejam na figura que para cada linha da tabela existem vários campos a serem preenchidos. Na abordagem da fila circular, cada linha dessa tabela teria o tamanho de um slot, de modo que a inserção seria pela cópia de um slot e a retirada por uma linha inteira da tabela na ordem em que os slots chegam. No Buffer circular estávamos interessados na ordem em que os bytes chegavam.

 

 

Onde poderia aplicar uma Fila Circular

 

Caro leitor, vamos voltar ao caso da UART que citei no artigo sobre buffers circulares. Nós já sabemos que usando eles podemos fazer com que a UART capture os bytes que chegam e os ordene para posterior tratamento. Agora imaginemos o caso em que por essa mesma UART trafegue um protocolo de comunicação, que contenha vários comandos, porém todos eles com a mesma sequência de bytes. Tomando, por exemplo, o conhecido protocolo MODBUS, um Telegram (estrutura padrão MODBUS) pode conter os seguintes campos conforme a figura abaixo:

 pacote-modbus

 

 

Desconsideremos o campo Start e End (geralmente são tratados por hardware), vejamos que o protocolo tem uma estrutura comum, com exceção do campo Data, que pode ser variável. Vamos assumir, para simplificar o raciocínio, que saibamos que o tamanho do campo Data no seu máximo uso seja conhecido. A nossa UART já tem o buffer circular para capturar bytes que venham entre Start e End. Ela lê do registrador de hardware e adiciona ao buffer circular, porém ao montarmos um pacote MODBUS e enviar para processamento, pode ser que outro pacote já esteja pronto para chegar. Não seria então muito melhor retirar todos os bytes do buffer circular e copiar a mensagem pronta para ser processada na ordem em que elas chegam? Eis onde a fila circular deve entrar. Com ela cada slot seria um comando MODBUS completo e ordenados do mais antigo para o mais recente, permitindo que a aplicação se preocupe em apenas uma coisa, retirar a mensagem completa e executar o comando. Esse fato ajuda a evitar o uso excessivo de CPU e permite que o uso de eventos como de fila vazia desabilitem o decodificador quando ele não precisa ser usado.

 

Assim uma fila circular tem grande aplicação em gestores de protocolos de comunicação complexos, ou seja, que não tratam cadeia de bytes, mas mensagens pré-formatadas e com uma sequência definida. Além disso, a fila circular também pode ser utilizada para agendamento de tarefas de sistemas operacionais da mesma forma que o buffer circular. Porém, como possui sua estrutura em forma de slots, ela será capaz de lidar com estruturas de dados complexas como um Task Control Block (estrutura de dados que contém todas as informações das tarefas a serem executadas).

 

 

Exemplo de Fila Circular

 

A implementação apresentada traz as rotinas básicas para criação e manipulação de uma fila circular. Um exemplo de uso também está sendo fornecido para ajudar o usuário em questões básicas de criação, inserção e remoção de dados, para que este possa em seguida usar em suas próprias aplicações. O módulo fornecido está o mais independente de arquitetura possível sendo que seu desempenho da cópia dos dados depende da implementação da função memcpy geralmente otimizada na LIBC fornecida com a toolchain favorita do usuário. Abaixo temos os arquivos:

 

Perdoem-me pelos comentários em inglês, utilizo de forma a tornar o acesso a esse tipo de documento universal (inclusive por estar em um repositório público). No arquivo circ_queue.h o usuário terá à disposição todas as rotinas para instanciar e utilizar sua fila de forma personalizada, ao final uma macro (da mesma forma que no bufffer circular) também fica à disposição para que seja possível inicializar uma estrutura totalmente inicializada e pronta para uso. Adicionalmente as rotinas de checagem estão providas para verificação de queue cheia ou vazia, além da rotina de flush, que efetua sua limpeza.

 

Abaixo daremos uma olhada na implementação (como de costume). Vejam:

 

 

Vejam que a implementação da Fila Circular está muito similar ao Buffer Circular, além da proteção implícita a vazamento de memória com uso do incremento circular. Ao leitor mais atento, a principal diferença encontra-se nas linhas 18 e 19 para inserção, e das linhas 51 a 57 para remoção. Vejam que no Buffer Circular usávamos os índices para acessar diretamente o byte especificado por ele, porém a queue está subdivida logicamente em slots, ou seja, pequenas áreas de memória menores combinadas em uma única área de memória. Logo, para correto acesso, utilizamos os índices em conjunto com o tamanho de cada slot, multiplicando-os entre si e obtendo o início da memória de slot. Além disso, logicamente são reservados 4 bytes para cada slot que guardam a quantidade de dados inseridas nele,  e ao efetuar um retrieve, a quantidade de bytes será devolvida para que o usuário saiba quanto tinha no slot acessado.

 

 

Conclusão

 

O buffer circular mostra-se versátil, podendo ter sua estrutura usada para construção de tipos de dados mais complexos, como o exemplo da Fila Circular, uma estrutura segura e eficiente para armazenamento temporário com o adicional de prover um bloco de memória associado para lidar com tipos de dados maiores e mais complexos. A implementação simples provida nesse artigo vai de encontro às necessidades de uso em pilhas de comunicação para processamento de mensagens que são extraídas de controladores on-chip como USB, UART, CAN, além de protocolos escritos em cima dessas interfaces.

 

Espero que o leitor tenha gostado. Deixe seus comentários abaixo. Até a próxima!

 

 

Links úteis

 

Repositório no Github com o módulo e exemplo, clique aqui.

Desenvolvedor, agnóstico em termos de tecnologia, portador de sangue maker. Procura exaustivamente por formas de transformar a ciência "engessada" das universidades no "simples de fazer" para o mundo real. Compra o pão com o dinheiro que ganha brincando de fazer software de tempo real para smart wearables sem esquecer o background em eletrônica. Possui interesses em tópicos como processamento digital de sinais, software de tempo real (bare-metal ou OS hosted) e fusão de sensores e hardware para aquisição de dados. Por ai dizem que sou mestre em engenharia elétrica(USP) e tecnólogo em eletrônica oriundo da FATEC.

Deixe um comentário

Seja o Primeiro a Comentar!

Notificar
avatar
 
wpDiscuz