File System Implementation

파일 시스템은 여러 단계로 구성되어 있다.

어플리케이션 프로그램 - 로지컬 파일 시스템 - file-organization module -  basic file system - I/O control - devices

Device drivers
메인 메모리와 디스크 사이의 정보 전송
효율을 위해 block단위로 전송된다. (하나의 block은 하나 이상의 sector)

Basic file system
디바이스 드라이버에게 명령을 보낸다.
device driver가 제공하는 함수를 사용한다.
각각의 physical block은 disk의 주소로 구분된다.

File organization module
logical block address를 physical address로 바꾼다.
Free space manager가 할당되지 않은 block들을 관리하고 있다가 요청이 들어오면 File organization module에게 block들을 제공한다.

Logical file system
metadata 정보를 다룬다. (실제 데이터를 제외한 모든 파일에 대한 정보)
FCB(file control block)을 통해 디렉토리 구조를 관리한다.

File system structure를 메모리에 올려놓고 쓰기

 출처 : Operating System Principles seventh edition
(a)는 file을 open할 때, (b)는 read할 때

Virtual File System
서로 다른 파일 시스템들이 같은 파일 시스템에 있는 것처럼 해주는 시스템.
한 시스템콜(예를 들면 open)을 사용해서 여러 파일 시스템을 이용할 수 있도록 한다.

Directory Implementation
효율적인 디렉토리 할당 문제와 디렉토리 관리 알고리즘을 사용해야 한다.
 

파일 디렉토리 구조를 만드는데 사용될 수 있는 자료구조들
Directory Implementation:Linear List

data block을 가리키고 있는 파일이름 리스트
 
삭제된 디렉토리 엔트리를 재사용하기 위한 방법
unused라고 표시를 해놓고, 그것을 free directory entries의 리스트에 붙이고, directory list의 마지막 entry를 unused라고 표시된 곳에 복사한다. 그러면 디렉토리 리스트 길이도 짧아지고, 삭제하는 시간도 줄어들 것이다.

Directory Implementation: Hash Table

hash를 이용한 linear list
찾기, 삽입, 삭제가 빨라진다.
collision문제, chained-overflow hash table로 해결할 수 있다.

Allocation Methods

file에 disk block을 어떻게 할당할 것인가.
공간효율성, 빠른 접근

Contiguous Allocation

각 파일은 디스크에 연속적인 block으로 할당되는 방식
단순하고 seek time이 빨라지는 장점이 있으나
새로운 파일을 위한 공간을 찾기가 어렵다거나, 원래 있던 파일이 증가될 수 없다는 단점이 있다.

Linked Allocation

각 파일은 disk blocks의 linked list이다.
directory는 list의 처음과 끝을 가리키는 포인터를 가지고 있다.
장점
external fragmentation이 없다.
파일 크기가 가변적이어도 상관없다.
단점
순차 접근만 가능하다. 찾을때 파일의 처음부터 시작해야 한다.
block마다 pointer를 위한 공간이 필요하다.
pointer가 깨졌을 경우 문제

File Allocation Table(FAT)

Linked allocation의 개선
FAT의 경우에
각 디스크파티션의 시작 섹션에 table을 둔다.
이 테이블은 파티션 내 모든 disk block 수만큼의 엔트리가 있고 각 엔트리는 파일의 다음 block number값을 갖는다.
디렉토리 entry는 파일의 첫번째 블락 넘버를 가지고 있다.
Random access time이 개선된다. FAT에서 일단 먼저 찾아보면 되니까.

Indexed allocation

모든 포인터를 index block에다가 넣기
각각의 파일들은 자신의 index block을 가지고 있다.
디렉토리는 index block의 위치를 가지고 있다.
포인터가 한두개밖에 없더라도 하나의 block이 할당되어야 하므로 공간낭비문제가 있다.
external fragmentation 없이 direct access를 지원할 수 있다. block이 더 필요하면 free-space manager에게 요청하면 block하나 받아서 index block에 번호 추가시키면 됨. 그리고 index block을 읽으면 어느 block에 순차적으로 탐색안하고 접근할 수 있음.

Index block이 얼마나 커야 하는가
index block이 너무 작으면, 큰 파일을 어떻게 다룰지에 대한 문제가 있다.
Linked scheme - index blocks의 list
Multilevel index - 첫번째 인덱스 블락은 두번째레벨 인덱스 블락을 가리킨다.
Combined scheme(UFS) - inode(FCB)가 가진 15개 index blocks 중에서 12개는 파일의 데이터와 직접 연결하는 index이고(direct blocks), 1개는 하나의 index block을 가리키는 index(single indirect block), 1개는 2개의 index block을 가리키는 index block의 index(double indirect), 나머지 하나는 triple indirect.

Disk Drive, Partitions, and a File System

디스크는 파티션으로 나누어 지고
파티션에는 boot block, super block, inode list, data block으로 이루어져 있다.
boot block은 OS를 로드하고 초기화하는데 필요한 코드들이 들어있고
super block에는 파일 시스템의 메타정보들이 들어있다.
Inode list에는 inode들이 들어있다. 유닉스에서는 directory를 하나의 파일처럼 간주한다.

Free-Space Management

시스템은 free space list를 유지한다.
free disk blocks들이 list에 있다.
리스트 구현 : bit vector, linked list, grouping, counting
bit vector
block i가 free면 0, 아니면 1
디스크 용량이 큰 경우 전체 벡터를 메인메모리에 다 못담는다.
연속적인 공간을 얻기는 쉽다.

linked list
첫번째 블락의 포인터만 가지고 있으면 된다.
연속적인 공간을 얻기 어렵다.
공간이 필요하면 리스트의 첫번째 블락부터 주면 된다.
리스트 탐색이 자주 필요하지 않아서 탐색문제는 크게 문제되지 않는다.

grouping
첫번째 free block에 n개의 free block 주소를 저장한다.
n-1개는 정말 비어있는 block이고 마지막 1개는 또 다른 n개의 free block 주소가 저장되어 있다.
free block을 한번에 많이 찾을 수 있다.

counting
연속적인 할당을 이용한다.
첫번째 free block의 주소와 그 블락 뒤에 몇 개의 free block이 있는지에 대한 정보를 가지고 있는다.

Page Cache and Buffer Cache
 

또다른 성능 향상 방법.
디스크 컨트롤러 내에 local memory가 있는데 cache라고 한다. 한 트랙을 담을 정도의 크기를 가지고 있어서
cpu가 cache에서 읽으면 빠르다.
어떤 시스템은 Buffer cache 이용하고 어떤 시스템은 Page cache이용.
buffer cache는 다시 쓰일 것 같은 block유지.
page cache는 virtual memory 기법이 사용된 것으로 파일 데이터를 block단위가 아니라 page단위로 사용하는 것.

I/O without a unified buffer cache

memory mapped file을 읽을 때, 
virtual memory가 buffer cache랑 데이터를 주고 받을 수 없어서 buffer cache의 내용을 page cache로 복사해야 함.(double caching)

대신에 unified buffer cache를 사용하면 memory mapping과 read, write 시스템콜이 같은 페이지 캐쉬를 사용한다.

Recovery

파일과 디렉토리가 main memory와 disk에 있을 때 시스템이 맛이 가도 data 손실이나 불일치를 막아야 한다.

Log-Structured file system
파일을 디스크에 쓰는 과정이 새로운 블락이 할당되고 inode에 새로운 블락정보와 파일정보를 업데이트 하고, block들이 디스크에 쓰여지는 등 과정이 atomic하지 않기 때문에 중간에 시스템에서 interrupt가 나는 경우 일관성 문제와 정보 손실 문제 등 발생. meta data가 손상될 수도 있고.
Journaling(로그기반 처리)은 database의 transaction 같은 것. 변경 과정을 파일에다가 기록.
파일의 일관성을 유지하기 위해 transaction이 제대로 잘 수행되거나 아님 아예 수행이 안되거나 둘 중하나를 보장한다.
메타데이터에만 적용될 수도 있고 파일에 적용될 수도 있다.

NFS(Network file system)
원격의 다른 컴퓨터 파일 시스템을 쓰는 기술.
패킷에 담아 read, write 같은 명령을 전달.