❧ Sistemas de Arquivos e Entrada/Saída ❧

Introdução10.1

Hoje veremos como o sistema operacional transforma blocos crus de armazenamento e dispositivos lentos em uma interface que parece simples: arquivos, diretórios, read, write, open, close e operações de entrada e saída.

Na aula anterior, vimos que a memória virtual cria uma ilusão poderosa. Cada processo acredita ter um espaço grande, contínuo e privado, mesmo que a RAM real seja limitada e compartilhada. Agora aparece um problema diferente. A memória do processo desaparece quando o processo termina, mas muitos dados precisam sobreviver por dias, meses ou anos.

O problema central desta aula é este: como armazenar informações de forma persistente, encontrável, compartilhável e eficiente, mesmo quando o hardware real só entende blocos, controladores, interrupções e erros?

Esta aula usa como base o Tanenbaum, capítulo 4, seções 4.1 a 4.4, e capítulo 5, seções 5.1 a 5.3. A progressão será: primeiro veremos a interface de arquivos e diretórios, depois como essa interface é implementada no disco, em seguida como o sistema tenta manter consistência e desempenho, e por fim como tudo isso depende do subsistema de E/S.

Arquivos como abstração persistente10.2

Um arquivo é uma unidade lógica de informação criada por processos e gerenciada pelo sistema operacional. Ele permite guardar dados em um dispositivo de armazenamento sem obrigar o programa a lidar diretamente com cilindros, setores, blocos físicos, controladores ou temporização de hardware.

Essa abstração atende a três necessidades que a memória principal não resolve sozinha.

Do ponto de vista de quem programa, o arquivo parece um objeto com nome, conteúdo e operações. Do ponto de vista do sistema operacional, ele também tem metadados, blocos associados, permissões e relação com algum diretório.

Nomes, extensões e tipos10.2.1

Quando um processo cria um arquivo, ele dá um nome a esse arquivo. Depois que o processo termina, o arquivo pode continuar existindo e ser acessado por outros processos usando esse nome.

As regras exatas variam entre sistemas. Alguns distinguem maiúsculas e minúsculas, como UNIX e Linux. Outros historicamente não distinguiam, como MS-DOS. Muitos sistemas usam extensões, como .c, .txt, .jpg e .pdf, para indicar uma convenção sobre o conteúdo do arquivo.

Há uma diferença importante aqui. Em sistemas como UNIX, a extensão costuma ser convenção. Um arquivo chamado dados.txt não é magicamente obrigado pelo kernel a conter texto. Já em ambientes gráficos, como Windows, a extensão frequentemente é usada para escolher qual programa será aberto quando o usuário clica no arquivo.

Estrutura interna dos arquivos10.2.2

Tanenbaum apresenta três formas clássicas de enxergar a estrutura de um arquivo.

A opção mais flexível é a sequência de bytes. Nesse modelo, o sistema operacional enxerga o arquivo como uma sequência linear de bytes numerados: byte 0, byte 1, byte 2, e assim por diante. Ele não tenta entender se esses bytes representam texto, imagem, banco de dados, vídeo ou código executável. Essa decisão fica para os programas de usuário.

Na sequência de registros, o sistema operacional já reconhece uma unidade lógica maior que o byte: o registro. Em vez de apenas ler "os próximos 200 bytes", o programa pode ler "o próximo registro". Isso fazia sentido em sistemas nos quais arquivos eram compostos por entradas de tamanho fixo ou por registros com estrutura conhecida, como cadastros comerciais. A diferença para a sequência de bytes é que, nesse modelo, o sistema sabe que existem fronteiras entre registros; no modelo de bytes, essas fronteiras só existem se o programa decidir interpretá-las.

Na árvore de registros, a organização vai além da ordem linear. Cada registro possui uma chave, e o arquivo é estruturado para permitir busca por essa chave. Em vez de percorrer registros em sequência até encontrar um cliente, por exemplo, o sistema pode navegar por uma árvore e localizar diretamente o registro desejado. A diferença para a sequência de registros é que a sequência preserva uma ordem simples de leitura, enquanto a árvore adiciona uma estrutura de busca dentro do próprio arquivo.

Essa flexibilidade da sequência de bytes é uma vantagem porque permite usos inesperados. O sistema não precisa ser alterado toda vez que surge um novo formato de arquivo. A desvantagem é que o sistema também ajuda menos. Se um programa interpreta bytes errados como se fossem uma imagem ou um executável, o erro precisa ser tratado em outro nível.

Acesso sequencial e acesso aleatório10.2.3

Os primeiros sistemas operacionais ofereciam principalmente acesso sequencial. O processo lia o arquivo em ordem, do início para o fim. Essa ideia combinava bem com fitas magnéticas, nas quais avançar até uma posição distante era naturalmente caro.

Com discos, passou a ser possível acessar partes diferentes do arquivo fora de ordem. Esse é o acesso aleatório. Ele é essencial para bancos de dados, sistemas de reservas, índices e qualquer aplicação que precise saltar diretamente para um registro específico.

Em sistemas como UNIX e Windows, o acesso aleatório costuma aparecer por meio de uma operação como seek, que altera a posição atual do arquivo. Depois disso, as próximas leituras ou escritas partem da nova posição.

Atributos e operações10.2.4

Além do conteúdo, arquivos têm atributos. Esses atributos são metadados, ou seja, informações sobre o arquivo.

As operações mais comuns são create, delete, open, close, read, write, append, seek, get attributes, set attributes e rename.

open merece atenção. Abrir um arquivo não significa necessariamente ler seus dados naquele instante. Significa preparar o sistema para acessos futuros. O sistema localiza o arquivo, carrega metadados relevantes, cria uma entrada interna e devolve ao processo um descritor de arquivo.

abrir entrada.txt para leitura
criar saida.txt para escrita
enquanto houver bytes na entrada:
    ler um bloco da entrada
    escrever esse bloco na saída
fechar os dois arquivos

Diretórios transformam nomes em localização10.3

Um sistema com milhares de arquivos não pode deixar tudo em uma única lista plana. Diretórios organizam nomes e permitem agrupar arquivos relacionados.

Tecnicamente, um diretório é uma estrutura gerenciada pelo sistema de arquivos que associa nomes a informações necessárias para localizar o arquivo. Dependendo do sistema, essa informação pode ser o primeiro bloco do arquivo, um conjunto de atributos ou o número de um i-node.

Diretórios hierárquicos10.3.1

Sistemas modernos usam diretórios hierárquicos, formando uma árvore. Isso permite que cada usuário, aplicação ou projeto tenha sua própria organização interna.

Em uma árvore de diretórios, um arquivo pode ser identificado por um caminho absoluto ou relativo.

O diretório de trabalho é o ponto de referência usado por caminhos relativos. Se o diretório atual é /usr/ast, então caixapostal e /usr/ast/caixapostal apontam para o mesmo arquivo.

Dois nomes especiais aparecem em muitos sistemas.

Assim, se o diretório atual é /usr/ast, o caminho ../lib/dictionary sobe para /usr e depois desce para /usr/lib/dictionary.

Operações com diretórios10.3.2

As operações com diretórios lembram operações com arquivos, mas o objetivo é gerenciar nomes e organização.

Em UNIX, remover um arquivo é conceitualmente remover uma ligação entre um nome de diretório e o arquivo. Por isso a operação se chama unlink.

Links rígidos e simbólicos10.3.3

Quando um arquivo precisa aparecer em mais de um lugar, o sistema pode usar links.

Links rígidos tornam o sistema de arquivos mais parecido com um grafo acíclico do que com uma árvore pura. Isso aumenta a flexibilidade, mas também exige mais cuidado em contagem de referências, backups e remoção.

Como arquivos são implementados no disco10.4

Até agora olhamos o sistema de arquivos pelo lado de quem usa. Agora precisamos olhar pelo lado de quem implementa.

O disco pode ser visto, de forma simplificada, como uma sequência de blocos. O sistema de arquivos precisa responder perguntas como estas:

1. Quais blocos pertencem a cada arquivo?
2. Quais blocos estão livres?
3. Onde ficam os metadados?
4. Como encontrar o diretório-raiz?
5. Como recuperar o sistema após uma queda?

Esquema geral de uma partição10.4.1

Tanenbaum mostra um esquema típico com MBR, bloco de inicialização, superbloco, informação de espaço livre, i-nodes, diretório-raiz e dados.

O superbloco é especialmente importante. Se ele for perdido ou corrompido, o sistema pode perder informações essenciais para interpretar o restante da partição.

Alocação contígua10.4.2

Na alocação contígua, cada arquivo ocupa uma sequência contínua de blocos no disco.

Essa técnica tem duas vantagens claras. Primeiro, é simples. Para localizar o arquivo, basta saber o bloco inicial e o tamanho. Segundo, a leitura sequencial é rápida, porque os blocos estão juntos.

O problema aparece quando arquivos são removidos e criados ao longo do tempo. Surgem lacunas. Um arquivo novo pode não caber em nenhuma lacuna, mesmo que o espaço livre total seja suficiente. Esse é o problema da fragmentação externa.

Além disso, a alocação contígua exige saber antecipadamente o tamanho final do arquivo, ou mover o arquivo quando ele cresce. Para arquivos que mudam constantemente, isso é ruim. Para mídias gravadas de uma vez, como CD-ROMs, a ideia volta a fazer sentido.

Lista encadeada e FAT10.4.3

Outra opção é armazenar o arquivo como uma lista encadeada de blocos. Cada bloco aponta para o próximo. Isso elimina a exigência de blocos contíguos.

A lista encadeada simples tem um problema grave para acesso aleatório. Para chegar ao bloco $n$, é preciso começar no primeiro bloco e seguir ponteiro por ponteiro.

A FAT, File Allocation Table, melhora isso colocando os ponteiros em uma tabela global do sistema de arquivos. Essa tabela tem uma entrada para cada bloco do disco. Se o bloco $4$ aponta para o bloco $7$, essa informação fica na entrada $4$ da FAT. Assim, o encadeamento pode ser seguido sem ler cada bloco de dados no disco. O custo é que a tabela cresce com o tamanho do disco e precisa ficar disponível na memória para funcionar bem.

I-nodes10.4.4

Em sistemas baseados em i-nodes, cada arquivo possui sua própria estrutura de metadados. Essa estrutura guarda atributos do arquivo e os endereços dos blocos que pertencem a ele. Ou seja, em vez de uma tabela global dizer qual é o próximo bloco de todos os arquivos do disco, cada arquivo carrega o seu próprio mapa de blocos.

A vantagem é que o sistema precisa carregar apenas os i-nodes dos arquivos em uso. Se um processo abre três arquivos, o sistema trabalha principalmente com os i-nodes desses três arquivos. Em uma FAT, a estrutura importante é a tabela global do disco, que cresce com o número total de blocos, mesmo que poucos arquivos estejam abertos.

O i-node pode conter alguns ponteiros diretos para blocos de dados e, quando o arquivo cresce, ponteiros para blocos de ponteiros adicionais. Assim, arquivos pequenos são baratos e arquivos grandes continuam possíveis.

Implementando diretórios10.4.5

Um diretório precisa mapear nomes para a informação que localiza o arquivo.

Há duas estratégias comuns.

Com nomes longos e variáveis, há outro problema. Se cada entrada reservar espaço para 255 caracteres, a maioria desperdiçará espaço. Por isso, sistemas reais podem usar entradas de tamanho variável, armazenar nomes em uma área separada ou usar estruturas de busca para acelerar diretórios grandes.

Diretórios pequenos podem ser pesquisados linearmente. Diretórios com milhares de arquivos podem usar tabelas de espalhamento ou caches de busca.

Gerenciamento de espaço em disco10.5

Depois de decidir como representar arquivos, o sistema precisa decidir como dividir e reutilizar o espaço livre.

Tamanho de bloco10.5.1

Quase todos os sistemas dividem arquivos em blocos de tamanho fixo. O tamanho do bloco é uma decisão de projeto importante.

Esse é um conflito clássico entre espaço e tempo. Blocos pequenos economizam espaço, mas podem piorar desempenho. Blocos grandes melhoram transferência, mas aumentam fragmentação interna.

Lista livre e mapa de bits10.5.2

Para reutilizar espaço, o sistema precisa saber quais blocos estão livres.

O mapa de bits costuma ser mais compacto. Um disco com $n$ blocos precisa de $n$ bits. Já uma lista precisa guardar números de blocos, normalmente com vários bytes por entrada.

Também é possível gerenciar cotas. Em sistemas multiusuário, uma cota limita quantos blocos ou arquivos cada usuário pode consumir. Isso evita que um usuário use todo o disco e prejudique os demais.

Confiabilidade e journaling10.6

Sistemas de arquivos precisam ser rápidos, mas também precisam sobreviver a falhas. O problema é que muitas operações conceitualmente simples exigem várias escritas reais no disco.

Remover um arquivo em um sistema parecido com UNIX pode exigir pelo menos três ações:

1. Remover a entrada do diretório.
2. Liberar o i-node.
3. Liberar os blocos de dados.

Se o sistema cai depois da primeira ação, o arquivo deixa de aparecer no diretório, mas seus blocos podem continuar marcados como ocupados. Se cai depois de liberar blocos, mas antes de remover a entrada do diretório, uma entrada válida pode apontar para blocos que o sistema acredita estarem livres. Isso pode causar corrupção séria.

Verificação de consistência10.6.1

Ferramentas como fsck examinam redundâncias do sistema de arquivos para encontrar inconsistências.

A verificação pode encontrar blocos desaparecidos, blocos duplicados na lista livre e blocos de dados atribuídos a mais de um arquivo. Alguns problemas desperdiçam espaço. Outros podem destruir dados se não forem tratados.

Essa estratégia funciona, mas pode ser lenta em discos grandes, porque precisa varrer muitas estruturas.

O papel do journaling10.6.2

Um sistema de arquivos com journaling registra no diário o que pretende fazer antes de modificar as estruturas principais. Se o sistema cair no meio da operação, ao reiniciar ele consulta o diário e completa ou desfaz a operação de forma controlada.

transação: remover temp.log
ação 1: remover entrada do diretório
ação 2: liberar i-node k
ação 3: marcar blocos b1, b2, b3 como livres

Para que essa ideia funcione bem, as operações registradas precisam ser idempotentes. Uma operação idempotente pode ser repetida sem mudar o resultado além da primeira execução. Marcar o bloco $n$ como livre é idempotente se repetir essa marcação não adiciona o mesmo bloco duas vezes a uma lista.

Desempenho do sistema de arquivos10.7

Disco é muito mais lento que memória. Mesmo quando a taxa de transferência parece alta, há latência de busca, rotação, fila e controlador. Por isso sistemas de arquivos usam várias otimizações.

Cache de blocos10.7.1

A cache de blocos mantém em RAM blocos que logicamente pertencem ao disco.

Quando um processo lê um bloco, o sistema verifica se ele já está na cache. Se estiver, a leitura é atendida sem acesso ao disco. Se não estiver, o bloco é lido do disco e guardado para acessos futuros.

Algoritmos como LRU podem ser usados para decidir quais blocos remover da cache, mas sistemas de arquivos têm uma preocupação extra. Blocos de metadados, como i-nodes, diretórios e mapas de espaço livre, são críticos para consistência. Se ficam sujos na cache e o sistema cai antes de gravá-los, o sistema de arquivos pode ficar inconsistente.

Por isso, a política de cache não é apenas desempenho. Ela também precisa considerar risco.

Leitura antecipada10.7.2

Se o sistema percebe que um arquivo está sendo lido sequencialmente, pode carregar o próximo bloco antes que ele seja pedido. Essa técnica é chamada de leitura antecipada.

Ela ajuda quando o padrão é previsível, como ler um vídeo ou percorrer um arquivo grande. Ela atrapalha quando o acesso é aleatório, porque pode ocupar largura de banda e cache com blocos que não serão usados.

Localidade e desfragmentação10.7.3

Outra otimização é colocar blocos relacionados próximos uns dos outros. Se blocos de um mesmo arquivo ficam próximos, o braço do disco se move menos e a leitura sequencial melhora.

Com o tempo, arquivos podem ficar fragmentados. A desfragmentação tenta mover blocos para tornar arquivos e espaço livre mais contíguos.

Entrada e saída: o caminho até o hardware10.8

O sistema de arquivos depende de E/S. Para ler um bloco, ele precisa conversar com camadas mais baixas que sabem lidar com controladores, interrupções, DMA e dispositivos reais.

Dispositivos de bloco e de caractere10.8.1

Tanenbaum divide dispositivos de E/S em duas categorias principais.

Essa classificação não é perfeita. Relógios e telas de toque não se encaixam tão bem. Ainda assim, ela é útil porque o sistema de arquivos normalmente conversa com dispositivos de bloco abstratos.

Controladores de dispositivos10.8.2

Um dispositivo geralmente tem uma parte mecânica ou física e uma parte eletrônica. A parte eletrônica é o controlador. O sistema operacional não conversa diretamente com cada detalhe do hardware físico. Ele escreve e lê registradores do controlador.

Esses registradores permitem enviar comandos, consultar estado e transferir dados. Por exemplo, o sistema pode perguntar se o dispositivo está pronto, mandar iniciar uma leitura ou verificar se houve erro.

E/S mapeada em memória10.8.3

Há duas formas clássicas de acessar registradores de dispositivos.

Na E/S mapeada em memória, um driver pode acessar registradores como se fossem posições especiais de memória. Isso simplifica a programação, mas exige cuidado com cache. Colocar registradores de dispositivo em cache seria perigoso, porque o software poderia ler um valor antigo e nunca perceber que o dispositivo mudou de estado.

E/S programada, interrupções e DMA10.8.4

Há três maneiras principais de executar E/S do ponto de vista do sistema operacional.

No DMA, a CPU programa o controlador de DMA com endereço, tamanho e direção da transferência. Depois, o controlador move dados entre o dispositivo e a memória. A CPU só precisa ser interrompida quando a transferência termina.

Camadas do software de E/S10.9

O software de E/S costuma ser organizado em camadas. Cada camada esconde detalhes da camada inferior e oferece uma interface mais regular para a camada superior.

Essa separação é essencial para a independência de dispositivo. Um programa que chama read não deveria precisar saber se os dados vêm de um SSD, de um HD, de um pendrive ou de um sistema de arquivos remoto.

Drivers10.9.1

Drivers contêm o conhecimento específico de cada dispositivo ou classe de dispositivos. Um driver de disco entende blocos, filas, controladores, erros e comandos do dispositivo. Um driver de teclado entende eventos de teclas.

Drivers podem ser carregados dinamicamente. Isso é importante em sistemas modernos, nos quais dispositivos são adicionados e removidos com frequência.

Um bom sistema operacional tenta padronizar a interface com os drivers. Assim, o restante do kernel não precisa ser reescrito para cada dispositivo novo.

Software independente de dispositivo10.9.2

Essa camada cuida de funções comuns:

1. nomeação uniforme,
2. proteção,
3. utilização de buffers,
4. relatório de erros,
5. alocação e liberação de dispositivos dedicados,
6. tamanho de bloco lógico independente do dispositivo.

No UNIX, dispositivos podem aparecer como arquivos especiais em /dev. Isso permite aplicar mecanismos de nomeação e proteção parecidos com os usados para arquivos comuns.

Buffers e spooling10.9.3

Buffers suavizam diferenças de velocidade entre produtor e consumidor. Um dispositivo pode produzir dados em uma taxa diferente daquela em que o processo consegue consumi-los. O sistema usa buffers para desacoplar esses ritmos.

Spooling é usado quando um dispositivo dedicado, como uma impressora, não deve ser entregue diretamente a qualquer processo. Em vez disso, processos colocam trabalhos em um diretório de spool, e um daemon autorizado envia esses trabalhos ao dispositivo em ordem.

Questões10.10

Próximos passos10.11

Vimos como arquivos, diretórios, alocação de blocos, journaling, cache e camadas de E/S se conectam. Na próxima aula, a continuação natural é olhar com mais detalhe para dispositivos específicos, especialmente discos, algoritmos de escalonamento de disco, tratamento de erros e armazenamento estável.