Baixe o app para aproveitar ainda mais
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|
Compartilhar