Garbage Collector

UNIVERSIDADE DE PERNAMBUCO

Garbage Collector

UNIVERSIDADE DE PERNAMBUCO

• Conceitos Básicos

• O que é o Garbage Collector

• Analisando o Código

• Execução do Garbage Collector

• Exemplos

• Algoritmos para Coleta de Lixo:

o Mark and Sweep Algorithm

o Reference Counting Algorithm

o Copying Algorithm

• Referências.

Roteiro da Apresentação

UNIVERSIDADE DE PERNAMBUCO

Existem três estratégias para se alocar memória:

o Estática: áreas de memória são alocadas antes do

início do programa;

o Linear: memória alocada em fila ou em pilha;

o Dinâmica: permite liberdade de criação e remoção

em ordem arbitrária;

Conceitos Básicos

3

UNIVERSIDADE DE PERNAMBUCO

• Java utiliza alocação dinâmica (heap) para objetos

e alocação linear (pilha) para procedimentos

sequenciais;

• Programadores não têm a responsabilidade e nem

a possibilidade de gerenciar a memória do sistema;

• A alocação e liberação de memória dinâmica é

realizada automaticamente usando algoritmos;

4

UNIVERSIDADE DE PERNAMBUCO

Então, por que se preocupar com

memória em Java?

5

UNIVERSIDADE DE PERNAMBUCO

• Mas algoritmos são configurados para situações

típicas:

o Determinadas aplicações podem requerer

ajustes;

o Saber o quanto, quando, onde ajustar requer

conhecimentos elementares;

6

UNIVERSIDADE DE PERNAMBUCO

A medida que vamos fazendo

alocações na heap o espaço vai se

tornando cada vez mais escasso.

Fazendo uma analogia seria como

um quarto repleto de coisas dispostas de

qualquer forma onde não se há mais

espaço para se guardar novos objetos...

7

UNIVERSIDADE DE PERNAMBUCO

8 Qualquer semelhança a algum ambiente conhecido é mera coincidência!

UNIVERSIDADE DE PERNAMBUCO

Neste caso é necessário

chamar alguém que entende

melhor do assunto para poder

nos ajudar nesta tarefa árdua e

complicada, que é organizar

tudo! 9

UNIVERSIDADE DE PERNAMBUCO

O Garbage Collector é

a nossa faxineira

querida de cada dia!

10

UNIVERSIDADE DE PERNAMBUCO

• Garbage Collector é o nome de uma rotina básica

de alguns sistemas, que serve para recuperar o

espaço de memória que havia sido alocado para

uso por alguma aplicação [1];

• Esse espaço de memória posteriormente ficou em

desuso pela aplicação [1];

• A alocação dos objetos é decidida em tempo de

compilação e estes são alocados no Heap [2] [3];

Garbage Collector

11

UNIVERSIDADE DE PERNAMBUCO

É papel dessa rotina

identificar e reaproveitar os

espaços de memória que não

são mais utilizados!

12

UNIVERSIDADE DE PERNAMBUCO

Para facilitar a compreensão do

assunto vamos considerar um esquema de

alocação dinâmica de espaço de memória,

uma lista ligada como mostra a próxima

figura.

Exemplo

13

UNIVERSIDADE DE PERNAMBUCO

Início

...

Esquema de Alocação de

Memória Dinâmica

14

UNIVERSIDADE DE PERNAMBUCO

Vamos analisar o trecho de código

abaixo e saber o que acontece quando a

instrução new é invocada:

Analisando o código:

15

Public class Empresa { Cliente novoCliente = new Cliente(); }

UNIVERSIDADE DE PERNAMBUCO

Quando a instrução new é invocada as

seguintes tarefas são realizadas:

• „Calcula-se o total de memória necessária;

• „O heap é examinado;

• Se tiver espaço, o construtor é invocado.

• Antes de retornar a referência, avança

com o ponteiro next object pointer [3]. 16

UNIVERSIDADE DE PERNAMBUCO

E se não houver

espaço suficiente no

heap?

17

UNIVERSIDADE DE PERNAMBUCO

Quando, ao processar a instrução

new, no heap não houver memória

suficiente, se executa o Garbage

Collector [3].

18

UNIVERSIDADE DE PERNAMBUCO

• Uma unidade de espaço é considerada ativa ou

útil quando ela pode ser acessada ou atingida [1].

Execução do Garbage Collector

Início

...

19

UNIVERSIDADE DE PERNAMBUCO

• Caso uma unidade de espaço não possa ser

acessada, então ela é definida como inativa ou

lixo [1];

• Unidades podem se tornar lixo quando ponteiros

são redirecionados tornando-as inacessíveis [1],

como veremos na próxima figura:

20

UNIVERSIDADE DE PERNAMBUCO

Lista 1

...

Lista 2

...

21

UNIVERSIDADE DE PERNAMBUCO

Lista 1

...

Lista 2

...

Lixo

22

UNIVERSIDADE DE PERNAMBUCO

Lista 1

...

Lista 2

...

23

UNIVERSIDADE DE PERNAMBUCO

Lista 1

...

Lista 2

...

Lixo!

Lixo!

24

UNIVERSIDADE DE PERNAMBUCO

• Durante o processo de garbage collector, os

objetos no heap são investigados, para isso

é construído um grafo de objetos, como

ilustra a próxima figura:

25

UNIVERSIDADE DE PERNAMBUCO

Exemplo 01

G E Y H S V B M W Q Heap

Grafo E

V

Y

B

H W M

Q

S

G

26

UNIVERSIDADE DE PERNAMBUCO

Exemplo 01

G E Y H S V B M W Q Heap

Grafo E

V

Y

B

H W M

Q

S

G LIXO!

LIXO!

27

UNIVERSIDADE DE PERNAMBUCO

Exemplo 01

G E Y H V B W Q

Heap Compactado

Next Object Pointer

28

UNIVERSIDADE DE PERNAMBUCO

Exemplo 02

Heap

29

A M T P L K J E Q S V Y G

R U X I O H Z D C F N W B

UNIVERSIDADE DE PERNAMBUCO

Exemplo 02 Grafo

A B

E

S

K Q

L

F

P

M

J N

D O

T

I

H

G

U R

W

Y

C

Z

X

V

30

UNIVERSIDADE DE PERNAMBUCO

Exemplo 02 Grafo

A B

E

S

K Q

L

F

P

M

J N

D O

T

I

H

G

U R

W

Y

C

Z

X

V

31

LIXO!

LIXO!

LIXO!

LIXO!

UNIVERSIDADE DE PERNAMBUCO

Exemplo 02

Heap

Compactado

Next Object

Pointer

32

A M T L K J E Q V G R U X

I O Z D C F N W B

UNIVERSIDADE DE PERNAMBUCO

• Há várias implementações de algoritmos de coleta

de lixo, cada um com suas vantagens e

desvantagens [4];

• O comportamento desse algoritmo é o principal

gargalo na maior parte das aplicações de vida

longa [4];

• Conhecer os detalhes do funcionamento do

algoritmo de coleta de lixo é importante [4];

33

UNIVERSIDADE DE PERNAMBUCO

Influência da coleta de lixo nas próximas

alocações [4]:

• A remoção de objetos deixa buracos no heap;

• Para alocar novos objetos, é preciso procurar nas

listas de espaços vazios (free lists) um que caiba

o próximo objeto;

• Alguns algoritmos compactam o heap, movendo

os objetos para o início do heap e atualizando os

ponteiros. 34

UNIVERSIDADE DE PERNAMBUCO

• Mark and Sweep Algorithm: rastreia objetos do

heap, marca o que não é lixo e depois varre o lixo.

• Reference Counting Algorithm: mantém, em cada

objeto, uma contagem das referências para ele; coleta

os objetos que têm contagem zero;

• Copying Algorithm: divide o heap em duas partes;

cria objetos em uma parte do heap e deixa outra parte

vazia; recolhe o que não é lixo e copia para a área

limpa, depois esvazia a área suja.

35

Algoritmos para Coleta de Lixo:

UNIVERSIDADE DE PERNAMBUCO

Mark and Sweep Algorithm

• O método Mark and Sweep, foi criado em 1960 por J.

McCarthy [2];

• Esse método é geral e funciona sempre, isto é, todo lixo é

sempre identificado e recolhido;

• Usa um bit adicional por elemento para servir de marca;

• O método consiste de duas fases: uma fase de marcação

seguida de uma fase de varredura e recolhimento [1].

36

UNIVERSIDADE DE PERNAMBUCO

• A partir de ponteiros externos conhecidos,

todos os elementos das estruturas de dados

acessíveis são marcados [1];

• Para isso é necessário algum algoritmo para

percorrer essas estruturas para ajudar no

percurso e na marcação [1];

Fase de Marcação (Mark)

37

UNIVERSIDADE DE PERNAMBUCO

• O espaço das posições em que estão

implementadas as estruturas de dados,

bem como a lista dos elementos livres, é

varrido ou percorrido sequencialmente [1];

Fase da Varredura (Sweep)

38

UNIVERSIDADE DE PERNAMBUCO

Quando cada elemento é examinado, é

tomada uma das duas ações [1]:

• Se o elemento é marcado, simplesmente

desmarca esse elemento e nada mais é

feito com o elemento;

• Se o elemento não é marcado, então por

definição ele é lixo e é recolhido.

39

UNIVERSIDADE DE PERNAMBUCO

• Vantagens:

o Não precisa de algoritmo complicados;

o Pode ser mais rápido que Contagem de

Referências.

40

UNIVERSIDADE DE PERNAMBUCO

• Desvantagens:

o Interrompe a aplicação principal;

o Fragmentação pode aumentar a frequência em

que o Garbage Collector ocorre;

o Precisa visitar todos os objetos alcançáveis na

fase de marcação e varrer o heap inteiro.

41

UNIVERSIDADE DE PERNAMBUCO

Reference Counting Algorithm

• O método Reference Counting foi criado por

Collins em 1960 [2];

• Tem a vantagem de identificar o lixo e procede

seu recolhimento assim que o lixo surgir [1];

• Usa um contador por elemento para servir de

contagem de referências [1];

42

UNIVERSIDADE DE PERNAMBUCO

• O contador de referências indica a

quantidade de ponteiros ou referências a

esse elemento [1].

• Este contador deve ser sempre mantido

atualizado. [1].

43

UNIVERSIDADE DE PERNAMBUCO

• Quando o contador de referências de um

elemento atinge o valor zero, o elemento é

lixo por definição;

• O elemento é então recolhido ao espaço

livre.

44

UNIVERSIDADE DE PERNAMBUCO

• Vantagens:

o Rápido: não precisa varrer o heap inteiro;

o Pode executar em paralelo com a

aplicação.

45

UNIVERSIDADE DE PERNAMBUCO

• Desvantagens:

o Custo de processamento alto;

o Incapacidade de avaliar estruturas

cíclicas.

• Soluções:

o Algoritmo de Coleta de Ciclos.

46

UNIVERSIDADE DE PERNAMBUCO

Copying Algorithm

• O método Copying Algorithm, foi criado por

Chenney em 1970 [4];

• O método de Cópia divide o heap em duas

áreas iguais chamadas de origem (from

space) e destino (to space) [4];

47

UNIVERSIDADE DE PERNAMBUCO

O Algoritmo funciona da seguinte maneira

[4]:

1. Objetos são alocados na área “from”;

2. Quando o coletor de lixo é executado, ele

navega pela corrente de referências e copia os

objetos alcançáveis para a área “to”;

3. Quando a cópia é completada, os espaços “to”

e “from” trocam de papel; 48

UNIVERSIDADE DE PERNAMBUCO

49

J

F

G

B

E

U

P

Z

Q

W

Heap Origem: From Heap Destino: To

UNIVERSIDADE DE PERNAMBUCO

50

J

F

G

B

E

U

P

Z

Q

W

J

G

U

Z

Q

W

Heap Origem: From Heap Destino: To

UNIVERSIDADE DE PERNAMBUCO

51

J

F

G

B

E

U

P

Z

Q

W

J

G

U

Z

Q

W

Heap Origem: From Heap Destino: To

UNIVERSIDADE DE PERNAMBUCO

Vantagens:

o A cópia ocorre de forma rápida;

o Não precisa visitar o heap inteiro;

o Não fragmenta a memória do heap.

52

UNIVERSIDADE DE PERNAMBUCO

Desvantagens:

o Aplicação precisa parar;

o Dobra a necessidade de memória do

heap;

o Uso ineficiente de memória.

53

UNIVERSIDADE DE PERNAMBUCO

Link:

http://mais.uol.com.br/view/ee0dmzfst8i2/garbagecollector040262D0B93346

?types=A

Sugestão de Vídeo Sobre o Assunto:

54

UNIVERSIDADE DE PERNAMBUCO

[1] SONG, S. W. Coletor de Lixo (Garbage Collector). Universidade

de são Paulo – IME/USP, 2008. Apostila.

[2] LINS, R. D. Garbage Collection. Universidade Federal de

Pernambuco. Apostila.

[3] LEITE, N. Garbage Collection. ISEL/LEIC – Semestre de Inverno.

Disponível em: http://www.deetc.isel.ipl.pt/programacao/ave/ . 2008-

2009. Apostila.

[4] ROCHA, H. Gerência de Memória em Java – Parte I: Arquitetura

da JVM e Algoritmos de Coleta de Lixo. Disponível em:

http://www.argonavis.com.br/. 2005. Apostila.

Referências