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:
(c) Ótimo
Calcule o número total de page faults utilizando os seguintes algoritmos de substituição de páginas:
(c) Ótimo
Passo 1
O enunciado pede: calcular o número total de page faults (falhas de página) ao usar o algoritmo de substituição ótimo, dado que há
frames disponíveis e a sequência de acessos à memória é
Informações relevantes fornecidas:
- Número de frames:
. - Sequência de acessos:
. - Pressuposição padrão: os frames começam vazios antes do primeiro acesso.
Passo 2
O que é uma “falha de página” e como funciona o algoritmo ótimo:
- Falha de página (page fault): ocorre quando a página referenciada não está presente em nenhum dos frames; então é necessário carregar essa página na memória (possivelmente substituindo outra).
- Algoritmo ótimo (Belady / MIN): ao precisar substituir uma página (quando todos os frames estão ocupados), ele escolhe para remoção a página cujo próximo uso ocorre mais tarde no futuro. Se uma página não for mais usada no restante da sequência, seu “próximo uso” é considerado infinito (
), e ela é a melhor candidata a ser removida.
Como aplicar na prática: para cada acesso que falta na memória, olhamos adiante na sequência (a partir do próximo acesso) e determinamos, para cada página que está atualmente nos frames, o índice do seu próximo uso; removemos a que tiver o maior índice (ouse não aparecer mais).
Passo 3
Estado inicial antes do primeiro acesso: frames vazios:
Contador de falhas de página inicial:
.
Passo 4
Acesso 1: acessar a página
.
- A página
não está nos frames (frames vazios) → falha de página. - Colocamos
em um frame livre. - Frames após o acesso:
- Falhas acumuladas:
.
Passo 5
Acesso 2: acessar a página
.
- A página
não está nos frames → falha de página. - Colocamos
em um frame livre. - Frames após o acesso:
- Falhas acumuladas:
.
Passo 6
Acesso 3: acessar a página
.
- A página
não está nos frames → falha de página. - Colocamos
no último frame livre. - Frames após o acesso:
- Falhas acumuladas:
.
Passo 7
Acesso 4: acessar a página
.
- A página
já está presente nos frames → não há falha. - Frames permanecem:
- Falhas acumuladas:
.
Passo 8
Acesso 5: acessar a página
.
- A página
não está nos frames → falha de página. - Todos os frames estão ocupados, então aplicamos o critério ótimo: olhamos para os acessos futuros após este ponto. A sequência restante (após o acesso atual) é
- Para decidir qual página remover, verificamos o próximo uso de cada página atualmente nos frames:
- Página
: próximo uso ocorre na primeira posição do futuro → índice de próximo uso pequeno. - Página
: próximo uso ocorre na terceira posição do futuro ( ª é , ª é , ª é ). - Página
: não aparece na sequência futura → próximo uso = .
- Página
- Pelo critério ótimo, removemos a página com próximo uso mais distante:
(porque ). - Substituímos
por . - Frames após o acesso:
- Falhas acumuladas:
.
Passo 9
Acesso 6: acessar a página
.
- A página
está presente em → não há falha. - Frames permanecem:
- Falhas acumuladas:
.
Passo 10
Acesso 7: acessar a página
.
- A página
não está nos frames → falha de página. - Sequência futura após este ponto:
- Próximos usos das páginas atuais:
- Página
: próximo uso é a segunda posição do futuro (aparece como depois de ). - Página
: próximo uso é a primeira posição do futuro (aparece imediatamente como ). - Página
: não aparece no futuro → próximo uso = .
- Página
- Pelo critério ótimo, removemos
(próximo uso ). - Substituímos
por . - Frames após o acesso:
- Falhas acumuladas:
.
Passo 11
Acesso 8: acessar a página
.
- A página
está presente em → não há falha. - Frames permanecem:
- Falhas acumuladas:
.
Passo 12
Acesso 9: acessar a página
.
- A página
está presente em → não há falha. - Frames permanecem:
- Falhas acumuladas:
.
Passo 13
Acesso 10: acessar a página
.
- A página
não está nos frames → falha de página. - Após este ponto não há mais acessos (sequência futura vazia), então o próximo uso de todas as páginas atuais é
. - Pelo critério ótimo, qualquer página atual pode ser removida (todas têm próximo uso =
). Escolhemos uma (por exemplo, remover ), e colocamos . - Frames após o acesso (uma possibilidade):
- Falhas acumuladas:
.