05-Gerencia_de_Memoria

Prévia do material em texto

1 SO I Cap. 4 1 SO I Cap. 4 
Cap. 4. Gerência de Memória 
 
Lei de Parkinson: Os programas crescem até ocupar toda a 
memória disponível. 
 
Gerente de Memória: 
 Módulo do sistema operacional que gerencia a memória 
principal e a área de memória secundária associada à memória 
principal; 
 Controla as áreas de memória em uso; 
 Controla as áreas de memória disponíveis; 
 Cede memória aos processos quando eles necessitam; 
 Retorna áreas dos processos para a memória disponível quando 
elas não são mais necessárias; 
 Realiza swapping. 
4.1 Gerência de Memória Básica 
 
 Sistema em que não se transfere áreas de memória dos processos 
de/para o disco; 
 A necessidade de swapping existe porque a memória principal 
não é suficiente para manter todos os programas necessários; 
 Fazer swapping depende da quantidade de memória disponível e 
do seu preço; 
 Se a quantidade/preço da memória se altera, as justificativas 
para um método ou outro podem se tornar obsoletas. 
 
 
4.1.1 Monoprogramação sem Swapping ou Paging 
 
 Um processo apenas por vez; 
 Este processo usa toda a memória disponível; 
 O processo deve incluir os device drivers para todos os 
dispositivos que utilizar; 
 Método em desuso. 
 
Formas de organização: 
 
 
 
 (a) é a forma geral desse tipo de organização; 
 (b) foi usado nos primeiros computadores pessoais, que vinham 
com um compilador Basic em ROM; 
 (c) é um IBM PC com DOS. A ROM é chamada de BIOS (Basic 
Input Output System). 
 
 
2 SO I Cap. 4 2 SO I Cap. 4 
4.1.2 Multiprogramação e uso de memória 
 
Razões para se usar multiprogramação: 
 Facilita a programação de aplicações, ao dividi-las em 2 ou mais 
processos; 
 Atende mais usuários ao mesmo tempo; 
 Utiliza melhor os recursos do sistema. 
 
Modelagem de multiprogramação 
 
 
 
 A multiprogramação melhora a utilização de CPU; 
 Em geral, um programa passa a maior parte do tempo esperando 
pelo término de operações de I/O; 
 P. ex.: se um processo usa apenas 20% de seu quantum, com 
monoprogramação 80% da CPU seria desperdiçado; 
 Então, com 5 processos a CPU ficaria ocupada 100% do tempo? 
 Não! Só se a espera por I/O de todos os processos não for 
simultânea! 
 Melhor modelo: ponto de vista probabilístico: 
 Um processo passa uma fração p de um período esperando 
por I/O; 
 Ocupação de CPU = 1 - p; 
 Com n processos, a probabilidade de todos estarem 
esperando I/O simultaneamente é de p
n
 (CPU idle); 
 Utilização de CPU = 1 - pn . 
 
Exemplo: 
 OS = 200 KB; 
 Processo = 200 KB; 
 Espera por I/O = 80%. 
 
a) Computador de 1 MB: OS + 4 processos 
 
 CPU idle = 0,8
4
 = 0,4 (40%) 
 Utilização = 1 – 0,4 = 0,6 (60%) 
 
b) 2 MB: OS + 9 processos 
 
 CPU idle = 0,8
9
 = 0,13 
 Utilização = 1 – 0,13 = 0,87 (87%) (+ 45%) 
 
c) 3 MB: OS + 14 processos 
 
 CPU idle = 0,8
14
 = 0,04 
 Utilização = 1 – 0,04 = 0,96 (96%) (+ 10%) 
3 SO I Cap. 4 3 SO I Cap. 4 
Este modelo permite verificar que o acréscimo de 1 MB é um bom 
negócio, mas 2 MB já não é tão interessante assim. 
 
Análise de Desempenho de Sistemas com Multiprogramação 
 
Considere um CPD onde o job médio fica 80% do tempo esperando 
por I/O. Num dia qualquer, são submetidos 4 jobs com as seguintes 
características (a): 
 
 
 
 
Em (b), verifica-se a utilização de CPU com 1 a 4 jobs com 80% de 
espera por I/O. Considera-se escalonamento Round Robin: 
 
a) 1
o
 job chega 10:00, precisa de 4 min. de CPU para terminar: 
 ele usa 12 seg. para cada minuto que fica processando; 
 sozinho, precisa de 20 minutos de execução. 
 
b) 10:10 chega o job 2 – precisa de 3 min. de CPU: 
 o job 1 já tem 2 minutos de CPU (metade!); 
 utilização = 1 – 0,82 = 0,36; 
 cada job recebe 18%; 
 a entrada do 2o job custa 10% do desempenho do 1o. 
 
c) 10:15 chega o 3
o
 job – precisa de 2 min. de CPU: 
 job 1 tem 2,9 minutos; 
 job 2 tem 0,9 minutos; 
 utilização = 0,49; 
 cada job recebe 16%; 
 a entrada do 3o job custa 11% do desempenho dos 2 primeiros. 
 
d) 10:20 chega o 4
o
 job – precisa de 2 min. de CPU: 
 job 1 tem 3,7 minutos; 
 job 2 tem 1,7 minutos; 
 job 3 tem 0,8 minutos; 
 utilização = 0,59; 
 cada job recebe 15%; 
 a entrada do 4o job custa 6% do desempenho de todos os outros. 
 
e) 10:22 termina o job 1: 
 utilização volta a 49% (16% por job); 
 job 2 tem 2 minutos; 
 job 3 tem 1,1 minutos; 
4 SO I Cap. 4 4 SO I Cap. 4 
 job 4 tem 0,3 minutos. 
 
f) 10:27.6 termina o job 3: 
 utilização volta a 36% (18% por job); 
 job 2 tem 2,9 minutos; 
 job 4 tem 1,2 minutos. 
 
g) 10:28.2 termina o job 2: 
 utilização volta a 20%; 
 job 4 tem 1,3 minutos. 
 
h) 10:31.7 termina o job 4. 
 
4.1.3 Multiprogramação com partições fixas 
 
Da análise do modelo de multiprogramação, conclui-se que ter mais 
de um processo em memória executando simultaneamente é muito 
útil. A questão é como organizar a memória: 
 A primeira solução é dividir a memória em n áreas fixas e em 
cada uma colocar um processo; 
 Essas áreas são chamadas de partições; 
 O tamanho das partições não precisa nem deve ser igual; 
 O espaço não usado de uma partição é perdido; 
 Quando chega um job, ele é colocado numa fila para a menor 
partição que possa recebê-lo. 
 
 A maioria dos jobs são pequenos; 
 Desvantagem de múltiplas filas: as filas para partições grandes 
podem ficar vazias enquanto as das pequenas ficam cheias, com 
jobs que não podem começar por falta de partições adequadas; 
 
 
 Uma alternativa é ter uma fila única para todas as partições; 
 Neste caso, toda vez que uma partição fica livre o sistema 
procura na fila o maior job que cabe nessa partição; 
 Este método dá preferência para os jobs maiores; 
 Jobs pequenos em geral são aplicações interativas que precisam 
dos melhores serviços; 
 Estratégia: deixar uma partição pequena livre para os casos em 
que só há partições grandes sobrando. 
 
 Outra opção: toda vez que um job do início da fila for preterido 
por outro maior, ele recebe um ponto. Quando atingir k pontos, 
ele não pode mais ser preterido. 
 
5 SO I Cap. 4 5 SO I Cap. 4 
Relocação e Proteção 
 
Ver figuras das filas para as partições. 
 Diferentes jobs são carregados em diferentes endereços; 
 De uma execução para outra, o job pode mudar de partição; 
 Na linkedição de um programa, o linker precisa saber em que 
endereço o job será carregado; 
 
Ex.: a 1
a
 instrução de um programa é uma chamada de procedimento 
no endereço 100. 
 Se o job é carregado na partição 1 (começa em 100 KB), o 
endereço 100 fica dentro do SO (fora da partição do job!); 
 Este endereço deve ser 100 Kb + 100; 
 Se o job é carregado na partição 2, o endereço 100 deve ser na 
verdade 200 Kb + 100; 
 Este sistema é chamado de problema de Relocação; 
 Uma solução: alterar todas as instruções somando o endereço 
base! 
 Problema: é preciso identificar quais instruções têm endereços - 
algumas têm opcodes, constantes, etc. 
 O linker precisa colocar no código uma tabela dizendo quais 
instruções precisam ser alteradas. 
 
Isto não resolve o problema! 
 Programas podem construir instruções e dar jumps para elas 
usando ponteiros; 
 Assim, podem acessar endereços fora de suas partições! 
 Isso não é aceitável em ambientes de multiprogramação e, 
principalmente, multiusuários! 
 
Solução do IBM/360: 
 Memória dividida em blocos de 2KB (além das partições); 
 Cada bloco recebe um código de proteção de 4 bits; 
 Cada processo possui uma palavra de status (PSW) que possui 
várias informações; 
 Entre elas uma chave de 4 bits! 
 Toda vez que um programa tenta acessar um bloco cujo código 
de proteção é diferente da chave na PSW, ocorre um trap e o SO 
descontinua o programa; 
 Só o SO pode alterar os códigos de proteção e as chaves nas 
PSWs. 
 Limite: 16 processos! 
 
Outra solução: Registradores Base e Limite: 
 Quandoum processo é escalonado, o registrador base é 
carregado com o endereço base da partição e o limite com o 
endereço final; 
 Todo acesso à memória tem o endereço somado ao endereço 
base; 
 O resultado deve ser menor do que o endereço limite; 
 No PC: registrador base = registrador de segmento; 
 Não possui registrador limite! 
 Outra vantagem: o programa pode ser relocado depois de 
iniciada sua execução! 
 
6 SO I Cap. 4 6 SO I Cap. 4 
 
4.2 Swapping 
 
Sistemas batch: 
 Partições fixas: simples e funciona! 
 Com jobs suficientes para manter a CPU ocupada em um nível 
interessante, não há necessidade de esquemas mais complicados; 
 Inclusive, como visto antes, depois de certo nível não é mais 
interessante ter mais partições para outros programas porque o 
resultado não melhora de forma perceptível. 
 
Sistemas timesharing: 
 Situação completamente diferente; 
 Normalmente há mais usuários que memória para manter os 
programas necessários! 
 Processos interativos em geral ficam a maior parte do tempo 
parados à espera de requisições dos usuários; 
 Os processos excedentes devem ficar em disco; 
 Para executar (atender uma requisição), o processo precisa estar 
em memória; 
 É preciso fazer movimentação memória  disco; 
 Esta movimentação é chamada de Swapping. 
 
4.2.1 Multiprogramação com Partições Variáveis 
 
Swapping pode ser feito em partições fixas: 
 Um processo bloqueado pode ser movido para disco e sua 
partição pode ser ocupada por outro processo; 
 Não é atrativo porque o desperdício pode ser grande. 
 
Partições variáveis: 
 Usado em sistemas bastante dinâmicos (número e tamanho dos 
processos em memória varia); 
 
 Este método melhora a utilização de memória, mas complica a 
alocação e dealocação de áreas e também o gerenciamento das 
áreas em uso; 
 
 É possível agrupar as áreas disponíveis movendo todos os 
processos para baixo (compactação de memória); 
 Gasta muita CPU copiar áreas de memória; 
 Pode ser feito via hardware. 
 
7 SO I Cap. 4 7 SO I Cap. 4 
 
 
Quanta memória um processo precisa? 
 Se todos os processos tiverem tamanho fixo, não há problemas; 
 Basta dar a memória que eles precisam e pronto. 
 
Muitas linguagens utilizam heaps de onde os processos retiram áreas 
de que precisam dinamicamente e acrescentam-nas em seus 
segmentos de dados. 
 
O que acontece se o processo tenta crescer? 
 Se há espaço na frente, ele pode simplesmente ocupar essa área; 
 Se houver um processo na frente, há 2 opções: 
 Ele pode ser movido para um buraco grande o suficiente para 
conter o novo tamanho do processo; 
 Um ou mais processos podem ser movidos para disco para 
liberar espaço. 
 Se o processo não pode crescer e a área de swap em disco está 
cheia, o processo fica bloqueado ou é exterminado. 
 
Obs.: se o crescimento dos processo é esperado, eles podem ser 
iniciados com uma margem. 
No swap, só a memória em uso é movida. 
 
 
 
Há esquemas de mais de um segmento por processo: 
 No esquema 2, o segmento de dados é usado como heap e 
contém o stack que cresce em sentido contrário; 
 Caso stack e dados se encontrem, é preciso passar o programa 
para uma área maior; 
 Se não houver, o processo fica bloqueado ou é exterminado. 
 
Obs.: há SOs que não permitem que se altere a área de código. 
8 SO I Cap. 4 8 SO I Cap. 4 
 
Modelos de memória do Pascal e C no PC: 
 Tiny: dados, código e stack contidos em 64 KB - ponteiro near 
(16 bits - até 64 KB - composição com o registrador de 
segmento) (programa .COM); 
 Small: dados e código em segmentos separados de 64 Kb cada 
um - ponteiro near; 
 Medium: 64 KB para dados e stack - até 1 MB para código - 
ponteiro far (32 bits - até 1 MB); 
 Large: dados e código em segmentos separados de até 1 MB 
cada um - ponteiro far. Dados estáticos (globais, constantes, etc.) 
ocupam até 64 KB. 
 Huge: idem large. Dados estáticos podem ser maiores que 64 
KB. 
 
Obs.: a linguagem COBOL possui uma instrução alter que modifica 
instruções goto no código! 
 
Há 2 formas de organizar a memória em uso e disponível: bit maps e 
listas encadeadas. Também é apresentado o sistema buddy para 
conhecimento. 
 
4.2.2 Gerência de memória com Bit Maps 
 
 Memória dividida em unidades de alocação (poucas palavras até 
vários KB); 
 
 
 
Questões que devem ser consideradas: 
 Qual o tamanho da unidade? 
 Se ela é pequena (ex.: 4 bytes), a tabela de alocação é grande; 
 Se a unidade é grande (ex.: 1 MB), a tabela é pequena; 
 Em compensação, o desperdício com processos pequenos (ou 
não múltiplos da unidade) é grande; 
 Quanto maior a unidade, menos operações de alocação são 
necessárias para dar o que os processos querem. 
 
Ex.: 4 bytes – processo 4 MB – 1 milhão de operações 
 500 KB – processo 750 KB – 2 operações – 250 KB 
perdidos! 
 
 
4.2.3 Gerência de memória com listas encadeadas 
 
 Organiza a memória em listas de segmentos; 
 Um segmento é um processo ou é um buraco entre 2 processos; 
9 SO I Cap. 4 9 SO I Cap. 4 
 O controle de processos e buracos pode ser separado ou na 
mesma lista; 
 Em geral, um processo X pode estar entre 2 processos ou entre 2 
buracos; 
 Quando X termina, há 4 possibilidades: 
 
 
 
Considere que um processo solicita uma área de memória. 
Algoritmos de pesquisa para listas encadeadas classificadas por 
endereço: 
 
 First fit: o sistema escolhe a primeira área grande o suficiente 
para atender a requisição; 
 A área é dividida em 2: processo e sobra; 
 Tende a não varrer a memória inteira, demorando para 
encontrar defeitos; 
 Gera espaços grandes. 
 
 Next fit: semelhante ao anterior, mas inicia a pesquisa de onde 
parou na última vez. 
 
 Best fit: procura na lista inteira pela área mais adequada para 
atender a requisição; 
 Mais lento; 
 Testes mostram que desperdiça mais memória – tende a criar 
muitos espaços pequenos. 
 
 Worst fit: procura pelo maior espaço que atende a requisição; 
 Testes mostram que não é bom. 
 
 
 
 
 
 
 
 
 
Melhoria – separar processos e espaços: 
 Só procura nos espaços – evita as áreas ocupadas; 
 É mais demorado quando um processo termina; 
 Classificação dos espaços por tamanho – é melhor para os 
métodos best fit, first fit e next fit; 
 Utilizar os próprios blocos para conter as informações gerenciais 
(e não uma tabela separada) – os blocos precisam conter o 
tamanho do bloco e um ponteiro para o próximo. 
 
 Quick fit: listas separadas por diversos tamanhos. 
 
4 KB 
 
8 KB 
 
12 KB 
 
20 KB 
10 SO I Cap. 4 10 SO I Cap. 4 
Problema: quando um processo termina, é difícil achar os blocos 
vizinhos. 
 Localizar o vizinho para tentar um merge é caro; 
 Sem o merge, a memória fragmenta em grande número de 
espaços pequenos e sem utilidade. 
 
4.2.4 Gerência de memória com o sistema Buddy 
 
Proposta: Knuth, 1973; Knowlton, 1965. 
 
Tira vantagem de que os computadores usam números binários para 
o endereçamento para acelerar o merge de buracos adjacentes 
quando um processo termina ou sofre swap. 
O Gerente de Memória mantém uma lista dos blocos livres para cada 
tamanho múltiplo de 2: 1, 2, 4, 8, 16, ..., 2
k
 bytes. 
Para 1 MB, são precisos 21 listas. 
Quando começa a atividade, o sistema está com toda a memória 
livre. Há apenas 1 entrada na lista de 1 MB; todas as outras listas 
estão vazias. 
 
Inicialmente: 
1 MB 
 
 
Requisita 70 KB p/ A 
A 128 256 KB 512 KB 
 
Requisita 35 KB p/ B: 
A B 64 256 KB 512 KB 
 
Requisita 80 p/ C: 
A B 64 C 128 512 KB 
 
Retorna A: 
128 B 64 C 128 512 KB 
 
Requisita 60 p/ D: 
128 B D C 128 512 KB 
 
Retorna B: 
128 64 D C 128 512 KB 
 
Retorna D: 
256 C 128 512 KB 
 
Retorna C: 
1 MB 
 
 
Vantagens: 
 Quando um bloco de 2k é liberado, só se pesquisa a lista de 2k e 
não todas as listas ou todos os blocos; 
 O sistema Buddy é bastante rápido. 
 
Problemas: 
É ineficiente! 
 Uma área de 35 KB precisa de 64 KB – 29 KB são perdidos; 
 Apresenta fragmentação interna – áreas alocadas para os 
processos e não utilizadas; 
 Apresenta fragmentação externa – buracos entre os processos. 
11 SO I Cap. 4 11 SO I Cap. 4 
 
4.2.5 Alocação do Espaço de Swap 
 
Opções de Swap Space: 
 Nenhum espaço em disco é alocado para um processo em 
memória; 
 Quando ele precisa deixar a memória, uma área de swap 
precisa ser alocada; 
 A cada vez, a área será num lugar diferente. 
 Alocação de área em disco quando o processo é criado; 
 Toda vez que ele sofre swap out, ele vai para a mesma área; 
 Essa área é dealocada quando o processo termina. 
 
Obs.: a área de swap precisa ser múltipla do bloco de disco. 
 
4.2.6 Análise do sistema de Swap 
 
Knuth, 1973: 
 Um segmento pode ser um processo ou um buraco (50%); 
 Entretanto, se 2 buracos forem adjacentes, eles se tornam apenas 
1; 
 Já 2 processos adjacentes não podem ser considerados 1 
processo! 
 Considere um processo médio; 
 Durante sua permanência no sistema, metade das operações no 
segmento acima serão de alocação de processos e a outra metade 
de dealocação de processos; 
 Assim, metade do tempo um processo terá outro como vizinho e 
na outra metade ele terá um buraco; 
 Na média, haverá n/2 buracos para n processos; 
 Regra dos 50%! 
 
 A regra dos 50% é garantida porque 2 buracos vizinhos sofrem 
merge para tornar-se apenas 1; 
 Regra da memória não usada: 
 Considere f como a fração de memória ocupada por buracos; 
 O tamanho médio de n processos é s; 
 Tamanho médio dos buracos: ks, onde k > 0; 
 k indica a proporção do tamanho médio de um buraco em 
relação ao processo médio; 
 Memória total: m; 
 n/2 buracos ocupam m - ns; 
 
(n/2) x ks = m – ns ou m = ns(1 + k/2) 
 
A fração de memória em buracos é o número de buracos (n/2) 
Vezes o tamanho médio dos buracos (ks) dividido pela memória 
total (m): 
 
 nks/2 nks/2 k 
f = ------- = -------------- = ------- 
 m ns(1 + k/2) k + 2 
 
ex.: se os buracos são 1/2 to tamanho dos processos, 20% da 
memória será perdida em buracos. 
Se os buracos são 1/4 dos processos (usando best fit e não first fit), o 
desperdício será de 11%. 
 
12 SO I Cap. 4 12 SO I Cap. 4 
4.3 Memória Virtual 
 
Problema: programas muito grandes para caber na memória 
disponível. 
Solução: dividir o programa em partes, os overlays: 
 A execução começa pelo overlay 0; 
 Quando ele termina, outro é carregado para ser executado; 
 Os overlays são mantidos em disco e sofrem swap in e out 
quando necessário (feito pelo SO); 
 A divisão do programa é feita pelo programador (tarefa difícil, 
demorada e complexa); 
 
Como deixar esta tarefa para o computador? 
 Fotheringham, 1961; 
 Memória virtual! 
 Idéia: o tamanho do programa, dados e stack pode exceder a 
memória real; 
 SO mantém as partes em uso em memória e o resto em disco. 
 
Ex.: programa de 1 MB pode rodar em 256 KB escolhendo-se com 
cuidado 256 KB de seu espaço para residir em memória. 
 
Ex.: 8 programas de 1 MB podem rodar em 2 MB de memória real 
escolhendo-se 256 KB de cada um. 
 
Obs.: memória virtual e multiprogramação combinam muito bem. 
Se um programa precisa fazer swap in de alguma parte sua, ele fica 
bloqueado esperando por I/O. 
 
4.3.1 Paginação 
 
Em qualquer computador, existe um conjunto de endereços que um 
programa pode produzir. 
 
 
 
Ex.: mov A, $1000 - copia conteúdo do endereço 1000 para A. 
 
1000 é um endereço virtual. 
O conjunto de endereços virtuais forma o espaço de endereçamento 
virtual. 
Quando não há endereçamento virtual, o endereço gerado é colocado 
diretamente no bus para acessar uma palavra de memória real. 
13 SO I Cap. 4 13 SO I Cap. 4 
Com memória virtual, o endereço virtual não vai diretamente para o 
bus. Antes disso, ele passa pela Unidade de Gerência de Memória 
(MMU). 
 
Ex.: um computador pode gerar endereços de 16 bits (64 KB). Mas 
sua memória real é de 32 KB. 
 
 
 
É preciso manter uma cópia completa do programa em disco, até os 
64 KB. 
O espaço de endereçamento virtual é dividido em unidades: as 
páginas. A memória física é dividida em frames (quadros). Páginas 
e quadros são do mesmo tamanho: valores usados são da faixa de 
512 bytes a 8 KB. No exemplo são de 4 KB e temos 16 páginas 
virtuais e 8 quadros. 
 
 
14 SO I Cap. 4 14 SO I Cap. 4 
Ex.: instrução MOVE A, &0 
 Endereço virtual 0 é enviado para a MMU; 
 Esse endereço cai na página 0 (0-4 KB); 
 De acordo com o mapeamento, corresponde ao quadro 2 (8-12 
KB); 
 A MMU transforma o end. 0 em 8192 e coloca-o no bus; 
 A memória não sabe sobre a MMU. Foi solicitado o endereço 
8192 e ela atende; 
 Da mesma forma, a CPU pediu o endereço 0 e recebeu. 
 
Como o programa não cabe na memória real, porque ela é menor 
que o espaço de endereçamento, apenas algumas páginas são 
mapeadas em quadros. As demais ficam em disco e um presence bit 
indica se a página está na memória ou não. 
 
Ex.: MOVE A, &32780 
 32780 é o byte 12 da página 8 (inicia em 32768); 
 A MMU descobre que a página não está mapeada (x); 
 Um trap é gerado pela CPU para o SO (page fault); 
 O SO escolhe uma página pouco usada e escreve seu conteúdo 
em disco; 
 Depois a página referenciada é carregada nesse quadro. 
 
Ex.: o SO decide descartar o quadro 1 
 O quadro 1 é marcado como "não mapeado" (evita acessos aos 
endereços 4-8 KB); 
 A página 8 é carregada no endereço físico 4 KB; 
 A cruz na 8a. página virtual é substituída por 1; 
 Quando a instrução interrompida for re-executada, o endereço 
32780 será mapeado no endereço físico 4108. 
Como funciona a MMU? 
 
Ex.: endereço 8196 (0010 000.000.000.100 em binário) 
 O endereço recebido na MMU é dividido em 2 campos: 
 4 bits para o número da página; 
 12 bits de offset. 
 Com 4 bits, pode-se representar 16 páginas; 
 Com 12 bits, pode-se endereçar 4 KB; 
 Os 4 bits = 2 endereçam a 2a. entrada na tabela de páginas 
virtuais; 
 O presence bit desta página é verdadeiro; 
 Essa entrada contém o valor 6 em 3 bits; 
 O valor 6 é composto com os demais 12 bits, resultando no 
endereço final 24580. 
 
4.3.2 Tabelas de Páginas 
 
Principais questões: 
1. A tabela de páginas pode ser extremamente grande: 
 Computadores modernos usam endereços de 32 bits; 
 Com páginas de 4 KB (12 bits), 32 bits podem endereçar 1 
milhão de páginas. 
2. O mapeamento deve ser rápido: 
 O mapeamento deve ser feito em todos os acessos; 
 Uma instrução típica tem um operador e um operando de 
memória; 
 Assim, são feitos 1, 2 ou mais acessos por instrução; 
 Se uma instrução demora 10 nseg. (como em algumas 
estações), a pesquisa na tabela de páginas deve ser feita em 
poucos nseg. para não se tornar um gargalo. 
15 SO I Cap. 4 15 SO I Cap. 4 
Tabelas de Páginas Multiníveis 
 
Objetivo: evitar que tabelas muito grandes residam inteiras na 
memória. 
 
Ex.: endereço virtual de 32 bits: 
 Páginas de 4 KB; 
 Tabela única > 220 = 1 milhão de entradas; 
 Endereço máximo = 4 GB; 
 
Ex.: endereço de 64 bits: 
 Tabela única > 252 = 4 quatrilhão de entradas! 
 Endereço máximo = 16.000 PB 
 
Qual o tamanho de uma entrada? 
 
 
 
 Cache desabilitado: usado em mapeamento de I/O em memória. 
Nesse caso, um registrador de hardware pode ser mapeado em 
memória. Mas o SO não pode usar o valor da memória. É preciso 
testar o registrador em si; 
 Referenciado: bit setado toda vez que uma página é referenciada 
(leitura ou gravação); 
 Modificado: bit setado caso a página seja modificada depois de 
carregada. Este bit fica setado até que a página seja gravada em 
disco (swap); 
 Proteção: dependendo do esquema, pode ser 1 bit (a página é 
RW ou só de leitura). Mais comum é um esquema mais 
complexo, de pelo menos 3 bits (RWX); 
 Presence: indica se a páginaestá com o frame associado 
presente ou não; 
 No. do frame: válido apenas para Presence bits 1. 
 
Supondo um sistema de 32 bits, proteção RWX, páginas de 4KB, 
memória real de 256 MB: 
 O número do frame tem 16 bits; 
 A entrada tem 23 bits; 
 1 milhão de entradas quer dizer uma memória de 2,9 MB para 
guardar apenas a tabela de páginas; 
 É preciso 1 tabela para cada processo! 
 A MMU precisa ter memória para manter a tabela (Caches do 
processador chegam a 512 KB!). 
 A troca de contexto deve considerar todos esses acessos! 
 
Uma tentativa de solução é o uso de tabelas multi-níveis: 
 
 Tabela Mestre (0-1023 - PT1) aponta para 1024 Tabelas 
Secundárias (0-1023 - PT2), que apontam para 1024 páginas 
reais de 4 KB; 
 Se a máquina possui 4 MB, o último nível aponta para 1024 
páginas + offset > endereço real 
 
Ex. um programa em C 
 
Endereço 0x00403004 = 4.206.596 
Esse endereço é o 12292 na área de dados! 
 
Em binário: 
 
Cach Ref Modif Prot Present No. do Frame 
16 SO I Cap. 4 16 SO I Cap. 4 
0000.0000.01 | 00.0000.0011 | 0000.0000.0100 
10 10 12 
 
PT1 = 1, PT2 = 3, OFFSET = 4 
 
 
 
 
 
 
 
 
 
 
 
 PT1 indica que no 1º nível olha-se a 2a. entrada; 
 Esse entrada indica um bloco do 2o. nível; 
 PT2 indica a 4a. entrada do 2o. nível; 
 Essa entrada indica um frame de memória real; 
 OFFSET indica o 5º byte desse frame. 
 
Obs.: apesar de a tabela ter 1 milhão de entradas, uma tabela multi-
nível necessita ter bem pouca quantidade presente: 
 Um bloco de 1024 entrada tem 2,9 KB; 
 Para acessar um endereço qualquer, é preciso: 
 Acessar a entrada principal (1º nível, 2,9 KB); 
 Depois o 2º nível (2,9 KB); 
 Finalmente o frame = 4 KB; 
 Total = 9,9 KB!!! 
 
Ou seja: 
 Na MMU é preciso 5,8 KB de 2,9 MB para um acesso; 
 Na memória, só 4 KB de 4 GB! 
 
 
 
 
Stack 
 
Heap 
 
Dados 
 
Código 
 
12 MB 
4 MB 
 
20 MB! 
 
4 MB 
 
4 MB 
 
17 SO I Cap. 4 17 SO I Cap. 4 
4.3.3 Exemplos de Hardware de Paginação 
 
PDP-11 (um nível) 
 Máquina da DEC da década de 70; 
 Ainda usado para controle de processos industriais; 
 Tem 16 bits de endereço virtual; 
 Página de 8 KB; 
 Até 4 MB de memória real em alguns modelos; 
 Endereços separados para instruções e dados (dobra o espaço de 
endereçamento!); 
 Um programa pode ter até 128 KB! 
 Com 3 bits, um máximo de 8 páginas virtuais! 
 
 
VAX (dois níveis) 
 Sucessor do PDP-11 
 32 bits de endereço virtual; 
 Páginas de 512 bytes (pequeno); 
 Endereços divididos em 3 campos: 
 Espaço: 2 bits; 
 Número de página: 21 bits; 
 Offset: 9 bits. 
 O espaço é dividido em 4 opções: 
 00 - código e dados do usuário (até 1 GB); 
 01 - stack do usuário (de 1 a 2 GB); 
 10 - sistema (fixo para todos os processos) (de 2 a 3 GB); 
 11 - reservado (de 3 a 4 GB). 
 
 
 
SPARC (3 níveis) 
 Máquina RISC; 
 Base das máquinas SUN; 
 MMU: figura 3-18, página 100 da 1a. edição; 
 
 Sistema admite múltiplos contextos (até 4096!); 
 O contexto é um no. fixo para o processo em execução; 
 O contexto indica qual é a entrada do 1º nível da tabela; 
 
68030 (4 níveis) 
 Níveis da tabela de páginas é programável (de 0 a 4); 
 Número de bits em cada nível programável! 
 Se o processo não tem memória suficiente, não é necessário usar 
todos os níveis. 
 
4.3.4 Memória Associativa 
 
As tabelas de páginas são mantidas em memória para melhor 
desempenho. 
 
Ex.: instrução MOV A, B 
 Só referencia registradores; 
 Acesso à memória para carregar a instrução (sem paginação); 
 Com paginação, é preciso algum acesso adicional para a tabela 
de páginas; 
 No Vax, são precisos 2 acessos para resolver o endereço virtual, 
mais a posição desejada – queda de desempenho de 2/3; 
 
 A velocidade de execução é limitada pela taxa de carga de 
instruções e dados; 
18 SO I Cap. 4 18 SO I Cap. 4 
 No 68030, a paginação pode causar perda de 20%! 
 
Solução: a maior parte dos acessos é feita em poucas páginas. 
Pode-se acrescentar um hardware que faz a tradução de endereços 
virtuais sem o uso da tabela de páginas. 
 
Memória associativa: poucas entradas (8-32). 
 
Como funciona? 
 Quando um endereço é apresentado à MMU, 1º o hardware 
verifica se o endereço está na memória associativa; 
 O teste é feito em paralelo para todas as entradas; 
 Se ela estiver presente, verifica-se se a proteção não é violada; 
 Se não, o frame é acessado. 
 
Ent. Válid Pag. Virt. Modificad Proteção Frame 
1 140 1 RW. 31 
1 20 0 R X 38 
1 130 1 RW. 29 
1 129 1 RW. 62 
1 19 0 R X 50 
1 21 0 R X 45 
1 860 1 RW. 14 
1 861 1 RW. 75 
 
O que acontece se o endereço não está na memória associativa? 
 A MMU verifica que o endereço não foi encontrado; 
 É feita uma pesquisa comum na tabela de páginas; 
 Uma das entradas da mem. assoc. é descartada; 
 Os dados da página acessada são copiados para essa entrada. 
Ex.: 
100 ns para acesso na tabela de páginas; 
20 ns para acesso na memória associativa; 
90% de acerto na memória associativa. 
 
Tempo médio = 0,9 x 20 + 0,1 x 100 = 28 ns. 
 
Obs.: a troca de contexto invalida a memória associativa. 
 
Atualmente, o nome técnico para a memória associativa é TLB 
(Translation Lookaside Buffer). 
 
Paginação de nível zero: MIPS R2000 
 
 A idéia da memória associativa é levada a um extremo; 
 Máquina RISC sem tabela de páginas; 
 Endereço virtual de 32 bits (20 de página virtual e 12 de offset); 
 Página de 4 KB; 
 Endereços físicos de 32 bits; 
 Memória associativa de 64 entradas: 
 Página virtual (20 bits); 
 PID (6); 
 6 bits; 
 Frame (20 bits); 
 4 flags de 1 bit; 
 8 bits. 
 
 Essa mem. assoc. funciona como as outras; 
 Quando a página não é encontrada: 
19 SO I Cap. 4 19 SO I Cap. 4 
 É gerado um trap para o SO (da mesma forma quando uma 
página não está presente); 
 O SO verifica em registradores de hardware qual é a página 
virtual necessária; 
 Os dados dela são carregados na mem. assoc.; 
 A instrução é re-executada. 
 
Obs.: baseado em simulações. 
Diminui a área do chip de tratamento para a mem. assoc.! 
Procura dar velocidade ao sistema ao passar para o SO o tratamento 
das falhas de busca na mem. assoc. 
 
4.3.5 Tabelas de páginas invertidas 
 
Idéia baseada na diferença entre o espaço de endereçamento e a 
memória real: 
 O espaço de endereçamento está em torno de 4 GB para 32 bits; 
 A memória real ainda está longe dessa marca (512 MB); 
 
Problema: novas arquiteturas de 64 bits! 
 Com 32 bits e páginas de 4 KB, uma tabela de páginas virtuais 
pode ter 2
20
 entradas (1 milhão); 
 Com 64 bits e páginas de 4 KB, pode-se ter 252 entradas! 
 São 4 quatrilhões!!! 
 
Alguns projetistas (IBM System/38 e HP Spectrum) optaram por 
inverter a relação: 
 Em geral, a tabela de páginas é organizada por endereços virtuais 
e o conteúdo de uma entrada é o endereço dos frames; 
 Numa tabela invertida, a tabela é organizada por frames e o 
conteúdo de uma entrada é o endereço virtual; 
 
 Usado em conjunto com memória associativa; 
 A pesquisa na tabela invertida pode ser feita com hash; 
 Pode ser feita direto em hardware! 
 Se a pesquisa não encontrar a página procurada, o SO precisa 
procurar a página em disco; 
 Pode manter a tabela de páginas em disco! 
 
4.4 Algoritmos de Substituição de Páginas 
 
4.4.1 Algoritmo Ótimo 
 
 Melhor algoritmo, mas impossível de implementar; 
 Em um Page Fault, considerar as páginas que estão em memória; 
 Para cada uma, determinar quantas instruções faltam para que 
seja acessada novamente; 
 Isso significa determinar o fluxo dos programas e quantas 
instruções ainda serão executadas antes que uma página seja 
acessada de novo; 
 Isso pode determinar que uma página será acessada em 10, 100 
ou 1000 instruções; 
 Esse número é usado como um label para cada uma das páginas; Aquela que tiver o maior label é selecionada para ser descartada! 
 Ex.: uma página será acessada em 1.000.000 de instruções. Outra 
em 10.000.000. Descartar a última significa adiar o momento de 
tratar um page fault; 
20 SO I Cap. 4 20 SO I Cap. 4 
 Computadores, como pessoas, tendem a adiar os eventos 
desagradáveis o máximo possível; 
 
 Avaliação: é impossível saber quanto falta para se acessar uma 
página! 
 Parecido com o algoritmo de Menor Job Primeiro. 
 
4.4.2 Algoritmo de Substituição de Páginas Não Recentemente 
Usadas (NRU) 
 
2 bits associados com cada página: 
 R – referenciada (R ou W); 
 M – modificada (W). 
 
Esses bits são setados toda vez que uma página é acessada. 
 Mantidos por hardware; 
 Quando um bit é setado para 1, ele permanece assim até que o 
SO passe-o para Zero em software; 
 Em cada interrupção do relógio, todos os bits R são zerados; 
 Isso é feito para distinguir entre as páginas referenciadas 
recentemente daquelas que não foram; 
 
Num page fault, todas as páginas são divididas em 4 categorias: 
 Classe 0: não referenciada, não modificada; (R = 0, M = 0) 
 Classe 1: não referenciada, modificada; (R = 0, M = 1) 
 Classe 2: referenciada, não modificada; (R = 1, M = 0) 
 Classe 3: referenciada, modificada. (R = 1, M = 1) 
 
Classe 1 ocorre quando uma página classe 3 tem o bit R zerado 
numa interrupção de relógio. 
NRU remove uma página aleatoriamente da classe mais baixa. 
 Preferível remover uma página modificada que uma referenciada 
com freqüência; 
 Vantagens: fácil de implementar, de entender e tem um bom 
desempenho. 
 
4.4.3 FIFO 
 
Comparação: 
 Supermercado com número fixo de prateleiras; 
 Aceita no máximo k produtos; 
 Chega um produto novo (iogurte diet); 
 Descarta um dos antigos (manteiga!!!). 
 
Funcionamento: 
 O SO mantém uma lista ordenada de páginas, sendo que a 1ª é a 
mais velha; 
 Quando chega uma página nova, ela é inserida no fim da fila; 
 Se é preciso descartar uma página, a 1ª é escolhida! 
 
Problemas: 
 Não considera a importância das páginas; 
 Descarta páginas antigas, mas que podem ser necessárias; 
 Mantém as páginas mais novas, mas que talvez não tenham 
importância; 
 Raramente usado em sua forma pura! 
 
 
 
 
21 SO I Cap. 4 21 SO I Cap. 4 
4.4.4 Segunda Chance 
 
 Modificação do FIFO para evitar o descarte de uma página 
pesadamente usada; 
 Antes do descarte, verifica o bit R da página candidata; 
 Se R = 0, então a página é antiga e não utilizada - é substituída; 
 Se R = 1, o bit R é resetado e a página é colocada no final da fila 
(Obs.: a 1
a
. é a mais velha) - seu tempo de chegada é atualizado 
para este momento; 
 O algoritmo continua pesquisando a fila; 
 Se todas as páginas têm R=1 (todas foram referenciadas no 
último período), funciona como o FIFO. 
 
 
 
4.4.5 O Relógio 
 
 FIFO e 2a. Chance precisam manipular filas; 
 O 2a. Chance precisa mudar as páginas de lugar na fila; 
 Como a ordem não se altera (ordem de chegada no sistema), é 
melhor manter as páginas organizadas numa fila circular; 
 Um ponteiro (ptr) aponta para o mais velho; 
 Num page fault, se ptr->R = 0: 
 A página é descartada; 
 A nova entra no lugar; 
 ptr++! 
 
 
 
4.4.6 LRU (Menos Recentemente Usada) 
 
Observação: 
 
 Páginas bastante usadas nas últimas instruções serão bastante 
usadas nas próximas; 
 Páginas não usadas por vários períodos provavelmente 
permanecerão sem utilização. 
 
Estratégia: 
 Num page fault, procurar pela página que não é usada a mais 
tempo. 
 
22 SO I Cap. 4 22 SO I Cap. 4 
Como implementar este algoritmo? 
 1o., manter todas as páginas numa lista encadeada; 
 Esta lista precisa ser ordenada pela hora de acesso: 
 A página usada mais recentemente fica na cabeça da fila; 
 Aquela que não é usada a mais tempo fica no final da fila. 
 O problema é manter a fila ordenada! 
 Quer dizer, é preciso ordenar a fila em cada acesso - a instrução 
atual coloca a página acessada na cabeça da fila: 
 1º a página da instrução torna-se a 1a.; 
 Depois, a página do 1º operando; 
 Por último, a página do 2º e 3º! 
 Esse processo implica em atualizar a fila em cada acesso; 
 A movimentação de páginas é muito cara!!! 
 
Implementação em hardware: 
 Contador atualizado em cada acesso! 
 Num page fault, o hardware procura o menor contador (LRU)! 
 
2
a
. solução: 
 Para uma máquina de n frames, o hardware LRU mantém uma 
matriz de n x n bits - inicialmente todos zerados; 
 Em um acesso a uma página, todos os bits da linha são setados e 
todos os bits da coluna são zerados; 
 Ex.: um sistema com 4 páginas (0-3); 
 Acessos às páginas 0 1 2 3 2 1 0 3 2 3. 
 
A qualquer momento, a linha com o menor valor binário 
corresponde à página LRU! 
 
 
 
4.4.7 Simulando LRU em Software 
 
Problemas do LRU: 
 Precisa de hardware especial; 
 Implementar esse método sem esse hardware é muito difícil. 
 
Solução implementada em hardware: 
 NFU (Não Freqüentemente Usada); 
 Precisa de um contador em software associado com cada página; 
 Em cada interrupção de tempo, o SO pesquisa todas as páginas 
da memória; 
 Para cada página, o bit R (0 ou 1) é adicionado ao contador; 
 Assim, os contadores são uma tentativa de determinar como as 
páginas são usadas no decorrer dos períodos; 
 Num page fault, a página com o menor contador é descartada; 
 
23 SO I Cap. 4 23 SO I Cap. 4 
Problemas: 
 Esse algoritmo não esquece! 
 Não faz diferença entre um R=1 recente e outro antigo! 
 
Ex.: um compilador é dividido em fases: 
 As 1as. fases são usadas pesadamente, mas nas fases seguintes 
essas páginas não são mais necessárias; 
 O SO pode manter páginas que uma vez foram muito usadas mas 
agora não são mais necessárias em prejuízo de outras úteis agora, 
mas que foram menos usadas antes! 
 
Solução: 
 Pequena modificação no NFU: 
 1º, o contador é deslocado 1 bit para a direita; 
 O bit R é adicionado ao bit mais a esquerda (e não somado 
ao bit da direita); 
 Este algoritmo é chamado de aging! 
 
Num page fault, a página com o menor contador é descartada: 
 É fácil verificar que a página acessada no último período tem o 
maior contador; 
 Os acessos antigos servem apenas de desempate para os acessos 
mais recentes (podem indicar que uma página é mais útil que 
outra); 
 Os contadores são limitados em 8 bits, p. ex.; 
 Cada tique do relógio ocorre a cada 20 mseg.; 
 Portanto um contador só pode manter um histórico de 160 
mseg.! 
 Se uma página não foi acessada em 160 msegs., provavelmente 
ela não é importante! 
 
 
24 SO I Cap. 4 24 SO I Cap. 4 
Trabalho sobre Semáforos 
 
Conceito de semáforo: 
 Variável binária mantida pelo SO! 
 
Implementação definida no Unix System V: 
 Conjunto de inteiros não negativos. 
 
Estruturas: 
 sys/types.h 
 sys/ipc.h 
 
int semget(key_t key, int nsems, 
 int semflag; 
 
key - valor que todos os processos concordam. 
Se semflag = IPC_CREAT nsems indica o no. de semáforos no 
conjunto. 
Valor devolvido - semid ou -1 
 
Includes: 
sys/types.h 
sys/ipc.h 
sys/sem.h 
 
Depois de aberto por todos os processos: 
int semop(int semid, 
 struct sembuf * opsptr, 
 unsigned int nops); 
nops - número de operações 
 
struct sembuf { 
 ushort sem_num; /* num. do semaf.: 
 0, 1, 2, ... */ 
 short sem_op; /* operação */ 
 short sem_flag; /* flags */ 
}; 
 
Obs.: conjunto de operações atômico (todas são feitas ou nenhuma). 
 
Valores de sem_op: 
1 - positivo: adicionado ao semáforo (libera um recurso) 
2 - zero: quem chama, espera até que o semáforo seja 0 
3 - negativo: espera que o semáforo  |sem_op| 
 então sem = sem - |sem_op| 
 (aloca um recurso) 
 
Se sem_flg = IPC_NOWAIT, não espera caso a operação não possa 
ser feita. 
 
int semctl(int semid,int semnum, 
 int cmd, 
 union semun arg); 
 
union semun { 
 int val; 
 /* só com SETVAL */ 
 struct semid_ds *buff; 
 /* usado p/ IPC_STAT IPC_SET */ 
25 SO I Cap. 4 25 SO I Cap. 4 
 ushort *array; 
 /* GETALL SETALL */ 
} arg; 
 
cmd: 
IPC_RMID - remove o semáforo do sistema 
GETVAL - verifica o valor do semáforo (retornado) 
SETVAL - seta o semáforo para val 
 
Rotinas de lock e unlock: 
#define SEMKEY 123456L 
#define PERMS 0666 
 
static struct sembuf op_lock[2] = { 
 0,0,0, /* wait sem#0 == 0 */ 
 0,1,0 /* incrementa sem#0 */ 
}; 
 
static struct sembuf op_unlock[1] = { 
 0, -1, IPC_NOWAIT /* decrem. Sem#0 */ 
}; 
 
if (semop(semid &op_lock[0], 2) < 0) 
 
if (semop(semid, &op_unlock[0], 1) < 0)