Coleta de resíduos
Sumário
Resíduos
Coleta de resíduos
Contador de referências
 Marcação e varredura
 Parada e cópia
 Marcação e compactação

Gerenciamento dinâmico de memória
2
Resíduo
Um objeto é uma instância de uma classe ou
de um array
Heap – região de memória onde os objetos
são alocados dinamicamente (não é o heap
árvore)
A memória alocada a cada objeto contém
espaço para administração da memória
3
Resíduos
Programas contém objetos e referencias a objetos
Quando existem referencias a objetos que não mais
existem ocorre um vazamento de memória
Objetos que não são mais referenciados são chamados de
resíduos
O procedimento de Coleta de resíduos é invocado quando
o total de memória alocada atinge determinado patamar

Usualmente o programa é suspenso enquanto se faz a coleta de
resíduos
Para facilitar a coleta de resíduos deve-se atribuir null a
toda variável referenciando objetos não mais necessários
4
Coleta de resíduos
Métodos de coleta de resíduos
Contador de referências
Marcação e varredura
Parada e cópia
Marcação e compactação
6
Método do Contador de Referências
Cada objeto possui um campo contador que
armazena o número de ponteiros (internos e
externos) que apontam para este objeto
Toda vez que o ponteiro para um objeto é
atualizado os contadores de referências dos
objetos para os quais o ponteiro apontava e passou
a apontar são atualizados
Toda vez que o contador de referências de um
objeto se torna nulo este objeto pode ser devolvido
à coleção de objetos livres
7
Contador de referências
Object p = new Integer (57);
Object q = p;
Object p = new Integer (57);
Object q = new Integer (99);
p=q;
8
Contador de referências
Implementações do contador de referências para p = q;
if (p != q)
{
if (p != null)
--p.refCount;
p = q;
if (p != null)
++p.refCount;
}
ou
if (p != q)
{
if (p != null)
if (--p.refCount == 0)
heap.release (p);
p = q;
if (p != null)
++p.refCount;
}
9
Contador de referências
Na referência a objetos que referenciam outros
objetos o problema se complica
Quando o primeiro objeto receber valor null os
objetos referenciados permanecerão como
resíduos até o coletor de resíduos recolher o
primeiro objeto
10
Contador de referências
Object p =
new Association (new Integer (57), new Integer (99));
11
Contador de referências
•Referência circulares
•Anula-se a lista mas os objetos permanecem
referenciados
12
Método de Marcação e Varredura
Objetos não referenciados são marcados
A coleta de resíduos é feita posteriormente
Objetos referenciados diretamente por variáveis
do programa são chamados de raízes (roots)
Objetos acessíveis indiretamente são ditos vivos
Demais objetos são resíduos
A marcação de objetos requer um atributo
booleano marked
13
Método de Marcação e Varredura
Algoritmo
for each root variable r
mark (r);
sweep ();
void mark (Object p)
if (!p.marked)
p.marked = true;
for each Object q referenced by p
mark (q);
void sweep ()
for each Object p in the heap
if (p.marked)
p.marked = false
else
heap.release (p);
14
Método de Marcação e Varredura
Objetos são criados com marked false
O processo de marcação atribui true a
marked para objetos acessívies ou vivos
O processo de varredura coleta os objetos
com marked false e atribui false a marked
dos objetos que permaneceram acessíveis
15
Método de Marcação e Varredura
16
Método de Parada e Cópia
Fragmentação



A alocação e deslocação de memória, ou seja, a
atribuição de trechos de memória a processos é feita em
blocos de memória de tamanhos requisitados pelos
respectivos processos
A natureza dinâmica dessas ocorrências faz com que,
em geral a memória fique fragmentada intercalando
blocos alocados e blocos livres
A fragmentação pode provocar a impossibilidade do
atendimento de uma solicitação pela inexistência de um
bloco livre no tamanho desejado muito embora o
somatório das áreas livres fragmentadas supere o
tamanho solicitado
17
Método de Parada e Cópia
No método de Parada e Cópia o heap é dividido em duas
regiões


activeHeap
inactiveHeap
Considera-se disponível o espaço inactiveHeap entre o
final do último bloco de memória alocado e o final da
memória
Sempre que uma solicitação de memória ultrapassa o
espaço disponível:




Interrompe-se o processamento
Objetos vivos são copiados da região ativa para a inativa
As regiões ativa e inativa trocam seus papéis
Verifica-se então a possibilidade de atendimento da solicitação
18
Método de Parada e Cópia
• Algoritmo básico
for each root variable r
r = copy (r, inactiveHeap);
swap (activeHeap, inactiveHeap);
19
Método de Parada e Cópia
void Object copy (Object p, Heap destination)
if (p == null)
return null;
if (p.forward == null)
q = destination.newInstance (p.class);
p.forward = q;
for each field f in p
if (f is a primitive type)
q.f = p.f;
else
q.f = copy (p.f, destination);
q.forward = null;
return p.forward;
20
Método de Parada e
Cópia
21
Método de Marcação e Compactação
• A referência a objetos pode ser implementada por meio de
manipuladores (“handles”)
• Cada objeto tem seu handle
• Handle contém
•
•
•
Referência a uma instância da classe do objeto
Ponteiro para região do heap aonde o objeto reside
Flag marked
• Quando a posição do objeto no heap modifica é necessário
apenas atualizar o ponteiro do handle pois todas as
referências ao objeto são feitas ao handle
22
Método de Marcação e Compactação
• Algoritmo básico
for each root variable r
mark (r);
compact ();
23
Exemplo de uso de handle
24
Método de Marcação e
Compactação
• Algoritmos
void mark (Object p)
if (!handle[p].marked)
handle[p].marked = true;
for each Object q referenced by p
mark (q);
void compact ()
long offset = 0;
for each Object p in the heap
if (handle[p].marked)
handle[p].object = heap.move (p, offset);
handle[p].marked = false;
offset += sizeof (p);
25
Gerenciamento dinâmico de memória
Gerenciamento dinâmico de memória
O processo de alocação de blocos de
memória pode ser feito de diversas
maneiras, tais como:
Primeiro ajuste
 Melhor ajuste
 Pior ajuste

27
Primeiro ajuste
A lista de blocos livres é percorrida
seqüencialmente até encontrar o primeiro
bloco livre cujo tamanho seja maior ou
igual do que a quantidade de memória
requisitada
28
Melhor ajuste
O método busca o menor bloco livre cujo
tamanho seja maior do que ou igual à
quantidade de memória requisitada
29
Pior ajuste
O método consiste na alocação de uma porção do
maior bloco livre constante da lista de blocos
livres
Usando um pequeno número de grandes blocos
para satisfazer a maioria das requisições muitos
blocos de tamanho moderado permanecem sem
fragmentação
A não ser no caso da maioria de requisições de
memória em grandes blocos, o método do pior
ajuste satisfaz a um maior número de requisições
do que os outros métodos
30
Primeiro exemplo
1) Considere-se a situação na qual existem
blocos livres com tamanhos 200, 300 e 100
unidades de memória.
Deseja-se alocar blocos de memória com os
tamanhos 150, 100, 125, 10 e 100 unidades.
A seqüência de alocação, pelos diversos
processos é a seguinte.
31
Primeiro exemplo
Espaços
Livres
200
300
100
150
200
150
100
Espaços
Livres
200
300
100
100
0
25
0
150
50
300
100
Processo da Primeira Escolha
Solicitações
100
125
100
100
50
50
50 Não pode
75 Não pode
200
75
100
100
0 Não pode
150
50
300
100
Processo da Melhor Escolha
Solicitações
100
125
100
100
50
50
50 Não pode
300
175
75 Não pode
0
0 Não pode
0
Espaços
Livres
200
300
100
Processo da Pior Escolha
Solicitações
100
125
100
100
100
0
150
25
25
100
100
100
32
Segundo exemplo
2) Considere-se a situação na qual existem
blocos livres com tamanhos 110 e 54
unidades de memória.
Deseja-se alocar blocos de memória com os
tamanhos 25, 70 e 50 unidades. A seqüência
de alocação, pelos diversos processos é a
seguinte.
33
Segundo exemplo
Espaços
Livres
110
54
Espaços
Livres
110
54
Espaços
Livres
110
54
Processo da Primeira
Escolha
Solicitações
25
70
50
15
85
15
54
54
4
Processo da Melhor
Escolha
Solicitações
25
70
50
110
40 Não pode
29 Não pode
29
Processo da Pior Escolha
Solicitações
25
70
50
15
85
15
54
54
4
34
Gerenciamento dinâmico de memória
O método do primeiro ajuste é mais eficiente se a lista de
blocos disponíveis for mantida em ordem crescente de
endereços de memória. Caso a lista seja mantida em ordem
crescente de tamanho de bloco a busca por melhor ajuste
se torna mais eficiente. Caso a lista seja mantida em ordem
decrescente de tamanho de bloco o método do pior ajuste é
o mais eficiente.
Todavia não é prático manter a lista de blocos disponíveis
classificada por tamanho. Na ausência de outras
considerações ou especificações é usual se dar preferência
ao método do primeiro ajuste.
35