파일 시스템 구현

파일 시스템의 인터페이스(open, read, write) 아래에서는 "파일 데이터를 디스크의 어느 블록에 어떻게 배치하고 찾을 것인가"라는 문제가 남는다. 이 노트는 그 구현 방법과, 디스크 I/O를 줄이기 위한 캐시 구조를 다룬다.

디스크 블록 할당 방식

하드디스크의 가장 작은 저장 단위는 섹터지만, 섹터는 작고 수가 너무 많아 하나하나 관리하기 어렵다. 그래서 운영체제는 섹터 하나 이상을 묶은 블록 단위로 파일과 디렉터리를 읽고 쓰며, 파일 하나는 여러 블록에 걸쳐 저장된다. 할당 방식이 달라지면 디렉터리 엔트리에 파일 위치로 무엇을 적는지도 달라진다. 오늘날에는 불연속 할당(연결·인덱스)을 주로 쓴다.

1. 연속 할당 (Contiguous Allocation)

파일을 디스크의 인접한 블록들에 연속으로 저장한다.

• 장점
  • 빠른 I/O: 하드디스크 접근 시간의 대부분은 헤드 이동(seek)인데, 한 번의 seek로 많은 데이터를 읽을 수 있다. 그래서 실시간 파일이나 스왑 영역처럼 속도가 중요한 곳에 적합하다.
  • 직접 접근 가능: 시작 위치 + 오프셋으로 바로 계산된다.
• 디렉터리 엔트리: 파일 이름, 첫 블록 주소, 블록 단위 길이. 시작이 2번이고 길이가 3이면 2·3·4번 블록이다.
• 단점
  • 외부 단편화가 생긴다. 파일 몇 개가 지워져 빈 블록이 모두 11개여도, 흩어진 빈 구간이 각각 7개보다 작으면 7블록짜리 파일은 저장할 수 없다.
  • 파일 크기를 키우기 어렵다. 미리 여유 공간을 잡아 두면 그만큼 낭비(내부 단편화)가 된다.

2. 연결 할당 (Linked Allocation)

빈 블록이면 어디든 저장하고, 각 블록이 다음 블록의 위치(포인터) 를 가진다. 데이터 블록들이 연결 리스트를 이루는 셈이다. 디렉터리 엔트리에는 파일 이름과 첫 블록 주소, 길이(또는 마지막 블록 주소)를 적는다. 마지막 블록에는 -1 같은 끝 표시를 넣는다.

flowchart LR
  e["엔트리: a, 시작 10, 길이 4"] --> b10["10"] --> b5["5"] --> b13["13"] --> b2["2 (-1, 끝)"]

• 장점: 외부 단편화가 없다.
• 단점
  • 직접 접근이 불가능하다. 영화 파일의 중간을 보려 해도 첫 블록부터 그 지점까지 차례로 따라가야 한다.
  • 한 섹터가 고장 나 포인터가 사라지면 그 뒤 데이터를 모두 잃는다.
  • 블록 일부를 포인터가 차지한다 (예: 512바이트 섹터 중 4바이트).
• 변형: 포인터만 따로 모아 둔 FAT(File Allocation Table) 방식이 이 문제들을 해결한다.

3. 인덱스 할당 (Indexed Allocation)

파일마다 인덱스 블록 하나를 두고, 데이터 블록들의 위치를 모두 거기에 적는다. 디렉터리 엔트리에는 파일 이름과 인덱스 블록 주소만 적으면 된다. 인덱스 블록 하나만 읽으면 7 → 13 → 11처럼 파일의 모든 블록 위치를 알 수 있다.

• 장점: 외부 단편화 없음, 직접 접근 가능.
• 단점
  • 작은 파일도 인덱스 블록이 필요해 공간이 낭비된다 (실제로 작은 파일이 많다).
  • 아주 큰 파일은 인덱스 블록 하나로 부족하다 → 인덱스 블록끼리 연결(linked scheme)하거나 다단계 인덱스(multi-level index)를 쓴다.

블록 단위 할당이 남기는 것: 슬랙 공간과 파일 조각화

파일을 블록 단위로 담으면 두 가지가 따라온다.

• 슬랙 공간(slack space): 파일의 마지막 블록에서 쓰지 않고 남은 부분이다. 4KiB 블록에 10KiB 파일을 담으면 블록 3개를 쓰고 2KiB가 남는다. 블록 하나 안의 낭비라 내부 단편화의 한 형태이고, 파일이 조금 커질 때는 이웃 파일을 건드리지 않고 이 자리에 이어 쓴다.
• 파일 조각화(file fragmentation): 불연속 할당에서는 파일이 커질 때 비어 있는 아무 블록이나 받는다. 생성·수정·삭제가 되풀이되면 한 파일의 블록이 디스크 곳곳에 흩어지고 순서도 뒤섞인다. 하드 디스크는 흩어진 블록마다 헤드를 옮겨야 해 읽기가 느려진다.

현대 파일 시스템은 연속된 블록 구간을 「시작 + 길이」로 기록하는 익스텐트(extent, ext4·NTFS·APFS)와, 쓰기를 모아 두었다가 한 번에 자리를 잡는 지연 할당으로 조각화를 애초에 줄인다.

UNIX 파일 시스템

가장 기본적인 구조로, 이후 많은 파일 시스템의 원형이 되었다. 디스크(파티션)를 다음 순서로 나눈다.

1. Boot block: 부팅에 필요한 정보(bootstrap loader). 모든 파일 시스템의 맨 앞에 있다.
2. Superblock: 빈 블록과 사용 중인 블록, inode 영역과 데이터 영역의 경계 등 파일 시스템 전체 정보.
3. Inode list: 파일 하나당 inode 하나. 파일 이름을 제외한 메타데이터(소유자, 권한, 크기, 데이터 블록 위치 등)를 담는다.
4. Data block: 실제 파일 내용. 파일 이름과 inode 번호의 짝은 디렉터리 파일의 데이터에 들어 있다.

UNIX는 인덱스 할당을 쓰고, 인덱스 블록 역할을 inode가 한다. inode마다 고유 번호가 있다. inode의 크기가 고정이라 포인터 수가 유한하므로, direct 포인터 → single indirect → double indirect → triple indirect 처럼 단계를 두어 작은 파일은 빠르게, 큰 파일도 커버한다. 전통적인 UNIX 파일 시스템(ext2·ext3도 같다)의 inode는 블록 주소 15개를 담는다.

작은 파일은 직접 블록만으로 끝나고, 크기가 커질수록 다음 칸을 쓴다. 삼중 간접까지 쓰면 대부분의 파일을 담을 수 있다. inode가 이름 말고는 모든 것을 가지므로 디렉터리 엔트리는 파일 이름과 inode 번호만 있으면 된다.

/home/minchul/a.sh를 읽는 과정은 다음과 같다. 루트 디렉터리의 inode 번호는 파일 시스템이 미리 알고 있다(ext 계열은 2번).

flowchart TB
  i2["2번 inode (루트)"] -->|"루트 디렉터리 블록에서 home의 inode 번호를 찾는다 (3번)"| i3["3번 inode (home)"]
  i3 -->|"home 디렉터리 블록에서 minchul의 inode 번호를 찾는다 (8번)"| i8["8번 inode (minchul)"]
  i8 -->|"minchul 디렉터리 블록에서 a.sh의 inode 번호를 찾는다 (9번)"| i9["9번 inode (a.sh)"]
  i9 --> rd["블록 주소를 따라 파일 내용을 읽는다"]

ext4는 이 구조를 이어받되, 큰 파일의 블록 주소를 간접 블록 대신 연속 구간(extent) 단위로 적는다.

FAT 파일 시스템

MS-DOS와 초기 Windows의 파일 시스템이었고, 지금도 USB 메모리·SD 카드 같은 이동식 저장 장치에서 널리 쓰인다. 연결 할당의 약점은 다음 블록 주소를 각 블록 안에 적었기 때문에 생긴다. FAT는 이 주소들을 한 표로 모아 약점을 보완한다. FAT12·FAT16·FAT32의 숫자는 FAT 항목 하나, 즉 블록(클러스터) 번호를 나타내는 비트 수다(FAT32는 그중 28비트를 쓴다).

• 위치 정보만 FAT 테이블에 따로 보관한다. n번 블록의 다음 블록 번호를 FAT의 n번 항목에 적는다.
• 블록(예: 512바이트)을 모두 데이터에 쓸 수 있다.
• FAT을 메모리에 올려 두면 테이블만 따라가 위치를 찾을 수 있어 직접 접근이 가능하다.
• FAT이 손상되면 치명적이므로 보통 2개 이상 복사해 둔다.

FAT로 포맷한 파티션은 예약 영역 | FAT 영역 | 루트 디렉터리 영역 | 데이터 영역 순으로 나뉜다(FAT12·FAT16 기준. FAT32는 루트 디렉터리도 데이터 영역에 둔다). 디렉터리 엔트리에는 파일 이름, 시작 블록, 크기와 함께 읽기 전용·숨김·시스템·디렉터리 여부 같은 속성까지 적는다.

flowchart TB
  start["/home/minchul/a.sh 읽기"] --> root["루트 디렉터리 영역"]
  root -->|"home은 3번 블록"| b3["3번 블록(home)"]
  b3 -->|"minchul은 15번 블록"| b15["15번 블록(minchul)"]
  b15 -->|"a.sh의 시작 블록은 9번"| fat
  subgraph fat["FAT: 9, 8, 11, 13번 블록을 차례로 읽는다"]
    direction LR
    f9["9"] --> f8["8"] --> f11["11"] --> f13["13"] --> fend["-1"]
  end

Windows의 기본 파일 시스템은 NTFS이고, FAT 계열은 기기 간 호환이 중요한 이동식 매체에 주로 남아 있다.

빈 공간 관리 (Free-Space Management)

디렉터리 구현

• 선형 리스트: <파일 이름, 메타데이터> 목록. 구현은 쉽지만 파일을 찾으려면 선형 탐색이 필요하다.
• 해시 테이블: 파일 이름을 해시해 위치를 바로 찾는다. 검색이 빠르지만 충돌(collision) 처리가 필요하다.
• 메타데이터는 디렉터리 안에 직접 두거나, 포인터만 두고 inode·FAT 같은 다른 곳에 보관한다.
• 엔트리는 보통 고정 크기라 긴 파일 이름은 엔트리 끝에 "이름의 나머지 위치"를 가리키는 포인터를 두어 처리한다.

VFS와 NFS

• VFS(Virtual File System): 서로 다른 파일 시스템을 같은 시스템 콜 인터페이스로 쓸 수 있게 하는 OS 계층.
• NFS(Network File System): 네트워크로 파일을 공유하는 대표적 방법. 원격 프로세스의 함수를 호출하는 RPC와, 서로 다른 시스템 간 데이터 표현을 맞추는 XDR을 사용한다.

버퍼 캐시와 페이지 캐시

리눅스 2.4 이전에는 두 캐시가 분리돼 같은 데이터가 두 번 캐시됐다. 지금은 버퍼가 페이지 캐시 안에서 메타데이터 블록을 가리키는 작은 역할만 하고, 캐시 페이지는 활성·비활성 LRU 목록으로 관리되어 오래 안 쓴 것부터 회수된다.

Memory-Mapped I/O

mmap()으로 파일의 일부를 프로세스의 가상 주소 공간에 매핑하면, 이후에는 메모리를 읽고 쓰는 것만으로 파일 입출력을 할 수 있다. mmap() 호출 자체는 시스템 콜이지만, 매핑된 뒤에는 매번 OS를 거치지 않는다.

파일 I/O 경로 비교

• 통합 버퍼 캐시가 없을 때
  • read()/write(): 디스크 → 버퍼 캐시 → 사용자 메모리로 복사.
  • mmap(): 디스크 → 버퍼 캐시 → 페이지 캐시로 한 번 더 복사한 뒤 매핑. 어느 방법이든 버퍼 캐시를 거친다.
• 통합 버퍼 캐시일 때
  • read()/write(): 페이지 캐시(= 버퍼 캐시)에서 바로 처리한 뒤 사용자 메모리로 복사.
  • mmap(): 페이지 캐시 자체가 사용자 주소 공간에 매핑되어 복사 없이 접근.

프로그램 실행과의 연결

실행 파일이 프로세스가 되면 code·data·stack 주소 공간이 생기고, 당장 쓰는 부분만 물리 메모리에 올라간다. 이때 code 영역은 이미 파일 시스템에 있으므로 스왑 영역에 내리지 않고, 필요 없으면 그냥 메모리에서 지운 뒤 나중에 파일에서 다시 읽는다. 실행 파일 자체가 메모리 매핑된 파일처럼 동작하는 셈이다. 메모리가 모자랄 때 어떤 페이지를 내보낼지는 가상 메모리의 페이지 교체에서 다룬다.