Gestor de memória, parte IV

Se ainda se lembram, o nosso gestor de memória já divide blocos grandes em blocos mais pequenos para não desperdiçar memória. Mas esse processo traz um outro problema que também leva a algum desperdício de memória.

A heap fragmentada

Imaginem o seguinte cenário:

1. ao longo do tempo vamos alocando blocos, até chegar a um ponto em que temos cem blocos com 1 Kb, cinquenta deles livres e os outros cinquenta ocupados.
2. Agora queremos alocar um bloco de 20 Kb. Como não há nenhum bloco livre com pelo menos 20 Kb, temos de criar um bloco novo.

Estão a ver o problema? Nós tínhamos 50 blocos de 1 Kb livres, num total de 50 Kb (sem contar com os BlockInfos) e não conseguímos alocar 20 Kb! O problema é que os 50 Kb que temos livres estão fragmentados, isto é, separados em vários pequenos fragmentos (blocos).

A solução é fundir os blocos adjacentes. Se tivermos 20 blocos livres adjacentes podemos fundí-los num só e já temos o nosso bloco de 20 Kb.

Na realidade até temos um bloco com mais de 20 Kb, porque até aqui tinhamos 20 Kb em espaço livre, mais 20 BlockInfos. Agora só temos um BlockInfo e o resto tudo livre: 20 Kb + 19*sizeof(BlockInfo). Também temos de ter isto em consideração.

A solução: como?

Antes de decidirmos quando é que devemos fazer a fusão dos blocos, vamos tratar do “como”. Reparem que como não conseguimos navegar para trás na nossa estrutura da heap não podemos fazer fusão com blocos anteriores, só com os seguintes:

int merge_next(BlockInfo* block);

O objectivo desta função é fundir um bloco com o seguinte, se possível. O valor de retorno diz se foi ou não efectuada a fusão.

A implementação é bastante simples. Basta mudar o tamanho do primeiro bloco por forma a encompassar o bloco seguinte. O tamanho novo será então a soma dos tamanhos de ambos os blocos, mais o tamanho do BlockInfo do segundo bloco, porque este deixa de existir:

    // Já devem conseguir perceber esta instrução
    // (aritmética de apontadores mais uma vez)
    BlockInfo* next =
        block + 1 + block->length / sizeof(BlockInfo);

    if(next->isFree)
        block->length += next->length + sizeof(BlockInfo);

    return next->isFree;

E esta função já funde dois blocos adjacentes.

A solução: quando?

Quando é que vamos fazer a fusão? Temos duas boas oportunidades para o fazer:

• quando libertamos um bloco, se o seguinte for livre, podemos fundí-los imediatamente (na função myfree).
• quando percorremos a heap à procura de um bloco livre com tamanho suficiente, podemos ir fundindo blocos sempre que possível (na função mymalloc).

Não são ambas mutuamente exclusivas. Podemos simplesmente fundir os blocos em ambas as situações, e é o que vamos fazer. Mas primeiro vamos analisar as vantagens de uma em relação à outra.

A primeira é bastante simples e rápida enquanto a segunda adiciona um processamento extra à nossa pesquisa. Mas a primeira nem sempre efectua a fusão, porque não podemos fundir com o bloco anterior. A segunda efectua sempre todas as fusões possíveis que encontre.

Porque é que vamos efectuar a fusão em ambos as situações?

1. Ao fundirmos na myfree estamos a poupar trabalho na pesquisa, reduzindo o número de fusões que efectuariamos nessa operação.
2. Ao fundirmos na mymalloc estamos a tratar dos casos que a myfree não consegue tratar.

Ao fazermos isto também estamos a reduzir o tempo de pesquisa pelos blocos. Isto porque como já efectuamos a divisão de blocos e agora vamos fundir os blocos livres, teremos sempre blocos livres maiores do que anteriormente e usamos apenas o espaço que precisamos. Assim encontramos espaço para novas alocações mais rapidamente, sem grande desperdício. Agora juntem o facto de abandonarmos a pesquisa quando encontramos o primeiro bloco com tamanho suficiente.

Teremos então pesquisas que encontram o que pretendem mais rápido e fundem os blocos que puderem pelo caminho. Como não se pesquisa sempre a heap de uma ponta à outra, efectuam-se poucas fusões durante a pesquisa. E como por vezes fundimos na myfree não ficamos com a parte final da heap muito fragmentada.

Vamos ficar com uma solução bastante razoável em termos de eficiência, tanto de tempo como de espaço. No entanto não é a solução óptima. A malloc da libc é muito mais complexa que isto! Mas para cumprir os objectivos do exercício a nossa serve.

Mãos à obra

Vamos começar pela fusão na myfree. Essa função era bastante curta (2 linhas). Agora não vai ficar muito mais longa:

void myfree(void* ptr)
{
    BlockInfo* usedBlock = ((BlockInfo*)ptr) - 1;

    usedBlock->isFree = 1;

    merge_next(usedBlock);
}

Já está. Agora para a mymalloc.

    BlockInfo* block = firstBlock;
    int found = 0;
    while(block != end && !found)
    {
        while(merge_next(block)); // Fundir enquanto possível
        if(block->length >= size)
        {
            found = 1;
        }
        block += (sizeof(BlockInfo) + block->length) / sizeof(BlockInfo);
    }

Notas finais

Eu considero este guião o mais difícil de todos. O código não é muito, mas pode ser pouco intuitivo para quem não está à vontade na aritmética de apontadores (pela minha experiência, muita gente). E é necessário delinear bem a solução antes de a implementar.

É uma daquelas coisas em que existe um abismo entre não perceber e perceber e é preciso um salto. Num momento não percebemos e então há algo que faz click! e as coisas tornam-se claras. Fico contente por vos ter ajudado a dar esse salto.

Queria agradecer a todos pelo apoio que têm dado nos comentários. Não tenham medo de apontar erros, fazer correções, críticas ou questões.