5.3.2 Mantendo a Ilusão de Memória Infinita
O método de representação delineado na seção 5.3.1 resolve o problema de implementar estrutura de lista, desde que tenhamos uma quantidade infinita de memória. Com um computador real, eventualmente ficaremos sem espaço livre no qual construir novos pares.1 No entanto, a maioria dos pares gerados em uma computação típica são usados apenas para guardar resultados intermediários. Depois que esses resultados são acessados, os pares não são mais necessários — eles são lixo. Por exemplo, a computação
constrói duas listas: a enumeração e o resultado de filtrar a enumeração. Quando a acumulação está completa, essas listas não são mais necessárias, e a memória alocada pode ser recuperada. Se pudermos arranjar para coletar todo o lixo periodicamente, e se isso acabar reciclando memória aproximadamente na mesma taxa em que construímos novos pares, teremos preservado a ilusão de que há uma quantidade infinita de memória.
Para reciclar pares, devemos ter uma maneira de determinar quais pares alocados não são necessários (no sentido de que seus conteúdos não podem mais influenciar o futuro da computação). O método que examinaremos para realizar isso é conhecido como coleta de lixo. A coleta de lixo é baseada na observação de que, em qualquer momento em uma interpretação baseada em memória estruturada em lista, os únicos objetos que podem afetar o futuro da computação são aqueles que podem ser alcançados por alguma sucessão de operações head e tail começando dos ponteiros que estão atualmente nos registradores da máquina.2 Qualquer célula de memória que não seja assim acessível pode ser reciclada.
Existem muitas maneiras de realizar a coleta de lixo. O método que examinaremos aqui é chamado stop-and-copy. A ideia básica é dividir a memória em duas metades: "memória de trabalho" e "memória livre". Quando pair constrói pares, ele aloca estes na memória de trabalho. Quando a memória de trabalho está cheia, realizamos a coleta de lixo localizando todos os pares úteis na memória de trabalho e copiando-os para localizações consecutivas na memória livre. (Os pares úteis são localizados traçando todos os ponteiros head e tail, começando com os registradores da máquina.) Como não copiamos o lixo, presumivelmente haverá memória livre adicional que podemos usar para alocar novos pares. Além disso, nada na memória de trabalho é necessário, já que todos os pares úteis nela foram copiados. Assim, se intercambiarmos os papéis da memória de trabalho e da memória livre, podemos continuar processando; novos pares serão alocados na nova memória de trabalho (que era a antiga memória livre). Quando esta estiver cheia, podemos copiar os pares úteis para a nova memória livre (que era a antiga memória de trabalho).3
Implementação de um coletor de lixo stop-and-copy
Agora usamos nossa linguagem de máquina de registradores para descrever o algoritmo stop-and-copy com mais detalhes. Assumiremos que há um registrador chamado root que contém um ponteiro para uma estrutura que eventualmente aponta para todos os dados acessíveis. Isso pode ser arranjado armazenando os conteúdos de todos os registradores da máquina em uma lista pré-alocada apontada por root logo antes de iniciar a coleta de lixo.4 Também assumimos que, além da memória de trabalho atual, há memória livre disponível para a qual podemos copiar os dados úteis. A memória de trabalho atual consiste de vetores cujos endereços base estão nos registradores chamados the_heads e the_tails, e a memória livre está nos registradores chamados new_heads e new_tails.
A coleta de lixo é disparada quando esgotamos as células livres na memória de trabalho atual, ou seja, quando uma operação pair tenta incrementar o ponteiro free além do fim do vetor de memória. Quando o processo de coleta de lixo estiver completo, o ponteiro root apontará para a nova memória, todos os objetos acessíveis a partir da root terão sido movidos para a nova memória, e o ponteiro free indicará o próximo lugar na nova memória onde um novo par pode ser alocado. Além disso, os papéis da memória de trabalho e da nova memória terão sido intercambiados — novos pares serão construídos na nova memória, começando no lugar indicado por free, e a memória de trabalho (anterior) estará disponível como a nova memória para a próxima coleta de lixo. A Figura 5.15 mostra a disposi ção da memória logo antes e logo depois da coleta de lixo.
Antes da Coleta
Depois da Coleta
Algoritmo Stop-and-Copy:
- Copiar objetos acessíveis da memória de trabalho para memória livre
- Marcar objetos movidos com "broken heart" (coração partido)
- Atualizar ponteiros para novos endereços
- Trocar papéis: memória livre vira memória de trabalho
- Lixo é automaticamente eliminado (não é copiado)
Figura 5.15: Reconfiguração da memória pelo processo de coleta de lixo.
O estado do processo de coleta de lixo é controlado mantendo dois ponteiros: free e scan. Estes são inicializados para apontar para o início da nova memória. O algoritmo começa relocando o par apontado por root para o início da nova memória. O par é copiado, o ponteiro root é ajustado para apontar para a nova localização, e o ponteiro free é incrementado. Além disso, a localização antiga do par é marcada para mostrar que seus conteúdos foram movidos. Esta marcação é feita da seguinte forma: na posição head, colocamos uma tag especial que sinaliza que este é um objeto já movido. (Tal objeto é tradicionalmente chamado de coração partido.)5 Na posição tail colocamos um endereço de encaminhamento que aponta para a localização para a qual o objeto foi movido.
Depois de realocar a raiz, o coletor de lixo entra em seu ciclo básico. A cada passo no algoritmo, o ponteiro scan (inicialmente apontando para a raiz realocada) aponta para um par que foi movido para a nova memória mas cujos ponteiros head e tail ainda se referem a objetos na memória antiga. Esses objetos são cada um realocados, e o ponteiro scan é incrementado. Para realocar um objeto (por exemplo, o objeto indicado pelo ponteiro head do par que estamos escaneando), verificamos se o objeto já foi movido (conforme indicado pela presença de uma tag de coração partido na posição head do objeto). Se o objeto ainda não foi movido, nós o copiamos para o lugar indicado por free, atualizamos free, configuramos um coração partido na localização antiga do objeto, e atualizamos o ponteiro para o objeto (neste exemplo, o ponteiro head do par que estamos escaneando) para apontar para a nova localização. Se o objeto já foi movido, seu endereço de encaminhamento (encontrado na posição tail do coração partido) é substituído pelo ponteiro no par sendo escaneado. Eventualmente, todos os objetos acessíveis terão sido movidos e escaneados, momento no qual o ponteiro scan ultrapassará o ponteiro free e o processo terminará.
Podemos especificar o algoritmo stop-and-copy como uma sequência de instruções para uma máquina de registradores. O passo básico de realocar um objeto é realizado por uma sub-rotina chamada relocate_old_result_in_new. Esta sub-rotina obtém seu argumento, um ponteiro para o objeto a ser realocado, de um registrador chamado old. Ela realoca o objeto designado (incrementando free no processo), coloca um ponteiro para o objeto realocado em um registrador chamado new, e retorna ramificando para o ponto de entrada armazenado no registrador relocate_continue. Para começar a coleta de lixo, invocamos esta sub-rotina para realocar o ponteiro root, após inicializar free e scan. Quando a realocação de root foi realizada, instalamos o novo ponteiro como o novo root e entramos no loop principal do coletor de lixo.
No loop principal do coletor de lixo devemos determinar se há mais objetos para serem escaneados. Fazemos isso testando se o ponteiro scan é coincidente com o ponteiro free. Se os ponteiros são iguais, então todos os objetos acessíveis foram realocados, e ramificamos para gc_flip, que limpa as coisas para que possamos continuar a computação interrompida. Se ainda há pares para serem escaneados, chamamos a sub-rotina de realocação para realocar o head do próximo par (colocando o ponteiro head em old). O registrador relocate_continue é configurado para que a sub-rotina retorne para atualizar o ponteiro head.
Em update_head, modificamos o ponteiro head do par sendo escaneado, então procedemos para realocar o tail do par. Retornamos para update_tail quando essa realocação foi realizada. Depois de realocar e atualizar o tail, terminamos de escanear aquele par, então continuamos com o loop principal.
A sub-rotina relocate_old_result_in_new realoca objetos da seguinte forma: se o objeto a ser realocado (apontado por old) não é um par, então retornamos o mesmo ponteiro para o objeto inalterado (em new). (Por exemplo, podemos estar escaneando um par cujo head é o número 4. Se representarmos o head por n4, conforme descrito na seção 5.3.1, então queremos que o ponteiro head "realocado" ainda seja n4.) Caso contrário, devemos realizar a realocação. Se a posição head do par a ser realocado contém uma tag de coração partido, então o par de fato já foi movido, então recuperamos o endereço de encaminhamento (da posição tail do coração partido) e retornamos isto em new. Se o ponteiro em old aponta para um par ainda não movido, então movemos o par para a primeira célula livre na nova memória (apontada por free) e configuramos o coração partido armazenando uma tag de coração partido e endereço de encaminhamento na localização antiga. A sub-rotina relocate_old_result_in_new usa um registrador oldht para guardar o head ou o tail do objeto apontado por old.6
No final do processo de coleta de lixo, intercambiamos o papel das memórias antiga e nova intercambiando ponteiros: intercambiando the_heads com new_heads, e the_tails com new_tails. Estaremos então prontos para realizar outra coleta de lixo na próxima vez que a memória acabar.