File system implementation

 

1. Allocation methods

    - File 저장을 위한 디스크 공간 할당 방법

 

1) Continuous allocation

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

 

    - 장점

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

 

    -  단점

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

        * 외부 단편화 문제

        * File의 크기가 커질 경우, 공간을 확보해야 하는데 연속되게 공간 확보을 못할 수 있음

 

 

2) Discountiunous allocation

(1) Linked allocation

    - File이 저장된 block들을 linked list로 연결

   

    - 장점

        * 외부 단편화 없음

        * 간단한 구현

 

    - 단점

        * 직접 접근하는데 O(n) 시간 복잡도

        * 포인터 저장 공간 필요

 

    - 사용

        * FAT(File Allocation Table) 방식을 windows에서 사용

 

 

(2) Indexed allocation

    - File이 저장된 block의 정보를 Index table에 저장

    - 장점

        * 직접 접근에 효율적

    

    - 단점

        * File 당 index tableㅇ 필요하기 때문에 공간 overhead

 

 

 

2. Free space management

    - 디스크의 빈 공간 관리

 

1) Bit vector

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

    - 사용중 : 1, 빈 공간 : 0

Bit vector

Disk

    - 장점

        * 간단한 구현

        * 접근이 쉬움

 

    - 단점

        * Bit vector를 메모리 공간에 보관해야 하므로 대형 시스템에 부적합

 

 

2) Linked list

    - 빈 block을 linked list로 연결

 

    - 단점

        * 포인터를 저장할 공간 필요

        * 직접 접근하는데 O(n) 시간 복잡도

 

 

3) Grouping

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

   

그룹핑(N=3)

Disk

    - 장점

        * linked list보다 빠르고 쉽게 접근

 

 

4) Counting

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

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

 

 

 

본 내용은 한국기술교육대학교 김덕수 교수님의 유튜브 강의를 듣고 정리한 내용입니다.