Sistema de Ficheiros - Autenticação · Vantagens / Desvantagens? Um sistema de ficheiros usa este esquema, qual? 12 23 Implementando Ficheiros (2) ... • Começou por ser o Minix

1

1

Sistema de Ficheiros

2

Armazenamento de Informação de Longa Duração

1. Deve guardar grandes quantidades de dados

2. Informação guardada deve sobreviver àterminação dos processos

3. Múltiplos processos devem poder aceder àinformação concurrentemente

2

3

Sistema de Ficheiros

• Solução: discos com ficheiros• Processo devem poder ler e escrever• Ficheiros são geridos pelo S.O.

4

Nomes de Ficheiros (1)

• UNIX vs Windows/MS-DOS• Maiúsculas, minúsculas• Uso de extensões

3

5

Nomes de Ficheiros (2)

Extensões típicas.

6

Estrutura dos Ficheiros

• Três tipos de ficheiros– sequência de bytes– sequência de registos– árvore

4

7

Tipos de Ficheiros (1)

• Regulares– ASCII– Binários

• Directorias• Especiais de caracteres (UNIX)• Especiais de blocos (UNIX)

8

Tipos de Ficheiros (2)

(a) Ficheiro executável (b) Arquivo

5

9

Acesso a Ficheiros• Acesso sequencial

– Ler todos os bytes/registos desde o ínicio– Não pode andar a saltar, pode voltar ao ínicio ou

andar para trás– Conveniente no caso de tapes magnéticas

• Acesso aleatório– bytes/registos lidos por qualquer ordem– essencial para sistemas de base de dados– ler pode ser …

• mover “file marker” (seek), depois ler ou …• ler e depois mover “file marker”

10

Atributos de ficheiros

Possíveis atributos de ficheiros

6

11

Operações nos ficheiros

1. Criar2. Apagar3. Abrir4. Fechar5. Ler6. Escrever

7. Append8. Seek9. Obter

atributos10.Definir

atributos11.Renomear

12

Um Exemplo Usando Chamadas ao Sistema paraFicheiros (1/2)

7

13

Um Exemplo Usando Chamadas ao Sistema paraFicheiros (2/2)

14

Ficheiros Mapeados em Memória

(a) Processo segmentado antes de se mapear o ficheirono seu espaço de endereçamento

(b) Processo depois de mapear– ficheiro existente abc num segment– criar novo segmento para xyz

• Como é implementado internamente? / Problemas?

8

15

DirectoriasSistema com Um Nível de Directorias

• Um sistemas com apenas um nível de directorias– Contém 4 ficheiros– Pertencem a 3 pessoas diferentes, A, B, and C

16

Sistemas com Dois Níveis de Directorias

Letras indicam donos das directorias e dos ficheirosNalgumas situações os utilizadores necessitam de aceder a

ficheiros fora das respectivas directorias. Exs.? Como?

9

17

Sistemas Hieráquicos de Directorias

Um sistema hierárquicos de directorias

18

Nomes dos caminhos (1)

• Caminho absoluto– Windows: \usr\ast\mailbox– UNIX: /usr/ast/mailbox

• Caminho relativo– Conceito de directoria actual– Bibliotecas devem ter cuidado ao mudar a

directoria actual, porquê?

10

19Uma árvore de directorias em UNIX

Nomes dos caminhos (2)

20

Operações Sobre Directorias

1. Criar (vazia, excepto…?)

2. Apagar3. Abrir

directoria4. Fechar

directoria

5. Ler directoria6. Renomear7. “Link”8. “Unlink”

11

21

Implementação do Sistema de Ficheiros

Uma possível organização do sistema de ficheiros

22

Implementando Ficheiros (1)

(a) Alocação contígua do espaço do disco para 7 ficheiros(b) Estado do disco depois dos ficheiros D e E terem sido removidos

Vantagens / Desvantagens?Um sistema de ficheiros usa este esquema, qual?

12

23


Guardar ficheiro como uma lista ligada de blocos de disco

Desvantagens?

24


Alocação da lista ligada usando uma tabela de ficheiros em RAM (FAT)

Desvantagens?

13

25


Um exemplo de um i-nodeVantagens? O(…)

Porquê?

26

Implementando Directorias (1)

(a) Uma simples directoriaentradas com tamanho fixoendereços no disco e atributos na entrada da directoria

(b) Directoria em que cada entrada referencia um i-node

14

27

Implementando Directorias (2)

• Duas formas de lidar com nomes grandes de ficheiros numadirectoria– (a) In-line– (b) In a heap

28

Ficheiros Partilhados (1)

Um sistema de ficheiros contendo um ficheiro partilhado

15

29

Ficheiros Partilhados (2)

(a) Situação antes de “link”(b) Depois de ser criado “link”(c)Depois de o dono original apagar ficheiro

Desvantagens? / Alternativa? / Desvantagens?

30

Gestão de Espaço em Disco (1)• Normalmente um ficheiro é dividido em blocos não

adjacentes de tamanho fixo. Porquê?• Qual o tamanho de um bloco? • Se for um cilindro então um ficheiro de 1 byte ocupa um

cilindro inteiro!• No UNIX por exemplo a média do tamanho dos ficheiros é

de 1kB.– Se se alocar um bloco de 32kB então 97% do disco não é usado!

• Por outro lado, blocos pequenos aumenta o tempo de acesso– Um ficheiro passa a ser consistuido por vários blocos

16

31

Gestão de Espaço em Disco (2)

• Linha a cheio (escala do lado esquerdo) mostra taxa de transferência

• Linha a tracejado (escala do lado direito) mostra espaço emdisco

• Todos os ficheiros com 2KB

Block size

32


(a) Guardar a lista de blocos livre numa lista ligada(b) Num bitmap

17

33


(a) Bloco de ponteiros em RAM para os blocos de disco livres quase cheia- três blocos de ponteiros no disco

(b) Resultado de libertar um ficheiro com 3 blocos(c) Estratégia alternativa para gerir esta situação

- entradas a cinzento representam ponteiros para blocos livres no disco

34


Quotas para registar o uso do disco por parte dos utilizadores

18

35

Fiabilidade dos Sistemas de Ficheiros (1)

• Backups– Recuperar por desastre– Recuperar por “estupidez”

• Backups totais• Backups incrementais Vantagens / Desvantagens?

36


• Dumps fisicos– começa no bloco 0 e copia tudo para a tape– grande velocidade– não permite backups incrementais– copia todas as directorias– não permite a recuperação de ficheiros individuais– e os blocos livres?– e os “bad” blocos?

• Dumps lógicos– começa numa ou várias directorias e percorre-as

recursivamente– reconstruir a lista de blocos livres– ficheiros partilhados apenas devem ser copiados uma vez– Ficheiros especiais não devem ser copiados

19

37


• Um sistema de ficheiros para ser “dumped”– quadrados são directorias, circulos são ficheiros– a cinzento, os modificados desde o último “dump”– cada directoria/ficheiro com o número de i-node

File that hasnot changed

38


“Bitmaps” usados pelo algoritmo de “dump”

20

39


• Inconsistência dum sistema de ficheiros– “crash” antes de todos os blocos modificados

terem sido escritos em disco– blocos podem ser ficheiros, i-nodes, directorias,

lista de blocos livres– utilitários: fsck, scandisk,…– fsck: mantem duas tabelas com um contador

por bloco:• quantas vezes está presente num ficheiro• quantas vezes está presente na “free list”

40


• Estado dum sistema de ficheiros– (a) consistente– (b) falta um bloco– (c) bloco duplicado na lista de livres– (d) bloco de dados duplicado

• Verifica tambem o sistema de directorias

Sols.?

21

41

Desempenho dos Sistemas de Ficheiros (1)

Estruturas de uma cache de blocosLRU é a melhor solução?

42


• Desvantagens do LRU– blocos críticos e muito referênciados não são

guardados em disco• LRU modificado

– o bloco será usado brevemente?– o bloco é essencial para a integridade do sistema?– blocos divididos em categorias

• i-node• blocos indirectos• directorias• cheios de dados• quase cheios de dados

• UNIX: sync e update• MS-DOS: write-through caches

22

43


• Ler blocos antes de serem necessários– Ao aceder ao bloco k coloca em cache o bloco k+1

• Qual o tipo de acesso onde esta optimizaçãoajuda? E o tipo de acesso onde prejudica?

• O sistema de ficheiros deve ser adaptativo

44


• I-nodes colocados no início do disco: Problemano acesso a ficheiros pequenos?

• Disco dividido em grupos de cilindros– cada um com os seus blocos e i-nodes

23

45

Sistemas de Ficheiros Estruturadoscom “Logs”

• Com CPUs mais rápidos, memórias maiores– caches de disco podem também ser maiores– aumento do número de leituras podem vir da cache– por isso, maior parte dos acessos ao disco serão escritas

• Estratégia LFS estrutura o disco todo como um “log”– todas as escritas são inicialmente feitas para um buffer

em memória– periodicamente escreve esses dados para o final do “log”

no disco– quando o ficheiro é aberto, localiza o i-node, depois

encontra os blocos

46

Exemplos de Sistemas de FicheirosCD-ROM

entrada de uma directoria em ISO 9660

24

47

O Sistema Ficheiros CP/M (1)

Organização da memória no CP/M

48

O Sistema Ficheiros CP/M (2)

entrada de uma directoria em CP/M

• 32 entradas• blocos de 1kB• Durante o arranque, é calculado um bitmap dos blocos livres

(como?) e carregado em memória• Como resolver o problema do limite de tamanho?

25

49

O Sistema de Ficheiros MS-DOS (1)

entrada de 32 bytes de uma directoria em MS-DOS

• Usa uma FAT: 12, 16 ou 32 (28 bits)

50

O Sistema de Ficheiros MS-DOS (2)

• Partição máxima para diferentes tamanhos de blocos• As entradas a branco indicam combinações impossíveis

26

51

Sistema de Ficheiros Windows 98 (1)

entrada de uma directoria usada no Windows 98(extendida do MS-DOS)

• Ficheiros com nomes grandes: entrada normal com nome do tipo: SISTEM~1.DOC, antecedida de entradas “especiais” queguardam o nome compeleto

Bytes

52


Bytes

Checksum

• Parte de uma entrada de um ficheiro com um nome grandeem Windows 98 (esta entrada antecede a entrada com o nome MS-DOS)

• Problema?

27

53


Um exemplo de como um nome de ficheiro grande pode ser guardadoem Windows 98

54

Sistema de Ficheiros UNIX / Linux

28

55

O Sistema de Ficheiros UNIX (1)

Directorias importantes em sistemas UNIX

56


• Before linking.• After linking.

(a) Antes do link. (b) Depois do link

29

57


• Separate file systems• After mounting

(a) (b)

(a) Antes do mount. (b) Depois do mount

58

Locks Sobre Ficheiros

(a) Ficheiro com um lock(b) Adicionar um segundo lock(c) Terceiro lock

30

59

Chamadas de Sistema para Ficheiros

• s é um código de erro• fd é um descritor de ficheiro• position é um deslocamento

60

A chamada stat

Campos retornados pela chamada stat.

31

61

Chamadas de Sistema para Directorias

• s é um código de erro• dir identifica uma directoria aberta• dirent é uma entrada numa directoria

62

Implementação do Sistema de Ficheiros UNIX (1)

Layout de uma partição nos sistemas UNIX clássicos

32

63


entrada de um directoria em UNIX V7

• Limitação imposta por esta estrutura?

64


Directory entry fields.

Campos de um i-node

33

65


Um i-node em UNIX

66

Tabela de descritores de ficheiros vs.Tabela de ficheiros abertos


Porque motivo a posiçãode leitura/escrita não é guardada na copia do inode em memória?

34

67


Os passos para localizar /usr/ast/mbox

68


• Berkeley FFS• Directoria com 3 ficheiros• Mesma directoria após apagar o ficheiro voluminous• Grupos de cilindros• Dois tamanhos de blocos

35

69

Sistema de Ficheiros Linux Ext2 (1)

• Começou por ser o Minix– Compativel com UNIX V7

• Depois o Ext– Nomes de ficheiros com 255 caracteres– Ficheiros de 2GB– Muito lento

• Finalmente Ext2– Muito semelhante ao Berkeley Fast File System

• O Linux suporta no entanto vários tipos de sistemas de ficheiros

70


Layout do sistema de ficheiros Linux Ext2

36

71


• Cada i-node com 128 bytes– 12 endereços directos de blocos– 3 indirectos

• Endereços dos blocos com 4 bytes• Blocos de 1KB• Quantos blocos são endereçados por um

bloco de indirecção simples? E dupla?

72

Sistema de Ficheiros Linux Ext3 (1)• Compatível com Ext2• Usa journaling

– Ficheiro especial• Quando o sistema de ficheiros é actualizado

um registo é acrescentado ao log• Uma tarefa processa estas transacções e

escreve os dados para o sistema de ficheiros

37

73

Sistema de Ficheiros Linux Ext3 (2)1. A operação é escrita no ficheiro de log2. A operação é escrita no sistema de

ficheiros3. A entrada do log é marcada como

completa• Mantém a consistência do sistema de

ficheiros– Se a máquina for abaixo, no reboot a tarefa

recomeça a escrever o que ainda não tinhaescrito

– Transacções incompletas são ignoradas

74

Sistema de Ficheiros Linux Ext3 (3)• Log com dados completos

– Mais seguro (dados são escritos na totalidadeou não são escritos de todo)

– Mais lento• Log apenas com metadata

– Mais rápido– Apenas garante consistência

38

75

Sistemas de Ficheiros Linux• ReiserFS

– Usa árvores balanceadas para os ficheiros e nomes de ficheiros

– Mantém um registo de todas as modificações daárvore

• XFS– Usa árvores balanceadas– Permite grandes ficheiros– Bom suporte para multiprocessadores

• JFS– Blocos livres estruturados numa árvore– Directorias pequenas optimizadas nos i-nodes

76

Sistema de Ficheiros do Windows 2000(NTFS)

39

77

API do Sistema de Ficheiros Windows 2000

• Win32 API para manipular ficheiros• Segunda coluna apresenta o equivalente UNIX

78


Parte do código para copiar um ficheiro em Windows 2000

40

79


• Win32 API para manipular directorias• Segunda coluna apresenta o equivalente UNIX

80

Estrutura do Sistema de Ficheiros

NTFS master file table

• Sequência de registos com 1 kB

• Cada registo corresponde a um ficheiro ou directoria, e descreve atributos e lista de blocos

• Primeiros 16 registos são ficheiros com metadados do NTFS

• Bitmap com entradas livres da MFT

41

81

Atributos usados nos registos MFT

• Cada registo consiste numa seq de <cabeçalho do atributo, valor>

• Cabeçalho contem o comprimento do atributo• Se atributos não couberem no registo, “valor” contem um

apontador para disco

inline ou listade blocos

82

Estrutura do Registo MFT de um Ficheiro

Registo MFT para um ficheiro com 3 “runs” e 9 blocos

42

83

Estrutura do Registo MFT de um Ficheiro Fragmentado

Ficheiro que necessita de 3 registos MFT para armazenar as “runs”

84

• Registo MFT para uma directoria pequena.• Directoria grandes guardadas numa árvore B+ para facilitar o lookup

Estrutura do Registo MFT de uma Directoria

43

85

Lookup de um Nome de um Ficheiro

Passos para o lookup de C:\maria\web.htm(traduzido por biblioteca para \??\C:\maria\web.htm)

86

Compressão de Ficheiros

(a) Exemplo de um ficheiro de 48 blocos comprimido para 32 blocos(b) Registo MTF do ficheiro após a compressão

44

87

Cifra do FicheiroK retrieved

user's public key

Documents

Sistema de Ficheiros - Autenticação · Vantagens / Desvantagens? Um sistema de ficheiros usa este esquema, qual? 12 23 Implementando Ficheiros (2) ... • Começou por ser o Minix