Questão 748174

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2012
• Provas: CESGRANRIO - 2012 - Petrobras - Analista de Sistemas Júnior - Engenharia de Software-2012
• Disciplina: Algoritmos e Estrutura de Dados

Seja o seguinte algoritmo de substituição de página:

•  Todas as páginas são mantidas em uma lista circular, e um ponteiro (H) referencia a página mais antiga.
•  Quando uma falta de página ocorre, a página apontada por H é inspecionada:
•  Caso o seu bit de referência seja igual a 0, a página é retirada da lista e uma nova é inserida no seu lugar. O ponteiro H passa a apontar para a próxima página da lista.
• Caso o seu bit de referência seja igual a 1, ele será zerado, e H passará a apontar para a próxima página da lista.
• O processo é repetido até que uma página onde R=0 seja encontrada.

Qual é o nome desse algoritmo de substituição de página?

• A. Ótimo
  
• B. Relógio
  
• C. (FIFO) Primeira a Entrar, Primeira a Sair
  
• D. (NUR) Não Usada Recentemente
  
• E. (MRU) Menos Recentemente Usada
  

Gabarito: B

Comentários

• Algoritmo de substituição de páginas Ótimo

  O algoritmo ótimo, proposto por Belady em 1966, é o que apresenta o melhor desempenho computacional e o que minimiza o número de faltas de páginas. No entanto, sua implementação é praticamente impossível. A idéia do algoritmo é retirar da memória a página que vai demorar mais tempo para ser referenciada novamente. Para isso, o algoritmo precisaria saber, antecipadamente, todos os acessos à memória realizados pela aplicação, o que é impossível em um caso real. Por estes motivos, o algoritmo ótimo só é utilizado em simulações para se estabelecer o valor ótimo e analisar a eficiência de outras propostas elaboradas. 

  
  

  Algoritmo de substituição de páginas CLOCK

  Este algoritmo mantém todas as páginas em uma lista circular (em forma de relógio). A ordem mantida segue a seqüência em que elas foram carregadas em memória. Além disso, é adicionado um bit de uso que indica se a página foi referenciada novamente depois de ter sido carregada. Ao precisar substituir uma página o algoritmo verifica se a página mais antiga está com o bit zerado (o que significa que a página não foi mais referenciada) para ser substituída. Se ela não estiver o bit é zerado e a próxima página da fila mais antiga será verificada. Esse processo continua até que uma página antiga com o bit zerado seja encontrada para ser substituída.  
  
  FONTE: http://www.riopomba.ifsudestemg.edu.br/dcc/dcc/materiais/58613113_AULA15-AlgoritmosdeSubstitui%C3%A7%C3%A3odeP%C3%A1ginas.pdf
• Algoritmo de substituição de páginas FIFO
  O FIFO (First-in, First-out) é um algoritmo de substituição de páginas de baixo custo e de fácil implementação que consiste em substituir a página que foi carregada há mais tempo na memória (a primeira página a entrar é a primeira a sair). Esta escolha não leva em consideração se a página está sendo muito utilizada ou não, o que não é muito adequado pois pode prejudicar o desempenho do sistema. Por este motivo, o FIFO apresenta uma deficiência denominada anomalia de Belady: a quantidade de falta de páginas pode aumentar quando o tamanho da memória também aumenta. Por estas razões, o algoritmo FIFO puro é muito pouco utilizado. Contudo, sua principal vantagem é a facilidade de implementação: uma lista de páginas ordenada pela “idade”. Dessa forma, na ocorrência de uma falta de página a primeira página da lista será substituída e a nova será acrescentada ao final da lista.
   
  Algoritmo de substituição de páginas NRU
  O algoritmo NRU (Not Recently Used) procura por páginas que não foram referenciadas nos últimos acessos para serem substituídas. Tal informação é mantida através de um bit. Este algoritmo também verifica, através de um bit de modificação, se a página teve seu conteúdo alterado durante sua permanência em memória. Esta informação também vai ajudar a direcionar a escolha da página. As substituições das páginas seguem a seguinte prioridade: páginas não referenciadas e não modificadas, páginas não referenciadas, páginas não modificadas e páginas referenciadas e modificadas.
  
  http://www.riopomba.ifsudestemg.edu.br/dcc/dcc/materiais/58613113_AULA15-AlgoritmosdeSubstitui%C3%A7%C3%A3odeP%C3%A1ginas.pdf
• Algoritmo de substituição de páginas MRU
  O algoritmo MRU (Most Recently Used) faz a substituição da última página acessada. Este algoritmo também apresenta algumas variações, semelhante ao LRU. Por exemplo, o MRU-n escolhe a n-última página acessada para ser substituída. Dessa forma, é possível explorar com mais eficiência o princípio de localidade temporal apresentada pelos acessos.
  
  http://www.riopomba.ifsudestemg.edu.br/dcc/dcc/materiais/58613113_AULA15-AlgoritmosdeSubstitui%C3%A7%C3%A3odeP%C3%A1ginas.pdf

• Força Guerreiro!!!!!!