1 Garbage Collection Rafael Dueire Lins Departamento de Informática Universidade Federal de Pernambuco

11

Garbage CollectionGarbage Collection

Rafael Dueire Lins

Departamento de Informática

Universidade Federal de Pernambuco

22

Gerenciamento EstáticoGerenciamento 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-de-compilação.

33

Alocação Estática:Alocação Estática:

Organização da MemóriaOrganização da Memória

Programa Principal

Subrotina A

Subrotina B

Subrotina C

44

Alocação Estática:Alocação Estática:Chamada a ProcedimentosChamada a Procedimentos

......z = DSucc (3) z = DSucc (3) w = DSucc (2) w = DSucc (2) ......

Programa Principal

Subrotina B

Subrotina C

DSuccDSucc(n)DSucc(n)temp1 = n + ntemp1 = n + nreturn temp1return temp1

55


......z = z = DSucc(3) DSucc(3) w = DSucc(2) w = DSucc(2) ......

Programa Principal

Subrotina B

Subrotina C

DSuccDSucc(3)DSucc(3)temp1 = 6temp1 = 6return temp1return temp1

66


......z = 6 z = 6 w = DSucc(2) w = DSucc(2) ......

Programa Principal

Subrotina B

Subrotina C


77


......z = 6 z = 6 w = w = DSucc(2) DSucc(2) ......

Programa Principal

Subrotina B

Subrotina C


88


......z = 6 z = 6 w = 4w = 4 ......

Programa Principal

Subrotina B

Subrotina C


99

Alocação em PilhaAlocaçã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.

1010

fac 2 é re-escrito como

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 PilhaAlocação em Pilha

1111

Alocação em Pilha:Alocação em Pilha:


Programa Principal

Subrotina A

Subrotina B

Subrotina A

Subrotina A

Subrotina C

Memória deTrabalho

Pilha de Registrosde Ativação

1212

Garbage Collection:Garbage Collection:Alocação Dinâmica de MemóriaAlocaçã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.

1313

Garbage Collection:Garbage Collection:


Programa Principal

Subrotina A

Memória deTrabalho

Pilha de Registrosde Ativação

Subrotina B

Subrotina C

Subrotina A

Heap

raiz 1 raiz 2

LixoLixo

1414


Mark-Scan (J.McCarthy 1960)Mark-Scan (J.McCarthy 1960)

Heap

Free-list 1.Todas as1.Todas as célulasestãocélulasestão na free-listna free-list

1515



HeapFree-list

1.Todas as1.Todas as célulasestãocélulasestão na free-list.na free-list.2.O processo 2.O processo do usuário do usuário usa célulasusa células

Raiz

1616



Heap

Free-list

1.Todas as1.Todas as célulasestãocélulasestão na free-list.na free-list.2.O processo 2.O processo do usuário do usuário usa células.usa células.3.A reescrita 3.A reescrita do grafodo grafo gera lixo.gera lixo.

Raiz

1717



Heap Free-list

3.A reescrita 3.A reescrita do grafodo grafo gera lixo.gera lixo.4.A free-list 4.A free-list fica vazia. fica vazia.

Raiz

1818



Heap Free-list

3.A reescrita 3.A reescrita do grafodo grafo gera lixo.gera lixo.4.A free-list 4.A free-list fica vazia. fica vazia. 5.Suspenso o5.Suspenso o processo doprocesso do usuário.usuário.6.Fá-se a 6.Fá-se a marcação.marcação.

Raiz

1919



Heap

Free-list

6.Fá-se a 6.Fá-se a marcação.marcação.7.Fá-se a 7.Fá-se a varredura,varredura, retornando retornando as células as células de lixo ade lixo a free-list.free-list.8.Retoma-se o8.Retoma-se o processo doprocesso do usúariousúario

Raiz

2020



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.

2121

Reference Counting (Collins 1960)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.

2222

Reference Counting (Collins 1960)Reference Counting (Collins 1960) NEW: tira uma célula da free-list e conecta-a ao

grafo.

1

2

1

1

1

1

1

Free-listFree-list

RootRoot

A A

New(A.esq)New(A.esq)

BB

CC

2323

Reference Counting (Collins 1960)Reference Counting (Collins 1960) NEW: tira uma célula da free-list e conecta-a ao

grafo.

1

2

1

1

1

1

1

Free-listFree-list

RootRoot

A A

New(A.esq)New(A.esq)

BB

CC

2424

Reference Counting (Collins 1960)Reference Counting (Collins 1960) COPY: copia um ponteiro.

11

1

1

1

Free-listFree-list

1

2

RootRoot

A A

Copy(C.dir, A->B)Copy(C.dir, A->B)

BB

CC

2525

Reference Counting (Collins 1960)Reference Counting (Collins 1960) COPY: copia um ponteiro.

12

1

1

1

Free-listFree-list

1

2

RootRoot

A A

Copy(C.dir, A->B)Copy(C.dir, A->B)

BB

CC

2626

Reference Counting (Collins 1960)Reference Counting (Collins 1960) DELETE: retira um ponteiro.

11

2

1

1

Free-listFree-list

1

2

RootRoot

A A

Delete(A->B)Delete(A->B)

BB

CC

2727


11

2

1

1

Free-listFree-list

1

2

RootRoot

A A

Delete(A->B);Delete(A->B);Delete(Sons_B)Delete(Sons_B)

BB

CC

2828


11

1

1

1

Free-listFree-list

1

2

RootRoot

A A

Delete(A->B);Delete(A->B);Delete(Sons_B);Delete(Sons_B);Free(B).Free(B).

BB

CC

2929

Cyclic Reference Counting Cyclic Reference Counting McBeth 1963McBeth 1963

Delete(Root->A)Delete(Root->A)2

1

RootRootA A

BB

Deleção de ponteiro a cíclo:

3030

Cyclic Reference Counting Cyclic Reference Counting McBeth 1963McBeth 1963

Space-leak.

Delete(Root->A)Delete(Root->A)1

1

RootRootA A

BB

3131

Cyclic Reference Counting Cyclic Reference Counting Brownbridge 1985Brownbridge 1985

Algoritmo errado!!!!

2 2

RootRoot

A A BB

2

CC

3232

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Algoritmo geral!!

2 2

RootRoot

A A BB

2

CC

Delete(Root->A)Delete(Root->A)

3333

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Age em RF > 1 (sharing)

1 2

RootRoot

A A BB

2

CC

Delete(Root->A)Delete(Root->A)Mark_red(A)Mark_red(A)

3434

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Mark-Scan local

0 0

RootRoot

A A BB

1

CC

Delete(Root->A)Delete(Root->A)Mark_red(A)Mark_red(A)Scan_green(A)Scan_green(A)

3535

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Busca referências externas.

0 0

RootRoot

A A BB

1

CC


3636

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Encontrada referência externa.

0 0

RootRoot

A A BB

1

CC


3737

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Sub-grafo em uso.

0 0

RootRoot

A A BB

1

CC

Delete(Root->A)Delete(Root->A)Mark_red(A)Mark_red(A)Scan_green(C)Scan_green(C)

3838

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Referências atualizadas.

0 1

RootRoot

A A BB

2

CC

Delete(Root->A)Delete(Root->A)Mark_red(A)Mark_red(A)Scan_green(C)Scan_green(C)

3939

Cyclic Reference Counting Cyclic Reference Counting Martinez-Wachenchauzer-LinsMartinez-Wachenchauzer-Lins Busca de lixo reciclável!

1 2

RootRoot

A A BB

2

CC

Delete(Root->A)Delete(Root->A)Mark_red(A)Mark_red(A)Scan_green(A)Scan_green(A)Collect_blue(A)Collect_blue(A)

Publicado em:Publicado em:Information Processing Letters 1990Information Processing Letters 1990

4040

Lazy Cyclic Reference Counting Lazy Cyclic Reference Counting

LinsLins Mark-Scan postergado.

2 2

RootRoot

A A BB

2

CC


4141


LinsLins Mark-Scan postergado.

1 2

RootRoot

A A BB

2

CC


PilhaPilha

Publicado em:Publicado em:Information Processing Letters 1992Information Processing Letters 1992

4242


LinsLins Mark-Scan só é chamado se necessário!!

1 2

RootRoot

A A BB

2

CC


PilhaPilha

4343


Cópia (Fenichel-Yochelson 1969)Cópia (Fenichel-Yochelson 1969)

A Heap é dividida em dois semi-espaç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.

4444



heap_1 heap_2

hp hp

raiz

4545



heap_1 heap_2 hp hp

raiz

4646



heap_1 heap_2

hp hp

raiz

4747



heap_1 heap_2

hp hp

raiz

4848



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.

4949



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.

5050


Cópia (Cheney 1970)Cópia (Cheney 1970)

Algoritmo mais amplamente usado.Algoritmo mais amplamente usado.

Não utiliza recursividade ou qualquer Não utiliza recursividade ou qualquer

outra estrutura de dados extra para outra estrutura de dados extra para

“lembrar” o caminho da cópia.“lembrar” o caminho da cópia.

Utiliza dois apontadores.Utiliza dois apontadores.

5151



heap_1

heap_2

hp hp

raiz

cp cp

5252



heap_1

heap_2

hp hp

raiz

cp cp

5353



heap_1

heap_2

hp hp

raiz

cp cp

5454


CópiaCópia O algoritmo de Fenichel-Yochelson Fenichel-Yochelson faz

uma varredura no grafo em profundidade (depth-firstdepth-first).

O algoritmo de CheneyCheney varre o grafo breadth-firstbreadth-first.

Experimentalmente encontra-se que a varredura depth-firstdepth-first traz maior localidadelocalidade entre as células.

Há versões de Cheney depth-first.Há versões de Cheney depth-first.

5555


Cópia Generacional.Cópia Generacional.

Otimiza o algoritmo de cópia.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.

5656



Heap 2

Raiz

Heap 1

Heap 0

CelulasCelulasVelhasVelhas

CelulasCelulasNovasNovas

5757



Minor Garbage Collection:– Heaps mais novas.Heaps mais novas.– Mais freqüênte.Mais freqüênte.

Major Garbage Collection:– Equivalente ao algoritmo original de cópia.– Heap mais velha.

Problema do algoritmo: ponteiros intergeneracionais sobretudo ponteiros intergeneracionais sobretudo

célula_mais_nova -> célula_mais_velhacélula_mais_nova -> célula_mais_velha

5858

Parallel Garbage Collection:Parallel Garbage Collection:

Cópia - Appel-Ellis-Li (1988)Cópia - Appel-Ellis-Li (1988) Baseado em BakerBaker. Usa informação do Sistema Operacional

para bloquear páginas de memória. Faltando espaço:Faltando espaço:

Suspende todos os threads do mutador.Suspende todos os threads do mutador. O coletor varre os objetos ainda não O coletor varre os objetos ainda não

varridos.varridos.

5959

Parallel Garbage Collection:Parallel Garbage Collection:

Cópia - Appel-Ellis-Li (1988)Cópia - Appel-Ellis-Li (1988)

Faltando espaço:Faltando espaço: Troca os semi-espaços.Troca os semi-espaços. Copia os objetos acessíveis para Copia os objetos acessíveis para to-to-

spacespace.. Proteje as páginas ainda não Proteje as páginas ainda não

copiadas.copiadas. Re-inicia os threads de mutadores.Re-inicia os threads de mutadores.

Algoritmo eficiente.

6060

6161

Documents

1 Garbage Collection Rafael Dueire Lins Departamento de Informática Universidade Federal de Pernambuco