Gerenciamento de Memória
Parte I
•Gerenciamento básico de memória
•Troca de processos
•Memória virtual
•Algoritmos de substituição de páginas
Parte II
•Modelagem de algoritmos de substituição de páginas
•Questões de projeto para sistemas de paginação
•Questões de implementação
•Segmentação
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
1
Gerenciamento de Memória
• Idealmente, o que todo programador deseja é
dispor de uma memória que seja
– grande
– rápida
– não volátil
• Hierarquia de memórias
– pequena quantidade de memória rápida, de alto custo cache
– quantidade considerável de memória principal de
velocidade média, custo médio
– gigabytes de armazenamento em disco de velocidade e
custo baixos
• O gerenciador de memória trata a hierarquia de
memórias
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
2
Multiprogramação
com Partições Fixas
•
Partições fixas de memória
a) filas de entrada separadas para cada partição
b) fila única de entrada
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
3
Modelagem de Multiprogramação
Maioria dos processos é CPU-Bound
Maioria dos processos é IO-Bound
Utilização da CPU como uma função do número
de processos na memória
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
4
Análise de Desempenho de
Sistemas de Multiprogramação
• Chegada de 4 jobs e suas necessidades de trabalho
• Utilização da CPU por até 4 jobs com 80% de espera por E/S
• Sequência de eventos entre chegada e término dos jobs
– Note que os números mostram quanto tempo da CPU cada job obtém
em cada intervalo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
5
Relocação e Proteção
• Não se sabe com certeza onde o programa será
carregado na memória
– Localizações de endereços de variáveis e de código de
rotinas não podem ser absolutos
• Uma possível solução: instruções do programa são
modificadas segundo a partição de memória em
que ele será carregado
• Uma solução para relocação e proteção: uso de
valores base e limite
– localizações de endereços são somadas ao valor base
antes de serem mapeadas na memória física
– localizações de endereços maiores que o valor limite
indicam erro
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
6
Troca de Processos (1)
• Alterações na alocação de memória à medida que
processos entram e saem da memória
• Regiões sombreadas correspondem a regiões de
memória não utilizadas naquele instante
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
7
Troca de Processos (2)
a) Alocação de espaço para uma área de dados em
expansão
b) Alocação de espaço para uma pilha com código e
uma área de dados, ambos em expansão
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
8
Gerenciamento de Memória com
Mapas de Bits
a)
Parte da memória com 5 segmentos de processos e 3
segmentos de memória livre
−
−
b)
c)
pequenos riscos simétricos denotam as unidades de alocação
regiões sombreadas denotam segmentos livres
Mapa de bits correspondente
Mesmas informações em uma lista encadeada
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
9
Gerenciamento de Memória
com Listas Encadeadas
Quatro combinações de vizinhança para o processo X em
término de execução
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
10
Memória Virtual
Paginação (1)
Localização e função da MMU
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
11
Memória Virtual - Paginação (2)
A relação entre endereços virtuais e endereços físicos de
memória dada pela tabela de páginas
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
12
Tabelas de Páginas
a) Endereço de 32 bits com 2 campos (PT1, PT2) para
endereçamento de tabelas de páginas
b) Tabelas de páginas com 2 níveis
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
13
Tabelas de Páginas
Entrada típica de uma tabela de páginas
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
15
Memória Associativa ou TLB
TLB para acelerar a paginação
TLB = Translation Lookaside Buffer
(tabela das traduções de endereços mais recentes em um dispositivo; funciona como uma
cache para tabelas de página)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
16
Algoritmos de Substituição de
Páginas
• A falta de página força uma escolha
– qual página deve ser removida
– alocação de espaço para a página a ser trazida
para a memória
• A página modificada deve primeiro ser salva
– se não tiver sido modificada é apenas sobreposta
• Melhor não escolher uma página que está
sendo muito usada
– provavelmente precisará ser trazida de volta logo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
18
O Algoritmo de Substituição de Página
Não Usada Recentemente (NUR)
•
Cada página tem os bits Referenciada (R) e
Modificada (M)
– Bits são colocados em 1 quando a página é
referenciada e modificada
•
As páginas são classificadas




•
Classe 0: não referenciada, não modificada
Classe 1: não referenciada, modificada
Classe 2: referenciada, não modificada
Classe 3: referenciada, modificada
NUR remove página aleatoriamente
– da classe de ordem mais baixa que não esteja vazia
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
20
Algoritmo de Substituição de Página
Primeira a Entrar, Primeira a Sair
• Mantém uma lista encadeada de todas as páginas
– página mais antiga na cabeça da lista
– página que chegou por último na memória no final da
lista
• Na ocorrência de falta de página
• página na cabeça da lista é removida
• nova página adicionada no final da lista
• Desvantagem
– página há mais tempo na memória pode ser usada com
muita freqüência
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
21
Algoritmo de Substituição de Página
Segunda Chance (SC)
•
Operação do algoritmo segunda chance
a)
b)
lista de páginas em ordem FIFO
estado da lista em situação de falta de página no instante 20,
com o bit R da página A em 1 (números representam instantes
de carregamento das páginas na memória)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
22
Algoritmo de Substituição
de Página Relógio
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
23
Menos Recentemente
Usada (MRU)
• Assume que páginas usadas recentemente logo
serão usadas novamente
– retira da memória página que há mais tempo não é usada
• Uma lista encadeada de páginas deve ser mantida
– página mais recentemente usada no início da lista, menos
usada no final da lista
– atualização da lista à cada referência à memória
• Alternativamente manter contador em cada entrada
da tabela de página
– escolhe página com contador de menor valor
– zera o contador periodicamente
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
24
O Algoritmo de Substituição
de Página WSClock
Operação
do Algoritmo
WSClock
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
29
Revisão dos Algoritmos de
Substituição de Página
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
30
Gerenciamento de Memória
Parte II
Modelagem de algoritmos de substituição de páginas
Projeto para sistemas de paginação
Questões de implementação
Segmentação
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
31
Modelagem de Algoritmos de
Substituição de Página
– Anomalia de Belady
Esperado: quanto
mais molduras de
página a
memória possuir,
menos faltas de
página o
programa terá.
Anomalia: neste
exemplo, o
algoritmo de
substituição FIFO
tem mais faltas
de página (10P)
para mais
molduras (4)...
• FIFO com 3 molduras de página
• FIFO com 4 molduras de página
• P mostra quais referências de página causaram faltas de página
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
32
Algoritmo de Pilha
distância
memória
disco
Estado do vetor de memória, M, após cada item
na cadeia de referências ter sido processado
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
33
A Cadeia de Distâncias: serve para
Previsão de Frequência de Faltas de Página
20
3
3
14
3
11
9
1
8
Possivelmente,
melhor custobenefício
0
Cálculo da freqüência de faltas de página
a)
b)
o vetor C
o vetor F
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
34
Controle de Carga
• Mesmo com um bom projeto, o sistema ainda pode sofrer
paginação excessiva (thrashing)
• Quando o algoritmo PFF (frequência de falta de páginas) indica
– alguns processos precisam de mais memória
– mas nenhum processo precisa de menos (ou seja, nenhum pode ceder
páginas)
• Solução :
Reduzir o número de processos que competem pela memória
– levar alguns deles para disco (swap) e liberar a memória a eles alocada
– reconsiderar grau de multiprogramação
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
35
Tamanho de Página
Tamanho de página pequeno
• Vantagens
– menos fragmentação interna
– menos programa não usado na memória
• Desvantagens
– programas precisam de mais páginas, tabelas
de página maiores
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
36
Espaços Separados de
Instruções e Dados
a) Espaço de endereçamento único
b) Espaços separados de instruções (I) e dados (D)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
37
Páginas Compartilhadas
P2
Dados do processo 2
Dados do processo 1
P1
Dois processos que compartilham o mesmo código
de programa e, por conseqüência, a mesma tabela
de páginas para instruções
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
38
Envolvimento do S.O. com Paginação
Quatro circunstâncias de envolvimento:
Criação de processo
1.


determina tamanho do programa
cria tabela de página
Execução de processo
2.

Inicia MMU (Unidade de Gerenciamento de Memória) para novos
processos
Ocorrência de falta de página
3.



determina endereço virtual que causou a falta
descarta, se necessário, página antiga
carrega página requisitada para a memória (swap)
Terminação de processo
4.

Libera tabela de páginas, páginas, e espaço em disco que as
páginas ocupam
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
39
Gerenciamento da falta de páginas
1) Chamadas do kernel pela MMU - hardware desvia a
execução para o núcleo (kernel)
2) Salvamento dos registradores de uso geral
3) S.O. determina página virtual requerida
4) S.O. valida endereço e remove página da memória
5) Se página modificada, escreve para o disco
6) S.O. lê página do disco e põe na memória principal
7) Atualiza tabelas de páginas
8) Executa do começo a instrução que provocou a falta
9) Processo colocado em “pronto”
10) Registradores restaurados
11) Programa continua
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
40
Fixação de Páginas na Memória
• Memória virtual e E/S interagem ocasionalmente
• Processo (1) emite chamada ao sistema para ler do
disco para o buffer
– enquanto espera pela E/S, outro processo (2) inicia
– ocorre uma falta de página para o processo 2
– buffer do processo 1 pode ser escolhido para ser levado
para disco – problema!
• Solução possível
– Fixação de páginas envolvidas com E/S na memória
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
41
Memória Secundária
(a) Paginação para uma área de troca estática
(b) Páginas alocadas dinamicamente em disco
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
42
Segmentação (1)
, que contém a análise
sintática do programa
variáveis
• Espaço de endereçamento unidimensional com tabelas
crescentes
• Uma tabela pode atingir outra…
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
43
Segmentação (2)
Permite que cada tabela cresça ou encolha,
independentemente
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
44
Comparação entre paginação e segmentação
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
45
Infra-estrutura de Software
Sistemas de Arquivos
•Arquivos
•Diretórios
•Implementação do sistema de arquivos
•Gerenciamento de espaço em disco
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
46
Armazenamento da Informação
a Longo Prazo
1. Deve ser possível armazenar uma
quantidade muito grande de informação
2. A informação deve sobreviver ao término do
processo que a usa – persistência
3. Múltiplos processos devem ser capazes de
acessar a informação concorrentemente –
compartilhamento
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
47
Nomeação de Arquivos
Extensões típicas de arquivos
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
48
Estrutura de Arquivos
•
Três tipos de arquivos
a) seqüência de bytes
b) seqüência de registros
c) árvore
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
49
Tipos de Arquivos
Identifica arquivo
como executável
Endereço no qual a
execução deve
iniciar
Mais adiante...
Para uso na
memória
Para
depuração
(a) Um arquivo executável (b) Um repositório (archive)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
50
Acesso aos Arquivos
• Acesso sequencial
– lê todos os bytes/registros desde o início
– não pode saltar ou ler fora de seqüência
– conveniente quando o meio era a fita magnética
• Acesso aleatório
– bytes/registros lidos em qualquer ordem
– essencial para sistemas de bases de dados
– ler pode ser …
• mover marcador de arquivo (seek), e então ler ou …
• ler e então mover marcador de arquivo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
51
Atributos de Arquivos
para quando
registro é
consultado
usando uma
‘chave’
Possíveis atributos (flags) de arquivos
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
52
Operações com Arquivos
1. Create
2. Delete
3. Open
4. Close
5. Read
6. Write
Pearson Education
7. Append
8. Seek: ponteiro
para acesso
aleatório
9. Get attributes
10.Set Attributes
11.Rename
Sistemas Operacionais Modernos – 2ª Edição
53
Diretórios
Sistemas de Diretório em Nível Único
• Um sistema de diretório de nível único
– contém 4 arquivos
– propriedades de 3 pessoas diferentes, A, B, e C
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
54
Sistemas de Diretórios
em Dois Níveis
As letras indicam os donos dos diretórios e arquivos
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
55
Sistemas de Diretórios Hierárquicos
Um sistema de diretório hierárquico
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
56
Nomes de Caminhos (pathnames)
Uma árvore de diretórios UNIX
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
57
Operações com Diretórios
1.
2.
3.
4.
Create
Delete
Opendir
Closedir
Pearson Education
5. Readdir
6. Rename
7. Link
8. Unlink
Sistemas Operacionais Modernos – 2ª Edição
58
Implementação do Sistema
de Arquivos
Master Boot Record:
Registro Principal do Boot,
usado para iniciar o
computador
Principais parâmetros do
sistema de arquivo – ex. tipo
do sistema de arquivos,
número de blocos do
sistema
Estrutura de dados com
informações sobre um
arquivo, sendo um i-node
por arquivo
Um possível layout de sistema de arquivo
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
59
Implementação de Arquivos (1)
(a) Alocação contígua do espaço em disco para 7 arquivos
(b) Estado do disco depois dos arquivos D e E terem sido removidos
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
60
Implementação de Arquivos (2)
Término de A
Armazenamento de um
arquivo como uma lista
encadeada de blocos de
disco
Pearson Education
Término de B
Sistemas Operacionais Modernos – 2ª Edição
61
Implementação de Arquivos (3)
Um exemplo de i-node
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
62
Implementação de Diretórios
(a) Um diretório simples
entradas de tamanho fixo
endereços de disco e atributos na entrada de diretório
(b) Diretório no qual cada entrada se refere apenas a um i-node
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
63
Arquivos Compartilhados (1)
Sistema de arquivo contendo um arquivo compartilhado
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
64
Arquivos Compartilhados (2)
(a) Situação antes da ligação
(b) Depois de a ligação ser criada
(c) Depois de o proprietário (C) remover o arquivo (i-node deixado
intacto para evitar erro, já que B não é o proprietário – e continua
na conta de alocação de C…)
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
65
Gerenciamento do
Espaço em Disco
Considerações relevantes:
• Tamanho do bloco: eficiência
• Monitoramento de blocos livres (ex. mapas de
bits)
• Cotas de usuários
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
66
O que vimos:
Módulo I
• Conceitos: SO (“máquina estendida”),
Processo e outros
• Escalonamento de Processos
• Entrada/Saída
• Gerenciamento de Memória
• Sistemas de Arquivos
S e g u e…
Pearson Education
Sistemas Operacionais Modernos – 2ª Edição
67
Próximas Datas Importantes
• 22/04/2008
• 24/04/2008
• 29/04/2008
Pearson Education
Lab: Processos,
Escalonamento, I/O,
Memória e
Aula de revisão
1º Exercício Escolar
Entrega dos projetos
Sistemas Operacionais Modernos – 2ª Edição
68