파일 시스템 구현

vsfs(very simple file system) 파일 시스템은 UNIX 파일 시스템을 단순화한 것으로 디스크 자료구조(on-disk structure)와 접근 방법 그리고 다양한 파일 시스템들의 정책을 소개하기 위해 제작되었다.

파일 시스템은 순수한 소프트웨어라는 점에서 CPU 가상화나 메모리 가상화와 다르다.

CPU 가상화나 메모리 가상화에서는 하드웨어가 필요하다.

어떻게 간단한 파일 시스템을 만들 것인가

43.1 생각하는 방법

파일 시스템에 대해 학습할 때 두 가지 측면에서 접근한다.

첫 번째는 파일 시스템의 자료 구조이다.

파일 시스템이 자신의 데이터와 메타데이터를 관리하기 위해 디스크 상에 어떤 종류의 자료 구조가 있어야 하는지 알아야 한다.

파일 시스템의 두 번째 측면은 접근 방법(access method)이다.

프로세스가 호출하는 open(), read(), write() 등의 명령들은 파일 시스템의 자료 구조와 어떤 관련이 있는가?

특정 시스템 콜을 실행할 때에 어떤 자료 구조들이 읽히는가?

어떤 것들이 쓰이고 모든 과정이 얼마나 효율적으로 동작하는가?

43.2 전체 구성

vsfs 파일 시스템의 자료 구조에 대해 디스크 상의 전체적인 구성을 개발한다.

가장 먼저 해야 할 것은 디스크를 블록(block)들로 나누는 것이다.

간단한 파일 시스템은 단일 블록 크기만 사용하고 일반적으로 사용되는 크기는 4KB이다.

파일 시스템의 디스크 파티션 구조는 4KB 블록들로 나열되어 있다.

N개의 4KB 블록의 크기를 갖는 파티션에서 블록은 0부터 N-1까지의 주소를 갖고 있다.

파일 시스템을 생성하기 위해서 블록들에 어떤 것을 저장해야 하는가?

가장 먼저 사용자 데이터가 있다.

파일 시스템의 대부분의 공간은 사용자 데이터로 이루어져 있다.

사용자 데이터가 있는 디스크 공간을 데이터 영역(data region)이라고 한다.

64개의 디스크 블록 중 마지막 56개의 블록처럼 디스크의 일정 부분을 데이터 영역으로 확보하자.

파일 시스템은 각 파일에 대한 정보(메타데이터)를 관리한다.

파일을 구성하는 데이터 블록(데이터 영역 내의)들과 그 파일의 크기, 소유자, 접근 권한, 접근과 변경 시간 등과 같은 정보를 아이노드(inode)라고 부르는 자료 구조에 저장한다.

아이노드들의 저장을 위해 디스크 공간이 필요하다.

전체 64개의 블록 중 5개의 블록이 아이노드를 저장하기 위해 할당된다.

아이노드는 일반적으로 128에서 256바이트 정도의 크기를 가진다.

아이노드 당 256 바이트를 가정하면 4KB 블록에는 16개의 아이노드를 저장할 수 있으며 파일 시스템에서는 총 80개의 아이노드를 저장할 수 있다.

64개의 블록으로 구성된 작은 파일 시스템 파티션에 최대 80개의 파일을 만들 수 있다는 것을 의미한다.

같은 파일 시스템이라도 더 큰 디스크 파티션에 생성한다면 아이노드 테이블을 더 크게 만들 수 있기 때문에 생성가능한 최대 파일 개수를 증가시킬 수 있다.

파일 시스템에는 데이터 블록(D)과 아이노드 볼륵(I)이 존재한다.

아이노드나 데이터 블록의 사용여부에 관한 정보가 필요하다.

각 블록이 사용 중인지 아닌지를 표현할 할당 구조(allocation structure)가 필요하다.

블록이 사용 중인지 아닌지를 나타내는 정보는 어느 파일 시스템이든 필요하고 표현하는 데에는 다양한 방법이 존재한다.

프리 리스트(free list)를 사용하여 사용 중이 아닌 블록들을 링크드 리스트 형태로 관리할 수 있다.

비트들의 배열인 비트맵(bitmap)을 사용하여 데이터 영역에 있는 블록들의 사용여부를 표현하기 위해서 데이터 비트맵(data bitmap)을, 아이노드 테이블에 있는 아이노드들이 사용 중인지를 나타내기 위해서 아이노드 비트맵(inode bitmap)을 사용한다.

각 비트는 블록이나 객체(각 아이노드)가 사용 중인지(1) 아닌지(0)를 나타낸다.

4KB 크기의 비트맵은 32K개의 객체에 대한 할당 정보를 관리할 수 있다.

한 블록은 파일 시스템 전체에 대한 정보를 담고 있는 슈퍼블록(superblock)을 위한 공간이다.

예를 들면 파일 시스템에 몇 개의 아이노드와 데이터 블록이 있는지, 아이노드 테이블은 어디에서 시작하는지(블록 3번) 같은 정보를 담고 있다.

파일 시스템을 식별할 수 있는 매직 넘버도 갖고 있을 것이다.

파일 시스템이 깨진다는 것은 슈퍼블록이 저장된 디스크 블록이 훼손되는 것이다.

파일 시스템을 마운트할 때, 운영체제는 우선 슈퍼블록을 읽어들여서 파일 시스템의 여러가지 요소들을 초기화하고, 그 후에 각 파티션을 파일 시스템 트리에 붙히는 작업을 진행한다.

디스크 볼륨에 있는 파일들을 접근할 때, 해당 파일을 읽거나 쓰는 데 필요한 자료 구조의 위치를 파악한다.

43.3 파일 구성: 아이노드

파일 시스템의 디스크 자료 구조 중 가장 중요한 것은 아이노드(inode)이다.

아이노드는 인덱스 노드(index node)를 의미하며, 이 노드들은 배열로 되어 있는데 각 배열은 특정 아이노드를 접근하기 위해 탐색된다.

아이노드는 파일 메타데이터를 저장하기 위한 자료 구조이며, 이 자료 구조는 파일 크기, 접근권한 그리고 파일 블록들의 위치 정보를 가지고 있다.

아이노드 테이블의 크기가 20KB이고 (4KB 블록 5개) 80개의 아이노드로 이루여져 있다.

아이노드 영역은 12KB 위치부터 시작하고(슈퍼블록은 0KB 위치에서 시작, 아이노드 비트맵의 주소는 4KB에서부터), 데이터 비트맵은 8KB에서부터 시작한다.)

32번 아이노드를 읽기 위해서는 파일 시스템은 아이노드 영역에서의 오프셋을 계산한다.

그 후 아이노드 테이블의 시작 위치를 더하면, 원하는 아이노드 블록의 정확한 바이트 주소를 구할 수 있다(20KB).

디스크는 바이트 단위로는 접근이 불가능하며 대신에 대체적으로 512바이트 크기를 갖는 섹터(sector)로 이루어졌다.

32번 아이노드가 존재하는 블록을 가져오기 위해서는 파일 시스템은 섹터 주소 (20 * 1024 / 512) 또는 40에 대한 읽기 요청을 하여 해당 아이노드 블록을 가져온다.

아이노드 블록의 섹터 주소 iaddr은 계산될 수 있다.

아이노드에는 파일에 대한 정보가 들어 있다. 파일의 종류 크기, 할당된 블록 수, 보호 정보, 시간 정보와 더불어 데이터 블록이 디스크 어디에 존재하는지와 같은 정보들이 포함된다.

아이노드를 설계 시 가장 중요한 결정 중 하나는 데이터 블록의 위치를 표현하는 방법이다.

간단한 방법은 아이노드 내에 여러 개의 직접 포인터(direct pointer, 디스크 주소)를 두는 것이다.

각 포인터는 파일의 디스크 블록 하나를 가리킨다.

이러한 방법은 파일 크기의 크기가 (포인터의 개수) * (블록 크기)로 제한된다.

멀티 레벨 인덱스

큰 파일을 지원하기 위해서 파일 시스템 아이노드 내에 다른 자료 구조를 추가했다.

일반적으로 사용되는 방법 중 하나는 간접 포인터(indirect pointer)라는 특수한 포인터를 사용하는 것이다.

간접 포인터는 데이터 블록을 가리키지 않는다.

간접 포인터가 가리키는 블록에는 데이터 블록을 가리키는 포인터들이 저장된다.

직접 포인터와 간접 포인터를 결합해서 사용할 수 있다.

아이노드에는 정해진 수의 직접 포인터, 그리고 하나의 간접 포인터가 있다.

큰 파일에 대해서는 간접 블록이 할당되고(디스크의 데이터 블록 영역에서), 아이노드의 간접 포인터는 이 간접 블록을 가리킨다.

블록이 4KB이고 디스크 주소가 4바이트라고 하면 1024개의 포인터들을 추가할 수 있게 되어 최대 파일의 크기는 (12 + 1024) * 4K 또는 4144KB가 된다.

더 큰 파일을 저장하고 싶을 경우 아이노드에 이중 간접 포인터(double indirect pointer)를 추가한다.

이중 간접 포인터가 가리키는 블록에는 간접 포인터들이 저장되어 있다.

각 간접 블록은 데이터 블록을 가리키는 포인터들을 가리키고 있다.

이중 간접 포인터가 가리키는 블록에는 간접 포인터들이 저장되어 있다.

각 간접 블록은 데이터 블록을 가리키는 포인터들을 가리키고 있다.

이중 간접 블록을 사용하면 파일은 4KB 1024 1024, 약 백만개의 4KB 블록을 가질 수 있다.

즉, 4GB가 넘는 크기의 파일을 지원할 수 있게 된다.

종합하면 디스크 블록들은 일종의 트리 형태로 구성되어 하나의 파일을 이룬다.

이러한 구성방식을 멀티 레벨 인덱스 기법이라 한다.

열두 개의 직접 포인터와 하나의 간접 블록과 이중 간접 블록을 사용하는 경우를 생각하면 블록 크기가 4KB라고 하고 각 포인터의 크기가 4바이트라고 한다.

43.4 디렉터리 구조

디렉터리에는 (항목의 이름, 아이노드 번호) 쌍의 배열로 구성되어 있다.

디렉터리의 데이터 블록에는 문자열과 숫자가 쌍으로 존재하며 문자열 길이에 대한 정보도 있다.

예를 들어 dir라는 디렉터리(아이노드 번호 5)에는 foo, bar와 foobar라는 3개의 파일이 있고 각각의 아이노드의 번호는 12, 13 그리고 24라고 하자.

각 항목은 아이노드 번호와 레코드 길이(이름에 사용된 총 바이트와 남은 공간의 합), 문자열 길이(실제 이름의 길이), 그리고 마지막으로 항목의 이름을 갖고 있다.

파일이 삭제되면(unlink() 호출) 디렉터리 중간에 빈 공간이 발생한다.

영역이 비었다는 것을 표시할 방법이 필요하다.

항목의 길이를 명시하는 이유 중에 하나가 중간에 빈 공간이 생기기 때문이다.

새로운 디렉토리가 생성할 때, 기존 항목이 삭제되어 생긴 빈 공간에 새로이 생성된 항목을 위치시킬 수도 있기 때문이다.

디렉터리는 정확히 어디에 저장될까?

대부분 파일 시스템에서 디렉터리는 특수한 종류의 파일로 간주한다.

디렉터리는 자신의 아이노드를 가지며, 이 아이노드는 아이노드 테이블에 존재한다.

링크 기반의 파일 구조

아이노드를 설계하는 데 사용되는 또 다른 방법은 연결 리스트를 사용하는 것이다.

아이노드 안에 다수의 포인터를 두지 않고 파일의 첫 번째 블록을 가리키는 포인터만 둔다.

큰 파일의 경우, 파일의 마지막 블록을 가리키는 포인터를 추가한다.

링크 기반의 파일 블록 구성은 특정 워크로드에 대해서 성능이 좋지 않을 수 있다.

예를 들면 가장 마지막 블록을 읽어야 하는 경우나 임의의 위치를 읽어야 하는 경우이다.

링크드 리스트 기반 구성의 성능을 개선하기 위해 데이터 블록 내에 다음 번 블록의 위치를 저장하지 않고, 링크드 리스트의 포인터 정보들만 테이블로 관리하여 테이블을 메모리에 상주시킬 수 있다.

다음 블록의 주소를 각 블록에 저장할 경우, 10번째 블록을 읽기 위해서는, 첫 블록부터 열 번째 블록까지를 차례로 읽어야 한다.

각 블록의 위치를 테이블에 모아둘 경우, 이 테이블이 메모리에 존재하면 각 블록을 따로 읽는 연산은 발생하지 않는다.

테이블 항목은 데이터 블록 D의 주소로 인덱스된다.

각 항목의 내용은 D의 다음 블록을 가리키는 포인터, 즉 파일의 D 다음에 오는 블록의 주소를 저장한다.

다음 포인터를 저장하는 테이블을 사용하면 연결식 할당 방법에서도 임의의 파일 접근을 효율적으로 할 수 있게 된다.

먼저 메모리 내의 테이블을 스캔하여 원하는 블록을 찾은 후 디스크 내의 해당 위치를 직접 접근하면 된다.

이러한 방식이 file allocation table 또는 FAT 파일 시스템의 기본 구조이다.

빈 공간의 관리

빈 공간을 관리하는 여러 가지 방법 중 하나가 비트맵이다.

초기 파일 시스템들은 프리 리스트(free list)를 사용하여 슈퍼블록 안의 한 포인터가 첫 번째 프리 블록을 가리키도록 하였다.

그리고 그 블록은 다른 프리 블록을 가리키는 포인터를 갖는 식으로 시스템 내의 프리 블록들의 리스트를 만들었다.

43.5 빈 공간의 관리

파일 시스템은 아이노드와 데이터 블록 사용 여부를 관리해야 한다.

새로운 파일이나 디렉터리를 할당할 공간을 찾을 수 있다.

빈 공간 관리(free space management)는 모든 파일 시스템에서 중요하다.

vsfs에서는 두 개의 비트맵을 사용한다.

파일 생성 시 아이노드를 할당해야 한다.

파일 시스템은 아이노드 비트맵을 탐색하여 비어 있는 아이노드를 찾아 파일에 할당한다.

파일 시스템은 해당 아이노드를 사용 중으로 표기하고 디스크 비트맵도 갱신한다.

43.8 요약

파일 시스템에서는 각 파일에 어떤 정보(메타데이터)가 필요한지 아이노드라고 부르는 자료 구조에 저장한다.

디렉터리는 특수 파일로서 파일 이름과 아이노드 번호 간의 연결정보를 저장한다.

또한 파일 시스템은 아이노드나 데이터 블록의 할당과 해제 여부를 나타내는 비트맵과 같은 정보를 갖고 있다.