[OS] 파일 시스템의 구현

파일 시스템의 구현

디스크 파일 시스템

• Boot control block (부트 제어 블럭)

• Volume control block (볼륨 제어 블럭) = 슈퍼 블록

• 볼륨(혹은 파티션)의 블록 수, 블록 크기, 가용 블록 수와 포인터, 가용 FCB 수와 포인터 등의 파티션 정보 저장

• Inode table

• FCB (File Control Block) : unix 에서는 inode

Allocation method

Contiguous allocation ( 연속 할당 )

하나의 파일에 무조건 연속적인 디스크 block 을 할당 : First fit, best fit, worst fit

External fragmentation 이 발생 → Compaction offline or online ( 한 쪽으로 몰아서 정리 )

Linked allocation ( 비연속 할당 )

링크드 리스트 방식으로 메모리를 할당하는 방식

파일이나 디렉토리의 시작 block 과 끝 block 만을 갖고 있으면서, 각 block 은 다신의 다음 block 을 가리키는 포인터를 지님

파일 전체를 읽어들이는 Sequential search 가 느리며 데이터가 아닌 포인터 정보를 저장하는 탓에 메모리를 낭비한다는 단점이 있음

 

FAT ( Files Allocation Table )

디스크 블록 각각에 링크드리스트 정보를 넣는 것이 아닌 allocation 테이블을 만들어두어 관리하는 기법

디렉터리의 경우에는 첫 번째 파일의 첫 번째 블록 번호를 가리킴

Random access time 을 개선할 수 있음

Indexed

각 파일마다 자신만의 index block 을 가짐

index block 에는 해당 파일이 차지하는 block 들의 리스트가 쭉 저장되어 있으며, 이는 파일의 Random access를 구현할 때 기존의 방식대로는 모든 block 을 sequential 하게 읽어야 했다는 단점을 해결함

단점 : 하나의 block 자체가 낭비된다는 점. 파일이 너무 크면 하나의 index block 으로는 표현이 불가능 하다는 점

메모리에서 해결했던 것처럼 multilevel index block 을 통해 해결 가능

Free space 관리

Bit vector, bit map

디스크의 free space 를 관리하는 기법으로 디스크 블럭 사이즈만한 bit 배열을 두고, 가용하면 1, 누군가 사용중이면 0으로 표시하는 기법

free space 계산법

(0 인 word 수) * (word 의 bit 수) + offset 1비트

bit map 크기 계산

block size = 4KB = 212 bytes

disk size = 1TB = 240 bytes

n = 240 / 212 = 228 bits = 32 MB

 

32MB 에서 더 줄이고 싶다면 block 단위에서 N 개의 block 을 묶은 cluster 단위로 available list 를 관리하면 됨

예를 들어 4개를 한 묶으로 관리하면 8MB 로 줄어듦 → 대신 internal fragmentation 이 발생

 

Linked list 방식

위와 같이 free space 가 다음 free space 를 가리키는 방법으로 사용함. 이 또한 포인터 정보로 블럭이 낭비된다는 단점이 있지만 디스크 용량이 워낙 크기에 요즘 많이 사용하는 방법임

단점 : 연속된 공간을 찾는게 어렵다.