48_디렉토리 구현 (Directory Implementation)

48_디렉토리 구현 (Directory Implementation)

 

디렉토리를 구현하는 공간을 어떻게 할당하고 관리하는가? 파일 시스템의 효율, 성능과 이들 알고리즘 장단점을 알아 보자.

 

[선형 리스트 (Linear List)]

디렉토리를 구현하는 가장 간단한 방법은 파일 이름과 자료 블록에 대한 포인터들의 선형 리스트를 디렉토리에 사용하는 것이다.

 

선형 리스트는 프로그래밍이 쉽지만 실행 시간이 길다. 새로운 파일을 생성하기 위해 먼저 디렉토리를 탐색하여 같은 이름의 존재 여부 확인 후 끝 부분에 새로운 항목을 첨가한다. 파일을 삭제 하려면 디렉토리에서 이름을 찾아 그 파일에 할당된 공간을 방출 한다. 파일 삭제 시간을 줄이기 위해 연결리스트를 사용할 수도 있다.

 

 

디렉토리 항목을 다시 사용하기 위해서는 몇 가지 방법이 있다.

• 비어있는 항목에 특별한 이름을 부여하거나 각 항목에서 사용되지 않는 비트를 이용하여 비었음이라고 표시
• 비어 있는 항목을 자유 디렉토리 항목의 리스트에 기록
• 자유화된 항목에 제일 마지막 항목을 복사해 넣고 디렉토리의 길이를 하나 줄이는 방법

 

선형 리스트로 구성된 가장 큰 단점은 파일을 찾기 위해 선형 탐색을 해야 한다는 것이다. 이는 빈번한 사용으로 인하여 사용자가 체감으로 느낄 정도로 오버헤드가 많다. 최근 많은 운영체제들은 가장 최근에 사용된 디렉토리 정보를 저장하기 위해 소프트웨어 캐시를 구현하여 사용하여 매번 디스크로부터 읽어오는 오버헤드를 감소 시킨다.

 

정렬된 리스트는 이진 탐색을 가능하게 하며 평균 탐색 시간을 줄인다. 그렇지만 리스트가 정렬 상태를 유지하려면 파일을 생성하거나 삭제하는 일이 복잡해 질 수 있다. 정렬을 위해 많은 데이터가 이동할 수도 있기 때문이다. 하지만 정렬된 리스트는 별도의 정렬 작업 없이 정렬된 리스트를 생산할 수 있다.

 

 

[해시 테이블 (Hash Table)]

디렉토리 구조로 해싱 테이블을 사용하기도 한다. 선형 리스트에 디렉토리 항목들이 저장되기는 하지만 해싱(hashing)도 함께 사용한다. 파일 이름을 제시하면 해시로부터 값을 얻어서 그것을 포인터로 활용하여 리스트에 직접 접근할 수 있다. 따라서 디렉토리 탐색 시간을 상당히 개선할 수 있다.

 

 

충돌(collision)에 대한 부분만 보완되면 삽입 삭제도 쉽게 할 수 있다. 해싱 테이블의 가장 큰 단점은 해시 테이블이 고정된 크기를 갖는다는 것이다. 이는 해시 테이블의 크기에 따라 해시 기능도 제한을 받는다.

 

예를 들어 64개의 항목을 갖는 선형 탐사(probing) 해시 테이블을 만든다고 하였을 때 나중에 65번째 파일을 생성하려면 디렉토리 해시 테이블을 키워야 한다. 그 경우 파일 이름을 0~127까지 매핑하는 새로운 해시 함수를 필요로 한다. 이때 기존 디렉토리를 새로운 해시 값에 맞게 다시 매핑 해야 하는 문제가 발생한다.

 

해시테이블의 제한을 개선하기 위하여 체인 오버플로우 해시 함수 테이블을 사용할 수 있다. 각 해시 항목은 하나의 값이 아니라 연결 리스트가 되고 새로운 항목을 연결 리스트에 추가함으로써 충돌을 해결한다. 이제 이름을 찾으려면 충돌하는 테이블 항들의 연결 리스트를 살펴보아야 하기 때문에 상대적으로 늦어지겠지만 이러한 연산은 전체 디렉토리를 선형으로 찾는 것보다 훨씬 빠르다.

 

[참고자료]

Operating System Concepts / 홍릉과학출판사