ACH2024 Aula15e16 OrganizacaoDeArquivos e AcessoEmMemoriaSecundaria

Prévia do material em texto

1
ACH2024 
Aulas 15 e 16
Organização de arquivos,
e acesso em memória secundária
Profa. Ariane Machado Lima
2
Organização de arquivos de dados
 Muitos arquivos de dados são uma lista de dados, 
cada um podendo conter vários campos
 Ex: linhas de uma tabela, seja de uma planilha, de um .csv, 
de uma tabela de banco de dados, ...
 Cada dado normalmente tem uma chave, pela qual é 
possível realizar operações de busca e ordenação
 Chamaremos cada dado (contendo a chave e demais 
campos) de registro
 Como separar os campos? Como separar os 
registros?
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Organização de arquivos de dados
 Registros de tamanho fixo x tamanho variável
 Tamanho fixo: fácil de calcular a posição dos 
registros dentro do arquivo (podemos forçar 
tamanho fixo à custa de perda de espaço)
 Tamanho variável: tem como conseguir calcular 
a posição dos registros (por ex: cada registro 
deve ter um campo inicial com o tamanho do 
registro) 
18
Cabeçalho de arquivos
 Cabeçalho do arquivo (descritor) pode conter 
informações como:
 Descrição dos formatos dos campos de um registro
 Códigos de tipos de registros para registros de 
tamanho variável
 Data de criação e atualização
Permite definição de padrões (ex: pdf, tiff, jpg) e facilita 
conversão entre padrões
19
Armazenamento de arquivos
● Quando estamos falando em arquivo, normalmente estamos 
falando em armazenamento em memória SECUNDÁRIA
● Memória secundária:
• HD
• Disquetes
• CD-ROM
• DVD
• Pen-drives
• Chips de memória
• Fita magnética
• ...
20
Memória primária x secundária
(TANEMBAUM & BOS, 
2015)
Mem. principal
Mem. secundária
21
22
ENTÃO POR QUE USAR MEMÓRIA PRIMÁRIA???
23
24
POR QUE ESSA DIFERENÇA?
VAMOS ENTENDER COMO SE DÁ A LEITURA DE UM DADO NO HD...
25
HD – Hard Disk (em contraposição 
às demais mídias da época)
26
HD – Hard Disk (em contraposição 
às demais mídias da época)
27
28
(TANEMBAUM & BOS, 2015)
Estrutura de um HD
pratos
29
O você acha que o computador deve fazer 
para ler algum dado do HD?
A divisão de uma trilha em setores é definida pelo 
disco, e não pode ser mudada.
30
O você acha que o computador deve fazer 
para ler algum dado do HD?
1) Identifica em que setor/trilha/superfície está 
a informação
2) Movimenta o braço de leitura para o cilindro 
correto (para poder acessa a trilha correta)
3) Rotaciona o prato para posicionar a cabeça 
de leitura sobre o setor correto
4) Faz a leitura de um certo nr de bytes 
31
O você acha que o computador deve fazer 
para ler algum dado do HD?
1) Identifica em que setor/trilha/superfície está 
a informação
2) Movimenta o braço de leitura para o cilindro 
correto (para poder acessa a trilha correta)
3) Rotaciona o prato para posicionar a cabeça 
de leitura sobre o setor correto
4) Faz a leitura de um certo nr de bytes 
Passos 2 e 3 (chamados SEEK) são 
mecânicos! Por isso demora tanto!
32
33
Observação: Acesso sequencial x 
acesso aleatório (ou randômico ou direto)
 Apesar do custo de um seek, o acesso é direto, 
pois não é necessário ler dados anteriores
 Também chamado de acesso aleatório ou 
randômico
 Em contraposição, fitas demandam acesso 
sequencial, ou seja, é preciso passar por todo o 
trecho de fita anterior ao que contém o dado 
desejado 
34
Quanto mais seeks, mais cara a 
leitura
Os arquivos não são estáticos, por isso
podem não estar armazenados de forma 
contígua pelo disco
→ tem que armazenar pedaços dos arquivos
nos setores (mais ou menos como se fosse
 uma lista ligada)
O tempo de acesso a uma informação,
na prática, depende:
- da distribuição dos dados de um 
 arquivo pelo disco
 - da tecnologia
35
Como calcular tempo de acesso
● Se acesso a disco é caro e queremos escolher estruturas 
de dados que diminuam o tempo de acesso, precisamos 
poder calcular (ou estimar) o tempo de acesso de uma 
forma não muito complicada, pelo menos:
- independente da distribuição e localização do arquivo em disco
- independente da tecnologia
● Para simplificar os cálculos, podemos fazer a seguinte 
aproximação (pior caso): 
- considera-se que é necessário um seek por “pedaço” de arquivo a ser 
lido
- tempo de acesso total = nr de acessos (seeks) * tempo de um acesso
36
Como calcular tempo de acesso
● Se acesso a disco é caro e queremos escolher estruturas 
de dados que diminuam o tempo de acesso, precisamos 
poder calcular (ou estimar) o tempo de acesso de uma 
forma não muito complicada, pelo menos:
- independente da distribuição e localização do arquivo em disco
- independente da tecnologia
● Para simplificar os cálculos, podemos fazer a seguinte 
aproximação (pior caso): 
- considera-se que é necessário um seek por “pedaço” de arquivo a ser 
lido
- tempo de acesso total = nr de acessos (seeks) * tempo de um acesso
De que tamanho tem que ser esse pedaço? 
Pode ser um byte? E se meu programa quiser ler um byte de cada vez?
Por que ainda valorizamos a memória principal?
37
Paginação
● Disco é grande, mas o acesso é lento
● Fazer várias pequenas leituras no disco tornaria os programas 
inviáveis…
● Solução: ler um “pedaço” razoável do disco, trazer para a memória 
principal, processá-la lá conforme necessário, se for salvar reescrever 
o pedaço todo no disco novamente
● Ou seja, tenho um subconjunto do meu disco em memória principal 
● Chamaremos esse “pedaço”, contendo x setores (x um número 
inteiro) de “página”
● O tamanho de uma página é definida pelo Sistema Operacional (SO) 
durante a formatação do disco, e não pode ser alterada 
dinamicamente. 
38
Memória virtual
● O Sistema Operacional (SO) gerencia se a 
informação (ou seja, a página que contém 
informação) já está em memória
• Se não estiver, precisa carregá-la (em uma moldura de 
página, ie, trecho que memória principal destinado a 
armazenar uma página do disco)
• Se não tiver moldura disponível, precisa descarregar 
alguma no disco antes 
● Com isso os programas podem endereçar todo o 
disco como se ele estivesse em memória principal 
(memória virtual)
39
https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html
40
https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html
Como ocorre esse mapeamento?
41
Memória virtual – mapeamento de 
endereços
Seja N o espaço de endereçamento (lógico) e M 
o espaço de memória principal (física)
f : N → M é um mapeamento podendo N >> M 
Como fazer esse mapeamento de endereço lógico 
(do programa) a um endereço físico da memória 
principal?
42
Memória virtual – mapeamento de 
endereços
Lembrando que pode |N| >> |M|
Um endereço de N (lógico, virtual): parte dos bits é o número da 
página (p) e a outra parte é a posição (offset) dentro da página (b)
Lembrando que pode haver tantas páginas quanto forem necessárias para 
cobrir N 
Tabela de Páginas: se a página de número p estiver na memória 
principal, a p-ésima entrada da Tabela de Páginas contém o 
endereço da moldura p' (na memória principal) que contém a 
página p
Isto é, um endereço n pertencente a N é pb (p concatenado com b) e 
o mapeamento f é:
f(n) = f(pb) = PageTable[p] + b = p' + b
43
Memória virtual – mapeamento de 
endereços
Página p (residente 
 na moldura presente
no endereço p’ da
 memória física)
44
45
46
Organização de arquivos na 
memória secundária
 Bloco: unidade de transferência de dados entre memória principal e 
a memória secundária
– Obs: Em sistemagerenciador de banco de dados (SGBD), um bloco é 
formado uma ou mais páginas (definido nos parâmetros de configurador 
de um SGBD)
– Usaremos aqui o termo bloco de forma genérica, a não ser quando 
especificado
 É comum considerar que em cada bloco pode haver vários registros
 Se R (tamanho fixo do registro, para simplificar) e B (tamanho do 
bloco) e R ≤ B:
fator de blocagem fb = floor(B/R)
= número de registros inteiros que cabem em um bloco
47
Cabeçalhos de arquivos
 Cabeçalho do arquivo (descritor) pode conter 
informações como:
 Descrição dos formatos dos campos de um 
registro
 Códigos de tipos de registros para registros de 
tamanho variável
 Primeiro e último bloco
 Informações para determinar os endereços dos 
seus blocos
48
Organização de arquivos na 
memória secundária
 Organização espalhada: os blocos são 
totalmente preenchidos; se um registro não 
cabe inteiramente na parte vazia do bloco, 
coloca o que couber e um ponteiro para o 
próximo bloco
 Organização não espalhada: registros não 
podem ser divididos. Cada bloco pode conter 
até fb registros.
 Perda de espaço de B - (fb*R) 
49
Alocação de blocos
 Os arquivos não são estáticos, eles crescem e diminuem
 Estratégias de alocação de blocos no disco devem 
considerar esse fato:
 Alocação contínua: leitura rápida; expansão difícil
 Alocação encadeada: leitura lenta; expansão rápida
 Alocação contínua combinada com encadeada: alocação 
encadeada de clusters de blocos contínuos (segmentos de 
arquivos ou extensões)
 Alocação indexada: um ou mais blocos de índices contém 
ponteiros para os blocos de fato
Número dos blocos Chave do primeiro registro de cada 
bloco
Bloco de índice
Blocos de dados contendo os registros (apenas a chave de cada registro aqui representada)
50
Buscas
 Queremos buscar um registro por sua chave
 O arquivo inteiro, com r registros, NÃO cabe na 
memória principal
 Como fazer uma busca eficiente, sabendo que 
cada acesso a dado pode exigir um acesso ao 
disco?
 Lembrando que nossa medida de complexidade é 
o nr de seeks (aproximado pelo nr de blocos 
acessados)
51
Acesso sequencial (não ordenado)
 O arquivo, de r registros espalhados em b blocos, não está 
ordenado nem indexado
 Inserção eficiente: O(1)
 Copia último bloco no buffer de memória
 Insere registro
 Reescreve bloco no disco
 Busca: sequencial não ordenada
 Tenho que olhar todos os blocos – O(b)
 Lembrando que a busca é por registros, não por blocos
 Remoção:
 Precisa achar onde está o registro – O(b)
 Exclui registro do bloco (que está no buffer) ou resetar bit para inválido
 Reescrever bloco de volta ao disco (com um espaço vazio)
=> Demanda uma reorganização periódica
52
Acesso sequencial (não ordenado)
 Modificação de registro de tamanho 
variável:
 Pode exigir a remoção de outros registros a 
serem inseridos em outros blocos
 Leitura ordenada: MUITO INEFICIENTE 
 Exige uma ordenação primeiro! (ordenação 
externa) 
53
Acesso sequencial ordenado
 Os r registros estão ordenados pela chave 
 Leitura ordenada eficiente (sequencial) – O(b)
 O próximo registro pode estar no mesmo bloco
 Mínimo / Máximo estão no cabeçalho do arquivo – O(1)
 Busca: dá para usar busca binária (baseada nos 
blocos!)
54
Acesso sequencial ordenado
 Os r registros estão ordenados pela chave 
 Leitura ordenada eficiente (sequencial) – O(b)
 O próximo registro pode estar no mesmo bloco
 Mínimo / Máximo estão no cabeçalho do arquivo – O(1)
 Busca: dá para usar busca binária (baseada nos 
blocos!)
Como é mesmo o algoritmo de busca binária (em memória)?
55
Acesso sequencial ordenado
 /* busca registro com chave k em um arquivo com b blocos */
buscaBinaria (k) {
 e ← 1; d← b;
 enquanto ( d >= e){
 m ← floor((e+d)/2);
 lê bloco m do disco para o buffer
 se (k < chave do primeiro registro do bloco m) d ← m – 1;
 senão se (k > chave do último registro do bloco m) e ← m+1;
 senão se (k = chave de algum registro do bloco m) retorma TRUE
 senão retorna FALSE
 } 
}
56
Acesso sequencial ordenado
 /* busca registro com chave k em um arquivo com b blocos */
buscaBinaria (k) {
 e ← 1; d← b;
 enquanto ( d >= e){
 m ← floor((e+d)/2);
 lê bloco m do disco para o buffer
 se (k < chave do primeiro registro do bloco m) d ← m – 1;
 senão se (k > chave do último registro do bloco m) e ← m+1;
 senão se (k = chave de algum registro do bloco m) retorma TRUE
 senão retorna FALSE
 } 
}
57
Acesso sequencial ordenado
 /* busca registro com chave k em um arquivo com b blocos */
buscaBinaria (k) {
 e ← 1; d← b;
 enquanto ( d >= e){
 m ← floor((e+d)/2);
 lê bloco m do disco para o buffer
 se (k < chave do primeiro registro do bloco m) d ← m – 1;
 senão se (k > chave do último registro do bloco m) e ← m+1;
 senão se (k = chave de algum registro do bloco m) retorma TRUE
 senão retorna FALSE
 } 
}
Complexidade: ?
58
Acesso sequencial ordenado
 /* busca registro com chave k em um arquivo com b blocos */
buscaBinaria (k) {
 e ← 1; d← b;
 enquanto ( d >= e){
 m ← floor((e+d)/2);
 lê bloco m do disco para o buffer
 se (k < chave do primeiro registro do bloco m) d ← m – 1;
 senão se (k > chave do último registro do bloco m) e ← m+1;
 senão se (k = chave de algum registro do bloco m) retorma TRUE
 senão retorna FALSE
 } 
}
Complexidade: O(lg b)
59
Acesso sequencial ordenado
 Inserção: cara! - O(b)
– Tem que achar a posição certa : O(lg b)
– Tem que abrir espaço para o registro (deslocar 
todos os registros com chave maior para frente) : 
O(?)
• Trazer o respectivo bloco para o buffer
• Deslocar os registros (o último registro vai para o 
próximo bloco, a não ser no caso de ser o último 
bloco e haver espaço para mais um registro)
• Salvar o bloco no disco 
60
Acesso sequencial ordenado
 Inserção: cara! - O(b)
– Tem que achar a posição certa : O(lg b)
– Tem que abrir espaço para o registro (deslocar 
todos os registros com chave maior para frente) : 
O(b)
• Trazer o respectivo bloco para o buffer
• Deslocar os registros (o último registro vai para o 
próximo bloco, a não ser no caso de ser o último 
bloco e haver espaço para mais um registro)
• Salvar o bloco no disco 
Alternativa para melhorar desempenho: deixar espaços vazios nos blocos (demanda 
Reorganização periódica e mais complicado para calcular localização dos registros)
61
Acesso sequencial ordenado
 Exclusão: cara pelos mesmos motivos! - O(b)
– Custo diminuído se usar bit válido/inválido para 
cada registro e efetuar reorganizações 
periódicas
62
Acesso sequencial ordenado
 Modificação: busca + atualização
– Caro se a atualização alterar o tamanho do 
registro (no caso de tamanho variável)
– Pior se for na chave: uma remoção e uma 
inserção 
63
Acesso sequencial indexado
 Índice primário: arquivo ORDENADO de registros de 
tamanho fixo contendo os campos <k,b>, sendo k a 
chave (primária) do primeiro registro (âncora) do bloco b 
O índice é ordenado 
pelo campo k
 Qual a vantagem?
Índice tem bi blocos, sendo bi << b (cada entrada é menor 
que um registro, e há só uma entrada por bloco)
→ busca binária no índice é muito mais rápida!!! O(lg bi)
64
Acesso sequencial indexado
 Índice primário: arquivo ORDENADO de registros de 
tamanho fixo contendo os campos <k,b>, sendo k a 
chave (primária) do primeiro registro (âncora) do bloco b 
O índice é ordenado 
pelo campo k
 Qual a vantagem? Índice tem bi blocos, sendo bi << B (no exemplo acima, bi = 1 
e B = 4), pois cada entrada é menor que um registro, e há só 
uma entrada por bloco de dado representado (b)
 → 
k
b
65
Acesso sequencial indexado
 Índice primário: arquivo ORDENADO de registros de 
tamanho fixo contendo os campos <k,b>, sendo k a 
chave (primária) do primeiro registro (âncora) do bloco b 
O índice é ordenado 
pelo campo k
 Qual a vantagem?
 Índice tem bi blocos, sendo bi << B (no exemplo acima, bi = 1 
e B = 4), pois cada entrada é menor que um registro, e há só 
uma entrada por bloco de dado representado (b)
 → busca binária no índice é muito mais rápida!!! O(lg bi)
k
b
66
Acesso sequencial indexado
 Índice primário: arquivo ORDENADO de registros de 
tamanho fixo contendo os campos <k,b>, sendo k a 
chave (primária) do primeiro registro (âncora) do bloco b 
O índice é ordenado 
pelo campo k
 Observação:
este é um índice esparso
se fosse denso, teria uma entrada por registro
b
k
67
Acesso sequencial indexado
 Problema: inserção / remoção
 Altera a posição em disco de vários registros
→ altera âncora de vários blocos
→ altera várias entradas do índice primário
 Formas de contornar o problema:
 Remoção por bits de validade
 Usar um arquivo desordenado de overflow (para as 
inserções, se necessário)
 Ou uma lista ligada de overflow (os registros do bloco e 
da lista podemm ser ordenados para melhorar a busca)
68
Acesso sequencial indexado
Índice de clustering
 Índice de clustering: arquivo ORDENADO de 
registros de tamanho fixo contendo os campos 
<c, b>, sendo c uma chave de classificação 
física que não possui valores distintos
 Uma entrada <c, b> para cada valor distinto de c, 
sendo b o primeiro bloco da primeira ocorrência 
da chave com valor c
69
Acesso sequencial indexado
Índice de clustering
 Inserção / remoção: ainda problemático, pois c 
ordena fisicamente os registros
 Alternativas: 
 espaços vagos para cada valor de c
 Remoção por bit de validade
70
Acesso sequencial indexado
Índice de clustering
 Busca:
 sem sucesso: NÃO acessa bloco de dado
 Quer só o primeiro registro ou todos?
 Primeiro: um bloco de dado (dado no índice)
 Todos: tem que ler q blocos (dá para saber o valor de 
q olhando para a próxima entrada no índice)
 Quanto maior o número de valores distintos, 
maior o tempo de busca binária nos índices
71
Acesso sequencial indexado
Índices secundários
 Índice secundário: arquivo ORDENADO de 
registros de tamanho fixo contendo os campos 
<i, w>, sendo i um campo de indexação que 
NÃO ordena fisicamente os registros, podendo 
ter valores distintos ou não
 w aponta para um bloco ou registro
 Podem existir vários índices secundários
72
Acesso sequencial indexado
Índices secundários
 Se i tem valores distintos, o índice é denso
 Se i tem valores duplicados:
 Opção 1: diversas entradas para um mesmo i, cada 
uma com w apontando para um registro (denso)
 Opção 2: 1 entrada para cada valor de i, e w 
multivalorado (campo de tamanho variável) aponta 
para blocos (esparso)
 Opção 3: uma entrada para cada valor de i e w 
(tamanho fixo) aponta para um bloco de ponteiros de 
registros (esparso) – mais usada 
Pensem na busca, inserção e remoção em cada caso...
73
Referências
 Slides da Profa. Graça (ICMC) - http://wiki.icmc.usp.br/index.php/SCC-
203_(gracan) (Arquivos 8, 9 e 12) 
 Slides do cap 6 do Ziviani
 GOODRICH et al, Data Structures and Algorithms in C++. Ed. John Wiley & 
Sons, Inc. 2nd ed. 2011. Seção 14.2
 ELMARIS, R.; NAVATHE, S. B. Fundamentals of Database Systems. 4 ed. Ed. 
Pearson-Addison Wesley. Cap 13 (até a seção 13.7).
 TANEMBAUM, A. S. & BOS, H. Modern Operating Systems. Pearson, 4th ed. 
2015
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73