Sistemas de Operação
Trabalho Prático 3
Ano Lectivo de 2002/2003
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 em UNIX. Mais concretamente, inclui o desenho da estrutura
de dados para organização do sistema de ficheiros, 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.
Etapas do Trabalho
O trabalho está estruturado por etapas para simplificar a sua execução.
Etapa 1: Estruturação do sistema de ficheiros
Nesta 1ª etapa pretende-se que desenhe o conjunto das estruturas de
dados de suporte à organização do sistema de ficheiros e que
implemente um procedimento format que permita definir e
formatar novos sistemas. Para tal, considere a organização que se
segue:
O sistema de ficheiros pode ser visto como um conjunto contíguo de
blocos de disco em que se destacam três regiões principais: o
superblock (a que corresponde o bloco 0), a região dos
inodes (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. Considere a seguinte estrutura para o
superblock:
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 {1, 2(default) ou 4 Kbytes}
int num_inodes; // o número de inodes no sistema de ficheiros
int root_inode; // o numero do inode a que corresponde o directório root
int free_inode; // o número do primeiro inode da lista de inodes não utilizados
int free_block; // o número do primeiro bloco da lista de blocos de dados não utilizados
} superblock;
- Os inodes servem para representar os ficheiros e os
directórios do sistema. Considere a seguinte estrutura para os
inodes:
#define N_DIRECT_BLOCKS 5
#define TYPE_FREE 0
#define TYPE_FILE 1
#define TYPE_DIR 2
typedef struct inode_entry {
int type; // o tipo do inode {TYPE_FILE, TYPE_DIR, TYPE_FREE}
int size_free; // tamanho em bytes do ficheiro (se TYPE_FILE)
// tamanho em bytes do directório (se TYPE_DIR)
// próximo inode não utilizado (se TYPE_FREE)
int direct_block[N_DIRECT_BLOCKS]; // índices dos blocos onde estão guardados os dados
int indirect_block; // índice do bloco de índices para outros blocos
} inode;
Os inodes são numerados de 0 até num_inodes - 1.
Através do valor de free_inode é possível aceder ao
primeiro inode não utilizado. Para percorrer a lista
completa dos inodes não utilizados deve seguir-se a
referência size_free do inode anterior. Um valor
de -1 em size_free marca o fim da lista.
- Os blocos de dados (data blocks) podem ser utilizados
para guardar os dados dos ficheiros, os dados dos directórios,
ou para albergarem blocos de índices para outros blocos
(indirect blocks). À semelhança dos inodes, os
blocos de dados não utilizados são mantidos através de uma
lista. Através do valor de free_block é possível
aceder ao primeiro bloco não utilizado. A primeira posição de um
bloco não utilizado guarda o índice para o próximo bloco não
utilizado; um valor de -1 marca o último bloco não utilizado.
Como cada bloco de dados deve poder ser representado por um
inode, o número total de inodes deve ser igual ao número
total de blocos de dados. Se o espaço necessário para representar um
inode é INODE_SIZE (32 bytes no caso da estrutura apresentada
acima) então em cada bloco é possível representar
BLOCK_SIZE/INODE_SIZE inodes (INODES_PER_BLOCK). Como
consequência, o número de blocos de dados deve ser múltiplo de
INODES_PER_BLOCK. Deste modo, o número de blocos total num sistema de
ficheiros (N_BLOCKS) resulta da fórmula 1+(INODES_PER_BLOCK+1)*N para
N>0, e o tamanho do sistema de ficheiros resulta da fórmula
N_BLOCKS*BLOCK_SIZE.
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 (sugestão de nome:
virtual_fs) deverá indicar 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 o block_size do
superblock) deve ser reportado um erro e o emulador deve
terminar.
Para iniciar um novo sistema de ficheiros, deverá indicar o
nome de um novo ficheiro seguido da informação relativa ao tamanho de
cada BLOCK_SIZE (opção -b seguido do tamanho em Kbytes: 1, 2 ou 4)
e ao tamanho mínimo do sistema de ficheiros (opção -s seguido do
tamanho em Kbytes). Exemplo: virtual_fs -b2 -s2000
discoC. Como 2000 Kbytes não é um tamanho válido para um sistema
de ficheiros com blocos de 2 Kbytes, já que não existe nenhum N tal
que 2*(1+(32+1)*N) seja igual a 2000, esse tamanho deve ser
arredondado para o primeiro N que resulte num valor maior que
2000. Para o exemplo em causa, o tamanho do novo sistema de ficheiros
deveria ser 2048 Kbytes, já que para N = 30, 2*(1+33*N) é igual a
1982, e para N = 31, 2*(1+33*N) é igual a 2048.
Esta etapa encontra-se parcialmente implementada aqui. Para a completar apenas necessita de escrever
o código que inicia as estruturas de dados de novos sistemas (ver
função my_format).
Etapa 2: I/O para manipulação dos blocos de dados
De forma a manipular os blocos de dados do sistema de ficheiros
implemente os seguintes procedimentos:
- char *lseek_block(int block_number);
- void read_block(int block_number, char *buf);
- void write_block(int block_number_, char *buf);
O procedimento lseek_block devolve o apontador para o início
do bloco de dados a que corresponde block_number. O
procedimento read_block escreve para buf o conteúdo
do bloco de dados a que corresponde block_number. O
procedimento write_block escreve o conteúdo de buf
para o bloco de dados a que corresponde block_number. Note
que o tamanho de buf deve ser igual a BLOCK_SIZE.
Etapa 3: Utilitários para manipulação de directórios
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.
Um ficheiro não é nada mais do que um conjunto de blocos de dados que
podem ser escritos e lidos. Cada ficheiro corresponde a um
inode que especifica quais os blocos de dados utilizados pelo
ficheiro. A ordem dos blocos no ficheiro é a ordem representada no
inode. Quando o tamanho do ficheiro excede N_DIRECT_BLOCKS
blocos de dados, utiliza-se um bloco de dados auxiliar para
representar os restantes blocos de dados necessários para o
ficheiro. O campo indirect_block da estrutura dos
inodes guarda o índice do bloco de índices para outros blocos.
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
seguinte tipo:
#define MAX_NAME_LENGHT 60
typedef struct directory_entry {
int inode; // inode associado ao ficheiro/subdirectório
char name[MAX_NAME_LENGHT]; // nome do ficheiro/subdirectório
} dir_entry;
Cada uma destas estruturas corresponde a um ficheiro/subdirectório do
directório em causa. O campo name guarda o nome do
ficheiro/subdirectório, enquanto o campo inode guarda a
referência do inode que representa o ficheiro/subdirectório.
Nesta etapa, pretende-se que implemente os utilitários para
manipulação de directórios. Segue-se uma breve descrição de cada um
deles:
- my_mkdir dir - cria um subdirectório dir no
directório actual
- my_rmdir dir - remove o subdirectório dir (se
vazio) do directório actual
- my_cd dir - move o directório actual para dir
- my_pwd - escreve o caminho absoluto do directório
actual
- my_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 inode associado
ao directório root "/" é definido pelo campo
root_inode 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 4: Utilitários para manipulação de ficheiros
Nesta etapa, pretende-se que implemente os utilitários para
manipulação de ficheiros. Segue-se uma breve descrição de cada um
deles:
- my_get fich1 fich2 - copia um ficheiro normal UNIX
fich1 para um ficheiro no nosso sistema fich2
- my_put fich1 fich2 - copia um ficheiro do nosso sistema
fich1 para um ficheiro normal UNIX fich2
- my_cp fich1 fich2 - copia o ficheiro fich1
para fich2
- my_cp fich dir - copia o ficheiro fich para o
subdirectório dir
- my_mv fich1 fich2 - move o ficheiro fich1 para
fich2
- my_mv fich dir - move o ficheiro fich para o
subdirectório dir
- my_rm fich - remove o ficheiro fich
- my_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.
Scripts de Teste
Carregue aqui para obter um conjunto de
scripts de teste. Para executar os scripts (ficheiros
'script_dir?' e 'script_file?') são necessárias duas condições:
- O emulador do sistema de gestão de ficheiros deverá ter o nome
'virtual_fs'
- O comando 'exit' deverá permitir terminar o emulador
Cada um dos scripts testa funcionalidades diferentes do sistema
de gestão de ficheiros. No início de cada ficheiro de script
descreve-se o output que é esperado obter com a sua execução.
Prazos
O trabalho deve ser entregue via web até
1 de Junho de 2003, sendo a sua demonstração feita posteriormente em
horário a marcar.