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:
(a) FIFO

Passo 1

O enunciado dá: há 3 frames disponíveis e a sequência de acessos às páginas é
1,2,3,2,4,1,5,2,1,6.
A pergunta é: calcular o número total de faltas de página (page faults) quando se usa o algoritmo de substituição FIFO (First-In First-Out).
Informações relevantes fornecidas: número de frames =3 e sequência de referências acima. Nada mais será pedido.

Passo 2

Explicação didática do que vamos usar (sem assumir que você já sabe):
  • Uma falta de página (page fault) ocorre quando a página solicitada não está presente em nenhum dos frames; nesse caso precisamos carregar a página na memória (num frame).
  • O algoritmo FIFO funciona como uma fila: quando um novo carregamento é necessário e todos os frames estão ocupados, removemos a página que entrou primeiro (a mais antiga) e colocamos a nova no seu lugar. Não mexemos na ordem quando há apenas um acesso (se a página já estiver presente, é um “hit” e não alteramos a fila).
  • Para controlar o FIFO usamos uma fila ordenada [ \; \cdot\; ] cujo elemento mais à esquerda é o mais antigo (será o primeiro a ser removido). Também manteremos o conjunto de páginas atualmente nos frames, representado por \{\;\}.
    Vou simular acessando cada referência da sequência, indicando se houve falta, o estado dos frames (conjunto) e a fila FIFO, e o contador acumulado de faltas. Assim você aprende a aplicar passo a passo na prova.

Passo 3

Acesso à página 1.
Frames antes: \varnothing (vazio). A página 1 não está na memória → falta de página.
Carregamos 1.
Frames agora: \{1\}. Fila FIFO: [1]. Contador de faltas: 1.

Passo 4

Acesso à página 2.
Frames antes: \{1\}. A página 2 não está na memória → falta de página.
Carregamos 2.
Frames agora: \{1,2\}. Fila FIFO: [1,2]. Contador de faltas: 2.

Passo 5

Acesso à página 3.
Frames antes: \{1,2\}. A página 3 não está na memória → falta de página.
Carregamos 3.
Frames agora: \{1,2,3\}. Fila FIFO: [1,2,3]. Contador de faltas: 3.

Passo 6

Acesso à página 2.
Frames antes: \{1,2,3\}. A página 2 já está presente → acerto (hit), sem falta.
Frames e fila permanecem: Frames \{1,2,3\}, Fila [1,2,3]. Contador de faltas: 3.

Passo 7

Acesso à página 4.
Frames antes: \{1,2,3\}. A página 4 não está presente → falta de página. Como os frames estão cheios, aplicamos FIFO: removemos a página mais antiga da fila, que é 1, e inserimos 4.
Frames agora: \{2,3,4\}. Fila FIFO atualizada: [2,3,4]. Contador de faltas: 4.

Passo 8

Acesso à página 1.
Frames antes: \{2,3,4\}. A página 1 não está presente → falta de página. Pelo FIFO, removemos a mais antiga na fila (que é 2) e inserimos 1.
Frames agora: \{3,4,1\}. Fila FIFO: [3,4,1]. Contador de faltas: 5.

Passo 9

Acesso à página 5.
Frames antes: \{3,4,1\}. A página 5 não está presente → falta de página. Pelo FIFO, removemos a mais antiga da fila (que é 3) e inserimos 5.
Frames agora: \{4,1,5\}. Fila FIFO: [4,1,5]. Contador de faltas: 6.

Passo 10

Acesso à página 2.
Frames antes: \{4,1,5\}. A página 2 não está presente → falta de página. Pelo FIFO, removemos a mais antiga da fila (que é 4) e inserimos 2.
Frames agora: \{1,5,2\}. Fila FIFO: [1,5,2]. Contador de faltas: 7.

Passo 11

Acesso à página 1.
Frames antes: \{1,5,2\}. A página 1 já está presente → acerto (hit), sem falta.
Frames e fila permanecem: Frames \{1,5,2\}, Fila [1,5,2]. Contador de faltas: 7.

Passo 12

Acesso à página 6.
Frames antes: \{1,5,2\}. A página 6 não está presente → falta de página. Pelo FIFO, removemos a mais antiga da fila (que é 1) e inserimos 6.
Frames agora: \{6,5,2\}. Fila FIFO: [5,2,6]. Contador de faltas: 8.

Passo 13

Resumo final: após simular toda a sequência com 3 frames usando FIFO, o total de faltas de página acumulado é 8. Força — você tiraria isso na prova simulando exatamente desse jeito: controlar a fila e o conjunto de frames, marcar hit ou miss a cada referência.

Resposta

8

Exercícios relacionados