Sistemas Operacionais I

Gerência de Armazenamento: Implementação do Sistema de Arquivos

Prof. Alexandre Duarte : http://alexandrend.comCentro de Informática | Universidade Federal da Paraíba

Estes slides são baseados no material que acompanha o livro Operating Systems Concepts de Silberschatz, Galvin and Gagne

Objetivos

Descrever os detalhes de implementação de um sistema de arquivos e de estruturas de diretórios locais

Discutir alocação de blocos e de gerência de blocos livres

Estrutura do Sistema de Arquivos Estrutura de arquivo

Unidade de armazenamento lógico Coleção de informações relacionadas

Sistema residente em armazenamento secundário

Organizados em camadas Bloco de controle de arquivos –

estrutura de armazenamento com todas as informações a respeito de um arquivo

Sistema de arquivos em camada

Exemplo de bloco de controle de arquivos

Estrutura do sistema de arquivos em memória

Sistemas de arquivos virtuais Sistemas de arquivo virtuais (VFS) fornecem

uma visão orientada a objetos para implementação de sistemas de arquivos

VFS permitem que a mesma interface de chamada de sistemas seja utilizada por diferentes tipos de sistemas de arquivos.

A API se comunica com o VFS ao invés de acessar diretamente o sistema de arquivos específico.

Visão esquemática do sistema de arquivos virtual

Implementação de Diretório

Lista linear de nomes de arquivos com ponteiros para blocos de dados. Fácil de programar Consome muito tempo de execução

Tabela Hash – lista linear com estrutura de hash Diminui o tempo de busca ao diretório

Requer tratamento de colisões Tamanho fixo

Métodos de alocação

Um método de alocação se refere a forma como blocos livres são alocados para arquivos:

Alocação contígua

Alocação encadeada

Alocação indexada

Alocação contígua

Cada arquivo ocupa um conjunto de blocos contíguos no disco

Vantagens Simplicidade – requer saber apenas o bloco inicial e

comprimento (número de blocos) Permite acesso aleatório Bom desempenho

Desvantagens Problemas com alocação de espaço Arquivos não podem crescer!

Quem usa VM/CMS da IBM

Alocação contígua

Sistemas baseadas em extensão Alguns sistemas de arquivos modernos

usam uma modificação do esquema de alocação contígua Sistemas de arquivos baseados em extensões

alocam blocos de disco em porções denominadas extensões

Uma extensão é uma porção contígua de blocos de disco Um arquivo consiste de uma ou mais extensões

Ainda é suscetível a problemas de fragmentação interna e externa!

Alocação encadeada

Cada arquivo é uma lista encadeada de blocos

Vantagens Simplicidade – requer apenas o endereço inicial Gerência de espaço livre – não há fragmentação

externa Desvantagens

Não permite acesso aleatório Menor confiabilidade

Utilizado, com algumas variações, pelo File-allocation table (FAT) do MS-DOS

Alocação encadeada

File-Allocation Table (FAT)

Alocação indexada

Mantém todos os ponteiros de um arquivo em um bloco de índice

Vantagens Permite acesso aleatório Acesso dinâmico sem fragmentação mas

com overhead do índice Desvantagens

Desperdício de espaço com arquivos com poucos blocos

Quem usa: Unix File System

Alocação indexada

Gerência de espaço livre

Mapa de bits (n blocos)

Facilita a obtenção de espaço livre contíguo Requer espaço adicional

Disco de 1TB com blocos de 4KB = 32 MB Disco de 1PB com blocos de 4KB = 32 GB

…

0 1 2 n-1

bit[i] = 0 bloco[i] livre

1 bloco[i] ocupado

Gerência de espaço livre

Lista ligada (lista de livres) Mais difícil de conseguir espaço contiguo Diminui o desperdício de espaço

Variações Agrupamento: primeiro bloco livre possui

número de n blocos livres Contagem: lista de sequencias contiguas

de blocos livres

Lista encadeada de blocos livres

Eficiência e desempenho

Eficiência depende de: Algoritmos para alocação de disco e de

diretórios Exemplo: pré-alocação

Tipos de dados mantidos nas entradas de diretório

Desempenho Cache de buffer – seção separada de memória

para blocos usados frequentemente Cache de página – armazena dados de arquivos

utilizando técnicas de memória virtual free-behind and read-ahead – técnicas para otimizar

acesso sequencial

Cache de páginas

Uma cache páginas armazena páginas ao invés de blocos de disco utilizando técnicas de memória virtual

Entrada/saída mapeadas em memória utiliza uma cache de páginas

Entrada/saída padrão pelo sistema de arquivos usa o cache de buffer de disco

E/S sem cache unificada

E/S com cache unificada

Recuperação

Verificação de consistência – compara os dados na estrutura de diretórios com os dados nos blocos de disco e tenta corrigir inconsistências

Utilizar programas de sistema para fazer backup do disco em um outro dispositivo de armazenamento

Recuperar um arquivo pedido restaurando-o do backup

Sistema de arquivos estruturado em log Sistema de arquivos estruturado em log

consideram todas as atualizações de arquivos como transações

Todas as transações são gravadas em um log O commit de uma transação ocorre quando ela é gravada

no log No entanto, após o commit o arquivo pode ainda não ter

sido atualizado As transações no log são executadas de forma

assíncrona no sistema de arquivos Quando o arquivo é modificado a transação é removida do

log Se o sistema de arquivos trava, todas as transações

no log deverão ser executadas após a recuperação