[OS] File System Implementation

동동·2022년 4월 23일

운영체제(Operating System, OS)

목록 보기

16/19

Allocation of File Data in Disk

Contiguous Allocation
Linked Allocation
Indexed Allocation

직접 접근이 가능 매체라 하더라도 데이터를 어떻게 관리하느냐에 따라 순차접근만 가능한 경우도 있다.
디스크에 파일을 저장하는 방식의 위의 3가지가 있다.

📌 Contigous Allocation(연속할당)

디스크에 파일을 저장할 때는 보통 동일한 크기의 섹터 단위로 나누어서 저장

파일시스템이나 디스크 외부에서 볼 때는 각 각의 동일한 크기의 저장공간을 논리적 블럭이라 부름

메모리관리의 페이징 기법과 유사

단점

external fragmentation(외부 조각이 생길 수 있음)
File grow가 어려움(파일 크기를 키우는데 제약이 있음)
- file 생성 시 얼마나 큰 hole을 배당할 것인가?
- grow 가능 vs 낭비(internal fragmentation)

external fragmentation(외부 조각) : 아무도 사용하지 않음 누군가에게 할당 가능
internal fragmentation(내부 조각) : 누군가에게 할당이 됐지만 사용되지 않음

장점

Fast I/O
- 한 번의 seek / rotation으로 많은 바이트 transfer
- Realtime file용으로, 또는 이미 run 중이던 process의 swapping용
Direct access(=random access) 가능
(시작 위치만 알면 그 위치부터 연속적으로 위치해있기 때문에 시작위치+x 해주면 바로 위치를 알 수 있음)

📌 Linked Allocation

파일이 디스크 빈공간에 아무 곳에나 들어갈 수 있는 방식
파일의 시작위치만 디렉토리가 지니고 있다.
외부조각 문제가 발생하지 않음

장점

External fragmentation 발생 안 함

단점

No random access(직접 접근 불가)
각 블럭에 다음 블럭 위치가 담겨 있기 때문에 중간 위치를 보기 위해서는 앞의 블럭을 다 훑어야 함 생략 불가 따라서 순차 접근만 가능
Reliability 문제
- 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
- 512 bytes/sector, 4 bytes/pointer

변형

File-Allocation Table(FAT) 파일 시스템
포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

📌 Indexed Allocation

아무리 작은 파일이라도 index를 위한 블럭과 실제 파일 저장파일 블럭 나눠서 필요함. 따라서 아주 작은 파일일 경우 공간 낭비라고 볼 수도 있음
장점

External fragmentation이 발생하지 않음
Direct Access 가능

단점

Small file의 경우 공간 낭비(실제로 많은 file들이 small)
Too Large file의 경우 하나의 block으로 index를 저장하기에 부족
- 해결 방안
  - linked scheme
  - multi-level index

📌 UNIX 파일시스템의 구조

어떤 파일시스템이던 부트 블럭이 가장 앞에 나옴.(컴퓨터를 킬 때 부팅한다고 함)

파일의 메타데이터는 파일 디렉토리에 있다고 앞에 나왔음. 근데 실제 파일 시스템에서는 파일의 모든 메타데이터를 파일 디렉토리에서 가지고 있지 않음
별도의 위치에 빼서 가지고 있는데 (Inode list)라는 곳에 가지고 잇음
inode(index node)에서 파일의 메타 데이터를 가지고 있는데 파일의 이름은 디렉토리가 직접 가지고 있음

inode를 가지고 있다는게 유닉스 파일시스템의 특징이다. Indexed allocation을 아주 살짝 변형해서 사용

파일의 크기가 아주 작을 경우 direct index만을 가지고 파일 위치 정보 표시 가능(직접적으로 위치 표시 가능)
엄청 큰 파일은 single indirect를 사용함. 파일 위치를 직접적으로 가리키지 않고 인덱스 파일의 위치를 가리킴

더 큰 파일은 double indirect를 사용. 인덱스 파일을 가리키지 않고 한번 거쳐야 인덱스 파일이 나옴

더더 크면 triple indirect 3단계 인덱스

📌 FAT File System

파일의 거의 모든 메타데이터를 디렉토리가 가지고 있고 FAT 영역에 다음 블럭의 위치를 가지고 있음 처음 위치는 디렉토리에 있음
linked allocation 활용 근데 linked allocation에서는 직접 접근이 안됐는데 FAT File System에서는 직접접근이 가능하다. linked allocation의 단점들을 모두 극복.

🚧 Free-Space Management

Bit map or bit vector
- Bit map은 부가적인 공간을 필요로 함
- 연속적인 n개의 free block을 찾는데 효과적
Linked List
- 모든 free block들을 링크로 연결(free list)
- 연속적인 가용공간을 찾는 것은 쉽지 않다.
- 공간의 낭비가 없다.
Grouping
- linked list 방법의 변형
- 첫번째 free block이 n개의 pointer를 가짐
  - n-1 pointer는 free data block을 가리킴
  - 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐
Counting
- 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안
- (first free block / # of contiguous free blocks)을 유지