[PintOS, Project 4] File System Implementation

 

File System Implementation

  ㆍAllocation methods : File 저장을 위한 디스크 공간 할당 방법

  ㆍFree space management : 디스크의 빈 공간 관리

 

 

 

Allocation Methods

Continuous Allocation

  - 한 File을 디스크의 연속된 block에 저장

  - 장점 :

     ㆍ효율적인 file 접근 (순차, 직접 접근)

  - 문제점 : 

     ㆍ새로운 file을 위한 공간 확보가 어려움

     ㆍ외부 단편화

     ㆍFile 공간 크기 결정이 어려움 : 파일이 커져야 하는 경우를 고려해야한다.

 

 

Linked Allocation

  - File이 저장된 block들을 linked list로 연결 : 비연속 할당 가능

  - Directory는 각 file에 대한 첫번째 block에 대한 포인터를 가짐

  - 장점 : 

     ㆍ구현이 단순함

     ㆍ외부 단편화 없음

  - 단점 :

     ㆍ직접 접근에 비효율적

     ㆍ포인터 저장을 위한 공간 필요

     ㆍ신뢰성 문제

         예) 사용자가 포인터를 실수로 건드리는 문제 등

 

 

FAT (File Allocation Table)

  - 각 blokc의 시작 부분에 다음 블록의 번호를 기록하는 방법

  - MS-DOS, Windows등에 사용 됨

그림 1. FAT 방식

 

 

Index Allocation

  - File이 저장된 block의 정보 (pointer)를 Index Block에 모아 둠

  - 직접 접근에 효율적 → 순차 접근에는 비효율적

  - File 당 Index block을 유지

     ㆍSpace overhead

     ㆍIndex block 크기에 따라 파일의 최대 크기가 제한 됨

     ㆍUnix 등에 사용 됨

그림 2. Index Allocation

 

 

Free Space Management

Bit Vector

  - 시스템 내, 모든 block들에 대한 사용 여부를 1bit flag로 표시

  - 단순하면서도 효율적이다.

  - Bit vector 전체를 메모리에 보관해야한다.

     ㆍ대형 시스템에 부적합

 

Linked List

  - 빈 block들을 linked list로 연결

  - 비효율적

 

Grouping

  - n 개의 빈 block을 그룹으로 묶고, 그룹 단위로 linked list로 연결

  - 연속된 빈 block을 쉽게 찾을 수 있음

 

Counting

  - 연속된 빈 block들 중 첫번째 block의 주소와 연속된 block의 수를 table로 유지

  - Continuous allocation 시스템에 유리한 기법