UNIVERSIDADE DO VALE DO RIO DOS SINOS
Ciências Exatas e Tecnológicas
Graduação Tecnológica em Segurança da Informação - Disciplina de Estruturas de Dados em C++
Prof. Leandro Tonietto
Trabalho
Objetivo
Implementar software para gerenciar armazenamento de arquivos. O software deve controlar o acesso ao
disco, determinar a melhor forma de armazenamento dos arquivos para evitar fragmentação e saber como
recuperar informações de arquivo do disco. Pode-se considerar que tem funcionamento baseado na idéia
de journally.
Funcionalidades do sistema
A interface padrão do sistema é edição de texto. Sempre que o usuário executar o sistema, ele entra em
modo de edição de um arquivo novo. O sistema deve mostrar também as seguintes opções de menu: editar
texto, salvar, carregar, novo, excluir, flush, salvar imagem do disco virtual e carregar imagem do disco
virtual.
O diagrama de funcionamento geral do sistema pode ser visto abaixo (não é um diagrama de classes):
Tabela de
alocação de
arquivos
Interface
GSA
Disco
virtual
Blocos
de bytes
arquivo
Disco
físico
Fila de
arquivos
Opções do sistema:
•
Editar texto: a interface retira o menu e permite que o usuário digite caracteres que serão
inseridos em um arquivo na memória. Quanto o usuário digitar FIM numa linha, o sistema acaba a
edição e, efetivamente, insere os caracteres lidos no objeto do arquivo e retorna ao menu
principal.
•
Novo arquivo: o sistema limpa a tela e cria um novo arquivo na memória e entra
automaticamente na opção editar texto.
•
Salvar arquivo: a interface solicita ao usuário que informe o caminho aonde o arquivo deve ser
gravado e passa os dados e o nome do caminho do arquivo para o Gerenciador do Sistema de
Arquivos (GSA). O GSA coloca o objeto do arquivo numa fila de arquivos a serem gravados no disco
virtual e preenche uma entrada na tabela de alocação de arquivos. Alternativamente, o GSA pode
apenas gravar na fila sem registrar na TAA uma entrada para o arquivo. Neste caso, antes de se
fazer a pesquisa pelo arquivo na TAA, deve-se pesquisar pelo mesmo na Fila de espera. Após
“salvar” arquivo, interface retorna ao menu principal.
•
Flush: esta opção solicita ao GSA que efetive a gravação dos arquivos da fila em disco. Antes de
gravar cada um dos arquivos em disco, o GSA deve verificar qual é a melhor área para gravação
dos blocos arquivo no disco (veja seção escolha da melhor área para gravação). O sistema efetiva
a gravação dos mesmos em disco e atualiza a entrada do mesmo na tabela de alocação de arquivos
(veja seção tabela de alocação de arquivos). Após este procedimento, volta ao menu principal.
Av. Unisinos, 950
Caixa Postal 275
CEP 93022-000
Fone: (51) 3591-1122 Fax: (51) 3590-8172
Email:
São Leopoldo
Rio Grande do Sul
http://www.unisinos.br
[email protected] Site: http://www.inf.unisinos.br/~ltonietto
Brasil
UNIVERSIDADE DO VALE DO RIO DOS SINOS
Ciências Exatas e Tecnológicas
•
Abrir arquivo: a interface solicita ao usuário qual é a identificação do arquivo (veja seção
arquivo), depois solicita ao gerenciador do sistema de arquivos (GSA) que retorne todos os bytes
do arquivo. O GSA localiza na tabela de referências de arquivos o endereço do primeiro bloco de
armazenamento de dados do arquivo, recupera os blocos que compõem os dados do arquivo,
remonta os bytes contidos nos blocos do arquivo no disco, obtém da tabela de alocação de
arquivos os metadados referentes ao mesmo e retorna a representação do arquivo para a
interface. A interface apresenta (imprime) os dados para o usuário. É importante mencionar que,
o GSA deve considerar que o arquivo pode estar em disco ou ainda não sido efetivamente salvo,
portanto, na fila de espera. Sendo assim, ele deve verificar primeiro se o arquivo está na fila de
arquivos e somente depois verificar a existência do arquivo no disco virtual. Após o procedimento,
o sistema pode voltar para o menu principal ou entrar diretamente na opção editar texto (lembrese de que pode ser complicado fazer edição de um texto já existente, portanto, apenas exiba o
conteúdo do arquivo não permita edição).
•
Remover arquivo: a interface solicita que um arquivo seja removido do sistema de arquivos. O
GSA primeiro verifica se o arquivo está na fila e, caso positivo, apenas o retira da fila. Caso
contrário, verifica a existência do arquivo em disco (disco virtual). Caso exista, remove os blocos
do arquivo do disco virtual e também a entrada do arquivo na TAA. Após o procedimento, o
sistema retorna ao menu principal.
•
Salvar imagem do disco virtual: solicita ao GSA que grave o disco virtual em arquivo do HD.
•
Carregar imagem do disco virtual: carrega do HD (de arquivo) o disco virtual assim como estava
quando foi solicitada a geração da imagem do disco virtual.
Arquivo
O arquivo é uma estrutura de dados que contém um array de bytes (conteúdo), um nome, uma
identificação única e demais informações que o aluno julgar importante manter a respeito do arquivo.
Em disco, o arquivo é apenas uma lista encadeada de blocos de bytes, onde cada bloco possui até 16 bytes
de dados e um apontamento para o próximo bloco de dados. O número de bytes por bloco pode ser
configurável, portanto, o sistema deveria ser capaz de gerenciar blocos de qualquer tamanho.
Quando os dados de um arquivo devem ser recuperados, o sistema deve acessar o disco virtual, carregar os
blocos do arquivo e remontar o array de bytes original.
Tabela de alocação de arquivos (TAA)
A tabela de alocação de arquivos é uma lista de metadados de arquivos. Idealmente, deve-se utilizar uma
estrutura do tipo Hashtable para gerenciar as entradas, ou uma lista seqüencial ou até uma árvore
genérica. Cada entrada da tabela de metadados possui: nome do arquivo, endereço do primeiro bloco,
quantidade de blocos do arquivo (ou tamanho em bytes do arquivo) e demais dados que o aluno julgar
interessante (talvez seja útil algum flag para indicar se o arquivo já efetivado em disco ou não).
É importante salientar ainda, que o arquivo em memória possui tanto os metadados quanto os bytes de
conteúdo. Em disco, o arquivo é composto uma lista de blocos de bytes. E os seus metadados são
armazenados na TAA.
Escolha da melhor área para gravação dos blocos dos arquivos.
Por questões de performance de leitura, é muito mais rápido ler os dados (blocos de bytes) em seqüência.
Entretanto, a fim de evitar desperdício ou fragmentação do espaço disponível em disco, o GSA escolhe
reaproveita blocos livres do disco virtual. Portanto, tem-se um paradoxo: é melhor que os dados estejam
gravados de forma seqüencial, porém também é importante evitar fragmentação. A solução é
implementar um algoritmo que tente privilegiar as duas situações da melhor maneira possível. Por
exemplo, o algoritmo pode procurar primeiro por um espaço contínuo de blocos livres que tenha o
tamanho suficiente para armazenar todos os blocos do arquivo em seqüência; caso ele não encontre,
então reaproveita blocos livres.
Av. Unisinos, 950
Caixa Postal 275
CEP 93022-000
Fone: (51) 3591-1122 Fax: (51) 3590-8172
Email:
São Leopoldo
Rio Grande do Sul
http://www.unisinos.br
[email protected] Site: http://www.inf.unisinos.br/~ltonietto
Brasil
UNIVERSIDADE DO VALE DO RIO DOS SINOS
Ciências Exatas e Tecnológicas
O aluno pode sugerir ou implementar o algoritmo de gerenciamento de blocos livres que ele preferir,
desde que evite a fragmentação do disco.
Demais considerações sobre o trabalho
Trabalho deve ser realizado em duplas
Deve ser feito exclusivamente em C++
Deve ser entregue compilável e executável.
A entrega do trabalho é feita em duas etapas, uma para GA e outra (final) para o GB.
Não serão permitidas entregas após o prazo de entrega.
A entrega é composta pelos códigos-fonte do programa devidamente comentados, identados e
compiláveis, bem como pelo executável e demais bibliotecas necessárias para execução.
Avaliação
O trabalho deve ser entregue até o dia 25/11/2008 e contém os seguintes itens entregáveis:
Diagrama de classes para compreensão do sistema como um todo (este não valerá nota, apenas
para entendimento da solução proposta).
Qualidade do código-fonte:
■ Deve ser feito em C++. Códigos-fonte em C serão sumariamente reprovados.
■ Deve-se usar classes para desenvolvimento do trabalho.
Funcionamento: funcionamento do sistema deve obedecer as regras das opções do sistema, supra
citadas.
Apresentação do código-fonte ao professor. Todo código-fonte deve apresentado e explicado ao
professor.
Avaliação individual, contribuição de cada integrante para o desenvolvimento do programa.
Versão da especificação: 1.0, 19/09/2008.
Av. Unisinos, 950
Caixa Postal 275
CEP 93022-000
Fone: (51) 3591-1122 Fax: (51) 3590-8172
Email:
São Leopoldo
Rio Grande do Sul
http://www.unisinos.br
[email protected] Site: http://www.inf.unisinos.br/~ltonietto
Brasil