4/16/15
Gerência de Memória
1.  Introdução
•  Realocação e Proteção
2.  Gerência básica de Memória
•  Registradores base e limite
•  MMU e troca de contexto
•  Multiprogramação c/ partições fixas
3.  Swapping
4.  Gerência de Memória no Minix
5.  Paginação (Memória Virtual)
•  Algoritmos para troca de páginas
•  Questões de Projeto e Implementação
•  Tabelas de páginas invertidas
6.  Segmentação
1
Gerência de Memória
•  O Gerente de Memória é um componente do Sistema
Operacional (contido inteira-ou parcialmente no kernel)
que aloca memória principal para os processos, e gerencia
a hierarquia de memória (Caches, RAM, e Disco)
•  Suas tarefas:
– 
– 
– 
– 
– 
– 
– 
Garante isolamento mútuo entre processos (proteção)
Mantém o registro das áreas de memória em uso
Aloca memória RAM para novos processos (no fork())
Faz o swapping transparente entre memória principal e disco
Atende a requisições de aumento de memória
Mantém o mapeamento de memória virtual para memoria fisica
Implementa a política de alocação de memória para os processos
2
1
4/16/15
Gerência de Memória
Lei de Parkinson: Programas sempre aumentarão de tamanho,
demandando toda a memória disponível
O ideal seria ter memória:
–  Infinitamente grande, com
acesso infinitamente rápido,
não-volátil e de baixo custo
Hierarquia de memoria
–  0.5-2 MB de caches (L1-L3):
muito rápidos, porém caros
–  0.5- 2 GB de RAM de
velocidade e preço médios
–  101-102 GB de disco: lento,
mas barato
Hierarquia de Caches e memória principal
3
GM para Monoprogramação
(sem swapping ou paginação)‫‏‬
Para S.Os com único usuário e dispositivos simples
(embarcados). Execução de um processo por vez.
•  Ciclo básico: Evento de E/S (p.ex. comando do usuário) è
carregamento programa è execução
•  Baixa utilização de CPU
Fig: Possíveis alocações de memória (monoprogramação)
4
2
4/16/15
Efeito da Multiprogramação
Degree of multiprogramming
Utilização da CPU como função do grau de multiprogramação (=
número de processos na memória)‫‏‬
5
Realocação e Proteção
São dois problemas introduzidos pela Multiprogramação:
•  Realocação: não se sabe de antemão em qual região de memória o
processo vai ser executado
–  Endereço de variáveis e do código não podem ser absolutos
•  Proteção: evitar que um processo acesse uma região usada por
outro processo
Solução 1: modificar endereços quando processo é carregado (o
ligador/carregador precisa ter um bit map sobre quais endereços do
programa precisam ser atualizados)‫‏‬
–  Como endereços são absolutos, seria possível acessar qualquer endereço de
memória, e um programa pode construir dinamicamente instruções
Solução melhor: Mapeamento para a memória física ocorre em tempo
de execução e é relativa a dois registradores: base e limite
–  Qualquer acesso à memória fora desses limites é considerado erro e processo
é abortado
6
3
4/16/15
Registradores Base e Limite
Para cada processo, existe um par, Base Register (BR), e Limit Register (LR),
que determinam a região de memória usada pelo processo
End. Lógico (*)
CPU
≤ LR?
End. Físico
Sim
Não
+
RAM
BR
Falha de acesso
Cabe à MMU (Memory Management Unit) fazer essa conversão.
A cada troca de contexto de processos, o par (BR/LR) precisa ser trocado.
Isso é o “memory map” do processo.
7
Técnicas baseadas em realocação
Questão: Organização espacial da memória:
1.  Memória com partições fixas (isto é, BR e LR só podem
assumir determinados valores)
Alternativas: Fila de espera de processos por tamanho de partição
versus Fila única
2.  Possibilidade de divisão/aglomeracão de partições
Fila única de partições
partições tem 2x bytes (p.ex.: 210 ↔ 2 partições de 29)‫‏‬
3.  Memória RAM sem partições (BR e LR assumem qualquer
valor)‫‏‬
Questão: permanência de processos na memória
a)  Processos/jobs mantém a mesma região durante toda a sua
execução OU
b)  Processos podem ser retirados da memória, e posteriromente
voltar à memória em outra região/partição (swapping)
8
4
4/16/15
Organização espacial de Memória
4 MB
2 MB
2 MB
512 KB
1 MB
1 MB
(a) Partições de tamanho
fixo
(b) Partições de 2i bytes
podem se agurpar e se
dividir
(c) Sem partições
Multiprogramação com partições fixas
Presente nos computadores de 1a. e 2a. geração
Exemplos: IBM OS/360
(+) simples de implementar
Filas de entrada separadas:
(-) processos menores não podem ser colocados em partições grandes
disponíveis.
Fila única:
–  Seleção First-Fit , Best Fit , Worst Fit
10
5
4/16/15
Swapping
Em sistemas com compartilhamento de tempo (timesharing), a memória
principal pode não ser suficiente para todos os processos.
Por exemplo:
•  existem muitos processos interativos (orienatdos a E/S) de muitos
usuários), ou
Ou um processo requisita mais memória para continuar a execução.
Ideia básica: usar espaço em disco como extensão da memória RAM(1), e
colocar lá os processos enquanto estiverem bloqueados (esperando por
E/S), carregando-os de volta para a memória assim que são desbloqueados
Pode ser usado para qualquer organização espacial de memória
(1) Partição de swapping ou paginação
12
Swapping
Main Memory
Disk (swap partition)
Duas alternativas:
•  Copiar a imagem inteira (swapping)
•  Permitir que processo fique parcialmente em memória, e
parcialmente em disco (paginação) è Memória Virtual
6
4/16/15
Swapping
Quando um processo é bloqueado (espera por E/S) ele pode ser swapped
out, e depois swapped in para memória principal.
Permite manter um número maior de processos ativos, aumentando a
utilização da CPU
Fig.: Sequência de alocação de memória usando swapping para 4 processos.
Pode acarretar:
–  Regiões de memória não utilizada (“buracos”) de qualquer tamanho
–  Um mesmo processo pode ocupar diferentes partições ao longo de sua
execução
14
Swapping
Principal problema do swapping com partições de tamanho variável:
•  Manter a informação sobre espaços não utilizados (livres)
•  Evitar uma fragmentação externa da memória (= espaços pequenos
não utilizados)‫‏‬
p1
p3
p4
Fragmentação = parcela da
memória desperdiçada
devido a imagens de
processos não diretamente
adjacentes.
Frag. interna = quando há
partições fixas;
Frag. externa = quando não
há partições
OS
•  Compactação de memória é muito custosa
–  São gastos milisegundos
15
7
4/16/15
Swapping
Também é usado para lidar com processos que aumentam sua
demanda de memória. Algumas alternativas:
a)  alocar uma partição para o processo que é adjacente a uma partição livre
b)  Alocar uma partição conjunta para a pilha e o heap, e faze-los crescer em
sentidos opostos.
Quando processo usa todo espaço de memória disponível, fazer um swap-out, e
um swap-in em uma partição maior (mas, se disco de swap está cheio, processo
precisa ser terminado)‫‏‬
16
Gerenciamento de espaços disponíveis
Idéia: dividir a memória em unidades de alocação de n bytes (1 KB no
Minix) e representar a ocupação de (livre/ocupado) de lotes de unidades
usando um bit map ou então uma lista encadeada
Fig: Representação da ocupação da memória com 5 processos e 3 lacunas em Bit
Map ou Lista encadeada
Bit Map: armazenamento compacto e simples, mas busca por determinado
tamanho de lote livre pode envolver análise de várias palavras (no bit map)
Lista ligada : cada nó contém o endereço inicial e o tamanho de uma partição
ocupada ou livre
17
8
4/16/15
Gerenciamento de Memória com Listas
•  Quando processo é swapped out, a lacuna correspondente precisa ser combinada
com espaços vizinhos livres.
•  Quando processo é swapped in, percorre-se a lista buscando um espaço livre
suficientemente grande (lista geralmente ordenada por endereços de memória)‫‏‬
è
è
è
è
Fig: Quando X é swapped out: quatro combinações de nós na lista
Possíveis critérios de escolha de espaço livre:
•  First Fit – aloca o primeiro espaço encontrado
•  Best Fit – percorre toda a lista e aloca o menor possível espaço è pode deixar
fragmentos muito pequenos para alocação para outros processos
•  Worst Fit – percorre toda a lista e aloca o maior possível espaço
18
Gerenciamento de Memória com Listas
Qualquer um dos algoritmo é mais eficiente se houverem 2 listas:
lista de memória em uso e lista de espaços livres
•  Listas são mantidas ordenadas por tamanho (# de unidades de alocação)‫‏‬
•  Problema: exige um processamento adicional sempre quando ocorre uma
liberação de memória (precisa-se verificar se há espaços adjacentes livres e
inserir o novo espaço na posição correta da lista).
Alternativa:
Quick Fit: mantém listas separadas por tamanho do espaço livre (2K, 4K, 8K, etc.)‫‏‬
•  Problema: ao liberar memória, o novo espaço criado precisa ser inserido na fila
correspondente (possivelmente, após combinação com áreas vizinhas)‫‏‬
4K
8K
16K
32K
64K
other
19
9
4/16/15
Gerenciamento de Memória em Minix3
•  Implementado pelo PM
•  Com swapping e nem paginação (processo carregado
permanece exatamente na partição alocada)
•  Motivos:
–  Ser compatível com processador Intel 8088, que não possui MMU
–  Menor complexidade do código
–  Possibilitar a portabilidade para outras arquiteturas (sist.
embarcados), também sem MMU
•  Memória sem partições
•  Espaços livres em lista encadeada e seleção usando politica
First Fit
•  O mapa de memória (qual segmento está alocado em qual
endereço de memória) é mantido pelo system task (no
núcleo) è separação de política e mecanismo
Gerenciamento de Memória no Minix3
•  Cada processo contém 2 (ou 3) segmentos, que são mapeados para uma
partição contígua de memória
–  Texto (segmento I) , dados (D) e pilha
–  Segmentos I e D podem ser alocados juntos (modo combinado) ou separado
•  Na tabela de processos (mproc.h), campo mp_seg[] é um vetor para os
segmentos de texto, heap e pilha.
•  Cada elemento deste vetor contém os endereços virtual e real de cada
segmento
210K (0x34800)‫‏‬
stack
0x8
208K (0x34000)‫‏‬
207K (0x33c00)‫‏‬
0xd0
0x2
0xc8
0x7
0xc8
data
203K (0x32c00)‫‏‬
Obs: 0 significa
text
200K (0x32000)‫‏‬
segmentos combinados I+D;
Tudo em unidades de Click = 1KB
21
10
4/16/15
Gerenciamento de Memória em Minix3
•  Fork copia endereços de segmentos do pai para o filho
•  Exec libera espaço ocupado (cópia da imagem pai) e procura-se por
espaço livre que comporte a nova imagem
•  Processo não aumenta o tamanho de sua imagem, que é determinado
(estaticamente) no cabeçalho no executável (formato do a.out)
•  Pilha e heap crescem em sentidos opostos.
•  Somente quando heap é atualizado (BRK system
call) o limite da pilha é atualizado
•  Motivo: compatibilidade com 8088 e
processadores mais simples, que não possuem
interrupção que detecta avanço da pilha sobre o
heap
pilha
data
text
22
Chamadas de sistema relacionadas a
gerência de memória
•  fork() - cria processo filho
PM clona a imagem do chamador, que é posicionada na
primeira lacuna disponível.
•  exec() - carrega executável a ser executado por chamador
PM libera a área de memória do chamador e procura outra
lacuna suficentemente grande para o executável indicado
•  exit() - termina o chamdor e libera a memória que estava
alocada a ele
•  wait()‫‏‬
•  brk() – gerado por um malloc()
11
4/16/15
Efeito de um fork() & exec()
Memória Virtual
É necessária, quando o total de memória necessária para um
conjunto de processos excede o tamanho da memória física.
Também aqui, usa-se parte do disco como extensão da
memória RAM.
Usa a técnica de paginação:
•  Espaço de endereçamento lógico de cada processo e memória
física são divididos em partições de mesmo tamanho fixo
(chamados de páginas e quadro de páginas)
•  Em vez de fazer o swap in/out de uma imagem inteira de
processo, cada página pode ser movida do disco para a
memória e vice-versa.
•  Em cada acesso a memória o hardware verifica se a página
correspondente está na memória, e se não for o caso, então um
tratador de páginas faltantes (page-fault) a copia para lá.
•  A espera pela cópia para a memória de uma página é
equivalente a um bloqueio por E/S
38
12
4/16/15
Paginação
Requer da existência de suporte por hardware (Memory
Management Unit -MMU)
–  MMU intercepta qualquer acesso à memória (p/ instruções e dados)
–  Mapeia endereços lógicos para endereços físicos (através de uma tabela
de página)‫‏‬
–  Quando página acessada não está em memória, gera uma interrupção de
falta de página (page fault), que causa a interrupção do processo em
execução e o seu bloqueio até que a página tenha sido copiada
39
Exemplo Memória Virtual
Exemplo: tamanho página = 4KB (varia
de 512 Bytes a 64 KB)‫‏‬
Um espaço de endereçamento virtual de
64K é mapeado em 32KB de
memória RAM
Número da página é usada como índice
para a tabela de páginas (TP)
Cada entrada na TP contém, entre
outros:
•  Bit presença: se página está em
memória
•  Se estiver, o número do quadro
correspondente
Endereço lógico X é mapeado para
endereço físico:
TP(X/ 4K) + X % 4K
40
13
4/16/15
Tabela de Páginas
Exemplo: Operação
interna a uma MMU
com 16 páginas de
tamanho 4 KB cada
Composição do endereço
lógico:
•  Bits mais significativos =
número da página
•  Bits menos significativos =
deslocamento do endereço
dentro de uma página
41
Paginação
• Região de memória física ocupada por um processo não precisa
ser contíguo
• Memória física é particionada em quadros de página (frames) de
tamanho 2x bytes
• Espaço de endereçamento lógico é dividido em páginas de
tamanho 2x bytes
• Cada endereço lógico é composto do par (número-da-página,
deslocamento), onde número-página é usado como índice para
uma entrada na tabela de páginas
Exemplo: páginas de 4 K para endereços de 32 bits:
Número-da-página
20 bits
deslocamento
12 bits
Obs:
- Em paginação, de certa forma, tem-se um registrador de realocação
por página
- Evita fragmentação externa, mas causa fragmentação interna
42
14
4/16/15
Paginação
CPU
pg
o
P0
0
P3
P1
1
P2
P2
2
P1
P3
3
fr
mem—ria
l—gica
pg: no. da página
fr: no. do quadro
o: offset (deslocamento)‫‏‬
o
4
0
6
1
2
2
1
3
0
4
5
6
P0
7
mem—ria
f’sica
tabela de
p‡ginas
Processo pode ser executado, contanto que haja um número mínimo de
páginas na memória (as páginas sendo acessadas)
O espaço de endereçamento lógico é contiguo, mas o espaço físico
respectivo é distribuído/separado.
A tradução é feita de forma transparente pela MMU, que acessa a
TabPaginas, e mantém um cache das páginas recentemente consultadas.
43
Paginação
Cada processo possui a sua tabela de páginas, que precisa ser carregada na
MMU cada vez que ocorre troca de contexto.
Cada entrada na Tabela de Processos contém um ponteiro para a tabela de
páginas do processo. O dispatcher é o encarregado de "carregar" a nova
tabela de páginas na MMU.
Como qualquer acesso à memória ocorre através do mapeamento pela TP. Isso
fornece também automaticamente um mecanismo de proteção...
... contanto que o preenchimento da tabela de página seja feita em modo
privilegiado (supervisor)!!
=> à medida que as páginas vão sendo alocadas, o núcleo preenche as entradas
na tabela de página.
Além disto, kernel precisa manter informações sobre o conjunto de quadros
disponíveis na memória principal:
Para isso, possui uma tabela de quadros (frame-table), com uma entrada por
quadro, informando se o mesmo está alocado, e para qual página de qual
processo.
=> De maneira geral, a paginação aumenta o tempo de troca de contexto. Por
que?
44
15
4/16/15
Controle de acesso
Paginação pode ser estendida para incorporar controle de acesso para
cada página:
• além do número do quadro, cada entrada da TP contém bits para o tipo
de acesso permitido: Por exemplo
somente-leitura(R), leitura-e-escrita(W) ou somente-execução(X)
• se acesso requisitado viola o permitido, a MMU gera a interrupção
“violação de acesso de memória”
• a validade de uma operação sob um endereço lógico pode ser testada
em paralelo com a obtenção do endereço físico correspondente.
Além disto, pode se usar bits valido/inválido para marcar as páginas
lógicas que efetivamente compõem o espaço de endereçamento
lógico do processo
• é útil para espaços de endereçamentos grandes e utilizados de forma
descontínua
• note-se que devido ao problema do não alinhamento de dados com os
limites das páginas, esse tipo de controle de acesso não é muito preciso.
45
Entrada da Tabela de Páginas
Resumo dos campos/flags:
•  Caching: se faz sentido guardar essa entrada da TP no cache
•  Referenced: se houve acesso a algum endereço da página nos
últimos ∆t
•  Modified: se houve acesso de escrita a algum endereço da
página nos últimos ∆t
•  Protection: Controle de acesso
•  Present: se página está na memória
•  Número do quadro na memória física (page frame number)
46
16
4/16/15
Tabela de Páginas (TP)
Possíveis implementações:
1) TP é um conjunto de registradores dedicados, que são carregados
através de instruções privilegiadas (ex. DEC PDP-11)‫‏‬
Pró: não necessita de MMU e tradução é veloz
Contra: número de entradas é pequeno (tipicamente 16-256)‫‏‬
2) TP é mantida em memória principal
- mantém-se um registrador com o endereço base da tabela (Process
Table Base Register, PTBR) e entrada na tabela = PTBR +
#página_virtual
Prós:
•  possibilita tabelas de páginas arbitrariamente grandes
•  a troca de contexto envolve somente PTBR
Contras:
•  tempo de acesso à memória duplica, devido ao acesso inicial à tabela de
páginas
47
A tabela de páginas
Possíveis implementações (cont.):
3) utilização de um Translation Look-aside Buffer (TLB)‫‏‬
- TLB = vetor associativo que permite comparação paralela com suas
entradas (de 8 - 128 entradas)
- é um cache das entradas da TabPaginas recentemente acessadas (è
princípio de localidade)‫‏‬
- quando uma página lógica é acessada e seu mapeamento não está
no TLB (TLB miss) então:
* acesssa-se a TabPaginas e coloca-se a entrada no TLB
* se a página está em memória, operacão é completada; senão
gera-se uma interrpção Page-fault
- a cada troca de contexto, o TLB precisa ser zerado
Vantagem: tradução rápida
Desvantagem: requer gerenciamento do conteúdo do TLB
(substituição de entradas)
48
17
4/16/15
Translation Look-aside Buffer
A razão de (TLB hits/acessos à memória) determina a eficiência da tradução e é
usada para calcular o tempo médio de acesso à memória
Razão de TLB hits depende do tamanho do TLB e da estratégia de troca de
entradas
49
Funcionamento do TLB
Ao receber um novo indice de página (I) todas as entradas do
TLB são comparadas em paralelo:
•  Se I é encontrado e tipo de acesso é válido, então usa-se a
entrada do TLB (è endereço do quadro)
•  Se tipo de acesso é inválido, gera-se uma falha de proteção (e
processo é abortado)
•  Se I não é encontrado na TLB, (TLB miss), faz-se uma consulta
a TabPáginas (TP) em memória, e copia-se a entrada completa
da TP para o TLB (para agilizar acessos futuros)‫‏‬
•  Quando houver acesso p/escrita, copia-se o flag de escrita
(Modify bit) de TLB para a TabPáginas
Obs: Pode-se aumentar a eficiência da paginação, aumentando-se
o tamanho do TLB.
50
18
4/16/15
TLBs – Translation Lookaside Buffers
Possível configuração do TLB para um programa com:
•  Um loop que percorre páginas 19-21, acessando um vetor nas páginas
129-130. O índice do vetor está em pagina 140 e a pilha em 860-861.
void main() {
structX vector[1000]
int I;
…
while (finished) {
…
vector[i] = …
}
}
51
Tabelas de página
•  Principal problema é que a própria TP precisa estar
em memória.
•  E pior, precisa-se manter uma TP por processo em
execução.
•  Então, dependendo do número de entradas de cada
TP (que depende do tamanho da página), pode ser
inviável, manter todas elas na memória do núcleo.
•  O que fazer?
19
4/16/15
Tabela de Páginas de 2 níveis
Resolve o problema de manter
grandes tabelas de página na
memória (para todos os
processos).
Ideia: fazer a TabPaginas ser paginada
(manter apenas as partes da
TabPagina cujo mapeamento
esteja sendo usado.
2 níveis: tabela raiz (de 1o. nível) e
TabelaPagina de 2o. nível
A tabela raiz contém os ponteiros para
essas partes da TabPaginas .
Second-level page tables
Top-level
page table
Offset = 12 bits
Tam. página= 4K
32 bits page number è 220 entries!
54
Tabela de Páginas de 2 níveis
20
4/16/15
Tabela de páginas Invertidas
Para arquiteturas de 64 bits, o espaço de endereçamento lógico é 264 bytes!
Mesmo se o se tamanho de página é 4KB, isso leva a TPs muito grandes, e.g.
252 ≈ alguns Tera Bytes!).
Por isso, em alguns sistemas usa-se uma TP invertida:
•  Uma entrada p/ cada quadro de página (da memória física)
•  Cada entrada contém uma lista de (processID, PresenceBit, no. da página)‫‏‬
Desvantagem: a tradução de endereços lógicos èfíscios fica bem mais lenta, i.e.
para cada página p, precisa-se fazer uma varredura pela TP invertida para
encontrar o quadro correspondente.
Só é viável, se o TLB for usado para guardar as associações correntes. Somente
quando ocorre um TLB miss, a TP invertida precisa ser pesquisada.
Usa-se também uma função de hash para indexar as entradas da TP invertida.
56
Tabela de Páginas Invertidas
L
Se página não está no TLB, então precisa-se percorrer a tabela
invertida procurando pelo PID e indice da página.
57
21
4/16/15
Paginação e Algoritmos de Substituição de Páginas
Qual
página
substituir?
Page-out
?
Page-in
Fig adaptada de Hussein Abdel-Wahab
http://www.cs.odu.edu/~cs471w/spring14/lectures/virtualmemory.htm
Algoritmos de Substituição de Páginas
A cada page-fault:
•  o gerenciador de memória aloca um quadro de páginas para a
página requisitada e
•  precisa escolher qual página (de um quadro de páginas) deve
ser removida da memória.
O Algoritmo de substituição de páginas determina qual página
deve ser removida e usa as informações estatísticas contidas
nas tabelas de páginas.
Nessa seleção deve levar em conta que:
–  uma página modificada precisa ser copiada para disco,mas uma nãomodificada pode ser sobreescrita
–  não é boa idéia tirar uma página que está em uso , pois ela terá que
ser carregada em breve
59
22
4/16/15
Algoritmo de substituição ideal
•  Substitui a página que será acessada no futuro
mais remoto
–  Infelizmente, não é viável na prática, pois exigiria
um conhecimento sobre todos os acessos futuros
•  Usado apenas em simulações para avaliar o
quanto os algoritmos concretos diferem do
algoritmo ideal
60
Algoritmo Página não recentemente Utilizada
(Not Recently Used - NRU)
• 
Cada página tem um bit de acesso (R) e de Modificação (M):
– 
– 
– 
– 
• 
Bits são setados sempre que página é acessada ou modificada
Pagina é carregada com permissão somente para leitura e M=0.
No primeiro acesso para escrita, o mecanismo proteção notifica o
núcleo, que seta M=1, e troca para permissão de escrita
A cada interrupção do relógio, seta-se R = 0
Páginas são classificadas em 4 categorias
1. 
2. 
3. 
4. 
Não referenciada, não modificada
Não referenciada, modificada
referenciada, não modificada
referenciada, modificada
• 
NRU escolhe primeiro qualquer página (em ordem ascendente
de categoria)
è Razão da prioridade de descarte (#2 antes #3): É melhor manter
páginas sendo referenciadas, do que modificadas mas pouco
referenciadas.
61
23
4/16/15
Algoritmo FIFO de substituição
•  Manter uma lista ligada de todas as páginas na ordem em que
foram carregadas na memória
•  A página (mais antiga), no início da fila, é a primeira ser
descartada
•  Principal Vantagem:
–  Simplicidade de implementação.
•  Principal Desvantagem:
–  Não é levado em conta se uma página está sendo frequentemente acessada
não.
–  Por exemplo: a página mais antiga pode estar sendo acessada com alta
frequência.
62
Algoritmo da Segunda Chance
•  Uma variante do algoritmo FIFO que leva em
conta acessos recentes às páginas:
–  Páginas são mantidas em fila FIFO (ordenada por momento
de carregamento)
–  Se página mais antiga possui bit R=0, ela é removida.
–  Se tiver bit R=1, o bit é zerado, e a página é colocada no
final da fila,. Ou seja: dá se uma 2a chance.
Página carregada há mais tempo.
Página carregada mais
recentemente.
R=1
A página é tratada como se fosse
carregada recentemente.
R=0
63
24
4/16/15
Algoritmo do Relógio
Todos as páginas carregadas estão em uma lista circular.
Ponteiro aponta para a próxima a ser testada
Trata-se simplesmente de uma implementação alternativa para o algoritmo
da 2a. Chance (sem a necessidade de manipular a fila)
64
Algoritmo Menos recentemente utilizada
Least Recently Used (LRU)
Assume que páginas usadas recentemente, deverão ser
usadas em breve novamente.
Princípio: descartar a página que ficou sem acesso durante o
periodo de tempo mais longo
•  Implementação ideal, mas impraticável:
–  Lista de páginas ordenadas pelo acesso mais recente
–  É inviável pois demandaria uma manipulação da lista a cada
acesso de memória!!
•  Alternativa (necessita de apoio de hardware):
–  usar um contador que é incrementado por hardware a cada acesso à memória
–  Cada vez que uma página é acessada, atualiza este contador na entrada da TP
correspondente
–  Seleciona a página com o menor contador
–  Periodicamente, zera o contador
65
25
4/16/15
LRU com Hardware especial
Manipular uma matriz n x n (para n entradas na TP) com o registro de
acessos recentes (linha i = contador da página i)
Idéia: Ao acessar página i preencha toda linha i com bit 1 e, em seguida, toda
coluna i com bit 0. A página mais antiga é aquela com menor valor.
Acesso Pág. 0
Acesso Pág. 1
Acesso Pág. 1
Acesso Pág. 0
Acesso Pág. 2
Acesso Pág. 3
Acesso Pág. 3
Acesso Pág. 2
Acesso Pág. 2
Acesso Pág. 3
66
Not Frequently Used (NFU)
Requer um contador por página.
A cada intervalo de tempo (clock tick) todas as páginas
referenciadas no último intervalo de tempo terão o seu
contador incrementado. Assim, a página com o menor contador
é a candidata a ser substituida.
Principal problema: contabiliza-se apenas a frequência de
acesso, mas não leva-se em conta quando foi esse acesso.
Páginas muito acessadas em passado longínquo permanecem
com alto ibope.
26
4/16/15
Algoritmo do envelhecimento Simulando LRU em Software
Manter um contador para cada página;
•  bit R mantém a informação se página foi acessada durante último
período de tempo (cada tick de relógio):
•  faz-se um shift de 1 bit para a direita no contador de cada página e
adiciona-se o R-bit como bit mais significativo no contador
68
Principais limitações do Alg. de
Envelhecimento (comparado ao LRU)‫‏‬
•  Quando duas páginas possuem o mesmo valor de contador
(de idade), não há como saber qual delas foi acessada por
último (no último período de tempo)
t
Pag.X
Pag.Y
•  Os contadores de idade têm um número finito de bits.
Portanto quando o valor atinge 0, não há como distinguir
se a última referência ocorreu há apenas n ticks do relógio
ou há muito mais tempo.
èNormalmente, basta contador com 8 bits e períodos de 20
ms entre ticks. Se uma página não foi acessada a 160 ms,
provavelmente não é mais relavente.
69
27
4/16/15
Questões de projeto de paginação
Quando um programa gera muitas faltas de página para
poucas instruções executadas, ele se encontra em
Ultra-paginação ( thrashing )‫‏‬
Deve-se tentar minimizar a taxa de page faults:
•  para cada processo em execução, manter número
suficiente número de páginas na memória
•  para processos que tenham sido movidos para disco e
estejam retornando (swapped-in), evitar que todas as
páginas sejam requisitadas individualmente, mas tentar
se antecipar
•  Por isso, precisa-se identificar qual é o conjunto de
páginas em uso corrente por cada processo
Ultra-paginação (Thrashing)
Fenômeno que ocorre quando o gerenciador de memória
fica sobrecarregado com cópias de páginas entre
memória e disco.
Alta frequência de faltas de página: ocorre quando um
processo possui muito menos páginas na memória do
que o seu conjunto de páginas em uso (working-set).
# taxa de falta de
páginas por tempo
# de páginas na memória
71
28
4/16/15
O Conjunto de páginas em uso
A maioria dos processsos apresenta uma localidade de referência
(acessa apenas uma fração pequena de suas páginas).
# páginas
Tamanho do conjunto no instante t
t
•  O conjunto de uso (working set) é o conjunto das páginas
acessadas pelas k referências mais recentes. O sistema de
paginação deve gerenciar este conjunto usando envelhecimento.
•  Quando um processo é escolhido para execução seu working-set
pode ser pré-paginado (em vez de fazer paginação por demanda)‫‏‬
72
Algoritmo de substituição baseado no working set
Mantém-se um contador virtual de tempo e periodicamente, atualiza-se o
contador em cada página que tenha o bit R=1.Working Set consiste
das páginas com contador dentro da janela de tempo [t- τ, t] Se R=0, não é feita autalização. Se (R==0 && age ≤ τ ) avança com tempo virtual
e depois verifica novamente. Descarta-se páginas com R=0 e mais antigas do que τ.
73
29
4/16/15
Resumo dos algoritmos de susbtituição de
página
Nome do Algoritmo
Avaliação/ Comentário
Ótimo – prevendo o futuro
Impossível, mas usado como
benchmark
Not Recently Used (NRU)
Pouco preciso
FIFO
Pode descartar páginas em uso
Segunda Chance
Melhoria significativa comparado
com o FIFO
Least Recently Used (LRU)
Excelente, mas requer
implementacão em hardware
Not Frequently Used (NFU)
Aproximacão do LRU
Aging
Excelente algoritmo com efeito
próximo ao LRU
Worsking Set Clock
Excelente algoritmo
75
Politica de Substituição Local vs. Global?
•  O número de quadros de páginas alocados a cada processo deve
variar?
•  A página a ser substituida deve ser do processo que causou a falta
de página (pol. local), ou de qualquer processo (pol. global)?
Processo A
causou o
page-fault
(a) Configuração original
(b) politica local
(c) politica global
80
30
4/16/15
Política de Alocação Local x Global
Prós and Contras de uma Política Global:
(+) consegue uma alocação mais eficiente da memória, pois leva
em conta flutuações no working set (conj. de trabalho) de todos
os processos
(-) favorece os processos com maior prioridade no escalonamento
(geralmente, os mais orientados a E/S) e penaliza processos
mais orientados a CPU
(-) alocação é mais complexa, pois precisa monitorar o conjunto de
trabalho de todos os processos simultaneamente e comparar a
idade do todas as páginas
(-) o conjunto de trabalho de um processo pode variar muito
rapidamente, e o alg. de envelhecimento não reflete isso
imediatamente
(-) pode tornar a execução de um processo inviável se não possuir
número mínimo de quadros de página.
81
Política de Alocação Local x Global
Freqüência de faltas de página como função do número de molduras
de página alocado
(A)= taxa inaceitavelmente alta de page-fault,
(B)= taxa muito baixa de page-faults, pode-se diminuir # de quadros do processo.
82 O Algoritmo Page Fault Frequency (PFF) fica monitorando essas taxas
para decidir de qual processo vai tirar um quadro de página.
31
4/16/15
Controle de Carga
•  Mesmo com um bom projeto, o sistema ainda pode sofrer
paginação excessiva (thrashing)‫‏‬
•  Quando o algoritmo PFF indica
–  alguns processos precisam de mais memória
–  mas nenhum processo executa bem com menos páginas
•  Solução :
Reduzir o grau de multiprogramação: o número de
processos que competem pela memória
–  levar alguns deles para disco e liberar a memória a eles alocada
–  reconsiderar grau de multiprogramação
•  Existem algoritmos orientados a taxa global de faltas de
página.
83 A questão do tamanho de página
Tamanho de página pequenos:
•  Vantagens
–  Melhor aproveitamento da memória físcica: menos
fragmentação interna
–  mais programas usando a memória
–  melhor alinhamento de segmentos de código e de
estruturas de dado às páginas
•  Desvantagens
–  programas precisam de mais páginas, tabelas de
página maiores, mais tempo para carregar entradas de
tabela nos registradores da MMU
–  Transferência de página menor ou maior de/para disco
demanda aproximadamente o mesmo tempo (mas é
feito de forma mais frequente)
84 32
4/16/15
Tamanho de Página
•  Custo associado ao tamanho de
página: tamanho da tabela de páginas
vs. fragmentação interna Espaço da tabela
de páginas
s" e p
custo adicional =
+
p 2
Fragmentação
interna
•  Onde
–  s = tamano médio do processo em bytes
–  p = tamanho da página em bytes
!–  e = tamanho da entrada da tabela de página
O resultado é:
p = 2" s" e
85 !
Questões de Implementação
Quatro momentos em que SO trata de paginação:
1.  Criação do processo
- 
- 
Determinar tamanho do processo
Criação ta TP
Quando processo ganha CPU
2. 
- 
- 
Re-setar MMU para novo processso
Limpar TLB
Interrupção de falta de página
3. 
- 
- 
- 
- 
Identificar qual é o endereço lógico causador da falta
Escolhe página a ser substituida
Carrega página requisitada para memória
Completa a instrução de máquina
Quando processo termina
4. 
- 
Desaloca TP e páginas na memória e na área de swaping
89
33
4/16/15
Bloqueando páginas na memória
Em políticas globais de substituição de páginas, pode haver
uma interferência entre paginação e requisições de E/S,
que requerem a retenção (bloqueio) temporária de
páginas na memória.
Exemplo:
1.  Processo1 faz requisição de leitura de dados de um dispositivo
para um buffer em uma página na memória
2.  Enquanto espera, outro processo 2 causa uma falta de página
3.  Por azar, a página do buffer de propcesso1 foi escolhida para
substituição
4.  Dispositivo não conseguiria copiar dados para o buffer
5.  Logo, há necessidade de manter as páginas que são fonte/destino
de dados de E/S
92
Separação de Política e Mecanismo
•  Paginador em espaço do usuário trata os pedidos de falta
de página e implementa o algoritmo de substituição.
•  O núcleo trata do carregamento de MMU
94
34
4/16/15
Segmentação
Paginação resolveu o problema da fragmentação externa, mas o
espaço de endereçamento (lógico) de um processo é linear.
Segmentação permite visualizar um espaço de endereçamento como
uma coleção de espaços de endereçamento (segmentos)
independentes e de tamanho variável
Segmentos são gerados na compilacão e/ou estão na forma de
bibliotecas
Exemplos:
programa principal, pilha de execução, tabela de símbolos, código
de funções, variáveis não inicializadas, bibliotecas
compartilhadas, vetores & matrizes, blocos de variáveis globais
(common block - Fortran), etc.
95
Segmentação: Exemplo Compilação
•  Espaço Virtual com vários segmentos que podem
crescer (e acabar usando a memória livre reservada)‫‏‬
96
35
4/16/15
Segmentação
Ideia central: Permitir que cada segmento creça independentemente.
è cada segmento constitui um espaço de endereçamento independente.
97
Segmentação
•  Segmento = entidade (parte) lógica do programa que contém um único tipo
de dados e do qual o programador está consciente. Exemplos: código, pilha,
heap, tabelas temporárias, bibliotecas, etc.
Vantagens da segmentação:
•  facilita definir e controlar modos de acesso diferenciados para cada parte do
programa
•  segmentos podem crescer independentemente (tabelas dinâmicas, pilhas de
threads)‫‏‬
•  facilita o compartilhamento de partes do programa (p.ex. shared libraries)‫‏‬
•  Facilita a ligação de código. Por ex.: se em cada segmento existe apenas 1
procedimento (end. 0 do segmento n), pode-se modifica-lo sem que seja
necessário alterar qq referência a este procedimento (isto não acontece
quando vários procedimentos estão em uma mem. virtual contígua)‫‏‬
Segmentação cria um espaço virtual multi-dimensional.
98
36
4/16/15
Segmentação
Processos podem também alocar um novo segmento usando
int shmget(key_t key, size_t size, int shmflg)
que retorna o shmId
E se conectar a ele (para compartilhamento) usando:
void *shmat(int shmid, const void *shmaddr, int shmflg);
99
Segmentação
Alguns sistemas permitem que o programador possa indicar quais
partes do programa devem ser segmentos independentes.
Endereço lógico consiste de:
• nºde segmento (s) e deslocamento no segmento (d)
• cada processo tem uma Tabela de Segmentos (TS), que é
fornecida à MMU para tradução de endereços.
• cada entrada na tabela consiste de par (base, limite), com
endereço base e um limite
• como visto anteriormente:
se (d <= limite[s]) então end-fisico = base[s] + d
senão "acesso não autorizado" (TRAP)‫‏‬
10
0
37
4/16/15
Segmentação
Segment Table of process Pi
Tabela de Segmentos (TS)‫‏‬
mem—ria
CPU
trap
s
d
<
yes
+
base
end. f’sico
translation HW
base +
limit
Segment Table (ST)
limit
base
• idealmente, TS deve ser armazenada em registradores rápidos ou em vetores
associativos que permitam consulta paralela (tipo TLB)‫‏‬
• quando TS é mantida em memória, cada processo tem um ponteiro indicando o
início da tabela (base register - STBR) e um contador do número máximo de
entradas na tabela (length register- STLR).
• antes de cada acesso é verificado se s <= STLR, e só então são consultados
limit[STBR+ s] e base[STBR+ s]
10
2
38
4/16/15
Implementação de Segmentação
Segmentos podem ser carregados em qualquer espaço livre da memória, logo:
•  precisa-se controlar a lista de lacunas disponíveis
•  pode causar fragmentação externa (sequencia a-d)‫‏‬
Pode-se fazer compactação de memoria para agrupar segmentos e criar uma lacuna
maior.
10
3
Segmentação (3)‫‏‬
Comparação entre paginação e segmentação
104 39
4/16/15
Segmentação com Paginação
•  Principal vantagem: Permite segmentos muito grandes
•  Cada segmento é um espaço de endereçamento completo, que é paginado da
mesma forma como um espaço de endereçamento uni-dimensional
•  Somente as partes de cada segmento que estão em uso, precisam estar na
memória física
•  Cada processo tem sua TabSegmentos, composta de Descritores
•  Cada Descritor contém:
–  Ponteiro para endereço da TabPaginas
–  Tamanho do Segmento em páginas
–  Bits de proteção
•  Quando um segmento está sendo usado (acessado), sua tabela de páginas
precisa estar em memória
•  Se o segmento puder ser muito grande (232 endereços), então a propria tab. de
páginas deverá ser paginada
•  Endereço Virtual:
s
p
o
s= indice na tab de segmentos
p= indice na tab de paginas
o= offset na página
10
5
Segmentação com Paginação
40
4/16/15
Segmentação com Paginação
•  Somente as partes de cada segmento que estão em uso, precisam estar na
memória física
S1.p5
p4
S1.p3
p3
S2.p5
p2
S3.p3
p1
S1.p2
Seg 1
Seg 2
Seg 3
RAM
10
7
Segmentação com paginação
no MULTICS
Conversão de um endereço que consiste de 2 partes para um endereço
físico de memória.
Para agilizar o acesso, MULTICS usa um TLB de 16 palavras, em que um
par (s,p) pode ser consultado em paralelo.
11
1
41