Bitmap de espaço livre - Free space bitmap

Os bitmaps de espaço livre são um método usado para rastrear setores alocados por alguns sistemas de arquivos . Embora o design mais simplista seja altamente ineficiente, implementações avançadas ou híbridas de bitmaps de espaço livre são usadas por alguns sistemas de arquivos modernos.

Exemplo

A forma mais simples de bitmap de espaço livre é uma matriz de bits , ou seja, um bloco de bits . Neste exemplo, um zero indicaria um setor livre, enquanto um um indica um setor em uso. Cada setor teria um tamanho fixo. Para fins explicativos, usaremos um disco rígido de 4  GB com setores de 4096 bytes e assumiremos que o próprio bitmap está armazenado em outro lugar. O disco de exemplo exigiria 1.048.576 bits, um para cada setor ou 1  MB . Aumentar o tamanho da unidade aumentará proporcionalmente o tamanho do bitmap, enquanto a multiplicação do tamanho do setor produzirá uma redução proporcional.

Quando o sistema operacional (SO) precisar gravar um arquivo, ele examinará o bitmap até encontrar locais livres suficientes para caber no arquivo. Se um arquivo de 12 KB fosse armazenado na unidade de exemplo, três bits zero seriam encontrados, alterados para uns, e os dados seriam gravados nos três setores representados por esses bits. Se o arquivo fosse posteriormente truncado para 8 KB, o bit do setor final seria zerado, indicando que ele está novamente disponível para uso.

Vantagens

  • Simples: cada bit corresponde diretamente a um setor
  • Verificação rápida de alocação de acesso aleatório: Verificar se um setor está livre é tão simples quanto verificar o bit correspondente
  • Exclusão rápida: Os dados não precisam ser substituídos na exclusão; virar o bit correspondente é suficiente
  • Custo fixo: uma vantagem e uma desvantagem. Outras técnicas para armazenar informações de espaço livre têm uma quantidade variável de sobrecarga, dependendo do número e do tamanho das extensões de espaço livre. Os bitmaps nunca podem funcionar tão bem quanto outras técnicas em suas respectivas circunstâncias ideais, mas também não sofrem casos patológicos. Como o bitmap nunca aumenta, diminui ou se move, menos pesquisas são necessárias para encontrar as informações desejadas
  • Baixa sobrecarga de armazenamento como uma porcentagem do tamanho da unidade: Mesmo com tamanhos de setor relativamente pequenos, o espaço de armazenamento necessário para o bitmap é pequeno. Uma unidade de 2  TB pode ser totalmente representada com um simples bitmap de 64  MB .

Desvantagens

  • Desperdício em discos maiores: o design simplista começa a desperdiçar grandes quantidades de espaço (em um sentido absoluto) para volumes extremamente grandes
  • Escalabilidade pobre: ​​embora o tamanho permaneça insignificante como uma porcentagem do tamanho do disco, a localização de espaço livre se torna mais lenta à medida que o disco é preenchido. Se o bitmap for maior do que a memória disponível , o desempenho cai drasticamente em todas as operações
  • Fragmentação : Se os setores livres forem pegos conforme são encontrados, as unidades com criação e exclusão freqüentes de arquivos se tornarão rapidamente fragmentadas. Se a pesquisa tentar localizar blocos contíguos, a localização de espaço livre se tornará muito mais lenta, mesmo para discos moderadamente cheios. Dados fragmentados também reduzem a velocidade de leitura em discos rígidos mecânicos devido à latência de busca da cabeça magnética, embora isso não seja um problema na memória flash .

Técnicas avançadas

Conforme o tamanho da unidade aumenta, a quantidade de tempo necessária para verificar o espaço livre pode se tornar irracional. Para resolver isso, as implementações do mundo real de bitmaps de espaço livre encontrarão maneiras de centralizar as informações no espaço livre. Uma abordagem é dividir o bitmap em vários pedaços. Um array separado então armazena o número de setores livres em cada bloco, de modo que os blocos com espaço insuficiente podem ser facilmente ignorados e a quantidade total de espaço livre é mais fácil de calcular. Encontrar espaço livre agora envolve pesquisar primeiro a matriz de resumo e, em seguida, pesquisar o fragmento de bitmap associado para os setores exatos disponíveis.

Essa abordagem reduz drasticamente o custo de localização de espaço livre, mas não ajuda no processo de liberação de espaço. Se o tamanho combinado da matriz de resumo e bitmap for maior do que pode ser facilmente armazenado na memória e um grande número de arquivos com setores espalhados for liberado, uma quantidade enorme de acesso ao disco é necessária para encontrar todos os setores, diminuir o contador de resumo e volte os bits para zero. Isso reduz muito os benefícios do bitmap, pois ele não está mais executando sua função de resumir o espaço livre rapidamente sem ler o disco.

Veja também

Referências