Buscar

Aula de estrutura de dados II - Gerenciamento de espaço

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 22 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 22 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 22 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Arquivos
Gerenciamento de espaço
Gilda Aparecida de Assis
Gerenciamento de Espaço
• Organização dos arquivos com o objetivo de 
melhorar desempenho
 Arquivo alocado no menor número de blocos 
contíguos da mesma trilha ou mesmo cilindro
• Como? 
 Reuso do espaço alocado para o arquivo
 Compactação e compressão do arquivo
Gerenciamento de Espaço
• Operações básicas com registros em arquivos
 Inserção de registros: operação simples, final do 
arquivo
 Exclusão de registros: gera espaços vazios no arquivo
 Atualização de registros: P. ex., atualizar um registro 
que aumente de tamanho.
 O que fazer com os dados adicionais?
 Anexar ao final do arquivo e ligar as partes por “ponteiros”? 
Processamento dos registros fica mais complexo
 Apagar o registro original e reescrevê-lo todo no final do 
arquivo ? Ok, mas temos que reutilizar o espaço livre.
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Exclusão de registros
 Reconhecer áreas que foram apagadas
 Geralmente, áreas apagadas são marcadas
 com um marcador especial.
 Por exemplo: * |
 Recuperar e utilizar os espaços vazios
 Lista encadeada de registros excluídos no próprio arquivo
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Lista encadeada de registros excluídos no 
próprio arquivo
 Registros de tamanho fixo: pilha de RRNs 
vagos. Topo da pilha está no cabeçalho do 
arquivo. Cada registro excluído contém o RRN 
do próximo registro removido.
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Pilha de RRNs vagos de registros de tamanho fixo
Remoção do registro de RRN 2
e depois o RRN 5
-1RRN 2
2RRN 5topo 5
-1RRN 2
5RRN 3topo 3
2RRN 5
Remoção do registro de RRN 2 
depois o RRN 5 e por último RRN 3
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Por que Pilha de RRNs excluídos para registros de 
tamanho fixo?
 Como todos os registros têm o mesmo tamanho, não há 
razão para preferir um registro vago ao invés de outro. 
Portanto, não há motivo para manter a lista de vagos em 
uma lista com uma ordem específica. 
 Pilha é a forma mais simples de manipular a lista.
 Pilha resulta em um mínimo de operações para reorganizar a 
lista quando se empilha e desempilha registros vagos.
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Exclusão de registros de tamanho variável com 
indicador de tamanho
 Cada registro removido é marcado com um caracter 
específico no primeiro campo (*) seguido por um 
delimitador (|) e por um campo de byte offset 
apontando para o próximo registro removido na lista.
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Exclusão de registro de tamanho variável com indicador tamanho
Arquivo com 3 registros de tamanho variável
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Exclusão de registro de tamanho variável com indicador tamanho
Registro Morrison... foi removido
Registro Ham... foi inserido
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Exclusão de registro de tamanho variável com indicador tamanho
 Para reusar um registro ele deve ser “grande o suficiente” 
para armazenar o novo registro inserido
 A inserção de registros excluídos na lista pode ser feita na 
frente (como pilha) mas a remoção para reuso poderá ser 
feita em qualquer posição da lista.
 É necessário uma busca sequencial na lista para encontrar 
uma posição com espaço suficiente
 Se atingir o final da lista e não encontrar um registro 
reusável, o novo registro é adicionado no final do arquivo.
Gerenciamento de Espaço
• Reuso do espaço alocado para o arquivo
 Exclusão de registro de tamanho variável com indicador tamanho
Inserção de um novo registro de 55 bytes
Lista de 
disponíveis
Gerenciamento de Espaço
• Fragmentação Interna
• Desperdício de espaço dentro do registro
Registros de tamanho fixo, fragmentação interna
Registros de tamanho variável, sem fragmentação interna
Gerenciamento de Espaço
• Fragmentação Interna
• Desperdício de espaço dentro do registro
Registros de tamanho variável com fragmentação interna após 
remoção seguida de inserção de registro menor que removido
Gerenciamento de Espaço
• Fragmentação Interna
• Desperdício de espaço dentro do registro
Registros de tamanho variável sem fragmentação interna após remoção (64 
bytes) seguida de quebra do registro excluído em dois: novo (26 bytes) e 
vago (35 bytes, pois 2 bytes formam o tamanho do novo registro)
Gerenciamento de Espaço
• Fragmentação Externa
• Espaço não usado entre registros de um arquivo.
• Registros de tamanho variável: Espaços que “sobram” 
após a “divisão para reuso” podem ser tão pequenos que 
a probabilidade de que um novo registro caiba neles é 
próxima de zero, ou seja, o espaço é muito fragmentado 
para ser usado.
• Como solucionar?
• Coalescimento
• Estratégias de alocação de espaço
Gerenciamento de Espaço
• Estratégias de alocação de espaço
• Objetiva minimizar a fragmentação antes que ela 
aconteça adotando uma estratégia de reuso para 
selecionar o registro vago na lista de disponíveis
• First-fit: seleciona o primeiro registro que servir, 
independente se o registro vago é muito maior ou 
justo para o novo registro
Gerenciamento de Espaço
• Estratégias de alocação de espaço
• Best-fit: seleciona o menor registro que servir
• Organiza-se a lista de vagos de forma ascendente de 
tamanho, buscando o primeiro registro que couber
• Percorrer a lista tanto para inserir registros vagos 
quanto para remover (reusar) registros.
• O espaço que sobra pode ser tão pequeno que não dá 
para reutilizar, resultando em fragmentação externa.
• Além disso, com o passar do tempo aumenta o tempo 
de busca pelo menor registro que comporta o novo 
pois os registros menores e que provavelmente não 
serão usados são colocados no início da lista
Gerenciamento de Espaço
• Estratégias de alocação de espaço
• Worst-fit: seleciona o maior que servir
• Diminui a fragmentação externa
• Lista organizada de forma descendente de tamanho
• O processamento pode ser mais simples pois se o 
primeiro registro da lista de disponíveis não é grande o 
suficiente para armazenar o novo registro, nenhum 
outro da lista será. Busca é O(1).
• A porção que sobra ao inserir um novo registro no 
maior espaço disponível é tão grande quanto possível, 
diminuindo a probabilidade de fragmentação externa
Gerenciamento de Espaço
• Estratégias de alocação de espaço
• A melhor estratégia é a mais apropriada para uma situação 
particular
• Estratégias de alocação só fazem sentido para arquivos de 
registros de tamanho variável, para registros de tamanho 
fixo não há razão para preferir um registro ao outro.
• Se espaço está sendo desperdiçado com fragmentação 
interna, então a escolha é entre first-fit e best-fit. A 
estratégia worst-fit pode piorar esse problema 
• Se o espaço está sendo desperdiçado devido à 
fragmentação externa, deve-se considerar a worst-fit
Gerenciamento de Espaço
• Coalescimento
• Junção de espaços vazios fisicamente adjacentes para formar 
um registro/espaço disponível maior
• A lista de registros disponíveis para reuso não é mantida na 
ordem física dos registros. Dois registros excluídos podem ser 
fisicamente adjacentes e não serem adjacentes na lista.
• Utilizar dois encadeamentos (espaços vagos e uma lista com 
os espaços vagos em ordem crescente dos endereços)
Gerenciamento de Espaço
• Exercício: Utilizando estratégia Best-fit para gerenciamento de 
registros disponíveis no arquivo, seja as operações (I-inserção, A-
atualização, E-exclusão) e os registros com indicador de tamanho.Mostre como fica o arquivo de dados após cada operação.
Operação Registro
I Astolfo Barroso Pinto|25/06/1943|
I Antônio Renato Aragão|13/01/1935|
I Paulo Silvino|27/06/1939|
I Dani Calabresa|12/02/1981|
E Paulo Silvino|27/06/1939|
E Astolfo Barroso Pinto|25/06/1943|
I Nelson Freitas|25/07/1962|

Outros materiais