[운영체제] 파일 시스템 2 : 디스크 할당, UNIX 파일 시스템, FAT 파일 시스템, Free Space Management, Directory Implementation, VFS & NFS, Page cache & Buffer cache

파일시스템 2
(참고 강의 : http://www.kocw.net/home/search/kemView.do?kemId=1046323)

Allocation of File Data in Disk

그럼 각각의 파일 데이터들을 디스크에 어떻게 할당을 할까?

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

각각의 '이론'들을 살펴보자. 메모리 할당과 크게 다르지 않다.

1. Contiguous Allocation = 연속할당

각 블록은 512 byte라고 한다.
512byte 넘는 파일은 연속해서 블록을 할당해주는 것이다.
디렉토리는 '파일명/시작/길이'의 리스트를 가지고 있다.

어떤 장단점이 있을지 당신은 이미 50% 알고 있다.

<장점>

• Fast I/O
  - 한번의 seek/rotation으로 많은 바이트 transfer
  -reatime file 용으로, 또는 이미 run 중이던 process의 swapping 용
• Direct access(=random access) 가능

하드 디스크 읽는데 걸리는 시간의 대부분은 디스크 헤드를 이동하는 시간이라고 한다.(마치 LP판 헤드 옮기듯)
연속 할당이라면 한 번만 찾으면 된다. 또한 Direct access가 가능하며, realtime file이나 swapping 용으로 적합하다.

<단점>

• external fragmentation
• file grow 어려움
  -file 생성시 얼마나 큰 hole을 배당할 것인가?
  -grow 가능 vs 낭비 (internal fragmentation)

연속 할당이기에, 파일이 갈수록 커진다면 남의 영역을 침범할 수 있다. 따라서 처음에 얼마나 큰 hole을 포함해 할당해줘야 할지, 그렇다고 너무 많은 영역을 할당해주면 내부 조각이 생길 수 있으니, 어려움이 있을 것이다.

2. Linked Allocation

Linked List를 만들어 하나의 파일을 여러 블록에 불연속 할당이 가능하다.

<장점>

• External fragmentation 없음

불연속할당이니 조각이 생길 리 없다.

<단점>

• No random Access
• Reliability 문제
  -한 섹터 고장나 pointer 유실되면 그 뒤에 다 잃음
• Pointer를 위한 공간이 block의 일부가 되어 공간 효율성 떨어뜨림
  - 512 bytes/sector, 4 bytes/pointer
  

<변형>

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

Linked list이니 특정 순서 읽고 싶으면 처음부터 읽어야 한다.
또 중간에 하나 포인터 잘못되면 그 뒤 전부 못 읽는다.
또 하나의 블록이 512 바이트인데, 포인터로 4bytes와 나머지는 파일 내용이니 공간 효율성이 떨어진다.

뒤에서 살펴 볼 FAT 파일 시스템은 위 단점들을 보완하기 위해 별도의 공간을 둔다. (자세한 내용은 뒤에 나온다.)

3. Indexed Allocation

파일당 인덱스 블록을 두고, 거기서 포인터들을 배열로 차례대로 저장해 놓은 방식이다.

<장점>

• External fragmentation 없음
• Direct Access 가능

<단점>

• small file 경우 공간 낭비
• too large file의 경우 하나의 블록으로 index 다 저장하기에 부족
  - 해결 방법 : linked scheme, multi-level index
  

실제로 대부분의 파일들이 ㅈㄴ 작은 파일들이다. 얘들을 위해 인덱스를 만들어주는게 얼마나 낭비인가.
파일이 너무 커서 인덱스가 너무 많을 경우, 맨 마지막에 다른 인덱스를 가르키는 포인터를 넣어서 이어 붙이던가, 멀티 레벨로 인덱스를 표현할 수 있겠다.

위 3가지는 파일 할당의 이론이고, 실제로 어떻게 적용하는지 보자.

UNIX 파일 시스템

Boot Block (모든 파일 시스템 공통)

• 부팅에 필요한 정보 (bootstrap loader)

Super block

• 파일 시스템에 관한 총제적인 정보

Inode list

Inode

• 파일 이름을 제외한 파일의 모든 메타 데이터를 저장

Data block

• 파일의 실제 내용 보관
  

UNIX 파일 시스템의 핵심은 Inode이다.
Data block에는 '파일 이름 - inode 번호'만 있다.
inode list에는 파일마다 정해진 크기의 inode가 있고, 이 안에 이름 뺀 모든 메타 데이터들이 담겨 있다.
여기에는 파일이 디스크에 어떤 블록에 흩어져 있는지도 나와 있는데, 파일이 ㅈㄴ 작을 경우 direct blocks 안에 위치가 적혀 있고, 좀 더 크면 single indirect, 더 크면 double...

FAT 파일 시스템

윈도우, 모바일에서 많이 사용하는 파일 시스템이다.
Data block의 directory file에는 '파일 이름 - 메타데이터 - FAT 포인터' 가 담긴다.
실제 파일 내용도 Data block 어딘가에 담겨 있다.
(UNIX와 달리 모든 메타 데이터들이 Data block에 담긴다.)

FAT에는 Data block 수 만큼 block이 존재하고, 각 블록에는 다음 위치 포인터만 있다.
위 그림을 보면 217-618-339-끝 이 연결되있는 것을 알 수 있다.
이를 Data block에서 실제로 읽으면 되는 것이다.

Linked Allocation의 단점인

• 중간에 끊겨서 유실
• block마다 포인터 4 byte 공간 낭비

를 FAT이라는 별개의 Partition을 둬서 단점을 지울 수 있는 것이다.

이 외에도 ㅈㄴ 많은 파일 시스템들이 존재한다고 한다.

Free Space Management

그럼 Data block의 block에서 어디가 비어있는지 어떻게 알아내나?

1. Bit map or bit vector

• 부가적인 bit map 공간 필요
• 연속적인 n개 free block 찾는데 효과적

UNIX에서는 Super block에 저장된다.
연속 할당을 쓰지 않더라도, 기왕 연속으로 할당되면 좋기에 이런 걸 찾는데 좋다.

2. Linked list

• 모든 free block들을 링크로 연결 (free list)
• 연속적인 가용공간 찾기 어려움
• 공간 낭비 없음

빈 블록에 다음 빈 블록을 가리키는 포인터만 저장하는 것이다. 따로 비트맵이 필요가 없으니 공간 낭비는 없을 것이다.

3. Grouping

• linked list 변형
• 첫번째 free block이 n개의 pointer를 가짐
  -n-1 pointer는 free data block을 가리킴
  -마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐
  

첫 블록에 빈 블록이 다 안 담긴다면, 위에서 봤던 index allocation처럼 또 다른 index 블록을 가리키고 이어서 빈 블록들을 가리킬 수 있다.

4. Counting

• 프로그램들이 종종 여러 연속적인 block을 할당하고 반납한다는 성질에 착안
• (first free block, # of contiguous free blocks) 유지

grouping을 좀 더 발전 시켜서, 연속적인 빈 블록을 실제로 다 따라가면서 알려주는 게 아니라 대놓고 몇개의 빈 연속블록이 있다는 것을 표시하는 방법이다.

Directory Implementation

Linear List

• filename - metadata의 list
• 구현 간단
• 디렉토리 내 파일 찾으려면 linear search 필요 (다 뒤져)

Hash table

• Linear List + hashing
• Hash table은 file name을 파일의 linear list 위치로 바꿔줌
• 탐색 시간 O(1)
• 충돌 가능성은 있음

디렉토리 파일을 file name, metadata로, 정해진 크기의 공간을 할당해서 적용한다.
그럼 파일 이름이 ㅈㄴ 길어서 용량을 초과한다면?

Long file name 지원

• list의 각 entry 크기는 고정
• file name이 더 길어진다면 entry 마지막 부분에 이름 뒷 부분이 위치한 포인터를 두는 방법
• 나머지 부분은 동일한 directory file 일부에 존재

File의 Metadata 보관 위치

• 디렉토리 내에 직접 보관
• 디렉토리에는 포인터를 두고 다른 곳에 보관(inode,FAT)

VFS & NFS

Virtual File System(VFS)

• 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 Layer

Network File System(NFS)

• 분산 시스템에서는 네트워크를 통해 파일 공유 가 가능
• NFS는 분산 환경에서의 대표적인 파일 공유 방법

Page cache & Buffer cache

Page cache

• Virtual memory paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
• Memory Mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용

Memory-Mapped I/O

• File의 일부를 virtual memory에 mapping 시킴
• 매핑 시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함

Buffer Cache

• 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
• File 사용의 locality 활용
  - 한번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전달
• 모든 프로세스가 공용으로 사용
• replacement algorithm 필요 (LRU,LFU)

Unified Buffer cache

• 최근 OS에서는 기존의 Buffer cache가 page cache에 통합됨