ACH2024 Aula11e12 GerenciamentoDeMemoria e ColetaDeLixo

Prévia do material em texto

1
ACH2024 
Aulas 11 e 12 – Gerenciamento de 
Memória e Coleta de Lixo
Profa. Ariane Machado Lima
2
Programa de ACH2024
 Algoritmos para classificação externa em disco e 
fita. Arquivos, consultas, organizações 
seqüênciais, técnicas de indexação, indexação 
cilindro-superfície, árvores-B, tries e hashing. 
Organização de arquivos: seqüêncial, aleatória 
e invertida. Estruturas de dados para alocação 
dinâmica de memória, coleta e compactação de 
lixo. Estruturas de dados para representação de 
grafos, algoritmos de busca em grafos.
3
Memória principal
 Memória utilizada por um programa:
 Em parte conhecida pelo compilador (estruturas 
estáticas declaradas no programa, alocadas em 
tempo de compilação)
 Em parte não conhecida pelo compilador (caso a 
linguagem de programação permita alocação 
DINÂMICA de memória, com estruturas alocadas 
em tempo de execução por meio de funções 
como malloc, calloc, new, ...)
4
Memória principal
 Memória utilizada por um programa:
 Segmento de texto (ou de código): código de um 
programa e variáveis alocadas estaticamente
 Segmento de pilha: alocação de espaço necessário à 
execução de sub-rotinas (variáveis locais, parâmetros, 
etc…)
 Segmento de heap: alocação dinâmica de memória
• Obs: nada tem a ver com a estrutura de dados “heap” 
Segm. de texto Pilha Memória disponível Heap
Sentido de crescimento
5
Alocação dinâmica de memória
Exemplos:
 malloc/calloc x free: linguagem C
 new x delete: Linguagem C++ 
 new x dispose: Linguagem Pascal
 new: Linguagens Java, Smalltalk
Vantagens:
 Alocar/desalocar à medida que for necessário (economia de memória)
 Quando o tamanho da memória necessária só é conhecida em tempo de 
execução
Desvantagens:
 Tempo (de execução) gasto no gerenciamento de memória
 Implementação do gerenciamento de memória pode ser complicado (para 
linguagens em que isso não é feito de forma transparente, como C, C++, 
Pascal)
6
Gerenciador de memória
Parte do sistema operacional responsável por 
manter os blocos de memória disponíveis, 
alocar a programas e reintegrar blocos 
liberados, além de gerenciar o acesso 
compartilhado, transferência de dados de/para o 
disco, etc.
Heap é uma parte da memória dedicada à 
alocação dinâmica (nada tem a ver com a 
“estrutura de dados” heap)
7
Outras questões a serem consideradas pelo 
gerenciador de memória
Fragmentação externa:
 Com o tempo (após alocações/desalocações 
sucessivas), o heap pode ficar fragmentado, isto 
é, com vários trechos de memória disponível 
intercortados por trechos de memória utilizada 
8
Outras questões a serem consideradas pelo 
gerenciador de memória
Fragmentação interna:
 Parte dos blocos alocados não são inteiramente 
utilizados 
9
Gerenciamento da memória:
mapa de bits ou listas ligadas
[TANENBAUM, A. S. Modern Operating Systems, 4th ed.]
10
Gerenciamento da memória por listas ligadas: 
procedimento de liberação de um trecho
11
Alocação dinâmica de memória
Como o gerenciador irá alocar a memória solicitada no heap 
terá impacto sobre a fragmentação 
Trechos consecutivos de memória (de tamanho variável) 
normalmente organizados em uma lista duplamente ligada
Cada trecho tem, além do espaço para armazenamento 
propriamento dito, quatro campos: dois ponteiros para estar 
na lista duplamente ligada (anterior e próximo), tamanho e 
flag disponível/reservado 
Duas principais estratégias de “VER” a memória e gerenciá-la:
 Como um vetor sequencial contendo trechos contíguos de 
memória utilizada e disponível (intercalados): métodos de ajuste 
sequencial
 Como várias listas de blocos: métodos de ajuste não sequencial
12
Métodos de ajuste sequencial
Vetor sequencial contendo trechos contíguos de 
memória utilizada e disponível (intercalados em 
qualquer ordem)
Se um trecho de tamanho R for requisitado (por 
exemplo 8 KB), onde ele será alocado?
Depende de qual variação do método de ajuste 
sequencial está sendo utilizado...
utilizadosdisponíveis
Posição inicial dos trechos (em KB)
13
Métodos de ajuste sequencial
Vetor sequencial contendo trechos contíguos de 
memória utilizada e disponível (intercalados em 
qualquer ordem)
Se um trecho de tamanho R for requisitado (por 
exemplo 8 KB), onde ele será alocado?
Depende de qual variação do método de ajuste 
sequencial está sendo utilizado...
utilizadosdisponíveis
Posição inicial dos trechos (em KB)
14
Métodos de ajuste sequencial
variações
 Primeiro ajuste: seleciona o primeiro trecho 
encontrado (a partir do início da lista) grande o 
suficiente 
 Próximo ajuste: seleciona o próximo trecho 
grande o suficiente (a partir do índice 
“corrente”, ajustado após a última alocação)
 Melhor ajuste: seleciona o menor trecho 
dentre os trechos grandes o suficiente 
 Pior ajuste: seleciona o maior trecho de todos
15
Métodos de ajuste sequencial
Vetor sequencial contendo trechos contíguos de 
memória utilizada e disponível (intercalados em 
qualquer ordem)
Se um trecho de tamanho R for requisitado (por 
exemplo 8 KB), onde ele será alocado?
Depende de qual variação do método de ajuste 
sequencial está sendo utilizado...
utilizadosdisponíveis
Posição inicial dos trechos (em KB)
16
Métodos de ajuste sequencial
variações
17
Métodos de ajuste sequencial:
variações
 Qual vocês acham que é melhor?
Melhor ajuste pode ser o pior: gasta tempo analisando tudo e, a menos que o 
ajuste seja perfeito, deixa sobrar normalmente trechos pequenos que não 
podem ser reutilizados
Pior ajuste tenta evitar esse desperdício, deixando sobrar trechos maiores que 
podem ser ainda utilizados, e assim posterga a criação de blocos pequenos
Primeiro ajuste é o mais eficiente: balanço entre tempo de achar um bloco de 
tamanho suficiente (retorna assim que achar o primeiro) e fragmentação (não 
deixa sobrar sistematicamente o menor ou maior trecho)
Próximo ajuste, similar ao primeiro ajuste, mas chega mais rápido ao fim do 
heap. Nesse caso:
Ou gastará mais tempo tendo que rever todo o heap para ver se há trecho 
disponível
Ou considera-se que acabou a memória, e portanto pode ter fragmentado mais.
18
Métodos de ajuste sequencial:
variações
 Qual vocês acham que é melhor?
 Melhor ajuste pode ser o pior: gasta tempo analisando tudo e, a menos que 
o ajuste seja perfeito, deixa sobrar normalmente trechos pequenos que não 
podem ser reutilizados
 Pior ajuste tenta evitar esse desperdício, deixando sobrar trechos maiores 
que podem ser ainda utilizados, e assim posterga a criação de blocos 
pequenos
 Primeiro ajuste é o mais eficiente: balanço entre tempo de achar um bloco 
de tamanho suficiente (retorna assim que achar o primeiro) e fragmentação 
(não deixa sobrar sistematicamente o menor ou maior trecho)
 Próximo ajuste, similar ao primeiro ajuste, mas chega mais rápido ao fim do 
heap. Nesse caso:
 Ou gastará mais tempo tendo que rever todo o heap para ver se há trecho 
disponível
 Ou considera-se que acabou a memória, e portanto pode ter fragmentado mais.
19
Métodos de ajuste NÃO sequencial
Mais adequados para grandes volumes de 
memória
Memória organizada em várias listas de trechos 
de memória
 
20
Métodos de ajuste não sequencial:
Estratégia 1: listas tamanho-específicas
Várias listas, cada lista contendo trechos de um 
mesmo tamanho
Número de listas potencialmente grande → listas 
organizadas em uma estrutura de árvore
 
21
Métodos de ajuste não sequencial:
Estratégia 2: ajuste exato adaptativo
 Baseada na ideia de que alguns tamanhos de trechos 
solicitados são mais “populares” → manter listas de trechos 
para esses tamanhos (número menor de listas)
 Essaslistas armazenam trechos DESALOCADOS durante as T 
últimas alocações. 
 Quando um trecho de tamanho b é solicitado, se b for um 
tamanho “popular”, procura na lista dos trechos de tamanho b 
(ajuste exato). Se não encontrar (ou se b não for um tamanho 
“popular”) procura na memória usando um método de ajuste 
sequencial
 Se após T alocações não foi feita nenhuma solicitação para um 
trecho de tamanho considerado “popular”, esse tamanho deixar 
de ser “popular” e sua lista é liberada (ajuste exato adaptativo)
22
Métodos de ajuste não sequencial:
Estratégia 2: ajuste exato adaptativo
23
Métodos de ajuste não sequencial:
Estratégia 2: ajuste exato adaptativo
Algoritmo de alocação: (ERRATA DO LIVRO)
bi bi >
25
Comentários finais
A fragmentação, em algum grau, é um problema em 
qualquer algoritmo
Para lidar com isso é necessário tomar providências 
extras. Ex:
 Compactar memória após certo número de alocações e 
desalocações
 Reconstruir a lista de tamanhos após certo tempo (no 
método de ajuste exato adaptativo)
 Outra estratégia de alocação que diminua a 
fragmentação, ex: buddy systems (método sofisticado de 
vai particionando em dois os trechos disponíveis, 
utilizando apenas o que for necessário)
26
Referência bibliográfica
DROZDEK, Adam. Data Structures and 
Algorithms in C++. Ed. Cengage Learning. 4a 
ed. 2013. Cap. 12 (seções 12.1 e 12.2)
27
Coleta de Lixo
28
O problema do vazamento de 
memória (memory leak)
Vazamento de memória: um trecho de memória, 
ainda não liberado, torna-se inacessível
Ex:
int* vertices = (int*) calloc(tamanho, sizeof(int));
… /* sequência de comando que NÃO incluem um 
     free(vertices) */ 
vertices = novo_conjunto_de_vertices; 
29
Gerenciamento de memória 
alocada dinamicamente
Em linguagens SEM coleta de lixo (garbage 
collection):
 Para cada comando de alocação, um de 
desalocação quando a memória não for mais 
necessária
Exemplos:
malloc/calloc x free: linguagem C
new x delete: Linguagem C++ 
new x dispose: Linguagem Pascal
30
Gerenciamento de memória 
alocada dinamicamente
CUIDADO! Certifique-se de não acessar posições de memória que 
foram desalocadas! Se não terá o famoso “Segmentation fault”!
Ex:
int* vertices = (int*) calloc(tamanho, sizeof(int));
…
free(vertices);
…
if (vertices[3] == ….) XXXXX errado!!! não existe mais 
 “vertices”
 
dangling pointer (ponteiro pendente)
31
Gerenciamento de memória 
alocada dinamicamente
BOA PRÁTICA DE PROGRAMAÇÃO:
 
Sempre que for usar um ponteiro que você não acabou de 
atribuir valor a ele ou usá-lo, certificar-se antes se ele é válido :
if (vertices == null) { printf “vertices == 
null\n”; exit(1); }
Sempre que for desalocar:
free(vertices);    
vertices = null;
vale a dica de cima também
antes do free!!!
32
Gerenciamento de memória 
alocada dinamicamente
Em linguagens orientadas a objeto, cuidar para que 
os destrutores façam a desalocação corretamente 
Ex: Objeto que tem atributos alocados 
dinamicamente (no construtor ou em durante a 
“vida” do objeto), precisa ter esses atributos 
desalocados explicitamente (no destrutor ou em 
outro método). Cuidado especial quando tiver 
uma hierarquia de classes…. 
 Ao utilizar herança, os destrutores devem “virtual” 
para garantir uma correta desalocação
33
Coleta de lixo
Há linguagens nas quais o usuário não precisa se preocupar em desalocar a 
memória (ex: LISP, Java, Smalltalk)
Isso é feito automaticamente pelo “coletor de lixo” da linguagem
Duas tarefas necessárias (que podem ser feitas sequenciamente ou 
integradas)
 Marcação: para identificar o que está sendo utilizado (vivo)
 Regeneração: para liberar o que não está sendo utilizado (morto) e compactar o 
heap
Há vários possíveis algoritmos de coleta de lixo. Ex:
 Contagem de referências
 Marcar e varrer (Mark-and-Sweep)
 Pare e copie
 Incremental
 Basedo em gerações
34
Contagem de referências
Cada célula de memória (trecho alocado do heap) 
precisa ter um campo inteiro que seja um contador 
de quantas variáveis apontam para ela
Quando uma variável deixa de apontar para ela, o 
contador deve ser decrementado
Quando o contador chega a zero, a célula é 
identificada como lixo:
 se ela tem ponteiros para outras células, os contadores 
dessas células são também decrementados 
 a célula é reintegrada à parte disponível do heap
35
Contagem de referências - Exemplo
b
36
Contagem de referências - Exemplo
37
Contagem de referências - Exemplo
Contadores de
 referência
a
38
Contagem de referências - Exemplo
b
39
Contagem de referências - Exemplo
a
X
40
Contagem de referências - Exemplo
Xa
41
Contagem de referências
Vantagem
É uma coleta de lixo “on the fly”, realizada ao 
longo da execução dos programas, não 
necessitando parar a execução dos programas 
para executar o coletor de lixo
42
Contagem de referências
Desvantagens
 Sobrecarga no uso da memória (um contador de referências 
para cada trecho/célula) 
 Sobrecarga de tempo, durante a execução do programa, 
atualizando as referências (pode haver a necessidade de 
várias atualizações recursivas) e reintegrando à memória livre
 Pode falhar na detecção de estruturas circulares: Contadores de
 referência
43
Marcar e varrer
Executado em algum momento específico, por 
exemplo quando a memória disponível está 
abaixo de um limiar
Executa as tarefas de marcação e regeneração em 
duas fases distintas (nas fases marcar e varrer) 
Ao invés de precisar de um campo inteiro, precisa 
só de um bit para indicar se a célula está 
marcada (viva, usada) ou não marcada (morta, 
não usada)
44
Marcar e varrer
 Inicialização: 
 marca todas as células do heap como “morta”
Fase de marcação:
 A partir dos ponteiros fora do heap (da pilha e 
variáveis globais do segmento de texto), marque 
cada célula alcançada como “viva” e percorra 
recursivamente os ponteiros dessas células
Fase de varredura:
 Percorra novamente o heap movendo cada célula 
“morta” para a lista livre (de memória disponível) 
45
Marcar e varrer
Capaz de identificar estruturas circulares não 
acessíveis
Tempo de execução depende do tamanho do 
heap, já que todo ele será percorrido pelo 
menos 2 vezes
Desvantagem: precisa de espaço em memória 
(que já está baixo) para a pilha que faz o 
percurso recursivo das referências 
46
Pare e copie
Para não ter que percorrer todo o heap:
Divide o heap em duas partes (dois semi-
espaços), sendo somente um ativo em 
cada instante
Alocações são feitas no semi-espaço 
ativo
Quando acaba o espaço disponível no 
semi-espaço ativo:
 seus trechos vivos são identificados 
como nos métodos anteriores (a partir 
das variáveis fora do heap, mas 
percorrendo os ponteiros em uma 
busca em largura) mas agora a ação é 
copiá-los, contiguamente, no segundo 
semi-espaço (não-ativo)
 Os dois semi-espaços trocam de papel 
(ativo ↔ não ativo)
47
Pare e copie
Desvantagem:
 Somente metade do heap está disponível
Vantagens:
 Tempo de execução depende do volume de dados vivos ao invés do 
tamanho total do heap
 Executa compactação da memória (isto é, memória disponível está 
contígua)
 Promove localização: trechos distintos de valores estruturados podem 
estar próximos fisicamente na memória, aumentando a chance de 
estarem na mesma página (usa busca em largura para fazer a cópia)
 Não usa memória adicional para marcações
 Não é recursivo (consome menos memória)
48
Coleta de lixo incremental
As estratégias “Marcar evarrer” e “pare e copie” vistas até 
agora baseiam-se em, algum momento, parar a execução do 
programa corrente e executar a coleta de lixo
O tempo de coleta pode ser inaceitável em sistemas de tempo 
real, nos quais o tempo é uma questão crítica (ex: sistemas de 
navegação aérea, sistemas de sensores de usinas nucleares, 
etc…)
Para esses casos, a coleta de lixo deve ser feita aos poucos, 
intercalada com a execução do programa, antes da memória 
disponível cair a níveis críticos
O método de contagem de referências é incremental, mas suas 
desvantagens o tornam desaconselhável
49
Coleta de lixo incremental
Necessidade de um programa mutador para 
arbitrar quem vai executar a cada instante: o 
programa ou o coletor 
Problema: nessa intercalação de execuções, o 
programa pode alterar estados das variáveis que 
já foram analisadas na últimas execuções do 
coletor
O coletor então precisa saber o que o programa fez 
desde sua última execução → maior sobrecarga 
de execução total
50
Marcar e varrer incremental
O que devemos adaptar no marcar e varrer 
tradicional (abaixo) para torná-lo incremental?
Inicialização: 
 marca todas as células do heap como “morta”
Fase de marcação:
 A partir dos ponteiros fora do heap (da pilha e variáveis globais do 
segmento de texto), marque cada célula alcançada como “viva” e 
percorra recursivamente os ponteiros dessas células
Fase de varredura:
 Percorra novamente o heap movendo cada célula “morta” para a lista 
livre (de memória disponível) 
51
Marcar e varrer incremental
Fase de inicialização: 
Nada precisa ser alterado
Fase de marcação: 
Todas as células alocadas durante a última interrupção precisam ser 
marcadas vivas
Obs: e se células marcadas como vivas tiverem sido inutilizadas 
durante a última interrupção?
• Serão coletadas apenas na rodada seguinte.
Fase de varredura:
Como o heap é varrido sequencialmente, basta garantir que 
alocações sejam feitas sempre em regiões anteriores ao ponto de 
reinício de varredura
52
Marcar e varrer incremental
Fase de inicialização: 
Nada precisa ser alterado
Fase de marcação: 
Todas as células alocadas durante a última interrupção precisam ser 
marcadas vivas
Obs: e se células marcadas como vivas tiverem sido inutilizadas 
durante a última interrupção?
• Serão coletadas apenas na rodada seguinte.
Fase de varredura:
Como o heap é varrido sequencialmente, basta garantir que 
alocações sejam feitas sempre em regiões anteriores ao ponto de 
reinício de varredura
53
Os semi-espaços ativos e 
inativos são agora chamados 
from_space e to_space
Sempre que uma célula do 
from_space é referenciada 
durante o programa, ela 
primeiro é copiada para o 
to_space (no fim)
Alocações são feitas no 
to_space (no topo), e a cada 
alocação são copiadas k 
células do from_space para o 
to_space (no fim)
Quando todas as células do 
from_space são copiadas, os 
dois semi-espaços trocam de 
papéis (from ↔ to)
Pare e copie incremental
54
Algoritmos baseados em gerações
Dados empíricos: a maioria dos dados se tornam lixo 
pouco tempo depois de criados
Ideia: dividir o heap em áreas baseadas na idade das 
células (gerações)
 Gerações mais novas sofrem coleta de lixo com 
mais frequência
 Novas alocações são feitas na geração mais nova
 Células que sobrevivem a um certo número de 
coletas são promovidas a uma geração mais velha
55
Observações
A maioria das técnicas de coleta de lixo são 
conservadoras: só assume-se que uma célula é lixo 
se ela for inacessível (em muitos casos não dá para 
prever se uma célula nunca mais será utilizada no 
programa se ainda houver uma referência a ela)
Para cada trecho de memória analisado, é preciso 
diferenciar o que contém valores propriamente ditos 
(inteiro, strings, etc) e o que contém ponteiros. Por 
ex: utilizando alguns bits do trecho para essa 
rotulação
56
Referência bibliográfica
DROZDEK, Adam. Estruturas de Dados e Algoritmos em C++. 
Ed. Cengage Learning. 2a ed. 2002. Seção 12.3 (voltado à 
implementação em Lisp)
TANENBAUM, A. S. Modern Operating Systems.Pearson 
Education 4 ed. Seção 3.2.3 
Tese: http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-
89-544.pdf
Parte inicial do cap 9 do livro Développement d'applications 
avec Objective Caml by Emmanuel Chailloux, Pascal Manoury 
and Bruno Pagano: 
http://caml.inria.fr/pub/docs/oreilly-book/pdf/chap9.pdf (15 
primeiras páginas que tratam do tema em geral)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56