[OS] Chap14-03 : 파일 시스템 구현_디렉터리 구현

운영체제(Operating System Concepts) 를 읽고 정리한 정리본입니다.

📌 Chap14-03 : 파일 시스템 구현_디렉터리 구현

🫧 디렉터리 구현

1. 선형 리스트
2. 해시 테이블

✨ 선형 리스트

• 간단하게 구현 가능하지만 실행 시간이 길다.

다음은 선형 리스트를 활용한 새 파일 추가 과정이다.

1. 디렉터리 탐색
2. 파일명이 중복되지 않는다면 디렉터리 끝부분에 새 파일 추가

생성과 마찬가지로, 삭제도 디렉터리 탐색 후 제거하는 과정을 거친다.

또한 디렉터리 항목을 재사용하기 위해서는 다음과 같은 방식을 채택할 수 있다.

1. 항목을 미사용으로 표시
   -> 이름이 모두 공백인 것과 같이 특수 이름으로 변경하거나 유효하지 않은 inode 지정, 항목마다 사용-미사용 비트 추가 등으로 표시

2. 가용 디렉터리 항목에 리스트 추가

✨ 해시 테이블

• 파일 이름을 통해 해시로부터 값을 얻는다. 이를 포인터로 활용해 리스트 직접 접근이 가능하다.

해시 테이블이 고정된 크기를 가진다는 점과 해시 테이블의 크기에 따라 해시 기능도 제한을 받는다는 문제가 있다.

만일 해시 테이블이 부족하다면 크기를 키워야 하고, 이는 새로운 해시 함수가 필요함을 야기하기 때문이다.

이러한 문제를 보완하기 위해 체인 오버플로우 해시 테이블을 사용할 수 있다.

각 해시 항목을 하나의 값이 아닌 연결 리스트로 구현함으로써 해시 테이블의 문제 뿐 아니라 선형 리스트에 대한 문제도 해결할 수 있을 것이다.