운영체제 11. 파일 시스템 (5) - File System Implementation

출처 : https://www.youtube.com/watch?v=HGT8HbbB_3w&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=42

 

 

 

File System Implementation

 

• Allocation methods
  • File 저장을 위한 디스크 공간 할당 방법
• Free space management
  • 디스크의 빈 공간 관리

 

 

Allocation Methods

 

File에게 디스크 공간을 할당하는 법

• Continuous allocation : 연속된 공간을 할당
• Discontinuous allocation : 비연속적인 공간을 할당
  • Linked allocation
  • Indexed allocation

 

 

Continuous Allocation

 

• 한 File을 디스크의 연속된 block에 저장
• 장점
  • 효율적인 file 접근 (순차, 직접 접근)
• 문제점
  • 새로운 file을 위한 공간 확보가 어려움
  • External fragmentation
  • File 공간 크기 결정이 어려움
    • ex) 그림에서 제일 큰 빈 공간이 6 block인데, 6block짜리 file C를 적재했을 때, file C를 append를 한다던지 해서 파일이 커지면 연속된 공간에 적재할 수가 없게됨 
    • 파일이 커져야 하는 경우 고려해야 함

 

 

Discontinuous allocation - Linked Allocation

 

• File이 저장된 block들을 linked list로 연결
  • 비연속 할당 가능
• Directory는 각 file에 대한 첫 번째 block에 대한 포인터를 가짐
• 장점
  • 간단함
  • external fragmentation 없음
• 단점
  • 직접 접근에 비효율적
  • 포인터 저장을 위한 추가적인 공간 필요
  • 신뢰성 문제 -> 파일을 사용할 수 없게 됨
    • 사용자가 포인터를 실수로 건드리는 문제 등
• 공간을 할당하기에는 좋지만, 직접 접근할 때 비효율적이고 포인터를 통한 연결로 인해 필요한 용량의 크기가 커지고 포인터를 잘 못 건드리면 파일을 날려버릴 수 있는 문제가 있다.

 

 

Linked Allocation : variation -> FAT

 

• File Allocation Table (FAT)
  • 각 block의 시작 부분에 다음 블록의 번호(link)를 기록하는 방법
  • File을 좀 더 빠르게 탐색할 수 있음
• MS-DOS, Windows 등에 사용 됨

 

 

Discontinuous Allocation - Indexed(목차) Allocation

 

• File이 저장된 block의 정보(pointer)를 Index block에 모아 둠
• 직접 접근에 효율적
  • Index table에 적힌 정보를 통해 내가 원하는 파일의 주소를 보고 바로 찾아갈 수 있으니 직접 접근에 효율적이다.
  • 순차 접근에는 비효율적. 다음으로 넘어갈 때마다 인덱스 테이블로 돌아와서 다음 block의 해당 주소를 찾아가야함
• File 당 Index block을 유지
  • Space overhead. Index table을 유지하기 위한 추가 공간이 필요함
  • Index block 크기에 따라 파일의 최대 크기가 제한 됨
• Unix 등에 사용 됨

 

 

다음은 Free Space Management 즉, 빈 공간을 어떻게 관리하는가에 대해서 배운다.

 

 

Free Space Management

 

• Bit vector
• Linked list
• Grouping
• Counting

 

 

Bit Vector

 

• 시스템 내 모든 block들에 대한 사용 여부를 1 bit flag로 표시. 빈 공간은 0 할당된 공간은 1로 표시
• 장점
  • 간단하고 효율적임
• 단점
  • Disk의 용량이 커짐에 따라 Bitmap 또한 커지게 됨, Bit vector 전체를 메모리에 보관해야 함 -> 메모리에서 차지하는 공간이 커짐 = overhead
    
    • 대형 시스템에 부적합

 

 

Linked list

 

• 빈 block을 linked list로 연결
• 비효율적
  • link 저장을 위한 추가적인 공간이 필요 (공간적인 비효율성)
  • 직접 접근에 비효율적임 (탐색 시간적인 비효율성)

 

 

Grouping

 

• n개의 빈 block을 그룹으로 묶고, 그룹 단위로 linked list로 연결 -> 필요한 링크의 수가 link / n으로 감소하게 됨
• 연속된 빈 block을 쉽게 찾을 수 있음

 

 

Counting

 

• 연속된 빈 block들 중 첫 번째 block의 주소와 연속된 block의 수를 table로 유지
  • ex) 비어있는 공간이 0, 1, 2, 3, 4, 5 라면 0(비어있는 첫번째 block의 주소), 6(연속된 block의 수)라고 적음
• 빈 공간들을 효율적이고 빠르게 찾을 수 있음
• Continuous allocation 시스템에 유리한 기법