Alocação de Memória

Na maior parte das linguagens imperativas o código é alocado estaticamente.

O compilador define, em tempo de compilação o endereço de cada artefato e este endereço é imutável durante o tempo de execução.

Variáveis estáticas dependem de seu tempo de vida:

• Globais existem durante todo o tempo de execução;
• Locais existem durante o tempo de uma função, ou método, ou procedure;
• Dados compartilhados entre objetos existem durante todo o de execução.

Método simples e eficiente de alocar memória para sub-rotinas.

Quando uma sub-rotina é chamada toda a memória necessária é alocada em um bloco chamado de Activation Record ou Stack Frame.

O layout destes frames varia de linguagem para linguagem e de arquitetura para arquitetura

Manter uma linked-list do blocos livres no heap.

Para alocar, buscamos na lista um bloco cujo tamanho seja igual ou maior que o necessário.

Se o tamanho for igual removemos o bloco da lista de blocos livres.

Se o tamanho for maior, modificamos o tamanho para o tamanho necessário.

Quando um artefato é deletado, o bloco é devolvido a lista de blocos livres.

E verificamos se esse bloco não pode ser unido a um dos seus vizinhos para criar um bloco maior.

Quatro algoritmos dominam este cenário.

First-fit: seleciona o primeiro bloco da lista de blocos livres que seja maior ou igual ao necessário.

Best-fit: busca em toda a lista o melhor bloco para alocar o espaço necessário, o de tamanho igual é melhor.

Buddy system: usa blocos de tamanho padrão $2^𝑘$. Se não existir nenhum espaço disponível. Se nenhum bloco de tamanho entre $2^{(𝑘−1)}$ e $2^𝑘$ atende então vamos encontrar um bloco de $2^{(𝑘+1)}$ e dividi-lo ao meio adicionando as metades a lista de blocos livres

Fibonacci heap: blocos de tamanho padrão seguindo a sequência de Fibonacci.

Malloc / new: aloca a memória necessária para um determinado artefato.

Free / delete: libera a memória usada por um determinado artefato.

Este modelo permite que o programador tenha controle da eficiência do seu executável.

Este modelo permite que erros de desalocação afetem a segurança do programa.

Solução clássica, dos anos 1950, Garbage Collector. Vamos investigar a memória e remover todos os artefatos inúteis ainda na memória.

A linguagem define o tempo de vida de um artefato.

Em tempo de execução mantém controle de todos o bindings de cada artefato, incrementando a lista sempre que uma referência é criada e decrementando sempre que a referência é destruída.

Se um objeto nunca é desalocado teremos um vazamento de memória (memory leak).

É necessário determinar se o artefato está vivo, ou não, de acordo com a especificação da própria linguagem.

Um processo adicional precisa ser incluído no seu executável.

Degrada os algoritmos de cache.

Aumenta o consumo de memória.

Em alguns casos, consome 10% do tempo de uso de um programa.

Reference Counting: neste algoritmo, uma estrutura de dados extra mantém uma contagem de todos os ponteiros, ou referências, para um determinado objeto. Este contador é incrementado sempre que uma referência é criada e decrementado sempre que uma referência é destruida. Quando o contador chega a zero, o artefato pode ser removido da memória.

1. Simples e fácil de implementar. Porém, a memória necessária para manter o contador pode ser muito grande.
2. O controle pode ser feito pelo próprio uso dos artefatos. Contudo, se os artefatos tem vida muito curta, o custo de manter o contador não faz sentido.
3. A liberação da memória é instantânea. Se a referência é feita por um grupo de artefatos, a memória pode não ser liberada.