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

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á \,3\, frames disponíveis e a sequência de acessos à memória é
1,2,3,2,4,1,5,2,1,6.
Informações relevantes fornecidas:
  • Número de frames: \,3\,.
  • Sequência de acessos: \{\,1,2,3,2,4,1,5,2,1,6\,\}.
  • 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 ( \infty), 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 (ou \infty se não aparecer mais).

Passo 3

Estado inicial antes do primeiro acesso: frames vazios:
\text{frames} = \{\\\ -,\\\ -,\\\ -\}.
Contador de falhas de página inicial: \,0\,.

Passo 4

Acesso 1: acessar a página \,1\,.
  • A página \,1\, não está nos frames (frames vazios) → falha de página.
  • Colocamos \,1\, em um frame livre.
  • Frames após o acesso:
\text{frames} = \{\,1,\\\ -,\\\ -\,\}.
  • Falhas acumuladas: \,1\,.

Passo 5

Acesso 2: acessar a página \,2\,.
  • A página \,2\, não está nos frames \{\,1,-,-\,\} → falha de página.
  • Colocamos \,2\, em um frame livre.
  • Frames após o acesso:
\text{frames} = \{\,1,\,2,\\\ -\,\}.
  • Falhas acumuladas: \,2\,.

Passo 6

Acesso 3: acessar a página \,3\,.
  • A página \,3\, não está nos frames \{\,1,2,-\,\} → falha de página.
  • Colocamos \,3\, no último frame livre.
  • Frames após o acesso:
\text{frames} = \{\,1,\,2,\,3\,\}.
  • Falhas acumuladas: \,3\,.

Passo 7

Acesso 4: acessar a página \,2\,.
  • A página \,2\, já está presente nos frames \{\,1,2,3\,\} → não há falha.
  • Frames permanecem:
\text{frames} = \{\,1,\,2,\,3\,\}.
  • Falhas acumuladas: \,3\,.

Passo 8

Acesso 5: acessar a página \,4\,.
  • A página \,4\, não está nos frames \{\,1,2,3\,\} → 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) é
1,5,2,1,6.
  • Para decidir qual página remover, verificamos o próximo uso de cada página atualmente nos frames:
    • Página \,1\,: próximo uso ocorre na primeira posição do futuro → índice de próximo uso pequeno.
    • Página \,2\,: próximo uso ocorre na terceira posição do futuro ( 1ª é \,1\,, 2ª é \,5\,, 3ª é \,2\,).
    • Página \,3\,: não aparece na sequência futura → próximo uso = \infty.
  • Pelo critério ótimo, removemos a página com próximo uso mais distante: \,3\, (porque \infty).
  • Substituímos \,3\, por \,4\,.
  • Frames após o acesso:
\text{frames} = \{\,1,\,2,\,4\,\}.
  • Falhas acumuladas: \,4\,.

Passo 9

Acesso 6: acessar a página \,1\,.
  • A página \,1\, está presente em \{\,1,2,4\,\} → não há falha.
  • Frames permanecem:
\text{frames} = \{\,1,\,2,\,4\,\}.
  • Falhas acumuladas: \,4\,.

Passo 10

Acesso 7: acessar a página \,5\,.
  • A página \,5\, não está nos frames \{\,1,2,4\,\} → falha de página.
  • Sequência futura após este ponto:
2,1,6.
  • Próximos usos das páginas atuais:
    • Página \,1\,: próximo uso é a segunda posição do futuro (aparece como \,1\, depois de \,2\,).
    • Página \,2\,: próximo uso é a primeira posição do futuro (aparece imediatamente como \,2\,).
    • Página \,4\,: não aparece no futuro → próximo uso = \infty.
  • Pelo critério ótimo, removemos \,4\, (próximo uso \infty).
  • Substituímos \,4\, por \,5\,.
  • Frames após o acesso:
\text{frames} = \{\,1,\,2,\,5\,\}.
  • Falhas acumuladas: \,5\,.

Passo 11

Acesso 8: acessar a página \,2\,.
  • A página \,2\, está presente em \{\,1,2,5\,\} → não há falha.
  • Frames permanecem:
\text{frames} = \{\,1,\,2,\,5\,\}.
  • Falhas acumuladas: \,5\,.

Passo 12

Acesso 9: acessar a página \,1\,.
  • A página \,1\, está presente em \{\,1,2,5\,\} → não há falha.
  • Frames permanecem:
\text{frames} = \{\,1,\,2,\,5\,\}.
  • Falhas acumuladas: \,5\,.

Passo 13

Acesso 10: acessar a página \,6\,.
  • A página \,6\, não está nos frames \{\,1,2,5\,\} → 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 é \infty.
  • Pelo critério ótimo, qualquer página atual pode ser removida (todas têm próximo uso = \infty). Escolhemos uma (por exemplo, remover \,5\,), e colocamos \,6\,.
  • Frames após o acesso (uma possibilidade):
\text{frames} = \{\,1,\,2,\,6\,\}.
  • Falhas acumuladas: \,6\,.

Resposta

6

Exercícios relacionados