Algoritmos e Estruturas de Dados III

2$^o$ semestre de 2008

Trabalho prático 5


Data de entrega: 26 de novembro de 2008



Este trabalho prático tem por objetivo projetar um sistema de paginação e utilizar esse sistema para dar suporte a um sistema de cache de consultas.

Um consulta é composta de um ou mais termos. A cada termo temos associado um conjunto de informações de ocorrência daquele termo. Para fins de simplificação, vamos assumir que esse conjunto de informações ocupa um espaço constante e parametrizável. Para satisfazer uma consulta, as informações de todos os termos que a compõem tem que ser lidos e processados. Um exemplo de arquivo de consultas está disponível.

A demanda por um sistema de cache de consultas vem do fato de que o volume dos dados associados aos termos é maior que a memória disponível, sendo necessário algum mecanismo coordenado que utilize tanto a memória primária quanto a memória secundária.

Para projetar o seu sistema de cache você recebe um registro típico de consultas a serem respondidas e o tamanho, em bytes, das informações a serem mantidas por termo. Você também pode assumir que o seu sistema recebe os seguintes parâmetros:

  1. tamanho da memória primária
  2. tamanho de cada página

Como parte do seu projeto, você deve investigar os compromissos em termos de tamanho de página, disposição das informações dos termos nas páginas e política de reposição de páginas. O tamanho da página vai definir o número de termos cujos conjuntos de informações podem ser mantidos em uma única página. A disposição das informações nas páginas define quais os termos cujos conjuntos de informação compartilham a mesma página. Você pode inclusive considerar a utilização de um índice que permita acessar de forma fácil esses conjuntos de informação. A política de reposição de páginas define qual a página a ser descartada quando uma nova página deve ser carregada e a memória está cheia.

Pede-se:

  1. Apresente uma metodologia de projeto do seu sistema de cache, considerando os três aspectos mencionados.

  2. Aplique a metodologia de projeto do sistema de cache e derive os valores ou estratégias para os três aspectos utilizando o registro de consultas provido.

  3. Faça uma análise comparativa das alternativas, em particular para vários valores de memória primária. A sua análise deve se basear na taxa de acerto do cache e número de bytes transferidos do disco para memória. Para fins de contraste, você pode também utilizar outros valores de tamanho de página, estratégias de disposição de páginas e políticas de reposição de página.

  4. Apresente a documentação da metodologia e dos resultados (veja aqui maiores detalhes sobre a entrega de trabalhos práticos).


Wagner Meira Jr
2008-11-11