Sistemas Operacionais - Implementação do Sistema de Arquivos PDF

Sistemas Operacionais Implementação do Sistema de Arquivos Professor Calebe Conceição Nas últimas aulas vimos Como a interface do sistema de arquivos é apresentada para o usuário final e como a gerenciamos em ambiente Unix/Linux Na aula de hoje descreveremos...

Sistemas Operacionais Implementação do Sistema de Arquivos Professor Calebe Conceição Nas últimas aulas vimos Como a interface do sistema de arquivos é apresentada para o usuário final e como a gerenciamos em ambiente Unix/Linux Na aula de hoje descreveremos em mais detalhes a implementação do sistema de arquivos locais e da estrutura de diretórios Daremos uma olhada na implementação dos sistemas de arquivo remotos Discutiremos os algoritmos de alocação e liberação de blocos, e suas compensações  Aprofunde-se no livro texto! Comece a ler o capítulo 10. Implementação do Sistema de Arquivos Contextualização Estrutura do Sistema de Arquivos Estrutura de arquivos Unidade lógica de armazenamento Coleção de informações relacionadas O sistema de arquivos reside no armazenamento secundário Provê uma interface de usuário para o armazenamento mapeamento lógico->físico Provê acesso conveniente e eficiente ao disco, facilita o armazenamento e busca de informações O disco provê reescrita in-loco e acesso aleatório As operações de E/S para transferências são realizadas em blocos de setores (normalmente 512 bytes) File Control Block (Bloco de Controle do Arquivo) - estrutura que guarda informações sobre um arquivo O driver de dispositivo controla um dispositivo físico O sistema de arquivos é organizado em camadas Sistema de arquivos em camadas  Camadas do Sistema de Arquivo Device drivers gerenciam as operações E/S na camada de I/O Control A partir de comandos como read drive1, cylinder 72, track 2, sector 10, into memory location 1060 gera como saída mandos de baixo nível específicos do controlador de hardware No basic file system, dado um comando simples como retrieve block 123 é traduzido para o device driver. Também gerencia buffer de memória e caches (alocação, liberação e substituição) Buffers guardam os dados em trânsito Caches guardam dados usados frequentemente O file-organization module entende arquivos, endereços lógicos, e blocos físicos. Traduz bloco lógico para bloco físico Gerencia espaço livre, e alocação de disco.  Camadas do Sistema de Arquivo O logical file system gerencia informações de metadados: traduz nome de arquivo para número de arquivo, manipulador de arquivo, localização de arquivo pelo gerenciamento do file control block (inodes no Unix) gerencia os diretórios proteção As camadas são úteis para reduzir a complexidade e redundância, mas adiciona sobrecarga e diminui o desempenho. As camadas lógicas podem ser implementadas por qualquer método de codificação escolhido pelo projetista do SO Há muitos sistemas de arquivos, algumas vezes no mesmo sistema operacional. Cada um com seus próprios formatos Há “novos” surgindo - ZFS, GoogleFS*, Oracle ASM, FUSE *já foi substituído pelo Colossus Implementação do Sistema de Arquivos Nós temos as chamadas de sistema no nível de API, mas como implementamos suas funções? Considerando as estruturas em disco e em memória Boot Control Block - contém informações necessárias pelo sistema para inicializar o SO a partir daquele volume. Necessário se o volume contém um SO, normalmente fica no primeiro bloco do volume. Volume Control Block (superblock, master file table) - contém detalhes do volume Número total de blocos, blocos livres, tamanho do bloco, ponteiros para blocos livres ou arrays. A estrutura de diretórios organiza os arquivos FCB (File Control Block) por arquivo contém muitos detalhes sobre o arquivo Número inode, permissões, tamanho, datas O NTFS guarda na master file table, usando uma estrutura de BD relacional. Um Bloco de Controle de Arquivo Típico Estruturas do sistema de arquivos na memória A tabela de montagem guarda os sistemas de arquivos, pontos de montagem e os tipos de arquivo As estruturas do sistema de arquivo necessárias e providas pelo SO são: Abrindo um arquivo Estruturas do sistema de arquivos na memória A tabela de montagem guarda os sistemas de arquivos, pontos de montagem e os tipos de arquivo As estruturas do sistema de arquivo necessárias e providas pelo SO são: Lendo um arquivo Estruturas do sistema de arquivos na memória A tabela de montagem guarda os sistemas de arquivos, pontos de montagem e os tipos de arquivo As estruturas do sistema de arquivo necessárias e providas pelo SO são: Abrindo um arquivo Lendo um arquivo Além disso, bufferes mantêm blocos de dados do armazenamento secundário A abertura retorna um manipulador de arquivo (file handler) para uso subsequente Dados da leitura são eventualmente copiados para os endereços de memória dos processos do usuário Partições e Montagens Partições podem ser um volume contendo um sistema de arquivo preparado ou raw → apenas uma sequência de blocos sem sistemas de arquivo. O bloco de boot pode apontar para um volume ou um conjunto de blocos do carregador de boot que contém código suficiente para saber como carregar o kernel do sistema operacional. Já ouviram falar da MBR? Ou ainda pode apontar para o programa de gerenciamento de boot multi SO (LILO, GRUB) A partição root contém o SO, outras partições podem ter outros SOs, outros sistemas de arquivo, ou podem ser raw Montada em tempo de boot Outras partições podem ser montadas automaticamente ou manualmente No momento da montagem, a consistência do sistema de arquivos é checada Todos os metadados estão corretos? Se não estão, corrija e tente novamente Se estão, adicione à tabela de montagem e permita o acesso Sistemas de Arquivos Virtuais Sistemas de Arquivos Virtuais (VFS) no UNIX provêem uma maneira Orientada a Objetos de implementar sistemas de arquivos VFS permitem a mesma chamada de sistema (a API) para ser usada nos diferentes tipos de sistemas de arquivos Separa operações genéricas dos sistemas de arquivo dos detalhes de implementação A implementação pode relacionar uma de muitos tipos de sistemas de arquivos, ou sistemas de arquivos em rede Implementa vnodes que guardam inodes ou detalhes de arquivos em rede E então dispara a operação que adequa as rotinas da implementação do sistema de arquivos A API é para a interface do VFS, e não para algum tipo específico de sistema de arquivo. Implementação de Sistemas de Arquivos Virtuais Por exemplo, Linux tem 4 tipos de objetos inode → Cada arquivo ou diretório tem um inode único dentro de uma partição. O sistema operacional utiliza o número do inode para acessar as informações e o conteúdo de um arquivo ou diretório. file → representa uma abstração de um arquivo aberto no kernel. superblock → estrutura de dados que contém informações gerais sobre um sistema de arquivos específico. dentry → (Directory Entry), é um objeto que representa uma entrada de diretório. Associa o nome de um arquivo ou diretório ao seu inode. Não contém informações sobre o próprio arquivo, mas sim sobre sua localização na árvore de diretórios. VFS define um conjunto de operações sobre os objetos que devem ser implementadas Cada objeto tem um ponteiro para uma tabela de função A tabela de funções tem endereços de rotinas para implementar aquela função naquele objeto Implementação de Diretórios Lista Linear de nome de arquivos com ponteiros para o bloco de dados Simples de programar Lento para executar Tempo de busca linear Pode ser mantido em ordem alfabética por lista encadeada, ou usar árvore B+ Tabela hash - lista linear com uma estrutura de dados Hash Diminui o tempo de busca de arquivos Colisões - situação em que a dois nomes de arquivos tem hash para a mesma localização Somente útil quando as entradas são de tamanho fixo, ou quando usa um método de overflow encadeado. Métodos de Alocação - Contígua Diz respeito a como os discos são alocados para armazenar os arquivos: Alocação contígua - cada arquivo ocupa um conjunto de blocos contíguos Melhor para desempenho na maioria dos casos Simples – somente a localização inicial (número do bloco) e comprimento são necessários Os problemas incluem encontrar espaço para o arquivo, saber o tamanho do arquivo, fragmentação externa, necessidade de compactação off-line (no tempo ocioso), ou on-line. Na prática, dividimos o endereço lógico por 512. O Quociente (Q) é o bloco acessado. O Resto (R) é o deslocamento dentro do bloco. Métodos de Alocação - Linked Alocação por linkagem - cada arquivo é uma lista encadeada de blocos. O arquivo termina em nil Não há fragmentação externa Cada bloco tem um ponteiro pro próximo bloco Sem necessidade de compactação ou desfragmentação externa O sistema de liberação de espaço é chamado quando um novo bloco é necessário Melhora a eficiência pelo agrupamento de blocos Confiabilidade pode ser um problema A localização de um arquivo pode demandar muitos I/Os e posicionamentos de disco O bloco a ser Variação FAT (File Allocation Table) acessado é o Q- ésimo bloco na O começo do volume tem uma tabela, lista encadeada indexada pelo número do bloco de blocos que Se assemelha à uma lista encadeada, representam o porém mais rápida no disco e facilita o uso arquivo. O de cache deslocamento O procedimento de alocação de um novo no bloco é R+1. bloco é facilitado Métodos de Alocação - Linked Métodos de Alocação - Indexed Cada arquivo tem seu próprio bloco contendo uma tabela de índice com ponteiros para seus blocos. Visão Lógica: Precisa de uma tabela de índice Acesso aleatório Acesso dinâmico sem fragmentação externa, mas tem o overhead da tabela de índice A tabela de índice ocupa só um bloco. Métodos de Alocação - Indexed O esquema é semelhante ao de paginação, discutido no capítulo 7. Para permitir arquivos grandes podemos encadear vários blocos de índices Quando um arquivo é criado, todos os ponteiros do bloco de índices apontam para nil À medida que novos blocos vão sendo alocados pelo gerenciador de espaço livre, seu endereço é adicionado à primeira posição livre. Qual o tamanho do bloco de índices, já que todo arquivo deverá ter um? Esquema encadeado → a última posição do bloco de índices aponta para um outro bloco, para arquivos muito grandes, ou para nil se suficiente. Esquema multinível → usa de 2 a 4 níveis de blocos, até encontrar o endereço correto do bloco (como no esquema de paginação) Esquema combinado → os primeiros endereços apontam para blocos diretos, os demais para blocos indiretos em diversos níveis, conforme demanda. Mais no livro! Esquema combinado: Unix UFS 4K bytes por bloco, 32 bits de endereço Gerenciamento de espaço livre O sistema de arquivo mantém uma lista de espaços livres para registrar blocos de disco que não estão sendo utilizados por nenhum arquivo. Implementado como um vetor de bits (ou mapa de bits). Essa abordagem facilita o encontro do primeiro bloco livre (ou os primeiros n blocos livres) no disco. Gerenciamento de espaço livre Mapa de bits requer espaço extra. Exemplo: tamanho do bloco = 4KB = 212 bytes tamanho do disco = 240 bytes (1 TB) n = 240 / 212 = 228 (256 MB) Se registramos clusters com 4 blocos → 64MB de memória Usando listas encadeadas: Não é fácil de encontrar espaços contíguos Porém sem desperdício de espaço Não precisa de atravessar a lista completa (se guardarmos também o número de blocos) Gerenciamento de espaço livre Agrupamento Modifica a lista encadeada para armazenar a lista de endereços dos próximos n-1 blocos livres no primeiro bloco livre, junto com um ponteiro para o próximo bloco que contém ponteiros para blocos livres. Contagem Como os espaços são alocados normalmente de forma contígua, também assim são liberados Guarda o endereço do primeiro bloco e a contagem dos próximos A lista de espaços livre contém entradas com endereços e tamanhos Mapa de Espaços -> leia no livro, seção 10.5.5 Eficiência e Desempenho Eficiência vai depender de: Alocação de disco e algoritmos de diretório Tipos de dados mantidos nas entradas dos diretórios de arquivo A estrutura de alocação de metadados: se prévia ou sob demanda Estruturas de dados de tamanho fixo ou variável Desempenho vai depender de: Manter dados e metadados juntos Uso de cache On-board O uso de escritas síncronas, demandadas pelo SO ou alguns apps Sem buffering/cache → as escritas demandam confirmação de disco Assíncrona → forma mais comum de escrita, mais rápida e pode usar o buffer Uso de técnicas de otimização do acesso sequencial: free-behind, read-ahead Contraintuitivamente, operações de leitura podem ser mais lentas que de escrita! Eficiência e Desempenho Eficiência vai depender de: Alocação de disco e algoritmos de diretório Tipos de dados mantidos nas entradas dos diretórios de arquivo A estrutura de alocação de metadados: se prévia ou sob demanda Estruturas de dados de tamanho fixo ou variável Desempenho vai depender de: Manter dados e metadados juntos Uso de cache On-board O uso de escritas síncronas, demandadas pelo SO ou alguns apps Sem buffering/cache → as escritas demandam confirmação de disco Assíncrona → forma mais comum de escrita, mais rápida e pode usar o buffer Uso de técnicas de otimização do acesso sequencial: free-behind, read-ahead Contraintuitivamente, operações de leitura podem ser mais lentas que de escrita! Recuperação Checagem de Consistência → Compara os dados na estrutura de diretórios com os blocos de dados no disco, e tenta ajustar inconsistências Pode ser lento e às vezes falha. fsck no Unix, ou o chkdsk no Windows. Usa programas de sistemas para fazer backup de dados para outra mídia de armazenamento (fita magnética, outro disco magnético, disco ótico…) Recupera um arquivo perdido ou disco inteiro restaurando o dado a partir do backup. Há ainda abordagens que fazem uso de registros em log, e as operações específicas são registradas em transações. Só após serem confirmadas passam a ter efeito. Hora-Trabalho de Hoje Leia o capítulo 10, seções 10.1 a 10.4.  Referências SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais, princípios básicos. LTC, 2013. Dúvidas? Na próxima aula… Estrutura do Armazenamento de Massa. Não falte! 😉 Obrigado pela atenção