Trabalho II: Simulador de Memória Virtual

Objectivo

O objectivo principal deste trabalho é permitir que os alunos adquiram uma maior sensibilidade e conhecimento dos conceitos de memória virtual e dos algoritmos que lhe estão subjacentes. Em particular, pretende-se que os alunos desenvolvam um simulador de uma forma simplificada de memória virtual baseada unicamente em paginação.

Porquê Memória Virtual?

Para intervalos de tempo relativamente pequenos é de esperar que para um programa de grande dimensão, apenas uma pequena parte do código e dos dados sejam necessários. Manter em memória a totalidade do código do programa bem como os seus dados é pouco eficiente já que a parte da memória que não está a ser acedida pode ser atribuída a outros processos.

Se pudermos manter na memória apenas os fragmentos de código e dados que estão a ser usados, então poderemos melhorar a utilização da memória e manter mais processos activos. Ao não mantermos o programa todo em memória, permite-nos pensar em ter programas que sejam maiores do que a quantidade de memória disponível. O utilizador veria então a máquina com um grande espaço de endereçamento apesar de a memória necessária para suportar tudo que ele faz não exista, isto é a memória virtual.

Esse mecanismo pode fazer parte de um sistema de administração de memória. Deve ser executado automaticamente sem que o utilizador precise de saber que ele existe. Código e dados que não estejam a ser usados são mantidos numa memória secundária, habitualmente o disco.

Neste sistema, o espaço de endereçamento virtual é dividido em blocos de igual tamanho chamados páginas. A memória é também dividida em blocos capazes de conter uma página, chamam-se molduras de página. Um endereço de memória virtual tem o seguinte formato:

número da página deslocamento na página

Para localizar a moldura que contém a página associada a um endereço de memória virtual, utiliza-se uma tabela de páginas. A tabela de páginas é consultada sempre que se acede a um endereço de memória virtual. Se a página existir em memória, o endereço físico em memória é calculado a partir do número da moldura que contém a página e do deslocamento indicado no endereço. Se a página não existe em memória tem de ser copiada da memória secundária. Uma das páginas em memória poderá ter de ser removida da sua moldura para dar lugar à nova página. O algoritmo que determina qual a página que deve ser removida é extremamente importante já que pode afectar consideravelmente a performance do sistema, pois pode acontecer que se removam páginas que estão para ser referenciadas proximamente.

Trabalho

Deverá desenvolver um simulador simplificado de memória virtual baseado em paginação. A simulação deve fazer-se através da leitura de uma sequência de comandos (leitura/escrita) de acesso à memória. O programa deve simular o sistema de memória guardando os dados nos comandos de escrita e devolvendo os dados nos comandos de leitura. A memória física e virtual deve ser iniciada com zeros e a tabela de páginas vazia.

Input

O input do programa será sob a forma de texto. Cada linha de input contém um comando. Cada comando é representado por uma letra (C, R, W ou V) seguido de um conjunto de argumentos. O primeiro comando é sempre do tipo C (configuração do simulador). As linhas de input que começam por # ou contendo apenas espaços deverão ser ignoradas. Para salvaguardar possíveis erros, o simulador deverá verificar e reportar erros. Após reportar um erro o simulador deve terminar a execução. Segue-se a descrição de cada um dos comandos a implementar: Erros de input para além dos acima especificados devem ser reportados da forma erro(Input,comando) (exemplo: erro(Input,A 10 5 45)).

Output

O output do programa deve apresentar as operações que decorrem dos acessos feitos à memória usando o seguinte formato:

Exemplos de input/output

Input Output 
  #isto é um comentario

  C 1024 2048 4096 lru 10

  W 0 56
  W 1027 57
  R 0
  R 2058
  R 1027
  V
  
                                  
  load M(0) P(0)
  write M(0) D(0) V(56)
  load M(1) P(1)
  write M(1) D(3) V(57)
  read M(0) D(0) V(56)
  store M(1) P(1)
  load M(1) P(2)
  read M(1) D(10) V(0)
  store M(0) P(0)
  load M(0) P(1)
  read M(0) D(3) V(57)
  Interrupções do relógio: 0
  Comandos de leitura: 3
  Comandos de escrita: 2
  Loads: 4
  Stores: 2
  Hit ratio: 20.00
  Miss ratio: 80.00
  Algoritmo: LRU
  ------------------------------
  Page | Mold Load Last Cont R M
  ------------------------------
     0 |    -    -    -    - - -
     1 |    0    -    5    - - 0
     2 |    1    -    4    - - 0
     3 |    -    -    -    - - -
  ------------------------------
  
  #isto é outro comentario

  C 1024 2048 4096 nfu 10

  W 0 56
  W 1027 57
  R 0
  R 2058
  R 1027
  V
  
                                  
  load M(0) P(0)
  write M(0) D(0) V(56)
  load M(1) P(1)
  write M(1) D(3) V(57)
  read M(0) D(0) V(56)
  store M(0) P(0)
  load M(0) P(2)
  read M(0) D(10) V(0)
  read M(1) D(3) V(57)
  Interrupções do relógio: 0
  Comandos de leitura: 3
  Comandos de escrita: 2
  Loads: 3
  Stores: 1
  Hit ratio: 40.00
  Miss ratio: 60.00
  Algoritmo: NFU
  ------------------------------
  Page | Mold Load Last Cont R M
  ------------------------------
     0 |    -    -    -    - - -
     1 |    1    2    -    0 1 1
     2 |    0    4    -    0 1 0
     3 |    -    -    -    - - -
  ------------------------------

Um conjunto mais alargado de exemplos de input/output pode ser obtido aqui.

Prazos

O trabalho deve ser entregue via web até às 16 horas do dia 30 de Abril de 2007, sendo a sua demonstração feita na aula prática imediatamente a seguir.

O que entregar? Um ficheiro .tar que inclua:

O código deve compilar e executar nas máquinas da sala das aulas práticas. Uma boa estruturação e legibilidade do código será valorizada.