Nenhum comentário

Memory Pool - Gerenciador de memória de bloco fixo real time

Memory Pool

 Olá caro leitor! Hoje vamos apresentar mais um recurso legal para que você tenha em seu conjunto de ferramentas e utilizar para resolver um problema do dia a dia. Em artigos passados eu apresentei a vocês um gerenciador de memória de tempo real, o TLSF, útil em momentos em que precisamos alocar e liberar memória dinamicamente. Mas existem situações em que a complexidade de implementação de um gerenciador de memória não justifica seu uso. Ou casos em que nossa aplicação precisa de um bloco de memória de tamanho fixo para armazenamento temporário (durante a extração de dados de um buffer circular, por exemplo). Existem ainda casos onde um gerenciador de memória não poderá ser opção por causa dos seus requisitos mínimos. O TLSF por exemplo não consegue trabalhar bem quando o bloco de memória é menor que 32 bytes.

 

Então, como proceder? Considere então utilizar uma Memory Pool, sempre que precisar de memória em tempo de execução, peça um bloco a ele, utilize e devolva para a Pool para que outra aplicação possa utilizar este bloco futuramente.

 

 

Memory o que? Explica isso ai direito

 

Memory pool, o nome em tradução livre pode sugerir algo como reserva de memória, depósito de memória ou algo similar. O Memory Pool é um tipo especial de gerenciador de memória frequentemente mais eficiente em tempo de execução do que um gerenciador clássico como o TLSF. Duas características são vitais para que isso seja realidade:

  • A Memory Pool vai ser logicamente dividida em blocos de tamanhos iguais;
  • A Memory Pool entrega apenas 1 bloco de memória por acesso.

 

Basicamente, podemos apenas requisitar da Memory Pool um único bloco por acesso, além disso o tamanho desse bloco sempre vai ser  fixo, o que a principio pode significar limitação e até inutilidade da sua existência, isso depende mais do perfil da aplicação e do hardware alvo e não das características citadas acima.

 

 

Abordagem tradicional de construção de memory pool

 

Como toda boa estrutura de dado, existem diversas formas para sua implementação, onde os ganhos entre simplicidade, eficiência em tempo de execução e armazenamento em memória variam de acordo com o objetivo inicial, mas dentre todas elas a forma mais comum de se implementar um bloco de memória se dá através de uma lista ligada. Vejam a figura abaixo:

 

memory-pool

 

A estrutura que contém os ponteiros Next e Data possui  o nome  de Node, uma cadeia de Nodes compõe a chamada lista ligada (teremos um post futuro sobre elas). Cada ponteiro Next aponta ao próximo Node da lista e cada ponteiro Data aponta para um bloco de memória logicamente subdividido no tamanho especificado pela aplicação. Ao alocar esse bloco, o ponteiro Data retorna o início de um novo bloco e o Node será retirado da lista ligada. Na devolução o Node será instanciado novamente e inserido na lista e seu ponteiro Data volta a possuir o endereço inicial do bloco.

 

Dependendo da implementação do algoritmo acima, a alocação e desalocação de memória pode atingir um nível de eficiência de execução em tempo constante, o que a principio tornaria uma solução ideal para uso em sistemas embarcados com restrições de memória e processamento.

 

Uma das desvantagens no entanto fica por conta de armazenar, além dos blocos de memória, um vetor de Nodes para composição da lista ligada e sua correta inicialização, impactando no footprint final de memória.

 

 

Trabalhando com bits e posição de bits

 

Quando a restrição de memória existe a ponto de que cada byte importa, uma alternativa que exige menos overhead na memory pool sempre será bem vinda. A abordagem da Memory pool que trazemos aqui possui a mesma capacidade de alocar e desalocar um bloco em O(1) (execução constante independente pra posição do bloco livre) e com a eliminação do uso de lista ligada em troca de uma limitação inicial: 

 

Cada Memory Pool só consegue fornecer 32 blocos do tamanho especificado, acima disso uma outra devera ser criada.

 

A limitação pode assustar de início mas pode-se estender o algoritmo para quantidades maiores de blocos disponíveis, porém duas Pools com 32 blocos são interessantes para a grande maioria  das aplicações. A grande vantagem se situa no footprint de memória final da solução. Como a lista ligada não se faz necessária, não precisaremos de 32 Nodes, apenas um pequeno cabeçalho que armazena quais blocos estão sendo utilizados e o tamanho de cada bloco, podendo ser ainda mais reduzida caso o tamanho do bloco não ultrapasse 256 bytes.

 

O funcionamento pode ser melhor compreendido se mostrarmos logo o código, vejam a interface: 

 

A interface em si é simples, possui as funções de alocação e devolução do bloco previamente alocado e a boa e velha macro para declaração da estrutura totalmente inicializada. Já na implementação vamos ter algo assim: 

 

Extramente simples, a função small_block_alloc() será quem retornará o bloco de memória livre, um bitmap de 32 bits mem->bitmap contém o estado de cada bloco, sendo 1 para livre e 0 para utilizado, realiza-se então uma pesquisa de zeros a esquerda que subtraída da largura do bitmap (em bits) menos 1 ira prover a posição do primeiro bit que contiver um bloco livre. Como sabemos o tamanho do bloco podemos obter seu offset partindo do enderenço inicial somado do tamanho de cada bloco pelo índice do bit que esta em 1, conseguindo endereceçar o bloco e retornar para aplicação. Vejam que a memory pool não precisa guardar nenhum estado, pois sabemos o endereco inicial e qual bit foi posto em 0 indicando seu uso. A função xxx_count_lead_zeros() foi provida para pesquisar o número de zeros à esquerda podendo ser otimizada se o processador possuir a instrução por hardware (CLZ). Essa instrução existe nos ARM Cortex-M3 e M4. Falar sobre a tabela DeBrujin e seu uso para contar zeros foge ao escopo deste artigo, e foi selecionado para ser uma solução genérica pois executa em tempo constante O(1).

 

Para liberar o bloco, a função small_block_free() deve ser chamada, onde o usuário passa o ponteiro para o bloco que ele requisitou previamente. Apesar de parecer estranho, o gerenciador de blocos não precisa saber nada sobre o bloco que ele recebeu, a característica de um bloco pertencer ou não a uma Memory Pool está no seu endereço inicial. Sabendo-se disso, o endereço base da Pool e dividindo pelo tamanho do bloco obteremos a posição do bit que devemos impor 1 indicando que esse bloco livre. Uma das vantagens dessa abordagem é que se o endereço estiver fora do range especificado ele não será aceito protegendo contra tentativas de liberar um bloco que não pertence a uma dada Pool.

 

 

Conclusão

 

O objetivo desse artigo foi apresentar uma alternativa ao conhecido gerenciador de memória utilizando uma técnica que não necessita de listas ou estruturas complexas, possuindo baixo footprint de overhead, além de oferecer alocação e desalocação de memória em tempo constante, ideal para uso em sistemas de tempo real. No link para repositório o usuário poderá encontrar um exemplo de como alocar, utilizar e desalocar uma Memory Pool. Gostaria de agradecer ao colega Mario Olofo pela discussão e ideias sobre alocadores de memória, que inspirou esse algoritmo. Espero que tenham gostado, bons projetos!

 

 

Links úteis

 

Repositório com o projeto no Github, clique aqui.

Outros artigos da série

<< Pilha Estática - Uma estrutura leve para sistemas embarcadosLista ligada - Estrutura "Zero Copy" - Parte 1 >>
Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Software » Memory Pool - Gerenciador de memória de bloco fixo real time
Talvez você goste:
Comentários:

Deixe um comentário

avatar
 
  Notificações  
Notificar

Séries



Outros da Série

Menu