Gerenciamento de memória baseado em região - Region-based memory management

Na ciência da computação , o gerenciamento de memória baseado em região é um tipo de gerenciamento de memória no qual cada objeto alocado é atribuído a uma região . Uma região, também chamada de zona , arena , área ou contexto de memória , é uma coleção de objetos alocados que podem ser realocados ou desalocados com eficiência de uma só vez. Assim como a alocação de pilha , as regiões facilitam a alocação e desalocação de memória com baixa sobrecarga; mas são mais flexíveis, permitindo que os objetos vivam mais tempo do que o frame da pilha em que foram alocados. Em implementações típicas, todos os objetos em uma região são alocados em um único intervalo contíguo de endereços de memória, de maneira semelhante a como os quadros de pilha são normalmente alocados.

Exemplo

Como um exemplo simples, considere o seguinte código C que aloca e desaloca uma estrutura de dados de lista vinculada: 

Region *r = createRegion();
ListNode *head = NULL;
for (int i = 1; i <= 1000; i++) {
    ListNode* newNode = allocateFromRegion(r, sizeof(ListNode));
    newNode->next = head;
    head = newNode;
}
// ...
// (use list here)
// ...
destroyRegion(r);

Embora muitas operações sejam necessárias para construir a lista vinculada, ela pode ser desalocada rapidamente em uma única operação, destruindo a região na qual os nós foram alocados. Não há necessidade de percorrer a lista.

Implementação

As regiões explícitas simples são fáceis de implementar; a descrição a seguir é baseada no Hanson. Cada região é implementada como uma lista vinculada de grandes blocos de memória; cada bloco deve ser grande o suficiente para atender a muitas alocações. O bloco atual mantém um ponteiro para a próxima posição livre no bloco e, se o bloco for preenchido, um novo é alocado e adicionado à lista. Quando a região é desalocada, o ponteiro da próxima posição livre é redefinido para o início do primeiro bloco e a lista de blocos pode ser reutilizada para a próxima região alocada. Alternativamente, quando uma região é desalocada, sua lista de blocos pode ser anexada a uma lista independente global a partir da qual outras regiões podem alocar novos blocos posteriormente. Com qualquer um dos casos desse esquema simples, não é possível desalocar objetos individuais em regiões.

O custo geral por byte alocado deste esquema é muito baixo; quase todas as alocações envolvem apenas uma comparação e uma atualização para o próximo ponteiro de posição livre. A desalocação de uma região é uma operação de tempo constante e raramente é feita. Ao contrário dos sistemas de coleta de lixo típicos , não há necessidade de marcar os dados com seu tipo.

História e conceitos

O conceito básico de regiões é muito antigo, aparecendo pela primeira vez em 1967 no AED Free Storage Package de Douglas T. Ross, no qual a memória era particionada em uma hierarquia de zonas; cada zona tinha seu próprio alocador e uma zona podia ser liberada de uma vez, tornando as zonas utilizáveis ​​como regiões. Em 1976, o padrão PL / I incluía o tipo de dados AREA. Em 1990, Hanson demonstrou que regiões explícitas em C (que ele chamou de arenas) podiam atingir desempenho de tempo por byte alocado superior até mesmo ao mecanismo de alocação de heap conhecido mais rápido. As regiões explícitas foram instrumentais no design de alguns dos primeiros projetos de software baseados em C, incluindo o Apache HTTP Server , que os chama de pools, e o sistema de gerenciamento de banco de dados PostgreSQL , que os chama de contextos de memória. Como a alocação de heap tradicional, esses esquemas não fornecem segurança de memória ; é possível que um programador acesse uma região após ela ter sido desalocada por meio de um ponteiro pendente ou se esqueça de desalocar uma região, causando um vazamento de memória .

Inferência de região

Em 1988, os pesquisadores começaram a investigar como usar regiões para alocação de memória segura, introduzindo o conceito de inferência de região , onde a criação e desalocação de regiões, bem como a atribuição de expressões de alocação estática individuais para regiões particulares, é inserida pelo compilador em tempo de compilação. O compilador é capaz de fazer isso de uma forma que pode garantir que ponteiros pendentes e vazamentos não ocorram.

Em um trabalho anterior de Ruggieri e Murtagh, uma região é criada no início de cada função e desalocada no final. Em seguida, eles usam a análise de fluxo de dados para determinar o tempo de vida de cada expressão de alocação estática e a atribuem à região mais recente que contém todo o seu tempo de vida.

Em 1994, este trabalho foi generalizado em um trabalho seminal de Tofte e Talpin para suportar polimorfismo de tipo e funções de ordem superior em Standard ML , uma linguagem de programação funcional , usando um algoritmo diferente baseado em inferência de tipo e os conceitos teóricos de tipos de região polimórfica e o cálculo da região . Seu trabalho introduziu uma extensão do cálculo lambda incluindo regiões, adicionando duas construções:

e 1 em ρ: Calcule o resultado da expressão e 1 e armazene-o na região ρ;
letregion ρ in e 2 end: Crie uma região e ligue-a a ρ; avalie e 2 ; em seguida, desalocar a região.

Devido a essa estrutura sintática, as regiões são aninhadas , o que significa que se r 2 for criado após r 1 , ele também deverá ser desalocado antes de r 1 ; o resultado é uma pilha de regiões. Além disso, as regiões devem ser desalocadas na mesma função em que foram criadas. Essas restrições foram relaxadas por Aiken et al.

Este cálculo lambda estendido foi planejado para servir como uma representação intermediária comprovadamente segura de memória para compilar programas de ML padrão em código de máquina, mas construir um tradutor que produziria bons resultados em grandes programas enfrentou uma série de limitações práticas que tiveram que ser resolvidas com novos análises, incluindo lidar com chamadas recursivas, chamadas finais e eliminar regiões que continham apenas um único valor. Este trabalho foi concluído em 1995 e integrado ao ML Kit, uma versão do ML baseada na alocação por região no local da coleta de lixo. Isso permitiu uma comparação direta entre os dois em programas de teste de médio porte, produzindo resultados amplamente variados ("entre 10 vezes mais rápido e quatro vezes mais lento"), dependendo de quão "amigo da região" o programa era; os tempos de compilação, entretanto, eram da ordem de minutos. O ML Kit foi finalmente dimensionado para grandes aplicativos com duas adições: um esquema para compilação separada de módulos e uma técnica híbrida que combina inferência de região com rastreamento de coleta de lixo.

Generalização para novos ambientes de linguagem

Após o desenvolvimento do Kit de ML, as regiões começaram a ser generalizadas para outros ambientes de linguagem:

  • Várias extensões para a linguagem de programação C:
    • O dialeto C seguro Cyclone , que entre muitos outros recursos adiciona suporte para regiões explícitas e avalia o impacto da migração de aplicativos C existentes para usá-los.
    • Uma extensão para C chamada RC foi implementada que usa regiões gerenciadas explicitamente, mas também usa contagem de referência em regiões para garantir a segurança da memória, garantindo que nenhuma região seja liberada prematuramente. As regiões diminuem a sobrecarga da contagem de referência, uma vez que as referências internas às regiões não exigem que as contagens sejam atualizadas quando são modificadas. RC inclui um sistema de tipo estático explícito para regiões que permite que algumas atualizações de contagem de referência sejam eliminadas.
    • Uma restrição de C chamada Control-C limita os programas a usar regiões (e apenas uma única região por vez), como parte de seu projeto para garantir estaticamente a segurança da memória.
  • As regiões foram implementadas para um subconjunto de Java e se tornaram um componente crítico de gerenciamento de memória em Java em tempo real , que as combina com tipos de propriedade para demonstrar o encapsulamento de objetos e eliminar verificações de tempo de execução na desalocação de região. Mais recentemente, um sistema semiautomático foi proposto para inferir regiões em aplicativos Java em tempo real embutidos, combinando uma análise estática em tempo de compilação, uma política de alocação de região em tempo de execução e dicas do programador. As regiões são adequadas para computação em tempo real porque sua sobrecarga de tempo é estaticamente previsível, sem a complexidade da coleta de lixo incremental.
  • Eles foram implementados para as linguagens de programação lógica Prolog e Mercury estendendo o modelo de inferência de região de Tofte e Talpin para suportar retrocesso e cortes.
  • O gerenciamento de armazenamento baseado em região é usado em toda a linguagem de programação paralela ParaSail . Devido à falta de ponteiros explícitos no ParaSail, não há necessidade de contagem de referência.

Desvantagens

Os sistemas que usam regiões podem ter problemas em que as regiões se tornam muito grandes antes de serem desalocadas e contêm uma grande proporção de dados mortos; esses são comumente chamados de "vazamentos" (embora sejam eventualmente liberados). A eliminação de vazamentos pode envolver a reestruturação do programa, normalmente com a introdução de novas regiões de vida útil mais curta. A depuração desse tipo de problema é especialmente difícil em sistemas que usam inferência de região, onde o programador deve entender o algoritmo de inferência subjacente ou examinar a representação intermediária detalhada para diagnosticar o problema. Os coletores de lixo de rastreamento são mais eficazes na desalocação desse tipo de dados em tempo hábil, sem alterações no programa; esta foi uma justificativa para sistemas híbridos de região / GC. Por outro lado, rastrear coletores de lixo também pode exibir vazamentos sutis, se as referências forem mantidas para dados que nunca serão usados ​​novamente.

O gerenciamento de memória baseado em região funciona melhor quando o número de regiões é relativamente pequeno e cada uma contém muitos objetos; programas que contêm muitas regiões esparsas exibirão fragmentação interna , levando ao desperdício de memória e uma sobrecarga de tempo para o gerenciamento da região. Novamente, na presença de inferência de região, esse problema pode ser mais difícil de diagnosticar.

Métodos híbridos

Conforme mencionado acima, o RC usa um híbrido de regiões e contagem de referência , limitando a sobrecarga da contagem de referência, uma vez que as referências internas às regiões não exigem que as contagens sejam atualizadas quando são modificadas. Da mesma forma, alguns métodos híbridos de região de marca combinam o rastreamento da coleta de lixo com regiões; essas funções dividem o heap em regiões, realizando uma passagem de varredura de marcação na qual todas as regiões contendo objetos ativos são marcadas e, em seguida, liberando todas as regiões não marcadas. Eles requerem desfragmentação contínua para permanecerem eficazes.

Referências