SO_cap8-9-gerenciamento_memória

Prévia do material em texto

Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition,
Gerenciamento de Memória
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition,
Capítulo 8: 
Memória Principal
Operating System Concepts – 8th Edition 3 Silberschatz, Galvin and Gagne ©2009
Sumário
• Conceitos básicos relacionados à memória
• Swapping
• Alocação contígua
• Paginação
• Segmentação
Operating System Concepts – 8th Edition 4 Silberschatz, Galvin and Gagne ©2009
Conceitos básicos
• Programas precisam ser carregados 
na memória e associados a um 
processo para poderem ser 
executados
• Fila de entrada: processos que 
estejam no disco esperando para 
serem carregados na mem.
• Há vários passos a serem seguidos 
antes dos processos poderem 
executar
Operating System Concepts – 8th Edition 5 Silberschatz, Galvin and Gagne ©2009
Vinculação de endereços (ligação)
• Programas em linguagem de alto nível (quase) nunca 
referenciam endereços específicos de memória:
° ex.: C define variáveis globais, locais e dinâmicas, mas não define 
endereços específicos para elas
° Dependendo da linguagem, do S.O. e do HW, há diversos momentos 
onde a associação entre os comandos e a memória pode acontecer:
• Tempo de compilação
• Tempo de carga
• Tempo de execução
Operating System Concepts – 8th Edition 6 Silberschatz, Galvin and Gagne ©2009
Vinculação de endereços (ligação)
• Tempo de compilação
° Se houver uma definição fixa sobre localização o compilador pode 
gerar endereços diretamente
° Se for preciso mudar os endereços, é preciso recompilar o programa
° Comum para elementos com endereços definidos pelo HW (ex., vetor 
de interrupções)
° Ocorre também na vinculação de símbolos definidos e acessados em 
módulos diferentes de um programa
Operating System Concepts – 8th Edition 7 Silberschatz, Galvin and Gagne ©2009
Vinculação de endereços (ligação)
• Tempo de carga:
° Compilador gera anotações sobre acessos relacionados a certos 
endereços
° O carregador (loader) lê essas anotações e altera o código do 
programa carregado para inserir os endereços adequados a cada caso
° Endereços ganham valor a partir do momento que sabe-se a posição 
inicial do programa
Operating System Concepts – 8th Edition 8 Silberschatz, Galvin and Gagne ©2009
Vinculação de endereços (ligação)
• Tempo de execução:
° Em alguns casos a localização de um processo na memória pode 
mudar em tempo de execução
° Nesse caso o HW deve prover suporte especial
° É preciso refazer vínculos eficientemente
• Mapas de endereços
• Tabelas de relação
• Endereçamento relativo
Operating System Concepts – 8th Edition 10 Silberschatz, Galvin and Gagne ©2009
Endereços lógicos x físicos
• End. lógico: gerado pela CPU (virtual, posição relativa)
• End. físico: visto pela unidade de memória (real)
Operating System Concepts – 8th Edition 18 Silberschatz, Galvin and Gagne ©2009
Swapping
• Processos podem ser transferidos entre memória 
principal e secundária (ex.: processos suspensos)
• Exigem relocação ao serem recarregados
• Maior overhead é o tempo de transferência
Processo
P4
(700K) Processo
P6
(900K)
Sistema
Operacional
P5
P4
P3
0
400K
1000K
2000K
2300K
2560K
1700K
900K
(1) Swap out
(2) Swap in
Operating System Concepts – 8th Edition 19 Silberschatz, Galvin and Gagne ©2009
Alocação contígua
• Forma simples de utilização da memória, duas partições:
 → (1) S.O. residente (memória baixa, vetor interrupções) ; (2) Processo de usuário
• Alocação contígua: cada processo ocupa um bloco único da memória física 
• É essencial que seja possível fazer relocação dinâmica e proteção entre as 
áreas de memória:
Operating System Concepts – 8th Edition 22 Silberschatz, Galvin and Gagne ©2009
Alocação contígua com 
múltiplos processos
• Cada processo ocupa um bloco da memória
• Ao terminar, bloco é liberado (buraco)
• Processos que chegam ocupam buracos
• S.O. deve controlar partições e buracos
• Relocação por tabela ou registrador base
Sistema
Operacional
P1
P2
P3
0
400K
1000K
2000K
2300K
2560K
Sistema
Operacional
P1
P3
0
400K
1000K
2000K
2300K
2560K
Sistema
Operacional
P1
P4
P3
0
400K
1000K
2000K
2300K
2560K
1700K
Sistema
Operacional
P4
P3
0
400K
1000K
2000K
2300K
2560K
1700K
Sistema
Operacional
P5
P4
P3
0
400K
1000K
2000K
2300K
2560K
1700K
900K
P2 termina
P1 termina
P4 iniciado
P5 iniciado
Operating System Concepts – 8th Edition 23 Silberschatz, Galvin and Gagne ©2009
Problema de alocação dinâmica:
onde colocar um processo novo?
• First-fit (primeiro apto): primeiro que couber
• Best-fit (mais apto): o de tamanho mais próximo
• Worst-fit (menos apto): sempre o maior buraco
→ First-fit e best-fit se saem melhor que worst-fit em 
termos de velocidade e utilização do espaço.
Operating System Concepts – 8th Edition 24 Silberschatz, Galvin and Gagne ©2009
Fragmentação
• Quebra do espaço em frações não utilizáveis
• Fragmentação externa:
° Memória não utilizada dividida em muitos buracos, 
pequenos demais para serem úteis
• Fragmentação interna:
° Limitações na forma como blocos são alocados podem 
gerar buracos dentro do bloco
° ex., alocação apenas em blocos de 4 KiB
Operating System Concepts – 8th Edition 25 Silberschatz, Galvin and Gagne ©2009
Compactação
• Solução para a fragmentação externa
° Mover blocos ocupados para perto uns dos outros
° Agrupar os buracos em um único bloco maior
° Só é possível com relocação dinâmica
Outra forma de lidar com fragmentação 
externa é permitir alocação não 
contígua (paginação ou segmentação)
Operating System Concepts – 8th Edition 26 Silberschatz, Galvin and Gagne ©2009
Segmentação
• Divisão da memória do processo em unidades
• Baseado na visão lógica do usuário/programador
• Um programa é uma coleção de segmentos de memória 
independentes (código, dados, pilha, ...)
• Cada um pode ser acessado independentemente
° Como se fossem diferentes dimensões
• Tornou-se “popular” ao ser adotada pela Intel
Operating System Concepts – 8th Edition 27 Silberschatz, Galvin and Gagne ©2009
Segmentação
• Mesmos problemas da alocação contígua!
Pilha de execução
Heap
(alocação dinâmica)
Dados
 (variáveis globais)
Código
(instruções)
0
12K
8K
4K
16K
20K
Não segmentado
Código
(instruções)
Segmento 1
Dados
Segmento 2
Heap
Segmento 3
Pilha
Segmento 4
Visão lógica
Código
(instruções)
Pilha
Dados
Heap
Visão física
Operating System Concepts – 8th Edition 30 Silberschatz, Galvin and Gagne ©2009
Segmentação: exemplo
Operating System Concepts – 8th Edition 31 Silberschatz, Galvin and Gagne ©2009
Segmentos compartilhados
Operating System Concepts – 8th Edition 32 Silberschatz, Galvin and Gagne ©2009
Paginação (paging)
• Memória (lógica/física) é dividida em blocos de tamanho 
fixo – potências de 2: p.ex., 4 KiB
• Blocos lógicos (páginas) são mapeadas em blocos 
físicos (quadros) pelo HW
• Endereços lógicos contíguos podem estar em páginas 
diferentes, em quadros não contíguos
• Quadros vazios são gerenciados
• Programa de n páginas requer n quadros (qq)
• Fragmentação interna (a última página)
Operating System Concepts – 8th Edition 34 Silberschatz, Galvin and Gagne ©2009
Paginação
Página 0
Página 1
Página 3
Página 2
Espaço de
endereçamento
Página 0
Página 1
Página 3
Página 2
0
1
2
3
4
5
6
7
Memória física
0
1
2
3
1
4
3
7
Tabela de
páginas
OperatingSystem Concepts – 8th Edition 36 Silberschatz, Galvin and Gagne ©2009
Gerência de quadros livres
Antes da alocação Depois da alocação
Operating System Concepts – 8th Edition 38 Silberschatz, Galvin and Gagne ©2009
Compartilhamento de páginas
Operating System Concepts – 8th Edition 45 Silberschatz, Galvin and Gagne ©2009
Tabelas hierárquicas (multinível)
• Páginas não são muito grandes (4 KiB → 12 bits)
• Se o resto do endereço identificar a página
° Com endereços de 32 bits, pode haver mais de 1 milhão 
de páginas (20 Bits)
° Tabela gigantesca (4 MiB) teria que ser alocada em 
posições contíguas da memória!
• Solução: quebrar o endereço em várias tabelas
° ex.: para 32 bits, dois níveis de tabelas, cada um com 10 
bits
Operating System Concepts – 8th Edition 47 Silberschatz, Galvin and Gagne ©2009
Processo de tradução com 2 níveis
Página nível 1 Página nível 2 Offset
Endereço lógico (32 bits)
Tabela nível 1
Endereços base
Tabela nível 1
Memória física
12 bits10 bits10 bits
Operating System Concepts – 8th Edition 48 Silberschatz, Galvin and Gagne ©2009
Tabelas de páginas por hash
• Comuns em endereços com mais de 32 bits
• Tabelas de mais níveis se tornam proibitivas
• Identificador de página gera um valor de hash
° Tabela de hash com colisão
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition,
Capítulo 9: 
Memória Virtual
Operating System Concepts – 8th Edition 55 Silberschatz, Galvin and Gagne ©2009
Sumário
• Princípios de paginação sob demanda
• Impacto da paginação sob demanda na criação de 
processos
• Algoritmos de substituição de páginas
• Alocação de quadros
• Thrashing
Operating System Concepts – 8th Edition 56 Silberschatz, Galvin and Gagne ©2009
Princípios gerais
• Memória física: memória segmentada/paginada já 
fizeram a separação entre endereço lógico e físico
° O objetivo é manter muitos processos em memória para permitir a 
multiprogramação
• Vamos além! Estendendo a funcionalidade da tabela de 
páginas...
° nem todas as páginas precisam estar na memória física o tempo 
todo, apenas a parte do programa em execução
• ex.: códigos para manipular condições de erros raramente usados
• Memória virtual: permite a execução de processos que 
não estão completamente em memória (física)
Operating System Concepts – 8th Edition 57 Silberschatz, Galvin and Gagne ©2009
Memória Virtual > Memória Física
• Espaço de endereços lógicos pode ser muito maior que o físico → os 
programas podem ser maiores que a memória física!
• A memória virtual torna a tarefa de programar mais fácil: 
° o programador não precisa preocupar com a quantidade de 
memória física disponível
Operating System Concepts – 8th Edition 58 Silberschatz, Galvin and Gagne ©2009
Paginação por demanda
• Tipicamente, carregar todo o programa pra memória pode 
trazer código com opções que o usuário não vá escolher
• Ideia alternativa: trazer as páginas para a memória física 
apenas quando necessárias (“paginação por demanda”)
° Páginas são carregadas apenas quando necessárias na execução do programa
° Páginas que jamais são acessadas jamais são carregadas na memória física!
• Benefícios do uso de Memória Virtual:
° Menos operações de E/S => reduz swap de programas
° Menor área de memória física ocupada => mais programas
° Mais processos/usuários atendidos => melhor utilização da CPU
Operating System Concepts – 8th Edition 59 Silberschatz, Galvin and Gagne ©2009
Extensão do princípio de swap
• Um permutador faz swap de processos inteiros entre memórias
° Processo era visto como um grande espaço de endereçamento contíguo
• Um paginador faz swap das páginas individuais (necessárias) do proc
° Processo agora é visto como uma sequência de páginas
Operating System Concepts – 8th Edition 60 Silberschatz, Galvin and Gagne ©2009
Suporte de hardware
• O bit válido/inválido é usado para controlar a presença (ou não) da 
página (lógica) na memória física (principal)
° Válida: página disponível em memória
° Inválida: página está em disco
Operating System Concepts – 8th Edition 61 Silberschatz, Galvin and Gagne ©2009
Manipulação de erro de página
• Bit inválido para uma página desejada → gera trap
• S.O. testa uma tabela interna do processo (no PCB)
° Referência inválida → aborta o processo (acesso ilegal)
° Referência válida
• Localiza no disco a página ausente
• Localiza um quadro vazio (na lista de quadros livres)
• Carrega a página desejada do disco para o quadro na mem.
• Atualiza a tabela de páginas indicando o bit como válido
• Reinicia a instrução interrompida (pela trap)
• O processo pode acessar a página, já na memória
Operating System Concepts – 8th Edition 62 Silberschatz, Galvin and Gagne ©2009
Erro de página (page fault)
Operating System Concepts – 8th Edition 65 Silberschatz, Galvin and Gagne ©2009
Mem. Virtual: benefícios para a 
gerência de processos
• Redução do custo de criação de processos
° fork() cria processo filho como duplicata do pai
° tradicionalmente, copia o espaço de end. e duplica as páginas
° alternativamente, pai e filho compartilham as mesmas páginas
• págs. são marcadas como páginas de cópia-após-gravação
• se um processo for gravar, será criada uma cópia da pág.
• Acesso a arquivos mapeados em memória
° tratar E/S de arquivo como acesso de rotina à memória
° parte do end. virtual pode ser associado a um arquivo
° pode levar a melhorias significativas de desempenho de E/S
Operating System Concepts – 8th Edition 67 Silberschatz, Galvin and Gagne ©2009
Arquivos mapeados em memória
• Memória virtual: mapeamento do endereço lógico do 
processo a uma área em disco
° Normalmente, o sentido é memória → disco
• No Unix, com o mmap(), pode-se fazer o oposto:
° Conteúdo do disco (arquivo) → espaço de memória
• Simplifica o acesso a arquivos de dados
° Podem ser tratados como vetores na memória
• Permite que processos compartilhem arquivos
Operating System Concepts – 8th Edition 69 Silberschatz, Galvin and Gagne ©2009
Superalocação de memória
• Processo em execução gera erro de página → S.O. determina onde 
ela reside no disco
° E se não houver um quadro vazio? (toda mem. em uso)
° Há necessidade de substituição de páginas
Operating System Concepts – 8th Edition 71 Silberschatz, Galvin and Gagne ©2009
Superalocação de memória
• Quando não houver um quadro vazio, o S.O. pode:
° Encerrar o processo do usuário
• Péssima escolha, pois vai contra o objetivo de otimizar a 
utilização
° Remover um processo da memória
• Boa escolha, mas como remove todos os seus quadros, 
reduz o nível de multiprogramação
° Realizar a substituição de páginas
• Solução mais comum
Operating System Concepts – 8th Edition 72 Silberschatz, Galvin and Gagne ©2009
Substituição de páginas
• Substituição/reposição de 
páginas
° Se nenhum quadro estiver livre
° Encontre uma página que não 
esteja em uso
° Libere o quadro dela
• Grave o conteúdo do quadro no 
espaço de permuta
• Modifique a tabela de páginas 
invalidando a página vítima
° OBS.: a página retirada pode vir a 
ser acessada de novo :(
Operating System Concepts – 8th Edition 74 Silberschatz, Galvin and Gagne ©2009
Substituição de páginas
• Melhoria na seleção da página vítima
° Tabela de páginas inclui bit extra para auxiliar no processo de escolha 
de candidatos
° Bit de modificação (ou bit poluído)
• Bit ligado: página foi modificada desde que foi lida no disco, devemos gravar 
a página no disco, custo maior
• Bit desligado: página não modificada, não precisa gravar no disco, pode ser 
descartada a um custo menor
• Substituição de páginas é essencial para a paginação por demanda
° Completa a separação entrememória física e lógica
° Tamanho do espaço de end. lógico não é mais limitado pela mem. física
° Mem. virtual enorme oferecida ao programador numa mem. física menor
Operating System Concepts – 8th Edition 75 Silberschatz, Galvin and Gagne ©2009
Relação entre falhas 
e nº de quadros disponíveis
• Existem muitos algoritmos de substituição de páginas nos S.O.
° Prefere-se aquele com a taxa de erros de página mais baixa
° Em geral, com a curva abaixo: + quadros → - erros
• OBS.: aumentando a memória física (RAM), aumenta-se os quadros
Operating System Concepts – 8th Edition 88 Silberschatz, Galvin and Gagne ©2009
Alocação de quadros 
para cada processo
• Como alocar a quantidade fixa de memória livre entre os 
vários processos?
° Cada processo precisa de um mínimo de páginas
• Dois esquemas principais:
° Alocação fixa
° Alocação por prioridade
Operating System Concepts – 8th Edition 89 Silberschatz, Galvin and Gagne ©2009
Alocação fixa
• Igual: todos os processos recebem o mesmo nº de 
quadros na memória física
• Proporcional: função do tamanho do processo
si= size of process p i
S=∑ si
m= total number of frames
ai= allocation for pi=
si
S
×m
m=64
si=10
s2=127
a1=
10
137
×64≈5
a2=
127
137
×64≈59
Operating System Concepts – 8th Edition 90 Silberschatz, Galvin and Gagne ©2009
Substituição global x local
• Substituição Global:
° Quadro a ser substituído escolhida do total de quadros
° Mesmo que o quadro esteja alocado a outro processo
° Um processo pode “tomar” quadros do outro
• → um processo não controla sua taxa de erros de página, dependente do 
comportamento de paginação de outros proc.
• Substituição Local
° Quadro tem que ser do próprio processo que gerou o erro
° Nº de quadros de cada processo não muda
• → conj. de págs. em mem. somente é afetado pela paginação do processo
° Paginação local pode “travar” um processo (poderia usar págs. menos 
utilizadas de outros procs.), já o global provê maior vazão de procs.
Operating System Concepts – 8th Edition 91 Silberschatz, Galvin and Gagne ©2009
Thrashing (atividade improdutiva)
• Quando a utilização de CPU diminui, S.O. aumenta a 
multiprogramação
• Mas, se processos não têm páginas “suficientes”
° Erros de página aumentam
° Utilização de CPU diminui
° S.O.: preciso aumentar a multiprog.
° Outro proc. é trazido para a mem.
° Demanda por quadros aumenta
° Erros de página aumentam
• Thrashing → processos estão ocupados apenas fazendo 
swap de páginas e aguardando na fila do paginador
Operating System Concepts – 8th Edition 92 Silberschatz, Galvin and Gagne ©2009
Localidade de referência 
e Thrashing 
• Por que memória virtual funciona? → localidade de referência
° Localidade é o conjunto de páginas que são ativamente usadas juntas
° Processo migram entre áreas de acesso (estruturas do programa e dos dados)
° Áreas podem se sobrepor ao longo do tempo (ex.: variáveis locais e globais)
• Localidade em padrão de acesso
° Uma função define uma localidade
e referências de memória feitas para
• Chamada da função
• Variáveis locais e globais
• Por que thrashing ocorre?
° ∑ localidades > memória total
Operating System Concepts – 8th Edition 101 Silberschatz, Galvin and Gagne ©2009
Impacto do padrão de acesso
int A[][] = new int[1024][1024];
// linha = uma pág.; memória < 1024 quadros
1024 x 1024 page 
faults
1024 page faults
for (j = 0; j < A.length; j++)
    for (i = 0; i < A.length; i++)
         A[i,j] = 0;
for (i = 0; i < A.length; i++)
    for (j = 0; j < A.length; j++)
       A[i,j] = 0;
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition,
Fim dos Capítulos 8 e 9
	Slide 1
	Slide 2
	Slide 3
	Background
	Binding of Instructions and Data to Memory
	Slide 6
	Slide 7
	Slide 8
	Logical vs. Physical Address Space
	Slide 18
	Contiguous Allocation
	Contiguous Allocation (Cont.)
	Dynamic Storage-Allocation Problem
	Fragmentation
	Slide 25
	Slide 26
	Slide 27
	Slide 30
	Slide 31
	Paging
	Slide 34
	Free Frames
	Shared Pages Example
	Hierarchical Page Tables
	Slide 47
	Hashed Page Tables
	Slide 54
	Chapter 6: CPU Scheduling
	Chapter 10: Virtual Memory
	Virtual Memory That is Larger Than Physical Memory
	Demand Paging
	Transfer of a Paged Memory to Contiguous Disk Space
	Page Table When Some Pages Are Not in Main Memory
	Page Fault
	Steps in Handling a Page Fault
	Process Creation
	Memory-Mapped Files
	What happens if there is no free frame?
	Slide 71
	Slide 72
	Page Replacement
	Graph of Page Faults Versus The Number of Frames
	Allocation of Frames
	Fixed Allocation
	Global vs. Local Allocation
	Thrashing
	Thrashing
	Slide 101
	Slide 103