Gerenciamento inteligente de memória com operações de tempo constante?

18

Vamos considerar um segmento de memória (cujo tamanho pode aumentar ou diminuir, como um arquivo, quando necessário) no qual você pode executar duas operações básicas de alocação de memória envolvendo blocos de tamanho fixo:

  • alocação de um bloco
  • liberando um bloco alocado anteriormente que não é mais usado.

Além disso, como requisito, o sistema de gerenciamento de memória não tem permissão para se deslocar pelos blocos alocados no momento: seu índice / endereço deve permanecer inalterado.

O algoritmo de gerenciamento de memória mais ingênuo incrementaria um contador global (com valor inicial 0) e usaria seu novo valor como endereço para a próxima alocação. No entanto, isso nunca permitirá reduzir o segmento quando restarem apenas alguns blocos alocados.

Melhor abordagem: mantenha o contador, mas mantenha uma lista de blocos desalocados (que podem ser feitos em tempo constante) e use-o como fonte para novas alocações, desde que não estejam vazias.

Qual o proximo? Existe algo inteligente que possa ser feito, ainda com restrições de alocação e desalocação de tempo constantes, que manteriam o segmento de memória o mais curto possível?

(Um objetivo pode ser rastrear o bloco não alocado no momento com o menor endereço, mas não parece possível em tempo constante ...)

Stéphane Gimenez
fonte
a verificação de uma lista não seria mais de tempo constante, pois a lista pode aumentar ou diminuir devido a algumas alocações / desalocações feitas anteriormente?
Sim
@ Sim, eu estava assumindo que é uma lista vinculada e com ela as operações seriam , porque você sempre trabalha apenas com a cabeça. O(N)
Sv16 /
Eu acho que sua “melhor abordagem” já utilizará a quantidade ideal de memória, ou seja, nunca alocará memória adicional se houver um bloco livre. Como você imagina que a abordagem "inteligente" melhoraria isso? Você quer dizer que ele deve ser alocado próximo ao início, para que haja uma chance melhor de reduzir o segmento após desalocações?
svick
@ Sim: Desculpe, talvez eu devesse ter usado o termo pilha (mas achei que poderia ser confuso), 'desalocar' é push e 'alocar' é pop, ou, no caso de falhar, basta voltar ao incremento do contador. Ambos são tempo constante.
Stéphane Gimenez
Você tem restrições em tempo real ou está bem com o tempo constante amortizado? As respostas provavelmente serão bem diferentes.
Gilles 'SO- stop be evil'

Respostas:

11

Com blocos de tamanho fixo, o que você descreveu é uma lista grátis . Essa é uma técnica muito comum, com o seguinte toque: a lista de blocos livres é armazenada nos próprios blocos livres. No código C, ficaria assim:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Isso funciona bem desde que todos os blocos alocados tenham o mesmo tamanho e esse tamanho seja múltiplo do tamanho de um ponteiro, para que o alinhamento seja preservado. Alocação e desalocação são em tempo constante (ou seja, em tempo constante como a memória acessa e adições elementares - em um computador moderno, um acesso à memória pode envolver falhas de cache e até memória virtual, portanto, acessos ao disco, portanto, o "tempo constante" pode ser bem grande). Não há sobrecarga de memória (nenhum ponteiro extra por bloco ou coisas assim; os blocos alocados são contíguos). Além disso, o ponteiro de alocação atinge um determinado ponto apenas se, ao mesmo tempo, muitos blocos precisarem ser alocados: como a alocação prefere usar a lista livre, o ponteiro de alocação é aumentado apenas se o espaço abaixo do ponteiro atual estiver cheio. Nesse sentido, técnica.

Diminuindoo ponteiro de alocação após uma liberação pode ser mais complexo, pois os blocos livres podem ser identificados com segurança apenas seguindo a lista livre, que os percorre em ordem imprevisível. Se a diminuição do tamanho do segmento grande, quando possível, for importante para você, você pode usar uma técnica alternativa, com mais sobrecarga: entre dois blocos alocados, você coloca um "furo". Os orifícios são vinculados a uma lista duplamente vinculada, em ordem de memória. Você precisa de um formato de dados para um furo, para poder localizar o endereço inicial do furo, sabendo onde ele termina e também o tamanho do furo, se souber onde o furo começa na memória. Então, ao liberar um bloco, você cria um furo que mescla com os furos seguinte e anterior, reconstruindo (ainda em tempo constante) a lista ordenada de todos os furos. A sobrecarga é de cerca de duas palavras do tamanho de ponteiro por bloco alocado; mas, a esse preço, você pode detectar com segurança a ocorrência de um "furo final", ou seja, uma ocasião para diminuir o tamanho do grande segmento.

Existem muitas variações possíveis. Um bom artigo introdutório é a Alocação Dinâmica de Armazenamento: Uma Pesquisa e Revisão Crítica de Wilson et al.

Thomas Pornin
fonte
4
Como você encontra os furos mais próximos a um local de desalocação em tempo constante?
Raphael
1
No segundo método que descrevo, um buraco é um cabeçalho (um par de ponteiros, para a lista de buracos) junto com o espaço para zero, um ou mais blocos de dados. Entre dois blocos alocados, sempre há um furo, mesmo que seja um micro-furo que consiste apenas em um cabeçalho de furo. Portanto, é fácil localizar os furos mais próximos: eles estão logo antes e logo após o slot. Obviamente, os micro-furos não fazem parte da lista gratuita (a lista de furos elegíveis para alocação). Outra maneira de visualizá-lo é que você adiciona um cabeçalho a todos os blocos e todos os furos (não micro) (a alocação no Ms-Dos de 16 bits funcionava dessa maneira).
9788 Thomas Thomin
4

Esta resposta é sobre técnicas genéricas de gerenciamento de memória. Perdi que a pergunta é sobre o caso em que todos os blocos têm o mesmo tamanho (e estão alinhados).


As estratégias básicas que você deve conhecer são o sistema de primeiro ajuste, próximo ajuste, melhor ajuste e o sistema de amigos . Eu escrevi um breve resumo uma vez para um curso que lecionei, espero que seja legível. Aponto para uma pesquisa bastante exaustiva .

Na prática, você verá várias modificações dessas estratégias básicas. Mas nada disso é tempo constante! Eu não acho que isso seja possível na pior das hipóteses, enquanto estiver usando uma quantidade limitada de memória.

rgrig
fonte
Interessante, eu tenho que ler isso em detalhes. No entanto, parece que esses sistemas lidam especificamente com alocações de tamanho não constantes, o que não é um problema com o qual eu seja confrontado.
Stéphane Gimenez
Certo. Desculpe, eu li muito rápido sua pergunta.
Rg1 /
O(lgn)
s / menor bloco livre / bloco livre no menor endereço /
rgrig
2

Você pode querer analisar a análise amortizada e, em particular, as matrizes dinâmicas. Mesmo que as operações não sejam realmente realizadas em tempo constante a cada passo, a longo prazo, parece que é o caso.

Gallais
fonte
2
E como exatamente as matrizes dinâmicas ajudarão na alocação de memória?
svick
Você (des) alocaria pedaços de células contíguas usando o mesmo tipo de algoritmo? Seu arquivo inteiro seria uma lista vinculada de partes cada vez maiores.
Gallais