디스크상에서 파일 시스템이 어떻게 구성되는지 알아보겠습니다.
연속 할당과 불연속 할당
파일 시스템은 기본적으로 메인 메모리를 페이징으로 관리하는 것과 유사한 방식을 사용합니다. 전체 디스크 공간을 블록이라는 균일한 공간으로 나누고 주소를 붙여서 관리합니다. 블록 하나 크기는 1~8KB입니다. 파일 시스템은 파일의 이름과 해당 파일이 시작하는 블록 주소를 가진 파일 테이블을 관리하고 사용합니다. 애플리케이션이 어떤 파일에서 데이터를 읽고자 하면 파일 관리자는 파일 테이블에서 해당 파일의 블록 주소를 찾아 그 위치에서 데이터를 읽어옵니다. 파일 테이블은 파티션 당 하나씩, 파티션 맨 앞에 존재합니다. 일반적으로 파일 하나는 여러 개의 블록을 사용합니다. 이런 여러 개의 블록을 어떻게 연결하는지에 따라 다음과 같이 나뉩니다.
- 연속 할당(contiguous allocation): 파일을 구성하는 데이터를 디스크상에 연속적으로 배열하는 방식입니다. 파일의 시작만 알면 전체 파일을 찾을 수 있습니다. 그러나 저장과 삭제를 반복하다보면 internal fragmentation이 발생해 연속 할당이 불가능하게 됩니다.
- 불연속 할당(non-contiguous allocation): 비어있는 블록에 데이터를 분산해 저장하고 이에 관한 정보를 파일 시스템이 관리하는 방식입니다. 연결 리스트를 사용한 연결 할당과 인덱스를 이용한 인덱스 할당을 통해 구현할 수 있습니다.
연결 할당(linked allocation, chained allocation)
연결 할당은 파일에 속한 데이터를 연결 리스트로 관리하는 방식입니다. 파일 테이블에는 시작 블록 주소만 저장하고, 나머지 데이터는 시작 블록부터 연결해 저장합니다. 파일 맨 끝에는 끝을 알리기 위해 널을 삽입합니다. 연결할당 방식은 테이블로 관리됩니다. 위도우의 FAT이 연결할당을 사용하는 예입니다. FAT은 파티션 전체 블록에 대한 정보를 가진 테이블로, 열 개수가 그 파티션에 존재하는 블록 개수와 같습니다. FAT의 구조는 다음과 같습니다.
FAT은 버전에 따라 FAT12, FAT16, FAT32가 존재합니다. 여기서 뒤에 붙는 숫자는 파일 할당 주소의 최대 크기입니다. 예컨대 FAT16의 최대 주소 크기는 2^16입니다.
테이블을 이용한 방식의 단점은 하나의 파티션이 사용할 수 있는 디스크 용량이 테이블의 주소 크기로 제한된다는 것입니다. 예를 들어 FAT16의 최대 파티션 크기는 32GB, FAT32는 최대 8TB와 단일 파일 크기 최대 4GB로 한정되어 있습니다. 때문에 64bit 윈도우는 NTFS 파일 시스템을 사용하고 있습니다.인덱스 할당(indexed allocation)
연결 할당이 가지는 최대 할당 크기에 제한이 있다는 단점을 극복하기 위해 나온 것이 인덱스를 이용한 인덱스 할당입니다. 인덱스 할당 방식에서는 파일 제어 테이블의 블록 포인터가 데이터 블록을 연결하는 것이 아닌, 데이터의 인덱스를 담고 있는 인덱스 블록을 연결합니다. 인덱스 블록에서 -1(NULL)은 파일의 끝을 알립니다.
유닉스의 Inode 방식이 인덱스 할당을 사용합니다. Inode 테이블은 다음과 같은 요소로 이루어져 있습니다. - 파일 제어 블록(file control block): 파일 소유자와 각종 속성을 나타냅니다. 파일에 대한 모든 권한의 정보를 포함하고 있기 때문에 슈퍼 블록(super block)이라고도 합니다.
- 블록 포인터(block pointer): 데이터가 있는 블록의 위치를 직접 연결하는 포인터입니다.
- 간접 포인터(indirect pointer): 크기가 작은 파일은 직접 연결된 블록 포인터로 빠르게 접근할 수 있습니다. 그러나 파일 크기가 커서 블록 포인터가 다 차면 인덱스 블록을 생성한 뒤 간접 포인터를 생성해 인덱스 블록을 연결합니다.
- 이중/삼중 간접 포인터: 통상적으로 인덱스 블록 하나는 256개의 블록을 지정할 수 있습니다. 파일 크기가 커서 인덱스 블록 하나로 통제가 안 된다면 이중 간접 포인터를, 그래도 안되면 삼중 간접 포인터를 사용합니다. 따라서 최대 256^3개의 인덱스 블록을 사용할 수 있습니다.
결론적으로 파일 크기가 작으면 블록을 직접 연결하고, 파일 크기가 크면 딘엑스 블록과 이를 연결하는 간접 포인터를 사용합니다. Inode 파일 시스템 구조는 다음과 같습니다.
디스크의 빈 공간 관리
디스크 블록 하나의 크기를 어떻게 정할 것인가는 메인 메모리의 분할 문제와 비슷합니다. 블록 크기 하나가 크면 적은 주소로 많은 양의 데이터를 관리할 수 있지만 internal fragmentation이 자주 발생합니다. 반대로 블록 크기가 작으면 많은 양의 블록 포인터가 필요합니다. 디스크에 파일을 저장할 때마다 모든 테이블을 뒤져서 빈 공간을 찾는 것은 비효율적이므로, 빈 블록의 정보만 모아놓은 빈 공간 리스트(free block list)를 유지합니다. 여기서 유의해야 할 점은, 데이터를 삭제할 때, 삭제할 데이터가 들어있는 블록 내부를 실제로 지우지 않는다는 것입니다. 대신, 빈 공간 리스트에 블록을 추가하고, 파일 테이블의 헤더를 삭제해서 파일이 삭제된 것으로 간주합니다. 파일이 사용했던 공간을 지우는 것은 많은 시간이 필요하기 때문입니다. 이 때문에 새로운 데이터가 블록을 덮어쓰지 않는 이상 데이터를 복구할 수 있는 여지가 존재합니다. 또 한, 빈 공간 리스트를 보고 새로운 블록을 할당할 때는 FIFO 방식으로 할당합니다. 이 때문에 디스크 복구나 휴지통에서 삭제한 파일을 되살리는 것이 가능합니다. 외부 저장 장치를 안전 제거하지 않고 강제로 분리한 경우엔 파일 시스템에 문제가 생길 수 있습니다. 데이터를 저장했지만 블록 포인터가ㅇ사라져서 데이터가 없어진 것처럼 보이는 경우, 디스크 빈 공간이 빈 공간 리스트에 등록되지 않아 사용할 수 없는 경우 등이 있습니다. 운영체제는 이런 오류를 수정하는 명령어를 가지고 있습니다. 윈도우는 chkdsk, 리눅스는 fsck입니다.
출처 - 쉽게 배우는 운영체제