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:
(d) LFU
Calcule o número total de page faults utilizando os seguintes algoritmos de substituição de páginas:
(d) LFU
Passo 1
O enunciado dá
frames disponíveis e a sequência de acessos à memória
.
A tarefa é calcular o número total de page faults quando usamos o algoritmo de substituição LFU (Least Frequently Used).
Informações relevantes que eu extraio do enunciado:
A tarefa é calcular o número total de page faults quando usamos o algoritmo de substituição LFU (Least Frequently Used).
Informações relevantes que eu extraio do enunciado:
- Número de frames:
. - Sequência de acessos:
. - Algoritmo pedido: LFU.
Passo 2
O que é o LFU e como vou aplicá‑lo (explicação didática e escolhas operacionais):
- LFU (Least Frequently Used) mantém um contador de frequência para cada página que está em memória: toda vez que uma página é referenciada (hit ou quando é trazida), seu contador aumenta em
. - Quando ocorre um page fault e não há frame livre, o LFU escolhe para expulsar a página com o menor contador de frequência.
- Se houver empate entre duas ou mais páginas com a mesma menor frequência, precisamos um critério de desempate. Vou usar desempate por LRU (Least Recently Used): entre as de menor frequência, expulso a que foi usada há mais tempo (ou seja, a menos recentemente). Essa combinação (LFU com desempate LRU) é comum e fácil de simular à mão.
- Convenção sobre contadores ao recarregar página: ao trazer uma página que estava fora da memória, eu inicializo seu contador em
na carga (ou seja, não mantenho contadores históricos de execuções anteriores quando a página foi previamente expulsa). Essa convenção é prática para exercícios manuais e evita ambiguidades. - O que vou registrar em cada acesso: a página solicitada, se é hit ou miss, os contadores de frequência das páginas presentes antes da ação, qual página é removida (se houver), os contadores atualizados e o estado dos
frames após a ação. Também vou numerar os acessos para referência de LRU (índice do passo).
Passo 3
Preparação para a simulação:
- Inicialmente todos os frames estão vazios. Assumo contadores nulos antes de qualquer referência.
- Vou percorrer a sequência acesso a acesso (são
acessos). Após cada referência, sempre atualizo o contador da página referida (se for carregada passa a ter contador ; se já estava em memória o contador aumenta em ). - Manterei também o número do acesso (posição na sequência) para decidir desempates por LRU.
Passo 4
Acesso 1 (primeiro da sequência): página
(índice do acesso:
).
- Estado antes: frames vazios. Contadores relevantes não existem ainda.
-
não está em memória → page fault. - Trago
para um frame; inicializo seu contador em (pela convenção). Último uso de = acesso . - Estado dos frames após:
. - Page faults acumulados:
.
Passo 5
Acesso 2 (segunda referência): página
(índice
).
- Estado antes: frames
com contadores . -
não está em memória → page fault. - Trago
e defino . Último uso de = acesso . - Estado dos frames:
. - Page faults acumulados:
.
Passo 6
Acesso 3 (terceira referência): página
(índice
).
- Estado antes: frames
com . -
não está em memória → page fault. - Trago
e defino . Último uso de = acesso . - Estado dos frames:
. - Page faults acumulados:
.
Passo 7
Acesso 4 (quarta referência): página
(índice
).
- Estado antes: frames
com contadores . Últimos usos: . -
está em memória → hit. Atualizo . Último uso de = acesso . - Estado dos frames permanece
com contadores . - Page faults acumulados:
(sem aumento).
Passo 8
Acesso 5 (quinta referência): página
(índice
).
- Estado antes: frames
com . Últimos usos: . -
não está em memória → page fault. Precisamos expulsar a página de menor frequência. - Frequências mínimas =
(páginas e têm ). Empate entre e . Aplicando desempate LRU: qual foi usada menos recentemente? foi usada no acesso , no acesso ; é menos recente → expulso . - Expulso
, trago e defino . Último uso de = acesso . - Estado dos frames:
com . - Page faults acumulados:
.
Passo 9
Acesso 6 (sexta referência): página
(índice
).
- Estado antes: frames
com . Últimos usos: . -
não está em memória (foi expulsa anteriormente) → page fault. Pela nossa convenção, ao recarregar definimos . Mas primeiro precisamos expulsar alguém porque não há frame livre. - Frequências mínimas =
(páginas e ). Empate entre e . Desempate LRU: último uso de = acesso , de = acesso ; é menos recente → expulso . - Expulso
, trago com . Último uso de = acesso . - Estado dos frames:
com . - Page faults acumulados:
.
Passo 10
Acesso 7 (sétima referência): página
(índice
).
- Estado antes: frames
com . Últimos usos: . -
não está em memória → page fault. Frequência mínima = (páginas e ). Desempate LRU: foi usada no acesso , no acesso ; é menos recente → expulso . - Expulso
, trago e defino . Último uso de = acesso . - Estado dos frames:
com . - Page faults acumulados:
.
Passo 11
Acesso 8 (oitava referência): página
(índice
).
- Estado antes: frames
com . Últimos usos: . -
está em memória → hit. Atualizo . Último uso de = acesso . - Estado dos frames permanece
com . - Page faults acumulados:
.
Passo 12
Acesso 9 (nona referência): página
(índice
).
- Estado antes: frames
com . Últimos usos: . -
está em memória → hit. Atualizo . Último uso de = acesso . - Estado dos frames permanece
com . - Page faults acumulados:
.
Passo 13
Acesso 10 (décima referência): página
(índice
).
- Estado antes: frames
com . Últimos usos: . -
não está em memória → page fault. Frequência mínima = (página ). Não há empate. - Expulso
, trago com . Último uso de = acesso . - Estado final dos frames:
com . - Page faults acumulados:
.
Resposta
7