46
Sistemas Operativos: Ficheiros Pedro F. Souto ([email protected]) May 24, 2011

Sistemas Operativos: Ficheiros

  • Upload
    others

  • View
    7

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Sistemas Operativos: Ficheiros

Sistemas Operativos: Ficheiros

Pedro F. Souto ([email protected])

May 24, 2011

Page 2: Sistemas Operativos: Ficheiros

Sumário

Ficheiros

Directórios

Implementação de Sistemas de Ficheiros

Controlo de Acesso

Leitura Adicional

Page 3: Sistemas Operativos: Ficheiros

Sumário

Ficheiros

Directórios

Implementação de Sistemas de Ficheiros

Controlo de Acesso

Leitura Adicional

Page 4: Sistemas Operativos: Ficheiros

Ficheiros

I Em comparação com memória principal, o disco:I tem muito maior capacidade (o seu custo unitário é mais

baixo);I permite que o tempo de vida dos dados seja independente

do do processo que os criou;I permite a partilha de dados (hoje mais simples).

I Contudo o acesso directo ao disco não é simples:I um ficheiro fornece uma abstracção dos dados no disco

mais fácil de usar.

Page 5: Sistemas Operativos: Ficheiros

Estrutura dum FicheiroI Ficheiros podem abstrair o espaço num disco de várias

formas:

(a) (b) (c)

1 Record

Ant Fox Pig

Cat Cow Dog Goat Lion Owl Pony Rat Worm

Hen Ibis Lamb

1 Byte

I como uma sequência de bytes (habitual em SO de usogenérico);

I como uma sequência de registos (comum há quase 50anos);

I como uma árvore (apropriada para ordenação – e.g.mainframes).

Page 6: Sistemas Operativos: Ficheiros

Estrutura dum Ficheiro em Unix

I Em Unix, um ficheiro é uma sequência de bytes.I Cabe às aplicações definirem a estrutura que bem

entenderem:

Object module

Header

Object module

Header

Object module

Header

Module nameDate

Size

Perm.Owner

Data

Data size

Text size

Magic #

Entry point

Flags

Text

Symbol Tbl.

Sym. Tbl. size

Page 7: Sistemas Operativos: Ficheiros

Tipos de Ficheiros em UnixI Unix suporta diferentes tipos de ficheiros:

I ficheiros;I texto (ASCII ou outro código, p.ex. UTF-8)I binários (não texto – não legíveis)

I directórios;I dispositivos de entrada/saída (/dev/):

character special fileblock special file

A chamada ao sistema mknod() permite criar este tipo deficheiro.

I mecanismos para comunicação entre processos:FIFO special fileUnix domain sockets

São criados usando as chamadas ao sistema mkfifo() esocket(), respectivamente.

I Cabe às aplicações definirem a estrutura interna que bementenderem.

I O sistema oferece mais flexibilidade, não restringindodesnecessariamente os utilizadores.

Page 8: Sistemas Operativos: Ficheiros

Nomes de Ficheiros

I Ficheiros são identificados por nomes:I tipicamente, strings alfanuméricas;I normalmente, o SO estabelece um comprimento máximo

I Unix:I distingue letras maiúsculas das minúsculas;I não conhece extensões (parte dum nome a seguir a um “.”

(ponto))I alguns programas requerem extensões específicas:

p.ex. gcc usa a extensão dos ficheiros de entrada para deter-minar o tipo de processamento necessário.

Page 9: Sistemas Operativos: Ficheiros

Outros Atributos (possíveis) dum FicheiroI Um SO guarda outra informação relativa a um

ficheiro, além do seu nome e do seu conteúdoTipo se o sistema de ficheiros suportar diferentes tipos;Owner o “dono” da informação no ficheiro;Protecção quem pode lêr, escrever, executar;Tamanho do ficheiro;Datas de criação, de acesso ou modificação:

um ficheiro código fonte modificado depois doficheiro objecto correspondente, deverá ser recom-pilado.

I Outros atributos possíveis, mas menos comuns:

Password para acesso ao ficheiroFlags bits que controlam ou permitem uma dads propriedade,

p.ex. hidden flag, system flag, lock flag, etc

Page 10: Sistemas Operativos: Ficheiros

Acesso a Ficheiros

I Sequencial (fita magnética)

headI para aceder a um byte/registo tem-se que aceder a todos

os que o precedem;I não é possível saltar para a frente ou para trás.

I Directo (random)I permite posicionar a cabeça de leitura/escrita em qualquer

byte/registo do ficheiro;I nem todos os dispositivos de E/S suportam este tipo de

acesso:I por exemplo, porta série.

Page 11: Sistemas Operativos: Ficheiros

Operações sobre FicheirosOperação Chamada ao Sistema em UnixCriar open() (creat()– obsoleta)Eliminar Operação sobre directórios (adiante)Lêr read()Escrever write()Reposicionar cabeça lseek()Lêr atributos fstat(), lstat(), stat()Alterar atributos chmod(), chown() . . .Mapear na Memória mmap(), munmap

I Em Unix:I tem-se que invocar open() antes de aceder a um ficheiro;

I O SO executa várias acções para tornar as operaçõessubsequentes mais rápidas

I deve-se invocar close() quando não se pretende acedermais ao ficheiro.

I Permite que o SO liberte recursos e transfira dados para odisco.

Page 12: Sistemas Operativos: Ficheiros

Chamadas ao Sistema sobre Ficheiros: exemplo/* File display program. Minimal error checking */int main(int argc, char *argv[]) {

int in_fd, rd_cnt, wr_cnt;char buf[BUF_SIZE];if (argc != 2) exit(1); /* syntax error */in_fd = open(argv[1], O_RDONLY); /* open source file */if (in_fd < 0 ) exit(2); /* error in open */while (TRUE) { /* loop until done, or an error */rd_cnt = read(in_fd, buf, BUF_SIZE); /* read from source */if (rd_cnt <= 0) break; /* end of file, or error */wr_cnt = write(STDOUT_FILENO, buf, rd_cnt); /* write block read */if (wr_cnt < 0) exit(4); /* error writing */

}close( in_fd); /* close files */if( rd_cnt == 0 ) /* no error on last read */

exit(0);else /* error on last read */

exit(5);}

I write() não garante que o SO escreve todos os bytes.

Page 13: Sistemas Operativos: Ficheiros

Mapeamento de Ficheiros em Memória (1/3)I Tal como noutros acessos, há que invocar open(),

primeiro.I Para mapear o ficheiro na memória, usa-se mmap():

File

Address−SpaceProcess

I Subsequentes acessos à região de memória em que oficheiro foi mapeado, são acessos ao ficheiro.

I munmap() desfaz a acção de mmap(), pelo queposteriores acessos àquela região de memória poderãoser ilegais.

Page 14: Sistemas Operativos: Ficheiros

Mapeamento de Ficheiros em Memória (2/3)

void *mmap(void *start, size_t length, intprot, int flags, int fd, off_t offset);

I mmap() mapeia apenas o ficheiro na memória:I As páginas são trazidas pelo sistema de MV;I Uma página modificada expulsa pelo sistema de MV, é

escrita no ficheiro.I mmap() permite a partilha de memória entre processos:

I Atenção aos endereços.

int munmap(void *start, size_t length);

Page 15: Sistemas Operativos: Ficheiros

Mapeamento de Ficheiros em Memória (3/3)

ProblemasI Qual o comprimento dum ficheiro após alterações?

I O SO consegue saber facilmente as páginas alteradas,mas não é fácil saber qual é o último byte do ficheiro.

I Modificações num ficheiro mapeado em memóriapodem não ser visíveis imediatamente em outrosficheiros que o acedam de forma convencional

I As modificações só são escritas para o disco quando apágina correspondente é expulsa da memória.

I E se o ficheiro fôr maior do que o tamanho máximo dumsegmento, ou do espaço de endereçamento virtual?

I Os argumento length e offset permitem omapeamento parcial, mas não é tão conveniente.

Page 16: Sistemas Operativos: Ficheiros

Sumário

Ficheiros

Directórios

Implementação de Sistemas de Ficheiros

Controlo de Acesso

Leitura Adicional

Page 17: Sistemas Operativos: Ficheiros

Directórios

I A associação entre ficheiros e a respectiva localização nodisco é feita através de directórios:

F1F3

F2 F4

F5

Files

Directory

I Quer os ficheiros quer os directórios residem no disco:I Em Unix, os directórios são um tipo especial de ficheiros.

Page 18: Sistemas Operativos: Ficheiros

Directórios Planos

I Há um único directório:

Root directory

A A B C

I As letras indicam os “donos” do ficheiro correspondente.

I Todos os ficheiros pertencem ao mesmo directório:+ Simplicidade de implementação.- Conflitos de nomes são inevitáveis.

I Essencialmente, esta solução não escala, mas pode seruma solução para um sistema embebido.

Page 19: Sistemas Operativos: Ficheiros

Directórios Estruturados em Árvore

I Quase todos os sistemas de ficheiros suportam umahierarquia de directórios:

bin dev varusr etc

bin

emacs

I O uso duma àrvore permite:I evitar conflitos de nomes;I agrupar ficheiros de alguma forma relacionados;I resolver nomes duma forma eficiente.

Page 20: Sistemas Operativos: Ficheiros

Directório Corrente e Nomes de Ficheiros

I Um ficheiro pode ser identificado usando dois tipos denomes (pathnames):absolutos incluem todos os componentes desde a raiz

( ) até ao ficheiro/directório, separados por /. P.ex.:/usr/bin/emacs:

I Em Unix, chroot() permite especificar o directório raizdum processo – usado para controlo de acesso.

I.e., um nome começando com o separador é absoluto.relativos incluem todos os componentes desde o

directório corrente (current/working directory) até aoficheiro/directório. P.ex.: bin/emacs.

I Em Unix, em qualquer instante, um processo estáassociado a um directório corrente, que pode variar aolongo da sua vida.

I Componentes com significado especial:. representa o directório corrente;.. representa o directório pai.

Page 21: Sistemas Operativos: Ficheiros

Operações sobre Directórios

Operação Chamada ao Sistema em UnixCriar um directório mkdir()Remover um directório rmdir()Mudar o directório corrente chdir()Mudar o directório raiz chroot()Ler elementos dum directório getdents()Criar um ficheiro open()Criar um nome novo link()Remover um ficheiro unlink()Alterar o nome dum ficheiro rename()

I A chamada ao sistema getdents() não é fácil de usar:é preferível usar funções da libc (man readdir).

Page 22: Sistemas Operativos: Ficheiros

Montagem de Sistemas de FicheirosI Um sistema de ficheiros não ocupa mais de um disco.I Unix permite enxertar (mounting) sistemas de ficheiros: o

nome dos ficheiros é independente do dispositivo que oscontém.

/

a b a

c

p q r q q r

d

/

c d

b

Diskette

/

Hard diskHard disk

x y z

x y z

I Este mecanismo é extremamente flexível, permite acedera sistemas de ficheiros:

I em suportes removíveis, p.ex., floppies;I remotos, p.ex. Network File System (NFS).

Page 23: Sistemas Operativos: Ficheiros

Sumário

Ficheiros

Directórios

Implementação de Sistemas de Ficheiros

Controlo de Acesso

Leitura Adicional

Page 24: Sistemas Operativos: Ficheiros

Implementação de Sistemas de FicheirosI Os sistemas de ficheiros são implementados no disco.I Por razões relacionadas com a administração de sistemas,

costuma dividir-se o disco em partições: discos virtuais.I Cada partição tem o seu sistema de ficheiros.

Entire disk

Disk partitionPartition table

Files and directoriesRoot dirI-nodesSuper block Free space mgmtBoot block

MBR

I O primeiro sector (o no 0) é conhecido por Master BootRecord (MBR), sendo usado no arranque do computador.

I O superblock contém informação essencial para acesso aosistema de ficheiros correspondente.

Page 25: Sistemas Operativos: Ficheiros

Implementação de Ficheiros: Blocos ContíguosI Ficheiros consistem num conjunto de blocos de disco:

I um bloco é um conjunto de sectores contíguos, tipicamenteuma potência de 2.

I Uma possibilidade é guardar os dados em blocoscontíguos:

File A (4 blocks)

File C (6 blocks)

File B (3 blocks)

File D (5 blocks)

File F (6 blocks)

File E (12 blocks)

File G (3 blocks)

(a)

(File A)

(File C)

File B 5 Free blocks 6 Free blocks

(File E)

(File G)

(b)

I Esta solução conduz inevitavelmente à fragmentação dodisco.

I Não é problema em sistemas de ficheiros do tipowrite-once, p.ex. CD-ROMs, DVDs, etc.

Page 26: Sistemas Operativos: Ficheiros

Implementação de Ficheiros: Listas Ligadas

I Uma solução é ligar os blocos que constituem um ficheiro:File A

Physical block

Physical block

4

0

7 2 10 12

File block

0

File block

1

File block

2

File block

3

File block

4

File B

0

6 3 11 14

File block

0

File block

1

File block

2

File block

3

I mas o acesso não sequencial é pouco eficiente;I o espaço disponível em cada bloco deixa de ser uma

potência de 2: o link ocupa alguns bytes.

Page 27: Sistemas Operativos: Ficheiros

Lista Ligada Usando uma Tabela em Memória

I Ambos os problemas podem ser resolvidos mantendo oslinks numa tabela em memória (File Allocation Table (FAT))

Physical block

File A starts here

File B starts here

Unused block

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

10

11

7

3

2

12

14

-1

-1

I O problema é que esta tabela ocupa bastante espaço emmemória (um link por bloco)

I Em princípio, a FAT poderia estar em memória virtualpaginada;

I Em qualquer caso, o acesso a um ficheiro poderá exigiracessos ao disco adicionais.

Page 28: Sistemas Operativos: Ficheiros

Index nodes (Inodes)

I Para conseguir um acesso não sequencial mais eficiente,ficheiros usam blocos apenas com referências (inodes):

File Attributes

Address of disk block 0

Address of disk block 1

Address of disk block 2

Address of disk block 3

Address of disk block 4

Address of disk block 5

Address of disk block 6

Address of disk block 7

Address of block of pointers

Disk block containing additional

disk addresses

I Tipicamente os inodes, residem em blocos do disco bemdeterminados:

I Em Unix, o SO cria-os quando formata o disco.

Page 29: Sistemas Operativos: Ficheiros

Unix InodesI Os apontadores podem ocupar bastante espaço:

I Embora muito mais pequenos do que um bloco/sector, oseu número pode ser muito elevado.

I Para uma melhor utilização do espaço no disco, Unix usavários níveis de indirecção:

I-node

Attributes

Dis

k ad

dres

ses

Single indirect block

Double indirect block

Triple indirect block

Addresses of data blocks

I O i-node contém o endereçodos 10 primeiros blocos.

Page 30: Sistemas Operativos: Ficheiros

Implementação de Directórios em UnixI Directórios são implementados como um ficheiro.I Mas o SO conhece a sua estrutura:

(a)

games

mail

news

work

attributes

attributes

attributes

attributes

Data structure containing the attributes

(b)

games

mail

news

work

I Cada elemento dum directório pode:a) ou conter os atributos do ficheiro correspondente;b) ou a localização duma estrutura de dados contendo esses

atributos (em Unix, os inodes):facilita a partilha de ficheiros.

Page 31: Sistemas Operativos: Ficheiros

Resolução dum Nome

I É o processo de determinar o ficheiro a que esse nome serefere.

I Este processo consiste na análise de cada um doscomponentes do nome, da esquerda para a direita:

independentemente do nome ser absoluto ou rela-tivo.

I Para que o SO resolva um nome, o processo tem que teras necessárias permissões de acesso a cada um dosdirectórios atravessados.

I A resolução de nomes pode ter um custo muito elevado,pelo que o SO pode manter uma cache de nomesresolvidos.

Page 32: Sistemas Operativos: Ficheiros

Resolução de Nomes em Unix

I Uma função essencial do subsistema de ficheiros é aresolução de nomes, e.g. /usr/ast/mbox:

Root directoryI-node 6 is for /usr

Block 132 is /usr

directory

I-node 26 is for

/usr/ast

Block 406 is /usr/ast directory

Looking up usr yields i-node 6

I-node 6 says that /usr is in

block 132

/usr/ast is i-node

26

/usr/ast/mbox is i-node

60

I-node 26 says that

/usr/ast is in block 406

1

1

4

7

14

9

6

8

.

..

bin

dev

lib

etc

usr

tmp

6

1

19

30

51

26

45

dick

erik

jim

ast

bal

26

6

64

92

60

81

17

grants

books

mbox

minix

src

Mode size

times

132

Mode size

times

406

Page 33: Sistemas Operativos: Ficheiros

Directórios como Grafos Acíclicos

I Frequentemente, é conveniente poder atribuir nomesdiferentes ao mesmo ficheiro:

I o grafo resultante deixa de ser uma árvore:Root directory

B

B B C

C C

CA

B C

B

? C C C

A

Shared file

Page 34: Sistemas Operativos: Ficheiros

Links (1/3)

Hard Links é o tipo de referência dum elemento de directóriocomum em Unix:

I Referencia directamente o ficheiro, i.e. o seu i-nodeI Dois hard links para o mesmo ficheiro são

indistinguíveis, i.e. apontam para o mesmo i-nodeSymbolic(/Soft) Links referenciam o ficheiro indirectamente

especificando um pathnameI Na resolução de nomes os symbolic links têm que ser

processados de forma especialBasicamente, o que resta do nome a processar temque ser acrescentado ao nome contido no link.

Page 35: Sistemas Operativos: Ficheiros

Links(2/3)I Com hard links, para evitar dangling links, cada ficheiro

tem um atributo que conta o número de nomes (referencecount):

C's directory B's directory B's directoryC's directory

Owner = C Count = 1

Owner = C Count = 2

Owner = C Count = 1

(a) (b) (c)

I Normalmente, os sistemas de ficheiros não suportam acriação de hard links para directórios:

I Introduzem a possibilidade de criar estruturas do sistemade ficheiros patológicas, a menor das quais é a introduçãode ciclos.

Page 36: Sistemas Operativos: Ficheiros

Links(3/3)

I Unix permite criar symbolic links não só para ficheiroscomo para directórios.

I Mas podem conduzir a dangling pointers.I O sistema de ficheiros requer um i-node adicional por

cada symbolic linksI A resolução de symbolic links pode ser muito menos

eficiente do que a de um hard linkI Note-se que só é possível criar hard links para ficheiros no

mesmo sistema de ficheiros.

Page 37: Sistemas Operativos: Ficheiros

Gestão do Espaço no DiscoI Como manter informação sobre os blocos livres?

(a) (b)

Free disk blocks: 16, 17, 18

A bitmapA 1-KB disk block can hold 256 32-bit disk block numbers

86

234

897

422

140

223

223

160

126

142

141

1001101101101100

0110110111110111

1010110110110110

0110110110111011

1110111011101111

1101101010001111

0000111011010111

1011101101101111

1100100011101111

0111011101110111

1101111101110111

230

162

612

342

214

160

664

216

320

180

482

42

136

210

97

41

63

21

48

262

310

516

I Cada bloco da lista inclui um vector de no de blocos livres,mais uma referência para o bloco seguinte na lista.

I Com o sistema de ficheiros quase cheio, listas ocupammenos espaço do que bitmaps.

Page 38: Sistemas Operativos: Ficheiros

Desempenho: Buffer CacheI O acesso ao disco é muito lento:

I Para evitar ir ao disco sempre que um processo acede aum ficheiro, o SO mantém uma cache dos blocos acedidosmais recentemente, a buffer-cache.

Rear (MRU)Hash table Front (LRU)

I Por vezes alterações a um ficheiro são efectuadas nabuffer-cache e só depois propagadas ao disco:

para garantir propagação para o disco deve usar-se uma chamada ao sistema (p.ex. fsync()).

Page 39: Sistemas Operativos: Ficheiros

Desempenho: Localização dos inodesI A leitura dum ficheiro, por mais pequeno que seja exige a

leitura de 2 blocos:I um para o inode e outro para o bloco com dados.

I Para minimizar a latência no acesso a um ficheiro,interessa manter os inodes tão próximo quanto possíveldos blocos com dados correspondentes.

I-nodes are located near the start of the disk

Disk is divided into cylinder groups, each with its own i-nodes

(a) (b)

Cylinder group

Page 40: Sistemas Operativos: Ficheiros

Log File System (Journaling FS)

Problema: os acessos de escrita ao disco afectam cada vezmais o desempenho do sistema de ficheiros:

I a memória é cada vez maior, o que permite usar cachestambém cada vez maiores;

I a maioria dos acessos de leitura podem ser satisfeitospela cache.

Solução: estruturar o disco como um log:I escritas para o disco são bufferizadas;I periodicamente, todas as escritas são propagadas para

o disco: para o fim do log;I quando um ficheiro é aberto para leitura, há que

localizar o seu inode e ler os blocos.

Page 41: Sistemas Operativos: Ficheiros

Sumário

Ficheiros

Directórios

Implementação de Sistemas de Ficheiros

Controlo de Acesso

Leitura Adicional

Page 42: Sistemas Operativos: Ficheiros

Controlo de Acesso

I O controlo de acesso a ficheiros é essencial para protegero sistema:

I Ficheiros contêm programas e dados.I Em Unix, como quase tudo é um ficheiro, o controlo de

acesso do sistema de ficheiros é ainda mais importantepara a segurança do sistema.

I Um mecanismo básico para controlar o acesso são asAccess Control Lists (ACL):

I A cada objecto associa-se uma Access Control List queespecifica, para cada utilizador

I as operações que o utilizador pode realizar sobre esseobjecto.

Page 43: Sistemas Operativos: Ficheiros

Uso de ACL para Proteger o Acesso a Ficheiros

A B C

ProcessOwner

F1 A: RW; B: A

F2 A: R; B:RW; C:R

F3 B:RWX; C: RX

File

User space

Kernel space

ACL

I ACLs nem sempre são exequíveis de implementar:I exigem a manutenção de muita informação.

Page 44: Sistemas Operativos: Ficheiros

Aproximação às ACL adoptada em Unix

I Um grupo é um conjunto de utilizadores (pessoas oufunções):

I um utilizador pode pertencer a vários grupos.I Cada ficheiro (directório ou dispositivo de E/S) pertence a:

I um owner ;I um grupo.

I A cada ficheiro (. . . ) associa-se permissões, i.e.operações que podem ser executadas sobre esse ficheiro,por:

I o owner ;I os membros do grupo;I os restantes utilizadores.

I O utilizador com uid igual a 0 (zero), o root, pode fazerqualquer coisa:

I A maioria dos ataques a máquinas Unix deve-se apasswords de root fáceis de adivinhar.

Page 45: Sistemas Operativos: Ficheiros

Sumário

Ficheiros

Directórios

Implementação de Sistemas de Ficheiros

Controlo de Acesso

Leitura Adicional

Page 46: Sistemas Operativos: Ficheiros

Leitura Adicional

Modern Operating Systems, 2nd. Ed.

I Secção 6.1: FilesI Secção 6.2: DirectoriesI Secção 6.3: File System Implementation

I Excepto Subsecções 6.3.5 e 6.3.6

I Subsecção 6.4.5: The UNIX V7 File SystemI Subsecção 9.6: Protection Mechanisms

I Excepto Subsecção 9.6.3

I Subsecção 10.7: Security in Unix