파일 시스템 구현

파일 시스템의 사용자 인터페이스를 살펴본 후, 이제 그 인터페이스 뒤에서

운영체제가 어떻게 파일 시스템을 구현하는지 알아봅니다.

디스크 위 자료 구조, 메모리 내 자료 구조, 할당 방법, 빈 공간 관리 등을 다룹니다.

1. 파일 시스템 계층 구조

┌──────────────────────────────────────────┐

│ 애플리케이션 (사용자 공간) │

├──────────────────────────────────────────┤

│ 논리적 파일 시스템 │

│ (파일 이름 → inode 변환, 보호 검사) │

├──────────────────────────────────────────┤

│ 파일 구성 모듈 │

│ (논리 블록 → 물리 블록 매핑) │

├──────────────────────────────────────────┤

│ 기본 파일 시스템 │

│ (블록 I/O 요청 발행) │

├──────────────────────────────────────────┤

│ I/O 제어 │

│ (장치 드라이버, 인터럽트 핸들러) │

├──────────────────────────────────────────┤

│ 저장 장치 (디스크/SSD) │

└──────────────────────────────────────────┘

2. 디스크 위 구조 (On-Disk Structures)

파일 시스템의 디스크 레이아웃

┌────────┬───────────┬──────────┬──────────┬─────────────────┐

│ Boot │ Super │ Free │ inode │ Data Blocks │

│ Block │ Block │ Space │ Table │ │

│ │ │ Mgmt │ │ │

│ 부트 │ 메타 │ 비트맵/ │ 파일 │ 실제 파일 │

│ 로더 │ 데이터 │ 리스트 │ 메타 │ 데이터 │

└────────┴───────────┴──────────┴──────────┴─────────────────┘

| 구조 | 역할 |

| ------------ | ------------------------------------------------------- |

| 부트 블록 | 부팅에 필요한 코드 (부트 로더) |

| 슈퍼 블록 | 파일 시스템 전체 정보 (블록 수, inode 수, 블록 크기 등) |

| 빈 공간 관리 | 사용 가능한 블록 추적 (비트맵 또는 연결 리스트) |

| inode 테이블 | 각 파일의 메타데이터와 블록 포인터 |

| 데이터 블록 | 실제 파일/디렉토리 데이터 |

inode 구조

┌─────────────────────────────────────┐

│ inode 구조 │

├─────────────────────────────────────┤

│ 파일 유형, 권한 (mode) │

│ 소유자 (uid, gid) │

│ 크기 (size) │

│ 타임스탬프 (atime, mtime, ctime) │

│ 링크 카운트 │

│ 블록 카운트 │

├─────────────────────────────────────┤

│ 직접 블록 포인터 [0-11] → 데이터 │

│ 단일 간접 포인터 → 포인터 블록│

│ 이중 간접 포인터 → 포인터² │

│ 삼중 간접 포인터 → 포인터³ │

└─────────────────────────────────────┘

// 간단화된 inode 구조체 (ext2 기반)

struct inode {

uint16_t mode; // 파일 유형 + 권한

uint16_t uid; // 소유자 ID

uint32_t size; // 파일 크기

uint32_t atime; // 접근 시간

uint32_t mtime; // 수정 시간

uint32_t ctime; // 상태 변경 시간

uint16_t gid; // 그룹 ID

uint16_t links_count; // 하드 링크 수

uint32_t blocks; // 할당된 블록 수

uint32_t direct[12]; // 직접 블록 포인터

uint32_t single_indirect; // 단일 간접 포인터

uint32_t double_indirect; // 이중 간접 포인터

uint32_t triple_indirect; // 삼중 간접 포인터

};

3. 메모리 내 구조 (In-Memory Structures)

파일 시스템은 성능을 위해 자주 사용하는 정보를 메모리에 캐시합니다.

┌───────────────────────────────────────────────┐

│ 커널 메모리 │

│ │

│ ┌─────────────────┐ ┌───────────────────┐ │

│ │ 마운트 테이블 │ │ 디렉토리 캐시 │ │

│ │ (파일시스템 목록)│ │ (최근 경로 정보) │ │

│ └─────────────────┘ └───────────────────┘ │

│ │

│ ┌─────────────────┐ ┌───────────────────┐ │

│ │ 시스템 전역 │ │ 프로세스별 │ │

│ │ 오픈 파일 테이블 │ │ 오픈 파일 테이블 │ │

│ └─────────────────┘ └───────────────────┘ │

│ │

│ ┌─────────────────┐ │

│ │ 버퍼 캐시 │ ← 디스크 블록 캐시 │

│ └─────────────────┘ │

└───────────────────────────────────────────────┘

4. VFS (Virtual File System)

VFS는 여러 종류의 파일 시스템을 단일 인터페이스로 통합하는 추상 계층입니다.

사용자 프로세스

open() read() write()

│

┌──────────┴──────────┐

│ VFS │

│ (가상 파일 시스템) │

│ │

│ vnode 인터페이스 │

└──┬──────┬──────┬─────┘

│ │ │

┌──┴──┐┌──┴──┐┌──┴──┐

│ext4 ││NFS ││FAT │

│ ││ ││ │

└──┬──┘└──┬──┘└──┬──┘

│ │ │

로컬 네트워크 USB

디스크 서버 드라이브

VFS의 주요 객체

// VFS 추상화의 주요 객체 (Linux 기반 의사 코드)

// 1. 슈퍼블록 객체: 파일 시스템 인스턴스 정보

struct super_block {

struct list_head s_list; // 슈퍼블록 목록

dev_t s_dev; // 장치 식별자

unsigned long s_blocksize; // 블록 크기

struct super_operations *s_op; // 연산 테이블

// ...

};

// 2. inode 객체: 개별 파일 정보

struct inode {

umode_t i_mode; // 파일 유형 + 권한

uid_t i_uid; // 소유자

loff_t i_size; // 파일 크기

struct inode_operations *i_op; // inode 연산

struct file_operations *i_fop;// 파일 연산

// ...

};

// 3. dentry 객체: 디렉토리 엔트리 (경로명 컴포넌트)

struct dentry {

struct inode *d_inode; // 관련 inode

struct dentry *d_parent; // 부모 디렉토리

struct qstr d_name; // 엔트리 이름

struct dentry_operations *d_op;

// ...

};

// 4. file 객체: 열린 파일 인스턴스

struct file {

struct dentry *f_dentry; // 관련 dentry

loff_t f_pos; // 현재 오프셋

unsigned int f_flags; // 열기 플래그

struct file_operations *f_op; // 파일 연산

// ...

};

5. 디렉토리 구현

선형 리스트

디렉토리 블록:

┌──────────┬────────┬──────────┬────────┬──────────┬────────┐

│ "file1" │ inode │ "file2" │ inode │ "file3" │ inode │

│ │ 23 │ │ 47 │ │ 12 │

└──────────┴────────┴──────────┴────────┴──────────┴────────┘

검색: O(n) - 파일 이름을 처음부터 순차 탐색

장점: 구현 간단

단점: 대규모 디렉토리에서 느림

해시 테이블

해시 함수: hash("filename") → 버킷 인덱스

버킷 0: ["file_a", inode 23] → ["file_d", inode 89] → NULL

버킷 1: ["file_b", inode 47] → NULL

버킷 2: NULL

버킷 3: ["file_c", inode 12] → ["file_e", inode 56] → NULL

...

검색: O(1) 평균 (해시 충돌 시 연결 리스트 탐색)

장점: 빠른 검색

단점: 고정 크기, 해시 충돌 관리 필요

6. 할당 방법 (Allocation Methods)

파일의 데이터 블록을 디스크에 어떻게 배치할 것인지를 결정합니다.

연속 할당 (Contiguous Allocation)

디렉토리 엔트리:

┌────────┬───────────┬──────┐

│ 파일명 │ 시작 블록 │ 길이 │

├────────┼───────────┼──────┤

│ file_a │ 2 │ 3 │

│ file_b │ 7 │ 2 │

│ file_c │ 14 │ 4 │

└────────┴───────────┴──────┘

디스크 블록:

0 1 [2 3 4] 5 6 [7 8] 9 10 11 12 13 [14 15 16 17]

file_a file_b file_c

**장점**: 순차/직접 접근 모두 효율적, 디스크 탐색 최소화

**단점**: 외부 단편화, 파일 크기 변경 어려움

연결 할당 (Linked Allocation)

디렉토리:

┌────────┬──────┬──────┐

│ 파일명 │ 시작 │ 끝 │

├────────┼──────┼──────┤

│ file_a │ 9 │ 1 │

└────────┴──────┴──────┘

디스크 블록 (각 블록에 다음 블록 포인터 포함):

블록 9 → 블록 16 → 블록 25 → 블록 1 → NULL

[data|16] [data|25] [data|1] [data|-1]

**장점**: 외부 단편화 없음, 파일 크기 변경 용이

**단점**: 직접 접근 비효율적 (순차 탐색 필요), 포인터 공간 오버헤드

FAT (File Allocation Table)

FAT 테이블 (메모리에 캐시):

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐

│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ ← 블록 번호

├─────┼─────┼─────┼─────┼─────┼─────┼─────┤

│ 3 │ EOF │ 5 │ 4 │ EOF │ 1 │ FREE│ ← 다음 블록

└─────┴─────┴─────┴─────┴─────┴─────┴─────┘

파일 A: 시작=0 → 0→3→4→EOF (블록 0, 3, 4)

파일 B: 시작=2 → 2→5→1→EOF (블록 2, 5, 1)

인덱스 할당 (Indexed Allocation)

디렉토리:

┌────────┬─────────────┐

│ 파일명 │ 인덱스 블록 │

├────────┼─────────────┤

│ file_a │ 19 │

└────────┴─────────────┘

인덱스 블록 19: 데이터 블록:

┌─────────────┐ 블록 9: [data...]

│ 9 │ ────→ 블록 16: [data...]

│ 16 │ ────→ 블록 25: [data...]

│ 25 │ ────→ 블록 1: [data...]

│ 1 │ ────→

│ -1 (끝) │

└─────────────┘

**장점**: 직접 접근 효율적, 외부 단편화 없음

**단점**: 인덱스 블록 오버헤드, 작은 파일에 비효율적

할당 방법 비교

| 방법 | 순차 접근 | 직접 접근 | 단편화 | 파일 확장 |

| ------ | --------- | --------- | ----------- | --------- |

| 연속 | 매우 빠름 | 빠름 | 외부 단편화 | 어려움 |

| 연결 | 보통 | 느림 | 없음 | 쉬움 |

| 인덱스 | 보통 | 빠름 | 없음 | 보통 |

7. 빈 공간 관리

비트맵 (Bit Vector)

블록 번호: 0 1 2 3 4 5 6 7 8 9 10 11 12

비트맵: 1 1 0 1 1 0 0 1 0 0 0 1 0

1 = 사용 중, 0 = 비어 있음

빈 블록 찾기: 비트맵에서 첫 번째 0 비트 탐색

장점: 연속 빈 공간 찾기 쉬움

단점: 대용량 디스크에서 비트맵 크기가 커짐

(1TB 디스크, 4KB 블록 → 32MB 비트맵)

// 비트맵에서 빈 블록 찾기

int find_free_block(uint32_t *bitmap, int total_blocks) {

int words = total_blocks / 32;

for (int i = 0; i < words; i++) {

if (bitmap[i] != 0xFFFFFFFF) { // 모두 사용 중이 아니면

// 첫 번째 0 비트 위치 찾기

for (int j = 0; j < 32; j++) {

if (!(bitmap[i] & (1 << j))) {

return i * 32 + j;

}

}

}

}

return -1; // 빈 블록 없음

}

연결 리스트

Free Space Head → 블록 2 → 블록 5 → 블록 6 → 블록 8 → NULL

각 빈 블록이 다음 빈 블록을 가리킴

장점: 구현 간단

단점: 연속 빈 공간 찾기 어려움, 순회 비용

TRIM 명령

SSD에서 삭제된 블록을 미리 알려주어 가비지 컬렉션을 최적화합니다.

TRIM 없이: TRIM 사용 시:

1. 파일 삭제 → 메타만 제거 1. 파일 삭제 → 메타 제거

2. SSD는 블록이 빈 줄 모름 2. TRIM 명령으로 SSD에 알림

3. 나중에 쓰기 시: 3. SSD가 미리 블록 삭제

읽기 → 삭제 → 쓰기 필요 4. 나중에 쓰기 시: 바로 쓰기

(쓰기 성능 저하) (쓰기 성능 유지)

8. 저널링 (Journaling)

시스템 충돌 시 파일 시스템 일관성을 유지하기 위한 메커니즘입니다.

저널링 동작 과정

일반 쓰기 (저널링 없음):

1. 데이터 블록 쓰기

2. inode 업데이트

3. 비트맵 업데이트

→ 2단계에서 충돌 시 불일치 발생!

저널링 쓰기:

┌──────────────────────────────────────┐

│ 저널 영역 (Log) │

│ │

│ 1. 트랜잭션 시작 (TxB) │

│ 2. 메타데이터 변경 사항 기록 │

│ 3. 트랜잭션 커밋 (TxE) │

│ │

│ → 커밋 완료 후 실제 위치에 적용 │

│ → 적용 완료 후 저널 삭제 │

└──────────────────────────────────────┘

저널링 모드

| 모드 | 저널에 기록 | 안정성 | 성능 |

| --------- | ------------------------------- | ------ | ---- |

| Journal | 메타데이터 + 데이터 | 최고 | 느림 |

| Ordered | 메타데이터만 (데이터 먼저 쓰기) | 높음 | 보통 |

| Writeback | 메타데이터만 (순서 보장 없음) | 보통 | 빠름 |

// 저널링 트랜잭션 의사 코드

void journaled_write(struct transaction *tx) {

// 1. 저널에 트랜잭션 시작 기록

journal_write_begin(tx);

// 2. 변경할 메타데이터를 저널에 기록

journal_write_metadata(tx, inode_data);

journal_write_metadata(tx, bitmap_data);

// 3. 저널에 트랜잭션 커밋 기록

journal_write_commit(tx);

// 4. 실제 파일 시스템 위치에 적용 (체크포인트)

write_to_actual_location(inode_data);

write_to_actual_location(bitmap_data);

// 5. 저널에서 트랜잭션 제거

journal_free(tx);

}

// 복구 시: 커밋된 트랜잭션은 재실행, 미커밋은 무시

void recover_from_crash() {

for_each_transaction(journal) {

if (transaction_committed(tx))

replay_transaction(tx); // 재실행

else

discard_transaction(tx); // 폐기

}

}

9. 정리

- **파일 시스템 계층**: 논리적 파일 시스템 → 파일 구성 모듈 → 기본 파일 시스템 → I/O 제어

- **디스크 구조**: 부트 블록, 슈퍼 블록, inode 테이블, 데이터 블록

- **VFS**: 여러 파일 시스템을 단일 인터페이스로 추상화

- **할당 방법**: 연속(빠르지만 단편화), 연결(유연하지만 직접 접근 느림), 인덱스(균형적)

- **빈 공간 관리**: 비트맵이 가장 일반적. SSD에서는 TRIM으로 최적화

- **저널링**: 트랜잭션 로그로 파일 시스템 일관성 보장

**Q1.** VFS의 역할은 무엇인가요?

**A1.** VFS(Virtual File System)는 ext4, NFS, FAT 등 서로 다른 파일 시스템을

통일된 인터페이스(open, read, write 등)로 추상화합니다.

이를 통해 애플리케이션은 기저 파일 시스템의 종류와 무관하게 동일한 시스템 콜로 파일에 접근할 수 있습니다.

**Q2.** 연속 할당과 인덱스 할당의 트레이드오프는 무엇인가요?

**A2.** 연속 할당은 순차/직접 접근 모두 빠르지만 외부 단편화가 발생하고 파일 크기 변경이 어렵습니다.

인덱스 할당은 외부 단편화가 없고 파일 확장이 용이하지만,

인덱스 블록에 대한 추가 공간과 I/O가 필요합니다.

**Q3.** 저널링에서 ordered 모드는 어떻게 동작하나요?

**A3.** Ordered 모드에서는 메타데이터만 저널에 기록하되,

데이터 블록은 메타데이터보다 먼저 디스크에 기록됩니다.

이를 통해 충돌 시 메타데이터가 아직 기록되지 않은 데이터를 가리키는 상황을 방지합니다.

Journal 모드보다 성능이 좋으면서도 데이터 일관성을 유지합니다.