Sistemas de Operação
Ano Lectivo de 2003/2004
Sistema de Gestão de Ficheiros
Objectivo
O objectivo principal deste trabalho é permitir que os alunos adquiram
maior sensibilidade e conhecimento do funcionamento de um sistema de
gestão de ficheiros. Em particular, pretende-se que os alunos sejam
capazes de compreender e lidar com a organização, o funcionamento e o
modo de solucionar alguns dos problemas que a implementação de um tal
sistema envolve.
Em traços gerais, o trabalho consiste no desenvolvimento de uma
aplicação capaz de emular um sistema (simplificado) de gestão de
ficheiros do tipo FAT. Mais concretamente, isso inclui o compreensão
da estrutura de dados para organização de um tal sistema, a
implementação de rotinas de I/O para acesso ao mesmo, e a
implementação de um conjunto de utilitários de mais alto-nível para
manipulação de ficheiros e directórios.
Descrição
Um sistema de ficheiros pode ser visto como um conjunto contíguo de
blocos em que se destacam três regiões principais: o superblock
(a que corresponde o bloco 0), a FAT (a que correspondem os
blocos seguintes, começando no 1), e a região para dados propriamente
dita (a que correspondem os restantes blocos).
- O superblock serve para guardar informação geral sobre o
sistema de ficheiros. Considere a seguinte estrutura para o
superblock:
#define CHECK_NUMBER 2004
typedef struct superblock_entry {
int check_number; // número que permite identificar o sistema de ficheiros como válido
int block_size; // tamanho de cada bloco do sistema {256, 512(default) ou 1024 bytes}
int fat_type; // tipo de FAT {8, 10(default) ou 12}
int root_block; // número do primeiro bloco a que corresponde o directório raíz
int free_block; // número do primeiro bloco da lista de blocos não utilizados
} superblock;
|
- A FAT (file allocation table) é um conjunto contíguo de
entradas, numeradas de 0 até 2^fat_type-1, que permitem
referenciar os blocos de dados livres e os blocos de dados
utilizados por cada ficheiro/directório. Através do valor de
free_block é possível aceder ao primeiro bloco de dados
não utilizado. Para percorrer a lista completa dos blocos não
utilizados deve seguir-se a referência guardada na entrada FAT de
igual ordem. Um valor de -1 numa entrada FAT marca o fim da
lista.
- Os blocos de dados (data blocks) são utilizados para
guardar os dados dos ficheiros e dos directórios. O número de
blocos de dados é igual ao número de entradas na FAT, e cada
bloco de dados corresponde à entrada na FAT de igual ordem. À
semelhança dos blocos não utilizados, os blocos de dados
utilizados por um ficheiro/directório são mantidos através de
uma lista na FAT. Um ficheiro não é nada mais do que um conjunto
de blocos de dados. A FAT especifica quais os blocos de dados
utilizados pelo ficheiro e a ordem dos blocos no ficheiro é a
ordem representada na FAT. A implementação de directórios é de
certa forma idêntica à dos ficheiros, a diferença reside no
facto dos blocos de dados para directórios seguirem um formato
predefinido. Um bloco de dados para um directório, pode ser
visto como um array de estruturas de dados do tipo que se segue,
em que cada uma dessas estruturas corresponde a um
ficheiro/subdirectório do directório em causa.
#define TYPE_DIR 'D'
#define TYPE_FILE 'F'
#define TYPE_FREE 'X'
#define MAX_NAME_LENGHT 23
typedef struct directory_entry {
char type; // tipo da entrada {TYPE_DIR, TYPE_FILE, TYPE_FREE}
char name[MAX_NAME_LENGHT]; // nome da entrada
int size; // tamanho em bytes (0 se TYPE_DIR)
int first_block; // primeiro bloco de dados
} dir_entry;
|
Como simplificação, vamos considerar que cada entrada na FAT é sempre
representada por um inteiro (4 bytes). Sendo assim o número de blocos
necessários para guardar a FAT é igual a
2^fat_type*4/block_size. Como o número de blocos de
dados deverá ser igual ao número de entradas na FAT, o número de
blocos total num sistema de ficheiros resulta da fórmula
1+2^fat_type*4/block_size+2^fat_type.
Multiplicando o número de blocos por block_size obtemos o
tamanho do sistema de ficheiros.
A emulação dos sistemas de ficheiros será feita sobre ficheiros comuns
estruturados segundo a organização descrita. Sendo assim, ao iniciar o
emulador do sistema de gestão de ficheiros (virtual_fs)
deverá indicar-se como argumento o ficheiro sobre o qual o emulador
deverá funcionar. Exemplo: virtual_fs discoC. Se o ficheiro
não corresponder a um sistema de ficheiros válido (verificar o
check_number e se o tamanho do ficheiro está de acordo com o
block_size e o fat_type) é reportado um erro e o
emulador deve terminar.
Para iniciar um novo sistema de ficheiros, deverá indicar-se o nome de
um novo ficheiro seguido da informação relativa ao tamanho de cada
bloco (opção -b seguido do tamanho em bytes: 256, 512 ou 1024) e ao
tipo de FAT (opção -f seguido do tipo: 8, 10 ou 12). Exemplo:
virtual_fs -b1024 -f12 discoC. O código que implementa a
formatação do sistema de ficheiros pode ser obtido aqui.
Etapas do Trabalho
O utilizador deve poder comunicar com o emulador do sistema de gestão
de ficheiros através de uma linha de comandos onde poderão ser
invocados uma série de utilitários para manipulação de ficheiros e
directórios.
Etapa 1: Manipulação de directórios
Nesta 1ª etapa pretende-se que implemente os utilitários para
manipulação de directórios. Segue-se uma breve descrição de cada um
deles:
- mkdir dir - cria um subdirectório dir no
directório actual
- rmdir dir - remove o subdirectório dir (se
vazio) do directório actual
- cd dir - move o directório actual para dir
- pwd - escreve o caminho absoluto do directório
actual
- ls - lista o conteúdo do directório actual
Note que a criação de um novo directório, implica desde logo, a
criação de duas entradas, uma para o directório corrente "."
e outra para o directório pai "..". O primeiro bloco
associado ao directório raíz "/" é definido pelo campo
root_block do superblock. Para todos os utilitários,
considere apenas os casos em que o argumento dir é o
directório corrente (.), o directório pai (..), ou um subdirectório do
directório actual. Para todos os outros casos, reporte um erro
apropriado (ou seja, não considere o uso de caminhos como
my_dir_1/.../my_dir_n/my_fich).
Etapa 2: Manipulação de ficheiros
Nesta 2ª etapa pretende-se que implemente os utilitários para
manipulação de ficheiros. Segue-se uma breve descrição de cada um
deles:
- get fich1 fich2 - copia um ficheiro normal UNIX
fich1 para um ficheiro no nosso sistema fich2
- put fich1 fich2 - copia um ficheiro do nosso sistema
fich1 para um ficheiro normal UNIX fich2
- cp fich1 fich2 - copia o ficheiro fich1
para fich2
- cp fich dir - copia o ficheiro fich para o
subdirectório dir
- mv fich1 fich2 - move o ficheiro fich1 para
fich2
- mv fich dir - move o ficheiro fich para o
subdirectório dir
- rm fich - remove o ficheiro fich
- cat fich - escreve para o ecrã o conteúdo do
ficheiro fich
Tal como na etapa anterior, não considere o uso de caminhos no
argumento dir.
Etapa Bónus: Desfragmentar o sistema de ficheiros
O criar, copiar e apagar de ficheiros e directórios, com o decorrer do
tempo, leva a que o sistema de ficheiros comece a ficar fragmentado,
isto é, os blocos de dados utilizados para representar
ficheiros/directórios deixam de poder ser contíguos e passam a
situar-se dispersos e intercalados no conjunto total dos blocos
disponíveis.
Nesta etapa pretende-se que implemente um procedimento defrag
que permita desfragmentar o sistema de ficheiros. O procedimento deve
reorganizar o conjunto de blocos de dados por forma a garantir que os
ficheiros e subdirectórios de um dado directório e que cada ficheiro
ou subdirectório particular, fiquem representados em blocos de dados
contíguos. O procedimento deve imprimir uma listagem dos blocos de
dados utilizados por cada um dos ficheiros/directórios antes e depois
de executar o processo de desfragmentação do sistema de ficheiros.