Organização de Arquivos - Organizando Arquivos para Desempenho (Parte 2)

Prévia do material em texto

Introduc¸a˜o a` Organizac¸a˜o de Arquivos: Aula 10
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade de Bras´ılia
1 / 44
Suma´rio
Organizando Arquivos para Desempenho
1 To´picos em Teoria da Informac¸a˜o
2 Compressa˜o de dados
3 Recuperando espac¸o em disco
4 Uma introduc¸a˜o a ordenac¸a˜o interna e busca bina´ria.
5 Ordenac¸a˜o de chaves (Keysorting ou Tag Sort).
6 Ordenac¸a˜o de arquivos grandes.
2 / 44
Compressa˜o de Dados
Codificac¸a˜o por Diciona´rio
A compressa˜o por diciona´rio baseia na criac¸a˜o de um diciona´rio com os co´digos das
letras mais frequentes.
O diciona´rio pode conter co´digos para palavras (conjunto de letras). Lembrando que
uma letra significa um s´ımbolo emitido pela fonte e uma palavra e´ um conjunto
poss´ıvel de s´ımbolos.
Este diciona´rio e´ compartilhado pelo codificador e decodificador.
O diciona´rio pode ser esta´tico ou dinaˆmico
Os algoritmos de codificac¸a˜o por diciona´rio mais comuns sa˜o os que usam dos
co´digos Lempel-Ziv.
3 / 44
Compressa˜o de Dados
Codificac¸a˜o por Diciona´rio: Lempel Ziv
Algoritmos LZ: Desenvolvido pelos israelenses Abraham Lempel e Jacob Ziv,
publicados em dois artigos em 1977 e 1978.
Cada artigo deu origem aos co´digos LZ77 e LZ78 respectivamente.
O LZ77 se baseia na ideia de que padro˜es similares va˜o estar posicionados a pouca
distancia um do outro no arquivo. Como isso na˜o e´ sempre verdade, o algoritmo
LZ78 normalmente e´ mais eficiente. Por isso, vamos estudar com mais detalhes o
LZ78.
Cada algoritmo (LZ77 e LZ78) tem va´riac¸o˜es. A mais famosa e´ a variac¸a˜o do LZ78
feita por Terry Welch conhecida como LZW.
Os comandos zip e unzip utilizam uma variac¸a˜o do LZ77 cohecida como LZH, e o
compress e uncompress do Unix utilizam as variac¸o˜es LZW e LZC do LZ78.
4 / 44
Compressa˜o de Dados
Caracter´ısticas do Algoritmo LZ78
Cada s´ımbolo e´ codificado por um par < i, c >, onde i e´ o ı´ndice correspondente a
letra (ou conjunto de letras) que ja´ existe no diciona´rio, e c e´ a palavra co´digo da
letra seguinte a` indicada por i.
O co´digo 0 e´ utilizado caso na˜o tenha sido encontrado nenhuma entrada no
diciona´rio para a letra sendo codificada.
Cada entrada novo no diciona´rio e´ uma letra concatenada com uma entrada ja´
existente.
5 / 44
Compressa˜o de Dados
Algoritmo LZ78
Vamos estudar o algoritmo com um exemplo. Digamos que queremos codificar a
seguinte sequeˆncia de letras:
wabba wabba wabba wabba woo woo woo
Onde espac¸o e´ codificado como o s´ımbolo ‘\s’.
Inicialmente o diciona´rio esta´ vazio logo, a primeira letra encontrada e´ codificada
como < 0, c(w) >. Onde c(W ) indica a palavra co´digo de para w.
Por exemplo, em um arquivo bina´rio podemos utilizar um co´digo bina´rio de 5 bits
para codificar as 26 letras minu´sculas do alfabeto, como w e´ a 23◦ letra, c(w) pode
ser 10111.
Num arquivo de texto c(w) pode ser a mesma letra w (que em ASCII ocupa 8 bits).
6 / 44
Compressa˜o de Dados
Algoritmo LZ78
wabba wabba wabba wabba woo woo woo
Seguindo o mesmo processo as pro´ximas duas letras sa˜o codificadas como
< 0, c(a) >, < 0, c(b) >.
A cada nova letra uma nova entrada no diciona´rio e´ criada. Logo, nosso diciona´rio,
por enquanto, e´:
I´ndice Entrada
1 w
2 a
3 b
7 / 44
Compressa˜o de Dados
Algoritmo LZ78
wabba wabba wabba wabba woo woo woo
Continuando, chegaremos na seguinte tabela:
I´ndice Entrada Sa´ıda Codificada
1 w < 0, c(w) >
2 a < 0, c(a) >
3 b < 0, c(b) >
4 ba < 3, C(a) >
5 \s < 0, c(\s) >
6 wa < 1, c(a) >
7 bb < 3, c(b) >
8 a\s < 2, c(\s) >
9 wab < 6, c(b) >
10 ba\s < 4, c(\s) >
. . . . . . . . .
Nota
Os ı´ndices podem ser codificados simplesmente com o co´digo bina´rio do ı´ndice.
8 / 44
Compressa˜o de Dados
A codificac¸a˜o do LZ78 tambe´m pode ser vista como uma a´rvore, pore´m NA˜O
necessariamente bina´ria (sera´ bina´ria se o alfabeto possui somente duas letras).
w a b \s
wa a\s ba bb
wab ba\s
0
1 2 3 5
6 8 4 7
9 10
9 / 44
Compressa˜o de Dados
Algoritmo LZ78
Na decodificac¸a˜o o decodificador vai gerando o diccionario assim que os pares
< i, c > sa˜o recebidos.
Ao enviar o primeiro par < i, c > na˜o e´ necessario enviar o ı´ndice 0, ja´ que e´ o
primerio s´ımbolo a ser codificado.
O comando ‘compact’ em Unix utiliza o Huffman adaptativo, o comando ‘compress’
utiliza o LZW.
Tipo Adaptative Huffman Lempel-Ziv
LATEX File 66% 44%
Speech File 65% 64%
Image File 94% 88%
Tabela: Comparativo: Huffman Adaptativo Vs Lempel-Ziv
10 / 44
Algoritmo LZ78
Algoritmo 1 LZ78
1: w ← NIL
2: while ¬EOF(input) do
3: K ← read(input)
4: if wK ∈ diciona´rio then
5: w ← wK
6: else
7: output(index(w),K)
8: diciona´rio← diciona´rio ∪ {wK}
9: w ← NIL
10: end if
11: end while
11 / 44
Compressa˜o de Dados
Compressa˜o com Perdas
Na compressa˜o com perdas na˜o somente elimina-se a redundaˆncia do sinal, mas
tambe´m a irrelevaˆncia dada uma certa aplicac¸a˜o.
Por exemplo, na˜o adianta mandar um sinal de v´ıdeo em resoluc¸a˜o 1080p se o v´ıdeo
vai ser assistido numa televisa˜o de resoluc¸a˜o 480p.
Na compressa˜o com perdas o sinal decodificado na˜o e´ exatamente igual ao original.
A compressa˜o com perdas consegue atingir maiores taxas de compressa˜o que a
compressa˜o sem perdas. Pore´m, isso sempre depende da qualidade desejada do sinal.
Exemplos de Compressa˜o com Perda
JPEG: Para codificar imagens. Existe o JPEG-LS que comprime sem perdas
MPEG-1 Layer 3 (MP3): Para codificar sinais de audio (mu´sica)
MPEG-2, MPEG-4,H.264/AVC: Para codificar sinais de v´ıdeo (seja para internet,
v´ıdeo conferencia, TV-digital, etc.)
12 / 44
Compressa˜o de Dados
Comandos de Compressa˜o no Unix
compact — Huffman Adaptativo
pack e unpack — Co´digos de Huffman byte por byte.
compress e uncompress — Lempel-Ziv (LZW e LZC)
zip e unzip — Lempel-Ziv (LZH)
gzip — Lempel-Ziv (LZ77)
bzip — Lempel-Ziv (LZ77/LZ78 e variac¸o˜es)
bzip2 — Transformada Burrows Wheeler + Huffman
tar — utiliza gzip ou bzip2
13 / 44
Func¸o˜es de Alto N´ıvel
Sistema Operacional: Func¸o˜es de Alto N´ıvel
Dentro das func¸o˜es de alto n´ıvel temos:
Estrutura do Sistema de Arquivos;
Seguranc¸a (gerencia de usua´rios);
Integridade;
Alocac¸a˜o de Espac¸o;
14 / 44
Func¸o˜es de Alto N´ıvel
Estrutura do Sistema de Arquivos
Como visto em aulas passadas a estrutura do sistema de arquivos e´ feito
normalmente em a´rvore. Onde os arquivos sa˜o armazenados em direto´rios, e cada
arquivo e identificado pelo seu nome e caminho, por exemplo:
/home/usr-12/myfile.dat.
Informac¸o˜es sobre os arquivos de um usua´rio sa˜o armazenados num arquivo especial
do direto´rio. Cada registro desse arquivo especial caracteriza um arquivo do usua´rio
que conte´m: nome, tamanho, enderec¸o, data da u´ltima modificac¸a˜o e outras
informac¸o˜es.
15 / 44
Func¸o˜es de Alto N´ıvel
Seguranc¸a
Em ambiente multiusua´rios, um usua´rio deve poder controlar o acesso a seus dados.
O SO deve conceder diferentes permisso˜es de acesso de leitura, escrita ou execuc¸a˜o
aos diferentes grupos de usua´rios.
16 / 44
Func¸o˜es de Alto N´ıvel
Integridade
Para garantir a integridade dos dados, torna-se importante a realizac¸a˜o de backups.
Os backups podem ser realizados manualmente pelo usua´rio ou de forma automa´tica
pelo SO (dependendo da configurac¸a˜o do SO feito pelo administrador do sistema e
da natureza dos dados).
17 / 44
Func¸o˜es de Alto N´ıvel
Alocac¸a˜o de Espac¸o
Alocac¸a˜o de Espac¸o na memo´ria secunda´ria e´ um dos recursos gerenciados pelo SO.
Vamos estudar com mais detalhe como e´ feito o gerenciamento da alocac¸a˜o de
espac¸o ao realizar operac¸o˜es de adic¸a˜o, eliminac¸a˜o e atualizac¸a˜o deregistros dentro
de um arquivo.
18 / 44
Recuperac¸a˜o de Espac¸o em Disco
Motivac¸a˜o
Suponha que num arquivo de registros de tamanho varia´vel, um registro foi
modificado de modo que o novo registro e´ maior do que o original.
O que voceˆ faz com os dados extras?
1 Colocar os dados adicionais do registro no final do arquivo e criar um ponteiro a partir
do espac¸o do registro original para a extensa˜o do registro?
2 Reescrever todo o registro no final do arquivo, deixando um “buraco” na posic¸a˜o do
registro original?
Desvantagens
Cada soluc¸a˜o tem suas desvantagens:
Na 1◦, o trabalho de processar o registro e´ mais lento do que era originalmente.
Na 2◦, o arquivo desperdic¸a espac¸o.
19 / 44
Recuperac¸a˜o de Espac¸o em Disco
Recuperac¸a˜o de Espac¸o em Disco
A partir de agora, veremos as maneiras como a organizac¸a˜o do arquivo se deteriora a
medida que ele vai sendo modificado. Tais modificac¸o˜es podem ser ocasionadas por:
1 Adic¸a˜o de novos registros.
2 Atualizac¸a˜o de registros.
3 Eliminac¸a˜o de registros.
20 / 44
Recuperac¸a˜o de Espac¸o em Disco
Recuperac¸a˜o de Espac¸o em Disco
Adic¸a˜o de Registo:
Esta operac¸a˜o na˜o deteriora a organizac¸a˜o do arquivo. Ja´ que o registro pode ser
adicionado no final do arquivo.
As questo˜es de manutenc¸a˜o se tornam mais complicadas quando:
Atualizamos registro de comprimento varia´vel;
O novo registro e´ menor (atualizar no mesmo lugar gera perda de espac¸o);
O novo registro e´ maior (e´ necessa´rio eliminar o registro velho e incluir o novo);
Eliminamos um registro de comprimento fixo ou varia´vel;
A eliminac¸a˜o e´ lo´gica. No entanto, devemos pensar em uma maneira de poder reusar
esse espac¸o.
Observac¸a˜o
Como a atualizac¸a˜o pode ser vista como um eliminac¸a˜o seguida de uma adic¸a˜o, vamos
focar na questa˜o da eliminac¸a˜o de um registro e reuso do espac¸o.
21 / 44
Eliminac¸a˜o e Compactac¸a˜o
Estrate´gia de Eliminac¸a˜o (fixo ou varia´vel)
Qualquer que seja a estrate´gia, e´ necessa´rio que o registro eliminado possa ser
identifica´vel.
Por exemplo:
Colocar um caractere especial como * ou um $ num campo do registro;
Colocar um campo fixo no registro para indicar o status do registro.
Estrate´gia de Recuperac¸a˜o (fixo ou varia´vel)
Deixar o registro eliminado por um tempo (os programas devem ignorar estes
registros eliminados);
Depois, recuperamos todos os espac¸os de uma so´ vez ao:
Copiar os registros va´lidos para uma nova a´rea de armazenamento em disco e devolver
a a´rea antiga;
Compactar no mesmo lugar, lendo e regravando apenas os registros va´lidos.
22 / 44
Eliminando Registros de Tamanho Fixo
Eliminac¸a˜o
Marcar o registro eliminado com um *, por exemplo.
Para reutilizar o espac¸o ao inserirmos um novo registro devemos:
Varrer o arquivo sequencialmente antes de adicionar o novo registro, procurando
registro por registro, ate´ que um registro eliminado seja encontrado. Se o programa
atingir o final do arquivo e nenhum registro eliminado for encontrado, enta˜o o novo
registro deve ser adicionado no final do arquivo
Processo muito lento!
23 / 44
Eliminando Registros de Tamanho Fixo
Eliminac¸a˜o
Para reutilizar o espac¸o de um registro eliminado, no´s precisamos: uma maneira de
saber, imediatamente, se existem espac¸os vazios no arquivo, e uma maneira de pular
diretamente para estes espac¸os, caso existam.
Soluc¸a˜o
Utilizar uma lista encadeada contendo todos os registros eliminados.
Lista Encadeada: estrutura de dados na qual cada elemento ou no´ conte´m uma
refereˆncia ao seu sucessor na lista.
Como todos os registros sa˜o do mesmo tamanho, na˜o faz diferencia qual registro da
lista e´ reutilizado.
A maneira mais simples de manusear esta lista, e´ como uma pilha (a pilha e´ mais
fa´cil de implementar). Uma pilha e´ uma lista na qual todas as inserc¸o˜es e remoc¸o˜es
dos no´s acontece num dos finais da lista (topo).
Vamos referir a esta pilha, contendo os registros que se tornaram espac¸os
dispon´ıveis, como PED (pilha de espac¸os dispon´ıveis).
24 / 44
Eliminando Registros de Tamanho Fixo
PED em Arquivo com Registro Cabec¸alho
O cabec¸alho e´ o primeiro registro do arquivo, contendo:
O topo da PED conte´m o NRR (nu´mero relativo do registro) do u´ltimo registro
eliminado.
Se topo(PED) < 0, enta˜o a pilha esta´ vazia (-1 representa um ponteiro nulo).
Quando um registro e´ eliminado, ele e´ marcado como eliminado e inserido na PED
(ou seja, tera´ um ponteiro para o registro eliminado antes dele). O espac¸o do
registro esta´ na mesma posic¸a˜o que antes, mas logicamente foi inserido na PED.
A PED pode ser um arquivo separado. Pore´m, e´ mais eficiente utilizar um campo do
registro para indicar a NRR do pro´ximo registro dispon´ıvel.
25 / 44
Eliminando Registro de Tamanho Fixo
João Pedro Luiz *-1 Paula *3 Rui
0 1 2 3 4 5 6
Topo da PED = 5
João *5 Luiz *-1 Paula *3 Rui
0 1 2 3 4 5 6
Topo da PED = 1
João 1° NovoRegistro Luiz Paula Rui
0 1 2 3 4 5 6
Topo da PED = -1
2° Novo
Registro
3° Novo
Registro
Figura: Exemplo de configurac¸o˜es da PED
26 / 44
Eliminando Registros de Tamanho Varia´vel
Eliminando Registros de Tamanho Varia´vel
Para dar suporte a reutilizac¸a˜o de registros de tamanho varia´vel atrave´s de uma lista de
espac¸o dispon´ıvel (LED), no´s precisamos de:
Uma maneira interligar os registros eliminados na LED (ou seja, um lugar para
colocar os apontadores).
Um algoritmo para incluir na LED novos registros eliminados.
Um algoritmo para achar e remover da LED os espac¸os dispon´ıveis quando se vai
reutiliza´-los.
27 / 44
Eliminando Registros de Tamanho Varia´vel
LED e Espac¸os Livres
A cabec¸a/topo da LED fica no registro cabec¸alho.
Estrutura dos registros normais (com reuso) se da´ como:
< tamanho registro > | < c1 > | < c2 > | . . . | < cn > | . . . . . .
Onde . . . . . . indica a fragmentac¸a˜o interna do registro (espac¸o perdido no registro,
menor que o original liberado).
Registro eliminado:
< tamanho do registro > ∗ < ponteiro > . . . . . .
Onde:
* indica que o registro esta´ livre (foi eliminado logicamente).
< ponteiro > e´ bina´rio e aponta para o primeiro byte do pro´ximo registro livre.
. . . . . . e´ o espac¸o restante do registro livre.
Observac¸a˜o
Na˜o podemos usar o NRR como ponteiro!
28 / 44
Eliminando Registro de Tamanho Varia´vel
Exemplo
Topo da LED = -1
40 Ames|John|123 Maple|Stillwater|OK|74075|64 Morrison|Sebastian
|9035 South Hillcrest|Forest Village|OK|74820|45 Brown|Martha|62
5 Kimbark|Des Moines|IA|50311|
Apo´s a eliminac¸a˜o do segundo registro, temos:
Topo da LED: 43
40 Ames|John|123 Maple|Stillwater|OK|74075|64 *| -1.............
..............................................45 Brown|Martha|62
5 Kimbark|Des Moines|IA|50311|
29 / 44
Eliminando Registro de Tamanho Varia´vel
Inclusa˜o e Remoc¸a˜o de Registros na LED
Na inclusa˜o, trata-se a LED como uma PED: adiciona-se o registro livre na
cabec¸a/topo da LED.
Na remoc¸a˜o, trata-se a LED como uma lista:busca-se o primeiro espac¸o na LED, tal
que:
|registro novo| ≤ |espac¸o|
Note que podemos pesquisar a LED inteira, sem achar o espac¸o adequado.
Se tal espac¸o existe, enta˜o ele e´ removido da LED e reusado.
Sena˜o o registro novo e´ colocado no fim do arquivo.
Observac¸a˜o
Essa estrate´gia pode levar a uma alta fragmentac¸a˜o interna dos registros.
Relembrando
Fragmentac¸a˜o interna e´ a perda de espac¸o ao n´ıvel de cada registro (ocorre por que o
espac¸o do registro na˜o e´ totalmente utilizado).
30 / 44
Eliminando Registro de Tamanho Varia´vel
Exemplo
Remoc¸a˜o de um registro da LED para armazenar um novo registro que requer 55 bytes
de espac¸o:
Nil47 38 72 68
47 38 Nil68
Oregistro de tamanho 72 e´ retirado da LED.
31 / 44
Fragmentac¸a˜o Interna
Fragmentac¸a˜o Interna em Registros de Tamanho Fixo
Suponha registros fixos de 64 bytes:
Ames|John|123 Maple|Stillwater|OK|74075|........................
Morrison|Sebastian|9035 South Hillcrest|Forest Village|OK|74820|
Brown|Martha|625 Kimbark|Des Moines|IA|50311|...................
Temos fragmentac¸a˜o interna representado pelos . . . . . . . . .
Alternativas:
Permitir que os campos possam variar.
Provoca perdas no final do registro.
Dimensionar cada campo pelo maior tamanho da informac¸a˜o .
Provoca perdas ao n´ıvel de campo.
Ambas alternativas provocam fragmentac¸a˜o interna.
32 / 44
Fragmentac¸a˜o Interna
Fragmentac¸a˜o Interna em Registros de Tamanho Varia´vel
Suponha registros de tamanho varia´vel com indicador de tamanho:
40 Ames|John|123 Maple|Stillwater|OK|74075|64 Morrison|Sebastian
|9035 South Hillcrest|Forest Village|OK|74820|45 Brown|Martha|62
5 Kimbark|Des Moines|IA|50311|
A fragmentac¸a˜o interna e´ eliminada na criac¸a˜o dos registros:
Usa-se so´ o espac¸o requerido.
Nos casos de eliminac¸a˜o de registro e reuso de espac¸os dispon´ıveis por registros
menores do que os originais:
Volta o problema da fragmentac¸a˜o interna.
33 / 44
Fragmentac¸a˜o Interna
Exemplo: Fragmentac¸a˜o Interna em Registros de Tamanho Varia´vel
Topo da LED: 43
40 Ames|John|123 Maple|Stillwater|OK|74075|64 *| -1.............
..............................................45 Brown|Martha|62
5 Kimbark|Des Moines|IA|50311|
Apo´s a ocupac¸a˜o do espac¸o do 2◦ registro por um novo registro menor que o anterior
temos:
Topo da LED: -1
40 Ames|John|123 Maple|Stillwater|OK|74075|64 Ham|Al|28 Elm|Ada|
OK|70332|.....................................45 Brown|Martha|62
5 Kimbark|Des Moines|IA|50311|
Presenc¸a de Fragmentac¸a˜o Interna!
34 / 44
Fragmentac¸a˜o Interna
Soluc¸a˜o: LED com Reuso e com Liberac¸a˜o de Espac¸o
Pega-se da LED um espac¸o dispon´ıvel:
Ocupa-se a parte final do espac¸o com o novo registro.
Altera-se, na LED, o tamanho do espac¸o inicial.
Essa entrada e´ mantida na LED para uso futuro.
Exceto pelo tamanho desse espac¸o, a LED na˜o e´ alterada.
Topo da LED:43
40 Ames|John|123 Maple|Stillwater|OK|74075|35 *| -1.............
.................26 Ham|Al|28 Elm|Ada|OK|70332|45 Brown|Martha|6
25 Kimbark|Des Moines|IA|50311|
35 / 44
Fragmentac¸a˜o Externa
Fragmentac¸a˜o Externa
Da soluc¸a˜o anterior, temos um problema: a parte que fica na LED pode ser muito
pequena!
Se tal espac¸o na˜o puder ser usado por nenhum outro registro, temos a fragmentac¸a˜o
externa.
Topo da LED: 43
40 Ames|John|123 Maple|Stillwater|OK|74075|35 *| -1.............
.................26 Ham|Al|28 Elm|Ada|OK|70332|45 Brown|Martha|6
25 Kimbark|Des Moines|IA|50311|
Apo´s a ocupac¸a˜o de mais um registro de 25 bytes na a´rea dispon´ıvel na LED, temos:
Topo da LED: 43
40 Ames|John|123 Maple|Stillwater|OK|74075|8 *| -1...25 Lee|Ed|R
t 2|Ada|OK|74820|26 Ham|Al|28 Elm|Ada|OK|70332|45 Brown|Martha|6
25 Kimbark|Des Moines|IA|50311|
36 / 44
Fragmentac¸a˜o Interna
Meios de Combater a Fragmentac¸a˜o Interna
Gerar um novo arquivo (quando a fragmentac¸a˜o ficar intolera´vel) eliminando os
espac¸os dos registros dispon´ıveis e devolvendo a a´rea do arquivo antigo ao sistema.
Concatenar espac¸os adjacentes na LED: combina´-los para fazer deles um u´nico
registro maior.
Tentar minimizar a fragmentac¸a˜o antes que ela ocorra, adotando uma das seguintes
estrate´gias de reuso:
1 Primeiro ajuste.
2 Melhor ajuste.
3 Pior ajuste.
37 / 44
Fragmentac¸a˜o Interna
Fragmentac¸a˜o Interna: Primeiro Ajuste
A LED na˜o esta´ ordenada.
Os espac¸os gerados pela eliminac¸a˜o de registros sa˜o inclu´ıdos na cabec¸a/topo da
lista.
Quando se quer introduzir um registro novo:
a LED e´ percorrida ate´ que |registro| ≤ |espac¸oi| ou que o fim da lista seja atingido.
Se um espac¸o foi encontrado, grave o registro nele e libere o espac¸o restante.
Sena˜o, inclua o registro no fim do arquivo.
38 / 44
Fragmentac¸a˜o Interna
Fragmentac¸a˜o Interna: Melhor Ajuste
A LED aqui esta´ ordenada em ordem crescente de tamanho dos espac¸os.
Os espac¸os gerados sa˜o inclu´ıdos na posic¸a˜o correta da LED (esse esforc¸o pode ser
significativo!)
Na inclusa˜o de um novo registro:
Percorremos a LED ate´ que |registro| ≤ |espac¸oi|.
Gravamos o registro em espac¸oi.
Observac¸a˜o
Neste me´todo, o espac¸o encontrado na LED e´ o menor espac¸o poss´ıvel dispon´ıvel para o
novo registro, pore´m, a sobra pode ser pequena demais e na˜o ser reusa´vel por nenhum
outro registro. gerando assim a fragmentac¸a˜o externa.
39 / 44
Melhor Ajuste: Vantagens e Desvantagens
Vantagens
Como esse e´ o menor espac¸o existente na LED que suporta o registro novo, o desperd´ıcio
e´ o menor poss´ıvel. Mesmo que ele gere fragmentac¸a˜o externa.
Desvantagens
Os primeiros elementos da LED, de ta˜o pequenos, podem na˜o ser aproveita´veis,
aumentando assim o tempo da busca ate´ se encontrar o espac¸o adequado.
A inclusa˜o dos espac¸os na LED pode ser lenta, requerendo enta˜o um tempo significativo.
40 / 44
Fragmentac¸a˜o Interna
Pior Ajuste
A LED aqui esta´ ordenada em ordem decrescente de tamanho dos espac¸os.
Os espac¸os gerados sa˜o inclu´ıdos na posic¸a˜o correta da LED (o que pode gerar um
esforc¸o significativo!).
Na inclusa˜o de um novo registro no arquivo:
Usamos o registro no topo da LED (vista como pilha).
Gravamos o registro nesse espac¸o.
Essa sobra e´ a maior poss´ıvel, aumentando assim as chances de sua reutilizac¸a˜o!
41 / 44
Pior Ajuste: Vantagens e Desvantagens
Vantagens
A busca pelo espac¸o na LED e´ ra´pida:
Pegamos o primeiro elemento da LED.
Se o primeiro elemento da LED na˜o for grande o bastante para o novo registro,
nenhum dos outros elementos sera˜o.
Diminui a chance de fragmentac¸a˜o externa: os espac¸os gerados pela reutilizac¸a˜o sa˜o
os maiores poss´ıveis.
Desvantagens
A inclusa˜o do espac¸o na LED ordenada pelo tamanho e´ custosa.
42 / 44
Fragmentac¸a˜o Interna
Conclusa˜o
A estrate´gia de reuso somente se aplica a:
Arquivos vola´teis.
Arquivos de registro com comprimento varia´vel.
Se o espac¸o e´ perdido por fragmentac¸a˜o interna (ou seja, esta˜o sobrando muitos espac¸os
dentro dos registros), a escolha recai sobre uma das estrate´gias:
Primeiro ajuste.
Melhor ajuste.
Se a perda e´ por fragmentac¸a˜o externa (ou seja, esta˜o sobrando muitos espac¸os que na˜o
utiliza´veis) enta˜o considere a estrate´gia do:
Pior ajuste.
43 / 44
Pro´xima Aula
Pro´xima Aula
Organizando Arquivos para Desempenho (continuac¸a˜o).
44 / 44