File System Implementations

디스크에 파일의 데이터를 저장하는 방법

Contiguous Allocation(연속 할당)

하나의 파일이 디스크상에 연속해서 저장되는 방법이다.

외부조각이 생길 수 있고 파일의 크기가 커지는데 어려움이 있다.
파일이 커질 것을 대비해서 미리 공간을 할당해 놓으면 내부조각이 생긴다.

빠른 I/O가 장점이고 직접접근이 가능하다.

Linked Allocation(연결 할당)

외부조각이 발생하지 않는다.

직접접근이 되지 않고 데이터의 중간에 배드섹터가 나면 포인터가 유실되고 뒷 부분을 상실하게 되어 reliability문제가 생긴다. 그리고 포인터를 위한 공간이 블록의 일부가 되어 공간 효율성이 떨어진다.

linked allocation을 변형한 File-allocation table(FAT)파일 시스템은 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제를 해결한다.

Indexed Allocation

외부조각이 생기지 않으면서 직접접근이 가능하다.

작은 파일의 경우에는 공간 낭비가 있다.
너무 큰 파일은 인덱스 블록 하나로 표시를 하기엔 부족하기 때문에 linked scheme이나 multi-level index를 사용하면 된다.
linked scheme은 인덱스 블록의 크기가 부족할 때는 마지막에 또다른 인덱스 블록을 가리키게 한다.
multi-level index는 하나의 인덱스 블록이 직접 파일의 위치를 가리키는게 아니라 또다른 인덱스 블록을 가리키게 해서 2단계로 쓴다.

unix 파일시스템의 구조

• boot block
  부팅에 필요한 정보(bootstrap loader)
• super block
  파일 시스템에 관한 총체적인 정보를 담고 있다.
• inode list
  파일 이름을 제외한 파일의 모든 메타 데이터를 저장한다.
  파일의 이름은 디렉토리가 가지고 있다.
• data block
  파일의 실제 내용을 저장한다.

위에서 부터 순서대로 구성되어 있다.

FAT File System

Free-Space Management

메모리에서 비어있는 블록을 관리하는 방법

bit map or bit vector

0	1	2	…	n-1
1	0	1	…

비어있는 블록은 0 아니면 1을 넣는다.
부가적인 공간을 필요로 하며 연속적인 n개의 비어있는 블럭들을 찾는데 효과적이다.

linked list

모든 비어있는 블럭들을 링크로 연결한다.
연속적인 빈 공간을 찾는 것은 쉽지 않고 공간의 낭비가 없다.

grouping

첫번째 빈 블럭이 n개의 포인터를 가진다.
n - 1 포인터는 빈 블럭을 가리킨다.
마지막 포인터가 가리키는 블럭은 다시 n개의 포인터를 가진다.

linked list보다는 낫지만 그래도 연속적인 빈 공간을 찾는데 좋지는 않다.

counting

빈 블럭의 첫 번째 위치와 거기서 부터 몇개가 빈 블럭인지를 관리한다.

Directory Implementation

디렉토리 구현 방법

linear list

file name	file의 metadata
aaa	aaa의 metadata
bbb	bbb의 metadata
…	…

구현이 간단하지만 특정 파일을 찾을려면 linear search를 하므로 연산에 시간이 많이 필요하다.

hash table

파일의 이름에 hash함수를 적용한다.
hash함수는 어떤 입력값을 주더라도 결과값이 특정 범위 안의 숫자로 한정이 된다.
특정 파일을 찾을려면 hash함수로 변환된 해당 인덱스로 바로 접근하면 된다.

변환시에 중복되어 충돌이 발생 가능하다.

Page Cache and Buffer Cache

Page Cache

가상 메모리의 페이징 시스템에서 사용하는 페이지 프레임을 캐싱의 관점에서 설명하는 용어이다.

Buffer Cache

파일의 데이터를 사용자가 요청했을 때 디스크에서 읽어와서 사용자에게 전달하고 운영체제가 읽어온 내용을 자기의 영역중 일부에 저장해 놓고 동일한 파일의 데이터를 다시 요청하면 디스크까지 가지 않고 buffer cache에서 바로 읽어다 준다.

가상 메모리 관점에서는 page cache라 하고 파일 시스템 관점에서는 buffer cache라 한다.