Unidade H 2 - Sistema de arquivos (alocação)

Alocação de arquivos

O sistema de arquivos pode fazer a organização dos setores lógicos de várias formas, cada qual com suas vantagens/desvantagens, que irão impactar no desempenho e forma de funcionamento do sistema de arquivo. Evidentemente, alguns métodos de alocação não são utilizados comercialmente, enquanto outros se aproximam bastante dos métodos de alocação nestes sistemas.

Alocação contígua

Neste método, os blocos lógicos do arquivo ocupam uma conjunto de blocos físicos no disco – uma área contígua. A figura H.3 mostra o esquema de alocação, supondo que cada bloco físico disponibilize 4KB de espaço. No disco hipotético apresentado, há 3 arquivos e seus descritores de arquivo simplificados são:

Descritor de ARQ1 inicio = 3; fim = 6;	Descritor de ARQ2 inicio = 8; fim = 10;
Descritor de ARQ3 inicio = 11; fim = 12;

 

Observa-se que os arquivos ocupam blocos físicos do disco em sequencia, por outro lado, se ARQ2 precisar aumentar de tamanho, não há blocos contíguos disponíveis. Em outras palavras, temos espaço em disco disponível, mas não podemos alocar para ARQ2. Uma solução seria reorganizar todos (ou parte) dos arquivos para que o espaço disponível passe a ficar contíguo.

Vantagens

• simplicidade para implementação;
• velocidade na busca de todos os blocos do arquivo;

Desvantagens

• inviabiliza/dificulta o crescimento do arquivo.

Alocação encadeada

Para resolver o problema do crescimento de arquivos, precisa-se de um mecanismo que facilite este crescimento. Para isto, utiliza-se uma estrutura de dados em que o cada bloco sabe o endereço do próximo bloco do arquivo. A figura H.4 procura demonstrar este recurso. No disco hipotético apresentado, há 3 arquivos e seus descritores de arquivo simplificados são:

Descritor de ARQ1 inicio = 3; fim = 6;	Descritor de ARQ2 inicio = 8; fim = 4;
Descritor de ARQ3 inicio = 11; fim = 3;

 

Cada bloco físico reserva uma parte de seu espaço para registrar o endereço do próximo bloco, por exemplo 4 bytes. Desta forma, o arquivo não cresce de forma contígua, o que pode ser observado em ARQ2, que está “espalhado” pelo disco. Além disso, o bloco descritor não aponta mais o fim do arquivo e sim seu tamanho.

O último bloco de cada arquivo aponta para um endereço chave -1 (que no caso indica fim do arquivo).

Vantagens

• permite o crescimento do arquivo;
• velocidade na busca de todos os blocos do arquivo;

Desvantagens

• “perde” espaço em disco para fazer o encadeamento - para blocos de 4 Kbytes, utilizando 4 bytes de cada bloco, perde-se 0,1% do espaço em disco para este controle.
• NÃO permite acesso relativo – para acessar o bloco 4 de ARQ2, precisamos percorrer todo o arquivo – o que é um problema para arquivos grandes;

Alocação indexada

A alocação indexada permite o crescimento do arquivo além de permitir o acesso relativo. Neste sistema, a lista de blocos ocupados pelo arquivo é transferida para dentro do descritor de arquivo, onde uma lista indexada é criada e armazena os endereços do próximo bloco. A figura H.5 procura demonstrar este esquema.  No disco hipotético apresentado, há 2 arquivos, que são ARQ1 e ARQ2.

Cada descritor de arquivo possui uma tabela indexada que registra o endereço do próximo bloco do arquivo, permitindo por exemplo buscarmos diretamente ; desta forma, podemos permitir o crescimento do arquivo e também acessar qualquer registro do arquivo diretamente.
         No entanto, o crescimento do arquivo é limitado ao tamanho da tabela de índices, que no caso da figura H.5, poderemos endereçar 10 blocos de 4KB cada, o que nos permite um arquivo de tamanho máximo de 40KBytes (que é um tamanho de arquivo bem limitado).

        

Para permitir arquivos maiores, teríamos que ter uma tabela de índices maior  - por exemplo para arquivos de 2GBytes precisamos de uma tabela com 500.000¹ índices, o que irá consumir muita memória (já que os descritores de arquivos ficam carregados na memória).

Vantagens

• permite o crescimento do arquivo;
• permite acesso relativo;

Desvantagens

• crescimento de arquivo é limitado ao tamanho da tabela de índices;

Alocação com níveis de indireção na indexação.

Para resolver o problema do crescimento de arquivos, adota-se níveis de indireção na tabela de indexação. O método de localização fica muito parecido com o método de indexação convencional. A figura H.6 procura representar o mecanismo².

No descritor de arquivos, que agora contem 11 índices, os 10 primeiros índices são apontadores diretos, ou seja, apontam blocos os blocos físicos do arquivo diretamente – o que permite um arquivo de até 40KB³. Para permitir o crescimento do arquivo, utiliza-se o índice de número 10 aponta para um bloco físico no disco (no caso bloco 18) que por sua vez funciona como um indexador.

Como cada bloco físico contém 4KB e um cada indexador ocupa 4bytes, podemos ter em um bloco físico 1024 índices. Verifica-se que o bloco 18 está apontando para 1024 blocos físicos (não é possível desenhar isto); o que nos permite aumentar nosso arquivo para 4,2MBytes.

 

Considerando que 1KB = 1024B então 4KB = 4096bytes o valor exato disponibilizado é: (4096 x 10 índices diretos) + (1024 índices indiretos x 4096) = 4235264 bytes que arredondando dá 4MBytes

 

E se precisarmos de um arquivo maior, usamos dois níveis de indireção (apontador duplamente indireto, que no caso, irá apontar para 1024 APONTADORES de 1024 blocos físicos de 4KB. Isto permite ao arquivo atingir 4,2GBytes.

 

Considerando que 1KB = 1024B então 4KB = 4096bytes o valor exato disponibilizado com apontador duplamente indexado é: (4096 x 10 índices diretos) + (1024 índices indiretos x 4096) + (1024 x (1024 índices indiretos x 4096))= 4299202560 bytes, que arredondando dá 4GBytes

 

E se ainda assim, nosso arquivo precisar aumentar de tamanho, lançamos uso do apontador triplamente indexado, que aponta para 1024 APONTADORES, onde cada um apontam para 1024 outros APONTADORES, que por sua vez apontam para 1024 blocos físicos de 4K. Isto permite ao arquivo atingir 4,4TBytes – o que, para os padrões atuais, é considerado um arquivo bem grande.

 

Considerando que 1KB = 1024B então 4KB = 4096bytes o valor exato disponibilizado com apontador duplamente indexado é: (4096 x 10 índices diretos) + (1024 índices indiretos x 4096) + (1024 x (1024 índices indiretos x 4096)) + (1024 x (1024 x (1024 índices indiretos x 4096))) = 4402345713664 bytes, que arredondando dá 4,4 TBytes