Monte
- Região da memória para alocação e liberação de blocos
- Momentos arbitrários durante a execução do programa
Relação do monte com ponteiros raízes (roots)
Blocos lixo e árvore de apontadores
Principais preocupações em um gerenciador de monte
- Espaço versus Tempo
- Normalmente é uma escolha entre os dois
Espaço
- Fragmentação interna
- Fragmentação externa
Tempo
- Algoritmo sofisticado mas demorado?
- Simples e rápido?
- Híbrido
Gerenciadores com uma lista encadeada de blocos livres
- Inicialmente com um único bloco com todo o monte
Dois algoritmos
- Primeiro Encaixe (first fit)
- Melhor Encaixe (best fit)
Análise intuitiva
- Best fit reserva blocos maiores para pedidos maiores
- Best fit custa mais que o primeiro encaixe
Pergunta
- Qual das abordagens gera menor fragmentação externa?
Pergunta. Considerando uma lista única
- Qual o custo de uma alocação?
Custo de alocação é linear
- Depende somente da quantidade de blocos já alocados
Reduzir para custo constante
- Ter várias listas com tamanho de blocos diferentes
Monte é dividido em pools (uma para cada tamanho de bloco)
Uma lista de blocos livres para cada pool
Quando vem um pedido de alocação
- Pedido é arredondado para o tamanho mais próximo
- Realiza o acesso direto a lista de blocos livres específica
Divisão de tamanhos de bloco: estática ou dinâmica
- Estática, definida em tempo de compilação
- Dinâmica
- Sistema Parceiro (Buddy System)
- Monte de Fibonacci (Fibonacci Heap)
- Tamanho dos blocos são potências de 2
- Blocos de tamanho 2^0, 2^1, 2^2, 2^3, 2^4 … 2^n
Algoritmo
- \pause Se um bloco de tamanho 2^k é pedido, pega da piscina 2^k
- \pause Caso não haja blocos livres nesta piscina
- Pega um bloco da piscina 2k+1, divide em 2 e devolve
- O bloco que sobrou é adicionado na lista 2^k
- \pause No momento da liberação do bloco de 2k
- Fundido com o bloco parceiro (antes da separação)
- Colocado de volta na lista 2k+1
Tamanho dos blocos retirados da sequência de Fibonacci
- 1, 1, 2, 3, 5, 8, 13, 21, …
Algoritmo
Funcionamento similar ao Sistema Parceiro
Algoritmo é ligeiramente mais complexo \linebreak → tamanhos dos blocos são mais irregulares
Permite uma fragmentação mais baixa
- A sequência de fibonacci cresce mais devagar que 2^k
Todos os algoritmos geram algum tipo de fragmentação
- Não importa qual algoritmo, quantas listas de blocos livres
- Diminuim a habilidade de responder pedidos de alocação
Algoritmos de Compactação do Monte
- Mover blocos já alocados
- Corrigir referências a esses blocos no programa \linebreak → Complexidade e custo computacional
