File System Internals_운영체제(13)

File system implementation

• file system을 향상시킬 때 On-disk, in-memory 두 part로 작업을 한다.
• Boot control block / Master Boot Record(MBR) : OS의 booting 정보가 담겨 있는 block, kernel 관련 정보
• Volume control block(super block, master file table) : 여러 개의 독립된 file system(volume)들에 대한 정보를 담고 있는 block
• Directory : file name, inode # 등을 담고 있다.
• File Control Block(FCB) : file에 관한 metadata를 담고 있는 block

File control block

• metadata 또한 block에 저장된다.
• file data block의 pointer를 저장한다. 작은 file의 경우에는 data block을 직접 저장하기도 한다.

In-memory FS structure

• (a) : file을 open할 때
• (b) : file을 read할 때
• user : file descriptor table / kernel : open file table
• kernel에는 중간에 buffer(cache)가 존재한다.

Directory Structure

• Table
• Linear list
  • 만들기는 쉽지만 search time이 오래 걸린다.
• Hash table
  • search time을 줄인 방식

Allocation

Contiguous allocation(연속 할당 방법)

• HDD를 동일한 크기의 block이 연속된 구조로 되어 있고, block 주소로 읽어낸다고 생각을 한다.
• file의 이름, 시작 block 주소, 길이가 directory에 저장되어 있는데, 이는 위의 그림처럼 HDD에 저장되어있다.
• block을 추가 해야할 때 문제가 발생한다.
• 장점
  • disk seek의 수가 최소화된다.
• 단점
  • external fragment가 발생할 수 있다. → 할당은 할 수 있지만 거의 불가능한 경우
  • compaction을 이용하여 external fragment를 해결한다.
  • file size가 계속 변하기 때문에 변하는 공간을 미리 확보하기 어렵다.
• 초창기에만 사용되다가 현재는 CD-ROM과 같이 1번 write하고 이 후 read만 하는 경우에만 사용한다. (WORM)

Extent-based allocation

• 연속 할당을 하는데, disk 공간을 Basic과 Extent로 2가지 영역으로 나눈다.
• basic 영역에 연속 할당을 하다가, 공간이 모자라면 extent 공간을 이용하고 basic에는 할당한 extent 공간의 주소를 가리키도록 한다.
• 장점
  • 여전히 simple하다
• 단점
  • Internal fragmentation : extent가 fixed size일 때, 남는 공간이 너무 큰 경우 발생
  • External fragmentation : extent가 variable size일 때, 중간에 사용하기 힘든 hole이 생겨서 발생
• Veritas File System(VxFS)에서 주로 사용된다.

Linked allocation

• File directory에 start, end가 나타나있고, 해당 구간 내에 불연속적으로 block에 저장한 뒤 link로 연결하는 방식
• 1 block을 4KB(32bit)라고 한다면, block을 개를 지정할 수 있다.
• block은 32bit가 pointer, 4KB-4B 만큼 data를 담는다.
• 단점
  • file을 순차적으로 읽을 때는 괜찮지만, 임의의 위치에 바로 접근하여 읽는 방식이 불가능하다.
  • Fragile : block이 bad sector가 되어서 pointer가 사라지면 link가 끊어져 file이 손실된다.
  • data 공간을 계산하는 데 불편함이 있을 수 있다.

Linked allocation - cluster

• 연속된 block으로 clustering을 하여 link한다.
• 장점
  • 적어도 clustering된 block끼리 읽는 것은 disk throughput을 높일 수 있다.
  • 매 block당 pointer가 있는 것이 아니여서 이러한 공간을 줄일 수 있다.
• 단점
  • Internal fragmentation : cluster 단위로 할당하기 때문에 hole이 발생

Linked allocation - FAT

• pointer를 연결하는 정보를 따로 분리를 한 방식
• File Allocation Table : 해당 block에서 pointer에 대한 정보만 저장
• 장점
  • FAT만 읽어들이면 어떤 file이 어떻게 구성되어있는지 알 수 있어서 seek가 빠르다.
  • random access time이 빠르다.
• 단점
  • 별도의 FAT 공간이 필요하다.

Indexed allocation

• 각 file을 구성하는 block의 pointer를 가리키도록 한다.
• 저장할 수 있는 최대 file size 문제
• 장점
  • direct access를 지원해서 external fragmentation이 없다.
  • Inode가 memory에 있다면 file을 쉽게 찾아갈 수 있다.
• 단점
  • space overhead가 발생할 수 있다.

Performance

• 연속저장이 순차, 랜덤 모두 좋지만, 가변적인 file에 대해 대처가 어렵다.
• linked는 순차에는 좋지만 랜덤에는 좋지 않다.
• file 생성 시 어떻게 access를 할 것인지 선언을 하도록 한다.
• index 방법은 flexible하지만 구현하는 데 있어서 복잡하다.

Free Space Management

Bitmap

• array를 사용, 각 칸이 bit인데 1이면 free, 0이면 사용 중
• bit 1이 free → block 1이 free와 같이 해석
• CPU에서 0이 아닌 첫 번째 1이 나타나는 bit가 어디인가를 check한다.
• 연속된 block을 clustering하여 비어있는 지 확인하는 방식도 존재한다.
• 꽤 많은 용량을 차지하기도 한다.

Linked list

• free block에 대한 정보를 pointer를 이용하여 link 형식으로 나타낸다.
• 대부분 head가 빈 block
• 중간에 link 정보가 사라지면 link 이후의 정보가 다 사라질 수 있다.

Grouping

• n개의 block을 clustering하여 n-1개의 free block의 address를 첫 번째 block에 적어둔다.

Counting

• 다음에 연속적으로 free인 block이 몇 개 있는지 block에 저장해두는 방식
• 할당될 때마다 count를 1개씩 줄여나간다.

Reliability

File system consistency

• system이 멈춰서 file 작업이 저장되지 않은 상황을 inconsistent state라고 한다.
• inode block, directory, free list에 문제가 발생하면 심각한 상황이 초래된다.

fsck : checking block/directory

• block : 사용되고 있는 block 정보, free block 정보를 대조하여 check한다.
• directory : inode와 관련되어있는 link(hardlink)를 찾는다.

Journaling file systems

• file이 update될 때, disk에 반영되기 전 crash가 된 상황에서 이전 기록들(log, journal)을 불러오는 방식
• update하면서 중간중간에 log에 기록을 한다.
• crash가 발생하면 journal을 확인하여 부분적으로 완료하거나 undo로 바꾼다.

Partitions & Mounting

• Partition : file system을 설치할 수 있는 기본 단위
• file system을 contain하면 1개의 volume이라고 한다. - raw format
• Boot block : boot volume/boot loader를 가리키는 block
• Root partition : OS에서 기본적인 file system을 담고 있다.

Virtual File System

• 상위에서 가장 일반적으로(generic) 지원해야하는 operation을 담고 잇다.
• vnode : virtual file system에서 가리키는 것 / inode : 실제 system에서 가리키는 것

Efficiency & Performance

Efficiency

• disk 할당 방법 / directory algorithm
• file directory entry들에 어떤 정보가 담겨 있는지
• metadata의 할당 방법
• data structure의 size

Performance

• 실제 data와 metadata는 가급적 가까이 둔다.
• Buffer cache : 중간에 임시 저장을 하여 효율을 높인다.
• Synchronous write : buffering 없이 disk로 바로 간다. / Asynchronous write : buffer 이용 방식
• Free-behind/read-ahead
• read가 write보다 느리다

Page Cache

• Memory-mapped I/O가 사용한다.
• 중간 다리 역할을 하기 때문에 disk I/O를 줄여준다.
• 같은 data가 page cache와 buffer cache 둘 다 존재하는 문제가 있다.