06-Gerencia_de_memoria

Prévia do material em texto

1 SO I Cap. 4-B 1 SO I Cap. 4-B 
4.5 Modelagem de Algoritmos de Paginação 
 
4.5.1 Anomalia de Belady 
 
Dedução baseada no senso comum: 
 Quanto mais frames tiver a memória real, menos page faults 
devem acontecer! 
 Belady, 1969 - mostrou um trabalho usando FIFO em que 
ocorrem mais page faults com 4 páginas reais que com 3! 
 Essa situação ficou conhecida como Anomalia de Belady. 
 Ex.: 5 páginas virtuais (0-4) e 3 frames. Páginas referenciadas na 
ordem 0 1 2 3 0 1 4 0 1 2 3 4 
 
 0 1 2 3 0 1 4 0 1 2 3 4 
 0 1 2 3 0 1 4 4 4 2 3 3 
 0 1 2 3 0 1 1 1 4 2 2 
 0 1 2 3 0 0 0 1 4 4 
 P P P P P P P P P 
Total: 9 page faults. 
 
A mesma ordem com 4 páginas reais: 
 
 0 1 2 3 0 1 4 0 1 2 3 4 
 0 1 2 3 3 3 4 0 1 2 3 4 
 0 1 2 2 2 3 4 0 1 2 3 
 0 1 1 1 2 3 4 0 1 2 
 0 0 0 1 2 3 4 0 1 
 P P P P P P P P P P 
Total: 10 page faults!!! 
4.5.2 Algoritmo de Pilha 
 
Observação: 
 Todo processo gera uma seqüência de referências de memória à 
medida que executa; 
 Cada referência corresponde a uma página virtual específica; 
 Todos os acessos de um programa formam uma lista ordenada de 
números de página - o String de Referência. 
 
Características de um sistema de paginação: 
 String de referência do processo; 
 Algoritmo de substituição; 
 Número de frames disponível (m). 
 
Análise do ambiente: 
 M - array mantido pelo sistema com a situação da memória; 
 M tem n elementos - número de páginas virtuais; 
 M é dividido em 2 regiões: 
 Superior: com m elementos, contém todas as páginas que 
estão na memória principal; 
 Inferior: com n - m elementos, contém todas as páginas que 
foram referenciadas e sofreram swap out. 
 
Simulando o andamento do programa: 
 M está vazio; 
 O processo começa a requisitar as páginas, na ordem do String 
de Referência; 
 A cada referência, o interpretador verifica se a página está na 
memória (parte superior de M); 
 Se não está, page fault; 
2 SO I Cap. 4-B 2 SO I Cap. 4-B 
 Se houver um slot livre, a página pedida é carregada na parte 
superior de M - ocorre só no início do processamento; 
 Se não, o algoritmo de substituição é acionado para descartar 
uma página e colocar a nova no lugar. 
Ex.: Usando LRU - espaço virtual de 8 páginas, 4 frames 
String de refer.: 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1 
 
 0 2 1 3 5 4 6 3 7 4 7 3 
 0 2 1 3 5 4 6 3 7 4 7 3 
 0 2 1 3 5 4 6 3 7 4 7 
 0 2 1 3 5 4 6 3 3 4 
 0 2 1 3 5 4 6 6 6 
 0 2 1 1 5 5 5 5 
 0 2 2 1 1 1 1 
 0 0 2 2 2 2 
 0 0 0 0 
 P P P P P P P P 
        4  4 2 3 
 
Propriedades desse modelo: 
 Toda vez que uma página passa a fronteira entre memória real e 
disco, a página que desce sofre um swap out; a que sobe sofre 
um swap in; 
 Toda página referenciada passa para o topo de M; 
 As páginas acima da referenciada descem uma posição; 
 Abaixo da referenciada não há alteração. 
 
Esse algoritmo atende a propriedade: 
M(m, r)  M(m + 1, r) 
Isto quer dizer que o algoritmo funciona da mesma forma para m 
frames e para m + 1 frames. 
Quer dizer, repetindo a execução de um programa da mesma forma 
com 1 frame a mais na memória real, todas as páginas que estavam 
presentes com m páginas estarão também com m+1, mais a página 
abaixo. 
 
3 5 5 3 1 1 1 7 2 3 4 1 
3 5 5 3 1 1 1 7 2 3 4 1 
7 3 3 5 3 3 3 1 7 2 3 4 
4 7 7 7 5 5 5 3 1 7 2 3 
6 4 4 4 7 7 7 5 3 1 7 2 
5 6 6 6 4 4 4 4 5 5 1 7 
1 1 1 1 6 6 6 6 4 4 5 5 
2 2 2 2 2 2 2 2 6 6 6 6 
0 0 0 0 0 0 0 0 0 0 0 0 
 P P P P P 
1 5 1 2 6 1 1 4 7 4 6 5 
 
Examinando as tabelas representando o array M, verifica-se que ele 
possui a propriedade do LRU. 
FIFO, por exemplo, não possui essa propriedade. 
Os algoritmos que apresentam a propriedade do LRU são chamados 
de algoritmos de pilha. 
 
Algoritmos de pilha não sofrem da anomalia de Belady! 
 
3 SO I Cap. 4-B 3 SO I Cap. 4-B 
4.5.3 O String de Distância 
 
 Representação mais conveniente do string de referência; 
 Quando uma página é referenciada, verifica-se qual é a distância 
dessa página para o topo da pilha; 
 Se ela ainda não foi referenciada (não está na pilha), diz-se que a 
distância é . 
 
O string de distância depende do string de referência e do algoritmo 
de paginação. 
 
4.5.4 Prevendo as taxas de page faults 
 
Propriedade do string de distância: prever o número de page faults 
dependendo do tamanho da memória real! 
 
Algoritmo: 
 Primeiro, verificar o número de vezes que cada número aparece 
no string de distância (p. ex.: quantos 1s, quantos 2s, etc.); 
 Organizar essas contagens no vetor C, onde Ci é o número de 
vezes que i ocorre no string de distância; 
 No exemplo dado, em 4 vezes a página referenciada estava no 
topo da pilha; 3 vezes a página estava na 2
a
. posição da pilha, 
etc. 
 Com o vetor C, pode-se computar o vetor F de acordo com a 
fórmula: 
 n 
 Fm =  Ck + C 
 K=m+1 
Essa fórmula indica o número de page faults que ocorrem dado um 
string de distância com m frames. 
 
C1=4 F1=20 
C2=2 F2=18 
C3=1 F3=17 
C4=4 F4=13 
C5=2 F5=11 
C6=2 F6=9 
C7=1 F7=8 
C=8 F8=8 
 
4.6 Questões de Projeto para Sistemas de Paginação 
 
Modelo Conjunto de Trabalho 
 
 Todos os processos ao iniciar não tem suas páginas carregadas; 
 Na primeira tentativa de carregar uma instrução, o processo 
recebe um page fault; 
 O SO carrega essa página. 
 Em seguida, ocorrem outros page faults para variáveis globais e 
pilha; 
 Em pouco tempo, o processo terá todas as páginas de que 
precisa com poucos page faults; 
 Paginação por demanda! 
 
Localidade de referência: a maioria dos processos referencia 
apenas uma parte pequena de suas páginas. 
 
4 SO I Cap. 4-B 4 SO I Cap. 4-B 
Conjunto de trabalho: grupo de páginas usadas num determinado 
instante. 
 
Situações: 
 Conjunto de trabalho reside inteiro na memória - poucos page 
faults, basicamente por mudança de fase; 
 Memória disponível pequena - muitos page faults; 
 
 Uma instrução é executada em frações de microssegundos; 
 Um swap in leva dezenas de milissegundos. 
 
Thrashing: execução que gera um page fault a cada poucas 
instruções. 
 
Numa situação de thrashing, ocorre de um processo sofrer swap out 
inteiro. O que fazer quando ele volta para a memória? 
 Tecnicamente nada! 
 Basta esperar que ele comece a pedir as páginas a cada page 
fault; 
 Problema: ele pode gerar dezenas de page faults depois de um 
swap in; 
 Assim, o processo de carga é lento e isso consome tempo de 
CPU; 
 
Há SOs que preferem carregar primeiro o conjunto de trabalho antes 
de deixar um processo executar - Modelo Conjunto de Trabalho. 
 
Objetivo: reduzir o número de page faults. 
 
Pré-paginação: carregar as páginas antes da execução do processo. 
Implementando o modelo conjunto de trabalho: 
 É preciso determinar quais páginas fazem parte do conjunto de 
trabalho; 
 Uma forma é através do algoritmo de Aging, considerando as 
páginas que têm pelo menos 1 dos n bits mais altos setados no 
contador (últimos n tiques). 
 
Melhoria no algoritmo do relógio (wsclock): 
 No algoritmo normal, quando o ponteiro aponta para uma página 
com o bit R=0, ela é descartada; 
 No wsclock, primeiro se verifica se a página pertence ao 
conjunto de trabalho. 
 
4.6.1 Políticas de Alocação Locais x Globais 
 
Dúvida: num page fault, deve-se considerar apenas as páginas do 
processo ou de todos? 
 
Local: cada processo recebe uma quantidade fixa de memória. 
Global: a quantidade de memória dos processos varia com o tempo. 
 
Em geral, políticas globais são melhores que as locais: 
 Numa política local, se o conjunto de trabalho de um processo 
aumenta, ocorre trashing (mesmo que haja páginas livres); 
 Se o conjunto diminui, ocorre desperdício (outros processos não 
podem usar as páginas que sobram); 
 Com políticas globais, o SO pode decidir a cada instante quantaspáginas um processo deve ter através dos bits de Aging (apesar 
de não prevenir trashing). 
 
5 SO I Cap. 4-B 5 SO I Cap. 4-B 
 
 
Problemas: 
 O conjunto de trabalho pode variar em instruções; 
 Bits de aging refletem apenas tiques. 
 
Outra abordagem: 
 Algoritmo de distribuição de páginas. 
 
1. Divisão entre os processos: 
 O número de frames é dividido igualmente entre os processos. 
 Ex.: 475 frames e 10 processos - cada um recebe 47 frames - as 5 
restantes passam para um pool para serem usadas em page faults. 
 
2. Proporcional: 
 Depende do tamanho dos processos; 
 Ex.: o processo A tem 300K e B tem 10K - A recebe 30x os 
frames de B. 
 
Exagero: 
 Uma instrução do tipo: INST OP1 OP2 
 INST, OP1 e OP2 têm 2 bytes cada; 
 Cada um está na fronteira entre 2 páginas! 
 Resultado: essa instrução precisa de 6 páginas! 
 Se o conjunto de trabalho desse programa é de 5 páginas, ele não 
pode executar!!! 
 
Nenhum desses métodos resolve o thrashing! 
 
4.6.2 Controle de Carga 
 
Forma de controle direto: 
 Usar a Freqüência de Page Fault (Algoritmo PFF). 
 Observação: na maioria dos algoritmos de substituição de 
páginas, a taxa de page faults diminui se o número de frames 
aumenta. 
 
 
 
 
 
 
 
 
 
 
1 
Número de frames de um processo 
1 - Page Faults/segundo 
B 
A 
6 SO I Cap. 4-B 6 SO I Cap. 4-B 
No gráfico, a linha marcada com A representa uma taxa de page 
faults inaceitável. 
Por outro lado, a linha B representa uma taxa baixa indicando que o 
processo tem muita memória (pode-se tirar alguns frames dele). 
 O sistema tenta manter todos os processos abaixo da linha A; 
 Se não é possível, remove alguns da memória! 
 Conclusão: mesmo com paginação, é preciso swapping. Não 
tanto para usar os frames do processo liberado, mas para 
diminuir a demanda por memória dos processos ativos. 
 
4.6.3 Tamanho de Página 
 
Na média, um segmento de um programa não preenche um número 
exato de páginas. 
 Metade da última página é desperdiçada. 
 Fragmentação interna. 
 
Considere n segmentos na memória e uma página de tamanho p. 
Desperdício = np/2 ! Argumento para se usar páginas pequenas. 
 
Ex.: um programa é dividido em 8 fases de 4KB cada uma. 
Tamanho de Página Ocupação Espaço Útil 
32 KB 32 KB 4 KB 
16 KB 16 KB 4 KB 
4 KB ou menos 4 KB 4 KB 
 
Tamanho de Página: 
 Maior: 
 Mantém áreas de programas sem necessidade; 
 Em compensação, um programa precisa de menos páginas. 
 Menor: 
 A tabela de páginas é maior; 
 Um processo precisa de muitas páginas. 
 
Em geral, as transferências de/para disco são feitas 1 página por vez: 
 O maior custo de uma operação de disco é o tempo de seek e 
rotação; 
 Assim, transferir uma página grande leva quase o mesmo tempo 
de uma pequena. 
 
Considere os seguintes elementos: 
 S = tamanho médio de um processo; 
 p = tamanho da página em bytes; 
 e = tamanho da entrada na tabela de páginas; 
 S/p = número de páginas por processo; 
 Se/p = tamanho da tabela de páginas 
 p/2 = fragmentação interna por processo; 
Overhead total = Se/p + p/2 
 Se/p cresce quando a página diminui; 
 p/2 cresce quando a página aumenta. 
 
Derivando em relação a p e igualando a zero: 
-Se/p
2
 + 1/2 = 0 
 
Fórmula para o tamanho ótimo de página: 
 p = (2Se)
1/2
 
 
Ex.: S = 128 KB, e = 8 bytes  p = 1448 (1 ou 2 KB) 
 
Computadores comerciais  p = 512 até 64 KB. 
7 SO I Cap. 4-B 7 SO I Cap. 4-B 
4.6.4 Espaços de dados e instruções separados 
 
A maioria dos computadores têm um espaço único de 
endereçamento para cada processo. 
Se esse espaço é grande o suficiente, tudo bem. 
Porém, em geral ele é pequeno, forçando os programadores a 
quebrar a cabeça para fazer caber tudo que é necessário. 
 
 
 
Uma solução, originada no PDP-11 de 16 bits, é ter espaços de 
endereçamento diferentes para instruções (I-space) e dados 
(D-space). 
 
Num computador deste tipo, os dois espaços podem ser paginados 
independentemente. Cada um possui sua própria tabela de páginas. 
O hardware sabe qual espaço usar dependendo do momento. 
 
4.6.5 Páginas compartilhadas 
 
Em grandes sistemas interativos, é comum diversos usuários 
executarem os mesmos programas (ex. Email, navegadores, editores, 
etc.). 
Esses programas possuem páginas que são duplicadas por todos os 
usuários (ex. Código). 
Se essas páginas não forem alteradas, elas poderiam ser 
compartilhadas entre todos, diminuindo o espaço ocupado. 
 
 
 
Claro, há cuidados extras a se tomar nesse caso: 
 Se 2 processos compartilham uma mesma página, caso o 
escalonador resolva fazer swap em um deles, essa página vai 
junto; 
 Se um dos processos termina, a página não pode ser liberada, 
nem o espaço em disco que ela ocupa. 
8 SO I Cap. 4-B 8 SO I Cap. 4-B 
Fazer uma pesquisa desses casos quando a situação ocorre não é 
aceitável, portanto é preciso um controle especial por meio de 
estruturas adequadas. 
 
Compartilhar dados é mais complicado do que código, mas é 
possível e é feito. 
 
Comando Fork do Unix: 
 Na execução do comando, um novo processo é criado; 
 Pai e filho compartilham então todas as páginas (dados e 
código); 
 Cada um passa a ter sua própria tabela de páginas, que aponta 
para as mesmas páginas – não é feito nenhuma cópia de página 
durante o fork; 
 Todas as páginas dos processos são marcadas como READ 
ONLY; 
 Enquanto os processos não modificarem algum dado, a situação 
permanece; 
 Quando uma palavra de memória for alterada, naquela página o 
compartilhamento é desfeito; 
 Ocorre um trap porque as páginas são todas de leitura; 
 A página é copiada para o novo processo (copy on write); 
 As duas cópias da página são marcadas como READ-WRITE; 
 Esse sistema permite manter compartilhadas as páginas não 
alteradas, tanto de código como de dados. 
 
4.6.6 Política de limpeza 
 
O sistema de paginação funciona melhor quando há páginas livres 
que podem ser usadas para atender as falhas. Se todas as páginas 
estão cheias e modificadas, antes de liberar uma é preciso salvá-la 
em disco. 
Para garantir um estoque de páginas livres, alguns sistemas 
providenciam um processo em background, o daemon de 
paginação, que fica adormecido a maior parte do tempo, mas é 
acordado de tempos em tempos para verificar a situação da 
memória. 
Se há poucas páginas disponíveis, o daemon seleciona algumas para 
descarte usando o algoritmo de substituição em uso. Se uma 
escolhida tiver sido modificada, será gravada em disco. 
Caso a página liberada seja necessária de novo, e ainda não tenha 
sido sobreposta, ela pode ser retirada do pool de páginas livres e 
devolvida ao processo. 
Em último caso, o daemon pode iniciar a gravação de páginas 
alteradas. Assim, não é preciso fazer isso no momento em que 
ocorre uma falha. 
4.7 Questões de implementação 
 
4.7.1 Envolvimento do SO com a paginação 
 
Há 4 momentos em que o SO tem relação com a paginação: 
 Criação de um processo: 
o É preciso determinar quão grande o programa e dados 
serão e criar uma tabela de páginas; 
o É preciso espaço para guardar esta tabela em memória; 
o A tabela não precisa ficar residente se o processo sofrer 
swap, mas deve estar quando ele estiver executando; 
o É preciso espaço em disco para fazer swap; 
9 SO I Cap. 4-B 9 SO I Cap. 4-B 
o A área de swap deve ser inicializada com o código e 
dados do programa – assim, quando ele iniciar as páginas 
já poderão ser trazidas de disco. 
 
 Escalonamento de um processo: 
o A MMU é resetada para o novo processo; 
o A memória associativa (TLB) é apagada; 
o A tabela de páginas do novo processo deve ser 
identificada como a tabela atual; 
o Algumas ou todas as páginas do processo devem ser 
trazidas para a memória para diminuir o número de page 
faults. 
 
 Numa falha de página: 
o Verificar nos registradores qual endereço virtual causou a 
falha; 
o Determinara página correta em disco; 
o Encontrar um frame disponível (descartar uma página + 
antiga se necessário); 
o Carregar a página para o frame; 
o Voltar o contador de instruções para a instrução que 
causou a falha e executá-la novamente. 
 
 No término de um processo: 
o Liberar sua tabela de páginas, suas páginas e o espaço em 
disco para swap; 
o Páginas compartilhadas só podem ser liberadas no 
término do último processo. 
 
 
4.7.2 Tratamento de falhas de páginas 
 
 O hardware causa um trap no kernel. Em algumas máquinas, 
alguns dados sobre o estado da instrução atual é salvo em 
registradores especiais; 
 Uma rotina especial salva registradores e outros dados, evitando 
que o SO destrua-os. O SO é chamado como um procedimento; 
 O SO descobre que uma falha ocorreu, e tenta verificar qual 
página virtual é necessária; 
o Um dos registradores deve ter essa informação; 
o Se não, deve-se verificar o CI, carregar a instrução que 
causou a falha, e fazer o parse em software para verificar 
o que ela fez que deu problema. 
 Descoberto o endereço virtual que causou a falha, o SO verifica 
se o endereço é válido e se a tentativa de acesso é consistente 
com a proteção; 
o Se não, o processo é morto; 
o Se não há problemas, o SO verifica se há alguma página 
livre. Se não houver, o algoritmo de substituição é 
chamado para escolher uma vítima. 
 Se o frame selecionado está ocupado, ele é selecionado para 
transferência para disco; 
o O processo que causou a falha é suspenso até que o I/O 
seja feito; 
o Ocorre uma troca de contexto; 
o O frame é marcado para evitar que seja usado para outra 
finalidade. 
 Assim que o frame for limpo (imediatamente ou após ser 
gravado em disco), o SO verifica o endereço em disco onde a 
página necessária reside e inicia uma operação de carga; 
10 SO I Cap. 4-B 10 SO I Cap. 4-B 
 Uma interrupção de disco indica que a página chegou: a tabela 
de páginas é atualizada e o frame é marcado como normal; 
 O backup da instrução que falhou é retornado – o CI volta a 
apontar para esta instrução; 
 O processo que falhou é escalonado; o SO retorna para o 
procedimento que o chamou; 
 Essa rotina recarrega os registradores e outros dados, retorna 
para o espaço do usuário para continuar a execução. 
 
4.7.3 Backup de Instrução 
 
 Uma referência a uma página que não está na memória causa um 
page fault; 
 A instrução que causou a falha é interrompida e um trap é 
gerado; 
 O SO carrega a página solicitada; 
 O processo é reiniciado naquela instrução. 
 
Ex.: instrução do 68000 MOVE OP1 OP2 
 
Essa instrução possui 3 elementos: operador e 2 operandos. 
Supondo que cada um tenha 16 bits, a situação é a seguinte: 
 
MOVE OP1 (#6) OP2 (#2) 
 
Endereço Conteúdo Significado 
1000 MOVE Operador 
1002 6 OP1 
1004 2 OP2 
 
Passos para a decodificação da instrução: 
1. Contador de Instruções (CI) avança para o Operador (1000); 
2. O operando é carregado no registrador de instruções (RI); 
3. A instrução é decodificada; 
4. CI = CI + 2; 
5. O endereço (CI) é carregado para um registrador (R); 
6. A posição endereçada por R é carregada em A; 
7. CI = CI + 2; 
8. O endereço (CI) é carregado para R; 
9. O valor de A é movido para o endereço de R. 
 
Se a falha ocorre na página da instrução (endereço 1000), nada foi 
feito ainda. 
O problema existe quando a falha ocorre em um dos operandos! 
Ex.: no caso, se a falha ocorre nos passos 6 a 9. 
Nesse caso, o processamento da instrução já causou alterações, mas 
não pode ser completado. 
 
Então, houve uma falha e o SO já trouxe a página necessária. A 
instrução precisa ser reiniciada. A questão: o que precisa ser feito? 
 
1
º
, é preciso saber onde ocorreu a falha. Em geral, os processadores 
não mantém esse tipo de informação. 
Em nosso exemplo, onde é possível ocorrer uma falha? 
 No endereço 1000 - a página da instrução não está residente; 
 No endereço 1002 - a instrução pode estar na fronteira de 2 
páginas; 
 No endereço 6 - a página de OP1; 
 No endereço 1004; 
 No endereço 2 - a página de OP2. 
11 SO I Cap. 4-B 11 SO I Cap. 4-B 
Quando o SO carrega a página, em que ponto estávamos? 
 Pelo conteúdo de RI, é possível saber qual é a instrução; 
 O problema é que a própria instrução talvez não tenha sido 
carregada; 
 Mesmo que tenha sido, em qual dos operando estamos? 
 
O problema pode ser pior! 
 O 68000 possui instruções com autoincremento; 
 São instruções que antes ou depois de executar incrementam o 
valor de um registrador; 
 Nesse caso, o incremento (se ocorreu) tem que ser desfeito! 
 
Resultado: paginação é impossível no 68000!!! 
 
PDP-11/45: 
 Salva o CI, os registradores incrementados e o valor do 
incremento. 
 
68010: 
 Salva informações sobre o estado interno na pilha para permitir o 
reinício. 
 
VAX: 
 O microcódigo faz o rollback do estado do processador, 
permitindo o reinício com facilidade. 
 
Máquinas RISC: 
 Os projetistas do hardware não se preocuparam em resolver, pois 
seria muito custoso; 
 O estado interno do sistema após uma falha é horrível! 
 O SO que se vire para resolver o problema - ou seja, os 
projetistas de sistemas operacionais devem achar a solução. 
 
4.7.4 Bloqueio de páginas em memória 
 
 Considere uma solicitação de I/O para um buffer em uma página 
de um processo; 
 Se houver troca de contexto, existe uma chance dessa página 
sofrer swap (paginação global); 
 Quando o I/O fosse atendido, o DMA seria feito sobre uma 
página incorreta! 
 Solução: 
 Bloqueio da página até que o I/O termine; 
 O I/O pode ser feito no kernel e ele transfere para o processo 
depois. 
 
4.7.5 Área de disco para swap 
 
Como gerenciar a área de page out? 
 Algoritmo mais simples: uma área para todo o sistema; 
 Quando um processo inicia, o sistema reserva uma área de swap 
para ele; 
 Área de swap  memória virtual total; 
 Quando o processo termina, a área de swap é liberada. 
 
A área de swap precisa ser inicializada: 
 Uma forma é copiar toda a imagem para a área de swap; 
 Iniciar o processo inteiro na memória e fazer swap se preciso; 
 Problema: o processo pode ser muito grande! 
 
12 SO I Cap. 4-B 12 SO I Cap. 4-B 
Outro problema: o processo pode crescer! 
 Solução: manter áreas separadas para código, dados e pilha. 
 
Outra solução: 
 Alocar área só quando é necessário; 
 Quando a página volta para a memória, a área de disco é 
liberada; 
 É preciso ter memória para todas as páginas! 
 
 
 
Na figura, vemos as duas situações. 
 
Daemons de Paginação 
 
A paginação funciona melhor se há frames livres. 
 Se a memória está cheia (e muitas delas estão modificadas), para 
trazer uma de disco é preciso gravar uma de memória para poder 
liberá-la. 
Alguns sistemas mantém um daemon, cuja função é manter uma 
taxa de memória livre. 
 O daemon permanece "dormindo" a maior parte do tempo; 
 Ele é acordado para verificar o estado das páginas; 
 Se há poucas páginas livres, ele libera algumas delas (se 
estiverem modificadas, grava em disco antes); 
 Inicia esse procedimento adiantado em relação aos processos. 
 
4.7.6 Separação de política e mecanismo 
 
A separação entre política e mecanismo é uma ferramenta para 
gerenciar a complexidade de um sistema. 
Na gerência de memória, isso pode ser alcançado passando a maior 
parte do gerente para um processo em modo usuário. 
 
 
 
Na figura, o sistema de gerência de memória é dividido em 3 partes: 
 Um manipulador de MMU de baixo nível; 
13 SO I Cap. 4-B 13 SO I Cap. 4-B 
 Um tratador de falhas de páginas que faz parte do kernel; 
 Um gerente externo que roda em modo usuário. 
 
Os detalhes da MMU são encapsulados no tratamento da MMU, 
que é um código dependente de máquina. 
O tratamento de falhas é independende de máquina e contém a 
maior parte do mecanismo de paginação. 
A política é determinada pelo gerente em modo usuário, quese 
encarrega de manipular o espaço em disco. 
 
Esta implementação deixa aberto onde fica o algoritmo de 
substituição. Seria interessante que ele ficasse no gerente externo, 
mas há problemas. 
O gerente em modo usuário não tem acesso aos bits R e M de todas 
as páginas. Assim, ou se cria algum modo de passar esta informação 
para ele, ou o algoritmo deve residir no kernel. 
Nesse caso, o algoritmo diz ao gerente que página ele selecionou 
para descarte e fornece os dados necessários. O gerente externo 
grava os dados em disco. 
 
Vantagens: código modular, mais flexibilidade. 
Desvantagens: overhead extra de cruzar a fronteira entre kernel e 
usuário várias vezes; mensagens trocadas entre os componentes. 
 
4.8 Segmentação 
 
Considere o exemplo de um compilador cuja memória é dividida em 
5 áreas: 
 Texto do fonte: salvo para impressão; 
 Tabela de símbolos: nomes e atributos das variáveis; 
 Constantes: do tipo inteiro e ponto flutuante; 
 Árvore de parse: contém a análise sintática do programa; 
 Pilha: usada para as chamadas de procedimento dentro do 
compilador. 
 
Analisando essas áreas: 
 As 4 primeiras crescem continuamente durante a compilação; 
 A última cresce e diminui dependendo da atividade do programa. 
 
Num espaço unidimensional, como o espaço virtual, as 5 áreas 
precisam ser alocadas de forma contígua. 
 
Prevendo o crescimento, é dado uma margem para cada área crescer. 
Considere que o programa compilado tem um número muito grande 
de variáveis declaradas. A tabela de símbolos cresce até ocupar a 
área reservada, não podendo crescer mais. Porém, há espaço nas 
demais! 
 
Uma solução é reorganizar a ocupação de todas as áreas do 
programa - semelhante ao sistema de overlays, em que o 
programador é o responsável! 
 
O que é preciso é uma forma automática de controlar o crescimento 
de tabelas, como a memória virtual libera o programador de 
controlar os overlays. 
 
Solução: oferecer muitos espaços de endereçamento virtual 
independentes - segmentos. 
 
14 SO I Cap. 4-B 14 SO I Cap. 4-B 
 
 
O que é um segmento? 
 Seqüência linear de endereços; 
 Inicia em zero e vai até um máximo; 
 Diferentes segmentos podem ter (e, em geral, tem!) tamanhos 
diferentes; 
 O tamanho de um segmento pode variar durante a execução 
(para mais ou para menos); 
 O endereçamento agora deve ser feito em 2 partes: 
 O endereço do segmento; 
 O offset dentro do segmento. 
 Em geral, segmentos contém entidades de tipos diferentes 
(procedimentos, tabelas, pilha, buffers, constantes, etc.). 
 
Vantagens: 
 Se os procedimentos de um programa forem colocados em 
segmentos distintos, a linkedição é facilitada - o endereço de 
uma chamada passa a ser (n,0), onde n é o número do segmento 
e 0 é o endereço de entrada do procedimento/segmento; 
 Se um procedimento é alterado, a compilação não altera 
nenhum dos outros: 
 Mesmo que o programa cresça, os endereços de entrada de 
todos os procedimentos continuam os mesmos. 
 O compartilhamento de procedimentos e bibliotecas (DLLs) é 
mais simples (basta compartilhar o segmento); 
 Já que os segmentos contém elementos de tipos diferentes, a 
proteção pode ser diferente para cada um; 
 É mais fácil compartilhar dados ou procedimentos entre vários 
processos: 
 P. Ex. Bibliotecas grandes, como sistemas gráficos; 
 Em geral, são compiladas e colocadas em todos os programas 
que necessitam delas; 
 Com segmentação, a biblioteca pode ser colocada em um 
segmento separado e pode ser compartilhada entre todos – 
não precisa ser duplicada em cada um; 
 Também é possível fazer este compartilhamento em um 
sistema de paginação, mas é + complexo; 
 Em geral, um sistema de paginação que faz isso simula 
segmentação. 
15 SO I Cap. 4-B 15 SO I Cap. 4-B 
A seguir, podemos ver uma comparação entre paginação e 
segmentação: 
 
 
 
O conteúdo de uma página é acidental. 
A proteção individual das páginas é possível: 
 Pode-se colocar alguns bits extras em cada página para controlar 
a proteção; 
 O programador precisa saber onde ficam as fronteiras para 
determinar o que fica em cada página; 
 Isso é exatamente o tipo de administração que a paginação foi 
criada para eliminar; 
 O usuário de um sistema segmentado tem a ilusão de que todos 
os segmentos estão em memória todo o tempo; 
 Não é necessário se preocupar com a administração do overlay 
deles. 
 
4.7.1 Implementação de Segmentação Pura 
 
Considerações: 
 Segmentos, como páginas, podem sofrer swap; 
 O espaço de um segmento maior pode ser ocupado por um 
menor; 
 Isso leva a perda de espaço útil - fragmentação! 
 Uma solução é a compactação, feita pelo SO. 
 
 
16 SO I Cap. 4-B 16 SO I Cap. 4-B 
Na figura, vemos em a-d operações que produzem fragmentação 
externa. Em e vemos a compactação do ambiente. 
 
4.7.2 Segmentação com Paginação: MULTICS 
 
Com um segmento grande, talvez não seja possível mantê-lo inteiro 
na memória: 
 Pode-se paginá-lo! 
 Assim, só as páginas do segmento que são necessárias no 
momento ficam residentes. 
 
Sistema MULTICS do Honeywell 6000: 
 Memória virtual de 218 segmentos (+ de 250.000); 
 Cada um pode ter 64 K words (36 bits); 
 Cada segmento é uma memória virtual; 
 Segmentos aceitam paginação; 
 Combina as vantagens da paginação: 
 Tamanho de página uniforme; 
 Só mantém em memória o que está sendo usado. 
 com as vantagens da segmentação: 
 Fácil de programar; 
 Modularidade; 
 Proteção; 
 Compartilhamento. 
 
Em a) o descritor de segmentos aponta para as tabelas de páginas. 
Em b) temos um descritor de segmento (os números são os tamanhos 
dos campos). 
 
 
17 SO I Cap. 4-B 17 SO I Cap. 4-B 
 
 
Acima, vemos um endereço virtual. Os campos têm tamanhos de 18, 
6 e 10 bits. 
 
 
 
Acima, vemos a forma de resolução de um endereço virtual. 
O MULTICS contém uma TLB de 16 entradas de alta velocidade 
que pode ser usada para resolver os endereços das páginas mais 
usadas. 
 
 
Programas com conjunto de trabalho até 16 páginas alcançam 
equilíbrio com os endereços de todas as páginas na TLB. 
 
4.7.3 Segmentação com Paginação: Intel 386 
 
 16K segmentos, cada um com até 1G palavras de 32bits; 
 Menos segmentos que o MULTICS, mas significativamente 
maiores; 
 Poucos programas precisam de mais de 1000 segmentos, mas 
muitos programas precisam de grandes segmentos. 
 Memória virtual dividida em 2 tabelas: 
 LDT (Local Descriptor Table): descreve os segmentos locais 
de cada programa (código, dados, pilha, etc.) – cada 
programa tem a sua; 
18 SO I Cap. 4-B 18 SO I Cap. 4-B 
 GDT (Global Descriptor Table): descreve segmentos do 
sistema (SO inclusive) – compartilhada por todos os 
programas. 
 Para usar um segmento, o 386 carrega um seletor para esse 
segmento em um dos 6 registradores de segmentos do 
processador: 
 CS mantém o seletor de código; 
 DS mantém o seletor de dados. 
 
 
 
 Um seletor é composto do seguinte: 
 Índex: 13 bits (máximo de 8K descritores de segmentos); 
 Global (GDT - 0)/Local (LDT - 1): 1 bit; 
 Nível de Privilégio: 0-3. 
 
O descritor 0 não é usado. 
Quando um seletor é carregado em um registrador de segmento, o 
descritor correspondente é carregado da LDT ou GDT e armazenado 
em registradores de microprograma, de onde pode ser acessado 
rapidamente. 
 
Um descritor de segmento consiste de 8 bytes, como pode ser visto 
na figura a seguir: 
 
 
Se o segmento está em memória e o offset está dentro do limite do 
segmento, o Pentium adiciona o campo Base de 32 bits do descritor 
para formar o endereço linear: 
 
 
 
Se a paginação estiver desabilitada (indicado por um bit num 
registrador de controle), o endereço linear é o endereço real. 
Nesse caso, temos um esquema puro de segmentação. 
Se a paginação estiver abilitada, o endereço linear é um endereço 
virtual que deve passar pela MMU, é mapeado em tabelas depágina, 
etc. 
19 SO I Cap. 4-B 19 SO I Cap. 4-B 
O único complicador é que, com 32 bits de endereço e páginas de 4 
KB, um segmento pode conter 1 milhão de páginas. 
Para evitar que segmentos pequenos tenham uma tabela muito 
grande, é usado um mapeamento em dois níveis. 
 
Para evitar o uso frequente da tabela de páginas, o Pentium possui 
uma TLB pequena. Desde que as falhas da TLB sejam raras, o 
desempenho é bom. 
 
Interessante notar que, se uma aplicação não precisa de 
segmentação, é possível usar um espaço único, paginado, de 32 bits. 
Basta carregar todos os registradores de segmento com o mesmo 
seletor, cujo descritor tem Base = 0 e Limit = máximo. 
O offset passa a ser o endereço linear, com um único espaço de 
endereçamento (paginação normal). 
 
De fato, todos os SOs atuais para o Pentium trabalham desta forma. 
Apenas o OS/2 explorava todos os recursos da MMU da arquitetura 
Intel. 
 
Proteção: 
 4 níveis de proteção: 0-3; 
 Sistema de anéis de proteção – 0 é o mais interno: 
 0 – kernel; 
 1 – system calls; 
 2 – bibliotecas compartilhadas; 
 3 – programas do usuário. 
 
Funcionamento da proteção: 
 Tentativas de acessar níveis mais altos são permitidas; 
 Acesso a um nível mais baixo não é permitido – causa traps; 
 Para fazer uma chamada entre níveis, é preciso passar um 
descritor (não um endereço); 
 Assim, não é possível fazer chamadas arbitrárias entre níveis, 
mas somente para entry-points determinados.