4: GARIS DE MEMÓRIA
____
_.-'111 `"`--._
,00010. .01011, ''-..
,10101010 `111000. _ ____ ;
/_..__..-------- ''' __.' /
`-._ /""| _..-''' ___ __ __ ___ __ __ . __' ___ . __
"`-----\ `\ | | | | __ | | |\/| |___ | | | |__] | |\ | |__| |__/ | | |
| ;.-""--.. |___ |__| |__] |__| | | |___ |___ |__| |__] | | \| | | | \ | |__|
| ,10. 101. `.======================================== ==============================
`;1010 `0110 : 1º Edição
.1""-.|`-._ ;
010 _.-| +---+----'
`--'\` | / / ...:::est:amicis:nuces:::...
~~~~~~~~~| / | |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\| / |
`----`---'
GARIS DE MEMÓRIA
Higor Eurípedes (a.k.a. enygmata ou fmul)
heuripedes at gmail dot com
Outubro de 2011Conteúdo
- Introdução
- O que são garbage collectors
- 2.1 - Alguns conceitos interessantes
- Tipos
- 3.1 - Tracing Garbage Collectors
- 3.2 - Reference Counting Garbage Collectors
- 3.2.1 - Um refcounted GC por dentro
- Citações, links e referências
1 - Introdução
Na-não, espere! Este não é um texto sobre os nossos mal tratados lixeiros, menos ainda sobre Alzheimer. Estou aqui para falar sobre os Garbage Collectors, ou GCs.
Neste artigo irei utilizar os termos "bloco" e "objeto", entenda-os como sendo regiões na heap do programa a menos que fique explícito que estou falando de objetos do paradigma de orientação à objetos.
2 - O que são garbage collectors
Coletores de lixo ou garbage collectors são peças de código que tem a função de liberar recursos que não são mais utilizados pelo programa a.k.a. o lixo do programa. Eles são comumente utilizados no gerenciamento de memória de linguagens de alto nível (principalmente naquelas que não permitem gerenciamento explícito) e por bibliotecas que permitem o compartilhamento de objetos entre programas.
Os GCs livram o programador de algumas preocupações, como chamar free() menos ou até mais que o necessário (causando erros double free), mas não é garantia de que não ocorrerão vazamentos de memória. Utilizar coletores de lixo também diminui as chances de que ocorram situações onde não existe nenhum ponteiro apontando pra um determinado bloco na heap, os rebeldes dangling pointers.
Mas, como diz o ditado e o meu colega sigsegv, "rapadura é doce mas não é mole". Nem tudo são flores no mundo dos garbage collectors, o uso de coletores implica em custos pro sistema e o uso incorreto pode causar pausas em programas multitarefa, picos de processamento aleatórios e fragmentação da memória do programa.
2.1 - Alguns conceitos interessantes
Quando falamos sobre garbage collectors repetimos sempre o termo "referência". As referências são ligações entre objetos na memória, são ponteiros, e podem ser classificadas quanto a força que exercem sobre a vida do objeto referenciado. As fracas são referências que muitas vezes sequer contem informações sobre o objeto referenciado (são ponteiros "crus") e não previnem que o mesmo seja coletado. Objetos referenciados fortemente não são coletados até que todas as referencias sejam removidas.
Outros conceitos importantes são "coleta" e "reciclagem", o primeiro implica em liberar a memória e o segundo significa informar o alocador que aquela região está disponível para reuso. A implementação destes dois conceitos vai depender dos requisitos do sistema.
3 - Tipos
Basicamente, existem duas vertentes entre os coletores de lixo: os tracing garbage collectors (tracing GC) e os reference counting garbage collectors (refcount GC). É possível também encontrar híbridos. Todos eles, porém, exigem que o programador utilize funções de alocação específicas ou que de alguma forma identifique a memória alocada como passível de coleção.
3.1 - Tracing Garbage Collectors
Os tracing GCs, em geral, trabalham escaneando a memória em busca de referências que possam ser alvos de coleta. Estes coletores costumam ser cíclicos, pois não coletam os objetos assim que deixam de ser utilizados, mas durante alguma etapa do ciclo de coleta.
Como o GC se comporta depende do algoritmo utilizado, o mark-sweep, por exemplo, possui três etapas: na primeira o GC identifica as referências; na segunda ele marca os objetos que ainda possuem referências; e, na terceira etapa, o GC coleta todos os objetos que não estão marcados.
A linguagem Java (por padrão) e as linguagens que são implementadas com a Common Language Infraestructure da .NET Framework utilizam um tipo de tracing GC chamado efêmero ou geracional, este GC técnicas de heurística para encontrar blocos não utilizados e por isso possui um certo nível de não determinismo, ou seja, torna-se difícil prever quando ocorrerá um ciclo. O uso deste tipo de GC pode causar dores de cabeça em sistemas com carga alta como o que aconteceu no site de perguntas e respostas Stack Overflow (veja o link sobre o GC da .NET no fim do artigo).
3.2 - Reference Counting Garbage Collectors
Os refcounting GCs são mais humildes que seus primos e utilizam somente contadores de referência para determinar quando um bloco está pronto para ser coletado. A ideia é simples, sempre que um bloco estiver com zero referências, ele estará pronto para ser coletado ou reciclado. Diferente dos tracing GCs, os refcounting GCs costumam guardar a informação sobre as referência junto ao bloco que é alocado para o usuário, muitas vezes na forma de cabeçalho. Este tipo de coletor é bastante utilizado em aplicações que necessitam que os recursos sejam liberados o mais cedo possível.
Uma desvantagem dos coletores baseados em contagem de referência é que eles não lidam com referências cíclicas sem que a complexidade aumente consideravelmente; na linguagem Perl, por exemplo, objetos com referência cíclica só são liberados numa etapa de coleta que ocorre no fim do programa. A solução mais simples nesses casos é utilizar um misto de referências fracas e fortes entre os objetos envolvidos ou simplesmente proibir que este tipo de referência aconteça.
Além da Perl, as linguagem Python e PHP e as bibliotecas GObject (parte da GLib e base da biblioteca Gtk+) e COM+ (uma biblioteca para IPC nos sistemas Windows) também utilizam contagem de referência para evitar problemas com alocação de recursos.
3.2.1 - Um refcounted GC por dentro
Como dito antes, os blocos alocados pelos coletores possuem um cabeçalho e também um corpo, onde ficam os dados do usuário. O cabeçalho, em geral, tem um tamanho fixo, o suficiente para armazenar o contador de referência.
Bloco alocado pelo coletor:
+--------------+------------------->
| Cabeçalho | Corpo
+--------------+------------------->
^-Tamanho fixo-^-Tamanho variável-->Em C você pode considerar que a estrutura básica do coletor é definida da seguinte forma:
typedef struct {
size_t refcount; /* Número de referências. */
} GCHeader;Nota: O corpo do bloco não tem delimitação e por motivos de portabilidade não vamos definir um membro ou estrutura pra ele. Vale lembrar que é possível criar uma estrutura para representar todo o bloco utilizando arrays de tamanho variável (C99) ou zero-length arrays.
No momento da alocação, o tamanho do cabeçalho é somado ao tamanho do bloco que o usuário deseja alocar e em seguida o contador é inicializado com o valor um. O ponteiro pro bloco recentemente alocado é movido para a próxima posição, ele agora aponta para o corpo do bloco.
/* aloca um bloco e retorna seu corpo */
void *gc_alloc(size_t size) {
size_t new_size = size + sizeof(GCHeader);
GCHeader *block = malloc(new_size);
block->refcount = 1;
block++;
return block;
}Para facilitar o trabalho, é uma boa ideia criar funções para acessar a região do cabeçalho:
/* retorna o cabeçalho do bloco */
GCHeader *gc_get_header(void *body) {
return ((GCHeader*)body)-1;
}E agora a implementação das funções que aumentam ou diminuem o numero de referências. A função para aumentar o número de referências não tem mistério, é só pegar o ponteiro pro cabeçalho e somar um à refcount:
/* adiciona uma referência ao bloco e retorna um ponteiro para o corpo */
void *gc_ref(void *body) {
GCHeader *header = gc_get_header(body);
header->refcount++;
return body;
}Já a função para diminuir o número de referências tem é um pouquinho mais complicada: precisamos checar se a quantidade de referências chegou a zero e liberar a memória se isso acontecer.
/* remove uma referência e retorna um ponteiro para o corpo (ou null caso
não hajam mais referências */
void *gc_unref(void *body) {
GCHeader *header = gc_get_header(body);
header->refcount--;
if (header->refcount == 0) {
free(header);
body = NULL;
}
return body;
}É importante notar que a implementação apresentada aqui não é aconselhada para uso em programas multitarefa, pois não utiliza nenhum mecanismo de sincronização ou operações atômicas.
4 - Citações, links e referências
- In managed code we trust, our recent battles with the .NET garbage collector http://samsaffron.com/archive/2011/10/28/in-managed-code-we-trust-our-recent-battles-with-the-net-garbage-collector
- Two-Phased Garbage Collection http://perldoc.perl.org/perlobj.html#Two-Phased-Garbage-Collection
- Arrays of Length Zero http://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html#Zero-Length
- Object memory management http://developer.gnome.org/gobject/stable/gobject-memory.html
- The Memory Management Reference: Beginners Guide: Recycling http://www.memorymanagement.org/articles/recycle.html
_____
.: :.
(_________)
__ | |
.: :. | |
(______) / /
|| / /
|| / / __
_ || | | (__) ,
(_) \\010| || .; _..--,
\\.0101010110. ;': ' ',,,\ .^. .^. .^.
.0101011010101. ;_; '|_ ,'
.100101010101011. | .;;;;., ,': .^. '. .^.
,;::;:::.. ..;;;;;;;;.. :_,' .;'
.^. .' '':::;._.;;::::''''':;::;/' .;:;
. ':::::::;;' '::::: ...;: .^.
.^. ':::' /':::; ..:::::;:..::::::::.. .^.
.^. .^. ; ,'; ':::;;...;::;;;;' ';;. .^.
,,,_/ ; ; ';;:;::::' '.
.^. ..' ,' ;' ''\ '
.^. ' ''' .^. ' ;'. .^. .^.
: : .^.
