Entendendo a alocação dinâmica de memória no FreeRTOS

IAR com o FreeRTOS Comunicação entre tarefas alocação dinâmica de memória
Este post faz parte da série Projeto com FreeRTOS. Leia também os outros posts da série:

Alocação dinâmica de memória

 

Em sistemas com pouca memória RAM disponível, a alocação dinâmica de memória permite disponibilizar regiões sob demanda. Quando esta memória não for mais necessária, poderá ser liberada e disponibilizada para uso futuro em outra aplicação. Desta forma, um sistema com pouca memória consegue executar um grande número de atividades cujas demandas de memória somadas são muito superiores ao total disponível no sistema.

 

Em sistemas mais complexos equipados com sistemas operacionais como o Linux, a alocação de memória é feita pela função malloc() e a desalocação pela função free(). Nos sistemas embarcados mais simples, a biblioteca padrão do compilador disponibiliza essas funções, mas elas possuem algumas desvantagens como: baixa velocidade de execução, não serem thread safe e tempo de execução não determinístico.

 

Para suprir a necessidade por este tipo de funcionalidade, o FreeRTOS implementa formas simples de gerenciar a memória RAM através das funções pvPortMalloc() e vPortFree(). Os nomes das funções são diferentes do padrão para evitar confusão com a versão disponibilizada pela biblioteca do compilador.

 

 

Algoritmos de alocação dinâmica de memória

 

Antes de apresentar o funcionamento da alocação dinâmica de memória dinâmica no FreeRTOS, vamos conhecer alguns dos algoritmos de alocação de memória mais comuns.

 

Em sistemas que utilizam alocação dinâmica de memória, toda a memória RAM livre é denominada de heap. O heap pode ser visualizado como uma grande região de memória livre. Uma tarefa do sistema pode solicitar a alocação de uma determinada quantidade de memória através da função malloc(). Esta função irá selecionar uma região do heap, marcá-la como “em uso” e disponibilizar para a tarefa que solicitou a memória. A partir deste ponto, apenas a tarefa em questão tem acesso a este pedaço de memória. A tarefa poderá desalocar esta memória a qualquer momento chamando a função free(). Esta função irá desalocar a região de memória e retorná-la ao heap disponibilizando-a para uso futuro por outras tarefas.

 

Normalmente o heap é organizado em blocos de memória RAM com tamanhos fixos ou variados (isso depende muito da construção do sistema). O sistema mantém uma lista de todos os blocos livres de forma a facilitar a localização destes blocos. A escolha do bloco de heap que será alocado é feita utilizando diversos algoritmos tais como First Fit, Best Fit, Worst Fit. Caso o bloco selecionado pelo algoritmo seja maior do que o tamanho desejado, o tamanho solicitado será alocado e um novo bloco será criado com o espaço restante do bloco original. Este novo bloco será inserido na lista de blocos livres para uso futuro.

 

Nas próximas subseções farei uma apresentação dos três algoritmos mencionados acima.

 

 

First Fit

 

Este algoritmo percorre a lista de blocos livres a partir do início e aloca o primeiro bloco maior do que a quantidade de bytes que se deseja alocar. Este algoritmo é mais rápido que os demais, pois não necessita que o sistema percorrera toda a lista de blocos de memória. Por outro lado, este algoritmo não oferece a alocação mais eficiente possível.

 

O funcionamento do algoritmo First Fit pode ser ilustrado com o exemplo da Figura 1. Nesta figura os blocos de memória ocupados são representados em azul enquanto que os blocos livres estão representados em branco. Para alocar um bloco com 7 KB, por exemplo, a lista de blocos livres será percorrida, a partir do início, em busca de um bloco igual ou maior do que 7 KB. O primeiro bloco livre tem 6 KB, o que é insuficiente para alocar a memória desejada. Já o segundo bloco, que tem 12 KB, é grande o suficiente para alocar os 7 KB desejados. Nesta situação, os primeiros 7 KB do bloco serão alocados para a tarefa que solicitou a alocação da memória. Os 5 KB restantes serão transformados em um novo bloco que será inserido na lista de blocos livres permitindo o seu uso futuro.

 

Exemplo de alocação dinâmica de memória no FreeRTOS
Figura 1: Exemplo de alocação dinâmica de memória usando algoritmo First Fit.

 

 

Best Fit

 

Este algoritmo sempre percorre toda a lista de bloco livres em busca do bloco que oferece a melhor alocação dinâmica de memória possível. No exemplo da Figura 1, o algoritmo Best Fit selecionará o bloco de 8 KB dividindo-o em dois blocos: um de 7 KB (que será disponibilizado para a tarefa solicitante) e um outro bloco de 1 KB, que será inserido na lista de blocos livres.

 

Esta estratégia permite uma alocação mais eficiente, mas exige mais tempo de processamento pois sempre necessita que toda a lista de blocos livres seja percorrida.

 

 

Worst Fit

 

No exemplo com o algoritmo Best Fit apresentado acima, foi criado um novo bloco de memória pequeno (1 KB) que dificilmente será alocado no futuro devido ao seu tamanho reduzido. Ao longo do tempo, o algoritmo Best Fit poderá levar à criação de um grande número de blocos pequenos. Numa situação deste tipo, poderá não ser possível alocar uma memória de um determinado tamanho por não existir um bloco grande o suficiente mesmo quando a soma de todos os blocos livres é maior do que a tamanho que se deseja alocar. Este fenômeno é conhecido como fragmentação.

 

O algoritmo Worst Fit tenta reduzir a fragmentação ao sempre alocar o maior bloco de memória disponível. Com isto, novos blocos de memória serão criados com tamanhos maiores. Aplicando o algoritmo Worst Fit ao exemplo da Figura 1, o bloco de 18 KB será selecionado e dividido em um bloco de 7 KB e um de 11 KB contendo o restante do espaço disponível.

 

Assim como o Best Fit, este algoritmo é mais lento do que o First Fit.

 

 

Tipos de alocação dinâmica de memória disponibilizados pelo FreeRTOS

 

O FreeRTOS disponibiliza cinco implementações diferentes de alocação de memória. O FreeRTOS permite, também, que o usuário implemente o seu algoritmo customizado se assim o desejar. As implementações disponibilizadas pelo FreeRTOS ficam no diretório Source/Portable/MemMang da estrutura de diretórios do código fonte. Cada um dos arquivos deste diretório contém uma das seguintes implementações: heap_1.c, heap_2.c, heap_3.c, heap_4.c, heap_5.c.  

 

Em cada um dos arquivos acima existe uma implementação das funções pvPortMalloc() e vPortFree(). Por este motivo, um destes arquivos deve sempre ser incluído em qualquer projeto com FreeRTOS.

 

Nas próximas seções serão descritas as particularidades de cada uma das cinco implementações.

 

 

Heap_1

 

Esta versão, a mais simples de todas, permite alocar mas não permite desalocar a memória, ou seja, a função pvPortFree() é vazia. Pode parecer estranho, mas em muitas situações isso não é um problema pois nestes sistemas as tarefas são criadas na inicialização e permanecem executando indefinidamente, ou seja, as estruturas que estas tarefas criam na memória não precisam ser desalocadas em momento algum.

 

Nesta implementação o heap é implementado na forma de um vetor declarado conforme abaixo:

 

static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];

 

Na inicialização do sistema, um ponteiro é apontado para a primeira posição do vetor. Este ponteiro indica a região do heap a partir da qual existe espaço disponível. Quando a função pvPortMalloc() for chamada, serão alocados tantos bytes quantos forem informados no parâmetro da função. O ponteiro do heap será reposicionado para o primeiro endereço após o final da região recem alocada.

 

Nesta implementação o tamanho total do heap é definido pela constante configTOTAL_HEAP_SIZE, que é declarada no arquivo de configuração FreeRTOSConfig.h.

 

É importante reforçar que esta versão só deve ser usada se não houver necessidade de remover da memória as tarefas, filas, semáforos, mutexes, e demais estruturas disponibilizadas pelo FreeRTOS.

 

Uma vantagem desta implementação é que o seu tempo de execução é determinístico, ou seja, é sempre constante. Essa característica é importante em sistemas com fortes restrições de tempo real. Uma outra vantagem desta implementação é a sua simplicidade e, consequentemente, o pouco uso de memória para controle do heap.

 

 

Heap_2

 

Esta implementação utiliza o algoritmo Best Fit e, ao contrário da versão Heap_1, permite que blocos de memória alocados anteriormente possam ser desalocados. Blocos que são desalocados não serão recombinados em blocos maiores, mesmo que sejam adjacentes a outros blocos livres. Isto significa que esta implementação poderá causar fragmentação do heap.

 

Nesta versão o heap é implementado da mesma forma como na versão Heap_1 e o seu tamanho é definido pela constante configTOTAL_HEAP_SIZE declarada no arquivo de configuração FreeRTOSConfig.h.

 

Alguns detalhes importantes desta implementação: 

  • Esta implementação deve ser usada quando tarefas, filas, semáforos, mutexes, etc, são constantemente alocados/desalocados. Deve-se levar em consideração a possibilidade de fragmentação;
  • Esta implementação não deve ser usada se os blocos de memória que vão ser alocados/desalocados têm tamanhos aleatórios como nos exemplos abaixo;
  • Se tarefas são criadas e posteriormente apagadas, mas sempre com o mesmo tamanho de pilha, então Heap_2 pode ser usado. Mas se o tamanho da pilha destas tarefas for diferente, então a memória disponível irá se tornar fragmentada em muitos blocos pequenos, impossibilitando eventualmente a alocação de novos blocos;
  • Fragmentação de memória irá ocorrer também, se filas com número de elementos diferentes forem criadas e depois apagadas constantemente;
  • Esta implementação não é determinística, ou seja, o seu tempo de execução não é constante e pode sofrer grandes variações se executada seguidas vezes. Isso deve ser levado em consideração em sistemas com restrições de tempo real.

 

 

Heap_3

 

Esta implementação simplesmente encapsula as funções malloc() e free() disponibilizadas pelo compilador, tornando-as thread safe. Para que o FreeRTOS possa utilizar as funções de alocação do compilador, é essencial que estas sejam thread safe.

 

Assim como o Heap_2, esta implementação é não determinística.

 

Para usar esta implementação, é necessário definir a localização e o tamanho do heap nas configurações do compilador/linker. Observe que se esta implementação for usada, o valor da constante configTOTAL_HEAP_SIZE será ignorado.

 

 

Heap_4

 

Esta implementação é semelhante ao Heap_2, com a diferença de que blocos adjacentes são combinados ao serem liberados. Da mesma forma como em Heap_2, o heap é implementado como um vetor e seu tamanho é definido pela constante configTOTAL_HEAP_SIZE.

 

Esta implementação pode ser usada quando tarefas, filas, semáforos e demais estruturas são alocadas/desalocadas continuamente, mesmo quando estas estruturas têm tamanhos diferentes.

 

Esta implementação reduz significativamente a ocorrência de fragmentação (em relação ao Heap_2), mas não a elimina por completo. O risco de fragmentação severa depende da sequência em que as variáveis são alocadas e desalocadas, não sendo possível determinar isso sem a realização de extensivos testes do sistema.

 

Assim como o Heap_2, este algoritmo não é determinístico.

 

 

Heap_5

 

Esta implementação utiliza o algoritmo First Fit e, assim como Heap_4, combina blocos consecutivos à medida que estes são desalocados. A grande diferença do Heap_4 para o Heap_5 é que este último permite que heap seja composto de mais de uma região de memória RAM não continua.

 

O Heap_5 deve ser inicializado chamando a função vPortDefineHeapRegions() que deve ser executado obrigatoriamente antes de alocar qualquer bloco de memória. A criação de qualquer componente do FreeRTOS (uma fila, um semáforo, uma tarefa, etc) irá sempre executar a função pvPortMalloc(). Portanto, a inicialização através da chamada da função vPortDefineHeapRegions() deve ser feita logo após a inicialização do hardware do sistema e antes da criação das tarefas.

 

vPortDefineHeapRegions() recebe como parâmetro um ponteiro para um vetor de estruturas do tipo HeapRegion_t. Esta estrutura é definida conforme abaixo:

 

typedef struct HeapRegion
{
	uint8_t *pucStartAddress;  /* ponteiro para o endereço de início de uma região da RAM*/
	size_t xSizeInBytes;  /* Tamanho da região */
} HeapRegion_t;

 

O vetor deve ser terminado por um item com os dois campos preenchidos com zero. As regiões de memória definidas no vetor devem necessariamente aparecer em ordem crescente de endereço. O trecho de código abaixo ilustra um exemplo de uso deste tipo vetor.

 

/* O exemplo abaixo aloca dois blocos de RAM para uso como heap. O primeiro bloco de 
0x10000 bytes inicia no endereço 0x80000000, e o segundo bloco com
0xa0000 bytes inicia no endereço 0x90000000.  O bloco que incia em 0x80000000 tem o menor endereço de inicio e portanto será o primeiro bloco a ser declarado no vetor. */

const HeapRegion_t xHeapRegions[] =
{
    { ( uint8_t * ) 0x80000000UL, 0x10000 },
    { ( uint8_t * ) 0x90000000UL, 0xa0000 },
    { NULL, 0 } /* Terminador do vetor */
};

/* Exemplo de chamada da função vPortDefineHeapRegions() para inicialização do heap */
vPortDefineHeapRegions( xHeapRegions );

 

Em vários modelos de microcontroladores existem regiões de memória RAM reservadas para uso por periféricos como controlador USB ou Ethernet. Estas regiões são reservadas para uso como buffers de recepção e transmissão de dados por estes periféricos, mas em aplicações em que estes periféricos não são usados, a memória RAM correspondente pode ser usada como heap. Normalmente estas regiões de memória RAM estão localizadas em regiões de endereço não adjacentes à memória RAM principal, por isto, nestes casos o Heap_5 é um interessante candidato para implementar o gerenciamento de memória.

 

Para o Heap_5 valem as mesmas observações que se aplicam ao Heap_4.

 

 

Referências

 

http://www.wou.edu/las/cs/csclasses/cs160/VTCS0/OS/Lessons/MemoryAllocation/index.html

http://www.freertos.org/a00111.html

Outros artigos da série

<< Comunicação entre tarefas no FreeRTOS: Filas
Este post faz da série Projeto com FreeRTOS. Leia também os outros posts da série:
NEWSLETTER

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

Obrigado! Sua inscrição foi um sucesso.

Ops, algo deu errado. Por favor tente novamente.

Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Gabor Sipkoi
Engenheiro eletrônico (UFPE) com mestrado em engenharia de sistemas (UPE) com 18 anos de experiencia com desenvolvimento de hardware e software para sistemas embarcados de tempo real. Tem grande experiencia com desenvolvimento de software para as famílias de microcontroladores ARM, PIC, Freescale e 8051. Atualmente é engenheiro consultor no CESAR - Centro de Estudos e Sistemas Avançados do Recife.

Deixe um comentário

avatar
 
  Notificações  
Notificar