Oppsett for test

A implementa¸c˜ao f´ısica de um sistema de arquivos representa a forma com que efetivamente os dados s˜ao tratados nos dispositivos de armazenamento, isto ´e, corresponde a organiza¸c˜ao f´ısica dos dados nestes dispositivos e como se d˜ao as opera¸c˜oes de armazenamento e recupera¸c˜ao destes dados. Con- forme Tanenbaum:

Usu´arios est˜ao preocupados em como os arquivos s˜ao denomina- dos, quais opera¸c˜oes s˜ao permitidas, a aparˆencia da estrutura de diret´orios e quest˜oes relacionadas a interface. Os implementado- res est˜ao interessados em como arquivos e diret´orios s˜ao arma- zenados, como o espa¸co em disco ´e gerenciado e como fazer que tudo funcione de forma eficiente e confi´avel [TAN92, p. 162].

Como indicado por Deitel [DEI92, p. 394] e Tanenbaum [DEI92, p. 162], os arquivos podem ser armazenados basicamente de duas formas, ou seja, atrav´es da:

5.5. SISTEMAS DE ARQUIVOS 187

Figura 5.26: Gerenciador de arquivos do MS-Windows XP • Aloca¸c˜ao cont´ıgua e

• Aloca¸c˜ao n˜ao cont´ıgua.

O projeto de um sistema de arquivos exige o conhecimento de v´arias informa¸c˜oes, entre elas: o tipo e n´umero de usu´arios; caracter´ısticas das aplica¸c˜oes que ser˜ao utilizadas; quantidade, tamanho e opera¸c˜oes sobre ar- quivos. A considera¸c˜ao destes fatores permite determinar qual a melhor forma de organiza¸c˜ao de seus arquivos e diret´orios.

Aloca¸c˜ao cont´ıgua

Uma forma de organizar-se os arquivos fisicamente ´e atrav´es da armazena- gem dos dados em ´areas adjacentes dos dispositivos f´ısicos, isto ´e, em setores consecutivos das unidades de disco [SG00, p. 373]. Sistemas de arquivos im- plementados desta forma s˜ao denominados de aloca¸c˜ao cont´ıgua ou cont´ınua e neles o armazenamento f´ısico corresponde `a organiza¸c˜ao l´ogica do arquivo, ou seja, o primeiro bloco de dados ocupa o primeiro setor alocado e assim sucessivamente (vide Figura 5.27).

Este ´e o esquema mais simples de organiza¸c˜ao f´ısica de arquivos que exibe algumas vantagens e desvantagens [DEI92, p. 395] [DEI92, p. 163]. As vantagens s˜ao:

• o controle de armazenamento do arquivo, isto ´e, a manuten¸c˜ao de diret´orios, se reduz ao tamanho do arquivo e ao setor inicial utilizado e

Figura 5.27: Organiza¸c˜ao f´ısica na aloca¸c˜ao cont´ıgua

• as opera¸c˜oes de leitura e escrita s˜ao as mais eficientes poss´ıveis para qualquer tipo de dispositivo.

Enquanto que as desvantagens s˜ao:

• exige que o tamanho do arquivo seja conhecido no instante de sua cria¸c˜ao e

• a ocorrˆencia de fragmenta¸c˜ao (veja discuss˜ao na se¸c˜ao5.5.6) reduz a capacidade efetiva de armazenamento, pois novos arquivos s´o podem ser criados em ´areas cont´ıguas.

Sistemas que exigem maior performance nas opera¸c˜oes de leitura e escrita e que n˜ao necessitem de modifica¸c˜oes freq¨uentes no tamanho de seus arquivos podem utilizar eficientemente este esquema de aloca¸c˜ao, tal como o sistema operacional IBM Vm/CMS.

Aloca¸c˜ao n˜ao cont´ıgua

A outra forma poss´ıvel de organizar-se fisicamente o armazenamento de arquivos ´e atrav´es da aloca¸c˜ao n˜ao cont´ıgua. Neste esquema cada bloco do arquivo pode estar armazenado num setor distinto da unidade de disco, de forma que o armazenamento f´ısico n˜ao corresponde `a organiza¸c˜ao l´ogica do arquivo, como mostra a Figura 5.28.

O principal objetivo da aloca¸c˜ao n˜ao-cont´ıgua ´e proporcionar um meca- nismo mais apropriado para o armazenamento de arquivos que tendem a ter seus tamanhos aumentados ou diminu´ıdos conforme s˜ao utilizados.

A aloca¸c˜ao n˜ao-cont´ıgua pode ser implementada de v´arias formas e den- tre estas as estrat´egias de aloca¸c˜ao orientadas `a setores:

• Lista ligada de setores

5.5. SISTEMAS DE ARQUIVOS 189

Figura 5.28: Organiza¸c˜ao f´ısica na aloca¸c˜ao n˜ao cont´ıgua • Indexa¸c˜ao de n´os (i-nodes)

Na lista ligada de setores (linked list allocation) cada setor do disco contˆem um ponteiro que pode ser utilizado para indicar um outro setor [SG00, p. 376]. Desta forma uma arquivo pode ser armazenado atrav´es de uma entrada simples no diret´orio que indica o primeiro de uma seq¨uˆencia de setores, onde cada um destes setores aponta para o pr´oximo. Um ponteiro com valor nulo indica que o arquivo terminou (vide Figura 5.29). N˜ao existe necessidade dos setores alocados estarem em posi¸c˜oes adjacentes tal como na aloca¸c˜ao cont´ıgua. O sistema pode manter uma lista de setores livres, que podem ser retirados para a cria¸c˜ao e aumento de arquivos ou recuperados quando diminuem ou s˜ao eliminados. Isto permite um mecanismo de arma- zenamento que acomoda facilmente as varia¸c˜oes de tamanho dos arquivos, usando integralmente a capacidade do disco, eliminando a necessidade de mecanismos de compacta¸c˜ao embora promova a fragmenta¸c˜ao da unidade de disco.

Figura 5.29: Aloca¸c˜ao n˜ao cont´ıgua com lista ligada

Conforme Tanenbaum [TAN92, p. 163] os maiores problemas encontra- dos no uso do mecanismo de uma lista ligada de setores s˜ao:

1. As opera¸c˜oes de leitura e escrita tendem a ser ineficientes devido a fragmenta¸c˜ao inerente deste m´etodo.

2. O acesso randˆomico deixa de existir pois torna-se necess´ario ler cada setor alocado para se determinar o pr´oximo at´e a posi¸c˜ao desejada. 3. O posicionamento do ponteiro dentro de cada setor faz com que o bloco

de dados deixe de ser uma potˆencia de 2, criando alguns inconvenientes do ponto de vista de programa¸c˜ao.

A lista ligada de setores indexada utiliza o mesmo princ´ıpio de ar- mazenamento de setores interligados eliminando o inconveniente associado ao ponteiro existente em cada setor. ´E criada uma tabela contendo a rela¸c˜ao de todos os setores do dispositivos sendo que para cada entrada se associa um ponteiro (retirado dos setores de dados). A entrada do diret´orio corres- pondente ao arquivo aponta para um setor desta tabela (o primeiro setor do arquivo) que tem associado um ponteiro para a pr´oxima entrada e as- sim sucessivamente. Um ponteiro nulo indica o fim do arquivo na tabela. Isto permite o acesso randˆomico do arquivo e mantˆem o bloco de dados do setor num tamanho que ´e potˆencia de 2, embora a ineficiˆencia devido a fragmenta¸c˜ao permane¸ca. Temos uma representa¸c˜ao deste esquema de organiza¸c˜ao na Figura 5.30.

Figura 5.30: Aloca¸c˜ao n˜ao cont´ıgua com lista ligada indexada A principal desvantagem deste m´etodo ´e o tamanho que da tabela de aloca¸c˜ao pode ter em unidades de grande capacidade, por exemplo, uma

5.5. SISTEMAS DE ARQUIVOS 191 unidade de 1.2 Gbytes dividida em setores de 1 Kbytes possui uma tabela de aloca¸c˜ao com mais de um milh˜ao de entradas, que pode consumir espa¸co precioso para ser mantida integralmente em mem´oria, pois cada entrada da tabela tipicamente utiliza 3 ou 4 bytes dependendo de como se d´a a otimiza¸c˜ao do sistema [TAN92, p. 164].

O DOS e Windows utilizam esta estrat´egia para a organiza¸c˜ao f´ısica de floppies e unidades de disco. A tabela de setores ´e chamada de Tabela de Aloca¸c˜ao de Arquivos (file allocation table) que d´a origem ao nome do sistema de arquivos FAT. Na FAT o registro inicial armazena informa¸c˜oes sobre a pr´opria unidade, existindo valores especiais para designa¸c˜ao de fim de arquivo e setores defeituosos [NOR89, p. 112].

A numera¸c˜ao associada ao nome FAT, como FAT12, FAT16 e FAT32, indica o n´umero de bits utilizado para numera¸c˜ao dos setores, representando assim a quantidade m´axima de setores que pode ser controlada, ou seja, 12 bits permitem endere¸car 4.096 setores, 16 bits endere¸cam 64K setores e 32 bits possibilitam 4G setores distintos. Isto exibe outra fraqueza desta estrat´egia, uma unidade de 1.2 GBytes de capacidade possuir´a setores de 512K (307,2K) e 32K (19,2K) com FAT de 12 e 16 bits respectivamente, o que ´e um inconveniente devido a granularidade excessivamente grossa (um arquivo de 1 byte ocupa sempre um setor).

Outra forma comum de organiza¸c˜ao de arquivos ´e atrav´es da indexa¸c˜ao de n´os (index nodes ou i-nodes). Um n´o indexado ´e uma pequena estrutura de dados que contˆem um conjunto de atributos e umas poucas centenas de entradas onde cada entrada ´e um endere¸co de um bloco de dados na unidade de disco. Desta forma, um pequeno arquivo pode ser mapeado com um ´unico i-node, otimizando todas as opera¸c˜oes realizadas sobre ele. Se o arquivo n˜ao puder ser armazenado num ´unico i-node, alguns dos endere¸cos de blocos de dados s˜ao substitu´ıdos por endere¸cos de outros i-nodes denominados de bloco indireto simples (single indirect block ). Para arquivos ainda maiores podem ser usados blocos indiretos duplos ou triplos (double ou triple indirect block ). Este ´e esquema tipicamente utilizado pelos sistemas Unix, como tamb´em esquematizado na Figura 5.31.

Uma varia¸c˜ao destas estrat´egias ´e alocar grupos de setores, denominados blocos (blocks ou extents) ao inv´es de setores individuais, no que se deno- mina estrat´egias de aloca¸c˜ao orientadas `a blocos. Estas estrat´egias visam combinar algumas das vantagens da aloca¸c˜ao cont´ıgua e da aloca¸c˜ao n˜ao cont´ıgua atrav´es da aloca¸c˜ao de blocos ao inv´es de setores individuais, o que elimina parcialmente o problema da fragmenta¸c˜ao al´em de permitir a otimiza¸c˜ao da leitura ou escrita atrav´es de opera¸c˜oes com blocos inteiros (read ahead ou lazy write). Como indica Deitel [DEI92, p. 397], existem v´arias maneiras de se implementar sistemas de aloca¸c˜ao orientados `a blocos, semelhantes as existentes para setores:

Figura 5.31: Aloca¸c˜ao n˜ao cont´ıgua com I-Nodes • Lista ligada de blocos indexada (index block chaining) • Mapeamento orientado `a blocos (block oriented file mapping)

Na lista ligada de blocos um n´umero fixo de setores ´e alocado de cada vez, isto ´e, os blocos possuem o mesmo tamanho, de modo que cada bloco contenha um ponteiro para o pr´oximo bloco tal como na lista ligada de setores, apresentando vantagens e desvantagens idˆenticas.

Na lista ligada de blocos indexada, cujo princ´ıpio tamb´em ´e o mesmo da lista ligada de setores indexada, ´e poss´ıvel termos blocos de tamanho fixo ou vari´avel, num mecanismo mais flex´ıvel para o armazenamento de dados.

No mapeamento orientado `a blocos, os ponteiros s˜ao substitu´ıdos por um esquema de numera¸c˜ao que pode ser facilmente convertido para a numera¸c˜ao de setores de uma unidade de disco. As opera¸c˜oes de modifica¸c˜ao de tamanho de arquivos se tornam bastante ´ageis neste esquema [DEI92, p. 400].