[운영체제] 파일 시스템 구현

파일 시스템 구조

디스크의 특징

• 재기록이 가능하다.
• 임의의 블록에 직접접근이 가능하다.

디스크 입출력

• 입출력은 효율성을 위해 블록 단위로 수행된다.
• 하드 디스크 드라이브의 각 블록은 하나 이상의 섹터로 구성된다.

파일 시스템 구현

• MBR(Master Bookt Record) : 컴퓨터를 부팅하는 용도로 사용된다. 디스크의 첫 섹터(섹터 0)에 위치한다.
• Partition table : 각 디스크 파티션의 시작과 끝 주소를 가지고 있다. 테이블에는 하나의 디스크 파티션이 활성(active) 상태로 설정되어 있다.
• Bookt block(부트 블록, 부트 제어 블록) : 일반적으로 한 파티션의 첫 번째 블록이다. 시스템이 파티션으로부터 운영체제를 부트시키는 데 필요한 정보를 가지고 있다.
• Superblock(볼륨 제어 블록) : 볼륨의 블록 수, 블록의 크기, 가용 블록의 수와 포인터, 가용 FCB(File Control Block) 수와 포인터 같은 볼륨 정보를 포함한다.

파일 제어 블록(File Control Block, FCB)

• FCB는 파일에 대한 소유, 허가, 파일 내용의 위치 등, 파일에 관한 정보를 가지고 있다.
• UNIX 시스템에서는 이를 파일 디스크립터(File descriptor)라고 부른다.

디렉터리 구현

선형 리스트로 구현

• 디렉터리를 파일 이름과 데이터 블록에 대한 포인터들의 선형 리스트로 구현하는 방식.
• 구현은 쉽지만, 실행 시간이 길다.
• 파일 생성 : 디렉터리를 탐색해, 같은 이름을 가진 파일이 존재하지 않음을 파악하고, 디렉터리의 끝에 새로운 항목을 추가한다.
• 파일 삭제 : 디렉터리에서 이름을 찾아 그 파일에 할당된 공간을 방출한다.
• 파일을 찾기 위해선 선형 탐색을 해야 한다는 단점이 있다.

해시 테이블로 구현

• 파일 이름을 제시하면 해시로부터 값을 얻어 이를 포인터로 활용해 리스트에 접근하는 방식.
• 디렉터리 탐색 시간을 상당 부분 개선할 수 있다.
• 해시 테이블이 고정된 크기를 갖고, 테이블의 크기에 따라 해시 기능도 제한을 받을 수 있다는 단점이 있다.

파일 구현(할당 방법)

연속 할당

• 각 파일을 연속된 디스크 블록에 저장한다.
• 파일이 할당되고 반납됨에 따라 가용 디스크 공간이 조각난다. 이로 인해 외부 단편화가 발생한다.

장점

• 구현이 쉽다.
• 읽기 성능이 뛰어나다.

단점

• 시간이 지날수록 디스크 공간이 단편화된다.

연결 할당

• 디스크 블록들을 연결 리스트 형태로 관리한다.
• 연결 할당은 연속 할당의 문제점을 해결한다.
• 파일은 저장장치 블록의 연결 리스트 형태로 저장되고, 이 블록들은 장치 내에 흩어져 저장될 수 있다.

장점

• 연속 할당과는 다르게, 남아있는 모든 디스크 블록이 사용 가능하다. 따라서 디스크 단편화로 인한 공간이 낭비가 발생하지 않는다.
• 디렉터리 엔트리에는 파일의 첫 번째 디스크 블록의 주소만 저장하면 된다. 나머지는 첫 번째 블록으로부터 추적해 찾을 수 있다.

단점

• 순차적 접근 파일에만 효과적으로 사용될 수 있고, 직접 접근 방식에는 비효율적이다. 파일의 한 블록을 찾으려면, 첫 블록의 읽기 작업과 그 이후의 HDD 탐색이 필요하다. 따라서 연결 할당 파일에 대한 직접 접근은 비효율적이다.

연결 할당의 변형 - FAT 사용

• 각 블록에 존재하는 포인터를 메모리내의 테이블 FAT(File Allocation Table)에 저장하는 방식.
• 위 연결 할당에서의 파일 A의 물리 블록 인덱스는 4→7→2→10→12 로 이동한다. 엔트리에 물리 블록 인덱스를 적어줌으로써 체인을 따라 블럭 이동이 가능해진다. 위 그림에서 -1은 더이상 유효한 블록이 없다는 것을 의미한다.

장점

• 직접 접근 속도를 높일 수 있다. 체인이 메모리에 존재하기 때문에 따라가는 데에 디스크 참조가 필요하지 않다.

단점

• 전체 테이블이 메모리에 존재해야만 한다. 따라서 FAT 기법은 디스크 용량이 커지면 이에 대응하지 못한다.