Algoritmos de substituição de páginas

O objetivo deste projeto é escrever um programa para simular os principais algoritmos de substituição de páginas usados no gerenciamento da memória virtual. O programa deverá simular os seguintes algoritmos:

  • FIFO (First In, First Out)
  • OPT (Algoritmo ótimo)
  • LRU (Least Recently Used)

O programa deverá receber como parâmetro o número de quadros disponíveis na RAM e ler da entrada padrão (stdin) a sequência de referências às páginas (uma referência por linha), conforme o exemplo a seguir:

simula-vm 4 < referencias.txt

ou

cat referencias.txt | simula-vm 4

Neste exemplo, a memória RAM tem 4 quadros disponíveis e o arquivo referencias.txt contém as referências de acesso às páginas.

O programa deve gerar como saída o número de falta de páginas verificado para cada algoritmo, de acordo com o exemplo a seguir:

    4 quadros,      30 refs: FIFO:    17 PFs, LRU:    15 PFs, OPT:    11 PFs

Atenção: deve ser usada a string de formato abaixo para a impressão do resultado na tela. Não imprima mais nada além disso.

printf ("%5d quadros, %7d refs: FIFO: %5d PFs, LRU: %5d PFs, OPT: %5d PFs\n", ...) ;

Para testar seu código, use os seguintes arquivos, que correspondem às strings de referências usadas no livro do professor (capítulo V - Gerência de Memória):

  • Arquivo 1, com resultados mostrados na figura 28 do livro.
  • Arquivo 2, com resultados mostrados na figura 31 do livro.
  • Arquivo 3, trecho de tracing de acessos à memória do compilador GCC (obtido e adaptado desta página). Este tracing tem 106 referências a 64K páginas. Os seguintes resultados são esperados para este teste:
Quadros FIFO LRU OPT
64 38496 30416 18377
256 9859 6270 3107
1024 1450 1273 1260
4096 1260 1260 1260

Deve ser entregue ao professor o código-fonte em C do simulador (arquivo simula-vm.c), devidamente comentado.

Dicas:

  • para ler os parâmetros da linha de comando use argc/argv
  • para ler dados da entrada padrão (stdin) use scanf
n = 0 ;
while ( (! feof(stdin)) && (n < MAXIMO) )
  scanf ("%d\n", vetor[n++]) ;
  • so/algoritmos_de_substituicao_de_paginas.txt
  • Última modificação: 2010/12/10 17:57
  • por maziero