Pilha Estática - Uma estrutura leve para sistemas embarcados

Ola meu caro leitor. Vamos continuar falando sobre pequenas estruturas de dados estáticas eficientes para uso em sistemas embarcados. Hoje vamos apresentar mais uma estrutura derivada do nosso Buffer circular, a Pilha Estática, em tradução livre do inglês Static stack. Como muitos devem saber a pilha é uma das primeiras estruturas de dados estudadas no meio acadêmico, tendo as mais diversas formas de implementar baseadas em listas e alocação dinâmica de memória. O objetivo desse artigo está em adicionar a essas abordagens uma forma adicional de implementação baseada em buffer circular, fácil de manipular.

 

 

O que é a Pilha Estática

 

A Pilha Estática é uma variante que utiliza da alocação estática para reservar a memória que será utilizada para armazenar dados, ou seja, não e necessário o uso de funções para reservar memória durante a execução. Toda a memória utilizada pela estrutura será reservada em tempo de compilação. A pilha estática, bem como toda a pilha, possui uma política de inserção e remoção de dados do tipo LIFO, em tradução livre postula-se: "O último dado a entrar no topo da pilha sempre será o primeiro a ser retirado".

 

Basicamente, de forma inversa à nossa Fila Circular (e Buffer), à medida que os slots são preenchidos eles empilham, de forma que o slot preenchido mais recentemente em relação aos demais será o primeiro a estar disponível para retirada. Essa operação é exatamente a mesma que o nosso processador utiliza para salvar variáveis e contexto durante a operação de um sistema operacional, através das conhecidas instruções push e pop. A explicação a respeito da operação da pilha pode ser ilustrada na figura abaixo:

 

Operação da Pilha
Figura 1: Operação da Pilha

 

 

Caso de Uso: Onde aplico uma pilha em geral?

 

Embora o processador já possua em hardware uma implementação de pilha, seu uso fica restrito ao salvamento de variáveis e registradores, além de dados utilizados pelo compilador que gerenciam o sistema de chamada de funções e troca de contexto, assim essa pilha tem seu uso bem restrito. Com a utilização de uma pilha podemos ilustrar o caso do gerenciador de janelas para uma aplicação que utiliza um display (o popular TFT), vejamos a figura abaixo:

 

Uso de Pilha em Display
Figura 2: Uso de Pilha em Display

 

Vejam que temos três janelas sobrepostas. Agora vem a pergunta, qual delas faz sentido processar primeiro? Provavelmente o usuário estará com sua atenção voltada para a última janela aberta, sendo necessário processar ela primeiramente, mas não podemos com isso descartar as demais, sendo necessário, no fechamento da mais recente, que retornemos o processamento para a janela mais recente anterior a essa, até que todas as janelas sejam processadas, ou fechadas. Vejam que essa política de atuação possui exatamente a mesma forma de operação do stack.

Logo, pilhas são excelentes para uso em aplicações que precisem guardar estados anteriores de forma temporária, também pode ser utilizada para alocação de blocos de memória fixos, sendo uma alternativa eficiente e leve ao uso do mecanismo tradicional de alocação dinâmica de memória. Usos incomuns da pilha também se situam em automatas como máquinas de estado, o uso da pilha permite que estados anteriores sejam guardados e em momentos convenientes sejam desempilhados ou checados, no caso de uma ação depender do estado (ou estados) anteriores.

 

 

Voce falou de pilha. E a pilha estática?

 

A Pilha Estática como já citado é uma versão que não precisa de alocação dinâmica, todos os seus parâmetros são definidos em tempo de compilação, o que exige do usuário que conheça quanto de memória (ou slots) ele precisa reservar. Existem diversas formas de implementação de uma pilha estática. A implementação aqui apresentada faz uso do nosso conhecido buffer circular para ganharmos também a proteção contra "memory leak", ou vazamento de memória, implícita dos buffers circulares. Vejamos abaixo a interface de nossa pilha estática:

 

 

A interface possui a mesma forma das apresentadas nos artigos anteriores, descrevemos a estrutura de controle do nossa pilha, e provemos as funções de inserção e remoção de dados, onde toda a política é gerenciada automaticamente, as funções de checagem para uso quando a pilha estiver cheia e vazia facilitam operações de sincronização e durante o desenvolvimento, temos ainda a clássica macro para declaração da pilha totalmente inicializada e pronta para uso. Vejamos agora a implementação:

 

 

A implementação da pilha estática no que diz respeito à localização na memória reservada, é exatamente igual ao que apresentamos nas demais estruturas dos artigos anteriores, a politica LIFO é gerenciada pelas linhas 35, 56 e 72 a 76. Percebam que a atualização dos índices é um pouco mais complicada que nos sistemas que usam politica FIFO, os índices de entrada e saída de dados caminham para o mesmo sentido, porém estão juntos. O índice de saída de dados sempre aponta ao primeiro dado disponível no topo do stack, já o de entrada (put_index) aponta ao primeiro slot livre (desde que exista espaço), por isso a atualização do primeiro, depende do segundo. Na remoção, diferente do método FIFO, que basta incrementar os índices, precisamos fazer com que eles "caminhem" no sentido inverso da inserção, logo introduzimos a você leitor a operação de decremento circular, que possui um caso especial que precisa ser tratado, ou seja, quando o índice de inserção (put_index) tem valor igual a zero, o que gera o código extra pra incremento e decremento que aparecem nessas linhas.

 

 

Conclusão

 

Além de estruturas com politica FIFO, temos também as estruturas com politica LIFO, no artigo de hoje apresentamos uma das mais populares, o stack ou pilha, além disso provemos ao leitor uma abordagem diferente de sua implementação, baseado em algo que já conhecemos de artigos anteriores, proporcionando um módulo leve, eficiente e protegido contra vazamento de memória. No link, com repositório para o GitHub existe uma aplicação exemplo que utiliza todas as funções e demonstra a utilização básica do nossa Pilha Estática. Espero que mais essa estrutura seja útil. Bons projetos!

 

 

Links uteis

 

Acesse aqui o repositório no Github contendo a implementação e aplicação exemplo.

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