Diretório

Transcrição

Diretório

Introdução
•
•
•
•
O sistema de arquivos é a parte mais vísivel do sistema operacional
Cria um recurso lógico a partir de recursos físicos através de uma interface
coerente e simples, fácil de usar
Mecanismo para armazenamento e acesso a dados e a programas
Duas partes básicas:
• Arquivos
•
Armazenamento de dados e de programas
• Diretórios
•
Organização e informações sobre arquivos
Sistemas Operacionais
1
Objetivos do sistema de arquivos
•
•
•
•
•
Fornecer mecanismos para usuários manipular arquivos e diretórios
Garantir a validade e coerência de dados
• Minimizar ou eliminar o risco de perda/alteração de dados
Otimizar o acesso
Fornecer suporte a outros sistemas de arquivos
Suporte a vários usuários (multiprogramação)
• Uso compartilhado (proteção e acesso concorrente)
2
Requisitos mínimos: ponto de vista do usuário
•
Cada usuário deve ser capaz de:
• Criar, apagar, ler e alterar arquivos
• Controlar as permissões de acesso a seus arquivos
• Nomear arquivos de forma simbólica
• Estruturar os arquivos de forma a adequá-los a suas necessidades
específicas
•
Criação de diretórios e subdiretórios
• Realizar back-ups e recuperar arquivos em caso de problemas
3
Requisitos mínimos: ponto de vista do sistema
•
O sistema operacional deve ser capaz:
• Descrever a localização de todos os arquivos e de seus atributos
•
Via diretório
• Gerenciar espaço físico do disco
•
Alocar blocos livres a arquivos em criação/expansão
•
Liberar blocos de arquivos removidos
•
Mecanismos para localizar eficientemente blocos (setores) que
compõem arquivos
4
Conceitos básicos
•
•
•
Arquivos
• Recipientes que contêm dados
Diretórios
• Conjuntos de referências a arquivos
Partição
• Abstração que permite a partir do disco físico criar discos lógicos
5
Conceito de arquivo
•
•
•
Informação pode ser armazenada em diferentes tipos de mídia
• O sistema operacional deve oferecer uma visão uniforme da
informação independente do dispositivo físico de armazenamento
•
Visão lógica é o arquivo
Arquivos são mapeados para dispositivos físicos
Arquivos possuem:
• Nome
• Atributos
• Estrutura interna
• Tipo
• Método de acesso
• Operações
6
Nomes de arquivos
•
•
O sistema de arquivos define um espaço de nomes
• Conjunto de regras e convenções para identificar simbolicamente um
arquivo
Variam de sistema para sistema
• Distinção entre letras maiúsculas e minúsculas
• Obrigatoriedade ou não de uma extensão
•
As vezes extensões são apenas convenções
• Tamanho máximo de nome e da extensão (se houver)
7
Atributos de um arquivo
•
•
•
Informações sobre arquivos
• Nome: informação simbólica empregada para referenciar o arquivo
• Tipo: binário, texto, executável, caracter, bloco
• Localização: posição do arquivo em um determinado dispositivo E/S
• Tamanho: número de bytes que compõem o arquivo
• Proteção: controla acesso de leitura, escrita e execução ao arquivo
• Hora e data de criação, identificação do usuário: informações
destinadas à proteção, segurança e monitoração
Varia de sistema operacional a sistema operacional
Atributos são mantidos em uma estrutura a parte
• Diretório
8
Estruturas de arquivos
•
•
•
Sequência de bytes
Sequência de registros
Árvore
9
Seqüência de bytes
•
•
•
Sistema operacional não
“interpreta” o conteúdo do arquivo
• Enxerga apenas bytes
Interpretação é a nível do
programa de usuário
Vantagem:
• Flexibilidade
byte
10
Seqüência de registros
•
•
•
Arquivo é “interpretado” como uma
sequência de registros, isto é
• Tamanho fixo
• Estrutura interna
Operações leem/escrevem
registros
Emprego raro
registro
11
Árvore
•
•
Conjunto de registros não necessariamente de mesmo tamanho
• Possuem um campo de acesso (chave)
Comum em mainframes
• Método ISAM (Indexed Sequential Access Method)
C
C
D
H
I
A
F
P
G
L
O
P
R W
L
12
Tipos de arquivo
•
•
Sistema operacional suporta vários tipos de arquivos
Tipos comuns:
• Regular
•
Arquivos de dados em ASCII e binário
• Diretório
•
Arquivos que mantém a estrutura (organização) do sistema de
arquivos
• Arquivos especiais de caracter/bloco
•
Vinculados a dispositivos de entrada e saída
13
Exemplos de arquivos UNIX
executável
(formato a.out)
biblioteca
14
Métodos de acesso
•
•
Forma pela qual o conteúdo de um arquivo é acessado
Métodos elementares de acesso:
• Acesso sequencial
• Acesso relativo
15
Acesso sequencial
•
•
•
Acesso a um arquivo é feito através de primitivas (chamadas de sistema)
do tipo read e write
Cada chamada de sistema read retorna ao processo os dados seguintes
àqueles que foram lidos na chamada anterior
Método não adequado a todas aplicações
• e.g.: acesso e atualização a cadastros de funcionários
16
Acesso relativo
•
•
Provê uma chamada de sistema específica para indicar o ponto em que
um arquivo deve ser lido/escrito
Implementado através da abstração de “posição corrente no arquivo”
17
Outros tipos de acesso
•
•
Os métodos sequencias e relativos não resolvem todos os tipos de acesso
• e.g.: localizar um registro a partir do conteúdo
Necessidades de métodos de acesso mais sofisticados, tais como
sequencial indexado, indexado, direto, hash, etc.
• Normalmente implementados por programas específicos
• Baseados nos métodos de acesso sequencial e relativo
18
Operações básicas sobre arquivos
•
•
Arquivo é um tipo abstrato de dados sobre o qual se pode efetuar uma
série de operações
• Criação (create)
• Escrita (write) e leitura (read)
• Reposicionamento em um ponto qualquer do arquivo (file seek)
• Remoção (delete)
• Abertura (open) e encerramento (close)
• Adicionalmente: truncagem (truncate); renomeação (rename);
appending, etc.
Geralmente correspondem a chamadas de sistema
• Operações mais complexas podem ser criadas utilizando-se das
operações básicas
19
Controle de acesso
•
•
•
•
Importante controlar o acesso aos arquivos devido a questões de
segurança e de confidencialidade
Objetivo é evitar acessos indevidos a arquivos
Baseado na identificação dos usuários
• Sistema de autenticação padrão (login name + senha)
• Usuários possuem direitos de acessos
Solução típica:
• Lista de acesso e grupo
20
Listas de acesso
•
•
•
Consiste em associar a cada arquivo e/ou diretório uma lista de acesso
que determina que tipos de acessos são permitidos para cada usuário
Maior inconveniente é o tamanho da lista
Uma solução consiste em:
• Criar classes de usuários
•
e.g.: proprietário, grupo, universo
• Tipos de acessos
•
e.g: read, write, modify, execute
21
Exemplo: UNIX
•
•
Cada objeto oferece 3 bits (rwx) para três domínios diferentes: proprietário,
grupo e outros
Problema de flexibilidade
• Quando um usuário pertence a vários grupos ele é identificado por um
grupo primário e o arquivo (/etc/groups) mantém todos os grupos a que
ele pertence
r w x r- - r - -
1 mary staff
214056
May 30 22:19
windbind.pdf
22
Outra abordagem: senhas
•
•
Associar uma senha a cada arquivo
• A grande desvantagem é o número de senhas
Declaração de compartilhamento de arquivo e/ou subdiretório
• Esquema utilizado pelo Macintosh e pelo Windows
23
Implementação de arquivos
•
•
•
Arquivos são implementados através da criação, para cada arquivo no
sistema, de uma estrutura de dados
Descritor de arquivo é um registro que mantém informações sobre o
arquivo
Informações típicas (atributos):
• Nome do arquivo
• Tamanho em bytes
• Data e hora da criação, do último acesso, da última modificação
• Identificação do usuário que criou o arquivo
• Listas de controle de acesso
• Local do disco físico onde o conteúdo do arquivo foi colocado
• Etc.
24
Tabelas de descritores de arquivos
•
•
•
Descritores de arquivos são armazenados no próprio disco
• Na realidade no mesmo disco lógico (partição)
Problema de desempenho
• Acesso ao disco para ler o descritor de arquivos é lento
• Solução é manter descritor em memória enquanto o arquivo estiver em
uso
•
Indicação se arquivo está em uso normalmente é feito pelo próprio
usuário (aplicação) através de chamadas do tipo open e close
Sistema de arquivos mantém os descritores de arquivos em memória em
uma estrutura de dados do sistema operacional
• Tabela de descritores de arquivos abertos (TDAA)
25
Tabelas de arquivos abertos por processo
•
•
•
Informações relacionadas com arquivos são de dois tipos:
• Não variam conforme o processo que está acessando o arquivo
•
e.g.: tamanho do arquivo
• Dependem do processo que está acessando o arquivo
•
e.g.: posição corrente
Informações dependentes do processo são armazenadas em uma tabela à
parte mantida pelo processo (TAAP)
• e.g.: posição corrente no arquivo, tipo de acesso e apontador para a
entrada correspondente na TDAA
Entrada na TAAP serve para referenciar o arquivo
• File handle
26
Emprego conjunto das tabelas TAAP e TDAA
FileHandle PosCor=12
Leitura
Leitura & esc
Arquivo B
Tabela de arquivos
abertos processo 0
Arquivo A
Descritor Arquivo A
Descritor Arquivo B
Leitura
Tabela de arquivos
abertos por processo 1
Tabela de
Arquivos Abertos
27
Leituras complementares
•
•
R. Oliveira, A. Carissimi, S. Toscani; Sistemas Operacionais. Editora
Bookman, 2010.
• Capítulo 8, seções 8.1, 8.2, e 8.3
A. Silberchatz, P. Galvin; Operating System Concepts. Addison-Wesley,
(4th edition).
• Capítulo 10, seções 10.1, 10.2,10.4, e 10.5
28
Gerenciamento do dispositivo de armazenamento
•
•
•
Problema: arquivos devem ser armazenados no disco!!
• Unidade de manipulação dos dados no dispositivo físico (bloco)
Pontos a serem tratados:
• Relação número de setores do disco que compõem um bloco
•
Não necessita ser 1:1
• Alocação de blocos no disco
• Recuperação de blocos liberados
• Localização de dados no disco
Existe uma relação entre a política de alocação com a política de gerência
de espaço livre
29
Alocação do espaço em disco
•
•
Como alocar espaço em disco de forma que os arquivos sejam
armazenados de forma eficiente e que permita acesso rápido
• Alocar blocos livres suficientes para armazenar o arquivo
• Blocos lógicos do disco são numerados sequencialmente
Duas formas básicas:
• Contígua (alocação contigua)
• Não contígua (alocação encadeada e alocação indexada)
00
01
02
03
04
05
06
....
53
54
55
....
72
73
74
...
96
97
98
....
30
Alocação contígua
•
•
•
Arquivo é uma sequência de blocos lógicos contíguos alocados no
momento da criação
Endereços no disco são lineares
• bloco lógico i e i+1 são armazenados fisicamente em sequência
• Reduz a necessidade de seek já que blocos estão na mesma trilha
•
No pior caso necessita apenas a troca de cilindro
Arquivo é descrito através de uma entrada na forma:
• Bloco físico inicial
• Tamanho do arquivo em blocos
31
Esquema alocação contígua
32
Problemas com alocação contígua
•
•
Problema 1: encontrar espaço para um novo arquivo
• Técnicas de gerência de memória
•
e.g.; first-fit, best-fit, worst-fit
• Gera fragmentação externa
•
Necessidade de compactação
Problema 2: determinar o espaço necessário a um arquivo
• Arquivos tendem a crescer, e se não há espaço contíguo disponível?
•
Aborta execução do programa com erro
•
Recopia o programa para uma zona maior
• Pré-alocar um espaço máximo para o arquivo
•
Fragmentação interna
33
Alocação encadeada
•
•
•
•
Soluciona os problemas da alocação contígua
• Relação a dimensionamento do tamanho e crescimento de arquivos
Alocação é baseada em uma unidade de tamanho fixo (bloco lógico)
• Análogo à paginação
Arquivo é uma lista encadeada de blocos
• Cada bloco contém um ponteiro para o próximo bloco
Arquivo é descrito em uma entrada na forma:
• Bloco inicial do arquivo
• Bloco final do arquivo ou tamanho do arquivo em blocos
34
Esquema de alocação encadeada
35
Prós e contras da alocação encadeada
•
•
•
•
Elimina a fragmentação externa
Arquivos podem crescer indefinidamente
• Não há necessidade de compactar o disco
O acesso a um bloco i implica em percorrer a lista encadeada
• Afeta o desempenho
• Adequado para acesso sequêncial a arquivos
Confiabilidade
• Erro provoca a leitura/escrita em bloco pertencente a outro arquivo
36
Exemplo: File Allocation Table (FAT)
•
•
Variação de alocação encadeada
FAT é uma tabela de encadeamento de blocos lógicos
• Uma entrada na FAT para cada bloco lógico do disco (sistema de arquivos)
• Composta por um ponteiro (endereço do bloco lógico)
• Arquivo é descrito por uma sequência de entradas na FAT, cada entrada
apontando para a próxima entrada
37
Sistema de arquivos FAT (MS-DOS)
•
Organização lógica do disco:
Setor 0 Área reservada
FAT
Diretório raiz
Setor n
•
•
•
Arquivos
Diretório raiz possui tamanho fixo em função da capacidade do disco
• Cada entrada possui 32 bytes
Tamanho da File Allocation Table (FAT) é proporcional a capacidade do disco
Alocação é baseada em clusters (bloco lógico)
• 2n setores (depende da capacidade do disco)
38
Esquema de funcionamento da FAT
•
Desvantagem principal é o tempo de seek
FAT
Diretório
0

jeep
217
Primeiro setor do
arquivo
(start block)
618
217

400
EOF
399
400

399
618
39
Alocação indexada
•
•
•
•
Busca resolver o problema de “ponteiros esparramados” pelo disco que a
alocação encadeada provoca
Mantém, por arquivo, um índice de blocos que o compõe
O índice é mantido em um bloco
Diretório possui um ponteiro para o bloco onde está o índice associado a
um determinado arquivo
40
Esquema de alocação indexada
41
Prós e contras da alocação indexada
•
•
•
Permite o acesso randômico a blocos independentes de sua posição
relativa no arquivo
Tamanho máximo do arquivo é limitado pela quantidade de entradas
suportadas pelo bloco
•
Muito pequeno (limita tamanho do arquivo)
•
Muito grande (desperdiça espaço em disco)
Solução é utilizar dois tamanhos de blocos, um para índice e outro para
dados
• e.g.: i-nodes e bloco de dados em sistemas UNIX
42
Variações em alocação indexada
•
•
Buscam resolver o problema do tamanho do bloco de índices
Três métodos básicos:
• Encadeado
• Multinível
• Combinado
43
Método encadeado
•
O índice mantém ponteiros para os blocos que compõem o arquivo com
exceção da última entrada
• Mantém um ponteiro para outro bloco onde o índice continua
Bloco de índices
(0)
Bloco de dados
(618)
0
k
k+1
n-1
n
Bloco de índices
(300)

618

400
300
k
k+1
n-1
n
Bloco de dados
(500)

500

NULL
NULL
44
Método multinível
•
Mantém um índice de índices
• Não resolve completamente o problema de limite
Bloco de índices
(310)
0
Bloco de índice
de índices (0)
0
310

n-1
n
Bloco de dados
(10)

n-1
n
10
Bloco de índices
(700)
0
442
530
700
Bloco de dados
(442)

n-1
n
45
Método combinado
•
•
Métodos encadeado e multinível em uma única estrutura de dados
O que justifica essa combinação?
• Acesso otimizado a blocos de dados: método indexado
• Limite de arquivos: multinível
Bloco de dados
(310)
Bloco combinado
(0)
Ponteiros p/
bloco de dados
0
Ponteiros p/
bloco de índices
n-1
n
Bloco de índices
(700)
0
442
310

530
700
Bloco de dados
(442)

n-1
n
46
Exemplo: estrutura de i-nodes (UNIX)
128
bytes
10
47
Problema com os métodos de alocação não contígua
•
•
Necessidade de acessar áreas específicas do disco para ler as informações de
encadeamento
• Quantidade de seeks depende do tipo da estrutura (FAT ou descritores)
Solução é manter em memória
• Tradicionais problemas de área de memória ocupada e de confiabilidade
48
Resumo dos tipos de alocação
•
•
•
Alocação contígua
• Só armazena endereço do primeiro bloco
• Acesso randômico é possível (bloco inicial + deslocamento)
• Gera fragmentação externa no disco
Alocação encadeada
• Armazena endereço do primeiro bloco
• Problema de desempenho (seek)
• Não recomendado para acesso randômico
Alocação indexada
• Visa solucionar problemas dos tipos anteriores
• Análise de desempenho (tamanho + tempo de acesso ) é complexa
•
Depende da estrutura de índice e do tamanho de arquivo
49
Conclusão: qual o melhor método de alocação?
•
•
•
Depende do tipo de acesso que o sistema faz a seus arquivos
• Sequêncial versus randômico
Fator adicional:
• Evolução tecnológica (novos hardwares) e de desempenho forçam a
coexistência de diferentes sistemas de arquivos
Necessidade de “fazer conviver” diferentes sistemas de arquivos em um
mesmo computador
• Suporte a múltiplos sistemas de arquivos
50
Suporte a múltiplos sistemas de arquivos
•
•
Fazer com que o sistema operacional suporte diversos sistemas de
arquivos diferentes simultaneamente
Solução inspirada na gerência de periféricos
• Parte independente do dispositivo
•
Serviços idênticos independente do tipo de sistema de arquivos
• Parte dependente do dispositivo
•
Interface padrão
Virtual File System (VFS)
CD-ROM
Partição raw
Disquete
51
Implementação de múltiplos sistemas de arquivos
•
•
•
Cada partição possui um único sistema de arquivos
Tabela com descritores virtuais de arquivos abertos
• Parte independente do sistema de arquivos
• Uma entrada ocupada para cada arquivo aberto (descritor virtual)
Descritor virtual
• Informações comuns a todo sistema de arquivo (proteção, nro de
acessos, ...)
• Apontador para uma estrutura “Tipo do sistema de arquivos”
• Apontador para o descritor do sistema de arquivos real
•
Lista de ponteiros para rotinas que implementam o código
necessário à execução de uma dada chamada de sistema (read,
write, close,...)
•
Informações sobre a gerência desse sistema de arquivos (blocos
livres, ocupados, estrutura de diretórios, ...)
52
Múltiplos sistemas de arquivos: estrutura de dados
Tabela com descritores virtuais
dos arquivos abertos
...
tipo
contador de uso
dados dependentes
...
tipo
contador de uso
dados dependentes
Tab. descritores
Sist. Arq. 1
tamanho
localização
direitos
etc
Descritor do S.A. 1
open
read
write
...
tab. descritores
dados
...
...
...
Tab. descritores
Sist. Arq. 2
tamanho
localização
direitos
etc
Descritor do S.A. 2
open
read
write
...
tab. descritores
dados
...
...
53
Organização da cache de disco
•
•
•
•
Objetivo é manter na memória principal uma certa quantidade de blocos do disco
Não adiciona nem elimina funcionalidades ao sistema de arquivos
• Função é melhorar o desempenho do sistema de arquivos
Não confundir com a cache do processador
Normalmente a cache de disco é mantida em uma área da memória principal e é
controlada pelo sistema operacional
• Pode ser global ou exclusiva (uma por sistema de arquivo suportado)
54
Funcionamento da cache de disco
•
•
•
Em uma requisição de E/S verifica se o bloco está na cache
• Sim: realiza o acesso a partir dessa cópia em memória
• Não: realiza o acesso a partir do disco e carrega o bloco para a cache
A modificação de valores é feito em blocos na cache
• Problema de quando atualizar o disco após um bloco ter sido alterado
Problema da perda de informações e da consistência do sistema de
arquivos em caso de pane do sistema (falta de energia)
55
Políticas de atualização da cache
•
•
•
•
Posterga ao máximo
Atualiza a cada intervalo de tempo
Atualiza imediatamente no disco
Atualiza imediatamente apenas informações sensíveis a consistência do
sistema do arquivo
56
Política de substituição
•
•
•
A cache de disco é um recurso limitado
O que fazer quando um novo bloco deve ser inserido na cache e não há
espaço livre ?
• Problema similar à gerência de memória virtual (substituição de
páginas)
Tipicamente a política Least-Recently-Used (LRU) é empregada
57
Implementação da política LRU
•
•
Facilmente implementada através de uma lista duplamente encadeada
• Quando o bloco é acessado ele é removido de sua posição na lista e
colocado no início da lista
• Todo bloco novo (acessado pela primeira vez) também é inserido no
início da lista
• O bloco menos recentemente acessado é o último da lista
Existe o problema de localizar rapidamente um bloco na lista
• Emprego de função hash
58
Implementação da cache do sistema de arquivos
HASH( partição, número do bloco )
LRU - início
LRU - fim
conteúdo do bloco
informações adicionais
59
Gerenciamento do espaço livre
•
•
•
Necessário manter a informação de blocos livres e ocupados
Métodos básicos:
• Mapa de bits (bitmap)
• Lista de blocos livres
Ambos métodos consideram que os blocos no disco são numerados
sequencialmente
00
01
02
03
....
25
26
....
53
54
55
....
72
73
74
...
96
97
98
....
60
Mapa de bits (bit map)
•
•
Forma simples de gerenciar o espaço em disco
Cada bloco do disco possui um bit indicando se o bloco está livre ou ocupado
Disco
Bloco 0
Físico 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Mapa de Bits.
0 0 1 0 1 0 1 0
0 0 1 1 0 0 0 0
tamanho_ bit _ map 
Capacidade_ disco(bytes)
8  tamanho_ bloco(bytes)
61
Lista de blocos livres
•
•
•
Os blocos livres são organizados em uma lista
Lista é mantida no próprio disco
• Problema é o tamanho da lista
• Paliativo: a medida que o espaço em disco é ocupado a lista diminui
de tamanho liberando espaço do disco
Solução alternativa é manter uma lista de áreas livres ao invés de uma
lista de blocos livres
• Endereço do bloco inicial da área livre e o seu tamanho
62
Gerência de espaço livre através de blocos livres
lógico
Bloco
Físico
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Disco
2
4
6
7
8
9
10
11
14
15
63
•
•
Bookman, 2010.
• Capítulo 8, seções 8.5 e 8.6
A. Silberchatz, P. Galvin; Operating System Concepts. Addison-Wesley, 4th
edition.
• Capítulo 11 seção 11.3
64
Diretório
•
•
•
Problema:
• Quantidade (grande) de arquivos implica na necessidade de organizá-los
Sistema de arquivos oferece duas formas de organização
• Partição
• Diretório
Partição divide um disco em discos lógicos (virtuais), mas não resolve a
organização de arquivos dentro desse disco lógico
• No mínimo uma em um sistema
• Onde “residem” os arquivos e os diretórios
65
O conceito de diretório
•
•
•
Estrutura de dados que contém informações sobre arquivos
• Atributos básicos: nome, tipo, ...
• Localização: dispositivo físico, end. Início, tamanho,...
• Controle de acesso: proprietário, informações de acesso, ações
permitidas,...
• Utilização: data criação/modificação, nro. de processos que o usam,
locking,...
Diretório é um arquivo pertencente ao sistema operacional
• Acesso é feito via serviços do sistema operacional
Tipos de operações em um diretório
• Pesquisar
• Criar e remover arquivos
• Listar diretório
• Atualizar diretório
66
Organização de diretório
•
•
Cada entrada do diretório é um arquivo
Existem duas formas básicas para se organizar um diretório
• Linear
• Em árvore
67
Diretório linear
•
•
•
Mais simples
O diretório corresponde a uma lista de todos os arquivos do disco
Desvantagem:
• Problema de nomeação e agrupamento
• 2 ou mais usuários não podem ter arquivos com o mesmo nome
(colisão)
Silberchatz, Galvin, Gagne. Applied Operating System Concepts (1st Ed.) John Wiley & Sons, 2000.
68
Diretório linear a dois níveis
•
•
Cada usuário possui o seu próprio diretório
• Informação mantida na raiz (master directory)
•
Cada entrada corresponde a um subdiretório (usuário)
Resolve parcialmente o problema de “colisão” de nomes e mas não
resolve o problema de organização dos arquivos
69
Diretório em arvóre
•
•
Generalização do diretório linear a dois níveis
• Permite aos usuários criar subdiretórios e organizar seus arquivos
Possui um diretório raiz (master)
70
Conceitos associados a um diretório em árvore
•
•
•
•
Qualquer arquivo (ou subdiretório) pode ser identificado de forma não
ambígua através de seu caminho (pathname)
• Conceito de diretório corrente, caminho absoluto e caminho relativo
Diretório corrente (diretório de trabalho):
• Qualquer nó da árvore
Caminho absoluto
• Quando se referencia um arquivo a partir da raiz da arvóre
•
e.g.: /spell/mail/prt/first
Caminho relativo
• Quando se referencia um arquivo a partir do diretório corrente
•
e.g.: prt/first
71
Prós e contras da estrutura em árvore
•
•
•
Vantagem:
• Procura eficiente por arquivos
• Possibilidade de agrupamento de arquivos
Desvantagem:
• Compartilhamento de arquivos
Questão é: copiar ou não arquivos a compartilhar?
• Conceito de search path
•
Lista de diretórios (caminhos absolutos) a pesquisar um arquivo
72
Diretório estruturado em grafos acíclicos
•
Generalização da estrutura em árvore
• Provê compartilhamento através de caminhos alternativos para um
arquivo
73
Aliases
•
•
•
•
Compartilhamento pode ser obtido através de aliases
Link é uma forma comum de alias
• Ponteiro para outro arquivo ou subdiretório
Link é uma entrada na estrutura de diretório
• Soft link (simbólico): fornece o caminho do arquivo
• Hard link: fornece a localização (bloco) do arquivo no disco
Remover um link implica em remover apenas a sua entrada na estrutura
de diretório, não o arquivo que aponta
74
Problema da remoção de arquivos
•
•
•
Solução 1:
• Acesso a um link simbólico dangling é detectado no momento do
acesso ao arquivo (não resolvido para nome válido)
Solução 2:
• Preservar o arquivo enquanto houver referências a ele
•
Contador de links ativos
•
Lista de links
Solução 3:
• Não permitir compartilhamento
75
Prós e contras de diretórios estruturados em grafos
•
•
Vantagem:
• Compartilhamento de arquivos
Desvantagem:
• Estrutura mais complexa de manter
• Um arquivo pode possuir mais de um caminho de acesso
•
e.g.: Problemas para contabilização de acessos, back-ups, etc...
• Remoção de um arquivo compartilhado
•
Problema de dangling pointer
• Criação de laços através de aliases
•
Necessita algoritmo para verificar se não cria um laço
(desempenho)
76
Exemplos de aliases: UNIX
%ln index hlink
%ln -s index slinl
%ls -l
-rw- - - - - - -rw- - - - - - lrwx rwx rwx
Contador de referências
2
2
1
chavez
chavez
chavez
chem
chem
chem
Diretório
5228
5228
5
Mar 12 11:36 index
Mar 12 11:36 hlink
Mar 12 11:36 slinkindex
bloco arquivo index
index
hlink
slink
bloco slink
77
Exemplos de aliases: UNIX
%ln index hlink
%ln -s index slinl
%ls -l
-rw- - - - - - -rw- - - - - - lrwx rwx rwx
Contador de referências
2
2
1
chavez
chavez
chavez
chem
chem
chem
Diretório
5228
5228
5
Mar 12 11:36 index
Mar 12 11:36 hlink
Mar 12 11:36 slinkindex
bloco arquivo index
index
hlink
slink
bloco slink
78
Organização de diretórios do UNIX
•
•
•
•
Baseado em partições
Diretório raiz do sistema de arquivos corresponde a uma partição especial
(root)
Conceito de ponto de montagem
Pontos importantes:
• Cada partição possui seu próprio sistema de arquivos
• Capacidade de integrar diferentes sistemas de arquivos em uma
mesma hierarquia
• Sistemas de arquivos podem ser diferentes
•
e.g.: ext2, FAT12, FAT32, NTFS, etc...
79
Montagem de
partições em um
subdiretório
Partição 1
etc
usr
passwd
Partição 2
bin
joão
Partição 3
maria
ls
who
Mail
hosts
so
trab1
teste
teste
trab
trab2
Pontos de
montagem
etc
passwd
hosts
joao
so
trab1
usr
teste
bin
maria
teste
ls
who
Mail
trab
trab2
80
Implementação de diretórios
•
•
•
Diretórios são arquivos especiais cujo contéudo é manipulado pelo sistema
operacional
Sendo um arquivo:
• Utiliza os mesmos mecanismos de alocação, liberação e localização
de blocos do disco que arquivos “comuns”
• Possuem um descritor de arquivo
Duas formas básicas de implementação de diretórios:
• Conjunto de arquivos de descritores de arquivos
• Vetor de descritores
81
Conjunto de arquivos de descritores de arquivos
•
Estrutura de diretório corresponde a um conjunto de arquivos do tipo
diretório
• Cada arquivo diretório possui descritores de arquivos
raiz
etc
passwd
usr
hosts
bin
Descritores
de arquivo
Arquivo
diretório raiz
“etc”
Arquivo
diretório etc
Arquivo passwd
“passwd”
“hosts”
Arquivo hosts
82
Vetor de descritores
•
•
•
Uma parte do disco é reservada para o armazenamento de descritores de
arquivos (diretórios”, regulares, etc...)
Forma um diretório único (o vetor)
• Arquivos e diretórios são identificados por sua posição nesse vetor
Supõem-se que o primeiro descritor descreve o diretório raiz (“/”)
/
raiz
etc
passwd
usr
hosts
etc
bin
usr
bin
passwd
hosts
83
Implementação de diretórios como tabelas
•
•
•
Um diretório nada mais é que uma tabela
Três implementações mais utilizadas:
• Lista não ordenada
• Lista ordenada
• Tabela de dispersão (tabela hash)
Vantages e desvantagens dessas implementações são as “tradicionais”:
• Simplicidade versus desempenho
84
Organização interna de uma partição
•
•
•
•
Uma partição é um disco lógico
Cada partição é autocontida, isto é, todas as informações para acesso aos
arquivos da partição estão contidas na própria partição
• Diretórios e subdiretórios
• Descritores de arquivos da partição
• Blocos de dados
• Lista de blocos livres da partição
Formatação lógica corresponde à inicialização dessas estruturas de dados
Normalmente um setor (bloco) especial do disco informa quais são as
partições e quais parcelas do disco a partição ocupa
85
Partições primárias em um disco IDE
MBR
Master Boot Record
Tabela de partições
Pré-boot
Setor de boot
Partição primária
/dev/hda1
/dev/hda2
Setor de boot
/dev/hda3
Setor de boot
/dev/hda4
Setor de boot
86
•
•
•
Bookman, 2010.
• Capítulo 8, seções 8.7, 8.8 e 8.9
A. Silberchatz, P. Galvin, G. Gagne; Applied Operating System Concepts.
Addison-Wesley, 2000, (1st edition).
• Capítulo 11
W. Stallings; Operating Systems. (4th edition). Prentice Hall, 2001.
• Capítulo 12
87
Sumário
•
•
•
Princípios básicos de hardware
• Arquitetura de computadores
Gerência de entrada e saída
• Software de entrada e saída
Disco magnético
88
Dispositivos periféricos típicos
•
•
•
Dispositivos de E/S são fundamentais para que um sistema seja utilizável
Existe uma grande gama de dispositivos de E/S
• Impossível de analisar todos
• Princípio de funcionamento tem uma base comum
Periférico mais importante é o disco por desempenhar um papel
fundamental em diversos aspectos do sistema operacional
• Armazenamento de dados
• Suporte a implementação de memória virtual
• Aspectos relacionados com tolerância a falhas e segurança de dados
(RAID)
89
Disco magnético
•
•
Um disco de plástico, ou metal, recoberto de material magnético
• Pratos (platters)
Dados são gravados e, posteriormente, recuperados através de um "mola"
condutora (cabeçote de leitura e gravação)
• Escrita: o cabeçote é submetido a uma tensão que gera um campo
magnético o qual magnetiza o disco com diferentes padrões de
polaridades
• Leitura: a variação do campo magnético gerado pela rotação do disco
induz uma corrente no cabeçote de leitura
90
Organização e formatação (1)
•
•
•
Disco é organizado em uma seqüência de circulos concêntricos
• Trilhas
• Largura da trilha corresponde a largura do cabeçote de leitura/escrita
Trilhas são separadas por gaps
• Evitar problemas de alinhamentos
Duas tecnologias definem o número de bits por trilhas
• O número de bits por trilha é constante
•
Trilhas mais internas possuem uma densidade maior bits/polegada
•
Discos com tecnologia CAV (Constant Angular Velocity)
• O número de bits por trilha depende se ela é mais interna ou mais
externa
•
Discos com tecnologia CLV (Constant Linear Velocity)
e.g.; CDROM
•
91
W. Stallings. Operating Systems (4th Ed.), Prentice Hall, 2001.
92
•
•
•
•
Transferência de dados para o disco é feito em blocos
• Tipicamente, bloco é menor que a capacidade de uma trilha
Trilha é subdividida em unidades de tamanho fixo (setores)
Setor:
• Armazenamento de informações
• Informações de controle
•
e.g.; início e final do setor, ECC (Error Correcting Code)
A definição de trilhas e setores é feita pela formatação física
• Feita na fábrica
93
Inf. de controle
Zona de dados
ECC
94
Características físicas (1)
•
•
•
Cabeçote de leitura/escrita são montados sobre um braço
• Fixo: um cabeçote por trilha
• Móvel: cabeçote se desloca sobre as trilhas
Removível versus não removível
• Meio magnético (pratos) são montados fisicamente no braço ou não
•
e.g.; disquete
Densidade dupla versus densidade simples
• Filme magnético é posto, ou não, nas duas superficies do prato
95
•
•
Múltiplos pratos (disk pack)
• Vários pratos empilhados e centrados
• Cada prato um cabeçote de leitura/escrita (braço móvel)
• Cilindro: conjunto de trilhas de mesmo número em pratos diferentes
Mecanismo do cabeçote leitura/escrita
• Contato físico entre a superfície magnética e o cabeçote (floppy)
• Distância fixa (air gap) da superfície magnética
• Distância fixa (air gap) da superfície magnética quando o disco entra
em rotação (disco rígido)
96
Cabeçote R/W
(1 por superfície)
Cilindro
Imaginário
Prato
Superfície
Trilha
Setor
Braço mecânico
97
Exemplo de especificações de disco
•
•
•
Disco 4.1 Gigabytes
• 255 cabeças
• 63 setores de 512 bytes
• 525 cilindros
• Capacidade: 255 x 63 x 512 x 525
Sexagésimo quarto setor mantém um mapa de setores na trilha
Tecnologia atual permite até 8 pratos com 16 cabeçotes
• Diferença no número de cabeçotes é lógico
98
Acesso a dados
•
•
•
•
Menor unidade de transferência é um bloco lógico
• Composto por um ou mais setores físicos
Acessar dado implica em localizar trilha, superfície e setor
Dois métodos:
• Método CHS (Cylinder, Head, Sector)
• Método LBA (Linear Block Addressage)
•
Tradução do L-CHS (Logical) para P-CHS (Physical)
Discos modernos endereçam blocos lógicos sequencialmente
• Conversão de um bloco lógico para sua localização física
•
Não é um mapeamento direto por haver setores fisicamente
defeituosos e pelo número de setores por trilha não ser constante
Cilindros que possuem mesmo número de setores (zonas)
•
99
Desempenho do disco
•
•
Para ler/escrever dados é necessário que o cabeçote de leitura e escrita
esteja posicionada na trilha e no ínicio do setor desejados
Três tempos envolvidos:
• Tempo de posicionamento (seek time)
•
Tempo necessário para posicionar o cabeçote de leitura/escrita na
trilha desejada
• Tempo de latência rotacional
•
Tempo necessário para atingir o início do setor a ser lido/escrito
• Tempo de transferência
•
Tempo para escrita/leitura efetiva dos dados
100
Temporização de acesso ao disco
Transfer
time
Trilha
Seek time
Setor
Cabeçote
leitura/escrita
Latency
time
tacesso  t seek  tlatência  ttrasnf .
101
Tempo de posicionamento (seek)
•
•
•
Possui duas componentes:
• Tempo de acionamento e aceleração do braço do cabeçote
• Tempo de deslocamento até a trilha desejada
Não é linear em função do número do trilhas
• Tempo de identificação da trilha (confirmação)
Tempo médio de seek
• Dado fornecido pelo fabricante
•
e.g.; 5 a 10 ms (tecnologia ano 2000)
102
Tempo de latência rotacional
•
•
Definido pela velocidade de rotação do motor
• e.g. (ano 2000):
•
discos rígidos (5400 rpm a 10000 rpm)
•
unidades de floppy (300 rpm a 600 rpm)
Considera-se o tempo médio
• Nào se sabe a posição relativa do cabeçote com a do setor a ser lido
• Metade do tempo de uma rotação
•
e.g.; 3 ms para um disco de 10000 rpm ( 6 ms uma rotação )
103
Tempo de transferência
•
Tempo de transferência de dados de/para disco depende da velocidade de
rotação
b
T
rN
•
T = tempo de transferência
b = número de bytes a serem transferidos
N = número de bytes em uma trilha
r = velocidade de rotação, nro de rotações por segundo
Tempo médio de acesso é dado por:
Tacesso
1
b
 t seek _ médio  
2r rN
104
Exemplo
•
Acessar um arquivo de dados de 1.3 Mbytes armazenado em disco com
as seguintes características:
Tseek_médio = 10 ms, 10000 rpms, 512 bytes por setor, 320 setores por
trilha
Caso I: Acesso seqüêncial (2560 setores = 8 trilhas x 320 setores)
Tacesso = 10 ms + 8 x (3 + 6) ms = 0.082 s
(Obs: supondo trilhas vizinhas, despreza-se o tempo de
seek)
Caso II: Acesso randômico (leitura na base um setor por vez)
Tacesso = 2560 x (10 ms + 3 ms + 0.01875 ms) = 33.328 s
105
Entrelaçamento (interleaving)
•
•
•
Forma de aumentar o desempenho no acesso ao disco
Objetivo é evitar a latência rotacional em setores adjacentes
Técnica consiste em numerar os setores não mais de forma contígua mas
sim com um espaço entre eles
Disco 1
Disco 2
Fator de entrelaçamento = 0
Fator de entrelaçamento = 2
15
0
14
5
1
13
2
12
11
10
6
8
7
11
15
6
3
4
1
4
9
12
5
9
0
10
14
7
3
2
8
13
106
Escalonamento do disco (1)
•
•
Tratar E/S em disco de forma eficiente se traduz em obter um tempo de
acesso rápido e explorar ao máximo a largura de banda do disco
• Se traduz em minimizar o tempo de posicionamento (seek)
Largura de banda do disco é definida como sendo o número total de bytes
transferidos, divididos pelo tempo decorrido entre o primeiro acesso e a
conclusão da transferência.
107
Escalonamento do disco (2)
•
Algoritmos para reduzir o tempo de seek
• Algoritmos de escalonamento do disco
•
Forma de organizar o atendimento a requisições
FCFS, SSTF, SCAN, C-SCAN, etc
Exemplo para análise
• Disco organizado em 200 trilhas (0-199)
• Posição inicial do cabeçote: trilha 53
• Atender a seguinte fila de requisições:
98, 183, 37, 122, 14, 124, 65, 67
•
•
108
FCFS - First Come First Served (1)
•
•
Acessa na ordem em que as requisições são solicitadas
Para análise em questão obtem-se um deslocamento equivalente a 640 trilhas
109
SSTF - Shortest Seek Time First (1)
•
•
Seleciona a requisição com o menor tempo de seek em relação a posição
atual do cabeçote de leitura/escrita
Análogo ao escalonamento SJF (Shortest Job First)
• Pode provocar postergação de uma requisição
110
SSTF - Shortest Seek Time First (2)
•
Deslocamento equivalente a 236 trilhas
111
SCAN (1)
•
•
O movimento do cabeçote inicia em uma extremidade do disco e se
movimenta em direção a outra extremidade
• Executa as requisições na ordem desta varredura
• Ao chegar no outro extremo, inverte o sentido e repete o procedimento
Conhecido como algoritmo do elevador
112
SCAN (2)
•
Deslocamento equivalente a 208 trilhas
113
C-SCAN (1)
•
•
•
Variação do algoritmo de SCAN
Procedimento é idêntico ao do algoritmo SCAN porém as requisições são
atendidas apenas em um sentido da varredura
• Ao final da varredura o cabeçote é reposiconado no início do disco
Fornece uma visão lógica onde o disco é tratado como uma fila circular
• Oferece um tempo médio de acesso mais uniforme que o algoritmo
SCAN
114
C-SCAN (2)
115
C-LOOK
•
•
Versão do C-SCAN
O cabeçote de leitura/escrita não necessita atingir o extremo do disco para
voltar ao início do disco
116
Outras variações de SCAN
•
•
N-step-SCAN
• Divide a fila de requisições em um certo número de filas de tamanho N
• Cada fila é atendida separadamente utilizando SCAN
• Novas requisições são inseridas em filas diferentes da que está sendo
atendida no momento da chegada destas requisições
FSCAN
• Baseada em duas filas
• Um fila recebe todas as novas requisições enquanto a outra é
empregada para atender as requisições já feitas
117
Qual algoritmo de escalonamento é melhor?
•
•
•
•
SSTF é o método comumente empregado
SCAN e C-SCAN apresentam um melhor desempenho em discos que
possuem um grande número de acesso
Fatores importantes
• Quantidade e tipo de requisições
• Organização de arquivos e diretórios no disco (sistema de arquivos)
O algoritmo de escalonamento deve ser escrito como um módulo separado
do sistema operacional para permitir sua substituição de forma fácil
118
RAID: Redundant Array of Inexpensive Disks
•
•
•
•
Conjunto de discos rigídos visto pelo sistema operacional como um único
disco lógico
Dados são distribuídos entre os diferentes discos físicos
• Permite o acesso paralelo a dados aumentando o desempenho
Possibilita o armazenamento de informações de paridade para permitir a
recuperação de dados em caso de problemas no disco
• Aumento de possibilidade de falhas já que existem mais dispositivos
envolvidos
Diferentes níveis
119
RAID nível 0
•
•
Dados são distribuídos nos diferentes discos do array
• Requisições a blocos de dados armazenados em discos distintos
podem ser efetuados em paralelo
O disco lógico é dividido em unidade de distribuição (strips)
• Strip pode ser blocos físicos, setores, etc...
• Strip são mapeados de forma round-robin em n discos (stripes)
• Técnica conhecida como stripping
120
RAID nível 1
•
•
Objetivo de RAID é fornecer uma redudância de dados para fornecer um
certo grau de tolerância a falhas
RAID 1 a redundância é obtida através da replicação dos dados
• Strips são armazenados em 2 conjuntos distintos de discos físicos
• Denominado de espelhamento (mirroring)
121
RAID nível 1: vantagens e desvantagens
•
•
Vantagens:
• Leitura de um dado pode ser feito privilegiando-se o disco que oferece
o menor tempo de seek e atraso rotacional
• Recuperação em caso de erro é simples
•
Acessa dados do disco não danificado
Desvantagem:
• Custo: necessita o dobro do espaço do disco lógico em discos físicos
122
RAID nível 2
•
•
•
•
O conjunto de discos é sincronizado, isto é, todos os cabeçotes estão
posicionados no mesmo ponto (trilha e setor)
Todos discos são acessados na realização de uma requisição E/S
A unidade de stripping é byte ou palavra
Executa o cálculo de código de correção de erros considerando um certo
número de bits e armazena o resultado em discos separados
123
RAID nível 2
•
•
O número de discos redundantes é proporcional ao logaritmo da
quantidade de dados armazenados no disco
Requisição de E/S
• Leitura: código de correção é calculado para os dados lidos e
comparado com o código de correção lido
• Escrita: cálculo e gravação do código de correção
124
RAID nível 3
•
•
•
Similar ao RAID 2
Diferença é que existe apenas um disco de redundância independente do
número de discos para armazenamento de dados
Cálculo de um código de detecção de erro (paridade)
• Possível reconstruir dados de um disco falho a partir desta informação
125
RAID nível 3: reconstrução de dados
•
Exemplo:
• Array composto por 5 discos físicos, onde discos 0 a 3 servem ao
armazenamento de dados e o disco 4 a paridade (redundância)
Paridade para o bit i de cada disco é calculado da seguinte forma:
x4(i)  x3(i)  x2(i)  x1(i)  x0(i)
Em caso de erro do disco 1, se pode reconstruir seus dados (bit a bit)
realizando o seguinte cálculo:
x1(i)  x4(i)  x3(i)  x2(i)  x0(i)
126
RAID nível 4
•
•
Diferença em relação aos níveis 2 e 3 é que os discos são independentes
podendo então satisfazer requisições em paralelo
Redundância é obtida calculado-se a paridade bit a bit de cada strip e
armazenando o resultado em disco de paridade
127
RAID nível 5
•
•
Organização é similar ao RAID 4
A informação de paridade é distribuída em todos os discos do array de
forma round-robin
128
RAID nível 6
•
•
Introduz um segundo cálculo de paridade para o mesmo conjunto de
dados:
• Paridade é calculada utilizando o esquema de OU exclusivo de RAID 4
e5
• Algoritmo adicional de verificação de dados
Vantagem sobre demais esquemas de RAID é que dois discos podem
falhar simultâneamente
129

Diretório

Transcrição

Documentos relacionados

PROTUSÃO DISCAL ( Método Cyriax )

ficha técnica

Fazer um disco de Benham

DVD TV Escola

20141206 Meia de Rock #55

A Tribuna ES

Como perder seu becape

Descritor de Arquivo

Aldeia 28.02.2010

Sistema Flexão Distração