Sistemas Operacionais

Aula 18: Sistema de Arquivos -- Implementação

Referências:

Capítulo 11

Visão Lógica X Implementação

O que é um arquivo ?

O usuário enxerga uma coleção de dados;
O sistema enxerga trilhas, setores e cilindros.

Alocação de Espaço em Disco

Gerência de espaço em disco se parece com o que ?

Gerência de memória, claro.

Só que aqui a otimizar o espaço utilizado é mais importante do que otimizar o tempo de acesso.

Três métodos básicos existem:

Alocação contígua;
Alocação encadeada;
Alocação indexada;

Alocação Contígua

Same old, same old stuff...

Vantagens:

Simples de implementar e fácil de acessar o arquivo;
Rápido acesso;

Desvantagens:

Fragmentação; como aumentar um arquivo ?

Solução:

Defrag/Compactação. Pode ser usado aqui porque o tempo não é tão crítico. Mas mesmo assim atrapalha.

Não é muito usado.

Alocação Encadeada

O arquivo passa a ser uma lista encadeada de blocos:

Exemplo: Pick System -- lista duplamente encadeada

Vantagens ?
Desvantagens ?

Alocação Encadeada

Vantagens:

Sem fragmentação;
Simples de aumentar um arquivo, assim como criar e apagar;

Desvantagens:

E acessos não sequenciais ?
Confiabilidade. E se um link se perder ?
- No sistema Pick isto se chamava GFE -- Group Format Error.
- Se ao chegar no trabalho pela manha houvesse um GFE na tela podia-se saber que o dia inteiro estava perdido em uma caçada de links...

Alocação Encadeada -- FAT

E se a gente guardar a lista encadeada separada ?

Vantagens:

Diminui a probabilidade de erros

Desvantagens:

É preciso cache a FAT -- eficiência;
Usado no DOS, causa má impressão.

Alocação Indexada

E se a lista encadeada for ``compactada'' ?

Diferenças:

Uma FAT para todos os arquivos;
Um índice por arquivo.

Acesso é mais eficiente que FAT ? Direto ou sequencial ?

Alocação Indexada

Problema: Usa-se ao menos um índice inteiro, mesmo que o arquivo use só um bloco.

Qual o tamanho ideal de índice ?

Muito grande, desperdicio;
Muito pequeno, não cabe arquivos grandes.
Mas na verdade o tamanho ideal é um bloco de disco.

E ai ?

Alocação Indexada

Solução:

Usar uma lista encadeada de índices.

Uma FAT de índices ? IAT ?

Índices multiníveis: usar índices de índices.
Solução BSD Unix (misto):

Alocação Indexada

Unix inode:

Fragmentação

Fragmentação externa foi resolvida com alocação encadeada e indexada. Mas e fragmentação interna ?

Depende do tamanho do bloco de dados
Por exemplo, com alocação encadeada o tamanho da FAT é inversamente proporcional ao tamanho do bloco.
Com alocação indexada isto não é problema: não é preciso manter um índice do disco todo.
- Por exemplo, no BSD Unix o bloco é de 4K.

Implementação de Diretórios

Dado um nome de arquivo temos que achar seu ``inode'' (ou equivalente). Problema básico de busca em tabelas:

Lista linear
- Fácil de implementar;
- Difícil de usar
Tabela de hash
- Mais eficiente.

Gerência de Espaço Livre

Várias opções existem:

Bitmaps: Pode-se guardar um bitmap do disco aonde o bit 1 significa que o bloco correspondente está livre.

Problema: Tem que ser ``cached'', mas ocupa muito espaço na memória.

Lista encadeada: Não ocupa espaço, mas é ``meio'' ineficiente para acessos não sequenciais.

Só que o acesso à lista de blocos livres é sequencial.

Sistema de Arquivos de Linux/Unix

Ponto inicial: um superbloco que contém informações tais como tamanho do bloco, número de blocos, lista de inodes, etc.

Replicado no disco, porque se o superblock não puder ser lido o sistema todo fica inacessível.
Usa um conjunto de grupos de blocos aonde cada grupo de blocos é um mini sistema de arquivos:

Motivo: tentar manter descrição e dados próximos.

Sistema de Arquivos de Linux/Unix

No Unix, inodes são pré-alocados e espalhados no disco:

Aumenta a performance

No Linux, os grupos de blocos fazem um papel semelhante

Sistema de Arquivos de Linux/Unix

Diretórios no Linux:

Lista encadeada de nomes/inodes: