운영체제 30. 파일 시스템 구현

30. 파일 시스템 구현

30.1 생각하는 방법

• 파일 시스템에 대해 학습할 때, 두 가지 측면에서 접근할 것을 권장한다.
• 첫 번째는 파일 시스템의 자료구조이다. 즉 파일 시스템이 자신의 데이터와 메타 데이터를 관리하기 위해 어떤 자료구조가 있어야 하는지 여러 파일 시스템은 배열과 같은 간단한 자료구조로 표현하지만 SGI의 XFS와 같은 파일 시스템은 좀 더 복잡한 트리 기반 자료 구조를 사용한다.
• 두 번째 측면은 접근 방법(access method)이다. 프로세스 호출하는 명령들은 자료구조와 어떤 관리이 있는가? 특정 시스템 콜을 실행할 때 어떤 자료구조들이 읽히는가
• 파일 시스템의 자료구조와 접근방법을 이해하였다면, 실제 동작 방식에 대한 개념 모델을 제대로 정립하는 것이다.

30.2 전체 구성

• vsfs 파일 시스템의 자료구조에 대한 전체적인 구성.
• 디스크를 4KB의 블럭들로 나눈다.
• 파일 시스템의 대부분의 공간은 사용자 데이터로 이루어져 있다. 사용자 데이터가 있는 디스크 공간을 데이터 영역(data region)이라고 한다.
• 파일 시스템은 각 파일에 대한 정보를 관리한다. 그 정보가 메타데이터(metadata)의 핵심이다. 파일을 구성하는 데이터 블록들과 그 파일의 크기, 소유자, 접근권한, 접근과 변경시간 등과 같은 정보들이 이에 해당한다. 파일 시스템은 이 정보를 보통 아이노드(inode)라고 부르는 자료구조에 저장한다.
• 아이노드들의 저장을 위해 디스크 공간이 필요하다. 이 영역을 아이노드 테이블이라 한다. 아이노드 테이블에는 아이노드들이 배열 형태로 저장된다.
• 아이노드는 일반적으로 128에서 256 bytes 정도로 크지않다. 같은 파일 시스템이라도 더 큰 디스크 파티션에 생성한다면 아이노드 테이블을 더 크게 만들 수 있기 때문에 생성 가능한 최대 파일 개수를 증가 시킬 수 있다.
• 필요한 정보 중 하나는 아이노드나 데이터 블록의 사용여부에 대한 것이다. 각 블록이 현재 사용중인지 아닌지를 표현할 할당구조(allocation structure)가 필요하다. 블록이 사용중인지 아닌지를 나타내는 정보를 어느 파일 시스템이든 꼭 있어야 한다.
• 블럭이 사용중인지 아닌지를 표현하기 위해 프리리스트나 비트맵을 사용한다. 비트맵은 데이터 영역에 있는 블럭들의 사용여부를 표현하기 위해 데이터 비트맵을 아이노드 테이블에 있는 아이노드들이 사용중인지 나타내기 위해서 아이노드 비트맵을 사용한다. 비트맵은 비트들의 배열이다. 각 비트는 해당 블록이나 객체가 사용중인지 아닌지를 나타낸다.
• 슈퍼블록은 파일 시스템 전체에 대한 정보를 담고있다. 파일 시스템이 깨진다는 것은 슈퍼블록이 저장된 디스크 블록이 훼손되는 것이다. 일반적으로 대부분 파일 시스템은 슈퍼블록을 몇 개 복사해둔다.
• 파일 시스템을 마운트 할 때, 운영체제는 우선 슈퍼블록을 읽어들여서 파일 시스템의 여러가지 요소들을 초기화하고, 그 후에 각 파티션을 파일 시스템 트리에 붙이는 작업을 진행한다. 이렇게 함으로 디스크 볼륨에 있는 파일들을 접근할 때 해당 파일을 읽거나 쓰는데 필요한 자료구조의 위치를 파악한다.

30.3 파일구성 : 아이노드

• 파일 시스템의 디스크 자료구조 중 가장 중요한 것은 아이노드이다. 이 노드들은 원래는 배열로 되어 있었는데, 각 배열은 특정 아이노드를 접근하기 위해 탐색된다.
• 각 아이노드는 숫자로 표현된다. 이것을 파일의 저수준 이름이라고도 부른다. vsfs에서는 아이넘버를 사용해서 해당 아이노드가 디스크 상에 어디 있는지를 계산할 수 있다.
• 아이노드에는 파일에 대한 정보가 다 들어있다. 파일의 종류, 크기, 할당된 블록 수, 보호 정보, 시간 정보와 더불어 데이터 블록이 디스크 어디에 존재하는지와 같은 정보들이 담겨있다. 이와 같은 파일에 대한 정보를 메타데이터라고 한다. 사용자 데이터가 아닌 기타 정보를 통틀어서 흔히 메타데이터라 부른다.
• 아이노드 설계시 가장 중요한 결정 중 하나는 데이터 블록의 위치를 표현하는 방법이다. 가장 간단한 방법은 아이노드내에 여러개의 직접포인터(direct pointer, 디스크 주소)를 두는 것이다. 각 포인터는 파일의 디스크 블록 하나를 가리킨다. 파일 크기는 (포인터의 개수) * (블록크기)로 제한된다.

멀티 레벨 인덱스

• 큰 파일을 지원하기 위해 파일 시스템 개발자들은 간접 포인터(indirect pointer)라는 특수한 포인터를 사용한다. 간접포인터는 데이터 블록을 가리키지 않는다. 간접 포인터가 가리키는 블록에는 데이터 블록을 가리키는 포인터가 저장된다. 직접 포인터와 간접 포인터를 결합해서 사용할 수 있다. 아이노드에는 정해진 수의 직접 포인터와 하나의 간접 포인터가 있다. 큰 파일에 대해서 간접 블럭이 할당이 되고, 아이노드의 간접 포인터를 가리킨다.
• 더 큰 파일을 저장하고 싶은 경우 이중 간접 포인터를 추가한다. 이중 간접 포인터가 가리키는 블록에는 간접 포인터들이 저장되어있다. 더 더 큰 파일을 표현해야 한다면 삼중 간접 포인터를 사용하면 된다.
• 디스크 블록들은 일종의 트리 형태로 구성되어 하나의 파일을 이룬다. 이러한 구성방식을 멀티레벨 인덱스 기법이라 한다.
• 많은 시스템들이 멀티 레벨 인덱스를 사용한다. SGI의 XFS와 Linux의 ext4같은 파일 시스템들은 간단한 포인터를 사용하는 대신 익스텐트(extent)를 사용한다.

30.4 디렉터리 구조

• 디렉터리는 쌍의 배열로 구성되어 있다. 디렉터리의 데이터 블럭에는 문자열과 숫자가 쌍으로 존재하며 문자열 길이에 대한 정보도 있다.
• 각 디렉터리는 . ‘dot’ 과 .. ‘dot-dot’ 이라는 두 개의 추가 항목이 있으며 dot 디렉터리는 현재 디렉터리를 가리키면 dot-dot은 부모 디렉터리를 가리킨다.
• 파일이 삭제되면 디렉터리 중간에 빈 공간이 발생한다. 영역이 비었다는 것을 표시할 방법이 필요하다. 항목의 길이를 명시하는 이유 중에 하나가 중간에 빈 공간이 생기기 때문이다. 새로운 디렉터리 항목을 생성할 때, 기존 항목이 삭제되어 생긴 빈 공간에 새로이 생성된 항목을 위치시킬 수도 있기 때문이다.
• 대부분 파일 시스템에서 디렉터리는 특수한 종류의 파일로 간주한다. 디렉터리는 자신의 아이노드를 가지며, 이 아이노드는 아이노드 테이블에 존재한다. 디렉터리는 자신의 데이터 블럭을 갖고 있으며, 이들 블럭의 위치는 일반 파일과 마찬가지로 아이노드에 명시되어 있다. 이 데이터 블럭들은 데이터 블럭 영역에 존재한다.

30.5 빈 공간의 관리

• 파일 시스템은 아이노드와 데이터 블록 사용여부를 관리해야 한다. 그래야 새로운 파일이나 디렉터리를 할당할 공간을 찾을 수 있다. 빈 공간 관리(free space management)는 모든 파일 시스템에서 중요하다. vsfs는 두 개의 비트맵을 사용한다.
• 파일 생성시 아이노드를 할당해야 한다. 파일 시스템은 아이노드 비트맵을 탐색하여 비어있는 아이노드를 찾아 파일에 할당한다. 파일 시스템은 해당 아이노드를 사용 중으로 표기하고 디스크 비트맵도 적절히 갱신한다. 이와 유사한 동작이 데이터 블럭을 할당 할 때에도 일어난다.
• ext2, ext3 와 같은 Linux 파일 시스템의 경우 데이터 블럭이 할당시 가능하면 여러 개의 블럭들이 연속적으로 비어 있는 공간을 찾아서 할당한다. 그 후에 할당 요청이 발생하면 기존에 할당된 공간에 이어서 블럭을 할당하기 위해서이다. 연속적으로 여러개의 블럭들이 비어있는 공간을 할당함으로써 해당 파일에 대한 입출력 성능을 개선한다. 이러한 선할당(pre-allocation) 정책은 데이터 블럭 할당시 자주 사용된다.

30.6 실행흐름 : 읽기와 쓰기

디스크에서 파일 읽기

• open이 호출되면 파일 시스템은 디스크 상에서 아이노드를 읽어 들어야 한다. 파일 시스템은 파일에 대한 전체 경로명을 갖고 있다. 파일 시스템은 경로명을 따라가서(traverse) 원하는 아이노드를 찾는다.
• 경로명을 따라가는 것은 항상 파일 시스템의 루트에서 시작하며, 루트 디렉터리(root directory)는 / 로 표기된다. 파일 시스템이 디스크에서 가장 먼저 읽을 것은 루트 디렉터리의 아이노드이다. 아이노드를 찾기 위해서는 아이넘버를 알아야한다. 일반적으로 어떤 파일이나 디렉터리의 아이넘버는 부모 디렉터리에서 찾을 수 있다. 루트 아이넘버의 경우 파일 시스템이 마운트 될때 이 값이 결정되는데 대부분의 unix 파일 시스템에서는 루트 디렉터리의 아이넘버는 2번이다.
• 파일 시스템은 읽어들인 아이노드에서 데이터 블럭의 포인터를 추출한다. 포인터가 가리키는 블럭에는 루트 디렉터리의 내용이 들어있다.
• 경로 명을 따라가 아이노드를 찾는다. 마지막 단계의 open은 파일에 대한 아이노드를 메모리로 읽어들인다. 파일 시스템은 최종적으로 해당 파일에 대한 접근 권한을 확인하고 프로세스의 파일 디스크립터를 할당받아 사용자에게 리턴한다.
• open()이후 read() 시스템 콜을 통해 파일을 읽는다. 첫 번째 읽기는 아이노드를 통해 해당 블럭의 디스크상의 위치를 파악한 후 해당 블럭을 읽는다. 파일을 읽은 후 파일을 마지막으로 읽은 시간을 아이노드에 기록한다. 파일 오프셋은 파일을 읽거나 쓸 때, 해당 작업을 수행할 위치를 저장하는 변수이다. read()는 해당 파일 디스크립터에 대한 오프셋을 갱신한다. 다음에 읽기 작업을 수행할 때, 이전에 읽었던 다음 위치부터 읽도록 할 것이다.
• I/O 발생 횟수는 경로의 길이에 비례한다. 경로가 하나 추가될 때마다 아이노드와 해당하는 데이터를 읽어야 한다. 디렉터리의 수가 많아지면 상황은 더 악화될 것이다.

디스크에 파일 쓰기

• 디스크 쓰기도 비슷한 과정을 밟는다. 파일을 열고, 그후에 write()를 호출하여 새로운 내용으로 파일을 갱신한다. 최종적으로 파일을 닫는다.
• 읽기와는 다르게 파일 쓰기는 블럭할당을 필요로 할 수 있다. 새로운 파일에 쓸 때에는 각 write()는 데이터를 디스크에 기록해야 할 뿐만 아니라 파일에 어느 블럭을 할당할지를 결정해야 하며 그에 따라 디스크에 다른 자료구조들을 갱신해야 한다. 그러므로 파일에 대한 쓰기요청은 논리적으로 다섯번의 I/O를 생성한다. 하나는 데이터 비트맵을 읽기 위해서, 또 하나는 비트맵을 쓰기 위해서, 그 다음의 두 개는 아이노드를 읽고 쓰기 위해서, 그리고 마지막으로 실제 블럭을 기록하기 위해서 I/O가 발생한다.

30.7 캐싱과 버퍼링

• 파일을 읽고 쓰는것은 많은 I/O를 발생시킨다. 성능 개선을 위해 대부분의 파일 시스템들은 자주 사용되는 블럭들을 메모리에 캐싱한다.
• 초기의 파일 시스템에서는 자주 사용되는 블럭들을 저장하기 위해서 캐시를 도입하였다. 가상 메모리에서 논의했듯이 LRU와 기타 다른 캐시 교체 정책들이 캐시에 어떤 블럭을 남길지 결정해야 한다. 이 고정크기의 캐시는 일반적으로 부팅시에 할당이 되며 전체 메모리의 약 10%를 차지한다.
• 하지만 이런 메모리의 정적 기법은 낭비가 많다. 고정크기 방식을 사용하면 파일 캐시에서 사용되지 않는 페이지들은 다른 목적을 갖도록 용도 변경을 할 수 없으므로 낭비가 된다.
• 현대 시스템은 동적 파티션 방식을 사용한다. 현대의 많은 운영체제는 가상 메모리 페이지들과 파일 시스템 페이지를 통합하여 일원화된 페이지 캐시(unified page cache)를 만들었다. 이렇게 하면 어느 한 시점에 어느 부분에 더 많은 메모리가 필요하냐에 따라 파일 시스템과 가상 메모리에 좀 더 융통성 있게 메모리를 할당할 수 있다.
• 캐시가 충분히 크면 대부분의 읽기 I/O를 제거할 수 있다. 쓰기는 영속성을 유지하기 위해서 해당 블럭들을 디스크로 내려야 한다, 쓰기의 경우에는 캐시가 읽기에서와 같은 필터 역할을 할 수가 없다. 캐시는 쓰기 시점을 연기하는 역할을 한다. 이를 쓰기 버퍼링(write buffering)이라 한다. 쓰기 버퍼링을 통해 얻을 수 있는 몇 가지 성능 이득이 있다. 하나는 쓰기 요청을 지연시켜 다수의 쓰기 작업들을 적은 수의 I/O로 일괄처리(batch)할 수도 있다. 두 번째는 여러 개의 쓰기 요청들을 모아둠으로써 다수의 I/O들을 스케줄하여 성능을 개선 할 수 있다. 마지막으로 지연시키는 것을 통해 쓰기 자체를 피할 수도 있다.
• 쓰기 버퍼링으로 인한 예기치 않은 데이터 유실을 피하기 위해 fsync()를 사용한다. 이를 호출하면 갱신된 내용이 디스크에 강제적으로 기록한다. 캐시를 사용하지 않도록 direct I/O 인터페이스를 사용하거나 디스크(raw disk) 인터페이스를 사용하여 파일 시스템을 건너뛰고 직접 디스크에 기록하는 경우도 있다.