File System

Organização lógica de um disco

Como organizar a informação necessária para suportar um sistema de ficheiros?

Estrutura lógica de um disco

Para qualquer parti√ß√£o do disco, existe sempre um boot block, que cont√©m c√≥digo (instru√ß√Ķes) que vai ser carregado para RAM.

O resto do disco irá conter informação, que pode ser organizada de várias formas.

Alternativa 1: Organização em Lista

Organização em Lista

Propriedades/Prós:

  • Forma mais simples de organizar um sistema de ficheiros
  • Cada ficheiro √© constitu√≠do por um registo de dimens√£o vari√°vel com quatro campos
    • Nome, Dimens√£o, Seguinte, Dados
  • No caso dos sistemas de ficheiros em CD/DVD, que s√≥ podem ser escritos uma vez, todos os ficheiros ficam compactados uns a seguir aos outros
    • No caso de sistemas onde √© poss√≠vel apagar ficheiros, √© necess√°rio manter tamb√©m uma lista de espa√ßos livres

Contras:

  • Tempo necess√°rio para localizar um ficheiro atrav√©s do seu nome, pior caso: O(n)O(n)
  • Ficheiros que mudam de tamanho ou s√£o apagados s√£o problem√°ticos:
    • Espa√ßo ocupado por cada ficheiro √© cont√≠nuo
    • Fragmenta√ß√£o da mem√≥ria

Alternativa 2

Consiste em ter duas Listas, uma delas com os meta-dados (Nome, Dimens√£o, Pointeiro para os Dados) e outra com os Dados em si.

Organização em duas listas

Prós:

  • Resolve a primeira desvantagem da alternativa 1:
    • criando um direct√≥rio √ļnico onde todos os nomes dos ficheiros est√£o juntos
    • os nomes dos ficheiros ficam perto uns dos outros no disco
    • aumenta a efic√™ncia da procura de um ficheiro dado o seu nome

Contras:

  • Resolve a segunda desvantagem da alternativa 1, mas a custo de perder funcionalidade: dividir os dados de cada ficheiro em blocos de dimens√£o fixa.

O sistema de ficheiros do CP/M (um dos primeiros para PCs, 1977) utilizava uma estrutura deste tipo.

Sistema de Ficheiros do CP/M

Estrutura de uma entrada do directório do sistema de ficheiros do CP/M:

block

Neste sistema:

  • cada bloco possu√≠a 1 KByte (por omiss√£o)
  • mapa de blocos com 16 entradas, logo a dimens√£o m√°xima de um ficheiro √© 16 KBytes

Mapa de blocos de dados cont√©m os n√ļmeros dos blocos de dados do ficheiro (Disk Block Number)

Para aumentar a dimens√£o m√°xima dos ficheiros, temos duas op√ß√Ķes:

  • Aumentar o mapa de blocos (ineficiente para ficheiros pequenos);
  • Aumentar o tamanho dos blocos (maior fragmenta√ß√£o interna).

Sistema de Ficheiros do MS-DOS

  • Evoluiu a partir do sistema CP/M
  • Possui uma estrutura de sistema de ficheiros semelhante
  • Em vez de um mapa de blocos por ficheiro, no MS-DOS existe:
    • uma tabela de blocos global partilhada por todos os ficheiros
    • esta tabela √ļnica √© t√£o representativa da estrutura do sistema de ficheiros que deu origem ao nome do sistema de ficheiros mais popular que a usa: o sistema de ficheiros FAT (Tabela de Aloca√ß√£o de Ficheiros ‚ÄĒ File Allocation Table).

File Allocation Table (FAT)

FAT filesystem

Num sistema de ficheiros FAT, a parti√ß√£o cont√©m tr√™s sec√ß√Ķes distintas:

  • A tabela de aloca√ß√£o (File Allocation Table, FAT): um vetor com, no m√°ximo, 2n2^n inteiros de nn bits (designado FAT-16 para n=16, FAT-32 para n=32, etc);
  • uma diretoria com os nomes dos ficheiros presentes no sistema de ficheiros;
  • uma sec√ß√£o com o espa√ßo restante dividido em blocos, de igual dimens√£o, para conter os dados dos ficheiros

A identificação dos blocos de um certo ficheiro é feita da seguinte forma:
O Diretório contém o nome do ficheiro e um inteiro que corresponde a um índice da tabela de alocação.
As entradas da FAT:

  • com o valor zero indicam que o bloco com o mesmo √≠ndice est√° livre;
  • com valores diferentes de zero indicam que o respectivo bloco faz parte de um ficheiro:
    • se o valor for maxmax, significa que este √© o √ļltimo bloco relativo ao ficheiro;
    • se o valor n√£o for x‚Ȇmaxx \neq max, significa que o bloco xx √© o pr√≥ximo bloco com dados relativos a este ficheiro.

Exemplo

Por exemplo, na imagem acima:

O FichA tem dados nos blocos:

  • 0 (√≠ndice no diretorio);
  • 2 (√≠ndice para que o √≠ndice 0 na FAT aponta);
  • como a entrada 2 na FAT √© max, o Bloco 2 √© o √ļltimo com dados do FichA.

O FichB tem dados nos blocos:

  • 1 (√≠ndice no diretorio);
  • 5 (√≠ndice apontado pela entrada 1 da FAT);
  • mais nenhum bloco, pois a entrada 5 da FAT cont√©m max.

O FichC só tem dados no bloco 3, pois o índice na diretoria é 3, e a posição 3 da FAT contém max.

A FAT é dimensionada para:

  • Caber em mem√≥ria RAM (a FAT √© carregada do disco para RAM quando o FS √© montado)
  • Ter tantas entradas quanto o n√ļmero de blocos de dados na parti√ß√£o em disco

Desvantagens do FAT

  • Elevada dimens√£o da FAT quando os discos t√™m dimens√Ķes muito grandes:
    • Por exemplo, numa parti√ß√£o 1 Tbyte: usando FAT-32 e blocos de 4 KBytes, a FAT pode ocupar 1 GByte (1TBytes/4KBytes √ó 4 bytes [sendo que este 4 adv√©m de serem endere√ßos de 32 bits, logo s√£o precisos 32 / 8 bits = 4 bytes para os representar])
  • Tabelas desta dimens√£o n√£o s√£o poss√≠veis de manter em RAM permanentemente:
    • √Č preciso ler a FAT do disco, o que prejudica muito o acesso √† cadeia de blocos de um ficheiro

Organização com Descritores Individuais de Ficheiros (i-nodes)

  • Manter a descri√ß√£o do ficheiro num descritor pr√≥prio de cada ficheiro, chamado i-node
    • Exemplos de atributos inclu√≠dos no i-node: tipo de ficheiro, dono, datas de √ļltimos acessos, permiss√Ķes, dimens√£o, localiza√ß√Ķes dos blocos de dados
    • √Č a estrutura que est√° entre as entradas dos diret√≥rios que referenciam o ficheiro e os seus blocos de dados
  • Vantagem: podem existir v√°rias entradas de diret√≥rio a apontar para o mesmo ficheiro
    • No√ß√£o de hard link: podem existir v√°rios nomes (ou caminhos/paths) para o mesmo ficheiro.
  • Os i-nodes s√£o guardados numa estrutura especial de tamanho fixo antes dos blocos de dados

inodes

  • No Linux tem o nome de tabela de inodes
  • No Windows tem o nome de MFT (Master File Table)
  • O n√ļmero m√°ximo de ficheiros numa parti√ß√£o √© dado pelo n√ļmero m√°ximo de i-nodes nessa tabela

A Sequ√™ncia de Passos para Aceder ao Conte√ļdo de um Ficheiro

ins

  • Um ficheiro √© univocamente identificado, dentro de cada parti√ß√£o, pelo n√ļmero de i-node (muitas vezes chamado i-number)
  • Os direct√≥rios s√≥ t√™m que efetuar a liga√ß√£o entre um nome do ficheiro e o n√ļmero do seu descritor tab5

Percorrer a árvore de diretórios

  1. Começar pelo diretório raíz
    • i-number da raiz tem valor pr√©-conhecido (e.g., i-num = 2)
  2. Dado o i-number, obter o i-node do diretório
    • Na cache de i-nodes (em RAM) ou na tabela de i-nodes (em disco)
  3. A partir do i-node, descobrir os √≠ndices dos blocos de dados com o conte√ļdo do diret√≥rio
  4. Ler cada bloco do diretório e pesquisar nele uma entrada com o próximo nome do pathname
  5. Assim que seja encontrada, a entrada indica o i-num do próximo nome
  6. Repetir a partir do passo 2 para este novo nome

Descritor do Volume

Possui a informação geral de descrição do sistema de ficheiros, como por exemplo, a localização da tabela de descritores e a estrutura da tabela de blocos livres.
Uma vez que a informa√ß√£o aqui guardada √© de import√Ęncia fundamental, o descritor de volume √© geralmente replicado noutros blocos. Se este se corromper pode ser imposs√≠vel recuperar a informa√ß√£o do sistema de ficheiros.

Implementação do descritor de volume:

  • Unix - bloco especial denominado superbloco
  • NTFS - ficheiro especial
  • FAT - a informa√ß√£o em causa √© descrita diretamente no setor de boot

inodes

Tabela de Blocos Livres (ou Tabela de Alocação)

Mantém um conjunto de estruturas necessárias à localização de blocos livres. Pode ser um simples bitmap (cada bit indica se o respetivo bloco está livre ou ocupado). O uso de uma tabela de blocos livres desacoplada dos i-nodes tem vantagens:

  • √© poss√≠vel ter estruturas muito mais densas;
  • pode-se organizar a tabela de blocos livres em v√°rias tabelas de menor dimens√£o para blocos adjacentes.

Sistema de Ficheiros EXT

O EXT é não só o principal sistema de ficheiros do Linux como um sistema de referência para outros sistemas de ficheiros atuais.

O sistema EXT mantém a tabela de i-nodes no Descritor de Ficheiros, atribuindo a cada i-node um i-number que corresponde à sua posição na tabela. Este i-number identifica então o respetivo i-node univocamente.
O n√ļmero de i-nodes (e portanto o n√ļmero de ficheiros) est√° ent√£o limitado pelo tamanho desta tabela.
Para além da tabela de inodes existem em cada partição ainda duas outras tabelas:

  • o bitmap de i-nodes - posi√ß√Ķes dos i-nodes livres
  • o bitmap de blocos - posi√ß√Ķes dos blocos livres

Cada i-node contém:

  • Meta-dados do ficheiro;
  • Localiza√ß√£o dos dados do ficheiro (√≠ndices do 1¬ļ bloco, do 2¬ļ bloco, etc).
Campo Descrição
i_mode Tipo de ficheiro e direitos de acesso
i_uid Identificador do utilizador
i_size Dimens√£o do ficheiro
i_atime Tempo do √ļltimo acesso
i_ctime Tempo da √ļltima altera√ß√£o do i-node
i_mtime Tempo da √ļltima altera√ß√£o do ficheiro
i_dtime Tempo da remoção do ficheiro
i_gid Identificador do grupo do utilizador
i_links_count Contador de hard links
i_blocks N√ļmero de blocos ocupado pelo ficheiro
i_flags Flags v√°rias do ficheiro
i_block[15] Vetor de 15 unidades para blocos de dados
Outros campos ainda n√£o utilizados

Referência Indireta

A referência indireta é usada em sistemas como o ext3. Esse sistema de ficheiros referencia os blocos da seguinte forma:

  • √ćndice dos blocos do ficheiro √© mantido num vetor i_block do i-node, com 15 posi√ß√Ķes
    • As primeiras 12 entradas s√£o diretas (i.e, correspondem diretamente a um bloco com dados do ficheiro);
    • As restantes entradas cont√™m refer√™ncias indiretas para outros blocos, com n√≠vel de indera√ß√£o um (para a entrada 13), dois (para a 14) e tr√™s (para a 15).
  • S√≥ se usam as entradas (e blocos de √≠ndices) necess√°rios

ext3

A dimensão máxima de um ficheiro é então B×(12+BR+(BR)2+(BR)3)B \times \left(12 + \frac{B}R + (\frac{B}R)^2 + (\frac{B}R)^3\right)

  • BB √© a dimens√£o em bytes de um bloco de dados;
  • RR √© a dimens√£o em bytes de uma refer√™ncia para um bloco;

Com blocos de 1 Kbyte e refer√™ncias de 4 byte, a dimens√£o m√°xima de um ficheiro √© ‚Čą\approx16 Gbytes

Vis√£o Global

global

Estruturas em RAM de Suporte ao FS

Estruturas de Suporte à Utilização dos Ficheiros

Todos os sistemas de ficheiros definem um conjunto de estruturas em memória volátil para os ajudar a gerir a informação persistente mantida em disco.

Objetivos:

  • Criar e gerir os canais virtuais entre as aplica√ß√Ķes e a informa√ß√£o em disco;
  • Aumentar o desempenho do sistema mantendo a informa√ß√£o em caches;
  • Tolerar eventuais faltas;
  • Isolar as aplica√ß√Ķes da organiza√ß√£o do sistema de ficheiros;
  • Possibilitar a gest√£o de v√°rias organiza√ß√Ķes de estruturas de ficheiros em simult√Ęneo.

Estruturas de Suporte à Utilização dos Ficheiros

  • Quando existe uma opera√ß√£o sobre um ficheiro j√° aberto, o identificador do ficheiro permite identificar na estrutura de descritores de ficheiros abertos do processo o ponteiro para o objecto que descreve o ficheiro na estrutura de ficheiros abertos global (passo 1).
  • De seguida √© perguntado ao gestor de cache se o pedido pode ser satisfeito pela cache (passo 2).
  • Se n√£o puder ent√£o √© invocada a fun√ß√£o correspondente √† opera√ß√£o desejada do sistema de ficheiros, dando-lhe como par√Ęmetro o descritor de ficheiro correspondente (passo 3).
  • Finalmente, os blocos de dados do ficheiro s√£o lidos ou escritos a partir da informa√ß√£o de localiza√ß√£o dos blocos residente no descritor de ficheiro (passo 4).

Tabelas de Ficheiros

File table

A file table contém:

  • Cursor que indica a posi√ß√£o actual de leitura/escrita
  • Modo como o ficheiro foi aberto

Tabela de ficheiros abertos - por processo:

  • cont√©m um descritor para cada um dos ficheiros abertos
  • mantida no espa√ßo de mem√≥ria protegida que s√≥ pode ser acedida pelo n√ļcleo

Tabela de ficheiros abertos - global:

  • cont√©m informa√ß√£o relativa a um ficheiro aberto
  • mantida no espa√ßo de mem√≥ria protegida que s√≥ pode ser acedida pelo n√ļcleo

A existência de duas tabelas é fundamental para garantir o isolamento entre processos, permitindo a partilha de ficheiros sempre que necessário (e.g. os cursores de escrita e leitura de um ficheiro entre dois ou mais processos).

Note-se que os identificadores para a tabela global estão na tabela privada que está em memória protegida, pelo que não podem ser alterados.


Slides: