SO - lista 7 - Memória Virtual

Prévia do material em texto

Universidade Federal do Ceará - Sistemas Operacionais 
Prof. Ms. Rafael Ivo 
Lista de Exercícios 7 – Memória Virtual 
 
1) Os sistemas operacionais atuais implementam paginação como gerenciamento de memória e                       
permitem processos muito grandes. Indique os principais problemas de um processo ter uma                         
tabela de páginas muito grande.  
P​roblema: Dois acessos a memória são necessários para acessar um conteúdo na memória. Um para                             
entrada da tabela de páginas outro para obter o conteúdo em si 
2) Alguns processadores possuem uma memória associativa de alta velocidade denominada TLB.                       
Por que ela melhora o desempenho de acesso a memória gerenciada por paginação?  
A TLB é uma espécie de cache, incluído no processador, que permite que ele mantenha as tabelas de                                   
endereços de algumas páginas pré-carregados, o que melhora consideravelmente a velocidade de acesso                         
à memória. Quanto maior é a TLB, mais endereços podem ser armazenados e maior é o ganho. 
3) Explique como a TLB funciona.  
A ​TLB funciona como uma memória cache, mantendo apenas as traduções dos endereços virtuais das páginas                               
mais recentemente referenciadas. Em geral, o TLB utiliza o esquema de mapeamento associativo, que permite                             
verificar simultaneamente em todas as suas entradas a presença do endereço virtual. As traduções dos                             
endereços virtuais podem ser armazenadas em qualquer posição da cache. Na tradução de um endereço virtual,                               
o sistema verifica primeiro o TLB. Caso o endereço virtual (tag) esteja na cache, o endereço físico é utilizado,                                     
eliminando o acesso à tabela de mapeamento (TLB hit). Caso o endereço não esteja na cache, a tabela de                                     
mapeamento deve ser consultada (TLB miss). Se a página estiver na memória principal, a tradução do endereço                                 
virtual é colocada no TLB e o endereço é traduzido. Caso contrário, ocorre um page fault, a página é carregada                                       
para a memória, a tabela de mapeamento é atualizada e a informação é carregada para a TLB. Como a TLB                                       
pode eliminar o acesso à tabela de mapeamento, as informações de um endereço virtual, contidas na entrada                                 
da tabela de páginas, devem também estar na cache. A tabela 3 descreve os campos de uma entrada típica de                                       
uma TLB.  
4) Considere um sistema de paginação com a tabela de páginas armazenada na memória. 
a) Se uma referência a memória leva 50 nanossegundos, quanto tempo leva para um processo 
fazer uma referência a um endereço lógico? 
 
 
 b) Se adicionarmos uma TLB de forma que 75% de todas as referências a páginas são encontradas 
nela, qual a média de tempo gasta para um processo fazer uma referência a um endereço lógico?  
0,75 x 100 = 525ns 
5) A paginação permite que certas páginas sejam compartilhadas entre processos. Explique                       
porque isto seria uma vantagem.  
Uma vantagem da paginação é a possibilidade de compartilhamento de código comum, é feito apenas                             
uma cópia do editor precisa ser mantida na memória física, logo a tabela de páginas de cada usuário é                                     
mapeada para a mesma memória física do editor. Outros programas muito usados também podem ser                             
compartilhados.  
6) A maioria dos sistemas operacionais modernos suporta um grande espaço de endereçamento                         
lógico, permitindo tabelas de páginas excessivamente grandes. Para gerenciá-las, técnicas como                     
paginação hierárquica e tabelas de páginas com hash foram propostas. Explique em detalhes                         
como estas técnicas funcionam.  
Paginação hierárquica: quebra o espaço de endereço lógico em múltiplas tabelas de páginas.  
• Uma técnica simples é uma tabela de página em dois níveis. Manter apenas a parte da tabela                                   
necessária. Ocupa menos espaço para o próprio SO.  
Página com função Hash. Cada entrada na tabela contém uma lista ligada de elementos, consistindo de:                               
O # da página virtual; O # da moldura (frame) e mm ponteiro para o próximo. 
7) O que é paginação por demanda?  
É baseada na paginação simples: a memória lógica é dividida em páginas que podem ser colocadas                               
em qualquer quadro da memória física; a TP é usada para conversão de endereços lógicos em físicos.                                 
Na paginação por demanda apenas as páginas que o processo acessa são carregadas para a                             
memória física. O bit de válido/inválido indica se a página já está presente na memória ou se ainda                                   
está no disco. 
8) Descreva o passo-a-passo que é executado quando uma página referenciada pela CPU não                           
encontra-se na memória principal.  
Ele poderia encerrar o processo do usuário. Solução drástica: Os usuários não devem ter conhecimento                             
de que seus processos estão sendo utilizados em um sistema paginação (a paginação deve ser ocultada                               
para o usuário). Solução mais comum: substituição de páginas. 
 
9) O que é memória virtual?  
A memória virtual envolve a separação entre a memória lógica percebida pelos usuários e a                             
memória física. Essa memória virtual torna a tarefa do programador mais fácil, porque não precisa                             
se preocupar com a quantidade de memória física disponível. O complemento à memória física                           
normalmente é denominado de memória de retaguarda, normalmente localizada na memória                     
secundária (atualmente, a mais utilizada é o disco (swap). 
10) O que é espaço swap?  
È uma memória virtual do computador (também é conhecido como área de troca). A memória virtual                               
funciona como uma extensão da memória RAM, que fica armazenada no disco. O porquê da memória                               
swap precisar existir é simples: o sistema operacional precisa de memória para funcionar, e se a                               
memória acabar, o sistema falha. O swap fica como uma reserva emergencial caso a memória RAM                               
acabe. A memória swap era bastante útil em tempos passados onde memória RAM era algo mais                               
escasso.  
11) Refaça a questão 8 quando não há quadros livres na memória primária.  
 
12) Qual a ideia básica do algoritmos de substituição de páginas ótimo? Por que ele não é usado                                   
nos sistemas operacionais atuais?  
Idéia: Substituir a página que não será usada pelo período de tempo mais longo. 
O uso desse algoritmo garante a menor taxa de page fault possível. Entretanto, esse algoritmo é difícil de                                   
implementar porque requer conhecimento antecipado da sequência de referências às páginas. Não dá                         
pra saber qual página irá demorar mais para ser acessada, não tem como saber quantas instruções serão                                 
executadas antes da página ser acessada. 
13) Descreva a ideia básica do algoritmo de substituição de páginas FIFO e o principal problema                               
de se implementar esta ideia.  
Algoritmo FIFO (Primeiro a entrar, primeiro a sair). O SO mantém uma lista de todas as páginas atuais na                                     
memória, com a página mais antiga na cabeça da lista e a página que chegou mais recentemente situadano final dessa lista. Na ocorrência de uma falta de página, a primeira página é removida e a nova é                                       
adicionada no final. 
Vantagem: Fácil de entender e programar 
Desvantagem: a página há mais tempo na memória pode ser usada com muita frequência. 
14) Como o algoritmo de substituição de páginas Segunda Chance melhora o algoritmo FIFO? 
Uma modificação simples no FIFO evita o problema de se jogar fora uma página intensamente usada, 
simplesmente inspecionando os bits de referência. 
 
15) Como o algoritmo de substituição de páginas NRU melhora o algoritmo Segunda Chance? 
Podemos aperfeiçoar o algoritmo de segunda chance considerando o bit de referência (R) e o bit de                                 
modificação (M) e classificando as páginas em quatro categorias. A principal diferença entre esse                           
algoritmo e o algoritmo de segunda chance é que neste dá-se preferência às páginas não                             
modificadas,reduzindo assim o número de gravações em disco necessárias 
16) Explique a ideia por trás do algoritmo de substituição de páginas LRU e porque é difícil                                 
implementá-la.  
Ao invés de determinar o futuro, observa o passado do uso da página. Ideia: substitui-se a página que não                                     
foi usada pelo período de tempo mais longo. Páginas referenciadas intensamente nas últimas instruções                           
provavelmente serão referenciadas novamente nas próximas instruções. A ideia do algoritmo é boa, mas                           
o principal problema é como implementá-la, porque pode requerer uma assistência muito grande de                           
hardware–Possíveis implementações. Contadores–Sempre que uma página for referenciada, o valor do                     
relógio da máquina é copiado e gravado na entrada da página na tabela de páginas–Substitui a página                                 
com menor valor de relógio. 
17) O algoritmo de substituição de páginas NFU busca ser uma aproximação do algoritmo LRU.                             
Indique como o NFU realiza esta aproximação e o efeito colateral que ele possui.  
Ao invés de usar um contador atualizado a cada referência, como no caso do LRU. O NFU exige um                                     
contador de software atualizado a intervalos regulares de tempo( Cada interrupção de relógio). 
→ SO percorre todas as páginas de memória, para cada página, o bit de referência é adicionado ao                                   
contador, os contadores controlam o quão frequente uma página foi referenciada. 
Problema: Uma página intensamente usada antes, pode ter sido deixada de ser usada depois. Porém, o                               
algoritmo continua afirmando que a página é frequentemente usada “NFU não esquece”. 
18) Indique a modificação que o algoritmo de envelhecimento faz ao algoritmo NFU e explique                             
porque ela torna este algoritmo melhor do que o anterior.  
Modificação do NFU: Os contadores são deslocados um bit à direita antes que R seja acrescentado. O bit                                   
R é adicionado ao bit mais a esquerda. A página com menor contador é escolhida 
19) Um computador tem quatro molduras de página. O tempo de carregamento de página na 
memória, o instante do último acesso e os bits R e M para cada página são mostrados a seguir (os 
tempos estão em tiques do relógio):  
 
a) Qual página será trocada pelo FIFO?  
Página 3 ( Olha o que está carregado a mais tempo) 
b) Qual página será trocada pelo SC? 
Página 2 ( Olha o bit de referência e da prioridade para que tenha o valor 0) 
c) Qual página será trocada pelo NRU? 
Página 2 (Olha o bit R e M).  
Classe 0: R=0 e M=0 : Nem recentemente utilizada nem modificada. Melhor página para substituição. 
 
Classe 1: R=0 e M=1 : Não recentemente utilizada mas modificada. Não é uma opção tão boa porque a                                     
página terá que ser gravada em disco antes da substituição. 
Classe 2: R=1 e M=0 : Recentemente utilizada mas não modificada. Provavelmente será usada                           
novamente em breve, mas pelo menos não terá de ser gravada em disco para ser substituída 
Classe 3: R=1 e M=1 : Recentemtente utilizada e modificada. Pior caso possível. 
d) Qual página será trocada pelo LRU?  
Página 1 ( Olha a última referência e escolhe a menor) 
 
20) Um sistema possui 4 quadros de memória física, inicialmente não alocados e com SO                             
implementando paginação por demanda. Nas tabelas abaixo, a primeira linha indica a                       
sequência de páginas que os processos estão requisitando à memória. As 8 primeiras colunas                           
mostram como as páginas vão sendo alocadas aos quadros e referenciadas. Entretanto, a                         
partir na 9 coluna não há quadros suficientes para a página ​A​. Continue o preenchimento das                               
tabelas segundo os algoritmos mencionados, indicando na última linha se aconteceu um ​page                         
fault ​naquela rodada.  
 
 
 
 
21) Considere a sequência de referências de página a seguir: 0-1-7-2-3-2-7-1-0-3. Quantos 
falhas de página (​page faults​) ocorreriam para os algoritmos de substituição abaixo, supondo a 
existência de 4 quadros inicialmente vazios? 
 
 a) Substituição FIFO 
 
 
 
 
 
 
 
 
 
 
 
 b) Substituição LRU  
 
 
 
 
 
 
22) Considere a sequência de referências de página a seguir: 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 
6, 2, 3, 0, 1. Quantos falhas de página (​page faults​) ocorreriam para os algoritmos de substituição 
abaixo, supondo a existência de 3 quadros inicialmente vazios? 
 
 a) Substituição FIFO  
 
 
 
 
 
 
 
 
 
 
 
 
b) Substituição LRU 
 
 
 
 
 
 
 
 
 
 
 c) Substituição ótima  
 
 
 
 
 
 
 
23) Repita o exercício acima com:  
 
a) 4 quadros  
 
 
 
 
 
b) 5 quadros  
 
 
 
 
 
 
c) 6 quadros 
 
 
 
 
 
 
 
 d) 7 quadros  
 
 
 
 
 
 
 
24) Um computador tem quatro quadros de memória. No primeiro tique do relógio, os bits R são                                 
0111 (página 0 é 0, as demais são 1). Nos tiques subsequentes os valores são 1011, 1010, 1101,                                   
0010, 1010, 1100 e 0001. Se o algoritmo de envelhecimento (​aging​) é usado com um contador                               
de 8 bits, quais valores dos quatro contadores após o último tique? Se uma página precisasse ser                                 
removida após o último tique, qual seria?  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
25) A tabela abaixo ilustra os valores dos bits R (referenciada) de cada página de memória a                                 
cada interrupção do relógio. Neste SO os algoritmos NFU e Envelhecimento usam contadores                         
com 8 bits. Após estas interrupções, acontece um ​page fault ​e uma das páginas precisa ser                               
substituída. Que página será substituída segundo cada um dos algoritmos? Justifique sua                       
resposta mostrando a ideia dos algoritmos.