[운영체제] 파일 시스템

xoey·2024년 11월 11일

CS 운영체제

운영체제

목록 보기

15/15

컴퓨터 시스템에서 가장 중요한 자원은 CPU, 메인 메모리이고, 그 다음으로 중요한 것이 하드 디스크와 같은 보조 기억 장치이다.

하드 디스크에는 파일 시스템(File System)이 존재하며, 이 파일 시스템은 계층 구조로 이루어져 있다. 예를 들어, 윈도우의 루트 디렉토리 아래에 여러 폴더와 파일이 위치하는 것처럼 말이다.

파일이 하드 디스크에 어떻게 할당되는지 알아보자.

하드 디스크는 다음과 같이 구성되어 있다.

플래터(Platter): 하드 디스크의 데이터를 저장하는 원형의 디스크로, 데이터를 실제로 저장하는 물리적인 공간이다. 하드 디스크에는 여러 개의 플래터가 쌓여 있으며, 각 플래터는 양면에 데이터를 기록할 수 있다. 플래터는 자성 물질로 코딩되어 있어, 디스크 헤드가 자성을 읽거나 변경함으로써 데이터를 기록하거나 읽어온다.
트랙(Track): 플래터의 표면에 기록된 원형 경로로, 데이터를 저장하는 단위이다. 플래터는 수많은 동심원 모양의 트랙으로 나뉘어져 있다. 하드 디스크의 디스크 헤드가 특정 트랙 위에서 데이터를 읽거나 쓴다.
실린더(Cylinder): 여러 개의 플래터가 쌓여있을 때, 같은 위치에 있는 트랙들을 묶어 실린더라고 부른다. 즉, 상하로 쌓인 여러 플래터의 동일 위치에 있는 트랙들이 모여 하나의 실린더를 형성한다. 데이터를 읽어올 때, 디스크 헤드는 트랙의 위치에 맞춰 실린더 단위로 데이터를 읽어들인다.
섹터(Sector): 트랙은 여러 개의 작은 구획으로 나누어져 있는데, 이 각각의 구획을 섹터라고 한다. 섹터는 하드 디스크에서 데이터를 저장하고 읽어내는 최소 단위이다. 일반적으로 한 섹터는 512bytes 또는 4KB 크기의 데이터를 저장할 수 있다.

섹터는 몇 개가 모여 블록(Block)을 이룬다. 하드 디스크는 블록 단위로 데이터를 읽고 쓰며, 이때문에 하드 디스크는 블록 디바이스(Block Device)라고도 불린다.

cf) 캐릭터 디바이스(Character Device): 글자 단위로 자료가 이동된다. (e.g. 키보드)

예시로 test.txt라는 파일에 ‘a’라는 글자를 저장한다고 가정해 보자. ‘a’는 1byte의 크기를 가지지만, 하드 디스크는 블록 단위로 데이터를 처리하기 때문에, 이 작은 파일을 저장할 때에도 최소 한 블록(일반적으로 4KB)이 할당된다. 결과적으로 1byte의 파일을 위해 4KB의 디스크 공간이 사용되며, 남은 공간은 비어있지만 사용할 수 없는 상태가 된다.

이 예시를 통해 디스크가 블록 단위로 데이터를 읽고 쓴다는 것을 알 수 있다. 블록 크기는 파일 시스템에 의해 결정되며, 작은 파일도 최소 블록 크기만큼의 공간을 차지한다.

디스크는 pool of free blocks로 구성되어 있으며, 이들은 각 파일에 할당된다. 각각의 파일에 대해 free blocks를 어떻게 할당하고, 어떻게 관리할지 알아보자.

1. 파일 할당

위 그림은 pool of free blocks를 논리적인 그림으로 나타낸 모습이다. 블록마다 인덱스 번호가 설정되어 있다.

파일에 블록을 할당하는 방식은 크게 연속 할당, 연결 할당, 색인 할당 세 가지로 나누어 볼 수 있다.

1.1. 연속 할당(Contiguous Allocation)

각 파일에 대해 디스크 상에 연속된 블록을 할당하는 방식이다.

예를 들어 f1이라는 파일이 5KB를 필요로 한다면, 디스크에서 5KB 크기의 연속된 블록을 할당해준다.

1.1.1. 특징

연속 할당 방식은 파일을 읽을 때 디스크 헤드를 한 번만 움직이면 연속적으로 파일을 읽을 수 있어 속도가 빠르다. 옛날 60-70년대의 IBM에서 많이 사용됐던 방법이며, 동영상, 음악, VOD와 같이 연속적으로 재생하는 용량이 큰 파일에 적합하다.

또한 이 방식은 파일을 순서대로 읽는 순차 접근(Sequential Access)과 특정 부분을 바로 읽을 수 있는 직접 접근(Direct Access) 모두 가능하다.

🔎 디렉토리(Directory)

디렉토리는 파일에 대한 메타데이터를 저장하는 파일 시스템의 테이블 역할을 한다.

디렉토리에는 파일의 이름, 크기, 생성 시간, 소유자와 같은 정보뿐만 아니라 시작 블록 번호와 파일의 크기도 저장된다. 연속 할당에서는 디렉토리에 파일의 시작 블록 번호와 연속된 블록의 크기만 있으면 해당 파일에 directly access할 수 있다.
file name: f1
file size: 5 bytes
...
-----------------
block number: 0

1.1.2. 단점

이 방식은 현재 거의 사용되지 않는데, 외부 단편화가 큰 문제로 작용하기 때문이다. 파일이 삭제되면 그 공간은 hole로 남게 되고, 다양한 크기의 파일들이 생성되고 삭제되면서 빈 공간이 조각난다. 이로 인해 충분한 연속된 공간을 찾기 어려워지고, 파일을 저장하지 못하는 상황이 발생한다. 이를 해결하기 위해 compaction을 통해 빈 공간을 모으는 작업이 필요한데, 이 작업은 매우 비효율적이고 시간이 많이 소요된다. (80년대 MS-DOS에서는 이를 해결하기 위해 compaction 프로그램을 따로 돌렸었다.)

또한 파일 크기 예측의 어려움도 큰 단점이다. 파일이 생성될 때, 파일의 최종 크기는 미리 알 수 없다. 파일이 예상보다 커지면 기존에 할당된 공간을 넘어 확장해야 하는데, 연속된 공간이 부족하면 확장이 불가능해 파일을 다른 곳으로 옮겨야 하는 상황이 발생한다. 특히 로그 파일과 같이 크기가 계속 증가하는 파일의 경우, 초기 할당 크기를 예측하기 매우 어렵다.

연속 할당 방식은 이렇듯 빠른 데이터 접근을 제공하지만, 치명적인 단점들로 인해 현대의 파일 시스템에서는 거의 사용되지 않는다.

1.2. 연결 할당(Linked Allocation)

파일을 연속적으로 할당하지 않고, 임의의 블록에 할당하면서 각 블록에 다음 블록을 가리키는 포인터를 저장하는 방식이다. 이는 자료구조의 연결 리스트(Linked List)와 유사한 방식이다. (cf. 연속 할당은 배열처럼 파일을 저장한다.)

이러한 파일을 linked list of data blocks라고 한다.

예를 들어, 파일의 첫 번째 블록을 6번 블록에 저장했다면, 6번 블록의 마지막에 다음 블록의 주소를 가리키는 포인터를 둔다. 디렉토리는 파일의 첫 번째 블록을 가리키는 주소를 저장한다.

file name: f1
file size: 5 bytes
...
-----------------
block number: 6

1.2.1. 특징

외부 단편화가 발생하지 않는다. 파일이 연속적인 블록에 저장될 필요가 없기 때문에, 디스크의 빈 블록을 효율적으로 사용할 수 있다.

또한 파일이 커질 경우에도 쉽게 확장할 수 있다. 추가적인 블록을 할당하고 포인터를 연결해 주기만 하면 된다.

1.2.2. 단점

가장 큰 단점은 직접 접근이 불가능하다는 점이다. 예를 들어, 파일 f1의 세 번째 블록에 바로 접근할 수 없다. 포인터를 통해 첫 번째 블록에서 순차적으로 접근해야만 세 번째 블록의 위치를 알 수 있다. 즉, 순차 접근만 가능하다는 뜻이다.

또한, 각 블록마다 포인터를 저장해야 하므로 추가적인 저장 공간 손실이 발생한다. 포인터 저장을 위해 약 4bytes 정도가 사용된다.

신뢰성 문제도 있는데, 만약 디스크의 특정 블록에 오류가 발생하면 해당 블록의 포인터를 읽지 못해 그 이후의 블록들도 모두 접근할 수 없게 된다.

이뿐만 아니라 파일이 여러 블록에 분산되어 있으므로 디스크 헤더가 자주 이동해야 하며, 이로 인해 성능 저하가 발생할 수 있다.

연결 할당은 연속 할당의 단점을 해결하지만, 나름의 문제점도 있다. 그럼에도 중요한 점은 외부 단편화가 발생하지 않아 디스크 공간 낭비가 없다는 것이다.

📁 FAT(File Allocation Table) 파일 시스템

MS-DOS의 개발 당시, MS는 연결 할당의 장점을 살리면서도 효율적인 파일 시스템을 만들기 위해 FAT 파일 시스템을 고안했다. FAT는 연결 할당의 변종으로, 포인터들을 각 블록에 저장하는 대신, 이 포인터들을 테이블로 따로 모아 디스크 블록 중 하나에 저장하는 방식이다. 이 테이블을 FAT라고 부른다.

FAT 시스템에서 각 블록은 FAT 테이블에 기록된 포인터를 통해 다음 블록을 가리킨다. 예를 들어, 6번 블록이 다음 블록으로 2번을 가리키고 있다고 할 때, 이 정보는 6번 블록에 있는 것이 아니라 FAT 테이블에 기록된다. 파일의 끝을 표시할 때는 -1을 사용한다.

이 방식의 장점은 직접 접근이 가능해진다는 것이다. 포인터를 일일이 따라갈 필요 없이 FAT 테이블을 읽어 원하는 데이터 블록으로 바로 이동할 수 있다. FAT 테이블은 부팅 시 메모리로 로드되기 때문에 테이블을 읽는 속도가 빠르다. 또한, 연결 할당의 단점 중 하나인 포인터가 깨지면 파일 전체를 읽을 수 없는 문제도 해결된다. 만약 테이블이 손상될 경우를 대비해 FAT 테이블의 복사본이 저장된다.

FAT에는 테이블을 위한 비트 할당 크기에 따라 여러 종류가 있다. FAT16, FAT32 같은 이름은 할당되는 비트 크기를 나타내며, 비트가 커질수록 저장 가능한 파일의 크기와 수가 늘어난다.

FAT는 주로 USB 메모리와 같은 이동식 디스크에서 많이 사용되며, 이 시스템은 MS-DOS, OS/2, Windows 등에서 널리 사용되고 있다.

1.3. 색인 할당(Index Allocation)

파일의 각 블록을 가리키는 포인터들을 인덱스 테이블에 저장하는 방식이다.

디렉토리는 해당 파일의 인덱스 블록의 위치를 저장한다. 즉, 인덱스 블록은 해당 파일의 데이터 블록들을 가리키는 포인터들의 집합이라고 볼 수 있다.

file name: f1
file size: 5 bytes
...
-----------------
index block number: 11

1.3.1. 특징

이 방식은 순차 접근과 직접 접근이 모두 가능하다.

또한 파일이 연속적으로 저장될 필요가 없어 외부 단편화 문제도 해결된다.

1.3.2. 단점

하지만 인덱스 테이블을 위한 별도의 블록이 필요하기 때문에 저장 공간의 낭비가 발생한다.
예를 들어, 1byte의 작은 파일, 영어 한 글자를 저장하기 위해 데이터 블록 하나와 인덱스 블록 하나가 사용되며, 이는 상당한 비효율이다.

FAT 파일 시스템의 경우 앞의 몇 블록 정도만을 테이블로 사용하였는데, 색인 할당 방식은 하나의 파일 당 한 블럭이 사용되므로 조금 더 손실이 크다고 볼 수 있다.

파일이 커질 경우, 하나의 인덱스 블록만으로 충분하지 않을 수 있다. 예를 들어, 한 블록이 512bytes라고 가정하고, 4bytes 정수형 포인터를 사용하면 한 인덱스 블록에 $512/4=128$ 개의 포인터를 저장할 수 있다. 즉, 128개의 블록을 가리킬 수 있으며, 이는 $128*512=64KB$ 의 파일 크기에 해당한다. 파일 크기가 64KB를 초과할 경우, 하나의 인덱스 블록만으로는 모든 파일 블록을 가리킬 수 없다.

이 문제를 해결하기 위해 다양한 확장 방식이 있다.

Linked 인덱스 방식: 하나의 인덱스 블록이 부족할 경우, 다른 인덱스 블록과 연결하여 파일의 모든 블록을 가리킬 수 있다.
다중 레벨 인덱스(Multilevel Index): 여러 단계의 인덱스 테이블을 사용하여 대용량 파일을 처리할 수 있다. 예를 들어, 2단계 인덱스를 사용하면 첫 번째 인덱스 블록은 두 번째 인덱스 블록을 가리키고, 그 블록이 실제 데이터 블록을 가리킨다.
혼합 방식(Combined Scheme): 첫 번째 인덱스 블록의 앞 부분은 실제 데이터 블록을 가리키고, 뒤쪽은 다른 인덱스 블록을 가리키는 방식이다. 이 방식은 대용량 파일을 처리하면서도 인덱스 테이블의 효율성을 높일 수 있다.