Garbage Collection
Rafael Dueire Lins
Departamento de Informática
Universidade Federal de Pernambuco
1
Gerenciamento Estático
Mais simples.
 Utilizado na versão original de
FORTRAN.
 A cada vez que um procedimento é
chamado utilizam-se as mesmas posições
de memória.
 Alocação decidida em tempo-decompilação.

2
Alocação Estática:
Organização da Memória
Programa Principal
Subrotina A
Subrotina B
Subrotina C
3
Alocação Estática:
Chamada a Procedimentos
...
z = DSucc (3)
w = DSucc (2)
...
Programa Principal
DSucc
DSucc(n)
temp1 = n + n
return temp1
Subrotina B
Subrotina C
4
Alocação Estática:
Chamada a Procedimentos
...
z = DSucc(3)
w = DSucc(2)
...
Programa Principal
DSucc
DSucc(3)
temp1 = 6
return temp1
Subrotina B
Subrotina C
5
Alocação Estática:
Chamada a Procedimentos
...
z = 6
w = DSucc(2)
...
Programa Principal
DSucc
DSucc(3)
temp1 = 6
return temp1
Subrotina B
Subrotina C
6
Alocação Estática:
Chamada a Procedimentos
...
z = 6
w = DSucc(2)
...
Programa Principal
DSucc
DSucc(2)
temp1 = 4
return temp1
Subrotina B
Subrotina C
7
Alocação Estática:
Chamada a Procedimentos
...
z = 6
w= 4
...
Programa Principal
DSucc
DSucc(2)
temp1 = 4
return temp1
Subrotina B
Subrotina C
8
Alocação em Pilha
Surgiu com Algol
 Possibilidade de procedimentos
recursivos.
fac n = n * fac ( n - 1 ) , n > 0
=1
, otherwise
 Se ProcA chama ProcB, ProcA nunca
termina antes do ProcB.
 Gerenciamento simples.

9
Alocação em Pilha
fac 2 é re-escrito como
10
fac 2 => 2 * fac ( 2 - 1)
=> 2 * fac 1
=> 2 * (1 * fac ( 1 - 1))
=> 2 * (1 * fac 0)
=> 2 * (1 * 1)
=> 2 * 1
=> 2
Alocação em Pilha:
Organização da Memória
Programa Principal
Subrotina A
Subrotina B
Subrotina A
11
Memória
de
Trabalho
Subrotina A
Subrotina C
Pilha de Registros
de Ativação
Garbage Collection:
Alocação Dinâmica de Memória
Listas: quebra da disciplina de pilha.
 Uma rotina chamada pode gerar uma
estrutura de dados que viva após o
término da sua chamada.
 IPL-5 foi a primeira linguagem a ter
listas como tipo primitivos. A falta de
um GC foi a causa do seu insucesso.
 LISP (J.McCarthy - 1960) foi a
primeira linguagem a ter GC.

12
Garbage Collection:
Organização da Memória
Programa Principal
Pilha de Registros
de Ativação
Subrotina A
Subrotina B
Subrotina C
Subrotina A
Memória
de
Trabalho
13
Lixo
raiz 1
raiz 2
Heap
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Free-list
14
1.Todas as
célulasestão
na free-list
Heap
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Raiz
15
Free-list
1.Todas as
célulasestão
na free-list.
2.O processo
do usuário
usa células
Heap
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Raiz
1.Todas as
célulasestão
na free-list.
2.O processo
do usuário
usa células.
3.A reescrita
do grafo
gera lixo.
Free-list
16
Heap
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Raiz
17
Heap
3.A reescrita
do grafo
gera lixo.
4.A free-list
fica vazia.
Free-list
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Raiz
18
Heap
3.A reescrita
do grafo
gera lixo.
4.A free-list
fica vazia.
5.Suspenso o
processo do
usuário.
6.Fá-se a
marcação.
Free-list
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Raiz
Free-list
19
6.Fá-se a
marcação.
7.Fá-se a
varredura,
retornando
as células
de lixo a
free-list.
8.Retoma-se o
processo do
usúario
Heap
Garbage Collection:
Mark-Scan (J.McCarthy 1960)
Tempo de suspensão do processo do
usuário:
Grafo_em_uso + Tamanho_da_Heap
 Imprevisibilidade do tempo de
suspensão.
 Necessita de 1-bit para a marcação.

20
Reference Counting (Collins 1960)
Desenvolvido para LISP.
 Evita a suspensão do processo de
usuário.
 Efetuado em pequenos passos
intercalados com as transformações
ao grafo.
 Exige a inclusão de um contador por
célula.

21
Reference Counting (Collins 1960)

NEW: tira uma célula da free-list e
conecta-a ao grafo.
Free-list
B
1
Root
C
1
1
1
2
22
A
New(A.esq)
1
1
Reference Counting (Collins 1960)

NEW: tira uma célula da free-list e
conecta-a ao grafo.
B
1
Root
C
1
1
1
2
23
A
New(A.esq)
Free-list
1
1
Reference Counting (Collins 1960)

COPY: copia um ponteiro.
Root
C
1
Copy(C.dir, A->B)
2
A
1
1
1
1
24
B
Free-list
1
Reference Counting (Collins 1960)

COPY: copia um ponteiro.
Root
C
1
Copy(C.dir, A->B)
2
A
1
2
1
1
25
B
Free-list
1
Reference Counting (Collins 1960)

DELETE: retira um ponteiro.
Root
C
1
Delete(A->B)
2
A
1
1
1
2
26
B
Free-list
1
Reference Counting (Collins 1960)

DELETE: retira um ponteiro.
Root
C
1
Delete(A->B);
Delete(Sons_B)
2
A
1
1
1
2
27
B
Free-list
1
Reference Counting (Collins 1960)

DELETE: retira um ponteiro.
Root
C
1
2
A
1
1
Free-list
B
1
1
28
Delete(A->B);
Delete(Sons_B);
Free(B).
1
Cyclic Reference Counting
McBeth 1963

Deleção de ponteiro a cíclo:
Root
A
2
Delete(Root->A)
1
29
B
Cyclic Reference Counting
McBeth 1963

Space-leak.
Root
A
1
Delete(Root->A)
1
30
B
Cyclic Reference Counting
Brownbridge 1985

Algoritmo errado!!!!
Root
2
2
A
31
2
B
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Algoritmo geral!!
Root
2
2
A
32
2
B
Delete(Root->A)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Age em RF > 1 (sharing)
Root
1
2
A
33
2
B
Delete(Root->A)
Mark_red(A)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Mark-Scan local
Root
0
0
A
34
1
B
Delete(Root->A)
Mark_red(A)
Scan_green(A)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Busca referências externas.
Root
0
0
A
35
1
B
Delete(Root->A)
Mark_red(A)
Scan_green(A)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Encontrada referência externa.
Root
0
0
A
36
1
B
Delete(Root->A)
Mark_red(A)
Scan_green(A)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Sub-grafo em uso.
Root
0
0
A
37
1
B
Delete(Root->A)
Mark_red(A)
Scan_green(C)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Referências atualizadas.
Root
0
1
A
38
2
B
Delete(Root->A)
Mark_red(A)
Scan_green(C)
C
Cyclic Reference Counting
Martinez-Wachenchauzer-Lins

Busca de lixo reciclável!
Root
1
2
A
39
2
B
Publicado em:
Information Processing Letters 1990
C
Delete(Root->A)
Mark_red(A)
Scan_green(A)
Collect_blue(A)
Lazy Cyclic Reference Counting
Lins

Mark-Scan postergado.
Root
2
2
A
2
B
C
Delete(Root->A)
40
Lazy Cyclic Reference Counting
Lins

Mark-Scan postergado.
Root
Pilha
1
2
A
2
B
C
Delete(Root->A)
41
Publicado em:
Information Processing Letters 1992
Lazy Cyclic Reference Counting
Lins

Mark-Scan só é chamado se
necessário!!
Root
Pilha
1
2
A
2
B
C
Delete(Root->A)
42
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
A Heap é dividida em dois semiespaços de igual tamanho.
 Quando o semi-espaço em uso fica
esgotado cópia-se o grafo-em-uso
para o outro semi-espaço deixando o
lixo para trás.

43
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
heap_1
raiz
44 hp
heap_2
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
raiz
heap_1
45
hp
heap_2
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
raiz
heap_1
heap_2
hp
46
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
raiz
heap_1
heap_2
hp
47
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
A cópia é recursiva.
 Há suspensão do processo de
usuário.
 Eficiente em máquinas com memória
virtual.
 Não necessita de espaço extra na
célula para marcação.

48
Garbage Collection:
Cópia (Fenichel-Yochelson 1969)
Complexidade computacional
proporcional ao grafo-em-uso.
 Degrada com a ocupância.
 Compacta os dados sem custo extra.
 Adequado para células de tamanho
variável.

49
Garbage Collection:
Cópia (Cheney 1970)
50

Algoritmo mais amplamente usado.

Não utiliza recursividade ou qualquer
outra estrutura de dados extra para
“lembrar” o caminho da cópia.

Utiliza dois apontadores.
Garbage Collection:
Cópia (Cheney 1970)
raiz
heap_1
cp
51
hp
heap_2
Garbage Collection:
Cópia (Cheney 1970)
raiz
heap_1
cp
52
hp
heap_2
Garbage Collection:
Cópia (Cheney 1970)
raiz
heap_1
cp
53
hp
heap_2
Garbage Collection:
Cópia
O algoritmo de Fenichel-Yochelson
faz uma varredura no grafo em
profundidade (depth-first).
 O algoritmo de Cheney varre o grafo
breadth-first.
 Experimentalmente encontra-se que
a varredura depth-first traz maior
localidade entre as células.
 Há versões de Cheney depth-first.

54
Garbage Collection:
Cópia Generacional.
55

Otimiza o algoritmo de cópia.

Células novas morrem cedo.

Células velhas vivem muito.

Segrega as células por idade:
várias heaps utilizadas.

Evidência experimental.
Garbage Collection:
Cópia Generacional.
Raiz
Heap 0
Celulas
Velhas
Heap 1
56
Celulas
Novas
Heap 2
Garbage Collection:
Cópia Generacional.

Minor Garbage Collection:
– Heaps mais novas.
– Mais freqüênte.

Major Garbage Collection:
– Equivalente ao algoritmo original de cópia.
– Heap mais velha.

57
Problema do algoritmo:
ponteiros intergeneracionais sobretudo
célula_mais_nova -> célula_mais_velha
Parallel Garbage Collection:
Cópia - Appel-Ellis-Li (1988)
Baseado em Baker.
 Usa informação do Sistema
Operacional para bloquear páginas de
memória.
 Faltando espaço:
 Suspende todos os threads do
mutador.
 O coletor varre os objetos ainda não
varridos.

58
Parallel Garbage Collection:
Cópia - Appel-Ellis-Li (1988)
Faltando espaço:
 Troca os semi-espaços.
 Copia os objetos acessíveis para
to-space.
 Proteje as páginas ainda não
copiadas.
 Re-inicia os threads de mutadores.
 Algoritmo eficiente.

59
60
61