Please enable JavaScript.
Coggle requires JavaScript to display documents.
Implementação do Sistema de Arquivos/2 - Coggle Diagram
Implementação do Sistema de Arquivos/2
Implementação de Diretórios
Lista linear
nomes de arquivos com ponteiro para os blocos de dados
Simples de programar mas demorado para executar
Criar novo arquivo
pesquisar diretório para assegurar nome
exclusivo
adicionar nova entrada ao final do diretório
Excluir arquivo
Pesquisa pelo nome seguido de liberação do espaço alocado
Tabela de Dispersão (Tabela Hash)
lista linear com estrutura de dados em hash
toma um valor calculado a partir do nome do
arquivo e retorna um ponteiro para o nome do arquivo na lista linear
Diminui tempo de busca de diretório. Inserção e exclusão também são mais simples
tem que administrar colisões, situações onde dois nomes de arquivos referem-se ao mesmo local
Métodos de Alocação
Alocação Contígua
armazenar um arquivo em blocos sequencialmente dispostos
sistema localiza um arquivo através do endereço do primeiro bloco e da sua
extensão em blocos
O acesso é bastante simples
Seu principal problema é a alocação de novos arquivos nos espaços livres
armazenar um arquivo que ocupa n blocos, é necessário uma cadeia com n blocos dispostos sequencialmente no disco
fragmentação externa
Operações de “compactação”, mas geralmente requerem que o sistema esteja offline
determinar o espaço necessário a um arquivo que possa se estender depois da sua criação
Pré-alocação, superestimando o tamanho (fragmentação interna). É ineficiente
Possibilidade: alocação contígua com blocos de extensão (um segmento aponta para o próximo)
Alocação Encadeada
Resolve os problemas da alocação contígua
Cada arquivo é uma lista encadeada de blocos de disco; os blocos de disco podem estar
espalhados em qualquer local no disco
O diretório contém um ponteiro para o primeiro e o último blocos do arquivo
Cada bloco contém um ponteiro para o próximo bloco. O usuário não enxerga esses ponteiros.
Não há fragmentação externa propriamente dita
Porém, o arquivo em si pode ficar espalhado
no disco
Uma operação de desfragmentação pode ajudar por um tempo
Desvantagens
É muito ineficiente em acesso direto
já que é preciso percorrer bloco a bloco, seguindo os ponteiros
Desperdício de espaço nos blocos com armazenamento de ponteiros
A confiabilidade é problemática
Alocação Encadeada usando Tabela de Alocação de Arquivos
Método simples, antigo, mas eficiente
Uma seção de disco no começo de cada volume é reservada para conter a tabela
A tabela tem uma entrada para cada bloco do disco e é indexada pelo número do bloco
A FAT é usada de maneira semelhante a uma lista encadeada
A alocação de um novo bloco a um arquivo é uma simples questão de encontrar a
primeira entrada na tabela com valor 0
substituir o valor anterior de fim de
arquivo pelo endereço do novo bloco. O 0 é então substituído pelo valor de fim de
arquivo
Vantagem
Tempo de acesso aleatório é melhorado
Alocação Indexada
A alocação indexada melhora o acesso direto
ao colocar todos os ponteiros de um
arquivo juntos em uma locação: o bloco de índices
Cada arquivo tem seu próprio bloco de índices, que é um array de
endereços de blocos de disco
O diretório contém o endereço do bloco de índices
Para encontrar e ler o i-ésimo bloco, usamos o ponteiro na i-ésima
entrada do bloco de índices
Desempenho
depende muito de como o sistema será usado
Muito acesso sequencial
Muito acesso aleatório
Gerenciamento do Espaço Livre
lista de espaços livres
A lista de espaços livres registra todos os blocos de disco livres
aqueles não alocados a algum arquivo ou diretório
Para criar um arquivo, pesquisamos a lista de espaços livres
Quando um arquivo é excluído, seu espaço em disco é adicionado à lista de espaços livres
Métodos Básicos
Vetor de bits
Para cada bloco
1 = livre
0 = ocupado
Vantagens: Simplicidade e eficiência
Desvantagem: o mapa inteiro precisa ser mantido da memória por questões de eficiência
Lista Encadeada
Recuperação
Sistemas de Arquivos Estruturados em Log
Todas as alterações de metadados são gravadas sequencialmente em um log
Cada conjunto de operações para execução de uma tarefa específica é uma transação
Uma vez que as alterações sejam gravadas nesse log, elas são consideradas como
confirmadas
Se o sistema cair, o arquivo de log conterá zero ou mais transações