Questão 464080

• Banca: CESGRANRIO
• Órgão: Transpetro
• Ano: 2011
• Provas: CESGRANRIO - 2011 - Transpetro - Analista de Sistemas Júnior
• Disciplina: Sistemas Operacionais
• Assuntos: Gerência de Memória

Um processo referencia 5 páginas identificadas por p1, p2, p3, p4 e p5, na seguinte ordem:
p1, p2, p3, p1, p4, p2, p5, p1, p2, p5, p2, p1

Considerando-se que o algoritmo de substituição de página seja LRU e que a memória principal encontra-se inicialmente vazia, qual é o número de transferências de páginas em um sistema com 3 quadros em memória principal?

• A. 6
• B. 7
• C. 8
• D. 9
• E. 10

Gabarito: B

Comentários

• O guilherme respondeu de forma bem didática e correta, segue o site.
  
  http://guilherme.inf.br/index.php?option=com_content&view=article&id=177:questao-24-da-transpetro-2011&catid=45:so&Itemid=59
  
  
• Vou colar aqui a resposta do Guilherme em caso da página sair do ar ou ser inacessível em algum local.
  
  "Amigos, essa é para quem esta estudando a disciplina de "sistemas operacionais", ou então esta ligado em questões de concursos... essa questão caiu na prova para analista de sistemas júnior da TransPetro 2011, realizada neste fim-de-semana (10/7/11):

   

  Questão 24: Um processo referencia 5 páginas identificadas por p1, p2, p3, p4 e p5, na seguinte ordem:
  p1, p2, p3, p1, p4, p2, p5, p1, p2, p5, p2, p1
  Considerando-se que o algoritmo de substituição de página seja LRU e que a memória principal encontra-se inicialmente vazia, qual é o número de transferências de páginas em um sistema com 3 quadros em memória principal?

  (A) 6
  (B) 7
  (C) 8
  (D) 9
  (E) 10

  clique no link "leia mais..." e veja a resposta!

   

   

  Explicação: O programa esta fragmentado em diversas páginas, para executar cada instrução do programa, o sistema operacional precisa carregar a página que contém a instrução que ele precisa executar num determinado momento. No caso deste tipo de exercício, a sequencia de páginas necessárias já esta definida, na sequencia determinada....

  Passo 1: O SO carrega a página P1 para a memória principal (MP). Número de transferências (NT) = 1;
  Passo 2: O SO carrega a página P2 para a MP; NT = 2
  Passo 3: O SO carrega a página P3 para a MP; NT = 3
  Passo 4: O SO precisa carrega a página P1 para a MP, mas.... ela já esta lá! Então... não ocorre nenhuma transferência de página para a memória principal. NT = 3
  Passo 5: O SO precisa carrega a página P4 para a MP, mas não temos mais espaço, pois os 3 quadros de MP estão sendo usados. Então.... como estamos usando o algoritimo LRU (Least Recently Used) para fazer a páginação, o SO descarta os itens (páginas) menos usado recentemente. As últimas páginas mais usadas foram P1 e P3, então essas ficam e o SO descarta da MP o P2, liberando espaço para o P4. NT = 4  (não perca a conta!! rsrs)
  Passo 6: O SO precisa carrega a página P2, portanto, usando o LRU, as páginas mais usadas recentemente foram P4 e P1, então P3 sai, liberando o quadro para P2. NT = 5;
  Passo 7: O SO carrega a página P5 no lugar de P1. NT = 6;
  Passo 8: O SO carrega a página P1 no lugar de P4. NT = 7;
  Passo 9: O SO precisa carrega a página P2 para a MP, mas ela já esta lá! NT = 7;
  Passo 10: O SO precisa carrega a página P5 para a MP, mas ela já esta lá! NT = 7;
  Passo 11: O SO precisa carrega a página P2 para a MP, mas ela já esta lá! NT = 7;
  Passo 12: O SO precisa carrega a página P1 para a MP, mas ela já esta lá! NT = 7;
  
  Resultado: Número total de transferências de páginas para a memória principal (NT) = 7;
  As trocas estão marcadas em vermelho com fundo amarelo:"

• Alguém saberia me explicar, por favor, por que no passo 7, carrega P5 no lugar de P1 e não no lugar de P4?
  
• No  passo 7 a P1 sai porque a P4 foi a usada mais recentemente, no passo 5.
  Já a P1 tinha sido usada no passo 4.
  
  Eu entendi sua dúvida no algoritmo LRU, o que conta mais é o recentemente.
  Tanto faz se uma página foi usada 9 vezes ainda há pouco, e vem outras 2 e são usadas 1 vez. 
  Quem sai é a que não é utilizada durante mais tempo.
  
    
  
  

• Entendi! Obrigada pela ajuda ;)

• Acho que toda questão ao citar uma sigla - como LRU - deveria descrever o significado (que seja em inglês!) da sigla!
  Mas... viva a sopinha de letras! Redes então...
• As explicações dos colegas estão perfeitas. Vamos ver se consigo facilitar mais o entendimento.
  Segundo Tanenbaum, Sistemas Operacionais Modernos, 3ª edição pag. 126; "quando ocorrer uma falta de pagina, elimine a página não utilizada pelo periodo de tempo mais longo".
  Então: A pagina que será utilizada vai para o inicio da fila. Se estiver em memoria passa para o início da fila. Se tiver em disco é trasferida para o inicio da fila. Dos 3 quadros o que tiver mais tempo sem utilização é descartada.
  
  Seguindo a sequencia:
  P1 P2 P3  - são trasferidos do disco para memoria
  P2 P3 P1 - P1 é carregado para o inicio da fila - não houve a necessidade de ir no disco pois ja está em memoria.
  P2 P3 P1 P4 - P4 é transferido do disco para memoria e P2 é o menos utilizado então é descartado
  P3 P1 P4 P2  - P2 é transferido do disco para memoria e P3 é descartado
  P1 P4 P2 P5 - P5 é transferido do disco para a memoria e P1 é descartado
  P4 P2 P5 P1 - P1 é trasferido do disco para a memória e P4 é descartado
  P2 P5 P1 -  agora é feito a troca de ordem das paginas de acordo com a utilização sem pedir paginas ao disco pois as paginas ja estão em memoria.
  Obs: Em vermelhos: Paginas excluidas. Sublinhado: paginas trasferidas.
  
• Essa é uma questão que, na minha opinião, deveria ter sido anulada, pois a questão não informa se as páginas que o programa referencia são páginas modificáveis ou não. Segundo o livro "Arquitetura de Sistemas Operacionais":
  
  Qualquer das estratégias de paginação deve considerar se a página foi ou não modificada antes de liberá-la. No caso de páginas contendo código executável, que não sofrem alterações, há uma cópia dela no disco, então ela pode ser descartada sem fazer "page-out", já as páginas modificáveis, que armazenam variáveis e estruturas de dados, o sistema deverá gravá-la na memória secundária antes do descarte. Cada página possui um "bit de modificação" (dirty bit ou modify bit) para esse propósito.
  
  Se considerarmos que todas as página não foram modificadas pelo programa, I.E. que ela é simplesmente descartada e a nova página é gravada em cima, o resultado é 7
  Já se considerarmos que as páginas sofreram alteração pelo programa, I.E. que a página deve ser salva na memória secundária (area de swap) antes de ser apagada da memória principal, o que ocasionaria 2 operações de transferências de páginas, teríamos 10 transferências:
  
  na memória: P1 P2 P3 ---- 3 transferências
  ...
  Insere página P4 na memória: P1 P2 P3 - p2 faz page-out, é salvo na area de SWAP e P4 é inserido. ---- 5 operações de transferência.
  Se continuarmos teremos as 10 operações.
  
  
  Ou seja, questão com 2 respostas possíveis.