Questão: Considere um sistema com 3 frames disponíveis e a seguinte sequência de acessos à memória: 1,2,3,2,4,1,5,2,1,6
Calcule o número total de page faults utilizando os seguintes algoritmos de substituição de páginas:
(b) LRU

Passo 1

O enunciado pede: calcular o número total de page faults usando o algoritmo LRU para um sistema com \;3\; frames e a sequência de acessos
1,2,3,2,4,1,5,2,1,6.
Informações dadas e condições iniciais:
  • Número de frames: \;3\;.
  • Sequência de acessos (na ordem): \;1,2,3,2,4,1,5,2,1,6\;.
  • Assumimos que os frames começam vazios (nenhuma página carregada).
  • Queremos o total de page faults ao final da sequência usando LRU.

Passo 2

O que é LRU e como vamos aplicá‑lo (aula rápida e prática):
  • LRU significa “Least Recently Used” (menos recentemente usado). Quando ocorre um page fault e precisamos substituir uma página, o LRU escolhe para remoção a página que foi usada há mais tempo (ou seja, a última vez que ela foi referenciada foi a mais antiga).
  • Implementação prática para fazer na prova sem complicação: associamos a cada página em memória um “timestamp” (ou contador de tempo) que indica o instante da sua última referência. A cada acesso incrementamos o tempo atual t por 1 e atualizamos o timestamp da página referenciada para t. Ao precisar substituir, escolhemos a página com menor timestamp (a mais antiga).
  • Neste exercício vamos numerar os acessos com tempos t=1,2,\dots,10 na ordem da sequência e seguir exatamente esse procedimento.

Passo 3

Acesso \;1\; (tempo \;t=1):
  • Frames antes: todos vazios \;[\;-,\;-,\;-].
  • Página \;1\; não está em memória → page fault.
  • Carregamos \;1\; num frame; timestamp de \;1 passa a ser \;t=1.
  • Frames depois: \;[1,\;-,\;-].
  • Page faults acumulados: \;1.

Passo 4

Acesso \;2\; (tempo \;t=2):
  • Frames antes: \;[1,\;-,\;-] com timestamps \;1: t=1.
  • Página \;2\; não está em memória → page fault.
  • Carregamos \;2\;; timestamp de \;2 é \;t=2.
  • Frames depois: \;[1,\;2,\;-].
  • Page faults acumulados: \;2.

Passo 5

Acesso \;3\; (tempo \;t=3):
  • Frames antes: \;[1,\;2,\;-] com timestamps \;1:t=1,\;2:t=2.
  • Página \;3\; não está em memória → page fault.
  • Carregamos \;3\;; timestamp de \;3 é \;t=3.
  • Frames depois: \;[1,\;2,\;3].
  • Page faults acumulados: \;3.

Passo 6

Acesso \;2\; (tempo \;t=4):
  • Frames antes: \;[1,\;2,\;3] com timestamps \;1:t=1,\;2:t=2,\;3:t=3.
  • Página \;2\; já está em memória → não há page fault (hit).
  • Atualizamos o timestamp de \;2 para \;t=4 (agora é a mais recentemente usada).
  • Frames continuam: \;[1,\;2,\;3] (ordem física irrelevante, consideramos timestamps).
  • Page faults acumulados: permanece \;3.

Passo 7

Acesso \;4\; (tempo \;t=5):
  • Frames antes: páginas e timestamps \;1:t=1,\;2:t=4,\;3:t=3.
  • Página \;4\; não está em memória → page fault.
  • Precisamos substituir a página menos recentemente usada: entre timestamps \;1,4,3 o menor é \;t=1 (página \;1).
  • Evitamos \;1 e carregamos \;4;; timestamp de \;4 é \;t=5.
  • Frames depois: \;[4,\;2,\;3] (com timestamps \;4:t=5,\;2:t=4,\;3:t=3).
  • Page faults acumulados: \;4.

Passo 8

Acesso \;1\; (tempo \;t=6):
  • Frames antes: \;[4,\;2,\;3] com timestamps \;4:t=5,\;2:t=4,\;3:t=3.
  • Página \;1\; não está em memória → page fault.
  • Menos recentemente usada é a com menor timestamp: \;3 com \;t=3.
  • Evict \;3, carregamos \;1; timestamp de \;1 fica \;t=6.
  • Frames depois: \;[4,\;2,\;1] com timestamps \;4:t=5,\;2:t=4,\;1:t=6.
  • Page faults acumulados: \;5.

Passo 9

Acesso \;5\; (tempo \;t=7):
  • Frames antes: \;[4,\;2,\;1] com timestamps \;4:t=5,\;2:t=4,\;1:t=6.
  • Página \;5\; não está em memória → page fault.
  • Menos recentemente usada é a com menor timestamp: \;2 com \;t=4.
  • Evict \;2, carregamos \;5; timestamp de \;5 fica \;t=7.
  • Frames depois: \;[4,\;5,\;1] com timestamps \;4:t=5,\;5:t=7,\;1:t=6.
  • Page faults acumulados: \;6.

Passo 10

Acesso \;2\; (tempo \;t=8):
  • Frames antes: \;[4,\;5,\;1] com timestamps \;4:t=5,\;5:t=7,\;1:t=6.
  • Página \;2\; não está em memória → page fault.
  • Menos recentemente usada é \;4 (timestamp \;t=5).
  • Evict \;4, carregamos \;2; timestamp de \;2 fica \;t=8.
  • Frames depois: \;[2,\;5,\;1] com timestamps \;2:t=8,\;5:t=7,\;1:t=6.
  • Page faults acumulados: \;7.

Passo 11

Acesso \;1\; (tempo \;t=9):
  • Frames antes: \;[2,\;5,\;1] com timestamps \;2:t=8,\;5:t=7,\;1:t=6.
  • Página \;1\; está em memória → hit, sem page fault.
  • Atualizamos timestamp de \;1 para \;t=9.
  • Frames depois: \;[2,\;5,\;1] com timestamps \;2:t=8,\;5:t=7,\;1:t=9.
  • Page faults acumulados: permanece \;7.

Passo 12

Acesso \;6\; (tempo \;t=10):
  • Frames antes: \;[2,\;5,\;1] com timestamps \;2:t=8,\;5:t=7,\;1:t=9.
  • Página \;6\; não está em memória → page fault.
  • Menos recentemente usada é \;5 (timestamp \;t=7).
  • Evict \;5, carregamos \;6; timestamp de \;6 fica \;t=10.
  • Frames depois: \;[2,\;6,\;1].
  • Page faults acumulados: \;8.

Resposta

8

Exercícios relacionados