14.1 파일 시스템 구조 (File-System Structure)
파일 시스템 계층 구조
- 파일 시스템은 여러 계층(Layer)으로 구성된다.
- 아래 그림과 같이 각 계층이 하위 계층의 기능을 활용하여 새로운 기능을 제공하는 구조를 갖는다.
1. I/O 제어 계층 (I/O Control Level)
- 디바이스 드라이버 및 인터럽트 핸들러가 포함되어 있음.
- 파일 시스템과 저장 장치 간 데이터를 전송하는 역할 수행.
- 디바이스 드라이버는 "명령 번역기" 역할을 하며,
- "블록 123을 읽어라" 같은 고수준 명령을 받아
- 하드웨어가 이해할 수 있는 저수준 명령으로 변환.
2. 기본 파일 시스템 (Basic File System, Block I/O Subsystem in Linux)
- 저장 장치에서 데이터를 읽고 쓰는 역할 수행.
- 블록 단위 데이터 전송 및 I/O 요청 스케줄링 담당.
- 버퍼(Buffer)와 캐시(Cache)를 관리하여 성능을 향상.
- 버퍼: 저장 장치로 데이터를 전송하기 전 임시 저장하는 공간.
- 캐시: 자주 사용되는 파일 시스템 메타데이터 저장.
3. 파일 조직 모듈 (File-Organization Module)
- 파일을 논리 블록(Logical Block) 단위로 관리.
- 파일의 논리 블록을 디스크 블록과 매핑하는 역할 수행.
- 여유 공간 관리(Free-Space Manager) 기능 포함.
- 사용 가능한 블록을 추적하고 필요 시 할당.
4. 논리적 파일 시스템 (Logical File System)
- 파일의 메타데이터(Metadata) 관리 담당.
- 예: 파일 소유권, 접근 권한, 파일 위치 정보.
- 디렉터리 구조 관리 및 파일-디스크 매핑 정보 제공.
- 파일 제어 블록(File Control Block, FCB) 관리.
14.2 파일 시스템 연산 (File-System Operations)
운영체제는 open() 및 close() 시스템 호출을 제공하여 프로세스가 파일에 접근할 수 있도록 한다.
이 섹션에서는 파일 시스템 연산을 구현하는 구조와 동작 방식을 설명한다.
14.2.1 개요 (Overview)
파일 시스템을 구현하기 위해 저장 장치(Storage)와 메모리(In-Memory) 구조가 사용된다.
저장 장치의 주요 구조
- 부트 제어 블록 (Boot Control Block)
- 운영체제를 부팅하는 데 필요한 정보 포함.
- 운영체제가 없는 디스크는 이 블록이 비어 있음.
- 볼륨 제어 블록 (Volume Control Block)
- 볼륨(디스크 파티션)의 메타데이터 관리.
- 총 블록 수, 블록 크기, 여유 블록 수 및 포인터 정보 포함.
- 디렉터리 구조 (Directory Structure)
- 파일 시스템 내 파일들을 체계적으로 정리.
- 파일 제어 블록 (File Control Block, FCB)
- 개별 파일의 메타데이터를 포함하는 구조체.
- 파일의 고유 ID를 가지며 디렉터리 엔트리와 연결됨.
메모리 내 주요 구조
운영체제는 파일 시스템 성능 향상을 위해 캐싱 및 인메모리(in-memory) 데이터 구조를 활용한다.
- 마운트 테이블 (Mount Table)
- 현재 마운트된 볼륨의 정보를 저장.
- 디렉터리 캐시 (Directory Structure Cache)
- 최근 접근한 디렉터리 정보를 저장.
- 다른 볼륨이 마운트된 디렉터리의 경우, 해당 볼륨을 가리키는 포인터 포함.
- 시스템 전체 오픈 파일 테이블 (System-Wide Open-File Table)
- 현재 열려 있는 모든 파일의 FCB 사본을 저장.
- 여러 프로세스가 같은 파일을 열 경우 중복 데이터를 줄이고 속도를 향상시킴.
- 프로세스별 오픈 파일 테이블 (Per-Process Open-File Table)
- 특정 프로세스가 열어둔 파일 목록을 저장.
- 각 파일은 시스템 전체 오픈 파일 테이블의 항목을 가리키는 포인터를 포함.
- 버퍼 (Buffers)
- 파일 읽기/쓰기 중 임시 저장 역할.
- 성능 향상을 위해 디스크 블록을 캐시에 저장.
14.2.2 파일 사용 (Usage)
파일 생성 과정
- 프로세스가 새로운 파일을 생성하면, 논리 파일 시스템(Logical File System)이 요청을 처리.
- 새로운 파일 제어 블록(FCB) 할당
- 일부 파일 시스템에서는 처음 생성할 때 모든 FCB를 미리 할당하고, 필요할 때 사용.
- 해당 디렉터리를 메모리에 로드하고, 새로운 파일 정보를 추가한 후 다시 디스크에 저장.
파일 열기 (open() 호출)
- open() 호출 시, 시스템 전체 오픈 파일 테이블을 검색
- 이미 열려 있는 파일이면, 해당 항목을 참조하여 프로세스별 오픈 파일 테이블에 포인터 추가 (중복 데이터 방지).
- 열려 있지 않은 파일이면, 디렉터리 구조에서 해당 파일을 찾아 FCB를 시스템 전체 오픈 파일 테이블에 복사.
- 이후 프로세스별 오픈 파일 테이블에 새로운 엔트리를 생성.
- 각 파일에는 현재 위치(Current Position) 및 접근 모드(Access Mode) 정보를 포함.
- 읽기/쓰기 작업 시 현재 위치를 업데이트하여 다음 작업을 원활하게 수행.
파일 닫기 (close() 호출)
- 프로세스별 오픈 파일 테이블에서 해당 파일 엔트리 삭제.
- 시스템 전체 오픈 파일 테이블에서 열린 프로세스 수를 감소.
- 모든 프로세스가 파일을 닫으면, 변경된 메타데이터를 디스크로 다시 저장 후 테이블에서 제거.
14.3 디렉터리 구현 (Directory Implementation)
파일 시스템의 디렉터리 할당 및 관리 알고리즘 선택은 효율성, 성능, 신뢰성에 큰 영향을 미친다.
이 장에서는 대표적인 디렉터리 구현 방식인 선형 리스트(Linear List) 와 해시 테이블(Hash Table) 방법을 비교한다.
14.3.1 선형 리스트 (Linear List)
구조 및 동작 방식
- 가장 간단한 방식: 파일 이름과 데이터 블록 포인터를 포함한 리스트 형태의 디렉터리 사용.
- 파일 생성: 디렉터리 검색 후 중복 이름이 없으면 새 엔트리를 추가.
- 파일 삭제: 디렉터리에서 해당 파일을 찾고, 할당된 공간을 해제.
단점
- 파일 검색 속도가 느림
- 파일을 찾으려면 리스트를 처음부터 끝까지 검색해야 함 (O(n) 시간 복잡도).
- 디렉터리 접근이 빈번하므로 성능 저하가 심할 수 있음.
14.3.2 해시 테이블 (Hash Table)
구조 및 동작 방식
- 해시 테이블을 활용하여 파일 검색 속도를 개선
- 선형 리스트(Linear List) + 해시 함수(Hash Function) 사용
- 파일 이름을 해시 함수로 변환 → 해시 테이블에서 해당 위치의 포인터 반환
- 검색 속도 개선: 해시 함수 덕분에 파일 검색 시간이 일정(O(1))에 가까움
장점
- 검색 속도가 매우 빠름 → 선형 리스트의 O(n) 탐색 시간을 O(1)에 가깝게 단축
- 삽입 및 삭제가 용이함 → 새로운 파일을 해시 테이블에 추가하면 끝
단점
- 충돌(Collision) 문제: 서로 다른 파일 이름이 같은 해시 값으로 변환될 가능성 있음
14.4 파일 할당 방식 (Allocation Methods)
효율적인 저장 공간 사용과 빠른 접근 속도를 보장하기 위해, 파일 할당 방식에는 연속 할당(Contiguous Allocation), 연결 할당(Linked Allocation), 인덱스 할당(Indexed Allocation)의 세 가지 주요 방식이 존재한다.
14.4.1 연속 할당(Contiguous Allocation)
개념
- 연속 할당은 파일이 디스크에서 연속된 블록(blocks)에 저장되는 방식이다.
- 파일이 저장될 때, 특정 시작 블록과 파일 크기(블록 단위)가 지정되며, 해당 범위 내에서 파일이 배치된다.
- 예를 들어, 파일의 크기가 5블록이고 시작 위치가 b라면, 해당 파일은 b, b+1, b+2, ..., b+4 블록에 저장된다.
장점
- 빠른 접근 속도:
- 순차 접근(Sequential Access): 파일을 순서대로 읽을 때, 바로 다음 블록을 읽으면 되므로 빠르다.
- 직접 접근(Direct Access): 특정 블록 i를 찾을 때, b + i의 위치로 바로 이동할 수 있어 검색이 빠르다.
- 단순한 구현: 파일의 시작 주소와 크기만 저장하면 되므로 관리가 용이하다.
단점
- 외부 단편화(External Fragmentation)
- 파일이 생성되고 삭제되면서 빈 공간(홀; hole)이 조각나게 되어, 충분한 공간이 있어도 연속된 블록이 없으면 새로운 파일을 저장할 수 없는 문제가 발생한다.
- 이를 해결하기 위해 디스크 조각 모음(Defragmentation)을 수행해야 하는데, 이는 시간이 오래 걸리며 시스템 성능을 저하시킬 수 있다.
- 파일 크기 예측 문제
- 파일을 저장할 때, 미리 크기를 지정해야 한다.
- 너무 작게 설정하면 추가 공간이 필요할 때 확장이 어렵고, 너무 크게 설정하면 내부 단편화(Internal Fragmentation)가 발생해 공간이 낭비된다.
- 확장성 문제
- 중간에 있는 파일을 확장하려면 전체 파일을 새로운 위치로 이동해야 할 수도 있어 비효율적이다.
14.4.2 연결 할당(Linked Allocation)
개념
- 연결 할당은 파일을 여러 개의 비연속적인 블록에 저장하는 방식이다.
- 각 블록은 다음 블록을 가리키는 포인터(pointer)를 포함하고 있으며, 파일의 첫 번째 블록 주소만 디렉터리에 저장된다.
- 예를 들어, 파일이 5개의 블록을 차지하고 첫 번째 블록이 9번 블록이면, 해당 블록에는 다음 블록의 주소(예: 16)가 저장되고, 16번 블록에는 또 다른 블록(예: 1)의 주소가 저장되는 방식으로 이어진다.
장점
- 외부 단편화 없음
- 파일 블록이 어디에든 저장될 수 있어 연속된 공간을 찾을 필요가 없다.
- 디스크 공간을 효율적으로 사용할 수 있다.
- 파일 크기 예측 불필요
- 파일이 크기를 확정하지 않고도 저장 가능하며, 필요할 때마다 블록을 추가할 수 있다.
- 삭제 및 확장 용이
- 중간 블록을 삭제하거나 새로운 블록을 추가하는 작업이 간단하다.
단점
- 직접 접근 속도 저하
- 특정 블록을 찾기 위해 처음부터 포인터를 따라가야 하므로, 직접 접근이 비효율적이다.
- 포인터 저장 공간 낭비
- 각 블록에 포인터가 포함되므로 저장 공간의 일부가 낭비된다.
- 포인터 손실 위험
- 운영 체제 버그나 하드웨어 오류로 인해 포인터가 손상되면 파일이 손실될 위험이 있다.
파일 할당 테이블(FAT, File Allocation Table) 방식
- FAT 파일 시스템은 연결 할당을 개선한 방식으로, 파일의 각 블록 위치를 테이블(파일 할당 테이블)에 저장한다.
- 파일을 찾을 때 FAT를 참조하여 빠르게 블록을 조회할 수 있다.
14.4.3 인덱스 할당(Indexed Allocation)
개념
- 인덱스 할당은 파일의 모든 블록 주소를 한 곳(인덱스 블록)에 모아두는 방식이다.
- 각 파일마다 인덱스 블록이 있으며, 이 블록에는 해당 파일의 모든 블록 주소가 저장된다.
- 예를 들어, 파일이 5개의 블록을 차지한다면, 인덱스 블록에는 각 블록의 실제 주소가 저장되어 있다.
디렉터리는 인덱스 블록의 주소만 저장하면 된다.
장점
- 직접 접근(Direct Access) 가능
- 특정 블록을 찾을 때 포인터를 따라갈 필요 없이, 인덱스 블록에서 바로 찾을 수 있다.
- 외부 단편화 없음
- 파일이 비연속적으로 저장될 수 있어, 남는 공간을 효율적으로 활용할 수 있다.
단점
- 인덱스 블록의 공간 낭비
- 작은 파일도 인덱스 블록을 필요로 하므로, 공간 낭비가 발생할 수 있다.
- 대형 파일 지원 문제
- 파일이 너무 크면 하나의 인덱스 블록에 모든 블록 주소를 저장할 수 없다.
14.5 여유 공간 관리 (Free-Space Management) 요약
파일 시스템에서 삭제된 파일의 공간을 새로운 파일에 재사용하기 위해 여유 공간을 관리하는 기법이 필요하다. 이를 위해 운영체제는 여유 공간 목록 (free-space list) 을 유지하며, 파일이 생성될 때 필요한 공간을 할당하고, 파일이 삭제되면 해당 공간을 다시 목록에 추가한다.
14.5.1 비트 벡터 (Bit Vector)
- 디스크의 각 블록을 비트맵(비트 벡터) 로 표현하여 관리한다.
- 블록이 사용 중이면 0, 비어 있으면 1로 표시됨.
- 첫 번째 빈 블록을 빠르게 찾을 수 있어 효율적이나, 대규모 디스크에서는 비트맵 크기가 커져 메모리 부담이 생김.
14.5.2 연결 리스트 (Linked List)
- 모든 빈 블록을 연결 리스트로 묶고, 첫 번째 빈 블록의 위치를 저장.
- 블록을 할당할 때 첫 번째 블록을 반환하고, 삭제 시 해당 블록을 다시 연결.
- 하지만 리스트를 탐색하려면 I/O 연산이 많아져 성능이 저하될 수 있음.
14.5.3 그룹화 (Grouping)
- 첫 번째 빈 블록에 다음 n 개의 빈 블록 주소 를 저장.
- 마지막 블록이 추가적인 n개의 빈 블록 주소를 포함하여 리스트를 확장.
- 단순한 연결 리스트보다 여러 빈 블록을 빠르게 찾을 수 있음.
14.5.4 카운팅 (Counting)
- 연속된 빈 블록이 많다는 점을 이용하여, 시작 블록 주소와 연속된 빈 블록 개수(n)만 저장.
- 개별 블록 주소를 저장하는 것보다 공간을 절약할 수 있으며, 검색도 효율적.
- 균형 트리 (Balanced Tree) 구조로 저장하면 삽입/삭제가 빠름.
14.5.5 공간 맵 (Space Maps) - ZFS
- ZFS 파일 시스템에서 사용되는 기법으로, 대용량 스토리지에서 메타데이터 I/O를 최소화하기 위해 고안됨.
- 디스크를 메타슬랩(metaslab) 단위로 나누고, 각 메타슬랩은 공간 맵 (space map) 을 가짐.
- 공간 맵은 블록 할당 및 해제 정보를 로그(log) 형태로 저장하고, 이를 균형 트리로 관리하여 효율성을 높임.
- 연속된 빈 블록을 하나의 엔트리로 합쳐 크기를 줄임.
14.5.6 TRIM을 이용한 블록 정리 (TRIMing Unused Blocks)
- HDD와 달리 NVM 플래시 기반 스토리지 (SSD 등) 는 블록을 덮어쓰지 못하고, 먼저 삭제(Erase)해야 함.
- TRIM(ATA) 또는 Unallocate(NVMe) 명령을 사용하여, 파일 시스템이 스토리지에 블록이 비어 있음을 알림.
- 이를 통해 미리 블록을 삭제하고, 쓰기 성능 저하 (Write Cliff) 를 방지하여 일정한 성능을 유지할 수 있음.
'운영체제 공룡책' 카테고리의 다른 글
| [운영체제 공룡책] 13장 File -System Interface (0) | 2025.03.24 |
|---|---|
| [운영체제 공룡책] 12장 I/O Systems (0) | 2025.03.22 |
| [운영체제 공룡책] 11장 Mass -Storage Structure (0) | 2025.03.19 |
| [운영체제 공룡책] 10장 가상 메모리 (0) | 2025.03.18 |
| [운영체제 공룡책] 9장 메인 메모리 (0) | 2025.03.17 |