SOII_Aula006_18122012

Prévia do material em texto

SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 1 
 
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. 
 
 
 
 
 
 
 
 
 
 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 2 
 
AULA DE HOJE 
 
1º Problema da Paginação  Velocidade da Conversão Num_psg_logica em Num_pag_fisica 
(Resolvido pela TLB) 
 
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 
 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 3 
 
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 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: 2
32
 bytes = 4 GB (2
30
*2
2
) 
 
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: 2
10
 = 1 KB 2
20
 = 1 MG 2
30
 = 1 GB 2
40
 = 1 TB 2
50
 = 1 PB 
 
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. 
 
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 – AULA 6 - 18/12/2012 
 
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. 
 
NaTPP 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 tabela e 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 – AULA 6 - 18/12/2012 
 
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 é 2
12
 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 – AULA 6 - 18/12/2012 
 
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 – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 7 
 
 
Figura 7 
 
 
Figura 8 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
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. 
 
2ª Técnica (Solução) Tabela de Páginas invertidas (TPI) 
 
 
Figura 9 
 
 
Figura 10 
 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 9 
 
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. Quem está 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 
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é encontraresse 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. 
 
 
 
 
 
 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 10 
 
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 
 
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. 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 11 
 
 
 
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: 
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. 
SISTEMA OPERACIONAL II – AULA 6 - 18/12/2012 
 
Elaborado por Luciana SA Amancio Página 12 
 
 
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.