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

Passo 1

O enunciado dá 3 frames disponíveis e a sequência de acessos à memória
(1,2,3,2,4,1,5,2,1,6).
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: 3.
  • Sequência de acessos: (1,2,3,2,4,1,5,2,1,6).
  • 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 1.
  • 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 1 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 3 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 10 acessos). Após cada referência, sempre atualizo o contador da página referida (se for carregada passa a ter contador 1; se já estava em memória o contador aumenta em +1).
  • 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 1 (índice do acesso: 1).
  • Estado antes: frames vazios. Contadores relevantes não existem ainda.
  • 1 não está em memória → page fault.
  • Trago 1 para um frame; inicializo seu contador em 1 (pela convenção). Último uso de 1 = acesso 1.
  • Estado dos frames após: [1,-,-].
  • Page faults acumulados: 1.

Passo 5

Acesso 2 (segunda referência): página 2 (índice 2).
  • Estado antes: frames [1,-,-] com contadores \text{count}(1)=1.
  • 2 não está em memória → page fault.
  • Trago 2 e defino \text{count}(2)=1. Último uso de 2 = acesso 2.
  • Estado dos frames: [1,2,-].
  • Page faults acumulados: 2.

Passo 6

Acesso 3 (terceira referência): página 3 (índice 3).
  • Estado antes: frames [1,2,-] com \text{count}(1)=1,\\ \text{count}(2)=1.
  • 3 não está em memória → page fault.
  • Trago 3 e defino \text{count}(3)=1. Último uso de 3 = acesso 3.
  • Estado dos frames: [1,2,3].
  • Page faults acumulados: 3.

Passo 7

Acesso 4 (quarta referência): página 2 (índice 4).
  • Estado antes: frames [1,2,3] com contadores \text{count}(1)=1,\\ \text{count}(2)=1,\\ \text{count}(3)=1. Últimos usos: 1@1,\\\ 2@2,\\\ 3@3.
  • 2 está em memória → hit. Atualizo \text{count}(2):= \text{count}(2)+1 = 2. Último uso de 2 = acesso 4.
  • Estado dos frames permanece [1,2,3] com contadores \text{count}(1)=1,\\ \text{count}(2)=2,\\ \text{count}(3)=1.
  • Page faults acumulados: 3 (sem aumento).

Passo 8

Acesso 5 (quinta referência): página 4 (índice 5).
  • Estado antes: frames [1,2,3] com \text{count}(1)=1,\\ \text{count}(2)=2,\\ \text{count}(3)=1. Últimos usos: 1@1,\\\ 2@4,\\\ 3@3.
  • 4 não está em memória → page fault. Precisamos expulsar a página de menor frequência.
  • Frequências mínimas = 1 (páginas 1 e 3 têm \text{count}=1). Empate entre 1 e 3. Aplicando desempate LRU: qual foi usada menos recentemente? 1 foi usada no acesso 1, 3 no acesso 3; 1 é menos recente → expulso 1.
  • Expulso 1, trago 4 e defino \text{count}(4)=1. Último uso de 4 = acesso 5.
  • Estado dos frames: [4,2,3] com \text{count}(4)=1,\\ \text{count}(2)=2,\\ \text{count}(3)=1.
  • Page faults acumulados: 4.

Passo 9

Acesso 6 (sexta referência): página 1 (índice 6).
  • Estado antes: frames [4,2,3] com \text{count}(4)=1,\\ \text{count}(2)=2,\\ \text{count}(3)=1. Últimos usos: 4@5,\\\ 2@4,\\\ 3@3.
  • 1 não está em memória (foi expulsa anteriormente) → page fault. Pela nossa convenção, ao recarregar 1 definimos \text{count}(1)=1. Mas primeiro precisamos expulsar alguém porque não há frame livre.
  • Frequências mínimas = 1 (páginas 4 e 3). Empate entre 4 e 3. Desempate LRU: último uso de 3 = acesso 3, de 4 = acesso 5; 3 é menos recente → expulso 3.
  • Expulso 3, trago 1 com \text{count}(1)=1. Último uso de 1 = acesso 6.
  • Estado dos frames: [4,2,1] com \text{count}(4)=1,\\ \text{count}(2)=2,\\ \text{count}(1)=1.
  • Page faults acumulados: 5.

Passo 10

Acesso 7 (sétima referência): página 5 (índice 7).
  • Estado antes: frames [4,2,1] com \text{count}(4)=1,\\ \text{count}(2)=2,\\ \text{count}(1)=1. Últimos usos: 4@5,\\\ 2@4,\\\ 1@6.
  • 5 não está em memória → page fault. Frequência mínima = 1 (páginas 4 e 1). Desempate LRU: 4 foi usada no acesso 5, 1 no acesso 6; 4 é menos recente → expulso 4.
  • Expulso 4, trago 5 e defino \text{count}(5)=1. Último uso de 5 = acesso 7.
  • Estado dos frames: [5,2,1] com \text{count}(5)=1,\\ \text{count}(2)=2,\\ \text{count}(1)=1.
  • Page faults acumulados: 6.

Passo 11

Acesso 8 (oitava referência): página 2 (índice 8).
  • Estado antes: frames [5,2,1] com \text{count}(5)=1,\\ \text{count}(2)=2,\\ \text{count}(1)=1. Últimos usos: 5@7,\\\ 2@4,\\\ 1@6.
  • 2 está em memória → hit. Atualizo \text{count}(2):= \text{count}(2)+1 = 3. Último uso de 2 = acesso 8.
  • Estado dos frames permanece [5,2,1] com \text{count}(5)=1,\\ \text{count}(2)=3,\\ \text{count}(1)=1.
  • Page faults acumulados: 6.

Passo 12

Acesso 9 (nona referência): página 1 (índice 9).
  • Estado antes: frames [5,2,1] com \text{count}(5)=1,\\ \text{count}(2)=3,\\ \text{count}(1)=1. Últimos usos: 5@7,\\\ 2@8,\\\ 1@6.
  • 1 está em memória → hit. Atualizo \text{count}(1):= \text{count}(1)+1 = 2. Último uso de 1 = acesso 9.
  • Estado dos frames permanece [5,2,1] com \text{count}(5)=1,\\ \text{count}(2)=3,\\ \text{count}(1)=2.
  • Page faults acumulados: 6.

Passo 13

Acesso 10 (décima referência): página 6 (índice 10).
  • Estado antes: frames [5,2,1] com \text{count}(5)=1,\\ \text{count}(2)=3,\\ \text{count}(1)=2. Últimos usos: 5@7,\\\ 2@8,\\\ 1@9.
  • 6 não está em memória → page fault. Frequência mínima = 1 (página 5). Não há empate.
  • Expulso 5, trago 6 com \text{count}(6)=1. Último uso de 6 = acesso 10.
  • Estado final dos frames: [6,2,1] com \text{count}(6)=1,\\ \text{count}(2)=3,\\ \text{count}(1)=2.
  • Page faults acumulados: 7.

Resposta

7

Exercícios relacionados