Algoritmos e estruturas de dados

Algoritmos e Estrutura de Dados 3

UFMG/ICEx/DCC

Trabalho Pr´tico 6 a 1o Semestre de 2011

Bacharelado

Esse trabalho pr´tico tem por objetivo familiarizar o aluno com conceitos de mem´ria secund´ria. a o a 1

Motiva¸˜o do problema ca A motiva¸˜o do problema deste trabalho ´ a mesma que foi utilizada no Trabalho Pr´tico 5. ca e a 2

Trabalho Pr´tico 6 a Informa¸˜es sobre localidade de referˆncia, como foi visto no trabalho anterior, podem ser empregadas com sucesso co e no uso de cache, que ´ basicamente uma ´rea de armazenamento tempor´ria onde dados s˜o disponibilizados para e a a a acesso r´pido. Quando um usu´rio do sistema requisita um dado, primeiramente ele verifica a cache, antes de a a realizar o acesso ` mem´ria. Se o dado for encontrado, ent˜o ele ´ utilizado na cache em vez de busc´-lo no local a o a e a original. Essa situa¸˜o ´ conhecida como cache hit (acerto da cache). A porcentagem de acessos que resultam em ca e cache hits ´ conhecida como a taxa de acerto (hit rate ou hit ratio ) da cache. Por outro lado, quando a cache ´ e e consultada e n˜o cont´m o dado desejado, diz-se que ocorreu cache miss (falha da cache). Eventualmente, o dado a e
´ copiado do local original de armazenamento e inserido na cache, ficando pronto para o pr´ximo acesso. e o
O uso de cache pode melhorar o desempenho dos sistemas quando se tem uma porcentagem de acertos alta
(hit ratio alto ), evitando a busca do dado original em dispositivos mais lentos de mem´ria secund´ria. Logo a o a cache deve ser um dispositivo de acesso r´pido cujo custo ´ caro e seu espa¸o, que normalmente ´ pequeno, deve a e c e ser muito bem aproveitado buscando sempre o m´ximo de ocupa¸˜o. a ca
Nesse contexto, a entidade de educa¸˜o mencionada no TP5 deseja construir uma cache na mem´ria do seu ca o servidor principal e conta com a sua ajuda para definir uma configura¸˜o que apresente o melhor custo/benef´ ca ıcio.
Para isso