SO - formatação do sistema de ficheiros SOFS13

DETISistemas de Operação

Formatação do sistema de ficheiros SOFS13

António Rui Borges

Departamento de Electrónica, Telecomunicações e Informática

DETI

1 - 2

Organização interna do sistema de ficheiros - 1

zona de dados

superbloco tabela de mapeamento cluster de dados → nó-i

tabela de nós-i tabela (bitmap) de clusters de dados livres


DETI

1 - 3


• superbloco – contém informação global sobre o sistema de ficheiros, nomeadamente sobre o tamanho e localização das regiões restantes

• tabela de nós-i – constitui um array cujos elementos são nós-i que descrevem os atributos dos ficheiros existentes; os nós-i livres formam adicionalmente uma lista biligada que está organizada como um FIFO linear

• tabela de mapeamento cluster de dados → nó-i – constitui um array com tantos elementos quantos os clusters de dados existentes na zona de dados, a sua finalidade é especificar se o cluster em questão está ou esteve anteriormente associado a um ficheiro, caso em que o elemento contém o número do nó-i correspondente

• tabela (bitmap) de clusters de dados livres – constitui um array de bits indicativo de parte dos clusters da zona de dados que presentemente não estão associados a qualquer ficheiro; cada bit do array referencia um cluster específico, aquele cujo número lógico corresponde ao respectivo índice

• zona de dados – contém os clusters de dados.


DETI

1 - 4


NTBlk = 1 + ⌈NTCltBPB

⌉ + ⌈NTCltRPB

⌉ + NBlkInT + NTClt⋅BPC

A ocupação completa do array de blocos [que forma o dispositivo,] impõe que a equação abaixo tenha soluções inteiras

em que NTBlk representa o número total de blocos do dispositivo, NtClt o número total de clusters da zona de dados, BPB o número de referências a clusters (bitmap) que podem ser armazenadas num bloco, RPB o número de referências a clusters que podem ser armazenadas num bloco, BPC o número de blocos contíguos que formam um cluster, NBlkInT o número de blocos que a tabela de nós-i ocupa e a função o menor inteiro maior ou igual ao argumento.

⌈⋅⌉


DETI

1 - 5

Organização do superbloco - 1

A estrutura de dados que define o superbloco pode considerar-se dividida em seis grandes regiões de parametrização

• cabeçalho – é formado pelos campos magic, version, name, ntotal e mstat que contêm o código de identificação e a versão do sistema de ficheiros, o nome e o tamanho (em número de blocos) do dispositivo de memória de massa onde ele está instalado e uma flag de sinalização que indica se o dispositivo foi adequadamente desmontado (retirado de operação) a última vez que foi montado (posto em operação)

• caracterização da tabela de nós-i – descreve a localização itable_start, e o tamanho (em número de blocos), itable_size, e (em número de elementos), itotal, da tabela de nós-i que se supõe estar organizada como um array; esta tabela inclui ainda a lista ligada de nós-i livres que interliga parte dos seus elementos, os que estão livres, numa lista biligada: ifree indica o número de nós-i presentemente livres e ihead e itail, respectivamente, os índices dos elementos correspondentes aos pontos de retirada e de inserção de valores


DETI

1 - 6

Organização do superbloco - 2

• caracterização da tabela de mapeamento cluster de dados → nó-i – descreve a localização, ciutable_start, e o tamanho (em número de blocos), ciutable_size, da tabela de mapeamento que se supõe estar organizada como um array

• caracterização da zona de dados – descreve a localização dzone_start, e o tamanho (em número de clusters), dzone_size, da zona de dados, indica ainda quantos clusters estão presentemente livres, dzone_free

• caracterização do acesso a clusters de dados livres – fctable_start e fctable_size descrevem, respectivamente, a localização e o tamanho (em número de blocos) da tabela (bitmap) de clusters de dados livres, e fctable_pos o índice da tabela a partir do qual se deve iniciar a pesquisa de novos clusters livres; por outro lado, dzone_retriev e dzone_insert especificam duas regiões de armazenamento temporário, caches, de referências a clusters livres para evitar o recurso directo à tabela

• zona reservada – espaço excedente para garantir que o tamanho em bytes de SOSuperBlock é exactamente igual a BLOCK_SIZE.


DETI

1 - 7

Organização das caches de referências a clusters livres

elemento comreferência válida

elemento semreferência válida

cache_idx

cache

cache de retirada

cache_idx

cache

cache de inserção


DETI

1 - 8

Manipulação do superbloco

O superbloco está localizado no bloco 0 do array que repre-senta o dispositivo. As rotinas que efectuam a sua manipu-lação estão definidas em basicoper

• transferência do conteúdo do superbloco do dispositivo para a área de armazenamento interno: soLoadSuperBlock

• obtenção de um ponteiro para a área de armazenamento interno: soGetSuperBlock

• transferência do conteúdo do superbloco da área de armazena-mento interno para o dispositivo: soStoreSuperBlock.

dispositivo

área dearmazenamento

interno


DETI

1 - 9

Organização da tabela de nós-i - 1

Um nó-i, ou nó identificador, é a estrutura de dados onde estão alojados os restantes atributos de um ficheiro. Os nós-i estão organizados numa tabela interna de tamanho fixo. É importante notar que, como cada ficheiro do sistema de ficheiros tem os seus atributos armazenados num nó-i, aquele localizado na tabela com entrada correspondente ao seu identificador interno, o número máximo de ficheiros distintos residentes no sistema de ficheiros é também fixo.

O campo mode serve simultaneamente para especificar o estado do nó-i, ocupado ou livre, o tipo do ficheiro descrito, atalho, directório ou ficheiro regular, e o controlo de acesso ao ficheiro, indicando, 'r', quem pode ler o seu conteúdo (listar, se for um directório), 'w', alterar o seu conteúdo (criar ou apagar ficheiros, se for um directório), ou, 'x', realizar sobre ele operações de execução (aceder aos ficheiros referenciados, se for um directório). Os utilizadores estão divididos em três classes: o utilizador a que pertence o ficheiro, owner, os utilizadores incluídos no mesmo grupo do owner, group, e os utilizadores restantes, other.


DETI

1 - 10


Torna-se muitas vezes conveniente manter referências para um dado ficheiro em diferentes regiões da árvore de directórios. Uma forma de se fazer isso é criando um atalho que descreva a localização do ficheiro em causa através um caminho absoluto (inicia-se na raiz do sistema de ficheiros) ou relativo (inicia-se no directório onde é incluída a descrição). Esta solução tem, no entanto, um problema: quando o ficheiro referenciado é apagado, ou é movido de um directório para outro, ou o seu nome é modificado, os atalhos associados passam a referenciar coisa nenhuma e não é fácil, nem eficiente, estabelecer um procedimento que resolva a questão.

Um meio alternativo mais seguro e eficaz consiste no estabelecimento daquilo que se designa de ligação primitiva (ou hard link): a entrada de directório que é criada, em vez de referenciar o identificador interno de um ficheiro de texto, o atalho, que contém a descrição da localização do ficheiro em causa, passa a referenciar o identificador interno do próprio ficheiro. Nestas condições, a alteração do nome ou a deslocalização de uma referência passam a ser problemas puramente locais da ligação primitiva envolvida na operação e não afectam as restantes ligações eventualmente existentes.


DETI

1 - 11


Do mesmo modo, mantendo a contagem do número de ligações primitivas efectuadas, campo refcount, o apagamento de um ficheiro passa a ser uma operação que se desenvolve prioritariamente sobre a entrada de directório – o ficheiro só é realmente apagado quando o número de ligações primitivas se torna zero.

Os campos owner e group definem a relação de pertença e são usados, conjuntamente com os bits de controlo de acesso do campo mode, para estabelecer o tipo de operações que um utilizador genérico pode realizar sobre o ficheiro.

Os campos mtime e atime constituem a monitorização de acesso ao ficheiro. Note-se que eles só têm este significado em nós-i ocupados. Quando o nó-i está livre, devem ser interpretados, respectivamente, como prev e next, ponteiros que vão permitir implementar a lista de nós-i livres como uma lista biligada.


DETI

1 - 12


O acesso eficiente ao conteúdo informativo de um ficheiro, como um continuum de dados, supõe que se possa constituir uma lista ordenada de referências aos clusters físicos da unidade de memória de massa aonde a informação está armazenada. Tudo se passa como se o continuum fosse dividido em pedaços com o tamanho de um cluster e a localização de cada cluster fosse armazenada no elemento de um array d, designado de array de referências directas, cujo índice representa o seu número de ordem.

Com efeito, sejam p a posição actual de um dado byte de informação no continuum de dados e d[l] e off as variáveis que permitem localizar o mesmo byte no cluster correspondente da memória de massa. As relações entre estas variáveis são expressas por

p = CLUST_SIZE ⋅l + off

l = p div CLUST_SIZE

off = p mod CLUST_SIZE


DETI

1 - 13


d[0]

d[1]

d[N_DIRECT–1]

Referenciação directa

clusters de dados


DETI

1 - 14


Referenciação simplesmente indirecta

d[N_DIRECT]

d[N_DIRECT+1]

d[N_DIRECT+RPC–1]clusters de dados

i1 ou i1[0]


DETI

1 - 15


Referenciação duplamente indirecta

d[N_DIRECT+RPC∙k]

d[N_DIRECT+RPC∙k+1]

d[N_DIRECT+RPC∙(k+1)–1]clusters de dados

i1[k]

i2

i1[1]

i1[2]

i1[RPC]


DETI

1 - 16


O o tamanho em número de bytes do ficheiro descrito vem expresso pelo campo size e o número de clusters que o seu conteúdo informativo ocupa, pelo campo clucount. Note-se, porém, que o entendimento dado a estas variáveis é muito preciso: tamanho significa o maior valor alguma vez assumido pela posição actual após a escrita de um byte no continuum de dados; número de clusters ocupados corresponde ao número de clusters que estão efectivamente reservados para armazenamento do conteúdo informativo, incluindo portanto, se necessário, os clusters de armazenamento dos arrays parcelares de referências directas e indirectas.


DETI

1 - 17


ihead

nó-i ocupado

nó-i livre

tabela de nós-i

lsta biligada de nós-i livres

(ponto de retirada)

itail (ponto de inserção)


DETI

1 - 18

Manipulação da tabela de nós-i

A tabela de nós-i está localizada num espaço contíguo de blocos do array que representa o dispositivo. A sua manipula-ção é efectuada um bloco de cada vez. As rotinas que o permi-tem fazer estão definidas em basicoper

• conversão do número de um nó-i no número [lógico] do bloco e no deslocamento [dentro do bloco] onde o nó-i está localizado: soConvertRefInT

• transferência do conteúdo de um bloco específico do dispositivo para a área de armazenamento interno: soLoadBlockInT

• obtenção de um ponteiro para a área de armazenamento interno: soGetBlockInT

• transferência do conteúdo de um bloco específico da área de armazenamento interno para o dispositivo: soStoreBlockInT.


DETI

1 - 19

Organização da tabela de mapeamento cluster → nó-i

A tabela de mapeamento cluster → nó-i constitui um array com tantos elementos quantos os clusters de dados existentes na zona de dados. A sua finalidade é especificar se o cluster em questão está ou esteve anteriormente associado a um ficheiro, caso em que o elemento contém o número do nó-i correspondente..


DETI

1 - 20

Manipulação da tabela de mapeamento cluster → nó-i

A tabela de mapeamento cluster → nó-i está localizada num espaço contíguo de blocos do array que representa o disposi-tivo. A sua manipulação é efectuada um bloco de cada vez. As rotinas que o permitem fazer estão definidas em basicoper

• conversão de um índice da tabela no número [lógico] do bloco e no deslocamento [dentro do bloco] onde o número do nó-i associado está localizado: soConvertRefCInMT

• transferência do conteúdo de um bloco específico do dispositivo para a área de armazenamento interno: soLoadBlockCTInMT

• obtenção de um ponteiro para a área de armazenamento interno: soGetBlockCTInMT

• transferência do conteúdo de um bloco específico da área de armazenamento interno para o dispositivo: soStoreBlockCTInMT.


DETI

1 - 21

Organização da tabela (bitmap) de clusters livres

A tabela (bitmap) de clusters livres constitui um array de bits indicativo de parte dos clusters da zona de dados que presentemente não estão associados a qualquer ficheiro; cada bit do array referencia um cluster específico, aquele cujo número lógico corresponde ao respectivo índice.

fctable_pos

O incremento de fctable_pos é feito sempre módulo dzone_total.


DETI

1 - 22

Organização da tabela (bitmap) de clusters livres

A tabela (bitmap) de clusters livres constitui um array de bits indicativo de parte dos clusters da zona de dados que presentemente não estão associados a qualquer ficheiro; cada bit do array referencia um cluster específico, aquele cujo número lógico corresponde ao respectivo índice.

fctable_pos

O incremento de fctable_pos é feito sempre módulo dzone_total.


DETI

1 - 23

Manipulação da tabela (bitmap) de clusters livres

A tabela (bitmap) de clusters livres está localizada num espaço contíguo de blocos do array que representa o disposi-tivo. A sua manipulação é efectuada um bloco de cada vez. As rotinas que o permitem fazer estão definidas em basicoper

• conversão de um índice da tabela no número [lógico] do bloco, no byte [dentro do bloco] e no bit [dentro do byte] onde a referência associada está localizada: soConvertRefBMapT

• transferência do conteúdo de um bloco específico do dispositivo para a área de armazenamento interno: soLoadBlockBMapT

• obtenção de um ponteiro para a área de armazenamento interno: soGetBlockBMapT

• transferência do conteúdo de um bloco específico da área de armazenamento interno para o dispositivo: soStoreBlockBMapT.


DETI

1 - 24

Um directório Um directório constitui neste sentido um tipo particular de ficheiro cuja função é materializar a descrição da estrutura hierárquica subja-cente, contendo referências para os ficheiros que são visíveis a um dado nível da hierarquia interna.

O seu conteúdo informativo pode ser entendido como uma tabela de referên-cias onde cada entrada associa o nome do ficheiro com o seu identificador interno.

Organização de um directório

n.nó-inome


DETI

1 - 25

Tarefas a efectuar

• preenchimento dos campos do superbloco

• criação da tabela de nós-i

• criação da tabela de mapeamento cluster de dados → nó-i

• criação do directório raíz

• criação da tabela (bitmap) de clusters livres e inicialização condicional do conteúdo dos clusters de dados


DETI

1 - 26

Teste 1 (dispositivo de 100 blocos)

Cenários de teste - 1

./createEmptyFile myDisk 100

./mkfs_sofs13 -n SOFS13 -i 100 -z myDisk







Comparar os resultados obtidos com aqueles que resultam do recurso ao programa de formatação fornecido, mkfs_sofs13_bin, usando a ferramenta showblock_sofs13.


DETI

1 - 27


Cenários de teste - 2


./mkfs_sofs13 -n SOFS13_12345678901234567890123 -i 100 -z myDisk







Comparar os resultados obtidos com aqueles que resultam do recurso ao programa de formatação fornecido, mkfs_sofs13_bin, usando a ferramenta showblock_sofs13.


DETI

1 - 28

Descarregamento do pacote

[ruib@ruib-laptop2 teste]$ lltotal 940-rw-r--r-- 1 ruib ruib 615298 Sep 19 09:58 SOFS12_alunos.zip-rw-r--r-- 1 ruib ruib 334731 Sep 23 04:31 SOFS13_alunos1.zip[ruib@ruib-laptop2 teste]$

[ruib@ruib-laptop2 teste]$ unzip SOFS13_alunos1.zip Archive: SOFS13_alunos1.zip . . .[ruib@ruib-laptop2 teste]$

Documents

SO - formatação do sistema de ficheiros SOFS13