디렉터리 구현

디렉터리는 파일 이름과 해당 파일의 속성 및 디스크 위치를 연결하는 핵심적인 데이터 구조입니다. 효율적인 디렉터리 구현은 파일 시스템 성능에 직접적인 영향을 미칩니다.

1. 디렉터리 엔트리의 구성과 메타데이터 위치 📌

디렉터리 엔트리(Directory Entry)는 일반적으로 파일 이름과 **파일의 속성(메타데이터)**을 저장합니다. 이 메타데이터를 저장하는 방식은 **링크(Hard Link)**의 구현 용이성에 영향을 미칩니다.

구현 방식	엔트리 내용	하드 링크 구현	파일 접근 I/O 비용
FCB 위치 포인터 저장 (Inode 방식)	파일 이름 + FCB의 디스크 주소 (예: i-node 번호)	매우 용이. 여러 엔트리가 같은 i-node를 참조.	2회 (디렉터리 검색 FCB 읽기)
FCB 자체 포함	파일 이름 + 파일의 모든 속성 정보 (FCB 전체)	어려움. 모든 FCB 복사본을 일관성 있게 업데이트해야 함.	1회 (디렉터리 검색 시 정보 확보)

2. 디렉터리 파일의 검색 구조: 성능 분석 🚀

디렉터리 검색은 파일 시스템에서 가장 자주 발생하는 작업이므로, 검색 메커니즘은 매우 중요합니다.

2.1. 선형 리스트 (Linear List)

• 구조: 디렉터리 파일 내의 모든 엔트리를 순차적으로 연결된 리스트 형태로 저장합니다.

• 검색 방법: 파일 이름이 일치할 때까지 리스트의 처음부터 순차적으로 비교합니다.

• 성능: 평균 검색 시간 복잡도는 $O(n)$입니다 (n은 디렉터리의 파일 수). 파일이 많아지면 성능 저하가 급격합니다.

• 공간 관리:

  • 가변 길이 레코드를 사용할 경우, 파일 이름 길이에 따라 엔트리 크기가 달라지며, 삭제 시 남는 공간을 재활용하기 어려워 단편화가 발생하기 쉽습니다.

  • 고정 길이 레코드를 사용할 경우, 공간 재활용은 쉽지만 파일 이름 길이에 제약이 생깁니다.

2.2. 해시 테이블 (Hash Table)

• 구조: 파일 이름을 해시 함수를 통해 변환하여 디렉터리 내의 **특정 위치(버킷)**로 직접 접근하는 방식을 사용합니다.

• 성능: 충돌이 적절히 관리된다면, 검색 시간 복잡도는 $O(1)$에 가깝습니다. 대규모 디렉터리에 최적의 성능을 제공합니다.

• 구현 난이도:

  • 충돌 관리: 충돌이 발생하면 **체이닝(Chaining)**이나 개방 주소 지정(Open Addressing) 등의 복잡한 메커니즘을 사용하여 처리해야 합니다.

  • 테이블 크기: 해시 테이블의 크기가 고정되어 있어, 디렉터리 크기가 예상치를 초과할 경우 **재조정(rehashing)**하는 데 비용이 큽니다.

3. 디렉터리 성능 최적화: 캐싱과 데이터 구조 💡

디스크 접근 속도와 CPU 처리 속도 간의 차이를 줄여 디렉터리 검색 성능을 극대화하기 위한 기법들입니다.

• 디렉터리 엔트리 캐시 (Directory-Entry Cache, DEC):

  • 역할: 가장 최근에 사용된 파일 이름과 그에 대응하는 FCB 주소(inode 번호) 쌍을 메모리에 캐시합니다.

  • 효과: 디렉터리를 탐색할 때 캐시에 히트하면, 디스크 I/O 없이 바로 FCB 주소를 얻을 수 있어 성능이 크게 향상됩니다.

• B-Tree 구조: 매우 큰 디렉터리(수십만 개의 파일)를 관리하는 경우, 선형 리스트나 해시 테이블 대신 B-Tree와 같은 트리 구조를 사용하여 검색 성능을 $O(\log n)$으로 개선할 수 있습니다. 이는 특히 파일 시스템 메타데이터의 영속성이 중요한 저널링 파일 시스템에서 활용될 수 있습니다.