Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO (BCC) E MATEMÁTICA COMPUTACIO NAL (BMC)
ALGORITMOS E ESTRUTURAS DE DADOS III
Professores: Nivio Ziviani (BCC) e Wagner Meira Jr (BMC)
[0.2cm] Monitores: Robert Pereira Pinto e Fabricio Benevenuto de Souza
Trabalho Prático 3
Data de Entrega: 23-Agosto-2002
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).

Memória Virtual

Este trabalho consiste em aperfeiçoar e avaliar um sistema de memória virtual.

Descrição

Neste trabalho será aperfeiçoado um sistema de memória virtual, o qual será utilizado para comparar os algoritmos de construção para árvore geradora mínima Kruskal e Prim que não se limitem à memória primária disponível.

Uma descrição da implementação do sistema de memória virtual é encoontrada no livro Projeto de Algoritmos, exercício 2, página 193 (obviamente a implementação deve ser feita em C, gerando um ``.o'' a ser ligado ao código do respectivo programa principal).

Também foi disponibilizado um exemplo de implementação de busca em profundidade para os sistemas Linux e Solaris usando handler de sinal de segmentação de falha e que implementa os níveis de memória do sistema de memória virtual.

O aperfeiçoamento do SMV existente se dará pela implementação de políticas de reposição de páginas diferentes e a sua avaliação para cargas de trabalho diferentes (isto é tamanhos de vetores diferentes). Devem ser avaliadas as políticas LRU, LFU e FIFO.

Os sistemas implementados devem ser avaliados utilizando as funções getrusage e gettimeofday. Deve-se também distinguir entre os tempos de entrada e saída e tempos de computação. Comente sobre os tempos de usuário e os tempos de sistema e sua relação com os tempos de relógio. Apresente e discuta gráficos e/ou tabelas destes tempos. Deve-se também contabilizar a quantidade de falhas de leitura e escrita para cada uma das políticas, além da sua relação com a quantidade de memória disponível, que não deve ultrapassar 50% da quantidade de memória requerida pelos vetores a serem ordenados. Avalie também o impacto do tamanho do registro a ser ordenado no desempenho das políticas.

Avaliação

Deverão ser entregues:

• listagem das rotinas;
• descrição breve dos algoritmos e das estruturas de dados utilizadas;
• análise da complexidade das rotinas;
• análise dos resultados obtidos.

Distribuição dos pontos:

• execução

  execução correta: 10%

  saída legível: 10%

• estilo de programação

  código bem estruturado: 10%

  código legível: 10%

• documentação

  comentários explicativos: 20%

  análise de complexidade: 10%

  análise de resultados: 30%

A entrega do trabalho prático deve seguir as instruções usuais.