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
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 é
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 e sequência de referências acima. Nada mais será pedido.
Informações relevantes fornecidas: número de frames
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
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
.
Frames antes: (vazio). A página
não está na memória → falta de página.
Carregamos .
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Carregamos
Frames agora:
Passo 4
Acesso à página
.
Frames antes: . A página
não está na memória → falta de página.
Carregamos .
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Carregamos
Frames agora:
Passo 5
Acesso à página
.
Frames antes: . A página
não está na memória → falta de página.
Carregamos .
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Carregamos
Frames agora:
Passo 6
Acesso à página
.
Frames antes: . A página
já está presente → acerto (hit), sem falta.
Frames e fila permanecem: Frames , Fila
. Contador de faltas:
.
Frames antes:
Frames e fila permanecem: Frames
Passo 7
Acesso à página
.
Frames antes: . A página
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 é
, e inserimos
.
Frames agora: . Fila FIFO atualizada:
. Contador de faltas:
.
Frames antes:
Frames agora:
Passo 8
Acesso à página
.
Frames antes: . A página
não está presente → falta de página. Pelo FIFO, removemos a mais antiga na fila (que é
) e inserimos
.
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Frames agora:
Passo 9
Acesso à página
.
Frames antes: . A página
não está presente → falta de página. Pelo FIFO, removemos a mais antiga da fila (que é
) e inserimos
.
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Frames agora:
Passo 10
Acesso à página
.
Frames antes: . A página
não está presente → falta de página. Pelo FIFO, removemos a mais antiga da fila (que é
) e inserimos
.
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Frames agora:
Passo 11
Acesso à página
.
Frames antes: . A página
já está presente → acerto (hit), sem falta.
Frames e fila permanecem: Frames , Fila
. Contador de faltas:
.
Frames antes:
Frames e fila permanecem: Frames
Passo 12
Acesso à página
.
Frames antes: . A página
não está presente → falta de página. Pelo FIFO, removemos a mais antiga da fila (que é
) e inserimos
.
Frames agora: . Fila FIFO:
. Contador de faltas:
.
Frames antes:
Frames agora:
Passo 13
Resumo final: após simular toda a sequência com
frames usando FIFO, o total de faltas de página acumulado é
. 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.