gerenciamento de memória baseada Região - Region-based memory management


Da Wikipédia, a enciclopédia livre

Em ciência da computação , gerenciamento de memória baseada em região é um tipo de gerenciamento de memória em que cada objeto alocado é atribuído a uma região . A região, também chamado de zona , Arena , área , ou contexto de memória , é uma coleção de objetos alocados que podem ser eficientemente desalocadas tudo de uma vez. Como alocação de pilha , regiões facilitar a alocação e desalocação de memória com baixo custo; mas eles são mais flexíveis, permitindo que os objetos a viver mais tempo do que o quadro de 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 forma semelhante a como os quadros de pilha são normalmente alocados.

Exemplo

Como um simples exemplo, considerar o seguinte C código que aloca e, em seguida, desaloca uma lista ligada estrutura de dados:

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 seja necessário muitas operações para construir a lista encadeada, ele pode ser destruído rapidamente numa única operação, destruindo a região em que os nós foram alocados. Não há necessidade de percorrer a lista.

Implementação

Regiões explícitas simples são simples de implementar; a seguinte descrição é baseada em Hanson. Cada região é implementado como uma lista ligada de grandes blocos de memória; cada bloco deve ser grande o suficiente para servir muitas alocações. O bloco atual mantém um ponteiro para a próxima posição livre no bloco, e se o bloco está cheio, um novo é alocado e adicionado à lista. Quando a região é desalocada, o ponteiro próximo livre de posição é reposto para o início do primeiro bloco, e a lista de blocos podem ser reutilizados para a próxima região a ser criado. Alternativamente, quando uma região é desalocada, a sua lista de blocos pode ser anexado a um freelist global de que outras regiões podem depois alocar novos blocos. Com este esquema simples, não é possível retirar atribuição de objetos individuais em regiões.

O custo total por byte alocado deste esquema é muito baixo; quase todas as alocações envolvem apenas uma comparação e uma atualização para o ponteiro-next-livre posição. Desalocá uma região é uma operação de tempo constante, e é feito raramente. Ao contrário, em típicos de recolha de lixo sistemas, não há necessidade para marcar os dados com o seu tipo.

História e conceitos

O conceito básico de regiões é muito antiga, primeiro aparecendo tão cedo quanto 1967 em Package AED armazenamento gratuito de Douglas T. Ross, em que a memória foi dividida em uma hierarquia de zonas; cada zona tinha seu próprio alocador, e uma zona poderiam ser libertados todos de uma vez, fazendo zonas utilizável como regiões. Em 1976, o PL / I padrão incluído o tipo de dados área. Em 1990, Hanson demonstrou que as regiões explícitas em C (que chamou arenas) poderia atingir um desempenho tempo por byte atribuído superior ao mesmo o mais rápido conhecido mecanismo de alocação de pilha. Regiões explícitas foram fundamentais na concepção de uma série de projetos de software iniciais baseadas em C, incluindo o Apache HTTP Server , o que lhes chama piscinas, eo PostgreSQL sistema de gerenciamento de banco de dados, o que lhes chama contextos de memória. Como alocação de pilha tradicional, estes esquemas não oferecem segurança de memória ; é possível para um programador para acessar uma região depois de ser desalocada através de um apontador pendente , ou para se esqueça de desalocar a região, causando um vazamento de memória .

região inferência

Em 1988, os pesquisadores começaram a investigar como usar as regiões para alocação de memória segura através da introdução do conceito de inferência região , onde a criação e deallocation das regiões, bem como a atribuição de expressões alocação estática individuais para determinadas regiões, é inserido pelo compilador em em tempo de compilação. O compilador é capaz de fazer isso de tal forma que ele pode garantir pendurado ponteiros e vazamentos não ocorrem.

Num trabalho mais cedo por Ruggieri e Draco, uma região é criado no inicio de cada função e desatribuído no final. Eles, então, usar a análise de fluxo de dados para determinar uma vida para cada expressão alocação estática, e atribuí-lo à região mais jovem que contém toda a sua vida.

Em 1994 este trabalho foi generalizada em um trabalho seminal de Tofte e Talpin para apoiar tipo de polimorfismo e funções de ordem superior no ML padrão , a programação funcional da linguagem, usando um algoritmo diferente com base no tipo de inferência e os conceitos teóricos de polimórficos tipos de região ea cálculo região . Seu trabalho introduziu uma extensão do cálculo lambda , incluindo regiões, acrescentando duas construções:

e 1 a ρ: Calcula-se o resultado da expressão de e 1 e armazená-la na região ρ;
ρ letregion em e 2 final: Criar uma região e ligá-la para P; avaliar e 2 ; em seguida, desaloque a região.

Devido a esta estrutura sintática, regiões estão aninhados , significa que, se R 2 for criada após r 1 , deve também ser desatribuído antes de r 1 ; o resultado é uma pilha de regiões. Além disso, as regiões devem ser desalocada na mesma função em que são criados. Estas restrições foram relaxados por Aiken et al.

Este cálculo lambda estendido foi destinado a servir como uma memória de segurança comprovadamente representação intermediária para a compilação de programas ML padrão em código de máquina, mas a construção de um tradutor que iria produzir bons resultados em grandes programas enfrentou uma série de limitações práticas que tiveram que ser resolvidos com o novo análises, incluindo lidar com as chamadas recursivas, cauda chamadas recursivas, e eliminando regiões que continham apenas um único valor. Este trabalho foi concluído em 1995 e integrado no Kit ML, uma versão do ML com base na alocação região no lugar de coleta de lixo. Isso permitiu uma comparação direta entre os dois em programas de teste de médio porte, produzindo resultados muito diferentes ( "entre 10 vezes mais rápido e quatro vezes mais lento"), dependendo de como "amigável-região", o programa foi; compilar vezes, no entanto, estavam na ordem de minutos. O Kit de ML foi, eventualmente, dimensionado para grandes aplicações com duas adições: um esquema para a compilação separado de módulos, e uma técnica híbrido que combina inferência região com traçando a recolha de lixo.

Generalização para novos ambientes de idiomas

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

  • Várias extensões para o linguagem de programação C :
    • O C dialeto segura Cyclone , que, entre muitas outras características 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 chamado RC foi implementado que usa regiões explicitamente gerenciados, mas também utiliza a contagem de referência em regiões para garantir a segurança de memória, garantindo que nenhuma região é libertado prematuramente. Regiões diminuir a sobrecarga de contagem de referência, uma vez que as referências internas para regiões não exigem contagem a ser atualizado quando eles são modificados. RC inclui um sistema de tipo estático explícito para regiões que permite que algumas atualizações contagem de referência a ser eliminado.
    • Uma restrição de C chamados programas limites de controlo-C para usar regiões (e apenas uma única região de cada vez), como parte do seu desenho para garantir a segurança estaticamente memória.
  • Regiões foram implementadas para um subconjunto de Java , e tornou-se um componente crítico do gerenciamento de memória em tempo real Java , que os combina com tipos de propriedade para demonstrar objeto encapsulamento e eliminar tempo de execução verifica no deallocation região. Mais recentemente, um sistema semi-automático foi proposto para inferir regiões em aplicações Java incorporados em tempo real, combinando um tempo de compilação análise estática, uma política de alocação de região de tempo de execução, e dicas programador. As regiões são um bom ajuste para computação em tempo real porque sua sobrecarga tempo é estaticamente previsível, sem a complexidade de coleta de lixo incremental.
  • Eles foram implementadas para os lógica de programação línguas Prolog e Mercury , estendendo de Tofte e Talpin modelo de inferência região para apoiar retrocesso e cortes.
  • Gerenciamento de armazenamento baseado em região é usado em todo o linguagem de programação paralela parasail . Devido à falta de ponteiros explícitos em parasail, não há necessidade de contagem de referência.

desvantagens

Os sistemas que utilizam regiões podem enfrentar problemas em que regiões se tornam muito grande antes de serem desalocados e contêm uma grande proporção de dados mortos; estes são comumente chamados de "vazamentos" (mesmo que eles são eventualmente libertados). vazamentos eliminando pode envolver a reestruturação do programa, normalmente através da introdução de regiões novas, mais curto tempo de vida. Depuração este tipo de problema é especialmente difícil em sistemas usando inferência região, onde o programador deve compreender o algoritmo de inferência subjacente, ou examinar a representação intermediária detalhado, para diagnosticar o problema. Trace coletores de lixo são mais eficazes na desalocá este tipo de dados em tempo hábil, sem alterações de programa; esta era uma justificação para sistemas região / GC híbridos. Por outro lado, Traçar coletores de lixo também podem apresentar vazamentos sutis, se as referências são mantidas a dados que nunca serão usados ​​novamente.

Gerenciamento de memória baseada em região funciona melhor quando o número de regiões é relativamente pequeno e cada um contém muitos objetos; programas que contêm muitas regiões esparsas vai expor fragmentação interna , levando a memória desperdiçada e uma sobrecarga de tempo para a gestão região. Mais uma vez, na presença de inferência região este problema pode ser mais difícil de diagnosticar.

métodos híbridos

Como mencionado acima, RC utiliza um híbrido de regiões e a contagem de referência , o que limita a sobrecarga de contagem de referência uma vez que as referências internas para regiões não necessitam de ser actualizadas para as contagens quando são modificados. Da mesma forma, alguns marca-região métodos híbridos combinam rastreamento coleta de lixo com as regiões; estes função dividindo a pilha em regiões, realizando uma passagem marca de varrimento em que quaisquer regiões que contenham objectos vivo são marcados, e, em seguida, libertando quaisquer regiões não marcados. Estes exigem desfragmentação contínuo para manter a eficácia.

Referências