[OS] 11-5. File System Implementation

File System Implementation

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

 

Allocation Methods

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

 

Continuous Allocation

• 한 File을 디스크의 연속된 block에 저장
• 장점: 효율적인 file 접근 (순차, 직접 접근), (연속적인 것을 알고 있기 때문에)
• 문제점
  • 새로운 file을 위한 공간 확보가 어렵다 (10개짜리 file을 넣을 때 compact해줘야 한다...)
  • External fragmentation이 발생할 수 있다. (새로운 파일이 연속된 공간보다 크기가 작음)
  • File 공간 크기 결정이 어렵다. (파일이 커져야 하는 경우 고려해야 함)
  • 문서의 전체 크기보다 커질경우 문제, 큰 공간을 얼마나 부여해야 하는 것도 문제

 

Discontinuous allocation - Linked Allocation

• File이 저장된 block들을 linked list로 연결함 (비연속 할당 가능)
• Directory는 각 file에 대한 첫 번째 block에 대한 포인터를 가진다.
• 단순함, External fragmentation이 발생하지 않음
• 단점
  • 직접 접근방식에는 비효율적 (읽을 때..)
  • 포인터 저장 공간을 위해 공간이 필요함
  • 신뢰성 문제 발생 (사용자가 포인터를 실수로 건드리는 문제 등)

 

Linked Allocation: Variation → FAT

File Allocation Table (FAT) : 각 block의 시작 부분에 다음 블록의 번호를 기록하는 방법

 

MS-DOS, Windows 등에 사용됨

 

sale-R 파일의 Directory에 시작링크, 블록번호, 다음블록 번호, 다음블록 번호... 들이 저장되어 찾아갈 수 있다. 

 

 

Discontinuous allocation - Indexed Allocation

• 목차를 보고 해당 파일로 찾아감
• File이 저장된 block의 정보(pointer)를 Index block에 모아 둠
• 직접 접근에 효율적 (순차 접근에는 비효율적) (Index 블럭으로 와서 다음 블럭을 찾기 때문에 비효율)
• File 당 Index block을 유지
  • Space Overhead (추가 공간이 필요하다)
  • Index block크기에 따라 파일의 최대 크기가 제한됨
• Unix 등에 사용됨

---

Free Space Mangement (빈공간 관리 방법)

• Bit vector
• Linked list
• Grouping
• Counting

 

Bit Vector

• 시스템 내 모든 Block들에 대한 사용 여부를 1 bit flag로 표시
• (Disk의 각 블록에 대해서 비어있는가 차 있는가 0,1 로 표시)
• Bit vector 전체를 메모리에 보관해야 함 (빈 공간도 저장 -> 공간이 커짐 -> 오버헤드 -> 대형 시스템에 부적함)
• (비트맵을 저장해야 하는 공간이 크기 때문에 부적합하다.)

 

Linked List

• 빈 Block을 linked list로 연결
• 비 효율적 (공간, 탐색시간)
• 링크 라는 공간을 가지고 있어야 하고 공간이 10개가 있다면 10번 따라가야 함

 

Grouping

• n개의 빈 block을 그룹으로 묶고, 그룹 단위로 linked list로 연결
• 필요한 링크의 수가 n으로 나눈만큼 줄어든다.
• 연속된 빈 block을 쉽게 찾을 수 있음
• 링크를 통해서 링크에 대한 overhead나 링크를 여러번 타는 부담을 줄일 수 있다.
•  

 

Counting

• 연속된 빈 block들 중 첫 번째 block의 주소와 연속된 block의 수를 table로 유지
• Continuous allocation시스템에 유리한 기법
• 위의 Grouping에서 링크를 따라가는 방법이 불편하여 나온 기법

출처: https://www.geeksforgeeks.org/file-systems-in-operating-system/

연속된 block을 table 로 기록함.

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---