Gestor de memória, parte III

No segundo exercício é pedida uma versão melhorada do gestor de memória do primeiro exercício. São pedidas duas coisas: fusão de blocos livres e optimização das procuras.

O que não estava muito bem

No gestor de memória simples que implementámos anteriormente, quando não existe um bloco com tamanho suficiente é alocado um novo bloco com do tamanho que foi pedido. Quando existe um bloco com tamanho igual ou superior, esse bloco é utilizado. Por completo. Isto pode ser muito mau.

Se alocarmos um bloco de 1 Kb e depois o libertarmos ficamos com um bloco livre de 1 Kb. Se agora pedirmos um bloco de 10 bytes, o bloco de 1 Kb vai ser todo marcado como utilizado e desperdiçamos espaço. Este é um primeiro problema.

Um outro problema acontece precisamente na situação contrária. Primeiro alocamos 100 blocos de 10 bytes. Depois todos esses blocos são libertados. Se quisermos agora alocar um bloco de 1000 bytes, temos espaço livre suficiente, mas nenhum bloco tem 1000 bytes. O nosso gestor de memória vai simplesmente expandir a heap novamente e desperdiçar os 1000 bytes dos outros 100 blocos.

E depois temos o problema do overhead da estrutura de controlo dos blocos:

Por exemplo, se eu usar o mymalloc para armazenar seja o que for, por um exemplo uma estrutura que ocupa 10bytes, o mymalloc feito aqui vai sempre reservar 10bytes para a minha estrutura + 4bytes (por norma) para o inteiro isFree na estrutura BlockInfo. Ou seja, por cada chamada que eu faça com o mymalloc vou usar sempre sizeof(TIPO_DE_DADOS) + 4bytes...

No exemplo acima dos 100 blocos de 10 bytes, não teríamos apenas 1000 bytes livres depois de os libertar, mas sim 100*(10+8) = 1800 bytes, um grande desperdício.

A solução

Podemos resolver estes três problemas fundindo os blocos livres que sejam contíguos e utilizando blocos completos apenas quando necessário (dividindo os blocos em dois).

A fusão é assim:

Quando libertámos um bloco que seja adjacente a outro bloco livre, ficamos com um único bloco livre que cobre o espaço usado por ambos.

A divisão é assim:

Quando temos um bloco livre maior que o tamanho pretendido, reduzimos o tamanho desse bloco e criamos um bloco usado nesse espaço.

Divisão

A divisão é um processo “simples”. Em vez de simplesmente marcar um bloco como usado...

    if(found)
    {
        block->isFree = 0;

        return block + 1;
    }

...temos de usar apenas uma parte desse bloco:

    if(found)
    {
        use(block, size);

        return block + 1;
    }

E agora vamos definir a função:

    void use(BlockInfo* block, size_t size);

Mas primeiro vamos olhar melhor para o resultado esperado para perceber melhor o que temos de fazer:

Sendo r o espaço restante, p o tamanho pedido e o o tamanho original temos:

r = o – p – sizeof(BlockInfo)

O novo BlockInfo (o do bloco livre) vai ficar p + sizeof(BlockInfo) bytes á frente do bloco inicial.

Vamos então escrever a função use. Começamos por calcular r:

    size_t r = block->length - size - sizeof(BlockInfo);

Agora cuidado! Como block->length >= size podemos ter situações em que r <= 0! Quando isto acontece temos de usar o bloco inteiro.

    if(r <= 0)
    {
        block->isFree = 0;
    }

Para separar o bloco em dois, temos de criar um bloco novo p + sizeof(BlockInfo) bytes á frente e actualizar os tamanhos e a flag isFree.

    else
    {
        BlockInfo* newBlock = /* p + sizeof(BlockInfo) bytes á frente de block */;
        newBlock->length = r;
        newBlock->isFree = 1;

        block->length = size;
        block->isFree = 0;
    }

Só falta calcular a posição do novo bloco. Mais uma vez a aritmética de apontadores vem à baila. Não podemos escrever simplesmente escrever:

        BlockInfo* newBlock = block + p + sizeof(BlockInfo);

Não podemos porque isto não avança p + sizeof(BlockInfo) bytes mas sim p + sizeof(BlockInfo) tamanhos de um BlockInfo. Sempre que se faz adições ou subtracções a apontadores a unidade não é o byte. A unidade é o tipo do apontador.

Como o que nós queremos é avançar p + sizeof(BlockInfo) bytes temos de dividir p + sizeof(BlockInfo) pelo tamanho de um BlockInfo, assim:

        BlockInfo* newBlock = block + (size + sizeof(BlockInfo)) / sizeof(BlockInfo);

Não há problemas nenhuns com truncagens ou restos porque nós já garantimos anteriormente que só alocamos tamanhos múltiplos de sizeof(BlockInfo).

(Nota: Eu sei que já disse isto sobre a aritmética de apontadores antes, mas esta é a parte mais esquisita do exercício, por isso vale a pena repetir)

Ficamos então com isto:

void use(BlockInfo* block, size_t size)
{
    size_t r = block->length - size - sizeof(BlockInfo);
    if(r <= 0)
    {
        block->isFree = 0;
    }
    else
    {
        BlockInfo* newBlock = block + (size + sizeof(BlockInfo)) / sizeof(BlockInfo);
        newBlock->length = r;
        newBlock->isFree = 1;

        block->length = size;
        block->isFree = 0;
    }
}

Podemos agora aplicar o princípio DRY (Don’t Repeat Yourself) e eliminar a repetição de block->isFree = 0. Ficamos então com uma função mais curta:

void use(BlockInfo* block, size_t size)
{
    size_t r = block->length - size - sizeof(BlockInfo);

    block->isFree = 0;
    if(r > 0)
    {
        BlockInfo* newBlock = block + (size + sizeof(BlockInfo)) / sizeof(BlockInfo);
        newBlock->length = r;
        newBlock->isFree = 1;

        block->length = size;
    }
}

E assim a divisão já está.

A fusão fica para a parte IV.