Algoritmos para contagem de referências cíclicas em sistemas multiprocessados

Abstract

O gerenciamento automático da memória dinâmica, conhecido como coleta de lixo (garbage collection), se tornou uma necessidade na maioria das linguagens de programação em uso atualmente. Dentre as técnicas para realizar o gerenciamento automático da memória, a contagem de referências se mostra vantajosa por uma série de razões, dentre elas o fato de ser uma técnica naturalmente incremental, o que evita a parada completa do processo do usuário para realizar tarefas de administração da memória. A natureza incremental da contagem de referências indica que o algoritmo pode ser adaptado para uma versão em sistemas multiprocessados, mantendo sua característica não suspensiva no programa do usuário. Entretanto, os problemas causados pela necessidade de sincronização entre threads pode anular os ganhos de eficiência obtidos com essa extensão, inviabilizando o uso de um coletor de lixo baseado em contagem de referências em um ambiente multiprocessado. Nesta tese apresenta-se um conjunto de algoritmos eficientes para utilizar a contagem de referências em sistemas com vários processadores, tendo como foco principal o algoritmo para contagem de referências para vários mutadores e um coletor. Este algoritmo foi implementado na máquina virtual Java Jikes RVM e seu desempenho testado em relação a coletores alternativos; os resultados de tais testes indicam que o algoritmo proposto tem desempenho competitivo com outros coletores similares, mas impõe tempos de pausa muito menores ao programa do usuário. A presente tese também apresenta uma prova informal da corretude do algoritmo proposto