단편화

3. 파일 시스템 단편화

파일 시스템 단편화는 다음의 여러 수준에서 발생할 수 있다.

• 개별 파일 내의 단편화
• 가용 공간 단편화
• 개별 파일 간의 참조 지역성 감소 (단, 서로 관련된 파일)^[4]
• 파일 시스템 자체를 위해 예약된 데이터 구조 또는 특수 파일 내의 단편화

3. 1. 파일 단편화

다음은 파일 단편화를 단순화하여 설명하는 예시이다. 새 디스크에 A, B, C, D, E라는 다섯 개의 파일이 순서대로 연속 저장되어 있고, 각 파일은 10개의 블록 공간을 사용한다고 가정한다. (여기서 블록 크기는 중요하지 않다.) 디스크의 나머지 공간은 하나의 빈 블록이다. 따라서 파일 E 이후에 추가 파일을 만들고 저장할 수 있다.

파일 B가 삭제되면, 10개 블록으로 구성된 두 번째 자유 공간 영역이 생성되어 디스크가 단편화된다. 빈 공간은 나중에 사용하기 위해 표시되고, 필요에 따라 다시 사용된다. 파일 시스템은 삭제 직후 디스크를 조각 모음할 수 있지만, 예측할 수 없는 시간에 심각한 성능 저하가 발생할 수 있다.

이제 7개의 공간이 필요한 F라는 새 파일은 파일 B가 있던 공간의 처음 7개 블록에 저장될 수 있고, 나머지 3개 블록은 계속 사용할 수 있다. 만약 3개의 블록만 필요한 G라는 새 파일이 추가되면, F 다음, C 앞에 있는 공간을 차지할 수 있다.

이후 F를 확장해야 하는 경우, 바로 뒤의 공간이 사용 중이므로 파일 시스템에는 세 가지 옵션이 있다.

# 어딘가에 새 블록을 추가하고 F에 두 번째 익스텐트가 있음을 나타낸다.

# 확장을 방해하는 파일을 다른 곳으로 이동하여 F가 계속 연결되도록 허용한다.

# 파일 F를 이동하여 새 크기의 하나의 연속 파일이 될 수 있도록 한다.

두 번째 옵션은 파일이 매우 큰 경우 세 번째 옵션과 마찬가지로 성능상의 이유로 실용적이지 않을 수 있다. 세 번째 옵션은 새 파일을 담을 수 있을 만큼 단일 연속된 자유 공간이 없는 경우 불가능하다. 따라서 일반적인 방법은 어딘가에 익스텐트를 만들고, 새 익스텐트를 이전 익스텐트에 연결하는 것이다.

파일 F의 끝에 추가된 자료는 동일한 익스텐트의 일부가 된다. 그러나 마지막 익스텐트 뒤에 사용할 수 있는 공간이 충분하지 않으면, 다른 익스텐트를 만들어야 한다. 결국 파일 시스템에는 여러 위치에 자유 세그먼트가 있으며, 일부 파일은 여러 익스텐트에 분산될 수 있다. 해당 파일(또는 모든 파일)에 대한 접근 시간이 과도하게 길어질 수 있다.

3. 2. 자유 공간 단편화

자유 공간 단편화는 파일 시스템에 새 파일이나 메타데이터를 쓸 수 있는 여러 개의 사용되지 않은 영역이 있을 때 발생한다. 원치 않는 자유 공간 단편화는 보통 파일 삭제 또는 잘림으로 인해 발생하지만, 파일 시스템은 근처 파일의 확장을 쉽게 하기 위해 자유 공간 조각("버블")을 의도적으로 삽입하기도 한다(단편화 방지 참조).

3. 3. 파일 분산 (참조 지역성 감소)

파일 분산은 관련 파일 조각화 또는 응용 프로그램 수준(파일) 조각화라고도 하며, 서로 관련 있는 파일들이 디스크 상에서 멀리 떨어져 저장되어 참조 지역성이 감소하는 현상을 의미한다. 파일 분산은 특정 응용 프로그램의 접근 패턴에 크게 의존하기 때문에, 다른 유형의 단편화보다 더 모호하고 객관적으로 측정하기 어렵다. 그러나 연구 결과에 따르면 가장 자주 접근되는 파일들이 초당 사용 가능한 디스크 처리량에 비해 작은 경향이 있어, 파일 분산은 성능에 큰 영향을 주는 중요한 유형의 단편화일 수 있다.^[4]

파일 분산을 방지하고 참조 지역성(파일 연속성)을 개선하려면 응용 프로그램 작동에 대한 가정이 필요하다. 일반적으로 더 작은 파일들을 단일 디렉터리 내에 함께 유지하고, 자연적인 파일 시스템 순서로 배치하는 것이 유용하다는 가정을 한다. 이는 대체로 합리적이지만, 항상 유효한 것은 아니다. 예를 들어, 응용 프로그램은 여러 디렉터리에 있는 파일들을 작성된 순서대로 읽을 수 있다. 따라서 모든 쓰기를 순차적으로 정렬하는 파일 시스템이 특정 응용 프로그램에서 더 빠르게 작동할 수도 있다.

4. 단편화 발생 원인

파일 시스템이 처음 초기화될 때는 비어 있는 공간이 연속적인 블록으로 구성된다. 그러나 파일 생성, 삭제, 수정이 반복되면서 단편화가 발생한다.

파일이 삭제되거나 크기가 줄어들면, 해당 공간은 새로운 빈 공간으로 남는다. 만약 새로운 파일이 이 빈 공간보다 크면, 파일은 여러 조각으로 나뉘어 저장된다. 또한, 기존 파일에 내용을 추가할 때 연속된 공간이 부족하면 파일은 여러 조각으로 나뉘어 저장된다. 시간이 지남에 따라 이러한 현상이 반복되면, 빈 공간과 파일들은 점점 더 조각화되는 경향이 있다.

이는 가변 길이로 메모리 관리를 수행하는 경우에도 발생한다. 메모리 영역 확보 및 해제가 반복되면, 연속된 빈 영역이 줄어들어 새로운 영역 할당이 어려워진다. 보조 기억 장치의 디스크 조각 모음은 이러한 외부 단편화를 해소하여 성능 향상을 돕는다.

5. 단편화의 영향

파일 시스템 조각화는 하드 디스크 드라이브의 순차적 접근 속도와 회전 지연 시간의 격차가 커지면서 더 큰 문제가 된다. 따라서 조각화는 파일 시스템 연구 및 설계에서 중요한 문제이다.^[8]

솔리드 스테이트 드라이브(SSD)는 기계적인 탐색 시간이 필요하지 않아 파일 시스템 조각화의 영향이 적다.^[10] 그러나 파일 시스템은 파일의 각 비연속 부분에 대한 추가 메타데이터를 저장해야 한다. 각 메타데이터 조각 자체는 공간을 차지하고 처리 능력과 프로세서 시간을 필요로 한다. 최대 조각화 한계에 도달하면 쓰기 요청이 실패한다.^[10]

보조 기억 장치의 디스크 조각 모음은 파일 시스템의 기능에 의해 메모리가 연속 영역이 아니어도 동작 가능하지만, 헤드의 시크에 의해 효율이 상당히 저하되는 경우에 외부 단편화를 해소하여 성능 향상을 도모하는 것이다.

6. 단편화 해결 기법

메모리 또는 디스크 단편화를 해결하기 위한 기본적인 방법으로는 통합과 집약 기법이 있다. 단편화 해결 기술은 ''선제적'' 방식과 ''사후적'' 방식으로 분류할 수 있는데, 이 기술들은 접근 패턴 예측의 어려움으로 인해 대부분 휴리스틱 성격을 가지며, 예상치 못한 작업 부하에서는 성능 저하가 발생할 수 있다.

6. 1. 메모리 단편화 해결

7. 단편화 방지 기법

파일 시스템이 처음 초기화될 때, 파티션에는 소수의 작은 내부 구조만 포함되어 있으며, 그 외에는 비어 있는 공간의 연속적인 블록일 뿐이다. NTFS나 ext2+와 같은 일부 파일 시스템은 특수한 목적으로 비어 있는 연속 영역을 미리 할당하기도 한다.NTFS 및 ext2+와 같은 일부 파일 시스템은 특수한 목적으로 비어 있는 연속 영역을 미리 할당할 수 있다.^영어 파일 시스템이 새로 생성된 파일을 파티션의 아무 곳에나 배치할 수 있다는 의미이다. 생성 후 얼마 동안은 파일을 최적에 가깝게 배치할 수 있다. 운영 체제 및 응용 소프트웨어를 설치하거나 아카이브를 압축 해제하면, 관련된 파일들이 서로 가깝게 배치되도록 별도의 파일들이 순차적으로 생성된다.

기존 파일이 삭제되거나 잘리면 새로운 자유 공간 영역이 만들어진다. 기존 파일에 내용을 추가하려고 할 때, 다른 파일이 이미 할당되어 있으면 파일이 끝났던 정확한 위치에서 쓰기를 다시 시작하는 것이 불가능한 경우가 많다. 따라서 새로운 조각을 할당해야 한다. 시간이 지남에 따라 파일의 추가/삭제가 반복되면, 자유 공간과 파일들이 점점 더 조각화되는 경향이 있다. 자유 공간 영역이 짧아지면 파일 시스템은 새 파일을 연속적으로 할당할 수 없게 되고, 파일을 여러 조각으로 나누어 저장해야 한다. 이는 파일 시스템이 가득 차서 큰 연속 자유 공간 영역을 사용할 수 없을 때 특히 문제가 된다.

단편화 방지 기법은 데이터를 디스크에 기록할 때 이러한 단편화를 최소화하는 기법이다. 대표적인 기법으로는 익스텐트 기반 할당, 파일 미리 할당, 지연 할당 등이 있다.

7. 1. 익스텐트 기반 할당

7. 2. 파일 미리 할당

7. 3. 지연 할당

참조

_[1] 뉴스 Should I defrag my SSD? https://www.pcgamer.[...] 2022-02-11
_[2] 웹사이트 Description of the ''can't extend'' error http://www.8bs.com/h[...]
_[3] 웹사이트 Possible data loss caused by the ''can't extend'' error http://8bs.com/mag/1[...]
_[4] 논문 A Large-Scale Study of File-System Contents 1999-06
_[5] 웹사이트 How NTFS reserves space for its Master File Table (MFT) https://learn.micros[...] Microsoft 2022-10-22
_[6] 웹사이트 DiskWarrior in Depth https://www.alsoft.c[...] 2022-10-22
_[7] 웹사이트 Maintaining Windows 2000 Peak Performance Through Defragmentation https://learn.micros[...] Microsoft 2022-10-22
_[8] 간행물 Future Storage Technologies: A Look Beyond the Horizon http://www.snwusa.co[...] Seagate Technology 2006-04-03
_[9] 간행물 Extent-like Performance from a UNIX File System http://www.cis.upenn[...] Sun Microsystems, Inc. 1991
_[10] 웹사이트 The real and complete story - Does Windows defragment your SSD? http://www.hanselman[...] 2014-12-03
_[11] 논문 Workload-Specific File System Benchmarks http://www.eecs.harv[...] Harvard University 2001-01
_[12] 논문 From ext3 to ext4: An Interview with Theodore Ts'o http://www.linux-mag[...] QuinStreet 2009-03-29
_[13] 웹사이트 Fragmentation in HFS Plus Volumes http://osxbook.com/s[...] 2004-05
_[14] 간행물 Scalability in the XFS File System http://www.soe.ucsc.[...] Silicon Graphics 1996-01
_[15] 웹사이트 The Reiser4 Filesystem http://video.google.[...] 2006-02-06
_[16] 서적 Mac OS X Internals: A Systems Approach Addison Wesley
_[17] 서적 Computer Architecture and Organization ''