[OS - File System] File System Implementation

1. Allocation Methods

 

(1) Continuous allocation

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

• cons : 효율적인 file 접근 (순차적, 직접적 접근)
• pros- 공간 확보의 어려움 (외부 단편화, External fragmentation 발생) - File 공간 크기 결정이 어려움 (파일이 커질 경우 고려사항이 많음)

(2) Discontinuous allocation

 

   (2.1) Linked Allocation

• File이 저장된 block 들을 linked list로 연결
• Directory는 각 file에 대한 첫 번째 block에 대한 포인터를 갖는다.
• cons : 간단하고 외부 단편화가 없음
• pros- 직접 접근에 비효율적- 포인터 저장을 위한 공간 필요- 신뢰성 문제 (사용자의 포인터 미스)

   (2.1.1) Linked Allocation : variation (FAT)

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

(MS-DOS, Windows 등에 사용 된다)

 

(2.2) Indexed Allocation

• File이 저장된 block의 정보(pointer)를 Index block에 모아 둔다.
• 직접 접근에 효율적 (순차 접근에는 비효율적임, 계속 Index table을 참조해야하므로)
• File당 Index block을 유지한다. (Space overhead가 발생, Index block 사이즈에 따라 파일 크기 제한)
• Unix 등에 사용된다.

 

2. Free Space Manegement

(2.1) Bit vector

• 시스템 내 모든 block 들에 대한 사용 여부를 1 bit flag로 표시한다. (Bitmap)
• pros : 간단하고 효율적임
• cons : Bit vector 전체를 메모리에 보관하므로, overhead 발생(대형 시스템에는 부적합)

(2.2) Linked list

• 빈 block을 linked list로 연결한다
• 모든 가용공간을 순회해야 하므로, 비효율적임

(2.3) Grouping

• n개의 빈 block을 그룹으로 묶고, 그룹 단위로 linked list 연결 (링크의 수가 줄어든다)
• 연속된 빈 block을 쉽게 찾을 수 있음

(2.4) Counting

• 연속된 빈 block들 중 첫 번째 block의 주소와 연속된 block의 수를 table로 유지한다.(ex start = 0, cnt = 6 => 0번 블럭부터 5번 블럭까지 free인 상태)

출처 : 한기대 김덕수 교수님 운영체제 강의
https://www.youtube.com/watch?v=3VOqyi-wbJU&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=40&ab_channel=HPCLab.KOREATECH