SOII_Materia_Parte06

Prévia do material em texto

SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 1 
 
33) RESUMO AULA PASSADA – PAGINAÇÃO 
 
Ilusão da Memória Lógica  O processo acha que esta só memória porque existe a memória lógica. 
Esta ilusão é construída pela conversão que o HW MRU. Ele faz a conversão para cada endereço que 
o processo tem que usar ela converte o endereço que é um endereço lógico para um endereço físico. 
Assim cria a ilusão da memória lógica. 
 
Como é feita essa conversão? A conversão do Endereço Lógico em Endereço Físico é feita em três 
passos: 
1º) Quebra do Endereço lógico em 2 partes: Página Lógica e Deslocamento feita por uma conta. 
2º) Conversão Num_psg_logica em Num_pag_fisica (Tabela de Páginas do Processo) 
3º) Cálculo do Endereço Físico. 
 
A Tabela de Páginas que faz a conversão da página lógica em página física tem campos o mais 
importante é o Num_pag_fisica e os bits de controle Válido (0  Página lógica não existe no mundo 
verdadeiro; 1 Existe no número verdadeiro), Executável (páginas que contém código são 
executáveis e não alteráveis) e Alterável (as páginas que contém variáveis são não executáveis e 
alteráveis). 
 
Se alguém tentar fazer o uso errado dessas paginas e não está autorizado o HW gera uma interrupção 
e o SO ao tratar esta interrupção tipicamente aborta o processo. 
 
Nessa conversão o passo 2 é o mais demorado porque consulta a TPP que está na memória. E 
consultar a memória não é uma coisa muito rápida. Para contornar essa situação existe um 
componente de HW que é um chip chamado TLB que faz parte da MRU. A TLB guarda o endereço 
de alguns registros da TPP. 
 
Na TLB tenho o campo Num_pag_Lógica que na TPP é um índice. Outra diferença é que na TLB 
não tem o bit valido, pois só vai para TLB conversões da pagina logica para pagina física que são 
válidas. 
 
Outro tipo é a TLB alternativa que tem o Num do processo como campo. Esse campo é importância 
porque a TLB é um componente de HW e ela guarda as conversões das paginas logicas para as 
paginas físicas do processo que está em execução. 
 
Quando o processo é bloqueado e o SO escalona outro processo o HW vai usar outra TPP e as 
conversões da TLB estão erradas e não podem mais serem usadas. A TLB convencional que não tem 
o campo Num do processo toda vez que o processo muda a TLB fica vazia. Na TLB alternativa que o 
HW guarda o Num do processo não precisa limpar a TLB quando um novo processo é escalonado. 
Esse campo permite que o HW diferencie de quem é a conversão. 
 
1º Problema da Paginação  Velocidade da Conversão Num_psg_logica em Num_pag_fisica 
(Resolvido pela TLB) 
 
 
 
 
 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 2 
 
34) 2º PROBLEMA DA PAGINAÇÃO  TAMANHO DA TABELA DE PÁGINAS DO 
PROCESSO 
 
 
Figura 1 
 
Para guardar as informações da conversão da memória lógica na memória física mostradas na 
Figura1 temos a Tabela de Páginas do Processo 1 mostrada na Figura 2. 
 
 
Figura 2 
 
Temos n paginas logicas na memoria logica como mostra Figura 1. E precisamos de n registros na 
TPP conforme mostra a Figura 2. 
 
É vantajoso ter muitas paginas logicas sem uso entre a área de dados e a área de pilha porque isso 
permite crescer essas áreas sem muita preocupação em bater uma na outra. Também permite ter 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 3 
 
outros tipos de áreas no meio do caminho. Não gasto memória verdadeira para paginas que não tem 
informação nenhuma. 
 
É muito comum colocar toda capacidade de endereçamento em registradores de 32 bits. A Intel 
trabalha assim por exemplo. Uma Máquina de 32 bits usa registradores de 32 bits. O que é guardado 
nesses registradores? Em um deles é guardado o endereço de memória de 32 bits. 
 
Capacidade de endereçamento de memória: 232 bytes = 4 GB (230*22) 
 
A vantagem de ter milhares de páginas lógicas na memória lógica do processo é crescer a área de 
dados e de pilha e poder incluir outro tipo de área no espaço livre. A desvantagem é o tamanho da 
TPP, pois consume memória porque cada pagina logica tem um registro na TPP. Como cada 
processo tem a sua TPP temos um desperdício de memória com página logicas não utilizadas. 
 
Embora os registradores sejam de 32 bits podemos não utilizar todos esses registradores, mas é 
utilizado porque é mais vantajoso. Não podemos utilizar mais do 32 bits. 
 
Observação 1: 210 = 1 KB 220 = 1 MG 230 = 1 GB 240 = 1 TB 250 = 1 PB 
 
34.1) CALCULANDO A QUANTIDADE DE PÁGINAS LÓGICAS 
 
Capacidade de endereçamento/ Tamanho_Pags = 4 GB/4 KB = 1 MB páginas 
 
Qtd_pag_logica = Qtd_registradores (Entradas) na tabela de pags = 1 MB entradas 
 
Tam_Tab_Pags = Qtd_Entradas_Tabela * Tam_Entrada = 1 MB * 4 B = 4 MB 
 
4 MB  Gasto para guardar a Tabela de Páginas do Processo. Este é o problema. Não é muita coisa 
para a memória hoje em dia, porém tenho uma TPP por processo. Sendo assim, este valor fica 
significativo se temos mais de um processo em execução nas maquinas hoje em dia que tem em 
média 15 a 20 processos. 
 
A máquina possui muitos processos sem interface com o usuário. No Windows são chamados de 
Serviço e no Unix de Daemon. 
 
Então se 1 processo gasta 4 MB para guardar a TPP na memória. 20 processos vão gastar 100 MB. 
Que é um gasto considerável de memória. Isto não é legal. Nenhum fabricante trabalha com este tipo 
de TPP. Todo tem alguma técnica para reduzir o tamanho da TPP. 
 
34.2) 1ª TÉCNICA(SOLUÇÃO) – QUEBRA DA TABELA DE PÁGINAS EM PEDAÇOS 
 
Conforme mostra a Figura 3 temos uma tabela com milhões de paginas. Se o tamanho da página 
lógica for reduzido ele priora o tamanho da TPP, pois ele é o divisor do cálculo para encontrar o 
tamanho da TPP. O que melhora é a fragmentação interna. O desperdício com o tamanho de pagina 
logica é em media de meia pagina logica, ou seja, 2 bytes por pagina logica. 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 4 
 
 
Figura 3 
 
Qual é a vantagem de quebrar em pedaço? É que muito desses pedaços não tem nenhum pagina 
logica valida. No exemplo da Figura 3 somente o primeiro e o ultimo pedaço guardam informação, 
ou seja, paginas logicas validas. Todo o meio da memoria logica da Figura 1 não tem nenhum 
informação (não tem página logica valida). 
 
A ideia é não gastar memoria com estes pedaços da TPP que não tem nenhum pagina logica valida. 
Então a TPP fica reduzida ao pedaço de cima e de baixo da TPP original conforme mostra a Figura 3. 
Logo o gasto com a memória será muito menor. 
 
Como saber quais são os pedaços que tem paginas logicas validas? Onde estão estes pedaços? 
Através do Diretorio de páginas. Ele guarda o endereço de um pedaço da TPP. Para estimar o 
tamanho da TPP preciso saber quantos registros tem no Diretório de paginas que é fácil saber. Para 
cada pedaço se tem 1024 entradas. Para calcular temos: 
 
Tamanho do Pedaço da Tabela de Páginas = Qtd_Entradas_Pedaço * Tam_Entrada = 1024*4 = 4 KB 
 
No exemplo da Figura 3 foram gastos com a Tabela de Páginas 8 KB (2 pedaços) + 4 KB 
(Diretório). Totalizando 12 KB. Um processo maior vai ter mais paginas validas e vai dar um valor 
maior de memória gasto, mas mesmo assim o gasto é menor do que a tabela simples (TPP). Cada 
processo tem uma estrutura parecida com a da Figura 3. 
 
Ao invés de ter o registrador que aponta para a TPP que está em uso. Nesse caso, o registrador 
aponta para o diretório. E é o diretório que diz qual é a TPP que será utilizada. Quando o SO 
escalona outro processo o registrador aponta para outro diretório. 
 
Isto funciona bem, mas tem uma pequena coisa ruim. Existe um gasto maior de tempo para fazer a 
conversão do endereço da página lógica no endereço da página física porque agora a informação não 
existe de forma simples na tabela. 
 
Na TPP simples o índice da tabela é o numero da pagina logica. Para saber onde está a pagina física 
da pagina lógica 3. O HW vai à posição 3 da tabelae vê em que pagina física está a pagina logica 3. 
Nesse caso para saber em qual a pagina física está a pagina logica 3 primeiro o HW tem que ir no 
diretório e vê qual o endereço do pedaço da entrada 0 da TPP da Figura 3. 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 5 
 
Então é feito o acesso ao registro desse diretório e em seguida para saber o endereço da pagina logica 
o HW faz o acesso ao registro do primeiro pedaço. Nesse caso para fazer a conversão serão gastos 
dois acessos a memoria: um para acessar o diretório e outro para encontrar a pagina logica 3. O 
acesso a memoria da conversão introduz uma lentidão na conversão que é resolvida pela TLB. Nesse 
tenho mais lentidão, pois fiz dois acessos à memória física. Esta solução resolve um problema e criar 
outro um pouco menor que é o problema de desempenho (desvantagem dessa técnica). A Intel utiliza 
esta técnica. 
 
Como o SO preenche o conteúdo da tabela? Uma área de controle do arquivo executável diz o 
tamanho do código, o tamanho inicial da área de dados e o tamanho inicial da área de pilha. E o SO 
escolhe na memoria física pagina que estão livres para guardar área de paginas lógicas do processo. 
Depois que ele escolhe ele preenche a tabela com as informações. 
 
Em uma tabela de níveis ele faz a mesma coisa, ou seja, ele vê quantas páginas validas tem na 
memoria logica? É mais ou menos 1024?Se for menos de 1024 será utilizado só um pedaço da 
memoria. Se for mais de 1024 será utilizado 2. A quantidade de pedaços que terei tem haver com a 
quantidade de páginas físicas na memória. A tabela simples não é criada, mas sim a tabela de dois 
níveis. 
 
Como ele sabe qual pedaço que tem que usar? Tem uma logica para o SO saber qual entrada será 
consultada. 
 
O passo 1 para conversão da página logica no endereço físico é quebrar o endereço em duas partes. 
Quantos bits tem o lado direito que é o deslocamento? Depende do tamanho da página. Se a pagina 
for de 4 KB é 212 então são 12 bits para o deslocamento. Os 20 bits restantes que ficam no lado 
esquerdo correspondem o numero da pagina logica Conforme mostra a Figura 4. O Num_pag_logica 
é pego para consultar o número da página física. Assim é feito na Tabela Simples. 
 
 
Figura 4 – Para Tabela Simples 
 
Na Tabela de dois níveis isto é feito um pouco mais complicado. O endereço da página logica é 
quebrado em dois e dois pedaços. Conforme mostra a imagem a seguir: 
 
 
Figura 5 – Para Tabela de Dois níveis 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 6 
 
A Parte 1 da Figura 5 identifica uma entrada no diretório. A parte 2 identifica uma entrada no 
pedaço da Tabela de Páginas. Cada pedaço vai de 0 a 1023. E a parte 3 identifica o byte da página 
na memória lógica do processo 1. 
 
A Figura 5, mostra o como exemplo a representação da página logica igual a 3. 
 
O deslocamento significa o numero do byte dentro da página logica que tem 4 KB. 
 
Essa solução fica bem pior quando se trata de uma máquina de 64 bits. Esta máquina quer dizer que 
o End_logico tem 64 bits com a capacidade de endereçamento 2 64. A Figura 6 mostra a divisão dos 
64 bits. 
 
 
Figura 6 
 
Isto é um tamanho gigantesco. Muitas vezes os fabricantes limitem este endereço. A Figura 6 ilustra 
um fato não real. Sabemos que 26 bits é igual a 2 26 = 64 MB Entradas. Logo, o diretório teria este 
tamanho de entradas. Sendo 4 Bytes por entrada temos 256 MB. Isto só para um processo. Portanto 
a lógica aplicada para 32 bits não pode se mantem para 64 bits porque o diretório e a tabela de 
páginas ficam gigantescos. 
 
Como funciona para 64 bits? A ideia é quebrar em mais níveis porque assim o diretório não terá 
apenas dois níveis. A jogada é a seguinte tenho uma quebra em duas sub paginas porque tenho dois 
níveis. A ideia é quebrar em mais níveis e assim cada diretório será menor. Como funciona? 
 
O 1º nível que seria o diretório ele aponta para tabela de pagina do 2º nível. Conforme mostra a 
Figura 7. Desse jeito a coisa funciona. 
 
Conforme mostra a Figura 8 temos uma entrada para tabela de pagina para cada nível. 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 7 
 
 
Figura 7 
 
 
Figura 8 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 8 
 
A parte 1 da Figura 8 identifica uma entrada no 1º nível. A parte 2 identifica uma entrada no 2º nível. 
A parte 3 identifica uma entrada no 3º nível. A parte 4 identifica uma entrada no 4º nível. A parte 5 
identifica uma entrada no 5º nível. O 6º nível é referente ao pedaço da tabela de paginas. 
 
Esse caso é um caso bem teórico a Intel não usa todos os 64 bits de endereço ela simplifica e usa um 
endereço menor. A tabela de páginas da Intel tem 5 níveis sendo 4 de diretório e 1 referente ao 
pedaço da tabela de paginas. 
 
A solução funciona, mas é insuficiente na hora da conversão, pois tem que ser feito 6 acessos a 
memoria. A desvantagem A solução não é boa para 64 bits. 
 
34.3) 2ª TÉCNICA (SOLUÇÃO) TABELA DE PÁGINAS INVERTIDAS (TPI) 
 
O índice da tabela de pagina é o numero da pagina real, ao invés da virtual, e o conteúdo da entrada 
será o numero da pagina virtual. Alem disso, há um campo indicando a que processo pertence a 
pagina real. Tabela Hash. 
 
Vantagem: economia de espaço, pois há menos paginas reais que virtuais, uma tabela para todos os 
processos. 
 
Desvantagem: Toda pagina real é mapeada, tendo conteúdo ou não, mapeamento muito lento, pois é 
necessário um acesso a memória para cada entrada, até achar a pagina virtual desejada e depende do 
funcionamento da TLB. 
 
Como a tabela é classificada por endereço virtual, o SO pode calcular onde na tabela está a entrada 
de endereço físico associada e usar esse valor diretamente. Uma das vantagens desse método é que 
cada tabela de pagina pode consistir em milhões de entradas. Essas tabelas consomem grande 
quantidade de memória física, que é necessária apenas para controlar como a outra memória física 
esta sendo usada. 
 
Para resolver esse problema, podemos usar uma tabela de pagina invertida. Uma tabela de pagina 
invertida tem uma entrada para cada pagina real de memória. Cada entrada consiste no endereço 
virtual da pagina armazenada naquela posição de memória real, com informações sobre processo que 
é proprietário da pagina. Assim, só existe uma tabela de pagina no sistema, e ela so tem uma entrada 
para cada pagina de memória física. 
 
Esse esquema aumenta o tempo necessário para pesquisara tabela quando ocorre uma referencia de 
pagina. Como a tabela de pagina invertida é classificada por endereços físicos, mas as pesquisas são 
feitas com endereços virtuais, a tabela inteira talvez precise ser pesquisada para encontrar uma 
correspondência. Essa pesquisa pode demorar muito. Para aliviar o problema, usamos uma tabela de 
hashing para limitar a pesquisa para uma entrada ou, no Maximo, algumas poucas entradas na tabela 
de paginas. É claro que cada acesso a tabela de hashing acrescenta uma referencia de memória ao 
procedimento, por isso uma referencia de memória virtual requer pelo menos duas leituras de 
memória real: uma para a entrada na tabela de hashing, outra para a tabela de pagina. Para melhorar 
o desempenho, utilizamos os registradores de memória associativa para manter entradas 
recentemente localizadas. Esses registradores são pesquisados em primeiro lugar, antes que a tabela 
de hashing seja consultada. 
 
 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 9 
 
 
Figura 9 
 
 
Figura 10 
 
Na Tabela de Paginas convencional ele é um array que tem um índice que é o numero da pagina 
logica e o campo contém o endereço da pagina física. Na Tabela de Páginas Invertida é ao contrário. 
Conforme mostra a Figura 10. O campo é o numero da página logica e o índice a pagina física. Então 
quem está na pagina física 0? A página logica 2. Quemestá página física 1? A página física 3. E 
assim por diante conforme mostra a Figura 9. 
 
Observamos na Figura 9 que a pagina logica 0 pode ter dois endereços de página físicas diferentes. 
Logo tem que ter mais informação na tabela invertida. Que é o numero do processo. E o bit de 
páginas válidas sendo 0 para página não válidas e 1 para páginas válidas. 
 
Essa tabela invertida tem uma grande vantagem importantíssima em relação às tabelas convencionais 
que o fato de ser única para toda maquina. Na tabela convencional tem uma para cada processo. A 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 10 
 
Invertida não, pois contem os dados de todos os processos. Embora possa ser uma tabela muito 
grande sua vantagem é ser única e o gasto é único. 
 
Instrução do processo 1 MOV X, 1200. Esse endereço 1200 é um endereço logico que o processo 
1 está utilizando e tem que ser convertido para o endereço físico. Fazendo a conversão encontramos 
página logica 2 e deslocamento 1. Então esse cara tem que virar endereço físico. Os 12 bits de 
deslocamento não mudam. Mas, para fazer a conversão tem o passo 2 que é descobrir qual é a página 
física que corresponde a pagina logica em questão. 
 
O dado que não tenho é justamente o endereço da página física. O dado que tenho é o endereço da 
pagina logica e é o conteúdo da tabela. Então para saber qual é a página física em principio terei que 
procurar. 
 
Em qual página física esta o Num_pag_logica = 1 do processo 1? Procura na tabela invertida de 
baixo para cima até encontrar. Nesse caso para fazer a conversão exibida na Figura 11 foram feitos 5 
acessos a Tabela invertida para encontrar o End_fisico da página logica 1 do processo 1. 
 
 
Figura 11 
 
Nesse exemplo o cenário é muito bom poderia ser pior a página poderia estar lá em cima da TPI. O 
problema (desvantagem) da Tabela invertida é conseguir fazer a conversão do Endereço da Página 
Lógica para Endereço da Página Física. 
 
Esse problema de procurar um dado em uma tabela é comum. Por exemplo, o caso de banco de 
dados consultar o dado do funcionário João da Silva tem um monte de empregados. Terá que 
procurar na tabela de empregados até encontrar esse sujeito. Existe uma coisa no banco de dados que 
é a indexação da tabela. Você pode escolher campos que vão ser utilizados para indexar a tabela. 
 
1ª SOLUÇÃO: TABELA DE PÁGINAS EM NÍVEIS: 
 
- A tabela de paginas é dividida em pedaços, pelo gerenciador de memória, em tamanhos 
iguais (diretórios), onde cada pedaco é apontado por uma entrada de diretório de paginas. 
- Desvantagem: Ocupa mais espaço, pois usa mais uma tabela. Se a pagina não estiver 
mapeada na TLB, são necessários 2 acessos a memória para encontrar a pagina real. 
- Vantagem: Somente diretórios contendo pelo menos uma pagina ativa são mapeados. Como a 
maioria das paginas virtuais fica ociosa, o numero de paginas mapeada é relativamente 
pequeno. Somente mapeando paginas virtuais com bit de presença 1. 
 
Implementado pelo hardware, mais precisamente pela Intel. 
 
Estruturas esparsas contêm informações irrelevantes, onde a maioria de seus valores são nulos, por 
exemplo, uma tabela de página que tem 1 milhão de entradas, a maior parte delas terá o bit de 
validade igual zero, poucas tem bit de validade igual a 1. Se nessa matriz a maior parte dos 
elementos for igual a 0 e se algum for diferente de 0, então existe uma jogada que resolve esse 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 11 
 
problema da memória, ao invés de fazer a matriz como um array direcional, fará um array de 
ponteiros para o array, nas poucas linhas que tem espaço relevante essas linhas tem um array de 
linhas alocadas. As demais linhas que tem sempre 0 não precisam de um array para guardar. 
 
 
Estruturas Esparsas linhas 
 
 
 
 
 
 
 
 
 
Fuction getElem (i,j : Integer) : byte; 
Begin 
 If linhas [i] = nil then getElem:=vazio 
 Else getElem = linhas[i]^[j]; 
End 
 
A função acima verifica se a linha existe ou não. Se não existir fica com valor 0, isso acontece nos 
casos em que a linha é igual a nil. Se existe, ou seja, linha diferente de nil, então será obrigado a 
percorrer o ponteiro que aponta para esse array. O espaço será muito menor. 
 
Esse é um mecanismo que existe no Windows NT. Ao invés de gastar 100MB, devido o array ter 
1000 linhas e 1000 colunas (1000 x 1000 é igual a 100MB), estará gastando 70KB. 
 
A tabela de páginas é dividida em partes iguais e só irão existir as que tiverem páginas válidas. Para 
isso haverá uma tabela que é chamada de diretório de páginas que essas partes iguais e só conterá as 
informações de páginas válidas. As demais páginas da tabela voltam para o nil. A estrutura desta 
tabela será o mesmo que o array de array mostrado acima. 
 
DIRETÓRIO DE PÁGINAS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
0 0 3 4 0 
 
0 0 0 0 
0 0 0 0 
0 0 2 
 1 0 0 3 
 
 
 
 
 
 1002 
1001 
1000 
1000
0 
0 0 3 4 0 0 
 
 
 
1 K 
entradas 
1 K 
entradas 
 
 
 
 
 
2 
1 
0 
 0 
 0 
504 1 
502 1 
500 1 
 
 0 
 0 
0 1 
4 1 
2 1 
 
1000
0 
0 0 2 0 
0 1 0 0 3 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 12 
 
Só duas páginas válidas, representadas pelos dois arrays acima, terão espaço fisicamente, os demais 
não irão existir, no caso da Intel terá 1K entradas e em cada pedaço de página também tem 1000 
entradas. De 4 MB (1MB X 4bytes) teremos 12 KB, já a tabela de páginas será maior se tiver várias 
páginas com valor válido, mas nunca será tão grande quanto 4 MB. É uma solução que funciona, 
pois a tabela de páginas fica muito menor, porém a conta do começo é inválida, quando a conversão 
de virtual para real é feita via tabela de páginas, são gastos dois acessos a tabela de páginas, um para 
acesso ao diretório e outro para a operação da tabela de páginas. Quando a conversão não está na 
TLB terá dois acessos a tabela de páginas, deixando o acesso bem maior. 
 
Cálculo: 
Acesso a memória via TLB = 10+100*p 
Via Tabela de páginas = (10 + 100 + 100 +100)*(1-p) = 210p + 310 (1-p) = 310 – 
200p= 310-180=130. 
Considerando 90% de perda, pois são dois acessos a tabela de páginas, um para o diretório de 
páginas e o 2 º acesso é o pedaço da tabela de páginas. 
 
2ª SOLUÇÃO: TABELA DE PÁGINAS INVERTIDAS: 
 
Com uma tabela tão grande a solução em níveis não funciona porque o diretório de páginas fica 
muito grande, a solução é colocar mais níveis, mas isso deixaria mais lento o tempo de conversão via 
tabela de páginas, isso não é muito bom. Quando a máquina tenta fazer um mapeamento tão grande o 
que normalmente se adota é a tabela de páginas invertidas. É uma derivação da tabela de páginas. 
 
O que é a tabela de páginas? Têm mais bits de controle, nº da página física e o índice da tabela de 
páginas, não são armazenas pois são índices de arrays, mais o índice da página lógica. A tabela de 
páginas é muito grande pois o espaço lógico é muito grande, por exemplo, com 32 bits de 
endereçamento como é o caso da Intel. 
 
 
 
 
 
11 
10 
9 
 
 
 
 
 
 
7 1 0 1 
0 1 0 1 
4 1 1 0 
2 1 1 0 
 
 
 
 
 
 
 
13 
12 
11 
10 
9 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Nº da página 
lógica 
Nº da página 
física E
x
ec
u
tá
v
el
 
A
lt
er
áv
el
 
n
ú
cl
eo
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 13 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Não tem mais a questão da quantidade de tabelas de páginas por processo, mas tem um PID que 
identifica o processo. Tenho uma tabela só para todos os processo. Ocupa muito menos espaço para 
armazenar a tabela. Poderia se pensar que essa é uma solução excelente, pois, gasta muita menos 
memória, porque não é memória lógica é memória física e, além disso, é uma tabelasó para todos os 
processos, mas tem um grande problema: O que é feito pelo hardware quando executa a seguinte 
instrução: mov ax, [4100], tem que converter o endereço que é lógico para o endereço 
correspondente, divide o hardware em dois pedaços, o pedaço que é o deslocamento da página e faz 
a conversão para o nº da página lógica para o número da página física. Na tabela de página normal já 
se sabe qual o endereço lógico, pois, está no array, neste caso não, terá que procurar, não é só ir 
direto na posição e saber qual o número que está lá. Por exemplo: Qual a página física onde está a 
página lógica 1 do processo 1? Ao invés de fazer um acesso a memória, tem que fazer vários acessos 
para saber qual a página física. Essa conversão tem que ser feita para cada instrução que está na 
memória. A procura é feita através da tabela Hash, para ganhar velocidade de acesso. Por causa 
disso, a TLB é bem mais eficiente, ou seja, a conversão será melhor se for feita via TLB ao invés da 
tabela de páginas invertida. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SO 
 
dados 
código 
 
 
 
 
12 
11 
10 
9 
8 
7 
6 
5 
4 
3 
2 
1 
0 
SO 
Espaço Virtual Espaço Real Espaço Virtual 2 
 
 
 
 
12 
11 
10 
9 
8 
7 
6 
5 
4 
3 
2 
1 
0 
Nº da página 
física 
Tabela de 
página invertida 
 
 
 
2 2 
3 1 
 
0 2 
1 1 
1 2 
0 1 
 
2 2 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 14 
 
 
Vantagem : Eficiente por gastar pouca memória 
Desvantagem : Ficará mais lento 
 
3ª SOLUÇÃO: GERAÇÃO DE UMA INTERRUPÇÃO (SEM SPARC): 
A conversão entre o endereço lógico e físico tem que ser feito, mas quem faz é o software, então na 
3ª solução ela é a geração de uma interrupção o HW faz a conversão do endereço lógico para o 
endereço físico, antes passa pela TLB para ganhar velocidade, todo o hardware de paginação tem 
TLB para ganhar velocidade, no caso dessa solução eles tentam fazer a conversão na TLB se 
conseguir é ótimo, se a conversão não tiver na TLB então o hardware gera uma interrupção. Essa 
conversão de lógico para físico é uma coisa complicada então as estruturas de controle estão 
amarradas ao hardware. A idéia dessa solução é deixar livre a escolha da estrutura de controle. Quem 
vai decidir qual o melhor mecanismo será o programador do SO. 
 
Onde está o SO? 
1) Em outro espaço de endereçamento lógico 
2) Nos espaços de endereçamento de todos os processos 
 
Tabela (SPARC) 
 
Nº da página lógica Nº da página física Validade Id do Espaço lógico 
1 4 1 1 
3 7 1 1 
0 5 1 2 
 
DIFERENÇAS ENTRE TABELA DE PÁGINA NORMAL E TABELA DE PÁGINA 
INVERTIDA: 
 
Estado Civil 
1 – Solteiro 
2 – Casado 
3 – Viuvo 
4 – Divorciado 
 
var 
 Est_Civil: array[1..4] of String; 
begin 
 Est_Civil[1] := „Solteiro‟; 
 . 
 . 
 . 
Function StringEstCivil(i: integer) : String; // ISTO É UM LOOK UP TABLE,ou 
// seja tabela de página normal, que é 
//mais eficiente que uma tabela de 
//página invertida 
begin 
 StringEstCivil := Est_Civil[i]; 
End; 
 
Function GetNomePai( s: String) : String; // Exemplo de uma tabela de página invertida, 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 15 
 
// pois possui procura e tem perda de 
// performance devido a esta procura. 
var i: integer; 
begin 
 for i = 1 to 100 do 
if A[i].Nome = s then // ISTO É UMA PROCURA! Devido ao teste 
//de igualdade que se repete. 
 return A[1].NomePai; 
end; 
 
Type 
 Pessoa = Record; 
Nome, NomePai : String; 
End; 
var 
 Pessoas: array[1..100] of Pessoa; 
begin 
 Pessoa[1].Nome := “Joao”; 
 Pessoa[1].NomePai := “Antonio”; 
 Pessoa[2].Nome := “Maria”; 
 Pessoa[2].NomePai := “Pedro”; 
end. 
 
2º PROBLEMA: TAMANHO DA TABELA 
 
A) Tabela de páginas em níveis (Intel 80386, 80486, Pentium): O problema desta solução é que a 
cada chamada externa tiver trocar o espaço do processo tem que zerar a TLB. 
 
B) Tabela de páginas invertidas (IBM: Power PC). É uma tabela para todos os processos, para não 
ocupar muito espaço. Não precisa zerar a TLB quando faz uma chamada ao sistema operacional 
sob a forma de uma interrupção, porque o espaço do endereçamento lógico é o mesmo. A 
interrupção ou chamada ao sistema ocorre e o espaço do processo também tem no sistema 
operacional, eles compartilham o espaço. Então a vantagem desta solução é de não zerar a TLB; 
Observação: O Solaris com processador Intel usam esta solução. 
 
C) Geração de Interrupção (Sun: UltraSparc): não é implementado em hardware, quando a tradução 
endereço lógico e endereço físico não pode ser feito via TLB. Neste caso, o hardware gera uma 
interrupção e o sistema operacional trata esta interrupção, fazendo a conversão, usando estrutura 
de dados feita em software e não hardware, o programador do software que escolhe a estrutura de 
dados usada para conversão. Diferente das duas soluções acima que utiliza estrutura de dados que 
o hardware conhece, então o hardware consulta a estrutura de dados e faz a conversão. 
 
Localização do Sistema Operacional: 
A) O SO tem seu próprio espaço de endereço lógico. 
B) O SO está presente no espaço lógico de todos os processos(Windows 95, NT, Linux); 
 
 
 
 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 16 
 
35) TABELA HASH – FUNÇÃO HASH 
 
A Tabela Hash é sempre associada a uma função hash. A Figura 12 apresenta a Tabela Hash. 
 
F(campos)  Nº Inteiro  Indexa a Tabela Hash 
 
Nesse caso quero procurar o numero do processo e o numero da página logica. Logo, terei a seguinte 
função hash: F(Nº da Página Lógica, Nº do Processo)  Inteiro 
 
Quando cada processo é criado o SO preenche a tabela invertida e também preenche a Tabela Hash. 
Então vamos supor que começou o processo 1. O SO preencheu a TPI e a TH com os dados do 
processo 1. Mas, para preencher a tabela hash vai ter usar a função hash para cada pagina logica do 
processo 1. 
 
F(Nº da Página Lógica, Nº do Processo)  (Nº da Página Lógica + Nº do Processo) % Tamanho da 
Tabela Hash 
 
 
Figura 12 
 
Fazendo o cálculo da função hash para cada página logica do processo 1. O resulta dessa função é o 
numero da página física onde está à página logica do processo. Onde está a página lógica do 
processo 1? Na pagina física 1 (encontrada através da F(0,1)) é esse valor que é colocado na página 
física da TH. O campo da TH é o numero da página física. 
 
Cálculo das funções de hash para o processo 1: 
F(0,1) = (0+1) % 14 = 1 
F(1,1) = (1+1) % 14 = 2 
F(2,1) = (1+2) % 14 = 3 
F(3,1) = (3+1) % 14 = 4 
 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 17 
 
Então o SO preencheu a Tabela Hash mostrada na Figura 12 e a Tabela Invertida mostrada na Figura 
13. A Tabela Hash é única assim como a Tabela Invertida. 
 
36) TABELA INVERTIDA 
 
A Tabela de páginas é igual à Tabela de Páginas comum exceto pelo fato de que a Invertida aponta 
para endereços lógicos (relação endereços físicos x endereços lógicos). 
 
Ex.: 
 
No. Pág. Lógica 
correspondente 
à Pág. Física 
Tabela de 
Páginas 
Invertida 
 
2 
4 
7 
 
7 
4 
9 
0 
0 
9 
8 
7 
6 
 5 
4 
3 
2 
1 
0 
0 
2 
1 
2 
 0 
1 
2 
1 
1 
2 
PID do 
Processo 
9 
8 
7 
6 
 5 
4 
3 
2 
1 
0 
Espaço de 
Endereçamento 
Lógico (EEL) do 
Processo 1 
 
PILHA P 2 
PILHA P1 
CÓD P 2 
 
DADOS P1 
1 DADOS P2 
CÓD P 1 
CÓD P 1 
CÓD P 2 
CÓD P 1 
 
 
 DADOS P1 
 
 
PILHA P 1 
 
 
 
CÓD P 1 
9 
8 
7 
6 
 5 
4 
3 
2 
1 
0 
Espaço de 
Endereçamento 
Físico (EEF) 
9 
8 
7 
6 
 5 
4 
3 
2 
1 
0 
Espaço de 
Endereçamento 
Lógico (EEL) do 
Processo 2 
 
 
 CÓD P 2 
 
 
DADOS 
P2 
 
PILHA P 2 
 
CÓD P 2 
A Tabela de Páginas Invertida é muito menor que 
a Tabela de Páginas pois o tamanho daquela é 
exatamente o tamanho da memória física. 
 
Se a máquina tem 512MB de memória, haverá 
128K entradas em vez de 1 M entradas(se fosse 
usada a Tabela de Páginas). 
 
Só existe uma Tabela de Páginas Invertida para 
todos os processos em vez de uma Tabela de 
Páginas para cada processo. 
 
Para que o HW saiba a qual processo pertence 
cada página física/lógica, há a necessidade de se 
utilizar um campo PID. 
No. Pág. 
Física 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 18 
 
 O problema é que é necessário varrer toda a Tabela de Páginas Invertida até encontrar a Página 
Física que tem como referência uma determinada Página Lógica usada por um determinado processo. 
 
O HW que usa Tabela de Páginas Invertida precisa usar uma tabela de hash que aumenta a 
velocidade na procura de uma página lógica. 
 
É mais lenta que a Tabela de Páginas em cerca de 5 vezes. 
 
A TLB precisa ser muito eficiente para compensar a lentidão da Tabela de Páginas Invertida. 
 
 
Figura 13 
 
Durante a execução o HW tem que fazer a conversão de página logica para pagina física. Agora com 
a TH como o HW faz? Ele aplica a função hash, por exemplo, F(1,1) = 2. Ele usa esse valor para ir à 
hash na posição 2 e encontra a página física que é 4. Para ter certeza ele vai na posição 4 da TPI e 
verifica se de fato a página que está procurando é do processo 1. Nesse caso são gastos dois acessos a 
memoria. 
 
Agora vou criar o processo 2 o SO preenche a TI e a TH com os dados do processo 2. Ao aplicar a 
F(0,2) = (0+2) % 14 = 2  Na Tabela Hash esse campo já está em uso. Temos um problema que 
chamamos de colisão. Como resolver a colisão? Tem várias soluções uma solução é criar uma lista 
encadeada de colisão. Tem mais um campo na TI para tratar o caso da colisão que se chama próximo 
elemento da lista de colisão. 
 
Esse campo é um numero inteiro. Então nesse caso deu 4 o hash. Quem colidiu com ele? A pagina 
logica 0 do processo 2. É colocado no campo próximo elemento da lista de colisão o número da 
página logica que ele colidiu. Quem não colidiu não tem próximo e este campo fica sinalizado com 
-1. Conforme mostra a Figura 13. 
 
Cálculo da função hash para o processo 2: 
SISTEMA OPERACIONAL II – PARTE 6 
 
Elaborado por Luciana SA Amancio Página 19 
 
F(1,2) = 3 
F(2,2) = 4  Colisão 
F(10,2) = 12 
 
Digamos que temos a instrução do processo 2  CALL 500. Esse endereço logico 500 tem que ser 
quebrado em duas partes conforme mostra a Figura 14. 
 
Figura 14 
 
Agora para descobrir o endereço físico temos que saber o número da página física. O HW: 
 
1º) Aplica-se F(0,2) = 2; 
2º) Vai na posição 2 da Tabela Hash e vê o valor que está lá, 4; 
3º) Vai na posição 4 da Tabela Invertida e pergunta ai está a página logica 0 do processo 2? Não. 
4º) Verifica o campo Próximo elemento da lista de colisão e vai na posição informada por este 
campo e pergunta se ai está a pagina logica 0 do processo 2? Sim. Então ele descobre o que queria 
que é o endereço físico da pagina logica 0 do processo 2 que é 3. 
 
Nesse caso a quantidade de acessos à memória será menor do que a quantidade de acesso da tabela 
de níveis. A tabela invertida a pesar de ser muito mais complicada ela vai gerar tipicamente menos 
acesso a memória do que uma tabela de níveis. No exemplo, temos 3 acessos. Se tiver 2 colisões 
serão 4 acessos a memoria. A ideia é ter poucas colisões. 
 
Portanto, para 64 bits é mais vantagem usar uma tabela invertida do que usar uma tabela com níveis. 
Porque tem menos acesso a memoria do que tem em uma tabela de níveis. 
 
ESPAÇO GASTO COM A TABELA INVERTIDA 
 
Qtd de entrada * Tamanho entrada = 1 MB * 8 B = 8 MB 
 
Qtd de entradas de Tabela Invertida = Qtd Páginas Físicas 
 
Qtd Páginas Físicas = Tamanho da Memória Física / Tamanho da Página = 1 MB 
 
É uma solução complicada utilizada pela IBM nas suas máquinas de 64 bits é uma solução 
interessante para estas máquinas de 64 bits. 
 
Mainframe utiliza a solução em níveis.