Estrutura de Dados

Organização de arquivos para desempenho (II)

Recuperação de espaço não utilizado em arquivos

Os arquivos sofrem modificações quando

  • registros são adicionados
  • registros são eliminados
  • registros são atualizados

Os dois últimos casos, especificamente, podem criar espaços vagos no arquivo:

  • registros de tamanho variável – problemas na atualização se o novo registro é maior ou menor que o original.
  • registros de tamanho fixo ou variável – problemas na eliminação.

Como uma atualização sempre pode ser tratada como eliminação seguida de inserção, vamos enfatizar os problemas decorrentes da eliminação de registros.

1) Eliminação de registros e compactação

Compactação consiste na busca por regiões do arquivo que não contém dados, e posterior recuperação desses espaços perdidos. Os espaços vazios são provocados, por exemplo, pela eliminação de registros.

Qualquer técnica de eliminação de registros deve fornecer mecanismos para que possamos reconhecer quando uma área corresponde a um registro que foi eliminado. Geralmente, isso é feito através da colocação de uma marca especial. Por exemplo, no nosso arquivo de clientes, o caracter * poderia ser colocado no início do campo de sobrenome do cliente.

Uma vez que somos capazes de reconhecer um registro “apagado”, a próxima pergunta é como reutilizar o espaço vago. Abordagens baseadas em compactação não removem cada registro apagado imediatamente, mas ativam procedimentos de remoção periodicamente. Ou seja, os programas que acessam o arquivo devem incluir lógica para ignorar registros marcados como removidos (vantagem: é possível fazer um “undelete”, especialmente se a marca estiver em um campo separado!).

Depois de um certo tempo (ou de um certo número de registros removidos), o procedimento de compactação é ativado, e o espaço de todos os registros é recuperado de uma só vez. Se existe espaço suficiente, a maneira mais simples de compactar é através de um programa de cópia de arquivos que “pule” os registros apagados. É possível, apesar de mais complicado e mais lento, fazer a compactação no próprio arquivo. Ambas as abordagens podem ser usadas para registros de tamanho fixo ou variável.

2) Eliminação de registros de tamanho fixo para re-utilização dinamicamente

A compactação é a maneira mais simples de recuperar espaço inutilizado. Mas existem aplicações que são muito voláteis e interativas, para as quais essa abordagem não serve. Nessas situações, desejamos reutilizar o espaço imediatamente, ou o mais depressa possível. Neste caso, precisamos de um esquema de recuperação dinâmico. Vamos considerar, inicialmente, a situação em que os registros têm tamanho fixo, o que torna o problema mais simples.

Para implementar um mecanismo para remoção de registros com subsequente reutilização do espaço, devemos garantir que:

  • os registros apagados estejam marcados de alguma maneira; e
  • é possível identificar e localizar os espaços antes ocupados pelos registros apagados, para reutilizá-los.

Já vimos como resolver o primeiro problema. Quanto ao segundo, não queremos procurar registro por registro no arquivo, até encontrar um vazio, se existir (principalmente se o usuário estiver esperando, on-line!). Precisamos encontrar uma maneira de

    • saber imediatamente se existem ou não espaços “vazios” no arquivo; e
    • acessar diretamente estes espaços (sem fazer buscas!), se eles existirem.

Listas encadeadas: podemos utilizar uma lista encadeada composta pelos registros que são eliminados no arquivo (lista Dispo! cada registro contém um campo adicional, com a posição no arquivo do próximo registro na lista. Ao inserir um novo registro, inserimos na posição do primeiro registro desta lista, que nada mais é que a lista dos espaços disponíveis do arquivo!). Os dois problemas estão resolvidos!

Pilhas: No caso de inserirmos um novo registro sempre na posição correspondente ao início da lista Dispo, retirando da lista sempre o primeiro registro, a lista pode ser implementada como uma pilha.

Registros eliminados: listas e pilhas

Dado que os registros eliminados são mantidos numa Dispo, a questão é aonde manter e como usar a Dispo:

    • Como vimos, a Dispo pode ser formada pelos próprios registros eliminados, os quais, além da marca de eliminado, contém um ponteiro para o próximo registro.
    • O ponteiro para o primeiro registro da Dispo pode ser mantido no header do arquivo. Se a lista está vazia, esse ponteiro tem o valor -1, por exemplo. Observe que os ponteiros não são ponteiros no sentido de posições de memória, mas sim RRNs.
    • Quando é necessário espaço para um novo registro, o próximo registro disponível é buscado na Dispo.
    • Uma vez que a lista existe, precisamos de uma rotina que retorne ou o número do próximo registro disponível, ou o número do próximo registro a ser anexado ao final do arquivo, caso a Dispo esteja vazia.

passo a passo como fica o acesso a Dispo e ao disco, quando são realizadas 4 operações de inserção e a Dispo contém apenas 3 registros.

Mecanismos para gerenciar a lista Dispo é simples. Precisamos de um local para armazenar o RRN do primeiro registro disponível na lista Dispo, que pode ser no registro header no início do arquivo.

Um registro removido deve ser marcado como tal (colocando ‘* ‘ no início, por exemplo) e inserido na Dispo (colocando antes do ‘*’ o RRN do atual primeiro elemento, e colocando o RRN deste registro no campo correspondente do registro header!).

3) Eliminação de registros de tamanho variável para reutilização

Já vimos que para suportar a reutilização do espaço dos registros removidos precisamos:

    • de uma maneira de ligar os registros removidos em uma lista (i.e., um lugar para o campo de ligação);
    • de um algoritmo para acrescentar registros removidos à lista;
    • de um algoritmo para encontrar e remover registros da lista de disponíveis quando necessário;

Que tipo de organização de arquivo precisamos adotar para gerenciar uma lista Dispo com registros de tamanho variável? Como vamos apagar registros inteiros e colocá-los na Dispo, precisamos de uma organizacão em que o registro seja uma entidade claramente definida. Podemos, por exemplo, adotar a organizacão que mantém, antes de cada registro, o seu tamanho.

Podemos manter uma Dispo similar à mantida para registros de tamanho fixo, só que ao invés de usar RRNs para identificar a posição de registros, a posição de um registro disponível deve ser dada pelo seu offset em relação ao início do arquivo. Podemos colocar um ‘*’ na primeira posição do primeiro campo, seguido de um campo que indica a posição do próximo registro da Dispo. A diferença é que, ao invés de manter o RRN e calcular o offset do registro, mantemos diretamente o offset, que não pode ser calculado.

Inserção de registros: é necessário pesquisar

Com registros de tamanho fixo, podíamos tratar a Dispo como uma Pilha porque qualquer espaço vago tem o tamanho de um registro, e consegue acomodar o registro que vai ser inserido. No caso de registros de tamanho variável, existe uma condição extra para que o espaço vago de um registro possa ser reutilizado: o espaço deve ser do tamanho adequado (o registro a ser inserido precisa, no mínimo, caber no espaço que está sendo reutilizado.

É bastante provável que seja necessário buscar na Dispo por uma vaga de tamanho suficiente para acomodar o registro a ser inserido. O procedimento de inserção de um novo registro deve, portanto, percorrer a lista toda, se necessário, até localizar um espaço no qual o novo registro caiba. Já a inserção de vagas na Dispo depois da remoção de registros pode continuar a ser feita no início da lista.

Algoritmos de inserção e de remoção de registros para este caso.

4) Fragmentação da estrutura de armazenamento

Quando utilizamos uma vaga cujo tamanho é maior do que o realmente necessário para o novo registro, algum espaço vai ser desperdiçado no final do novo registro. Conseqüência: framentação interna! Isso é tanto pior pelo fato de que, se você está lembrado, utilizamos registros de tamanho variável justamente para diminuir a fragmentação interna!

Uma maneira de evitar isso seria, ao invés de alocar o espaço todo para o registro, alocar apenas o espaço realmente necessário, e retornar “a sobra” de volta para a Dispo! O problema é que se começarem a ser criadas “vagas” muito pequenas, elas não vão ser úteis para acomodar registro nenhum… a isto chamamos fragmentação externa!

Em outras palavras, a fragmentação interna é decorrente dos espaços perdidos dentro dos registros, enquanto que a fragmentção externa é decorrente dos espaços perfidos fora dos registros (espaços vazios reconhecidos e potencialmente utilizáveis, mas muito pequenos para serem realmente úteis).

No caso de utilizarmos a Dispo como indicado, o que fazer para evitar estes problemas? Uma maneira é através de compactação de memória (secundária, no caso). Poderiamos gerar novamente o arquivo quando a fragmentação externa se tornar intolerável. Outras abordagens são:

    • Se dois registros adjacentes têm sobra de espaço, podemos combinar o espaço desperdiçado formando um único registro vago, e colocá-lo na Dispo! (o ponto é: dois registros logicamente adjacentes são fisicamente adjacentes?) (compactação das vagas).
    • Tentar evitar o problema adotando outras estratégias de alocação. Pode-se escolher melhor a posição de inserção.

5) Estratégias de alocação

First-fit: A Dispo é organizada como no caso dos registros de tamanho fixo, sem qualquer critério especial, e a vaga alocada é a primeira encontrada (através de uma busca sequencial) que possuir tamanho suficiente.

Best-fit: a Dispo é organizada de modo que as vagas estejam em ordem crescente de tamanho. A vaga alocada é a primeira que possuir tamanho suficiente, que é a menor vaga na qual o registro cabe e, portantoaquela na qual menos espaço será desperdiçado. Esta estratégia tende a aumentar a fragmentação externa, e requer mais tempo para as remoções. Os tempos de busca para as inserções também tendem a aumentar com o tempo.

Worst-fit: a Dispo é organizada de modo que as vagas estejam em ordem decrescente de tamanho. A vaga alocada é a primeira (desde que possua tamanho suficiente): esta será a maior vaga na qual o registro cabe e, portanto, a que resulta na maior sobra de espaço. Esse espaço que sobra deve, então, ser devolvido à Dispo na forma de uma nova vaga.