빈 공간 비트맵

Free-space bitmap

빈 공간 비트맵은 일부 파일 시스템에서 할당된 섹터를 추적하는 데 사용되는 한 가지 방법입니다.가장 단순한 설계는 매우 비효율적이지만 일부 최신 파일 시스템에서는 고급 또는 하이브리드 빈 공간 비트맵 구현이 사용됩니다.

예

빈 공간 비트맵의 가장 단순한 형태는 비트 배열, 즉 비트 블록입니다.이 예에서 0은 자유 섹터를 나타내고 1은 사용 중인 섹터를 나타냅니다.각 섹터는 고정된 크기일 것이다.설명을 위해 4096바이트 섹터가 있는 4GiB 하드 드라이브를 사용하고 비트맵 자체가 다른 곳에 저장되어 있다고 가정합니다.이 디스크 예에서는 섹터별로 1,048,576비트 또는 1MiB가 필요합니다.드라이브의 크기를 늘리면 비트맵의 크기가 비례적으로 증가하지만 섹터 크기를 곱하면 비례적으로 감소합니다.

operating system(OS)이 파일을 쓸 필요가 있는 경우는, 그 파일에 충분한 빈 장소를 찾을 때까지 비트맵을 스캔 합니다.12KiB 파일이 샘플드라이브에 저장되어 있는 경우, 3개의 제로비트가 검출되어 1로 변경되어 데이터는 이들 비트로 표현되는3개의 섹터에 걸쳐 써집니다.이후 파일이 8KiB로 잘린 경우 최종 섹터의 비트는 다시 0으로 설정되며 다시 사용할 수 있음을 나타냅니다.

이점

  • 심플: 각 비트는 섹터에 직접 대응합니다.
  • 고속 랜덤 액세스 할당 검사:섹터가 비어 있는지 확인하는 것은 해당 비트를 확인하는 것만큼이나 간단합니다.
  • 빠른 삭제: 삭제 [clarification needed]시 데이터를 덮어쓸 필요가 없습니다. 해당 비트를 뒤집으면 충분합니다.
  • 고정 비용:장점과 단점 둘 다.빈 공간 정보를 저장하는 다른 기법에서는 빈 공간 익스텐트의 수와 크기에 따라 오버헤드의 양이 달라집니다.비트맵은 각각의 이상적인 상황에서 다른 기술만큼 잘 할 수 없지만 병적인 경우도 겪지 않습니다.비트맵은 증가, 축소 또는 이동하지 않으므로 원하는 정보를 찾는 데 필요한 조회가 줄어듭니다.
  • 드라이브 크기에 비해 스토리지 오버헤드가 적습니다.비교적 작은 섹터 크기에서도 비트맵에 필요한 스토리지 공간은 작습니다.2TB 드라이브는 64MB 비트맵(4096바이트 섹터의 경우)으로 완전히 표현할 수 있습니다.

단점들

  • 대용량 디스크에서 낭비:심플한 디자인은 매우 큰 [1]볼륨을 위해 많은 공간(절대적인 의미)을 낭비하기 시작합니다.
  • 낮은 확장성:디스크 크기의 극히 일부로서 크기는 무시해도 되지만 디스크가 가득 찰수록 빈 공간을 찾는 속도가 느려집니다.비트맵이 사용 가능한 메모리보다 클 경우 모든 [1]작업에서 성능이 급격히 저하됩니다.
  • 플래그멘테이션:빈 섹터가 발견되면 파일 생성 및 삭제가 빈번한 드라이브는 빠르게 조각화됩니다.검색이 연속된 블록을 검색하려고 하면 여유 공간을 찾는 속도가 중간 정도만 채워진 디스크에서도 훨씬 느려집니다.단편화된 데이터는 자기 헤드의 지연을 요구하기 때문에 기계식 하드 드라이브의 읽기 속도도 느려지지만 플래시 메모리에서는 문제가 되지 않습니다.

고도의 기술

드라이브의 사이즈가 커짐에 따라, 빈 영역을 스캔 하는 데 필요한 시간이 부적절해질 수 있습니다.이를 해결하기 위해 빈 공간 비트맵의 실제 구현에서는 빈 공간에 대한 정보를 중앙 집중화하는 방법을 찾을 수 있습니다.한 가지 방법은 비트맵을 여러 청크로 분할하는 것입니다.그런 다음 각 청크에 사용 가능한 섹터 수를 저장하므로 공간이 부족한 청크는 쉽게 건너뛸 수 있으며 사용 가능한 총 공간을 계산하기가 더 쉽습니다.사용 가능한 공간을 찾으려면 먼저 요약 배열을 검색한 다음 관련 비트맵 청크를 검색하여 사용 가능한 [1]섹터를 검색합니다.

이 접근방식은 빈 공간을 찾는 비용을 대폭 절감하지만 공간을 확보하는 과정에는 도움이 되지 않습니다.요약 배열과 비트맵의 합계가 메모리에 쉽게 저장할 수 있는 크기보다 크고, 섹터가 산재한 다수의 파일이 해방된 경우 모든 섹터를 검색하여 요약 카운터를 줄이고 비트를 0으로 되돌리려면 엄청난 양의 디스크 액세스가 필요합니다.이렇게 하면 디스크에서 읽지 않고 빈 공간을 빠르게 요약하는 기능을 더 이상 수행하지 않으므로 비트맵의 이점이 크게 줄어듭니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c Bonwick, Jeff (2007-09-14). "Space Maps". Archived from the original on April 1, 2009. Retrieved 2009-10-02.