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
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
frames e a sequência de acessos
Informações dadas e condições iniciais:
- Número de frames:
. - Sequência de acessos (na ordem):
. - 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
por e atualizamos o timestamp da página referenciada para . Ao precisar substituir, escolhemos a página com menor timestamp (a mais antiga). - Neste exercício vamos numerar os acessos com tempos
na ordem da sequência e seguir exatamente esse procedimento.
Passo 3
Acesso
(tempo
):
- Frames antes: todos vazios
. - Página
não está em memória → page fault. - Carregamos
num frame; timestamp de passa a ser . - Frames depois:
. - Page faults acumulados:
.
Passo 4
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
não está em memória → page fault. - Carregamos
; timestamp de é . - Frames depois:
. - Page faults acumulados:
.
Passo 5
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
não está em memória → page fault. - Carregamos
; timestamp de é . - Frames depois:
. - Page faults acumulados:
.
Passo 6
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
já está em memória → não há page fault (hit). - Atualizamos o timestamp de
para (agora é a mais recentemente usada). - Frames continuam:
(ordem física irrelevante, consideramos timestamps). - Page faults acumulados: permanece
.
Passo 7
Acesso
(tempo
):
- Frames antes: páginas e timestamps
. - Página
não está em memória → page fault. - Precisamos substituir a página menos recentemente usada: entre timestamps
o menor é (página ). - Evitamos
e carregamos ;; timestamp de é . - Frames depois:
(com timestamps ). - Page faults acumulados:
.
Passo 8
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
não está em memória → page fault. - Menos recentemente usada é a com menor timestamp:
com . - Evict
, carregamos ; timestamp de fica . - Frames depois:
com timestamps . - Page faults acumulados:
.
Passo 9
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
não está em memória → page fault. - Menos recentemente usada é a com menor timestamp:
com . - Evict
, carregamos ; timestamp de fica . - Frames depois:
com timestamps . - Page faults acumulados:
.
Passo 10
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
não está em memória → page fault. - Menos recentemente usada é
(timestamp ). - Evict
, carregamos ; timestamp de fica . - Frames depois:
com timestamps . - Page faults acumulados:
.
Passo 11
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
está em memória → hit, sem page fault. - Atualizamos timestamp de
para . - Frames depois:
com timestamps . - Page faults acumulados: permanece
.
Passo 12
Acesso
(tempo
):
- Frames antes:
com timestamps . - Página
não está em memória → page fault. - Menos recentemente usada é
(timestamp ). - Evict
, carregamos ; timestamp de fica . - Frames depois:
. - Page faults acumulados:
.