[OS] 파일 시스템 내부 (File Systems Internals)

floatFirstTOC: right

🖥️ 시작하며

🔍 파일 시스템 개요

1️⃣ 사용자의 관점에서

1. 파일의 이름이 어떻게 지정되는가?

2. 파일에 어떤 작업이 허용되는가?

3. Directory Tree는 어떻게 생겼는가?

2️⃣ 개발자의 관점에서

1. 파일과 디렉터리는 어떻게 저장되는가?
• 파일과 디렉터리는 일반적으로 블록 단위로 디스크에 저장
• 메타데이터: 파일의 이름, 크기, 위치, 권한 등을 저장하는 메타데이터가 함께 관리
• 디렉터리 엔트리: 각 디렉터리는 해당 디렉터리에 포함된 파일과 하위 디렉터리의 목록을 저장

2. 디스크 공간은 어떻게 관리되는가?

3. 모든 것을 효율적이고 신뢰성 있게 만드는 방법은?

🔍 Disk Layout

• Master Boot Record (MBR)
• 디스크의 첫 번째 섹터에 위치하며, 부트 로더 코드와 파티션 테이블을 포함
• MBR은 디스크가 부팅될 때 실행되며, 활성 파티션을 찾아 부팅을 진행

• 파티션 (Partitions)
• 디스크는 여러 개의 파티션으로 나뉘어질 수 있음
• 각 파티션은 독립된 파일 시스템을 가질 수 있음

💡 파일 시스템 구조 (FS-dependent)

🔍 File System Internals

📌 주요 구성 요소

1️⃣ System Call Interface

• 사용자 프로그램이 파일 시스템과 상호작용할 수 있도록 하는 인터페이스

• 파일을 열고, 읽고, 쓰고, 닫는 등의 시스템 호출을 제공

2️⃣ Virtual File System (VFS)

• 다양한 파일 시스템을 추상화하여 통일된 인터페이스를 제공

• 이를 통해 사용자 프로그램은 파일 시스템의 종류에 관계없이 동일한 방식으로 파일에 접근할 수 있음

3️⃣ 지원하는 파일 시스템

• minix: Minix 파일 시스템

• nfs: Network File System, 네트워크를 통해 파일을 공유하는 파일 시스템

• ext4: Linux에서 널리 사용되는 확장 파일 시스템

• fat: FAT 파일 시스템, 주로 Windows와 USB 드라이브에서 사용

• mmfs: 메모리 맵 파일 시스템

• procfs: 프로세스 파일 시스템, 시스템 프로세스 정보를 파일 형태로 제공

• 이외에도 다양한 파일 시스템을 지원할 수 있습니다.

4️⃣ Buffer Cache

• 파일 시스템에서 데이터를 읽고 쓸 때 성능을 향상시키기 위해 사용되는 캐시

• 자주 사용하는 데이터를 메모리에 저장하여 디스크 접근 횟수를 줄임

5️⃣ Device Driver

• 하드웨어 장치와 상호작용하는 소프트웨어

• 파일 시스템 요청을 실제 물리적 디스크로 전달하고, 디스크에서 데이터를 읽어오는 역할

📌 데이터 흐름

1. 사용자 요청: 사용자가 파일을 읽거나 쓰기 위해 시스템 호출 인터페이스를 통해 요청을 보냄

2. VFS 처리: VFS는 이 요청을 받아서 적절한 파일 시스템으로 전달

3. 파일 시스템 작업: 각 파일 시스템은 필요한 데이터를 버퍼 캐시에서 찾거나, 디바이스 드라이버를 통해 디스크에서 읽어옴

4. 디바이스 드라이버: 디바이스 드라이버는 파일 시스템의 요청을 실제 디스크로 전달하고, 필요한 데이터를 읽거나 씀

5. 결과 반환: 파일 시스템은 디바이스 드라이버로부터 데이터를 받아 버퍼 캐시에 저장하거나, VFS를 통해 사용자에게 직접 반환

🔍 In-memory Structures

📌 주요 구성 요소

• Per-process File Descriptor Table (각 프로세스 별 파일 디스크립터 테이블)
• 각 프로세스는 자신만의 파일 디스크립터 테이블을 가지고 있음
• 이 테이블은 프로세스가 열고 있는 파일들의 목록을 관리
• 테이블 항목은 파일 디스크립터 번호를 통해 파일 테이블의 항목을 참조

• File Table (시스템 전체의 파일 테이블)
• 시스템 전체에서 열려 있는 파일들의 정보를 관리
• 각 항목은 파일 디스크립터 테이블의 항목이 참조하는 실제 파일 정보를 포함
• 주요 정보:
• Count: 이 파일을 열고 있는 프로세스의 수
• Offset: 파일 내 현재 위치
• File Attributes: 파일 크기, 권한, 소유자 등 메타데이터

• In-memory Partition Table (메모리 내 파티션 테이블)
• 디스크의 파티션 정보를 메모리에 저장하여 빠르게 접근할 수 있도록 함
• 각 파티션의 시작 위치와 크기 등의 정보를 포함

📌 데이터 흐름

1. 파일 열기
• 프로세스 A가 파일 a.txt를 열면, 프로세스 A의 파일 디스크립터 테이블에 새로운 항목이 추가
→ 이 항목은 시스템 전체의 파일 테이블 내의 해당 파일 정보를 가리킴

2. 파일 정보 관리
• 시스템 전체의 파일 테이블은 열려 있는 모든 파일의 정보를 관리
→ 이 테이블은 파일을 열고 있는 프로세스 수, 파일 내의 현재 위치, 파일 메타데이터를 포함

3. 캐시 사용
• 디렉터리 캐시는 디렉터리 검색을 빠르게 하기 위해 사용
• 버퍼 캐시는 디스크 I/O를 최소화하고 성능을 높이기 위해 자주 사용하는 데이터 블록을 메모리에 저장

🔍 VFS (Virtual File System)

• 사용자와 응용 프로그램은 파일 시스템의 종류에 관계없이 동일한 인터페이스를 사용할 수 있음

• VFS는 사용자 레벨에서 발생하는 시스템 호출 요청을 처리
• open , write , stat 등

• VFS는 마운트 포인트를 통해 특정 파일 시스템과 상호 작용
• vnode 는 특정 파일 시스템의 파일을 추상화한 객체, 파일의 메타데이터와 데이터에 대한 정보 포함

🔍 Directory 구현

📌 Table, Linear List, Hash Table

1️⃣ Table

• 고정 길이 항목을 사용하는 테이블 구조

2️⃣ Linear List

• 특징
• 구현이 간단하여 프로그래밍이 쉬움
• 하지만 항목을 찾기 위해 선형 검색이 필요하므로 시간이 많이 소요됨
• 항목을 찾기 위해 처음부터 끝까지 하나씩 비교하는 방식

• 성능 향상
• 항목을 정렬하여 평균 검색 시간을 줄일 수 있음
• 예: B-트리(B-tree)를 사용하여 정렬된 리스트로 관리

3️⃣ Hash Table

• 특징
• 디렉터리 검색 시간을 줄이기 위해 사용
• 해시 테이블은 일반적으로 고정 크기이며, 해시 함수는 이 크기에 의존함
• 충돌 해결 메커니즘 필요 (여러 항목이 동일한 해시 값을 가질 때)

• 충돌 해결 방법
• 해시 테이블 크기 확장 및 재매핑 (Enlarge the hash table and remap)
• 파일 수가 많아질 때, 해시 테이블의 크기를 늘리고 기존 항목을 재매핑
• 체인 오버플로우 해시 테이블 (Chained-overflow hash table)
• 충돌이 발생할 경우, 링크드 리스트를 사용하여 동일한 해시 값을 가진 항목들을 체인으로 연결

📌 Metadata의 위치

🔍 Allocation (데이터 블록에 대한)

1️⃣ Contiguous Allocation (연속적)

⚙️ 장점 (Advantages)

1. 디스크 탐색 횟수가 최소화됨
• 파일이 연속된 블록에 저장되므로, 파일을 읽거나 쓸 때 디스크 헤드가 이동하는 횟수가 줄어듬

2. 디렉터리 항목이 단순해짐
• 파일의 이름, 시작 디스크 블록, 길이(블록 수) 등 기본 정보만으로 파일을 관리할 수 있음

⚙️ 단점 (Disadvantages)

1. 동적 저장소 할당이 필요함
• 파일을 저장할 때 첫 번째 맞는 공간(First Fit)이나 가장 적합한 공간(Best Fit)을 찾아 할당해야 함

2. 외부 단편화 (External Fragmentation)
• 외부 단편화를 해결하기 위해 가끔씩 디스크 압축(compaction)을 수행해야 함

3. 파일 크기 예측이 어려움
• 파일 크기가 사전에 예측하기 어려울 경우, 연속된 큰 공간을 미리 할당해야 하는 문제가 발생할 수 있음
• 파일 크기가 변하는 경우, 연속된 공간을 다시 할당해야 할 수 있음

💡 CD-ROM과 같은 읽기 전용 파일 시스템에서의 사용

1. 모든 파일 크기가 사전에 알려져 있음
• CD-ROM에 파일을 쓰기 전에 모든 파일의 크기가 정해져 있어 파일 배치 용이

2. 파일이 이후 사용 중 변경되지 않음
• 읽기 전용 파일 시스템에서는 파일이 변경되지 않으므로, 외부 단편화 문제나 파일 크기 변화 없음

💡 참고: 수정된 연속 할당 (Modified Contiguous Allocation)

• 초기 연속 공간 할당 (청크)
• 파일을 저장할 때 처음으로 큰 연속된 공간을 할당

• 추가 연속 공간 할당 (엑스텐트)
• 초기 공간이 부족해지면 또 다른 연속된 공간(extent)을 할당

⚙️ 장점 (Advantages)

1. 디렉터리 항목이 여전히 단순함
• 파일의 이름, 시작 디스크 블록, 길이, 그리고 extent로의 링크 정보만을 저장

2. 디스크 탐색 시간이 최소화됨
• 대부분의 파일이 연속된 블록에 저장되므로 디스크 탐색 시간이 줄어듬

⚙️ 단점 (Disadvantages)

1. 내부 단편화 (Internal Fragmentation)
• extent가 너무 크면 파일에 실제로 필요한 공간보다 더 많은 공간이 할당되어 비어있는 공간이 발생

2. 외부 단편화 (External Fragmentation)
• 크기가 다양한 엑스텐트를 허용할 경우 시간이 지남에 따라 외부 단편화가 발생

2️⃣ Linked Allocation

⚙️ 장점 (Advantages)

1. 디렉터리 항목이 단순함
• 디렉터리 항목에는 파일 이름, 시작 블록, 끝 블록 등의 기본 정보만 필요

2. 외부 단편화 없음

3. 파일 크기 확장 가능
• 파일의 크기를 사전에 예측할 필요가 없음

⚙️ 단점 (Disadvantages)

1. 큰 탐색 오버헤드 (SSD는 걱정 X)
• 파일을 읽기 위해 여러 블록을 순차적으로 접근

2. 포인터 유지에 따른 공간 오버헤드
• 각 블록은 다음 블록을 가리키는 포인터를 포함해야 함

3. 블록 크기가 2의 거듭제곱이 아님
• 포인터가 공간을 차지하기 때문에, 실제 데이터 저장 공간은 블록 크기에서 포인터 크기를 뺀 만큼이 됨

4. 취약성
• 포인터가 손실되거나 손상되면 나머지 부분 접근 불가능

💡 참고 : 클러스터를 사용한 연결 할당

⚙️ 장점 (Advantages)

1. 논리적-물리적 블록 매핑이 단순함
• 클러스터 단위로 할당되므로 논리적 블록 번호와 물리적 블록 번호 간의 매핑이 간단해짐
• 클러스터 간의 연결만 관리하면 되므로 구조가 단순

2. 디스크 처리량 개선
• 클러스터 단위로 데이터를 읽고 쓰므로 디스크 탐색 횟수가 줄어들어 디스크 처리량이 개선

3. 포인터에 대한 공간 오버헤드 감소
• 각 클러스터에 대해 하나의 포인터만 필요하므로, 블록 단위로 포인터를 유지하는 것보다 공간 오버헤드가 줄어듦

⚙️ 단점 (Disadvantages)

1. 내부 단편화
• 클러스터가 여러 블록으로 구성되므로 파일의 크기가 클러스터의 배수가 아니면 마지막 클러스터의 일부 공간이 낭비될 수 있음

💡 FAT을 활용한 연결 할당

• 각 파티션의 시작 부분에 디스크의 일부를 할당해 FAT을 저장
• FAT은 각 블록의 상태와 다음 블록에 대한 포인터를 포함하는 테이블

• 파일의 각 블록은 FAT의 Entry에 해당
• 각 Entry는 블록이 파일의 일부인지, 사용 가능한 블록인지, 또는 파일의 마지막 블록인지 표시

• 랜덤 접근 시간이 향상되고, 단순한 구조를 가지며 파일 크기 확장이 용이하다는 장점 존재

3️⃣ Indexed Allocation

📌 특징

• 인덱스 블록 (Index Block)
• 각 파일마다 인덱스 블록을 할당하여 파일의 데이터 블록들을 가리키는 포인터를 저장
• 인덱스 블록은 파일의 데이터 블록 위치를 기록하는 배열을 포함

• 각 파일의 고유 인덱스 블록
• 파일을 열 때, 파일의 디렉터리 엔트리에는 파일의 인덱스 블록 위치가 저장됨
• 파일의 인덱스 블록을 통해 파일의 모든 데이터 블록을 찾을 수 있음

⚙️ 장점 (Advantages)

1. 효율적인 블록 관리
• 모든 포인터가 하나의 인덱스 블록에 모여 있으므로, 파일의 블록들을 쉽게 추적할 수 있음

2. 외부 단편화 없음
• 데이터 블록이 디스크 상의 임의의 위치에 저장될 수 있으므로, 외부 단편화 문제가 발생하지 않음

3. 임의 접근 용이
• 파일의 데이터 블록을 임의 순서로 접근할 수 있음
• 인덱스 블록을 통해 원하는 블록에 직접 접근할 수 있음

⚙️ 단점 (Disadvantages)

1. 공간 오버헤드
• 각 파일마다 인덱스 블록을 저장해야 하므로, 인덱스 블록에 대한 추가 공간이 필요
• 특히 작은 파일이 많은 경우, 인덱스 블록에 대한 오버헤드가 커질 수 있음

2. 큰 파일 지원의 한계
• 인덱스 블록의 크기가 제한되어 있어, 매우 큰 파일의 경우 모든 블록을 인덱스 블록에 기록할 수 없음
→ 이를 해결하기 위해 다단계 인덱스 구조(예: 다단계 inode)를 사용할 수 있음

💡 사용 예시

• Unix 파일 시스템 (UFS)
• Unix 파일 시스템은 인덱스 할당 방식을 사용하여 파일의 데이터 블록을 관리
• 각 파일은 inode라는 고유 인덱스 블록을 가지고 있으며, 이 inode는 파일의 메타데이터와 데이터 블록 포인터를 포함함

🔍 Free Space Management

1️⃣ Bitmap or bit vector

• 각 블록을 비트맵의 1비트로 표현 (1: 자유 블록, 0: 할당된 블록)

• 간단하고 빠른 탐색 가능

2️⃣ Linked List

• 첫 번째 자유 블록에 대한 포인터를 유지하며 모든 자유 블록을 연결

• 탐색 시간이 걸리고, Bad Block이 존재할 수 있다는 단점

🔍 Performance

📌 Buffer Cache (Page Cache)

⚙️ 특징

• 버퍼 캐시는 시스템 전체에서 사용되며, 모든 프로세스가 공유

• 디스크에서 데이터를 읽는 대신 캐시에 있는 데이터를 읽으면 디스크 접근 시간이 메모리 접근 시간으로 단축

• 4MB캐시도 굉장히 효율적

⚙️ 문제점

• 버퍼 캐시와 가상 메모리 (VM) 간의 경쟁
• 버퍼 캐시는 메모리를 사용하여 파일 블록을 캐시하므로 가상 메모리 시스템과 메모리가 경쟁

• 교체 알고리즘 필요성 (Replacement Algorithms)
• 캐시가 가득 찬 경우, 새로운 블록을 캐시하기 위해 기존의 블록을 교체해야 함

📌 Read Ahead

1. 예측 및 요청
• 파일 시스템은 프로세스가 현재 블록을 처리하는 동안, 다음 블록을 요청할 것이라고 예측 → 캐시 저장

2. I/O와 실행의 중첩
• 프로세스가 현재 블록을 처리하는 동안, 파일 시스템은 다음 블록을 디스크에서 읽어오는 작업을 수행
→ I/O 작업과 프로세스 실행이 겹쳐져 동시에 진행

3. 캐시에서의 읽기
• 프로세스가 다음 블록을 요청할 때, 해당 블록은 이미 캐시에 저장되어 있으므로 바로 제공

⚙️ 장점 (Advantages)

1. 순차적으로 접근하는 파일에 매우 효과적
• 순차적으로 접근하는 파일의 경우, 다음 블록을 예측하여 미리 읽어오는 것이 매우 효율적
• 예: 동영상 재생, 대용량 데이터 처리 등

2. 디스크 접근 시간 절약
• 프로세스가 필요한 블록을 요청할 때 이미 캐시에 저장되어 있으므로 디스크에서 읽어오는 시간을 절약

3. I/O와 실행 중첩으로 성능 향상
• I/O 작업과 프로세스 실행을 동시에 진행함으로써 전체 시스템의 효율성을 높임

⚙️ 블록 배치 최적화

1. 할당 중 최적화
• 파일 시스템은 파일을 할당할 때, 블록이 디스크 전체에 흩어지지 않도록 노력함
• 연속된 블록을 할당함으로써 read ahead 기법의 효과를 극대화

2. 주기적인 재구조화 (요즘은 SSD써서 안함)
• 디스크의 블록이 분산되더라도, 주기적으로 재구조화하여 블록을 연속적으로 배치