Software blog

NT 파일 시스템을 위한 자료구조 특성.

Characteristics of Data Structures for NT File System

NT 파일 시스템에서 파일 스트림을 관리하는 파일 컨트롤 블록(File Control Block, FCB)를 적절히 생성하고 이를 관리 하기 위해서는 파일의 닫기(Close)와 클린업(Cleanup)에 대한 차이를 이해하는 것이 필요하다. 이에 따라서 FCB를 메모리에서 해제 할 수 있기 때문에 FCB는 이에 대한 정보를 자신의 자료구조 필드(Field)에 저장해두는데 닫기와 클린업 동작자체가 매우 유사하기 때문에 이를 관리하는 오브젝트 매니저(Object Manager)와의 묵시적 통신 수단을 이해 해야 한다. 더불어 파일 시스템 구현에서 필요한 부가 기능과 그에 따른 자료구조의 특성들을 이해해보자.

정명수 |

필자는 지난 3년간 삼성전자에서 플래시 메모리와 관련된 연구와 임베디드 소프트웨어, 커널 드라이버 등을 개발 했었다. 현재는 조지아 공대(Georgia Institute of Technology) 컴퓨팅 칼리지에 재학 중이다. 글쓰기를 매우 좋아하며 학부시절에는 객체 지향 패러다임을 통하여 해석하는 프로그래밍 언어론에 관심이 있었으나 실무과정을 거치면서 컴퓨터 아키텍처로 관심사가 옮겨졌다. 최근에 관심 있는 분야는 운영체제, 파일시스템, 실시간 스케줄링 등이다.

저번 칼럼에서 우리는 이미 파일 컨트롤 블록을 정의하고 설계 하였다. 오늘 우리는 이 자료구조를 사용하면서 가장 많이 혼돈을 하게 되는 두 개의 카운터를 관리 하는 방법과 파일 컨트롤 블록의 할당 시점, 그리고 적절한 해제 시점이 언제인지를 구분하여 볼 것이다. 아울러 데이터 압축, 온-디스크(On-disk) 자료구조, 빠른 이름 찾기 캐시(Dynamic Name Lookup Cache)등의 기능을 정의하고 이에 대한 자료구조의 필요성을 조명해본다.

본 칼럼에서 간략하게 언급된 자료구조들은 이후 실제 구현에서 예를 보일 수 있도록 하겠다. 본 칼럼을 위해서 드라이버 개발에 익숙하지 않은 개발자라면 반드시 마이크로 소프트웨어 2월부터 언급 되었던 파일 시스템 구현의 기본 사항부터 다시 읽어보는 것이 바람직하다.

파일 컨트롤 블록(FCB) 구조체의 할당과 해제의 적절한 시점

디스크 비종속, 종속적 부분과 NT에 의해 요구되는 부분을 포함하여 바이트 스트림이 처음 열리고 해당 바이트 스트림에 대하여 시스템 메모리 상에 할당된 FCB가 존재 하지 않는 두 가지의 조건이 만족 될 때 파일 시스템 개발자는 FCB 구조체를 할당해야 한다. 예를 들어서 만약 imaso.log라는 파일이 시스템이 부팅 될 때 처음 참조 되었다면 해당 파일이 존재하는 논리적 볼륨을 관리하는 파일 시스템 드라이버는 IRP_MJ_CREATE에 의해서 호출자로부터 전달 되는 열기 요청을 받는데 이때 FCB 구조체를 할당할 수 있다.

만약 FCB를 생성 한 뒤에 다시 열기 요청을 받는다면 어떻게 처리 해야 할까? 해당 바이트 스트림에 대한 FCB 구조체가 시스템 메모리상에 존재 하는 한 그 뒤에 요청에는 FCB 구조체를 할당할 필요가 없다. (혼돈 하면 안 되는 것은 FCB가 전역에 하나만 존재하는 것이 아니라는 것이다. 말 그대로 각 바이트 스트림에 대하여 FCB가 하나씩 존재 한다고 보면 된다) FCB가 파일 시스템 드라이버에 의해서 시스템 메모리에 유지 되고 있는지 아닌지를 결정하는 것은 ReferenceCount필드이다. 이전 칼럼에서 언급 된 것처럼 FCB 구조체 설계는 파일 시스템 드라이버 개발자에 의해서 결정 되는 것이므로 실제 필드 이름은 각기 다를 수 있다. 우리 SFS예제에서는 _nRefCnt 가 ReferenceCount필드를 의미한다. 파일 시스템 드라이버가 FCB 구조체 생성을 취소하거나 실패 했을 경우, 이후에 발생하는 열기 요청에 대하여 처음 발생한 것이 아니더라도 다시 FCB를 생성 해주어야 한다.

파일 컨트롤 블록은 열려진 바이트 스트림의 정보를 관리하는 유일한 자료구조 이므로 이를 참조하는 NT 컴포넌트가 하나라도 있다면 파일 시스템 개발자는 FCB를 시스템 메모리상에 유지 해주어야 한다. ReferenceCount 필드가 하는 주요 역할은 FCB를 참조하는 수를 나타내는 것으로 ReferenceCount 필드가 0가 되면 파일 시스템 개발자는 FCB를 시스템 메모리상에서 해제 시켜도 된다. 다시 말해 해당 바이트 스트림을 참조하는 컴포넌트가 시스템에 없고 이를 사용하는 사용자가 존재 하지 않기 때문에 관련된 정보를 관하는 FCB를 없애도 된다는 것이다.

ReferenceCount 필드와 OpenHandleCount의 역할 차이.

이전 칼럼을 읽은 독자라면 이를 이해하고 있겠지만, 참조 수(RerferenceCount) 관리, 연 핸들 수(OpenHandleCount) 관리를 각각 맞고 있는 이 두 필드는 SFS예제에서 각각 _nRefCnt, _nOpenHdelCnt라는 이름으로 관리 되고 있다. 아무래도 이 둘간의 용도 차이가 헷갈릴 여지가 있는데, 이 둘간의 차이를 이해하는 것은 NT 커널 하에서 파일 시스템을 개발하는 데 매우 중요하다. 참조 수와 연 핸들 수에 대한 이 두 필드는 파일 시스템 드라이버 FCB 구조체를 시스템 메모리로부터 안전하게 해제하기 위하여 사용되며, 모두 파일 시스템 드라이버 내부의 FCB 구조체에 의해서 관리된다. 이 두 필드는 파일 시스템 개발자에 의해서 설계되고 사용 되기 때문에 다른 커널모드나 사용자 모드의 컴포넌트들에게는 보이지 않는다.

참조 수를 관리 하는 ReferenceCount(_RefCnt) 필드는 이 필드를 포함하고 있는 FCB 구조체 인스턴스를 외부에서 참조하고 있는 수를 나타낸다. 이 ReferenceCount가 0이 되지 않는 한 파일 시스템 드라이버 개발자는 FCB를 사용하고 있는 외부의 특정 모듈이 존재한다는 사실을 알 수 있으며 해당 FCB 구조체의 인스턴스를 시스템 메모리로부터 해제 할 수 없다는 것을 알 수 있다. 좀 더 구체적으로 ReferenceCount 필드가 참조 수를 유지 하는 방법을 알아 보자면 IRP_MJ_CREATE를 요청을 받을 때(다시 말해 파일 열기와 생성) 마다 파일 시스템 드라이버 개발자는 1을 증가 시킨다. 반대로 이 ReferenceCount 필드의 값을 감소 시키는 시점은 파일 시스템 드라이버가 IRP_MJ_CLOSE를 받았을 때 이다.

파일 시스템이 ReferenceCount에 따라 이를 꼭 관리해주여야 하는 이유는 무엇일까? 이는 NT I/O 매니저 또한 파일 시스템 드라이버가 참조 수를 관리하고 생성 시에는 이를 증가, 닫을 시에는 이를 감소 할 것이라는 것을 가정하여 동작 한다는 것이다. 이러한 파일 시스템 드라이버의 참조 수 자체를 NT I/O 매니저가 고려할 뿐만 아니라 이 참조 수를 관리 하는 필드가 0가 되면 파일 시스템이 메모리를 해제 할 것이라는 것도 고려 하고 있다. 이러한 파일 시스템의 동작 방식은 I/O 매니저와 다른 윈도우 NT 컴포넌트들에게도 반영 되어 있다. 앞서 언급 한 것처럼 FCB 구조체와 그 인스턴스는 파일 시스템에서 다른 커널 컴포넌트로 외부공개 되어 있지 않지만, I/O 매니저와 다른 윈도우 컴포넌트들은 파일을 열고 닫을 때 사용되는 IRP 요청을 통해서 파일 시스템의 참조 수 관리 필드를 간접적으로 조절 할 수 있다. 따라서 NT 시스템 컴포넌트들은 파일 시스템 드라이버의 적절한 행동을 예상할 수 있고, 또한 파일 시스템 드라이버에 의해서 FCB가 시스템 메모리에 유지되는 시간을 조절 할 수 있다. 다시 말하면 파일 시스템 개발자는 이렇게 암묵적으로 이루어지는 메커니즘을 따라 참조 수를 관리하고 FCB를 유지 해주어야 한다.

<그림 1, CLEANUP과 CLOSE 입출력 요청 패킷(IRP)의 사용 예>

열려진 핸들 수(OpenHandleCount)는 FCB를 위해 외부의 사용자 핸들의 수를 관리 한다. 이 필드 또한 IRP_MJ_CREATE에 의해 증가된다. 그림 1에서 알 수 있듯이, OpenHandleCount(_OpenHdleCnt)는 참조 수를 관리하는 ReferenceCount와 달리 IRP_MJ_CLOSE에 따라 감소 하는 것이 아니라 IRP_MJ_CLEANUP에 의해서 감소 된다. IRP_MJ_CLEANUP 요청은 NT I/O 매니저에 의해서 관리 되는데 사용자 프로세스가 마지막 시점에 파일 핸들을 닫으면 이를 파일 시스템 드라이버에게 전달한다. 마지막 시점이라는 것은 모든 해당 파일을 열고 있던 사용자의 인스턴스들이 없어서 그 카운트가 0이 될 때를 의미한다.

파일 오브젝트 타입의 구조체는 윈도우 실행부(Executive)에서 정의된 자료구조로서 NT 오브젝트 매니저(Object Manger)에 의해서 관리 된다. 파일 오브젝트(File Object) 구조체에 대하여 오브젝트 매니저는 두 개의 카운터(Counter)를 유지한다. 이 카운터와 관련된 필드들의 이름들은 정확히 외부에 들어 나있지 않기 때문에 본 칼럼에서는 파일 시스템 개발의 대가인 Rajeev Nagar가 정의하는 가상의 이름으로 이를 대신 하겠다. 하나는 파일 오브젝트와 관련이 있는 하나 이상의 한들을 소유하고 있는 프로세스마다 이를 관리하는 프로세스 핸들 카운트(ProcessHandleCount)이고 또 다른 하나는 프로세스 핸들 카운트의 총 수를 더해 놓은 것과 같은 시스템 핸들 카운트(SystemHandleCount)라는 것이다. 이 두 가지 핸들 카운터 이외에 추가적으로 NT 오브젝트 매니저는 모든 오브젝트에 대하여 오브젝트 참조 카운트(ObjectReferenceCount)라는 것을 가지고 있다. 이 참조 카운트는 프로세스 핸들 카운트나 시스템 핸들 카운트 중 하나가 증가하면 같이 1씩 증가한다. 여기서 주의 해야 할 점은 프로세스 핸들 카운트나 시스템 핸들 카운트가 증가하지 않아도 간혹 오브젝트 참조 카운트가 증가하는 경우가 있다는 것이다. 예를 들면 커널 모드의 컴포넌트들의 오브젝트를 참조 할 때는 해당 오브젝트의 핸들을 요구하지 않고 직접 관여하기 때문에 이때는 시스템 핸들이나 프로세스핸들 카운트가 증가 하지 않는다.

특정 프로세스가 소유한 핸들을 ZwClose()함수나 NtClose()함수를 통해서 닫을 때에는 NT 오브젝트 매니저가 해당 오브젝트에 대한 파일 프로세스 핸들 카운트, 시스템 핸들 카운트 모두를 하나씩 감소 시킨다. 파일 오브젝트 경우에 닫는 절차 시에는 I/O 매니저에 의해서 제공되는 IopCloseFile()함수를 호출 하는데 오브젝트 매니저는 프로세스 핸들 카운트와 시스템 핸들 카운트 필드를 IopCloseFile()함수에게 전달하여 제공한다. IopCloseFile()함수는 외부에 존재하는 모든 사용자 핸들이 닫히는 경우 내부적으로 IRP_MJ_CLEANUP을 파일 시스템에게 요청하고 만약 시스템 핸들 카운트가 1이라면 외부 사용자 핸들에 의한 참조가 단 하나만 존재 하는 것이므로 NtClose()함수를 호출 한다.

IopCloseFile()함수가 한번 호출 되어 처리되고 나면 파일 시스템 드라이버 쪽에서도 해당 IRP_MJ_CLEANUP처리를 끝냈을 것이므로 오브젝트 매니저는 오브젝트 참조 카운트를 감소 시킨다. 만약 이 참조 카운트가 0이라면 오브젝트 매니저는 해당 오브젝트를 IoDeleteFile()함수를 사용하여 삭제한다. 비록 파일 시스템 드라이버가 사용자 핸들이 닫힐 때 마다 클린업(Cleanup)과 관련된 IRP를 받더라도 해당 파일 시스템 드라이버는 IRP_MJ_CLOSE를 받기 전에는 해당 FCB를 해제 할 수 없다는 것을 명심해야 한다.

UNIX 계열의 경우도 IRP_MJ_CLEANUP과 IRP_MJ_CLOSE와 같은 형태의 요청으로 파일에 관련된 참조들을 관리하는데 IRP_MJ_CLEANUP과 같은 것이 vnode close이며 마지막에 전달되는 IRP_MJ_CLOSE는 비 활동 요청(Inactivate) 동작으로 vnode 구조를 관리한다. 그렇다면 파일 시스템 드라이버가 관리하는 FCB 구조체의 두 필드, 참조 수와 열려진 핸들 수를 가지고 어떤 것들을 더 유추해 낼 수 있을까?

우선 얼마나 많은 사용자 핸들들이 FCB를 참조 하고 있을 지 생각 해보자. 다른 말로 하면 파일 시스템 드라이버 개발자는 IRP_MJ_CLEANUP를 아직 받지 않은 IRP_MJ_CRATE 요청의 총 수에 대한 아이디어를 가지고 있어야 이를 처리 할 수 있다. 이 숫자가 0이 아닌 이상 파일 시스템 드라이버는 적어도 하나의 스레드가 FCB에 의해서 지시된 파일 스트림의 유효한 핸들을 가지고 있다는 것을 알 수 있고 이를 위해서 FCB를 그때까지는 시스템 메모리상에 상주 시켜두어야 하는 것을 유추 할 수 있다. 이 사실은 ReferenceCount가 0이 아니면 삭제를 할 수 없는 요구사항과는 또 다른 것이다.

새로운 파일 오브젝트가 I/O 매니저에 의해 생성되는 동작에 따라 파일 시스템 드라이버의 FCB의 오브젝트 핸들 카운트가 증가한다고 하더라도 해당 파일 오브젝트에 대하여 시스템 전체의 핸들 수를 관리 할 필요는 없다. 사용자 파일 핸들이 하나의 프로세스 내에 여러 스레드상에 복사 되거나 파일 핸들이 부모 프로세스로부터 상속 될 때 마다, 그리고 특정 프로세스가 파일 오브젝트 포인터에 생성을 요청할 때마다 NT 오브젝트 매니저는 시스템 핸들 카운트를 증가 시킨다. 파일 시스템 드라이버는 이러한 파일 핸들에 대한 복사나 상속에 대하여 어떠한 정보도 받지 않기 때문에 열려진 핸들 수(OpenHandleCount)는 이러한 상속, 복사 등의 작업에 의해 증가 되지 않는다. 자신도 모르는 사이에 파일 오브젝트에 접근한 핸들들이 증가하는데 파일 시스템 드라이버 입장에서 그럼 열려진 핸들 수를 관리하는 것에 의미가 있는 것인가? 파일 시스템 드라이버는 이러한 상속, 복사 등의 작업에 의해서 통지 받는 정보가 전혀 없더라도 문제가 없다. 왜냐면 그림 2에서처럼 이렇게 파일 오브젝트 참조를 획득한 것들은 I/O 매니저가 해당 사용자 핸들들이 모두 닫히기 전에는 IRP_MJ_CLEANUP 요청을 보내지 않기 때문이다. 그래서 파일 시스템 드라이버는 항상 자신에게 생성, 또는 열기 요청을 받은 핸들에 대해서만 클린업 요청을 받으며 해당 클린업 요청에 대하여 열려진 핸들 카운트를 감소 시키기만 하면 된다.

<그림 2, 열려진 핸들 수 관리와 IRP_MJ_CLEANUP이 이슈(Issue)되는 시점>

FCB 구조체를 위한 외부 참조가 얼마나 있는지 확인하려면 어떻게 해야 할까? 참조 수를 관리하는 ReferenceCount는 FCB 인스턴스의 외부 참조의 전체 수를 파악하는데 도움을 준다. 재미있는 점은 열려진 핸들 수(OpenHandleCount)가 0이 된지 한참이 지나서 ReferenceCount가 0이 될 수도 있다는 것이다. 이 것은 모든 FCB에 대한 모든 사용자 핸들을 닫더라도 특정 커널 모드 컴포넌트들은 FCB를 시스템 메모리상에 상주시키길 원한다는 것으로 해석 할 수 있다. 일반적으로 이런 상황은 그림 3에서처럼 NT 캐시 매니저와 NT 가상 메모리 매니저가 함께 특정 파일데이터를 사용자가 닫았다고 하더라도 이를 메모리 안에 캐싱 시켜 놓고자 할 때 발생한다.

NT 가상 메모리 매니저와 캐시 매니저가 파일 데이터를 메모리에 상주 시켜 놓으려고 하는 것은 사용자가 이 파일에 대해서 다시 접근할 때 가능한 빨리 응답하도록 기회를 주어 성능을 향상하려는 것이다. 가상 메모리 매니저와 캐시 매니저는 FCB 인스턴스가 메모리상에 없으면 해당 파일을 접근 할 수 있는 방법이 없으므로 이를 고려하여 동작하는 것이다. 이러한 캐싱기법은 어떻게 보면 단순히 소모적인 행동으로 보여 질 수 있으나 실제 많은 사용자들이 한번 접근한 파일 스트림에 대해서 다시 접근하는 경향이 있으므로 (지역성, Locality of cache) 해당 FCB를 당분간 유지하고 이를 메모리에 두어 디스크로의 접근을 막고 성능을 향상시키는 기법은 실제로 꽤 효과가 있는 것으로 알려져 있다. 그렇다면 어떻게 가상 메모리 매니저나 다른 NT 커널의 컴포넌트들이 FCB를 메모리에 그대로 유지 시키게 할 수 있을 것인가? 이러한 암묵적 커뮤니케이션 기법들은 파일 시스템 개발자가 반드시 알아야 할 것들이다. 왜냐면 NT 커널 컴포넌트들이 이러한 방법으로 성능 향상을 꾀하고 있는데 파일 시스템 개발자가 자신의 파일 시스템 구조 자체에만 신경을 쓴다면 전체 시스템의 성능이 떨어질 수 밖에 없다. NT 커널의 컴포넌트들은 FCB를 메모리에 유지 시켜놓기 위해서 파일 시스템이 ReferenceCount와 OpenHandleCounte를 참조 하는 행동을 고려하여 파일 오브젝트를 강제적으로 참조한다. 이러한 작업을 통하여 NT 커널의 컴포넌트들은

사용자들이 해당 파일 오브젝트를 닫았다고 하더라도 오브젝트 매니저가 해당 오브젝트를 닫는 요청을 통지하지 못하도록 막는다. 그 결과, 파일 시스템 드라이버는 FCB의 참조 수를 감소 시키지 못하고 0이 되지 않아서 FCB 인스턴스를 메모리상에서 해제 하지 않게 된다.

<그림 3, 참조된 수와 열려진 핸들 수가 차이가 생기게 되는 경우>

다른 기타 주요 구조체

이제까지 언급된 파일 시스템의 자료 구조 이외에도 파일 시스템 개발자가 자신의 파일 시스템의 기능을 구현하기 위해서 보조, 또는 관리 해야 하는 몇몇 중요한 자료구조들이 존재한다. 파일 시스템 개발자가 부가적으로 관리 해야 하는 기능과 자료구조는 아래와 같이 크게 가지로 나뉘어 진다.

1. 바이트 단위의 락 메커니즘(Byte-range Locks)
2. 동적 이름 찾기 캐시(Dynamic Name Lookup Cache)
3. 파일 스트림과 디렉터리 할당량 관리(File Stream and Directory Quotas)
4. 기회적 락 메커니즘(Opportunistic Locks)
5. 디렉터리 변경 통지 기능(Directory Change Notification)
6. 데이터 압축과 암호화 기능(Data Compression, Encryption and Decryption)
7. 빠른 리커버리 로깅 지원(Recovery Logging)
8. 온-디스크 자료구조 지원(On-disk Data Sturucture)

이 단락부터는 그러한 자료구조들과 특성을 살펴 보기로 하자.

바이트 범위의 락 메커니즘

대부분의 파일 시스템들이 바이트 범위의 락 메커니즘을 제공하는데 이러한 락들은 필수적인 기능과 그렇지 않은 경우 둘 모두에 대해서 구현 될 수 있다. 필수적인 기능은 NT 파일 시스템 드라이버를 위한 기능 명세에 포함 되는 것으로 반드시 제공되어야 한다. 다시 말해서, 만약 한 스레드가 특정 바이트 범위의 락을 요구한다면 윈도우 NT 계열아래의 파일 시스템 드라이버 개발자는 같은 파일 내에 같은 바이트 범위에 대해서 사용을 요구하는 모든 스레드를 락킹할 수 있어야 한다. 필수적인 락 메커니즘과 다르게 보조의 역할을 하는 락 메커니즘도 제공할 수 있다. 이 보조의 바이트 범위 락 메커니즘은 두 개의 다른 프로세스가 특정 파일 스트림의 바이트 범위 내에서 동시에 접근하며 서로 협력해야 하는 작업이 있을 때 동기화 기능을 제공한다. 주의해야 할 것은 설사 파일 시스템 개발자가 필수적 락 메커니즘 대신에 보조적 바이트 범위의 락 메커니즘을 제공하더라도 실제 윈도우 NT 플랫폼은 보조적 바이트 범위의 락 메커니즘을 효율적으로 제공하지 못한 다는 것이다. 따라서 만약 이러한 형태로 락 메커니즘을 제공하려고 하는 파일 시스템 개발자가 있다면 구현에 있어서 최대한 주의를 기울여야 한다.

우리가 이러한 바이트 범위의 락 메커니즘을 지원하는 파일 시스템을 구현 하기 위해서는 반드시 이 기능을 지원하기 위한 파일 컨트롤 블록과 컨텍스트 컨트롤 블록(FCB/CCB)에 관련된 자료구조들을 메모리상에 유지 해야 한다는 것이다. 실제 락 메커니즘에 대해서는 이후 SFS 파일 시스템 구현 예제에서 한번 더 언급하기로 하자.

동적 이름 찾기 캐시 구현

만약 UNIX 파일 시스템을 공부한적이 있는 독자라면 동적 이름 찾기 캐시(Dynamic Name Lookup Cache, DNLC)의 아이디어에 익숙할 것이다. DNLC는 디렉터리 내에서 최근에 액세스된 파일들의 캐시이다. 최근에 접근하여 온-디스크 메타 정보를 읽어온 파일 이름들은 특정 디렉터리 내에 특정 파일 이름을 빨리 찾기 위해 대부분의 경우 DNLC는 해시 리스트 자료구조로 구성한다. 대부분의 파일 시스템 구현에서 디렉터리 내에 특정 파일을 찾기 위해서 선형 검색 알고리즘을 사용하는데 DNLC는 최근에 접근한 파일 이름을 찾기 위해서 이러한 선형 검색을 피하고 속도를 증가 시키는 역할을 한다. (캐시라는 이름도 이러한 이유로 유추 할 수 있다)

정확히 이야기하면 DNLC를 구현하는 것은 필수사항은 아니다. NT 커널을 포함 대부분의 운영체제는 파일 시스템 드라이버 개발자가 DNLC를 지원하는 것에 대하여 특별히 신경을 쓰지 않는다. 하지만 성능상의 가급적 DNLC의 구현을 고려 해주는 것이 좋다. 리눅스 커널에 익숙한 사람이라면 한번 생각 해보라. 가장 많이 콘솔에 치는 명령어가 무엇인가? 디렉터리 내에 파일을 찾아내는 "ls" 이다. 어떤 경우는 해야 할 일이 없을 때 아무 없이 "ls"를 콘솔 창에 치기도 하니까 말이다.

파일 스트림과 디렉터리 할당량 관리

NT 커널이 과거 파일 스트림과 디렉터리, 논리적 볼륨에 대하여 할당량을 관리 하지 않았지만, NT 버전 5.0부터 이를 지원한다. UNIX 계열의 운영체제의 디스크 할당량 관리처럼 파일 스트림, 디렉터리에 대한 할당량 관리를 지원하려면 파일 시스템 개발자는 반드시 이에 관련된 적절한 자료 구조를 인-메모리, 온-디스크 모두에 유지 해야 한다. 물론 이러한 기능이 제대로 지원을 적절히 구현하지 못하였다면 이러한 기능을 하는 필터 드라이버를 제작하여 기존 파일 시스템 드라이버를 지원 할 수 있다.

기회 락킹 메커니즘.

기회 락(Opportunistic Lock, oplock)은 윈도우 기반의 플랫폼에서 네트워크를 관리하는 LAN 매니저의 기능 중 하나이다. 기본적으로 기회 락은 서버가 자신의 클라이언트들에게 자신의 지역 디스크를 공유할 수 있게 해준다. 이를 통하여 서버는 클라이언트에게 특정 파일 스트림이 서버에 의해서 변경 되지 않는다는 것에 대하여 정보를 전달 할 수 있고, 클라이언트는 서버에 의해 파일의 변경이 필요 한 경우 변경이 일어나기 전에 이에 대한 사실을 확인 할 수 있다.

oplock으로 불리는 기회 락의 이러한 기능을 이용하여 클라이언트는 파일 스트림의 캐싱을 안전하게 할 수 있기 때문에 원격 파일 스트림 접근에 대한 응답시간을 최대한 줄일 수 있다. 만약 이러한 기능이 제공되지 않는다면 클라이언트가 캐시를 하는 동안에 서버가 이러한 데이터를 변경하게 되어 비 일관성 문제를 야기 할 수 있기 때문에 클라이언트는 매번 동기화 과정을 거쳐야 하는 오버헤드를 감수 해야 한다. oplock은 파일 시스템 구현에 필수적인 항목은 아니지만, 만약

네트워크 리렉터리를 개발하고 있는 것이 아니고 자신의 파일 시스템이 앞서 언급된 LAN 매니저와 논리적 볼륨을 공유 해야 한다면 oplock 구현을 반드시 고려해야 한다. oplock은 DNLC처럼 필수 요구사항은 아니지만 구현되지 않았을 경우 공유된 논리 볼륨의 접근에 대해여 심각한 성능저하를 가져 올 수 있다.

디렉터리 변경 통지 기능

디렉터리 변경 통지 기능은 윈도우 운영체제와 I/O 매니저가 필요로 하는 또 다른 종류의 기능이다. 대체적으로 디렉터리 변경 통지는 유저 모드나 커널모드의 컴포넌트들이 특정 디렉터리나 디렉터리 트리들의 변경을 모니터링 하는데 유용하게 쓰인다. 이러한 컴포넌트들은 자신이 원하는 변경이 어떤 것인지 (예를 들면 파일의 생성에 대한 모니터만을 원한다던가, 수정 작업에 대해서만 모니터를 원한다던가 하는) 정확히 기술 할 수 있고 이를 이용해서 I/O 매니저에게 이를 요구할 수 있다. 요청을 받은 I/O 매니저는 기술된 변경 사항이 감지되면 비동기적으로 이에 대해 알아 낼 수 있도록 파일 시스템을 질의한다. 이러한 디렉터리 변경 통지 기능은 많은 어플리케이션으로 하여금 특정 디렉터리의 변경을 감지 하기 위해 단순히 계속 정보를 질의하며 시간을 보내는 비효율적인 방법을 피하게 해준다. 물론 이러한 디렉터리 변경 통지도 파일 시스템에게 필수적으로 구현되어야 하는 요구사항은 아니지만 모든 NT계열의 파일 시스템들은 이를 지원하고 있기 때문에 파일 시스템 개발자는 디렉터리 변경 통지 기능의 구현을 고려해주어야 한다.

데이터 압축

NTFS는 데이터 압축을 기본 기능으로 제공하고 있다. 따라서 파일 시스템 개발자는 데이터 압축 기능을 구현 해야 할 필요가 있으며 필요에 따라 온라인(Online) 데이터 압축 메커니즘을 제공해야 할 수도 있다. 데이터 압축 기능을 제공하기 위해서 파일 시스템 드라이버 개발자는 온-디스크 와 인-메모리 자료구조를 이용하여 특정 파일 스트림이 압축 되었는지를 기술 할 수 있어야 하며 만역 압축 되었다면 원래 파일 스트림의 사이즈는 얼마였는지 또 이를 관리하기 위한 정보들을 다룰 수 있어야 한다.

NT I/O 매니저는 파일 시스템 개발자에게 데이터 압축을 지원하기 위해 사용자 프로세스가 압축된 형태의 파일 스트림을 요구할 수 있도록 하는 시스템 콜 인터페이스(System Call Interface)를 제공한다. I/O 매니저가 사용자 프로세스로 하여금 압축 제어에 관련된 정보와 실제 파일 스트림의 사이즈, 압축된 파일 스트림의 사이즈를 질의 할 수 있게 해 놓았기 때문에 파일 시스템 개발자는 이에 대한 정보를 반드시 유지 해주어야 한다.

암호화 기능

개발해야 하는 파일 시스템의 특성에 따라 저장된 데이터에 대하여 동적으로 암호화와 이에 대한 해독을 해야 할 수 도 있다. 당연히 이러한 요구사항을 만족 시키기 위해 이를 구현하는 파일 시스템 개발자는 반드시 암호화, 해독에 관련된 정보를 관리하는 자료구조를 설계, 유지 해주어야 한다. 만약 파일 시스템 개발 당시에 암호화 기능을 구현하지 않았는데 추후에 이를 구현 해주어야 한다면 해당 파일 시스템 자체를 변경 시키지 않고 필터 드라이버를 파일 시스템 위에 상주시켜 이 기능을 대신 수행하게 할 수 도 있다.

빠른 리커버리(Recovery)를 위한 로깅(Logging) 작업

잘 알려진 바와 같이 NTFS는 예상치 못했던 시스템 실패에 대해서 빠른 리커버리 로깅(Recovery Logging)을 위한 인-메모리와 온-디스크 자료구조를 사용한다. 만약 독자가 로그 기반의 파일 시스템을 개발해야 한다면 로그 파일 스트림과 로깅을 위한 적절한 인-메모리, 온-디스크 자료구조들을 설계 하여 관리 해야 한다. 로그 기반의 파일 시스템과 저널링 기법들에 대한 연구는 이제까지 활발하게 이루어져 왔다. 이 중에서 가장 근간이 되는 것은 버클리 대학의 Mendel Rosenblum 와 John K. Ousterhout이 작성한 "The Design and Implementation of a Log-Structured File System"으로 로깅 작업을 지원해야 한다면 이 논문을 읽어보는 것이 가장 바람직하다.

온-디스크 자료구조 지원

일반적으로 네트워크 네트워크 리디렉터, 데이터 베이스 파일 시스템들은 온-디스크 파일 스트림을 관리 하기 위하여 온-디스크 자료구조들을 사용해야 한다. 여기는 디렉토리의 컨텐츠(Contents)들을 담고 있는 디렉토리 엔트리 자료구조, 온-디스크 FCB, inode, vnode니 비트맵(Bitmap), 볼륨 정보와 같은 것들이 필요 할 수 있다. 이러한 온-디스크 자료구조 지원은 비록 네트워크 리디렉터나 데이터 베이스 이외에도 플래시를 사용하는 파일 시스템, 새로운 포맷 형태의 파일 시스템을 개발하는 개발자라면 온-디스크 자료구조를 설계 관리 해야 한다. 또한 이러한 형태의 파일 시스템 개발자는 온-디스크 자료구조를 저장하고 읽어오는 시점을 잘 결정해주어야 하며 이를 인-메모리 자료구조로 변경 시켜 메모리상에서 관리 할 수 있도록 하는 방법을 제공해야 한다.

다음 칼럼에는

자료구조는 명시적으로 그것에 관여하는 컴포넌트들과 알고리즘, 일정한 형태의 루틴뿐만 아니라 암묵적으로 관여되는 커뮤니케이션 방법을 모두 담고 있다. 특히나 세부적인 요구사항이 다양하고 복잡하게 얽힌 운영체제를 대부분이 레이어드(Layered) 아키텍처를 사용하여 설계, 유지 보수를 하고 있다. 이러한 레이어드 아키텍처에서는 직,간접적으로 각 컴포넌트들간에 자료구조 사용에 간섭이 존재 한다. 간혹 자료구조와 암묵적 통신 방법을 이해하지 못하는 경우 필요한 코드를 써 내려가면서 실제로 왜 이러한 코드가 자신의 드라이버 안에 있는지 모르는 경우가 종종 있다.

우리는 우선적으로 눈에 보이는 자료구조들을 정의하고 이에 필요한 통신 지식들을 습득 함으로써 실제 구현에 들어갔을 때 전반적으로 이를 이해 할 수 있도록 이에 대한 내용을 칼럼상 선 배치 하였다. 다음 칼럼부터는 디스패치 루틴 중 드라이버의 진입점을 위한 코드 설정, 열기, 읽기 둥의 기본 동작들을 정의하고 이러한 동작들에 대한 간략한 설명과 함께 실제 구현 예를 살펴 볼 것이다.

References

Rejeev Nagar, "Windows NT File System Internals": A Developer Guide, O'Reilly 1998

P. B. Kruchten."The 4+1 View Model of architecture."

David Garlan and Mary Shaw January 1994 "An Introduction to Software Architecture"

Kernel Source http://reactos-mirror.googlecode.com/svn

Kernel Source http://nuwen.net

파일 시스템 구현을 위한 컨트롤 블록과 설계

Major Control Blocks and Design for NT File System Implementation

파일 시스템 드라이버는 특정 데이터를 블록 디바이스(Block Device)로부터 정확히 인출 해주거나 저장 할 수 있는 여러 가지 정보들이 필요하다. 또한 이러한 인출, 저장, 생성 동작에 의해서 시스템의 성능이 저하 되지 않도록 각 자료구조들을 구성 해야 하며, 파일 시스템 드라이버가 사용하는 자료구조 중 온-디스크(On-disk) 상태를 유지해야 하는 특정 정보들에 대한 분리가 필요하며 이를 관리하는 파일 시스템 드라이버의 컨트롤 블록들이 커널 메모리 어떤 부분에 상주해야 하는 지 또한 설계해야 한다.

정명수 |

필자는 지난 3년간 삼성전자에서 플래시 메모리와 관련된 연구와 임베디드 소프트웨어, 커널 드라이버 등을 개발 했었다. 현재는 조지아 공대(Georgia Institute of Technology) 컴퓨팅 칼리지에 재학 중이다. 글쓰기를 매우 좋아하며 학부시절에는 객체 지향 패러다임을 통하여 해석하는 프로그래밍 언어론에 관심이 있었으나 실무과정을 거치면서 컴퓨터 아키텍처로 관심사가 옮겨졌다. 최근에 관심 있는 분야는 운영체제, 파일시스템, 실시간 스케줄링 등이다.

바로 이전 달 칼럼에서 우리는 파일 시스템의 기본 기능을 위한 컨트롤 블록(Control Block)들의 전제적인 구조에 대한 도식을 간단하게 살펴 보았다. 본 칼럼에서는 파일 시스템 드라이버라면 반드시 필요한 주요 컨트롤 블록과 이를 커널 메모리 상에서 어떻게 구성 할 것인지, 자료구조는 어떤 식으로 디자인하는지를 알아 볼 것이다. 그리고 저번 컬람의 논리 블록, 물리 블록 파라미터를 설명하면서 빠진 VPB 자료 구조도 간단히 언급 할 것이다. 이번 칼럼에서 주로 다루는 주요 파일 시스템 드라이버의 컨트롤 블록들은 아래와 같다.

1. 볼륨 컨트롤 블록(Volume Control Block)
2. 파일 컨트롤 블록(File Control Block)
3. 컨텍스트 컨트롤 블록(Context Control Block)

이 자료 구조들은 저번 칼럼(마이크로소프트웨어 2월)에 나와 있는 도식과 개념들을 바탕으로 이루어지므로 만약 이에 익숙하지 않은 독자가 있다면 해당 칼럼을 반드시 참고하기를 권한다.

VPB 자료구조

이전 칼럼의 다이어그램에서 VPB 구조체의 위치를 미리 선보였었는데, 여기서는 VPB 구조체의 실질적인 기능과 몇 가지 주의사항들을 알아보도록 하자. VPB 구조체는 물리 디스크 디바이스 오브젝트(Physical Disk Device Object)와 논리 볼륨 디바이스 오브젝트(Logical Volume Device Object)사이에 논리 연관성을 생성하는 중요한 작업을 맡고 있다. 다만 VPB는 실질적으로 마운트(mount)가 가능한 물리, 가상, 논리 미디어에 대한 정보만 관리하는 디바이스 오브젝트 이기 때문에 파일 시스템 개발자가 네트워크 리디렉터(Redirector)나 서버 형태의 드라이버를 개발한다면 VPB 구조체를 통해서 직접 이를 관리 할 수 없다.

앞서 언급 되었듯이 VPB 구조체는 논리적 관계를 기술 하는 자료구조로서 여기에는 마운트된 디바이스의 물리 디바이스 오브젝트와 논리 디바이스 오브젝트의 물리적 연관관계를 기술 하지는 않는다. 다시 말해 "Attach(어태치)" 동작에 의해 연결되는 논리 볼륨 디바이스에서 물리 디바이스, 또는 물리 디바이스에서 논리 볼륨 디바이스로 가는 직접적 포인터가 존재 하지 않는다. 이후에 다시 언급 되겠지만 "Attach" 작업의 대표적인 I/O 매니저의 API인 IoAttachDevice는 해당 마운트된 디바이스의 파일 시스템이나 필터 드라이버들의 디바이스 오브젝트와 실제 목적지의 오브젝트 관계를 연관 시켜 주어 원래 디바이스 오브젝트로 가는 리퀘스트(Request)들을 가로채기 위한 한 가지 방법으로 사용 되는 것이지 이 둘간의 물리적 연관 관계를 기술하는 것이 아니라는 것을 기억하고 있어야 VPB를 올바르게 이용 할 수 있을 것이다.

VPB가 논리적 연관 관계만을 기술한다고 해서 파일 시스템 마운트 작업 시 다른 작업이 필요한 것은 아니다. 여기서 필요한 것은 두 디바이스 오브젝트간의 논리적 연관만을 VPB 구조체를 통하여 기술 하면 된다. 왜냐하면 NT커널의 I/O 매니저는 VPB 구조체를 통해서 두 디바이스 오브젝트간의 연관 관계를 확인 하고 특정 리퀘스트가 어느 파일 시스템 볼륨 디바이스 오브젝트로 가야 하는지를 알 수 있기 때문이다. 각 파일 오브젝트 구조체가 정상적으로 온-디스크 자료구조(1월 칼럼에 기술)을 포함한 해당 디바이스 열기 작업을 수행 하였다면 해당 파일 오브젝트는 물리 디바이스를 소유한 VPB의 정보를 참조 할 수 있다.

VCB (볼륨 컨트롤 블록, Volume Control Block)

바로 앞서 언급 된 것처럼, 마운트 작업의 일부로서 파일 시스템 개발자들은 각 파일 시스템이 해당 논리적 볼륨에 저장되는 데이터들에 대한 접근 관리할 인-메모리(In-memory) 자료구조를 생성 해야 한다. 우리가 제작할 SFS(Simple File System)에 의해 관리되는 해당 자료구조 중에 하나가 바로 볼륨 컨트롤 블록이다.

볼륨 컨트롤 블록인 VCB 스트럭처는 파일 시스템 드라이버의 필수적인 정보들을 다루기 때문에 매우 중요하다. 얘를 들면 이 정보 안에는 다른 인-메모리 루트(Root) 스트럭처를 가리키는 포인터, 논리적 볼륨 위에 현재 열려 있는 파일 스트림의 개수, 특정 시점의 논리적 볼륨의 상태 플래그, 동기화를 위해 VCB가 스스로 관리하는 정보 등이 여기 포함 된다. 저번 칼럼에서 SFS의 취지를 소개 했듯이 우리는 베니어(Veneer) 레이어에 좀 더 초점을 맞추고 있기 때문에 SFS에 의해 관리 되는 대부분의 자료구조들처럼 VCB 자료구조 중에서도 디스크상의 가용 가능한 클러스터 들의 정보, 할당된 클러스터 정보, 그리고 이 정보들을 관리하는 온 디스크 스트럭처들에 대한 포인터를 관리 한다. Windows NT I/O 매니저는 파일 시스템 드라이버가 관리해야 하는 자료 구조들을 관리할 필요가 없지만, 파일 시스템은 VCB 스트럭처와 같은 자료 구조들을 관리 해주어야 한다.

우리가 만드는 SFS는 마운트된 논리 볼륨을 기술 하기 위해 VCB 스트럭처를 디바이스 오브젝트 익스텐션(Device Object Extention)에 할당한다. 만약 개발자가 Windows 디바이스 드라이버에 대한 지식이 있다면 두 가지를 짐작 할 수 있다. 첫 째, VCB 스트럭처를 할당 하는 것은 기존 시스템과 파일 시스템의 내부 기술 구조에 대한 연관관계를 생성하는 방법이므로 매우 정형화 된 일이 다는 것이며, 둘 째, VCB 구조체는 비페이징 영역의 메모리에 할당 되어야 한다는 것이다. 왜냐하면 디바이스 오브젝트 익스텐션은 디바이스 오브젝트(Device Object)를 생성할 때 NT I/O 매니저에 의해 비페이징 영역에 할당 되기 때문이다.

<그림 1, 볼륨 컨트롤 블록의 자료구조>

그림 1에 기술 되었듯이 SFS에 의해 생성된 VCB는 NT 캐시 매니저가 사용하는 정보를 담은 필드들이 존재 한다. 대부분의 Windows NT 파일 시스템 드라이버 구현은 온-디스크 형태의 볼륨 메터(Meta) 정보를 메모리상에 캐시 하기 위해 캐시 매니저를 사용한다. 이를 캐싱하기 위해서는 온-디스크 볼륨 정보를 기술 하는 스트림 파일 오브젝트를 생성하고 이 파일 오브젝트를 캐싱을 초기화 해주는 작업을 수행 해야 한다. 이 데이터는 CcMapData() 함수를 이용하여 파일 시스템 캐시를 통하여 사상(Mapping)되며 일반적으로 사용자 스레드에 의해서 접근이 될 수 있을 정도로 비교적 손쉬운 방법으로 접근할 수 있다.

심플 파일 시스템 드라이버(Simple File System, SFS)

이전 컬럼에서 소개된 다이어그램(CCB, FCB, 파일 오브젝트에 대한 연관 관계 다이어그램)에서 최 하단에 존재하는 파일 컨트롤 블록은 메모리상에 각 파일 스트림에 대한 정보를 기술 한다. 어플리케이션이 사용자에게 서비스를 제공하기 위해 인-메모리 형태의 자료 구조를 사용 하듯이 파일 시스템 또한 인-메모리 데이터 스트럭처를 사용 해야 한다. 전통적인 파일 시스템은 일반적으로 파일과 디렉토리, 두 가지 형태의 온-디스크 스트럭처를 사용한다. 파일은 우리가 이해하고 사용하고 있는 정의 그대로 디스크 상에 저장된 바이트단위의 스트림이고 디렉토리는 파일 시스템이 파일에 대한 정보들을 관리 하기 위해 따로 정의한 스트럭처이다. 디렉토리는 사용자 데이터를 저장하는 입장에서 봤을 때 아무런 의미가 없지만 데이터베이스 관점에서 봤을 때 실제 데이터를 위한 인덱스와 같은 역할을 한다. 파일과 디렉토리는 리부팅에 자유로운 형태로 비휘발성 스토리지에 저장되는 영구적인 오브젝트라고 봐도 무방하다.

파일들은 디렉터리 안에 명명된 형태의 오브젝트 형태로 존재 하기 때문에 파일 오브젝트로 명명되어 있는 디렉토리 엔트리(Entry)와 이와 연관된 데이터들 사이에 논리적 분리 자체가 무엇 보다 중요하다. 예를 들어서 파일 "디렉토리1"에 포함된 "파일1"을 생각 해보자. "디렉토리1"의 디렉토리 엔트리에 의해서 "파일1"을 인식할 수 있는데, 해당 파일의 사이즈와 관계 없이 고정된 사이즈의 "파일1"에 대한 유효 오브젝트로서 디렉토리 엔트리는 반드시 하나 존재 하게 된다. 만약에 16바이트짜리 파일이 있는데 이를 잘라냄(Truncate)을 통해서 0 바이트로 만들었다고 하더라도 디렉토리 안의 디렉토리 엔트리는 그대로 존재하게 된다. 이러한 잘라냄 동작은 디렉토리 엔트리를 삭제하거나 해제 시키지 않고 해당 엔트리의 파일 사이즈 정보만 0 바이트로 갱신 해줄 뿐이다. 이와 달리 만약 파일 자체를 삭제(Delete) 한다면 해당 파일에 대한 디렉토리 엔트리는 해제 될 것이고 데이터를 위해 할당된 스토리지 또한 해제될 것이다.

이와 조금 다른 상황을 생각 해보자. 만약 파일 시스템 드라이버가 다중(Multiple) 링크드 파일들을 지원 한다면 파일 이름과 파일 데이터를 위한 스토리지 영역의 분리는 좀 애매한 상황이 된다. 다시 말해 두 개로 분리된 각기 다른 디렉토리 엔트리가 데이터를 저장하는 같은 온-디스크 스트럭처를 참조하는 상황이 있을 수 있다. 예를 들어 "디렉토리1"에 존재 하는 "파일1"과 "디렉토리2"에 존재하는 "파일2"가 같은 온-디스크 데이터를 가리키는 유사물이 될 수 있다. 이러한 경우 만약 독자가 "파일1"을 삭제 한다고 하더라도, 다시 말해 디렉토리 엔트리는 삭제 하더라도 해당 데이터를 위해 할당된 스토리지는 해제 되지 않는다. 왜냐하면 "디렉토리2"의 "파일2"가 할당된 스토리지를 참조 하고 있기 때문이다. 해당 데이터를 위해 할당된 스토리지 영역은 그것을 참조하는 모든 데이터 엔트리가 삭제 된 다음에야 해제 될 수 있다.

사용자가 파일이나 스토리지에 존재하는 디렉토리 오브젝트에 접근을 시도 할 때 파일 시스템은 사용자 리퀘스트를 만족하기 위해서 반드시 스토리지로부터의 정보를 보유해야 한다. 일반적으로 이 실질적인 데이터 정보는 디스크에 저장되지만, 마지막 갱신 시간이나 마지막으로 읽은 시간 등 사용자가 컨트롤 정보 또는 메타 정보를 요구하는 경우 파일 시스템은 이를 만족 시키기 위해서 디스크가 아닌 곳에서 정보를 인출하여 서비스할 수 있다.

앞서 말한 기능(메타정보 인출)을 위해서 파일 시스템은 열린 파일들이나 디렉토리의 추상화 수준의 자료 구조를 생성하고 관리 한다. 다시 말해 각 파일 시스템들은 인-메모리에 사용자의 리퀘스트를 만족시키기 위해서 컨트롤 데이터 스트럭처를 정의하고 이를 관리하여 실제 디스크로의 접근 횟수를 줄이고 성능향상을 꾀 할 수 있다. 물론 이러한 인-메모리 형태의 자료구조 관리는 파일 시스템 구현 자에게 달려 있다. 보통 인-메모리의 자료구조는 온-디스크 데이터의 접근을 용이하게 하고 스토리지에 저장된 데이터로부터 새로 생성 될 수 있다.

대부분의 UNIX 계열의 구현에서는 파일이나 디렉토리를 추상화하여 인 메모리 추상화를 보통 vnode라고 부른다. Windows NT 계열에서는 이러한 추상화를 파일 컨트롤 블록이라고 부른다. 어떤 용어를 사용하여 이 추상화를 기술 하던 간에 중요한 것은 하나의 온-디스크 오브젝트는 하나의 추상화 도구로 기술 된다는 것이다. 따라서 설사 파일 시스템이 다중 링크드 파일 스트림을 지원 하더라도 개발자는 이 파일 스트림을 위하여 반드시 하나의 FCB만을 생성해야 한다. 다른 프로세스가 다른 경로 이름이나 심볼을 통해 같은 온 디스크 오브젝트를 참조한다고 하더라도 전자와 마찬가지로 다루어야 한다.

SFS의 자료구조는 크게 두 가지 논리적 콤포넌트를 필드로 구성한다. 하나는 SFS_NT_DEPEND_FCB라고 불리는 자료 구조로서 NT 커널에 의존적인 자료구조들을 가지고 있다. 이 필드의 내부에는 NT 캐시 매니저에서 소개된 위 섹션 오브젝트 포인터 스트럭처와 공용 FCB 헤더를 포함한다. 선언된 코드는 그림 2와 같다.

<그림 2, SFS의 NT 의존성 파일 컨트롤 블록 자료구조>

물론 파일 시스템 드라이버는 해당 파일 시스템의 컨트롤 정보 또는 메타 데이터를 디스크로 데이터를 저장해야 하는 경우도 있는데 이는 그림 3에 정의된 디스크 의존 파일 컨트롤 블록으로 선언하여 사용한다. 이는 구현될 파일 시스템의 FCB에 정의 되기 때문에 만약 파일 시스템 개발자가 추가적으로 자신만의 데이터를 관리하고자 하면 그림 3과 같이 선언하여 FCB 내에서 사용하도록 한다. 이렇게 분리된 자료구조는 파일 시스템을 포팅하거나 수정할 때 유용하게 사용 될 수 있는 간단한 추상화 기법이다.

<그림 3, SFS 디스크 의존성 파일 컨트롤 블록 자료구조>

두 번째는 현재 존재하는 시스템과는 독립적인 데이터를 관리하는 SFS의 실제 파일 컨트롤 블록이다. SFS_FCB에 대해서 관심을 가져야 하는 첫 번째는 이 자료구조의 컨텐츠에 대해서 운영체제가 결정하는 것은 아무 것도 없다는 것이다. 따라서 각 파일 시스템 구현에서 FCB 자료구조에는 확장성, 다시 말해 개발자가 필드를 필요에 따라 추가 하거나 삭제 할 수 있다. 그림 4에 제시된 SFS의 파일 컨트롤 블록의 각 필드들은 일반적으로 Windows NT아래 생성되는 대부분의 파일 시스템에서 필요한 필드들이다. 대부분의 파일 시스템은 파일 컨트롤 블록과 연관된 오브젝트 이름에 대한 특정 정보들을 관리한다. 파일 시스템이 하는 것과 유사하게 FCB 또한 레퍼런스 카운터와 핸들 카운터(그림 4참조) 필드를 관리하는데 이는 이후 칼럼에서 이를 어떤식으로 SFS가 사용하는지 알아 볼 것이다. 코드 예제 형태로 제시 될 텐데 이는 해당 두 필드가 파일 시스템을 제작하면서 어떻게 유용하게 사용되는 지를 잘 설명 할 수 있을 것이라 생각한다.

.

<그림 4, SFS의 파일 컨트롤 블록 자료구조>

앞서 살짝 언급 되었지만 그림 4의 SFS의 FCB에는 온-디스크 자료구조에 대한 정보가 거의 없다. 예를 들어서 FCB에 의해서 기술되는 파일 스트림의 실제 온-디스크 클러스터들에 대한 정보들이 빠져 있다. 베니어 레이어에서는 이러한 자료구조가 필요하지 않지만 실제 제작자들의 환경에 따라 파일 시스템에 필요한 자료구조들이 정의 될 수 있다. 만약 우리가 제작하고 있는 SFS의 코드를 가지고 특정 파일 시스템에 적용하려 한다면 온-디스크 포멧에 맞는 자료구조를 분리된 형태로 정의하고 포인터나 아니면 그림 5처럼 자료구조를 그대로 FCB안에 선언하는 형태로 하여 디스크 독립적인 자료구조와 아닌 자료구조를 FCB내에 구분 시킬 필요가 있다.

<그림 5 파일 컨트롤 블록의 구성>

우리는 SFS 파일 컨트롤 블록에 디스크 의존 파일을 포인터가 아닌 일반 삽입 형태로 선언 하여 선언하였다.

이제 NT 커널에 의존성이 존재하는 FCB 자료구조에 대해서 이야기 해보자. 비록 Windows NT 가 파일 시스템 드라이버로 하여금 파일 시스템 컨트롤 블록을 자유롭게 선언 하도록 하고 있지만 NT 캐시 매니저와 가상 메모리 매니저를 사용하고 파일 시스템 드라이버가 이와 유기적으로 동작하기 위해서는 NT에서 정의된 자료구조들이 FCB에 의해 관리 되어야 한다. 물론 파일 시스템을 생성 하면서 이를 무시한 채로 자신이 직접 모든 것을 개발 할 수 있지만 이제까지 설명 했던 대로 시스템 캐시를 사용하는 것이 훨씬 효율 적이며 메모리 맵드(Mapped) 파일 같은 것을 사용 하기 위해서라도 이러한 NT에 의존성을 가진 필드들을 파일 컨트롤 블록에서 사용 할 수 밖에 없다. 각 FCB는 크게 3 종류의 NT 의존 자료를 사용하는데 하는 FSRL_COMMON_FCB_HEADER이고 다른 하나는 SECTION_OBJECT_POINTERS, 그리고 나머지는 동기화를 위한 ERESOURCE이다 하나의 파일 스트림에 대해여 인-메모리에 이를 기술하는 FCB를 하나 선언 하는 것과 마찬 가지로 특정 FCB와 연관된 공용 FCB 헤더와 섹션 오브젝트, 리소스들은 하나씩만 선언 되어야 한다. 앞서 언급 되었듯이 이러한 NT 의존성 필드들은 FCB내에 선언 될 필요 없이 다른 형태로 파일 시스템 개발자에 의해서 관리 될 수 있지만, 파일 스트림당 유일한 인스턴스 또는 스트럭처로 존재 하는 공통점 때문에 통상적으로 FCB안에 같이 선언 하여 사용한다.

파일 시스템 드라이버 개발자는 이 NT 의존성 자료구조들을 반드시 메모리에 할당 해주어야 하는데 그림 5에서 볼 수 있듯이 ERESOURCE 타입은 절대 페이징 영역에 할당 되어서는 안 된다. 또한 공용 FCB 헤더와 파일 오브젝트 포인터 또한 절대 페이징 영역에 할당 시켜서는 안 된다.

컨텍스트 컨트롤 블록(Context Control Block, CCB)

CCB 자료구조는 파일 시스템 드라이버가 파일 스트림에 대한 열기 동작에 상태 정보들을 저장하기 위해 사용 된다. 앞서 언급 되었듯이 각 파일 스트림은 인-메모리에 단일 FCB에 의해서 기술 된다. 문제는 FCB 구조체가 파일 스트림에 대한 접근에 대한 정보만을 관리한다는 데 있다. 따라서 FCB는 사용자의 파일 열기 동작에 대한 어떠한 정보도 가지고 있지 않기 때문에 이를 대신 하기 위하여 컨텍스트 컨트롤 블록이 사용 된다.

CCB는 파일 시스템 드라이버에 의해서 성공적인 열기 동작 때 마다 생성 된다. 각 CCB 스트럭처는 일반적으로 그 파일 스트림에 해당하는 FCB에 서로 링크로 연결 되고 조합된다. CCB 또한 FCB처럼 FCB로 가는 백포인터(Back-pointer)를 소유하는 것이 일반적이다.

이전 달 칼럼에서 소개 되었던 CCB, FCB, 파일 오브젝트에 대한 관계도를 살펴 보면 3개의 CCB를 확인 할 수 있다. 파일 시스템 드라이버는 이 3개의 CCB를 IRP_MJ_CREATE 리퀘스트를 받을 때 마다 생성하였다. 좌측 두 개의 CCB는 하나의 FCB로 연결 되어 있는데 이는 같은 파일 스트림에 대한 두 번의 IRP_MJ_CREATE 리퀘스트를 받았음을 의미한다. 이 둘 이외에 다른 CCB는 나머지 하나의 FCB에 연결 되어 있다.

주의 해야 할 것은 FCB와 CCB간의 사상은 일대다의 형태가 가능하지만 NT I/O 매니저가 열기와 생성 요청에 대해서 생성한 파일 오브젝트 스트럭처와 파일 시스템 드라이버에 의해 생성된 CCB간의 사상은 일대일로만 가능 하다는 것이다. 따라서 하나의 파일 스트림에 대해서 FCB는 하나가 존재 할 수 있지만 CCB와 파일 오브젝트는 다수 존재 할 수 있다.

그렇다면 파일 스트림에 대해서 FCB는 하나 존재 함에도 불구하고 대부분의 파일 시스템 드라이버가 파일 스트림 열기에 대해서 다수의 CCB를 생성하여 관리 하는 이유는 무엇일까? 여기에는 파일 스트림의 특정 정보는 전역적으로 관리가 안되고 그러한 특정 정보들은 하나의 파일 스트림에 대해서 공용된 상태를 유지 하지 않는다. 이러한 상황의 간단한 예로 CCB들은 사용자 스레드로 요청 받은 바이트 범위의 락에 대한 정보를 유지 할 수 있다. 만약 스레드가 파일 핸들에 대해서 락을 해제 하지 않고 파일을 닫았다면 IRP_MJ_CLEANUP을 받은 파일 오브젝트라 자신과 일대일로 사상된 CCB의 인스턴스를 인출하여 락에 대한 정보를 확인 하여 정상적인 동작으로 유도 할 수 있다. 유사하게 파일 시스템 드라이버는 디렉토리 검색 동작에서 해당 파일 스트림에 대한 다음 바이트 오프셋 정보등을 관리 할 수도 있다.

만약 CCB가 FCB와 하나인 형태로 조합 되어 있다면 이러한 정보 관리는 아주 애매하게 될 수 있다. 따라서 이러한 CCB의 정보는 파일 시스템 드라이버로 하여금 FCB의 비 전역 정보가 사라지지 않도록 관리해주는 기능을 수행한다. NT I/O 매니저는 파일 시스템 드라이버 개발자로 하여금 CCB 구조체에 대한 어떠한 요구사항도 기술 하고 있지 않다. 따라서 파일 시스템 드라이버에 의해서 관리되는 CCB는 NT I/O 매니저에게 완전히 감춰진 정보로 사용 된다.

다음 칼럼에는

오늘은 디스패치(Dispatch) 루틴에 들어가기 전에 파일 시스템 드라이버가 갖추어야 하는 최소한의 자료구조인 파일 컨트롤 블록, 컨텍스트 컨트롤 블록, 볼륨 컨트롤 블록에 대해서 알아 보았다. 이러한 세부적인 기술에도 불구하고 분명 이를 사용함에 있어서 궁금한 점이 있을 수 있다. 따라서 다음 칼럼에서는 디스패치 루틴에 들어가기 전에 해당 컨트롤 블록들에 대해 기존에 개발자들 사이에서 알려진 노하우를 공유하고 파일 시스템 드라이버가 필요로 하는 다른 자료구조를 간단히 소개하고 파일 시스템의 디스패치 루틴을 소개 하도록 하겠다.

References

Rejeev Nagar, "Windows NT File System Internals": A Developer Guide, O'Reilly 1998

P. B. Kruchten."The 4+1 View Model of architecture."

David Garlan and Mary Shaw January 1994 "An Introduction to Software Architecture"

Kernel Source http://reactos-mirror.googlecode.com/svn

Kernel Source http://nuwen.net

파일 시스템 구현을 위한 기본 기능과 컨셉 정의

Basic Functionalities and Concepts for File System Implementation

파일 시스템 개발을 위해서 우리는 NT 커널의 기본 구조와 파일 시스템이 긴밀히 관여 해야 하는 정책, 실행부 자원(캐시 매니저, 가상 메모리 매니저, I/O 매니저)등을 알아 보았다. 실제 파일 시스템 그 자체를 설계하고 구현 하는 것은 이러한 운영체제에 의존성을 가진 것들과 큰 관여를 하지 않을 수 있지만, 파일 시스템과 관련된 NT 커널의 실행부 자원과 정책들을 이해해야 하는 것은 Windows의 기존 파일 시스템들처럼 NT 커널 내에서 적절히 상호 커뮤니케이션 하면서 신뢰성과 호환성 등을 고려 하기 동작하기 위해서이며, NT 아래서는 베니어(Veneer) 레이어가 하는 완충 작용과 프로토콜을 따리 주지 않으면 제작하는 파일 시스템이 정상적으로 동작 할 수 없기 때문이다.

본 칼럼은 파일 시스템 구현 섹션의 첫 칼럼으로써 Windows NT환경에서 파일 시스템의 설계 정책과 베니어 레이어의 기능을 정의하고, 이를 위한 자료구조의 일부를 알아 볼 것이다. 또한 운영체제에게 현재 파일 시스템의 존재 여부를 보고하기 위하여 레지스트리를 어떤 식으로 사용 해야 하는 지도 알아 볼 것이다.

정명수 |

필자는 지난 3년간 삼성전자에서 플래시 메모리와 관련된 연구와 임베디드 소프트웨어, 커널 드라이버 등을 개발 했었다. 현재는 조지아 공대(Georgia Institute of Technology) 컴퓨팅 칼리지에 재학 중이다. 글쓰기를 매우 좋아하며 학부시절에는 객체 지향 패러다임을 통하여 해석하는 프로그래밍 언어론에 관심이 있었으나 실무과정을 거치면서 컴퓨터 아키텍처로 관심사가 옮겨졌다. 최근에 관심 있는 분야는 운영체제, 파일시스템, 실시간 스케줄링 등이다.

이 칼럼을 읽고 있는 대부분의 개발자나 설계자들은 파일 시스템 전체를 구현 해야 하는 경우에 있지는 않을 것이다. 컴퓨터 공학과 과학 쪽에서 이제는 대부분의 문제나 이슈들이 수렴되고 거의 안정화 단계에 들어가는 분야가 크게 두 가지가 있는데, 하나는 캐시 관련 문제이고 다른 하나는 파일 시스템 관련 문제이다. 이런 이유 때문에 상업적으로 사용할 목적으로 독립적 파일 시스템을 구현해야 하는 개발자는 매우 드물다. 그러나 많은 사람들이 윈도우 NT 커널에 파일 시스템이 어떤 식으로 구성되고 동작하는 지 그리고 파일 시스템의 설계, 구조, 동작 알고리즘과 같은 것들을 궁금해 한다. 나아가 많은 사람들이 파일 시스템과 같은 형태의 기능을 가지는 소프트웨어를 구현 해야 하거나 또는 파일 시스템과 긴밀히 연관되는 모듈을 작성 해야 할 수 있다. 긴밀히 연관 되는 모듈은 어떤 것들이 있을까? 예를 들면 독자들이 어플리케이션 레벨에서 의사 파일 시스템(Pseudo file system)형태로 소스 코드를 관리 해주는 프로젝트를 개발 할 수 도 있고, 파일 시스템 드라이버에 전달되는 입출력을 가로채어 이를 가공 한 뒤 파일 시스템에 다시 넘겨주거나 블록 디바이스(Block device)에게 전달 해주는 필터 드라이버를 개발 해야 할 수 있고, 현재 Window NT관련된 파일 시스템들(NTFS, FASTFAT, FAT32등)들의 일부 기능만 수정해서 사용 해야 할 수도 있다. 사실 어떤 이유에서 파일 시스템과 관련된 모듈을 개발하던 간에 파일 시스템의 설계 및 구현에 대한 충분한 이해가 필요한 것은 당연하다.

우리는 파일 실제 파일 시스템 개발을 위한 본 칼럼 섹션(File System Driver Implementation)을 위해서 아래와 같은 NT 커널의 실행부 자원, 매니저들을 알아 보았다.

1. NT 주요 아키텍처와 파일 시스템(NT Core Architecture and File system)
2. 가상 메모리 매니저(Virtual Memory Manager)
3. NT 캐시 매니저(NT Cache Manager)
4. NT I/O 매니저(NT I/O Manager)
5. 가상 주소 번역(Virtual Address Translation)

본 컬럼 섹션에서는 위에서 언급된 NT 컴포넌트(Component)들을 기반으로 하여 Windows NT 환경에서 파일 시스템 구현 자체에 초점을 맞출 것이다. 따라서 구현을 이해하기 전에 위의 컬럼들과 운영체제의 기존 이슈들을 이해하지 못한다면 반드시 이들을 읽어보는 것을 권한다. (운영체제에 대한 기본지식들은 필자의 블로그에서 확인 할 수 있다.)

앞으로 진행되는 장기간 진행되는 파일 시스템 구현 섹션은 파일 시스템에 대한 개발자들의 이해를 최대한 돕기 위해서 우선적으로 파일시스템 자료구조를 확인하고 파일 시스템이 Window NT 커널 환경에서 제대로 구현 되기 위한 디스패치루틴(Dispatch routine)들을 알아 볼 것이다. 디스패치 루틴과 자료구조들은 실제 Window NT의 내부구조를 이해하지 못한 독자라면 이해에 어려움을 겪기 쉬우므로 이해를 돕기 위해 각 디스패치 루틴과 관련된 파일 시스템 자체의 기능들을 기술하고 필요하다면 의사코드, 다이어그램 등으로 설명을 보충 하도록 하겠다.

파일 시스템 설계

제대로 된 설계가 없이 주먹구구식으로 작성된 파일 시스템은 이 세상에 없다. 제대로 된 설계를 위해서 우리가 파악 해야 하는 것은 우리가 작성해야 할 파일 시스템의 목적과 그 목적을 달성하기 위한 상세 기능 설계이다. 이러한 설계방식은 일반적인 개발방법론에 나오는 설계 방식과 유사하게 보이지만 실제는 그렇지 않다. 왜냐하면 파일 시스템은 다른 프로그램들과 달리 기능성 요구사항 명세(Functional Requirement)보다 비기능성 요구사항(Non-functional Requirement)가 많기 때문이다. 다시 말해 대부분의 파일 시스템은 기능성 요구사항은 읽기, 쓰기, 초기화, 생성 정도로 정해져 있기 때문에 비기능적 요구사항이 파일 시스템이 골이 되고 이를 얻기 위한 올바른 설계가 수반되어야 한다. 예를 들어 빠르고 간단한 파일 시스템을 개발 했다고 하면 이 파일 시스템의 개발 골은 신뢰성, 편리한 유지보수, 데이터 저장의 편리성등의 비기능성 요구사항이 될 수 있다. 따라서 이 파일 시스템은 현존 하는 소프트웨어나 하드웨어의 비정상적 동작에 의해 파일 시스템의 일관성(Consistency)가 깨질 수도 있으며 데이터 보안 같은 좀 더 복잡한 형태의 파일 시스템의 특징을 반영하지 않는다. 이러한 형태의 파일 시스템으로는 과거 FAT과 같은 형태의 파일 시스템을 들 수 있다. FAT과 NTFS는 모두 기능성 요구사항은 다르지만 FAT은 NTFS보다 불안정하긴 하지만 훨씬 간단한 형태의 메터정보(Meta Information) 활용과 구조변형 및 유지보수를 쉽게 할 수 있다.

NTFS의 예를 들어보자. NTFS는 Windows NT기반에 맞도록 구현된 로그 기반의 파일 시스템 이다.(Log-based file system, 좀 더 자세한 이해를 원하는 독자는 Mendel Rosenblum와 John K. Ousterhout의 논문 The Design and Implementation of a Log-Structured File System를 반드시 읽어보도록 권한다. 이 논문은 모든 로그기반의 파일 시스템의 근원이 되는 논문으로 이를 이해하는데 큰 도움이 될 것이라고 필자는 확신한다) 이 파일 시스템은 앞서 언급된 FAT과 같은 형태의 빠르고 간단한 형태의 파일 시스템과 달리 기본 목표가 시스템 실패로부터 빠른 복원과 데이터 일관성(Consistency)를 위해서 만들어졌으며, 데이터 압축이나 바이트 범위의 잠금 기능을 제공한다. 이런 로그 기반의 파일 시스템보다 복잡한 형태가 분산 파일 시스템이다. 앤드류 파일 시스템(Andrew File System)과 같은 형태의 DPS(Distribute File System)는 파일 시스템 구현이 훨씬 복잡한 형태의 좋은 예가 될 수 있다. 이 파일 시스템은 NTFS와 같은 로컬 파일 시스템의 기능과 함께 원거리 서비스를 위한 클라이언트 서버 컴포넌트를 조합하여 하나의 네임스페이스(Namespace)로 이를 접근 할 수 있도록 해준다. 엔드류 파일 시스템 이외에 마이크로 소프트의 오브젝트 파일 시스템(Object File System)또한 복잡한 형태의 파일 시스템 목표와 디자인 설계를 가지고 있다.

파일 시스템 코드

앞으로 우리가 컬럼에서 실습하여 작성해볼 간단한 파일 시스템(이후 SFS또는 Simple File System으로 이를 호칭)의 골을 설계해보자. 우리가 작성할 파일 시스템은 특정한 하드웨어 없이 Windows NT 커널의 컴포넌트와 파일 시스템 드라이버 사이에서 상호작용 정도를 조작하는 형태의 간단한 파일 시스템이다. 따라서 이 칼럼에서는 파일 시스템 그 자체(예를 들면 메타 정보관리 및 블록 디바이스 특성을 고려한 설계 및 구현)에 대한 구현은 가급적 생략하여 일반적인 형태로 윈도우 위의 파일 시스템 개발에 도움이 되고자 한다. 모든 파일 시스템은 정의된 시스템 서비스 루틴을 사용하여 데이터 관리를 요하는 사용자들의 요구를 만족 시켜주기 때문에 파일 시스템 구현은 반드시 현재 존재 하는 운영체제와 아주 밀접한 관련이 있다. 이 외에도 앞서 언급된 메타 데이터의 예처럼 파일 시스템은 사용자 데이터를 저장하는 것을 관리하는 자료구조를 관리하는데 이 자료구조는 일부를 제외하고 기본적으로 자신들이 관리하는 블록 디바이스 상에 존재하기 때문에 이들을 관리하는 것도 파일 시스템의 특징 중 하나이다.

앞서 언급한 여러 가지 기능/비기능성 요구사항을 만족 시키고 모듈들을 분리하여 사용하기 위해서 가장 많이 사용 되는 아키텍처 방식이 레이어드(Layered)아키텍처이다. 이전 칼럼에서 레이어드 아키텍처의 특징과 간략한 소개는 한적이 있으므로 파일 시스템을 한 레이어로 봤을 때 이 안에서 다시 각 기능들을 통상적으로 어떻게 나누어 설계하는지 살펴보자.

<그림 1 파일 시스템 드라이버의 일반적 레이아웃(layout)>

Window NT커널 내에서 동작하기 위해서는 NT 커널의 시스템 인터페이스와 함께 파일 시스템이 잘 조화를 이루도록 설계되어야 한다. 요구사항 분석에서부터 설계된 파일 시스템, 그 자체로만도 구현이 복잡하고 유지보수가 어려워지는 경향이 있는데 만약 이러한 파일 시스템을 그대로 NT 커널에 붙이려고 한다면 기능 구현 및 유지보수가 훨씬 어려워진다. NT 커널의 시스템 인터페이스들은 단순히 API수준을 사용하는 것과 달리 운영체제의 행동과 특성에 따라 API의 사용순서, 자료구조 운영 등이 복잡하므로 이러한 특성과 파일 시스템 자체 기능을 하는 코어 사이에서 이를 완충 해주는 작업을 하는 레이어가 필요한데 이런 작업을 베니어(Veneer)가 처리한다. 베니어는 상위레벨의 시스템 인터페이스를 변환하여 실제 파일 시스템에게 기능/비기능적 요구를 지시 할 수 있게 하는 기능을 한다. 코어는 이런 베니어가 변경하여 내려주는 파일 시스템으로서의 요구사항을 만족 시키고 블록 디바이스에 존재하는 실제 데이터들을 관리하는 역할을 한다. 마지막으로 블록 디바이스 인터페이스 레이어는 하위 레벨의 기존 디스크나 네트워크 드라이버와의 조율을 해주는 역할을 한다. 중요한 것은 베니어 레이어의 역할이 NT 커널 내의 파일 시스템에서는 매우 중요하다는 것이다. 드라이버를 한번이라도 개발을 해본 사람은 반드시 겪었을 시스템 패닉이나, 운영체제의 오동작들은 파일 시스템 내의 기능/비기능의 구현보다도(실제 코어들은 시뮬레이션을 통해서 충분히 검증 되어 올라오는 경우가 더 많다) NT 커널을 잘 이해하지 못하고 작성하여 베니어의 기능을 충실히 못했을 가능성이 더 많이 존재 한다.

NT계열을 파일 시스템 구현을 포함하여 대부분의 파일 시스템들은 아래와 같은 구조로 위치한다.

<그림 2 NT커널에서 파일 시스템의 위치>

그림 2에서 표시된 정보의 흐름, 1,2,3 은 파일 시스템의 기본 기능이라기보다 베니어의 기능으로 볼 수 있다. 우리는 Windows NT 커널에서 코어와 관계 없이 현재 파일 시스템 드라이버의 기능을 수행할 수 있는 베니어 개발에 초점을 맞출 것이다. 따라서 블록 디바이스로부터의 데이터를 실제 인출, 배열, 조작등에 대한 부분은 언급 하지 않는다. 이제까지 칼럼에서 누차 언급 되었듯이, NT I/O 매니저,캐시 매니저, 가상 메모리 매니저들과 함께 상호 작용을 이해하고 머릿속에 그려보는 것은 아주 중요하다. 이것은 우리가 상업적인 파일 시스템이나 필터, 플러그형태의 소프트웨어를 Windows NT 커널아래 스스로 자신의 기능을 가지는 네이티브(Native) 파일 시스템의 기본 조건이다.

심플 파일 시스템 드라이버(Simple File System, SFS)

우리가 앞으로 구현할 SFS는 앞서 언급 된 것처럼 베니어 구현이슈를 주로 다룬다. 파일 시스템을 개발, 설계하는데 있어서는 아주 많은 설계 이해관계의 충돌, 그리고 비기능적 요구사항의 선택 등의 절차들이 필요하다. 예를 들어서 보안성을 높이기 위해서는 보안모듈에 초점을 맞춘 파일 시스템과 메타 데이터들의 배열구조를 생각 해봐야 할 것이고, 병렬성을 최대화 하는 파일 시스템을 원한다면 각 데이터들의 동기화, 그리고 블록 디바이스의 병렬처리 등에 큰 관심을 쏟아야 할 것이다. 반대로 만약 우리가 현업에서 적은 인력과 빠른 솔루션 확보를 강요당한다면 병렬성을 최대한 줄이는 설계방식을 선택 해야 할 것이다. SFS는 이러한 설계 이슈, 그리고 상업적 파일 시스템으로서의 제공 기능에 대한 설계를 다루지 않으므로 이 SFS가 실제로 여러분이 현업에서 만들 사용 파일 시스템 전체를 구현해주지는 않지만, 여러분이 Windows NT 커널아래에서 안정적이고 정상적으로 동작하는 파일 시스템을 구현하는데 있어서 뼈대를 제공할 것이다.

베니어로서의 SFS구현 시 메모리 관리는 매우 중요한 문제이다. 일반적으로 다른 인터페이스를 조율하는 래핑(Wrapping)모듈은 서로 다른 파라미터를 변경하고 조율하기 위해 메모리 할당 및 복사가 많이 이루어진다. 우리가 구현할 SFS를 비롯하여 필터 드라이버등과 같은 모든 커널 드라이버는 메모리 할당문제를 염두에 두고 있어야 한다. 우리는 SFS뿐만 아니라 모든 드라이버 개발에 있어서 효율적인 메모리 관리가 중요한 목표 중에 하나라는 것을 잊으면 안 된다. 만약 독자가 구현하는 파일 시스템 드라이버가 비페이징 영역의 메모리를 요구한다면 반드시 해당 드라이버가 동작 시에 메모리 사용량을 측정하여 이를 최소화 할 수 있도록 노력해야 한다. 아무리 우리가 메모리를 비페이징 영역이나 페이징 영역에 잘 분리하여 메모리를 할당 하였다고 하여도 페이징 자체가 매우 비싼 동작이기 때문에 최소화 자체에 많은 신경을 써야 한다. 빈번한 페이지 폴트나 TLB 폴트는 우리가 작성하는 파일 시스템 드라이버뿐만 아니라 전체 파일 시스템에서 심각한 성능 저하를 보이게 한다.

레지스터 사용

대부분의 파일 시스템 구현에는 실제 코드 이외에도 많은 수의 키와 Windows NT 레지스트리에 값 개체를 생성 해주어야 한다. 우리는 SFS 파일 시스템 드라이버를 위해서 로컬머신쪽 레지스트리에 HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SFS라는 이름으로 키를 등록한다.

<표 1 Simple File System, SFS관련 레지스터 설정>

SFS와 관련된 레지스트리 설정을 마쳤다면 이벤트로드에 대한 값을 설정한다.

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\ServiceS\EventLog\System\SFS 에 등록하는 이 키는 NT 이벤트 로그(Event Log)를 이용한 SFS를 통하여 이벤트 로그를 보여주는 어떠한 어플리케이션이라도 메시지를 확인할 수 있도록 해준다.

<표 2 이벤트 로그 관련 레지스터 설정>

SFS 드라이버 자체에는 유용하지 않을 지 모르지만 SFS의 제작자, 드라이버의 부가설명이나 기타 정보들을 남겨 둘 수 있는 키도 있는데 이 키는 HKEY_LOCALJVIAMACHINE\SOFTWARE\SFS 위치에 기록이 가능하다.

< 표 3 기타 파일 시스템 정보 관련 레지스터 설정>

소프트웨어의 버전을 관리할 때는 하나의 정보만으로 유용하지 않을 경우가 있는데 이러한 경우를 위해서 CurrentVersion에는 VirsionMajor, VersionMinor, VersionBuild, InstallDate와 같은 서브 키를 이용해서 이를 기록 할 수 있다.

자료구조

어떤 파일 시스템 드라이버를 설계하던 간에 그 파일 시스템이 사용할 자료구조를 정의 해야 하는데 일반적으로 이러한 자료구조는 어디에 상주하는가에 따라 크게 두 가지로 분류 할 수 있다. 첫째는 디스크상에 자료구조를 두는 것으로 파일 시스템드라이버가 이 자료구조를 필요로 하거나 갱신 해야 할 때마다 이를 디스크상에서 읽어야 하며 이에 대한 주소를 모두 기억하고 있어야 한다. 이를 온-디스크(On-disk) 자료구조라고 부르며 이와 반대로 메모리상에 올려두고 빠른 엑세스를 하도록 하는 자료구조를 인-메모리(In-memory) 자료구조라고 부른다. 만약 파일 시스템 드라이버 개발자중에서 특정 드라이버의 자료구조의 유형과 커널 콤포넌트를 이해야 하는 경우라면 (사실 대부분이 그렇지만) 이 자료구조가 인-메모리인지 온-디스크인지에 따라 이를 다루는 방법이 상이하므로 이에 대한 이해가 필요하다.

사실 이상적인 상황이라면 운영체제를 설계 함에 있어서 특정 파일 시스템과는 독립적으로 온-디스크 자료구조와 이에 대한 주소 레이아웃을 가도록 설계 되어야 한다. 온-디스크 자료구조뿐만 아니라 인-메모리 자료구조 또한 어떤 파일 시스템 드라이버든 간에 해당 운영체제 위해서 해당 파일 시스템 드라이버가 제공하고자 하는 기능을 쉽게 구현하기 위해서 어떤 의존성 없이 제공되어야 하지만, Windows NT를 포함하여 비상업적 운영체제는 물론이고 상업적으로 잘 설계된 대부분의 운영체제 또한 이러한 이상적인 환경을 지원 하지 못한다. 다만, Windows NT의 경우, 커널이 파일 시스템에 관련된 자료구조에 특별한 관여를 하지 않는 수준의 설계를 가지고 있다. 따라서 파일 에 대한 정보들을 기대하고 있는 사용자의 경우, 만약 여러분이 제작한 파일 시스템 드라이버가 디스크 위에 파일 이름, 접근 시간, 마지막 쓰여진 시간 등의 특성을 관리하지 않는다면 해당 사용자는 매우 혼란스러울 수 밖에 없다.

Windows NT와 관련된 마이크로 소프트사의 파일 시스템들은 각 파일 시스템마다 각기 다른 특징들을 가지고 있다. 예를 들면 FASTFAT의 경우 접근 제어 리스트(Access Control List)에 저장되는 파일의 보안 정보등을 전혀 제공하고 있지 않기 때문에 파일에 대한 다중 링크, 파일 압축 또는 시스템 실패 시 복원을 위한 파일 복원 정보들을 전혀 가지고 있지 않다. 반면 NTFS의 구현에서는 앞서 언급된 모든 기능들이 전부 구현 되어 제공되고 있으며 이에 대한 정보들을 모두 온-디스크 자료구조에 담아두고 있다. 이러한 온-디스크 자료구조는 FAT 계열의 파일 시스템과 완전히 다른 특성을 보여준다.

앞선 섹션에서 언급 되었듯이 우리가 파일 시스템 드라이버를 구현하고자 하는 목적은 Windows NT 기반 아래서 특정 파일 시스템의 기능과 관계 없이 베니어와 같은 형태의 파일 시스템 드라이버를 논의 하고자 하는 것이므로 특정 파일 시스템의 제작에 대한 온-디스크 자료구조에 대해서는 더 이상 언급을 하지 않을 것이다. 다만, 파일 시스템 개발자가 알아 두어야 할 것은 파일 시스템 개발에서 온-디스크 자료구조를 사용 하기 위해서는 해당 자료구조를 블록 디바이스로 입출력 시키기 위해서는 다양한 자료구조를 단지 기능에 의한 추상화수준으로 자료구조를 설계 하면 안되고 블록디바이스의 입출력 사이즈, 접근성 등을 고려하여 레이아웃을 잡아야 한다는 것이다. 다시 돌아 와서, 우리의 목적에 맞도록 파일 시스템 드라이버가 반드시 정보를 유지해야 하고 그것을 관리하기 위한 자료구조를 구현하기 위해 우리는 인-메모리 자료구조에 좀 더 초점을 맞추도록 한다.

비록 Windows NT에서 파일 시스템 드라이버를 설계, 제작하기 위해 문서화 해놓거나 권장하고 있는 자료구조들은 없지만 우리는 파일 시스템 드라이버를 구현 하기 위해서 FCB로 불리는 파일 컨트롤 블록(File Control Block)과 CCB로 불리는 컨텍스트 컨트롤 블록(Context Control Block) 자료 구조 두 가지에 대해서는 반드시 고려 해주어야 한다. FCB는 온-디스크 자료구조를 시스템 메모리 상에 올려 놓은 것을 참조 할 수 있는 유일한 자료구조이다. 예를 들면 디렉토리, 파일, 자료구조의 볼륨, 그리고 우리가 작성할 파일 시스템 드라이버가 관리하는 자료구조인 오브젝트들은 FCB에 의해서 참조된다. 만약 독자가 UNIX 구현에 대한 배경 지식이 있다면 메모리에 상주하면서 파일을 표현하는 자료구조로서 vnode가 Windows NT의 파일 컨트롤 블록, FCB와 유사하다는 것을 알 수 있을 것이다. vnode와 FCB 두 자료 구조 모두 디스크상에 파일을 관리하고 참조 할 수 있도록 정보를 담고 있는 메모리상에 상주한다.

반면 컨텍스트 컨트롤 블록, CCB는 열려 있는 파일의 온-디스크 오브젝트들을 관리하고 참조 할 수 있는 정보들을 가지고 있기 위해서 파일 시스템에 의해서 생성되고 조작되는 자료구조이다. 예를 들어서 사용자가 특정 파일에 대해서 열기에 대한 동작을 수행하면 운영체제는 해당 파일에 대해서 열기를 시도하고 만약 성공하게 되면 해당 파일에 대한 제어권을 사용자에게 넘겨준다. 해당 제어권(핸들, handle이라고도 불림)을 관리하기 위해 Windows NT의 파일 시스템들은 컨텍스트 컨트롤 블록을 생성하고 관리 해야 한다. 컨텍스트 컨트롤 블록은 각 파일 마다 하나 각각 존재하는 오브젝트 핸들로 파일 시스템에 의해서 유일하게 관리 되기 때문에 파일 시스템 드라이버 개발자(특히 특정 레거시 파일 시스템을 제작하는 개발자)들은 컨텍스트 컨트롤 블록을 어떻게 관리 할 것인지에 신경을 써야 한다.

메모리에 상주시켜야 하는 파일 관리 및 참조에 관련된 일련 정보

NT I/O 매니저 컬럼에서 언급 했듯이 I/O 매니저가 열기 동작에 대하여 적절한 파일 오브젝트를 전달 해주는데 이를 통하여 파일 컨트롤 블록, 컨텍스트 컨트롤 블록, 디바이스 오브젝트 등의 유용한 자료구조에 접근 할 수 있다. 파일 시스템 개발자는 지금부터 소개 되는 구조체를 생성하거나 또는 초기화, 플래그 변경에 대해서 다른 어떤 것들보다 큰 책임이 있다. 따라서 각 구조체간의 관계 등을 숙지 해 놓는 것이 좋다. 큰 그림이 그려지면 이 자료구조들을 어떻게 사용 할 것인지, 또 프로토콜을 맞추기 위해 어떤 흐름을 지켜줘야 하는지, 템플릿에 가까운 코드들을 일일이 작성 해주어야 하는 지 훨씬 이해하기 쉬울 것이다.

물리 디바이스 오브젝트(Physical Device Object)

자료구조 스택에서 가장 아래 존재하는 디바이스 오브젝트부터 살펴 보자. 물리 디바이스 오브젝트는 디바이스 오브젝트는 크게 아래와 같은 DeviceType들의 조합으로 이루어 진다.

1. FILE_DEVICE_DISK
2. FILE_DEVICE_VIRTUAL_DISK
3. FILE_DEVICE_CD_ROM

이 자료 구조는 IoCreateDevice()를 통해서 생성되는데 일반적으로 물리 또는 가상 디스크 오브젝트를 관리 할 때 사용한다. 생성시간에 VPB라고 불리는 볼륨 파라미터 블록(Volume Parameter Block) 자료구조가 생성되고 NT I/O 매니저에 의해 미디어 타입이 할당된다. VPB 자료 구조 초기화 시에 VPB_MOUNTED 플래그는 빈 상태의 값을 가지게 되는데 이는 해당 물리 디바이스에 논리 볼륨이 할당 되지 않았다는 것을 의미한다.

<그림 3 파일 시스템 관련 자료구조간의 관계도>

이는 이후 파일 시스템 구현 시에 (필요하다면) 해당 물리 디바이스에 논리 볼륨을 마운트하기 전에 이를 검증하기 위해 사용되기도 한다. 다시 말해 마운트 할 것인 아닌지를 이 플래그를 통해 확인 할 수 있다는 것을 의미하기도 하고 나중에 다음 논리 볼륨 디바이스 오브젝트를 엑세스 할 수 있게도 해준다.

논리 볼륨 디바이스 오브젝트(Logical Volume Device Object)

그냥 볼륨 디바이스 오브젝트라고 불리기도 하는데 이는 마운트된 논리 볼륨 정보의 인스턴스라고 보면 된다. 볼륨 디바이스 오브젝트는 파일 시스템 구현 시에 개발자에게 의해서 생성된다. 마운트라는 것은 블록 디바이스에 있는 자료를 사용자가 접근하기 전에 일반적으로 대부분의 운영체제에서 행해지는 동작 중 하나이다. 개발자 입장에서 본다면 볼륨을 마운트하는 동작은 파일 시스템 드라이버에게 해당 블록 디바이스에 계속되는 접근을 위한 준비의 기회를 주는 것이라고 보면 된다.

따라서 파일 시스템이 볼륨을 마운트 하는 대부분의 동작은 파일 시스템 그 자체 또는 특성에 따라 모두 달라 질 수 있으며 이 기간 동안에는 운영체제의 간섭을 최소화 하고 있다. 일반적으로 이 시간에 가장 먼저 하는 수행 하는 것이 온-디스크 구조체를 확인 하여 해당 블록 디바이스 할당된 다른 파일 시스템이 있는지를 확인 하는 과정을 거친다. 이 과정을 거치고 나면 파일 시스템은 볼륨 크기, 루트 디렉토리의 위치, 여유 블록의 사상 정보, 할당된 클러스터의 사상정보 같은 기본이 되는 볼륨 정보를 읽고 볼륨 엑세스를 하기 위해 필요한 자료구조들을 인-메모리로 보관하기 위해 필요한 메모리 사이즈를 확보한다. 논리 볼륨 마운팅의 일부로서 대부분의 운영체제시스템에서 정의된 자료구조를 생성, 초기화 시키기를 권장하고 I/O 메니저 구조체와 인-메모리 구조체로서의 존재하는 마운트 볼륨의 정보들의 관계를 정의하도록 배려해준다. 따라서 파일 시스템 설계자들은 반드시 파일 시스템 구현을 할 플랫폼의 운영체제 요구사항을 숙지 해야 함은 물론이고 올바른 자료구조를 적시에 할당 해주어야 한다.

Windows NT에서는 I/O 매니저가 생성된 논리 볼륨과 함께 물리 블록 디바이스 또는 미디어(Media)의 정보를 가지고 있는 디바이스 오브젝트를 요구하는데 해당 디바이스 오브젝트가 정상적으로 초기화 되었는지 등을 VPB를 통해서 알 수 있다. 다시 말해 각 볼륨 디바이스 오브젝트는 논리적으로 물리 디바이스 오브젝트를 가지고 있는 VPB 자료구조를 사용하여 물리 디바이스 오브젝트와 연관 시킨다. 앞서 언급 되었듯이 이 관계는 해당 물리 디바이스 오브젝트에 대해 I/O 매니저가 처음 열기 또는 생성 동작을 할당 받는 볼륨 마운트 시점에서 생성된다.

이러한 관계를 코드상에서 명확히 설정 해주는 것과 이에 대한 논리적 볼륨 디바이스 오브젝트는 파일 시스템 개발자에게는 매우 중요한 과정이다. 왜냐하면 우리가 만드는 파일 시스템 드라이버에 의해서 이 동작들이 수행 되어야 하며 사용자의 생성, 열기에 대한 디바이스 오브젝트와 타겟 드라이버를 결정하는 것은 앞서 언급한 과정을 통해 I/O 매니저에 의해 관리 되기 때문이다.

이 과정이 중요한 만큼 이에 대한 절차를 그림 4로 정리 해보았다.

<그림 4 마운트 초기 작업 의사 결정도>

마운트의 특정 작업이 끝나고 나면 VPB내에 DeviceObject필드를 포인터로 사용하여 논리 볼륨 디바이스 오브젝트에 접근 할 수 있게 된다. 따라서 이후에는 I/O 매니저가 생성 또는 열기 작업을 마치기 위해 필요한 인스트럭션(Instruction)등을 수행 할 수 있다.

다음 칼럼에는

파일 시스템 컨셉과 코드에 대한 정의를 통해서 우리가 만들어야 하는 파일 시스템의 베니어 레이어의 역할, NT 커널 아래서의 파일 시스템의 위치, 레지스터 설정들을 이해 할 수 있었을 것이다. 이 아이디어들은 본격적으로 파일 시스템 구현에 들어감에 있어서 파일 시스템 드라이버가 해야 하는 특정 자료구조의 설정 및 플래그 변환 등의 논리적 순서를 이해하는데 큰 도움이 될 것이다.

다음 칼럼에서는 파일 시스템 드라이버가 반드시 책임져야 하는 자료구중 이번 칼럼에서 소개 되지 못한 것들을 소개하고 의사코드를 작성하는 시간을 가져 볼 것이다.

References

Rejeev Nagar, "Windows NT File System Internals": A Developer Guide, O'Reilly 1998

P. B. Kruchten."The 4+1 View Model of architecture."

David Garlan and Mary Shaw January 1994 "An Introduction to Software Architecture"

Kernel Source http://reactos-mirror.googlecode.com/svn

Kernel Source http://nuwen.net

NT 가상 메모리 매니저와 파일 시스템

Communication between Virtual Memory Manager and File System

가상 메모리 매니저를 다루는 이유는 결국 파일 시스템 드라이버 입장에서 가상 메모리 매니저의 동작을 이해하고 이를 적절히 운용하여 시스템의 성능을 올리기 위해서이다. 대부분의 운영체제에서 가상 메모리 매니저와 파일 시스템간의 정보를 정의 하고 있으나 실제 NT에서는 가상 메모리 매니저의 코드를 볼 수 없기 때문에 어떠한 인터페이스를 통해서 기존 운영체제의 컨셉을 이용하고, 시스템을 조율 할 지가 난해 할 수 있다. 파일 시스템 드라이버 개발자는 가상 메모리 매니저에 의해서 운용되는 사상된 메모리 이미지(Mapped Memory Image)나 가상 메모리 매니저만이 오직 조작 할 수 있는 물리 메모리 주소 영역을 이해하고 파일 시스템 드라이버가 동작하는 시스템 가상 주소 공간을 운용하기 위한 동작을 이해 해야 할 뿐만 아니라, 두 모듈간의 의존성을 파악하여 시스템을 설계 해야 한다.

정명수 |

필자는 지난 3년간 삼성전자에서 플래시 메모리와 관련된 연구와 임베디드 소프트웨어, 커널 드라이버 등을 개발 했었다. 현재는 조지아 공대(Georgia Institute of Technology) 컴퓨팅 칼리지에 재학 중이다. 글쓰기를 매우 좋아하며 학부시절에는 객체 지향 패러다임을 통하여 해석하는 프로그래밍 언어론에 관심이 있었으나 실무과정을 거치면서 컴퓨터 아키텍처로 관심사가 옮겨졌다. 최근에 관심 있는 분야는 운영체제, 파일시스템, 실시간 스케줄링 등이다.

NT의 가상 메모리 매니저의 마지막 칼럼으로서 메모리 매니저가 파일 시스템 드라이버나 커널 드라이버에게 노출 시켜 놓은 함수나 루틴들을 알아보고 그 안의 동작을 이해하도록 한다. 이러한 가상 메모리 매니저의 API들은 대부분 파일 시스템 드라이버 개발자에게 노출 되어있고 매우 중요한 역할을 하고 있으나 실제로 잘 문서화가 되어 있지 않기 때문에 파일 시스템 드라이버 개발자가 간과 하기 쉽다.

하지만 현재 파일 시스템 드라이버가 운용되는 시스템 가상 주소 공간과 메모리 할당, 그리고 사용자 모드의 어플리케이션과 통신을 위해서 어디까지가 파일 시스템의 영역이고 어디까지가 가상 메모리 영역까지 인지를 판단하여 시스템의 성능을 향상하도록 설계하기 위해서는 가상 메모리 매니저의 내부와 이를 이해하여 파일 시스템 정책을 적절히 추가 해야 한다. 이번 칼럼에서는 메모리 페이징을 위한 서로 간의 영역과 역할 차이, 그리고 운영체제의 핵심이 되는 페이지 폴트 핸들링, 마지막으로 파일 시스템과의 교류를 위한 여러 가지 가상 메모리 매너저의 API들을 소개한다.

MPW, 수정되거나 사상된 페이지 쓰기 스레드

이전에 컬럼에 언급 되었듯이, NT 가상 메모리 매니저 (VMM, Virtual Memory Manager)는 물리적 메모리 제약과 관계 없이 각 프로세스마다 자신의 독립된 가상의 메모리 공간을 제공하기 위한 태스크(Task)를 가지고 있다. 이 태스크를 위해서 NT VMM은 메모리에 존재하는 페이지 데이터와 정보들을 블록 디바이스(Block Device)로 내보 내거나(스왑 아웃, Swap out이라고도 불린다.) 블록 디바이스로 내보냈던 데이터를 다시 메모리로 불러 들어오는 동작(스왑 인, Swap in)을 지원 해야 한다. 페이징(Paging)이라고 부르는 시스템에서 수행 되는 프로세스에 대해서 모두 균등하게 적용 된다. 적은 물리 메모리를 가지고서 상대적으로 큰 메모리를 사용자에게 보여주기 위해서는 가상 메모리에 할당된 물리 메모리의 양에 한계가 발생할 때 앞서 말한 스왑 인,아웃 작업을 통해 새로운 페이지 프레임(Page Frame)을 할당 받아야만 한다. 따라서 이런 작업을 위해 NT VMM은 자동적으로 데이터가 쓰여진 페이지(더티 페이지, Dirty Page)나 수정된 데이터를 블록 디바이스로 플러시(Flush)하게 된다. 이렇게 페이지 프레임 안에 수정된 데이터는 크게 두 가지 방법으로 블록 디바이스로 스왑 아웃 된다. 첫 번째는 하나에서 열 여섯 개의 페이지 파일을 통해서 수정된 데이터를 쓰는 작업을 통해 스왑 아웃 하는 것이다. 만약 페이지 파일이 사상된 섹션 오브젝트(Mapped Section Object)로 할당 되어 있다면 수정된 데이터는 디스크상에 이름이 있는 파일 형태로 저장된다. 만약 페이지 프레임이 디스크로 플러시 되지 않는다면 NT VMM은 페이지 프레임을 재 사용 할 수 없고 이는 데이터 손실로 이어진다.

메모리 사용이 요청에 대해서 언제든지 서비스 할 수 있도록 NT VMM은 항상 사용 가능한 충분한 램(Ram)을 가지고 있어야 한다. 이를 위해서 NT VMM은 일정량의 사용 가능한 페이지 프레임을 고정적으로 보유하고 있다. 따라서 이 페이지 프레임은 NT VMM이 페이지 할당 시에 이를 사용 할 수 있도록 어떤 수정된 데이터도 가지고 있지 않아야 한다. 먄약 VMM이 이러한 가용 가능한 페이지 프레임들의 영역을 소유하고 있지 않다면 페이지 프레임을 필요하는 대부분의 프로세스가 블록 되게 된다. 그 프로세스들의 수정된 데이터를 위한 페이지 프레임을 확보 하기 위해 미리 확보된 가용 공간을 페이지 프레임을 사용 하는 것이 아니라 필요 즉시에 스왑 아웃을 하여 이를 확보 하기 때문에 스왑 아웃 시에 블록 디바이스로 접근이 발생 함으로서 이에 대한 지연시간이 모두 프로세스에게 보이게 되기 때문이다. 대부분 이해하고 있듯이 현재까지 컴퓨터 아키텍처에서 속도상 가장 병목을 보이는 것이 I/O이기 때문에 프로세스의 스왑 아웃 작업이 그대로 사용자에게 보여지게 된다면 큰 문제가 될 수 있다.

따라서 NT VMM은 수정되거나 사상된 페이지 쓰기(Modified and Mapped Thread, 이후 MPW로 호칭)에 대한 스레드를 적어도 두 개 이상 소유하고 있다. 이 중에 하나는 비동기적(Asynchronous)으로 사상된 페이지를 페이지 파일에 쓰기 위해서 생성된다. 수정된 페이지 프레임을 쓰든지 아니면 사상된 페이지를 쓰든지 그 기본적인 기능은 동일 하기 때문에 보통은 이 둘을 하나의 통일된 용어로 쓰는 것이 일반적이다. 이 스레드는 앞서 언급 된 병목 현상과 디스크에 대한 지연시간을 감추기 위한 것이기 때문에 항상 NT VMM이 요청에 따라 즉각적으로 할당할 수 있는 페이지 프레임을 보유하도록 해주며 이와 중첩적으로(Overlapped) 블록 디바이스로 데이터를 쓴다. MPW 스레드 각각은 이러한 방법을 통하여 높은 시스템 포퍼먼스를 확보하기 위해 실시간 스레드로 정의 되는데 NT에서는 이를 LOW_REAL_TIME_PRIORITY 보다 한 단계를 더 높은 우선순위를 가진다.

NT VMM은 데이터를 블록 디바이스로 플러시 하기 위해서 앞서 언급된 비동기 쓰기를 사용하는데 이때 I/O 매니저의 IoAsynchronousPageWrite()를 참조한다. 이API 호출은 I/O 매니저에 의해서 해당 사상된 페이지 파일이나 이름이 붙여진 형태의 파일을 가진 디스크 볼륨을 관리하는 파일 시스템에게로 바로 전달 된다. 파일 시스템 개발자는 이런 면 때문에 개발 당시 I/O를 좀 더 세분화 하여 관리 할 필요가 있다. NT VMM에 의해서 수정되거나 사상된 페이지를 플러시할 때 생성된 입출력은 다른 일반적인 입출력과 구분 할 수 있도록 IRP_PAGING_I/O의 파라미터를 가는 요청으로 수행된다. 이 입출력 요청 패킷(IRP, I/O Request Packets)에는 페이징에 대한 정보 말고도 IRP_NOCACHE 플래그도 설정되어 있다. 파일 시스템 개발자가 관심을 가져야 하는 것은 페이징 I/O 쓰기 요청을 처리하면서 절대 다른 페이지 폴트를 발생시켜서는 안된 다는 것이다. I/O 매니저는 다른 케이스의 입출력과 페이징에 대해서 다른 형태로 페이지 쓰기 형태를 관리 하기 때문이다. I/O 매니저는 페이징 I/O의 비동기 쓰기의 커널 APC를 정상적으로 마무리하기 위하여 MiWriteComplete() 루틴을 사용한다.

페이지 폴트 핸들링(Page Fault Handling)

NT VMM 물리 메모리 주소공간에 표현 되지 않는 가상 메모리의 컨텐츠를 참조하는 모든 케이스를 처리 해야 하는 책임이 있다. MMU (Memory Mapping Unit)와 같은 하드웨어가 일반적으로 가상 주소와 물리 주소를 번역하긴 하지만 NT 커널에서는 MMU가 이전 컬럼에 언급된 PTE가 메모리에 없는 경우 이 문제를 해결 하기 위에 직접적으로 매핑 정보에 접근 하는 것이 아니라 VMM에게 해당 문제를 전달 하는 것으로 종료 된다. VMM은 페이지 폴트가 발생 했을 때 커널 모드든 유저 모드든 MmAccessFault()라는 함수로 이 제어권을 넘겨 받는다. 다른 NT함수들도 마찬가지 이겠지만 MmAccessFault()는 VMM이 하는 가장 기본이 되는 기능 중에 하나임에도 불구 하고 그 내부 정보를 알기가 매우 힘들 정도로 기술 문서가 부족하다. 따라서 MmAccessFault()의 함수에 대해서 좀 더 이해하는 시간을 가져 보도록 하자.

MmAccessFault()함수는 크게 3가지 종류의 정보를 받아 들일 수 있도록 파리미터를 정의하고 있다. 하나는 페이지 폴트가 일어난 가상 주소 공간에 대한 정보 이고 다른 하나는 현재 페이지 폴트가 일어난 동작(Operation)에 대한 속성을 나타내는 플래그이다. 다시 말해 폴트가 발생한 메모리 페이지가 쓰기를 하다가 일어난 것인지 아니면 읽기를 하다가 일어 난 것인지를 나타내며 일반적으로 FALSE형태가 읽기상태에서 발생 한 것으로 알려져 있다. 마지막으로는 해당 MmAccessFault() 함수가 사용자, 커널 모드 둘 다를 관리 하므로 이를 구분하기 위한 추가 정보가 하나 더 존재 한다.

VMM이 페이지 폴트를 핸들링하기 위해 제어권을 받으면 우선적으로 하는 것이 현재IRQL이문제가 없는 것인지를 확인 하는 것이다. MInAccessFault()함수는 현재 IRQL레벨을 체크하는데 만약 APC_LEVEL보다 높고 페이지 테이블 디렉토리(Directory)와 페이지 테이블 엔트리(Entry)가 유효하지 않은 것이라면 VMM에게 현재 IRQL 레벨을 디버거 정보로 출력하게 한다. 그 다음이 페이지 폴트 문제를 해결 하기 위해 호출 되는 함수는 MiDispatchFault()함수이다. 이 함수는 처음 이야기 하였듯이 VMM이 페이지 폴트의 제어권을 할당 받은 MmAccessFault() 함수가 페이지 프레임을 유효하게 하기 위해 실행 되는 함수이다. 이 루틴은 가상 주소 공간의 상위 2GB인 시스템 주소 공간가 사용자 주소 공간을 접근 하기 위한 전처리 작업들을 수행한다. 페이지 폴트에 관련된 문제들을 해결 하기 위해 좀 더 세부적인 루틴들이 연이어서 호출 되는데 이런 서브루틴들은 폴트가 발생한 주소에 따라 다르다.

만약 폴트가 일어난 주소가 페이지 파일을 기반으로 하고 있다면 MiResolvePageFileFault()함수가 호출 되는데 이 함수는 우선적으로 MiEnsureAvailablePageOrWait() 함수를 이용하여 해당 페이지 파일로부터 데이터를 읽기 위해서 충분한 페이지 프레임을 메모리로 할당한다. 메모리 할당을 마치고 나면 이 MiResolvePageFileFault() 함수는 PTE로부터 읽기 동작이 지정된 해당 페이지 파일을 파악하고 가용 가능한 물리 페이지의 리스트를 가지고 있는 메모리 디스크립터 리스트(MDL, Memory Descriptor List, 메모리 기술자 리스트라고도 불림) 생성한다. MDL이 생성되고 나면 해당 패이지에 대한 메모리 처리가 진행중인 것을 PTE에 기록 하고서 이를 호출한 MiDispatchFault()에게 0xC0033333으로 사전 예약된 상태를 리턴한다. 0xC0033333로 정의 된 상태 값을 리턴 받은 MiDispatchFault()는 I/O 매니저의 API인 IoPageRead()를 사용하여 페이징에 대한 읽기 동작을 수행한다. 앞선 섹션 MPW 스레드에서 언급 했듯이, 파일 시스템 드라이버는 IRP_PAGING_IO와 IRP_NOCACHE 플래그로 먼저 요청사항을 수행 했기 때문에 이번 IoPageRead를 페이징에 관한 읽기 동적으로 수행 할 수 있다. VMM은 페이지 폴트가 일어난 읽기 요청이 모두 끝날 때 까지 기다리고서 요청이 성공적으로 끝나면 해당 프로세스에 대한 워킹 셋(Working Set Model)에 페이지를 추가 한다. 워킹 셋은 NT 커널에서만 적용 되는 것이 아니라 여러가지 운영체제에서 빈번하게 일어나는 메모리 폴트에 의해 운영체제 자체가 제 기능을 못하게 되는 것을 막기 위해서 사용된다.

만약 폴트가 발생한 주소의 PTE가 처리중임을 나타낸다면 MiResolveTransitionFault()를 호출 한다. 처리 중에 있는 페이지는 앞서 언급된 PTE에 기록된 정보를 통해서 알아내는데 이것이 처리중인 경우를 좀 더 상세히 살펴 보면 아래와 같은 세가지 이유가 주를 이룬다.

1. 페이지 프레임이 유효한 정보를 가지고 있음에도 불구하고 해당 페이지가 프리(Free) 페이지 영역에 존재 할 경우.
2. 마찬가지 이유로 페이지 프레임이 유효한 정보를 가지고 있음에도 불구하고 프로세스의 워킹 셋에 의해 수정된 페이지 리스트에 존재 하는 경우.
3. 페이지가 블록 디바이스로부터 읽어오는 중인 경우

MiResolveTransitionFault()가 처리 중에 있는 페이지 정보를 PTE로부터 인출 하고 나면 이 함수는 블록 되고 나서 입출력이 모두 끝나기를 기다리게 된다. 만약 에러가 일어난다면 PTE에 무효(Invalid) 상태로 바꾸고 나서 함수를 정상 리턴 시킨다. 이것은 강제적으로 다른 페이지 폴트에 의해서 해당 PTE가 더 이상 진행 중이라는 상태를 번복해서 저장 하지 않기 위함이다. 이러한 경우가 아니라면 PTE를 유효 상태로 두고 현재 프로세스에 워킹 셋에 이를 추가한다. MInAccessFault() 함수는 메모리 사상 파일이나 공유 메모리 범위에 존재하는 가상 주소 공간이 폴트를 냈을 경우 PPTE(Prototype PTE)와 함께 MiDispatchFault()를 호출 하게 된다. 이 경우 MiDispatchFault()는 MiResolveProtoPteFault() 함수를 호출하여 문제를 처리한다. 만약 사상 파일에 소유된 PPTE메모리로 폴트가 발생한 페이지의 집합을 결정 해야 하는 경우, VMM은 여퍼 페이질을 한번에 처리 하여 시스템 성능을 올리기 위해 MiResolveProtoPteFault() 루틴을 이용하여 MDL을 할당하고 0xC00333333을 리턴 한다. 만약 PPTE가 페이지 파일내에 공유된 메모리를 백업하기 위해 생성 된 것이라면 MiResolvePageFileFault() 루틴이 호출 되는데 이 루틴은 페이징에 대한 읽기 동작을 수행하기 위한 페이지 파일 넘버(PFN)을 결정하고 이를 통하여 읽기에 사용될 MDL 구조체를 생성한 뒤 앞선 상황과 마찬가지로 0xC00333333을 리턴 한다. 만약 PPTE가 사용 중이라면 이 루틴은 MiResolveTransitionFault() 서브 루틴을 자체적으로 호출하여 이를 처리 할 것이며 만약 '0'으로 채워진 제로페이지를 요구하는 경우라면 MiREsolveDemandZeroFault()를 호출 할 것이다.

이제까지 언급된 서브 루틴들이 적절히 호출 되고 성공적으로 완료를 하였다면 MiResolveProtoPteFault() 함수는 PPTE의 데이터들을 반영하는 PTE를 만들게 된다. 한번 프로세스를 위한 PTE를 생성하고 나면 페이징에 대한 읽기가 가능한 해당 PTE는 PEN 데이터 베이스 엔트리에 추가 되게 된다. 간혹 NT VMM은 페이지 폴트에 대한 응답으로 '0'으로 채워진 제로 페이지 프레임이 필요한 경우가 있는데 이런 대부분 디스크 상에 파일을 확장하거나 또는 새롭게 할당된 영역에 특정 스레드가 접근 하는 경우다. 이런 경우는 MiDispatchFault() 루틴이 가용가능한 페이지 프레임의 리스트로부터 제로 페이지 프레임을 할당 해주는 MiResolveDemandZeroFault() 서브 루틴을 호출 하는 것으로 해결 될 수 있다. 만약 제로 페이지 프레임을 할당 하기 위한 가용 가능한 페이지가 없다면 MiResolveDemandZeroFault() 함수는 0xC7903004를 리턴하여 가용 가능한 페이지 프레임을 생성 하도록 하는 페이지 폴트를 발생시켜 이를 해결 한다.

지금까지 기술 되었던 것처럼 NT VMM은 시스템 메모리에 기술 되지 않는 페이지를 폴트를 발생 시킴으로써 MMU가 가상 주소와 물리 주소를 번역 할 수 있도록 하고 있다. 만약 우리가 파일 시스템을 드라이버에서 페이지 폴트와 관계된 작업을 수행할 때 IRQ 레벨을 DISPATCH_LEVEL이나 그 이상의 우선순위를 가지는 일련의 동작을 만들었다면 각별한 주의를 해야 한다. VMM은 언급된 IRQL 레벨에서 페이지 폴트를 만족 시켜주지 못하기 때문이다. 우리에게 비 페이징 영역과 페이징 영역을 구분하여 할당 해야 한다면 어떤 기준으로 할 것인가? 라는 질문을 누군가 던진다면 단순히 그 페이지가 빈번하게 동작하거나 중요한 메타(meta)데이터를 가지고 있기 때문이라고 답할 수 없다. 이번 컬럼에서 알 수 있듯이 IRQL 레벨이 DISPATCH_LEVEL에서 수행되거나 또는 그 이상에서 수행 되는 경우 반드시 시스템 메모리를 비 페이징 영역으로 고정 시키고 해당 페이지에 접근 해야 한다.

파일 시스템 드라이버와 상호작용

NT VMM과 파일 시스템 드라이버는 서로에게 여러 가지 기능을 의존 하고 있다. 이러한 의존성은 소프트웨어의 엔트로피(Entropy)를 높이는 역할을 하기 때문에 일반적으로 소프트웨어 공학에서 이를 회피 하려고 하지만 가상머신을 통한 운영체제가 아닌 이상 가상 메모리 관리와 폴트 시 파일 시스템의 서로간의 협업은 반드시 필요하기 때문에 두 모듈간의 의존성은 불가 피하다. 특히 NT 커널상에서는 파일 시스템이 페이지 파일 I/O와 메모리 사상에 의한 오브젝트를 처리 해주기 때문에 VMM이 파일 시스템에 의존 할 수 밖에 없고 파일 시스템 입장에서는 NT VMM이 시스템 드라이버에서 발생한 페이지 폴트를 처리뿐만 아니라 파일 시스템이 사용하는 캐시처리 메모리 할당등의 메모리 처리 문제 때문에 VMM에 의존 적일 수 밖에 없다. 이것은 기능상의 모듈을 위반하는 것이 아니라 오히려 부분적 순서(Partial Order) 상의 레이어드(Layerd) 아키텍처의 최대한 지키면서 각자 해야 할 일을 명확히 정의 한 것으로 볼 수 있다.

이런 두 모듈간에 협조 속에서도 서로 침범 하지 않아야 하는 것들이 있는데 파일 시스템 드라이버 입장에서는 일부 데이터에 대하여 메모리를 명시적으로 조절 하는 것이나 모듈 자체가 VMM의 기능에 의해서 더럽혀지는 것을 막아야 하는 부분이다. NT 플랫폼(Platform)에서 파일 시스템은 VMM이 제공하는 메모리 공간의 시스템에 동적으로 올라가는 실행 이미지이기 때문에 기본적으로 파일 시스템과 다른 기타 커널 드라이버들은 페이징 되지 않는다. 다시 말해 이러한 모듈들이 올라가 있는 동안 이 드라이버들은 램상에 상주하게 된다. 물론 커널 드라이버와 관련된 전역 메모리 부분들도 기본적으로 스왑 아웃 되지 않는 것을 기본으로 한다. 만약 우리가 이런 기본 사항을 변경 하기 위해서는 컴파일러에게 시스템 성능 향상을 위해 스왑 아웃을 명시적으로 알려 줄 수 있다. #progma alloc_text() 라는 전처리로 컴파일러에게 전달 할 수 있으며 첫 번째 매크로 인자로서는 페이징 가능한 코드를 알려주는 4자의 유일한 스트링을 정의 해주어야 한다. 두 번 째 인자는 루틴의 개수를 알려 주는 것이다. 이렇게 전처리를 통해 컴파일러에게 명시적으로 자신의 코드의 특정 부분이 페이징이 가능하다고 알려 줄 수도 있지만 mmLockPageableDataSection()이나 LmLockPageableCodeSection() 같은 함수를 사용하여 동적으로 코드나 데이터를 페이징으로 막기 위해서 락(Lock) 시킬 수도 있다.

사용자 스레드들과 유사하게 파일 시스템과 커널 드라이버도 VMM의 상호 참조 구조 안에서도 동적 메모리를 할 당 할 수 있다. 전형적으로 개발자가 명시적으로 페이징이 가능한 메모리, 불가능한 메모리 그리고 캐시 메모리에서 데이터 정렬이 되어 있는 메모리를 ExAllocatePoolWithTag()를 사용하여 할당한다. 이러한 조건과 함께 메모리를 할당하는 경우 메모리 할당이 실패할 경우 시스템 전체에 문제가 생길 수 있다는 것을 숙지하고 예외 처리를 잘 해야 한다. 또한 NT의 실행부에서 이러한 메모리 할당을 지원 하긴 하지만, 절대적으로 이 해당 주소의 물리 메모는 VMM만이 조작 가능 하다는 것도 알고 있어야 한다. ExAllocatePool() 관련된 함수들 중 하나를 사용하여 할당하는 가상 주소 공간의 어떤 포인터들도 커널 가상 주소 공간을 벗어 날 수 없다. 엄격히 말해서 사용자 프로세스와 달리 커널 프로세스는 실제로 하나의 가상 주소 공간을 사용하고 있지만, ZwAllocateVirtualMemory()를 사용하여 할당 당시에 컨텍스트에서만 접근이 가능한 메모리를 할당 받을 수 있다. 커널 가상 주소 공간은 현재 실행 되고 있는 커널 모드 드라이버가 어떤 프로세스의 컨텍스트에 동작 하던지 간에 엑세스가 가능 해야 하기 때문에 (NT 커널은 사용자와 커널 드라이버간에 1:1 매핑 구조를 사용 하고 있다. 사용자 모드와 커널 모드간의 프로세스 매핑은 전형적인 운영체제 이슈로 이 부분을 모르는 독자들은 swblog.net의 펀더멘털 노트를 참조하기 바란다) NT VMM은 가상 공간을 하위 2GB로 사용하는 모든 프로세스가 시스템 가상 주소 공간으로 예약된 주소를 사용하며 시스템에서 실행되는 모든 프로세스 컨텍스트 안에서 같은 주소 간간으로 사상된다.

파일 시스템 개발자는 사용자 모드의 코드에서 전달된 파라미터안의 사용자 공간의 버퍼를 조작 해야 하는 경우가 있는데 이는 대부분 사용자 모드에서 정의된 주소 공간에 데이터 넣거나 빼는 작업이다. 따라서 메모리 조작에 특히 조심해야 하는 것들이 있다. 이렇게 전달 된 주소 공간은 실제로는 커널 공간의 가상 주소가 아니기 때문에 사용자 모드의 특정 프로세스 컨텍스트 안에서만 유효한 값을 가지게 되는 경우가 존재 한다. 물론 앞서 언급한 VMM간의 특징 때문에 사용자 모드에서 APC_LEVEL보다 높은 우선 순위로 전달된 메모리를 접근 하기 위해서는 반드시 페이지 락을 통해서 이 버퍼를 사용하다가 페이지 폴트가 발생 하지 않도록 하기 위해 물리 페이지를 고정해야 한다. 다시 말해 우연하게 할당된 메모리의 프로세스 컨텍스트와 동일한 환경에서 실행 된다고 하더라도 페이지 아웃이 되어 있다면 완전 쓰레기 값을 참조하거나 기대치 못한 폴트를 발생 시켜 전체 시스템이 멈출 수 있다는 것을 상기 해야 한다. VMM은 언급된 개발자의 고려사항을 모두 지원한다. 우선 VMM의 MmProveAndLockPages() 이나 MmBuildMdl()과 같은 보조 함수들을 이용하여 어떤 버퍼들이든 간에 관련된 물리 메모리를 고정 시킬 수 있다. VMM의 MmProveAndLockPages() 이나 MmBuildMdl()의 함수는 내부적으로 해당 가상 주소 공간 뒤에 존재하는 물리 페이지 프레임들을 기술하여 리스트로 가지고 있는 MDL을 생성하며 부가적으로 기술된 페이지들이 메모리상에서 쫓겨 나가지 않도록 관리하여 버퍼를 편하게 쓸 수 있는 방법을 제시하고 있다. 두 번째로 사용자 모드에서 전달된 메모리 공간을 시스템 가상 주소 공간으로 사상 시켜 해당 주소가 존재하는 컨텍스트와 관계 없이 버퍼를 쉽게 접근하게 하는 것을 툴을 제공하는데 이 것이 MmGetSystemAddressForMdl()이다.

이러한 것 이외에도 시스템적으로 메모리를 관리 해야 하는 여러 가지 일련의 작업들을 처리한다. 예를 들어 NT VMM은 시스템에서 사용되는 모든 스레드에게 4KB 페이지 프레임 기준으로 3개의 페이지를 고정적으로 할당 된 스택 프레임들도 관리한다. 앞서 언급 되었듯이 물리 페이지 프레임을 조작 할 수 있는 것은 오직 VMM 만 가능하기 때문에 VMM이 파일 시스템과 NT 캐시 매니저의 캐싱 파일 데이터들의 관리를 보조하고 페이지 폴트가 생겼을 때 시스템 성능을 증가 시키기 위해서 페이지 클러스터(Cluster)를 지원 한다. 여기서 클러스터라는 것은 16 페이지를 하나의 클러스트로 묶어서 64KB 사이즈 또는 128KB 단위로 접근하게 하는 것을 의미한다. 이런 클러스터의 개념은 아주 오래 전에 Marshall K. McKusick에 의해 제시된 "A Fast File System for Unix"나 "The Design and Implementation of a Log-Structured File System" 에 의해서 그 성능이 검증 된 바 있다. 이러한 성능상에 문제 말고도 VMM은 커널 필터 드라이버나 사용자 모드의 어플리케이션간에 커뮤니케이션을 위해서 공유 메모리 오브젝트나 메모리 사상 파일들도 대신 해서 생성 해준다.

파일 시스템 드라이버에게 유용한 VMM의 지원 함수가 있는데 그것은 MmQuerySystemSize() 이다. NT VMM은 내부적으로 MmSystemSize라는 전역 변수를 초기화하여 시스템의 메모리량을 대략적으로 알려주는데 MmQuerySystemSize()는 이 변수의 정보를 얻는 함수이다. 이 함수에 의해서 반환 되는 시스템 메모리양은 크게 3가지인데 하나는 MmSmallSystem, MmMediumSystem 그리고 MmLargeSystem이다. 이 시스템 정의 값은 이름에서 알 수 있듯이 메모리 양이 적은 시스템, 중간형태, 큰 시스템을 대략적으로 구분 해준다.

이 리턴 값을 가지고 정확한 물리 메모리의 양을 파악 할 수는 없지만 파일 시스템 개발자는 현재 시스템에 대해서 동적으로 시스템의 성능을 고려한 정책을 사용 할 수 있다. 예를 들어 MmQuerySystemSize() 함수가 MmSmallSystem을 리턴했다면 파일 시스템은 큰 메모리 시스템이나 중간형태의 메모리 시스템 보다 적은 형태로 메모리를 할당 받거나, 미리 존(Zone)형태로 메모리를 할당 받아 시스템을 운영 할 수 있고 또한 다른 큰 시스템이나 중간 크기 메모리 사이즈를 가진 시스템보다 적은 워커(Worker) 스레드를 할 당 할 수 있다. 파일 시스템 개발자는 AcquireFileForNtCreateSection()과 ReleaseFileForNtCreateSection() 두 함수를 반드시 제공해야 하는데 이유는 공유 메모리와 메모리 사상 파일을 지원 하기 위해 VMM이 하이라키(Hierarchy) 상에서 파일 시스템 아래에 존재 하기 때문에 파일 시스템의 적절한 콜백 시스템을 요구하기 때문이다.

파일 시스템 구현을 위한 VMM의 지원 루틴.

NT VMM은 MmFlushImageSection과 MmCanFileBeTruncated()라는 두 개의 함수를 제공한다. 이 두 함수는 파일 시스템 설계자나 개발자들에게 매우 중요한 역할을 하는 함수 인데 다른 VMM의 지원 루틴이나 API들처럼 잘 문서화 되어 있지 않다. 이번 칼럼에서는 이 두 개의 함수를 좀 더 구체적으로 알아보는 것으로 글을 마감하고자 한다.

MmFlushImageSection()는 특정 이미지 섹션 오브젝트와 관련된 정보를 담고 있는 메모리상의 페이지가 취소 될 수 있는 지를 파일 시스템이 NT VMM에게 질의를 요청 할 수 있도록 해주는 함수이다. 예를 들어서 만약 사용자가 메모리에 사상되어 있는 특정 오피스 실행 파일을 복사하려다가 취소를 하고 이를 지우는 것을 원했다고 하자. 이런 경우 해당 이미지는 마지막 소프트웨어 버전의 사본을 갱신하려고 할 것이다. 따라서 파일 시스템 드라이버 개발자는 파일을 삭제 하기 전에 파일 데이터를 포함하고 있는 모든 페이지가 플러시 되거나 완전히 지워지는 것을 확인 해야 한다. 일반적으로 실행 시간에 이 페이지들은 모든 유저가 파일을 닫았다고 하더라도 파일 스트림 데이터들을 그대로 유지 하고 있을 수 있다. 하지만 만약 유저가 파일 스트림을 삭제 하려 한다면 파일 시스템은 이러한 정보들이 메모리에 머물 수 없도록 해야 한다. 따라서 파일 시스템 드라이버가 파일 스트림을 쓰기 위해 파일을 여는 작업을 원하는 스레드에게 해당 동작을 허가 해주기 전에 MmFlushImageSection()를 호출 해주여야 하며 NT VMM은 다른 스레드가 이전에 해당 파일을 메모리에 실행 이미지로 사상 시켜 놓은 경우 이 파일 스트림을 열려는 해당 스레드를 제한 해야 한다. NT VMM이 한번 이미지 섹션에 대한 플러싱 동작이 안전하다고 결정하면 VMM은 해당 섹션을 보유하고 있는 리스트의 모든 페이지를 더티(Dirty) 상태로 표시하고 모두 블록 디바이스로 비운다. 따라서 파일 스트림에 대한 비 동기적으로 수정된 모든 쓰기 동작은 반드시 플러시 전에 정지 되어야 한다. 파일 시스템 개발자 입장에서는 VMM이 더티 페이지로 리스트의 정보를 바꾸는 것은 순간적이고 VMM이 비동기 쓰기 동작에 대한 확인을 한 후 바로 쓰기를 할 것이기 때문에 파일 시스템 드라이버가 더티에 대한 정보를 백업하고 있다면 해당 페이지가 플러시에 의해서 다시 한번 쓰여 질것이라는 것을 고려 해야 한다.

MmCanFileBeTruncated()는 VMM이 파일 시스템 드라이버가 파일 스트림을 잘라내는 것을 반드시 실행 해야 할지 아니면 못할지를 결정하는 것에 대한 실마리를 제공한다. 만약 사용자가 해당 파일 스트림이 이미지로서 메모리에 사상 되어 있는 경우에 이에 대한 조작을 허락하지 않도록 요청 할 수 있고 VMM 이 이미지 섹션 오브젝트를 생성하였기 때문에 이에 대한 스트림을 잘라 내는 요청을 거절 할 수 있다. MmCanFileBeTruncated()는 해당 요청에 대한 결과를 반환 해주는 것으로 파일 시스템은 파일 스트림을 잘라내기 전에 이를 확인하여 불필요한 예외상황을 미연에 방지하는 것이 좋다. 파일 시스템 드라이버 개발자는 이 함수를 호출 하기 전에 파일 스트림을 배타적으로 획득 되었는지 보장 해야 한다. 따라서 MmCanFileBeTruncated()를 호출 하기 전에 MainResource를 배타적으로 획득 하는 작업을 선행 한다.

다음 칼럼에는

이로서 3회에 걸친 NT 가상 메모리 매니저에 대한 이야기를 마칠까 한다. 파일 시스템 드라이버를 개발 하기 위해서는 자신의 정책과 설계가 가장 중요한 요인이겠지만, NT상에서 이러한 컨셉과 정책을 구현 하려면 실제 파일 시스템과 떼어 낼수 없는 캐시 메니저, 그리고 가상 메모리 매니저를 반드시 이해 해야 한다. 어떻게 보면 좀 구체적인 구현 이슈이긴 하지만 NT상의 파일 시스템의 구조 전체를 변경 할 만큼 중요한 이슈이므로 파일 시스템 구현 자체에 들어가기 전에 각 모듈들을 6회에 걸쳐서 소개 하였다.

다음 칼럼에서는 이제까지 소개 되었던 파일 시스템의 자료구조, I/O 매니저, 캐시 매니저, 그리고 가상 메모리 매니저에 대한 지식을 기반으로 하여 파일 시스템 드라이버가 실제 NT 커널에서 어떤 식으로 구현 되는지를 알아 볼 것이다.

References

Rejeev Nagar, "Windows NT File System Internals": A Developer Guide, O'Reilly 1998

P. B. Kruchten."The 4+1 View Model of architecture."

David Garlan and Mary Shaw January 1994 "An Introduction to Software Architecture"

Kernel Source http://reactos-mirror.googlecode.com/svn

Kernel Source http://nuwen.net

NT의 가상 주소 변환

The Virtual Address Translation with Considering MMU and TLB

가상 주소를 변환 하는 것 자체는 매우 간단한 일이다. 가상 주소와 물리 주소의 매핑(Mapping)정보를 이용하여 단순히 해당 물리 주소의 정보를 가져오는 것으로 해결 할 수 있다. 하지만 여기에는 해당 컴퓨터 아키텍처의 성능을 고려 해야 한다. 이에 따라 이러한 매핑 정보들을 캐시하는 TLB (Translation Lookaside Buffer)가 일반적으로 사용된다. 이러한 TLB은 하드웨어적으로 구성되며 각 시스템의 아키텍쳐에 따라 완전히 다른 형태를 이루게 된다. NT 가상 메모리 매니저(VMM, Virtual Memory Manager)는 이종간의 TLB들을 관리하도록 하며 가상 주소와 물리 주소간의 번역을 하드웨어적으로 처리하는 MMU들의 동작을 범용적으로 추상화 하기 위해서 몇 가지 자료구조와 복잡한 알고리즘을 사용한다.

정명수 |

필자는 지난 3년간 삼성전자에서 플래시 메모리와 관련된 연구와 임베디드 소프트웨어, 커널 드라이버 등을 개발 했었다. 현재는 조지아 공대(Georgia Institute of Technology) 컴퓨팅 칼리지에 재학 중이다. 글쓰기를 매우 좋아하며 학부시절에는 객체 지향 패러다임을 통하여 해석하는 프로그래밍 언어론에 관심이 있었으나 실무과정을 거치면서 컴퓨터 아키텍처로 관심사가 옮겨졌다. 최근에 관심 있는 분야는 운영체제, 파일시스템, 실시간 스케줄링 등이다.

가상 주소와 물리 주소간의 번역은 아키텍쳐에 따라 매우 다를 수 있다. 설사 주소 변환 또는 번역 작업이 쉽게 이루어 질 수 있다고 하더라도 이를 수행하는 여러 가지 MMU와 TLB와 같은 하드웨어들을 도와 호환성과 이식성을 가진 운영체제를 만드는 것은 복잡한 데이터 조작과 하드웨어 관리를 필수적으로 수반한다. 이번 컬럼에서는 윈도우 NT가 VMM을 통해서 이러한 작업을 어떻게 수행 하는 지와 더불어 이를 위한 자료구조, 그리고 그들간의 연결 상태들을 알아보도록 하자.

만약 독자가 MMU와 TLB동작을 제대로 이해하지 못하고 있다면 필자의 블로그의 Fundamental Note의 OS 카테고리의 Virtual Address 란을 반드시 읽어보기 바란다. 본 컬럼에서는 가상 주소에 대한 기본을 다루는 것이 아니라 윈도우 NT를 중심으로 가상 주소를 운용하는 기법을 이야기 하는 것으로 가상 주소에 대한 기본 운영체제 지식이 수반 되지 않으면 전반적이 이해에 대하여 어려움을 겪을 수도 있다.

가상 주소 번역 (Translation of Virtual Address)

윈도우 NT의 각 가상 주소(Virtual Address)는 32 bit로 구성 된다. 이러한 가상 주소는 반드시 바이트 단위의 특정 주소 공간으로 번역 할 수 있는데, 이를 위해서는 크게 두 가지의 시스템 콤포넌트(Component)에 대한 이해가 필요하다. 첫째는 프로세서에 의해 제공되는 메모리 관리 유닛(MMU, Memory Management Unit, 이후 MMU로 언급)이고 다른 하나는 운영체제에 의해 구현된 가상 메모리 매니저(VMM, Virtual Memory Manager)이다. 디바이스 드라이버 개발자가 일반적으로 이해는 물리, 가상 주소간의 번역은 가상 주소에서 물리 주소로의 번역이 일반적이나, 반대로 물리 주소에서 가상 주소로의 번역 또한 가능하다. 예를 들어서 주소간 번역을 맡고 있는 페이지 매핑 테이블의 사이즈가 부족하여 특정 주소 공간의 컨텐츠를 메모리가 아닌 스토리지로 저장해서 공간을 확보해야 하는 경우, 해당 컨텐츠를 스토리지로 내보내고 나서 이를 무효화 처리를 해주어야 하는데 이때 해당 물리 주소가 어떤 가상 주소에 매핑 되어 있는지를 찾아야 적절한 무효화 처리를 해줄 수 있다.

통상적으로 가상 주소 번역은 MMU 하드웨어에 의해 이루어 지는데 이를 위해서는 VMM은 주소 번역에 필요한 적절한 맵(Map)들과 MMU가 실제 주소를 번역 할 때 사용되는 페이지 테이블(Page Table)들을 관리해주어야 한다. 일반적으로 윈도우 NT에서 VMM이 프로세스의 가상 주소 공간에 대한 정보를 구성하는 것은 프로세스가 컨텍스트 스위칭(Context Switching)을 처음 시도 할 때이다. VMM은 컨텍스트 스위칭이 시작 될 때 해당 프로세스의 적절한 물리 주소 번역에 대한 정보를 담아 두기 위해 페이지 테이블을 구성한다.

프로세스가 가상 주소 공간을 접근을 시도할 때 MMU는 가상 주소에서 물리 주소공간으로 번역을 시도한다. 이 때 일반적으로 해당 가상 주소 공간에 대한 매핑 정보를 필요로 하는데 해당 매핑 정보 또한 메모리에 테이블 형태로 존재하기 때문에 특정 프로세스가 가상 주소의 컨텐츠에 접근을 시도할 때 상당한 오버헤드가 존재 할 수 있다. 우선적으로 주소 번역을 위한 매핑 테이블을 메모리에서 한번 읽어드려야 하고 이렇게 읽어온 매핑 정보를 통하여 가상 주소를 물리주소로 번역한 뒤, 다시 메모리를 접근하여 원하는 컨텐츠를 확보 해야 한다. 따라서 하나의 가상 주소 접근을 위해 2번의 메모리 접근이 발생하므로 이를 줄이기 위해 TLB라는 매핑 정보에 대한 캐시가 통상적으로 제시 된다. TLB는 가장 최근에 번역 되어진 주소 관간의 정보들을 프로세스 ID(PID)를 통해서 분류하여 저장 해둔다.(PID를 통해서 각 프로세스마다 다른 주소 공간을 분류 하는 경우도 있고 아닌 경우도 있는데 이는 해당 컴퓨터 아키텍쳐(Architecture)에 따라 다르다) 따라서 MMU가 가상 주소를 물리 주소로 번역을 시도 할 때 TLB를 먼저 확인 하여 TLB에 매핑 정보가 있다면 메모리에 접근하여 해당 매핑 정보를 읽어 드릴 필요 없이 바로 처리 할 수 있게 된다. TLB에 대한 자세한 내용은 뒤에서 한번 더 언급 하도록 하겠다. 다시 돌아가서 MMU는 앞서 언급된 번역 속도를 향상 하기 위해 TLB에 먼저 매핑 정보가 있는지 확인한다. 만약 TLB에서 매핑 정보를 찾지 못하는 경우에만 메모리에 접근 하여 매핑 정보를 가져와 가상 주소에서 물리 주소로의 번역을 시도한다. 여기서 각 번역은 페이지 프레임(Page Frame)으로 이루어져 있음을 상기 해야 한다.

가상 주소에서 물리 주소로 변역을 하고 나서 해당 물리 주소가 현재 메모리에 매핑 되어 있는 경우, 프로세스는 바로 해당 물리 주소의 메모리로의 접근을 허락 한다. 그렇지 못한 경우는 우선적으로 예외 (Exception)을 발생 하고 예외 핸들러(Handler)는 페이지 폴트(Fault)를 발생시킨다. 페이지 폴트가 발생하면 이에 대한 핸들러에게 제어권을 보내어 이를 관리 하는데 윈도우 NT의 경우는 VMM 페이지 폴트 핸들러가 이를 담당한다. VMM 페이지 폴트 핸들러는 적절한 데이터를 시스템 메모리로 가져 온 뒤 매핑 정보를 업데이트하고 예외를 발생한 페이지로 제어권을 반환하는 절차를 일반적으로 거친다. 물론 이러한 예외 처리는 페이지 프로텍션(Protection)에 대한 충돌충 있을 때도 하드웨어에 의해 동일하게 일어 날 수 있다.

MMU에 대한 설계는 윈도우 NT의 VMM에 상당히 많은 영향을 미친다. MMU 인터페이스 격인 VMM은 하드웨어 의존성이 매우 강하고, 이 때문에 이종간의 플랫폼에서 호환성 및 이식성이 현저히 떨어진다. 저번 컬럼에서 언급 되었듯이 VMM은 시스템의 물리 메모리를 관리 하기 위해서 비페이징 영역(Non-paged pool)에 페이지 프레임에 대한 데이터베이스를 유지 하고 있다. 이 데이터 베이스는 연속적인 물리 주소 공간의 페이지 프레임들의 집합으로 이루어져 있다. 각각의 물리 페이지 프레임이 순차적으로 구성 되기 때문에 (n개의 물리 RAM이 있다면 페이지 프레임 숫자는 페이지 프레임 0번에서 페이지 프레임 n-1으로 구성 된다고 볼 수 있음) 페이지 프레임을 위한 페이지 프레임 숫자(PFN, Page Frame Number) 데이터 베이스 엔트리(Entry) 계산은 매우 간단 하다. 한번 가상 주소가 물리 주소로 번역 되고 나면 PFN은 PFN 데이터 베이스의 사이즈에 의해 곱해지고, 곱한 후에 결과 주소는 물리 베이스 주소 (Base Address)에 더해진 뒤 PFN 데이터 베이스 할당 되게 된다.

32 비트 가상 주소를 위한 자료구조

윈도우 NT의 32비트 가상 주소를 고려 하여 주소 번역에 사용되어야 하는 자료 구조, 또는 하드웨어 사이즈들을 고려 해보도록 하자. 이러한 작업은 실제 파일 시스템 드라이버 개발자에게는 빈번한 일로, 주소 공간에 대한 이해와 함께 이러한 주소 공간을 어떤 식으로 관리하고, 자료구조를 구성하는지를 이해하는데 필수적이다. 페이지 테이블 사이즈가 4096 바이트이기 때문에 페이지 오프셋 계산에 12 비트를 필요로 한다. 해당 12 비트는 LSB(Lease Significant Bit)에 저장 된다. 따라서 MMU는 페이지 테이블 내에 PTE의 페이지 프레임들을 구분하는데 20비트를 가지고(32비트 – 12 비트) 계산 하게 된다. PTE는 20비트로 구성된 (백만 개의) 순차적 배열 정도로 추상화 할 수 있다. 인텔의 x86 아키텍처를 비롯하여 대부분의 아키텍처에서 PTE에 대한 자료구조들을 미리 정의 해두었다. 인텔 플랫폼(Platform)의 경우 각각의 PTE는 반드시 4바이트로 구성된다. 현재까지 고려한 것을 다시 정리하면 가상 주소 공간을 위한 번역 정보에 필요한 사이즈를 유추 할 수 있다. 다시 말해 백만개 엔트리와 각 엔트리(PTE) 4바이트로 구성 되기 때문에 2²² (4MB)형태의 사이즈를 필요로 한다. 각각의 페이지 테이블은 하나의 페이지 사이즈에 저장 되어야 하기 때문에 하나의 프로세스에 대한 페이지 테이블은 1024 페이지 프레임으로 모든 PTE들을 구성 될 수 있다.

주소 번역에 필요한 정보를 위한 메모리도 매우 큰 사이즈이기 때문에 이에 대한 성능저하를 피하기 위해 페이지 테이블 역시 페이징 된다. 이를 위해서 x86 프로세스는 이중 레벨의 페이지테이블 엔트리를 정의 해두었다. 각각의 프로세스는 페이지 테이블의 PTE들을 포함하는 페이지 디렉토리(Directory)를 가지고 있다. 이 디렉토리는 한 개의 페이지 사이즈와 동일하기 때문에 1024개의 각각 페이지 테이블을 참조하는 PTE들을 가지고 있다. 일반적으로 프로세스를 위한 가상 주소는 10 비트를 예약 해두는데 이 10비트는 페이지 디렉토리로부터 페이지 테이블을 구분하는데 사용 되며 페이지 내에 오프셋으로 12 비트를 사용한다.

<그림 1, 가상 에서 물리 주소로의 번역>

TLB를 포함하여 가상 주소가 번역 되는 과정을 다시 정리 해보자. MMU는 TLB를 우선적으로 확인하여 해당 가상 주소에서 물리 주소로의 매핑 정보가 있는지를 먼저 확인한다. 만약 TLB에 존재 하는 경우 (이 경우를 보통 TLB hit로 부른다) 단순히 해당 물리 주소를 바로 반환 하여 작업을 종료 할 수 있다. 만약 TLB에 존재 하지 않는 경우 ( 이 경우는 TLB miss로 불린다)는 조금 작업이 복잡하다. 우선 프로세스마다 존재하는 페이지 테이블 중 현재 가상 주소의 번역을 요청한 페이지 테이블을 확인하여 엑세스가 필요한 물리 페이지 프레임의 정보를 가지고 있는 PTE의 위치를 찾는다. PTE가 가리키는 물리 주소가 해당 프로세스의 권한으로 접근이 가능하고(Protection check) 현재 메모리에 상주하고 있다면 MMU는 해당 주소의 접근을 허락한다. 다른 경우라면 앞서 언급 되었던 것처럼 페이지 폴트 또는 프로텍션 위반으로 예외를 발생 시킨다. 이러한 예외는 결국 VMM에 의해서 관리 된다.

여기서 우리는 한가지 개념을 더 이해 해야 한다. 그림 1에 나와 있는 프로토타입 페이지 테이블이다. 사실, 하나 이상의 가상 주소가 같은 물리 주소에 매핑 되는 경우가 있기 때문인데, 프로토 타입 페이지 테이블은 이렇게 하나 이상의 프로세스의 가상 주소 공간이 하나의 물리 페이지로 매핑 되는 페이지 프레임들과 페이지 테이블 엔트리들의 정보를 보유하고 있다. 이를 위해서 우리는 공유 메모리와 메모리 맵드(Mapped) 파일의 컨셉을 이해 해야 한다.

공유 메모리와 메모리 맵드 파일(Memory Mapped File)

우리가 어플리케이션 레벨에서 개발을 할 때에는 메모리 접근에 대해서 그다지 어려움을 느끼지 못한다. 어플리케이션 프로세스는 간단히 malloc 을 호출 하는 것으로 VMM으로부터 가상 주소를 얻을 수 있고 프로세스는 단순히 해당 가상 주소를 통해서 메모리 블록을 접근 할 수 있다. 계속 언급되어 왔듯이 운영 체제는 가상 주소와 물리주소간의 번역과 이때 성능향상을 위해 채용된 하드웨어들을 관리 해야 하는 책임이 있다. 더욱이 운영체제는 시스템에서 동작하는 모든 프로세스 동작 형태를 확인 할 수 있어야 하며 특정 프로세스에 물리 메모리를 할당하는 작업들도 수반 해야 한다. 동시에 대부분의 어플리케이션은 자신에 필요한 만큼의 메모리를 계속 요청 할 수 있고, 특정의 경우는 스토리지와 같은 디바이스로 I/O를 신청 할 수도 있다. 추가적으로 복잡한 어플리케이션의 경우 공유 메모리를 통한 데이터 공유를 시도하기도 한다.

일반적으로 I/O는 파일 시스템의 읽기 쓰기의 시스템 콜을 통해서 이루어진다. 따라서 사용자가 I/O를 요청 하는 경우 시스템 트랩에 의해서 사용자 모드에서 커널 모드로 프로세서가 옮겨가고 스토리지로부터 데이터를 인출 하고 나면 다시 모드를 변경 하게 된다. 읽기의 경우, 파일 시스템은 반드시 데이터를 읽어서 시스템 메모리에 적재한뒤 다시 그것을 사용자 어플리케이션의 버퍼 영역으로 복사 해주어야 한다. 쓰기 요청의 경우는 운영체제가 어플리케이션 버퍼로부터 시스템 메모리로 복사를 하는 작업을 먼저 하게 된다. 시스템 버퍼로부터 데이터를 복사하는 행위는 I/O 요청에 대한 시스템 호출에 대한 오버헤드와 함께 어플리케이션의 실행에 큰 부하를 미칠 수 있다. 더욱이 같은 파일에 대해서 다른 두 프로세스가 접근 하는 경우 정말 필요 없는 부하가 가중 될 수 있다. 이러한 경우 두 어플리케이션 프로세스는 같은 바이트 영역을 접근 하지만 앞서 언급된 바대로 자신이 소유한 버퍼를 가지고 하나의 물리적 주소의 데이터를 가져온다. 하나의 데이터에 대해서 다른 두 버퍼를 사용 하는 오버헤드 문제 이외에 데이터의 코히어런스(Coherence)문제도 존재 한다. 두 프로세스의 이름을 프로세스1과 2로 붙여 주고 문제가 되는 부분을 예로 살펴 보자. 프로세스 1이 자신이 소유한 버퍼를 통해서 물리적 주소의 데이터를 가지고 와서 수정하였지만 아직 다시 해당 물리 주소 공간으로 데이터를 업데이트 하지 않았는데 프로세스 2가 같은 물리 주소 공간에 대해서 읽기를 요청하는 경우 프로세스 1에 의해서 수정된 데이터를 보지 못하고 단지 해당 물리 페이지의 데이터를 그대로 가져와서 사용 하게 된다.

이와 달리 만약 각 프로세스가 자신이 가지 버퍼를 물리 주소로 매핑 한다면 상황이 달라진다. VMM은 스와핑(Swapping) 데이터를 스토리지로부터 읽어 이를 가상 메모리로 언제든지 제공 할 수 있다. 어플리케이션은 해당 하는 스토리지 파일의 I/O를 신청 하는 대신 특정 메모리를 할당하여 이를 접근 하도록 한다. 그러면 해당 페이지는 페이지 폴트를 일으킬 것이고 이 페이지 폴트는 운영체제에 의해서 데이터가 교환 되고 정상적인 페이지 접근으로 변경 될 것이다. 따라서 어플리케이션은 이러한 방법으로 물리 메모리를 접근 할 수 있다.

이러한 파일과 가상 주소 공간의 매핑 방법은 앞서 언급한 문제들을 해결 하는 것 이외에도 다른 장점도 가지고 있다. 같은 파일에 대한 매핑을 신청하는 모든 어플리케이션이 가상 주소 공간에 물리 페이지를 접근 함으로서 어떤 어플리케이션 프로세스가 해당 파일을 수정 하던 간에 일괄적으로 최신의 데이터를 볼 수 있다는 것이다. 따라서 NT VMM은 이러한 방법의 수단으로 파일 매핑을 지원한다. 매핑된 오브젝트는 이러한 스토리지에 존재하는 파일을 대신하는 수단이 된다. 사용자가 파일을 실행 할 때 NT VMM은 이를 신청한 사용자의 프로세스에 가상 공간에 매핑된 오브젝트를 할당시키고 나서 인스트럭션을 실행하게 된다. 만약 같은 머신의 다른 프로세스가 같은 파일을 실행하게 된다면 아까 할당되었던 매핑된 오브젝트를 그 프로세스의 가상 주소 공간에 할당 해준다. 해당 물리 페이지의 VAD(Virtual Address Descriptor)는 이미 메모리에 상주하고 있기 때문에 사용자 프로세스는 상당히 빠른 시간 안에 자신의 요청한 파일을 볼 수 있다.

파일 매핑은 두 프로세스의 물리 메모리를 공유 하는 방법만을 지칭 하지는 않는다. 가상 주소에 해당하는 물리 페이지 프레임으로부터 독립적으로 VAD 조작이 가능 하기 때문에 VMM은 모든 프로세스에 대해서 해당 프로세스의 VAD를 약간 수정 하는 것만 으로 간단히 공유 메모리를 제공 할 수 있다. 이는 사용자 프로세스는 파일을 기반으로 한 공유 메모리를 할당 하는 것 만으로 공유 메모리 오브젝트를 할당 할 수 있다는 것을 의미하기도 한다. 이러한 공유 기능은 VMM의 기본이 되는 작업으로 VMM이 맵핑된 오브젝트 그리고 공유 오브젝트를 제공하기 위해 사용 하는 자료 구조가 바로 앞서 언급되었던 프로토타입 페이지 테이블이다.

<그림 2, 같은 페이지를 프로세스마다 다른 가상 주소 공간에 매핑 시킨 예>

프로토타입 페이지 테이블 (Prototype Page Table)

페이지 프레임은 프로토타입 페이지 테이블(PPT)로 기술되는 특별한 구조체에 의해 공유 되도록 설계되어 있다. PPT는 다른 중요 커널 오브젝트나 자료구조와 달리 비페이징 영역 이외에도 페이징 영역 모두에 할당 되어 사용 될 수 있다. VMM이 프로세스를 위해 매핑 정보 또는 공유 오브젝트를 생성할 때는 파일 매핑을 기본으로한 물리 페이지를 기술 하기 위해 프로토타입 페이지 테이블 엔트리(PPTE) 또한 같이 할당한다. 매핑된 오브젝트를 위한 PPT는 같은 오브젝트를 매핑하는 모든 프로세스에 의해 공유 된다. 각각의 PPTE는 실제 메모리를 가리킬 수도 아닐 수도 있다. 다시 말하면 해당 페이지는 페이지 물리 페이지 프레임에 매핑 되어 있거나 아니면 스토리지에 매핑 되어 있을 수 있다는 것이다. 모든 프로세스가 같은 PPT를 사용 하기 때문에 프로세스들은 같은 페이지 프레임과 매핑된 데이터를 볼 수 있다. 페이지 프레임이 PPTE에 할당 되면 처음에는 PPTE는 항상 유효 상태(Valid)로 표시 된다. 인텔 x86 MMU와 MIPS 이종간의 아키텍처라도 MMU는 프로토타입 페이지 테이블을 위해 PPTE와 같은 유사 구조 페이지 테이블을 제공하지만 각각은 동일 하지 않다. NT VMM은 이를 위해서 다음과 같은 형태로 공유 메모리를 이종간 MMU에서 동작 시킬 수 있도록 한다.

우선 인텔 x86 의 아키텍처의 MMU는 PTE와 페이지 테이블을 정확히 기술하고 있다. 따라서 VMM은 프로세스가 파일 매핑을 생성할 때는 언제든지 PPT와 PPTE를 상주 메모리에 할당한다. 프로세스가 매핑된 파일 오브젝트의 가상 주소를 접근을 시도할 때 MMU는 해당 가상 주소를 페이지 디렉토리 테이블 오프셋을 가지고 적절한 페이지 테이블로 가상 주소를 번역 한다. 초기 상태에서 해당 PTE에 대한 접근은 페이지 폴트를 일으키게 된다. (초기에 물리 주소의 데이터가 로드 되어 있지 않으므로) 이 페이지 폴트는 VMM 페이지 폴트 핸들러고 뛰게 되고 VMM의 페이지 폴트 핸들러는 해당 가상 주소의 정보를 담고 있는 VAD로 하여금 매핑된 오브젝트를 가리키도록 변경 시키게 한다. 따라서 VMM은 적절한 PPTE를 찾을 수 있게 되는데 이 시점에 PPTE는 유효 상태로 마크 되어 있기 때문에 PFN 데이터 베이스 엔트리와 해당 백포인터를 연결 할 수 있다. 동시에 VMM은 PTE를 유효상태로 변경하고 PTE가 적절한 물리 주소를 가리킬 수 있도록 한다. 이러한 연결 방법은 PPTE와 PTE가 적절한 물리 주소 정보를 담을 수 있도록 하고 PFN 데이터 베이스 엔트리는 이 PPTE의 백포인터를 설정하도록 한다. 이후 메모리 접근이 재시도 되고 MMU은 정상적으로 초기화된 PTE를 찾을 수 있게 되므로 해당 가상 주소를 물리 주소로 번역이 가능해지게 된다.

페이지 테이블 설계에 있어서의 고려사항

여기서 주의 해야 할 것은 PFN 데이터베이스 엔트리는 PTE를 직접 참조 하기 못한다는 것이다. VMM은 PFN 데이터베이스 엔트리로부터 가상 주소가 공유 메모리 오브젝트로 할당된 정보를 가지는 PTE를 찾을 방법이 없다. VMM이 할 수 있는 최선책은 PFN 데이터베이스 엔트리를 참조하는 PPTE를 찾는 것이다. 이러한 기교는 심각한 결함을 야기 할 수 있다. 예를 들어, 커널 모드 컴포넌트가 VMM이 특정 물리 페이지를 쫓아 내기를 원한다고 하면 일반적으로 VMM에게 해당 PFN 데이터베이스 엔트리를 무효화 시키도록 하여 해결 한다.

무효화된 PFN 데이터베이스 엔트리는 나중에 MMU로 하여금 해당 가상 주소를 참조 할 때 페이지 폴트를 유발 시기키기 위해서 PTE를 무효화로 만든다. 문제는 해당 페이지가 매핑된 오브젝트를 가지고 있을 때이다. VMM은 공유 페이지를 보유하고 있는 페이지 프래임을 PTE를 접근할 방법이 없다. 따라서 만약 VMM에게 특정 페이지 프레임을 메모리에서 쫓아내게 하려고 한다면 VMM은 에러를 반환하여 이 작업이 매핑된 오브젝트와 관련되었을 경우 처리 할 수 없음을 표시하도록 한다. 이것은 우리와 같은 시스템 개발자에게 큰 문제가 될 수 있다.

섹션과 뷰(Section and View)

윈도우 NT 시스템은 오브젝트를 기반으로 한다. 여기서 오브젝트는 OOP(Object Oriented Paradigm)에서 이야기하는 클래스와는 다른 개념이다. 다시 말해 윈도우 NT는 대부분의 기능 조작들을 오브젝트 현태로 제공한다. 따라서 파일 매핑은 생성되고 접근 될 때 아래와 같은 두 가지를 고려 해주어야 한다.

파일 매핑과 공유 메모리 오브젝트를 관리하는 섹션 오브젝트 (Section Object)는 VMM에 의해서 생성된다.

프로세스가 매핑된 파일이나 공유 메모리 오브젝트에 대해서 접근을 원하는 경우, 호출자는 반드시 VMM에게 해당 파일로 뷰(View)를 매핑 시키도록 요구해야 한다. 결과적으로 이 뷰를 통해서 파일을 보고 제한된 범위 내에서 이를 접근 할 수 있도록 한다. 물론 프로세스로 하여금 같은 파일에 대해서 동시에 여러 개의 뷰를 생성하는 것을 허락 하기도 한다. 또 이 반대로 하나의 파일에 대해서 여러 프로세스에 뷰를 다른 뷰를 제공하는 것도 가능하다.

섹션 오브젝트는 다른 NT 오브젝트라 가지고 있는 것과 같이 프로텍션에 대한 특성을 가지고 있다. 섹션 오브젝트에 대한 프로텍션 특성을 명세 함으로서 프로세스는 해당 오브젝트와 파일 오브젝에 대한 데이터들을 정의 할 수 있다. 섹션 오브젝트는 크게 아래 두 가지 카테고리로 분리 된다.

실행 이미지에 대한 파일 매핑

비 실행 파일에 대한 매핑

우리가 VMM이 매핑 파일을 나타내는 섹션 오브젝트를 생성하도록 요구하는 경우, 우리는 어떻게 매핑된 파일을 다룰 것인가를 명세 할 수 있다. 시스템 로더(Loader) 는 파일 매핑을 사용 하여 명세된 파일 매핑이 실행 가능한 이미지를 실행하도록 해준다. 하지만 만약 복사와 같은 작업을 요청한다면 파일 매핑을 비 실행 파일로 매핑 시킨다. VMM은 섹션 오브젝트가 생성 될 때 마다 이것이 실행 가능한 이미지를 다루는지를 항상 정검한다. 만약 우리가 텍스트 파일등을 실행 가능한 이미지로 파일 매핑을 원한다면 VMM은 에러를 반환 하게 될 것이다.

실행 이미지 파일 매핑과 비 실행 파일에 대한 매핑 사이의 가장 큰 차이점은 VMM에 의한 매핑 범위가 어떤 식으로 수행 되는 가에 있다. 비 실행 파일 매핑이 프로세스에 수정 될 때 물리 메모리의 컨텐츠가 VMM에 변경 되기 때문에 이 수정에 대한 요청은 같은 파일 매핑을 사용하는 모든 프로세스에 보여 질 수 있다. 이러한 수정 작업은 나중에 스토리지로 데이터가 플러시 될 때 한번에 반영 된다. 하지만 이미지 파일에 대한 매핑이 수정될 때는 이와 다르게 별도의 페이지에 복사된다. 복사된 이후에 별도의 페이지는 페이지 파일에 의해서 가리켜진다. 만약 프로세스가 파일의 매핑을 취소하면 이 수정사항은 실제 스토리지로 반영 되지 않고 사라 질 수 있다.

공유 메모리 오브젝트 또는 섹션 오브젝트를 생성하기 위해서는 NT VMM은 NtCreateSection() 을 후출 해야 한다. 이 루틴은 커널 모드 개발자에게 알려져 있지는 않지만 대신에 ZwCreateSection()을 통해서 이를 대신 수행 할 수 있다.

이 루틴은 커널 모드에 의해서 공유 메모리 오브젝트나 스토리지를 우한 파일 매핑을 생성하는데 사용 될 수 있다. 파일 시스템 드라이버 개발자가 네트워크 파일 시스템을 개발 하는 경우라 할 지라도 우리는 이를 공유 메모라니 매핑된 파일 오브젝트를 생성하는데 사용 할 수 있다. 때로는 커널 모드 드라이버 개발자가 공유 메모리 데이터를 사용자 공간의 모듈과 공유를 원하거나 커널 모드 드라이버가 네트워크 건너편에 전에 존재하는 데이터를 원하는 경우 우리는 간단한 공유 메모리 오브젝트나 파일 기반의 공유 오브젝트를 얻어 쉽게 이를 조작 할 수 있다. 또한 커널 모드와 사용자 모드의 모듈간에 데이터를 서로 교환 해야 하는 경우에도 이러한 섹션 오브젝트가 응용 될 수 있다.

섹션 오브젝트에 대한 다른 Zw 함수들은 DDK 문서를 참조하여 써도 무방하다. 이에는 아래와 같은 함수들이 있다.

• ZwOpenSection()
• ZwMapViewOfSection()
• ZwUnmapViewOfSection()

NTSTATUS 

  ZwOpenSection(

    OUT PHANDLE  SectionHandle,

    IN ACCESS_MASK  DesiredAccess,

    IN POBJECT_ATTRIBUTES  ObjectAttributes

    );

NTSTATUS 

  ZwMapViewOfSection(

    IN HANDLE  SectionHandle,

    IN HANDLE  ProcessHandle,

    IN OUT PVOID  *BaseAddress,

    IN ULONG_PTR  ZeroBits,

    IN SIZE_T  CommitSize,

    IN OUT PLARGE_INTEGER  SectionOffset  OPTIONAL,

    IN OUT PSIZE_T  ViewSize,

    IN SECTION_INHERIT  InheritDisposition,

    IN ULONG  AllocationType,

    IN ULONG  Win32Protect

    );

NTSTATUS 

  ZwUnmapViewOfSection(

    IN HANDLE  ProcessHandle,

    IN PVOID  BaseAddress

    );

다음 칼럼에는

다음 컬럼에서는 이번 컬럼에 이어서 파일 매핑의 자료구조와 남은 이슈들을 다루고 VMM이 가상 주소를 관리함에 있어서 가장 키 이슈가 되는 페이지 폴트부분을 중점 적으로 다루도록 하겠다. 마지막으로 파일 시스템 드라이버 개발에 있어서 VMM을 위해 필요한 FSD 구현 사항들을 마지막으로 VMM에 대한 컬럼을 마무리 하도록 할 것이다.

References

Rejeev Nagar, "Windows NT File System Internals": A Developer Guide, O'Reilly 1998

P. B. Kruchten."The 4+1 View Model of architecture."

David Garlan and Mary Shaw January 1994 "An Introduction to Software Architecture"

Implement and Evaluate Advanced Power Efficient Gathering in Sensor Information System (개선된 센서 라우팅 방식 A-PEGASIS 구현 및 성능 평가)

정명수               박규영

(Myoungsoo Jung) (Gyuyoung Park)

본 기술 문서는 서창진과 양진웅에 의해서 구현된 개선된 센서 라우팅 방식(A-PEGASIS)을 구현하고 TyniOS와 TOSSIM을 이용하여 기존 LEACH 라우팅 방식과의 성능 비교를 위해 작성 되었다. 본 기술 문서에서는 단순히 A-PEGASIS 논문에 제시된 애매한 제한된 스패닝 체인 트리 메소드를 보다 명확히 기술하고 이에 대한 알고리즘과 동작방식을 구체적으로 제시한다. 본 기술 문서의 실험치는 TinyOS와 TOSSIM환경 위에서 구현된 A-PEGASIS 통신 방식은 기준 LEACH에 비해서 에너지 소비량(산술적 평균) 24% 향상, Base station과 통신을 위해 각 노드들의 생존량이 1.85~3배 정도되는 것을 보여 준다.

1. INTRODUCTION

최초 계층 구조 알고리즘인 LEACH는 Base station과 통신하기 위해 Figure 1에서처럼 전체 네트워크의 망을 특정한 개수 개의 센서 노드를 가진 클러스터로 나누고 그 중에서 클러스터 헤더 또는 coordinator로 불리는 대표자를 선출하여 이를 통하여 Base station과 통신을 한다. 통신을 할때는 해당 클러스터의 모든 측정값들을 하나의 패킷으로 Fusion하여 통신을 하게 되는데 그 결과 멀리 떨어져 있는 Base station과 집적 통신하는 노드의 수를 줄이고 클러스터 헤더에서 일괄적으로 퓨전하여 전송 되는 에너지 소비를 줄였다.

Figure 1클러스터의 구성 방법과 LEACH의 계층 구조

클러스터 헤더를 통한 LEACH의 통신 접근 방법은 무선 선서 네트워크의 가장 간단한 통신방법인Flooding이나 Gossiping 보다 훨씬 효율적인 동작을 수행 하지만 클러스터 헤더를 선출(Selection) 하는 과정에서 비효율적인 문제가 발생한다. 다시 말해서 각각의 클러스터 안에 분산적이며 확률적인 방법으로 선택된 클러스터 헤더의 센서 노드들은 클러스터가 중첩(Overlap)되는 특정 지역이 발생하여 클러스터 헤더가 밀집되는 현상이 발한다. 이러한 현상은 Base Station에게 측정값을 전달하는 토폴로지의 경로가 길어지게 되는 결과를 초래하며 이로 인해 성능 하락을 보이게 된다.

이에 반하여, 서창진과 양진웅에 의해서 제안된 A-PEGASIS는 기존 계층 구조 알고리즘들을 계선한 PEGASIS 알고리즘에 약간의 수정을 가하여 좀 더 효율적인 통신 알고리즘을 제안한다. 이 두 논문 다 Coordinator(PEGASIS군에서는 클러스터라는 의미가 존재 하지 않으므로 대표자라는 이름으로 대신하며 이는 클러스터의 헤더와 같은 역할을 한다)가 100% 퓨전을 하는 가정을 기반으로 하였기 때문에 Coordinator수가 하나로 축약된 계층 알고리즘으로 에너지 전달의 소비를 대폭 감소하였다. 다만 PEGASIS에서는 체인을 생성할 당시 Prim Algorithm을 사용하는데 이를 통하여 생성된 체인은 평균 길이가 길고 마지막으로 선정된 링크의 길이가 다른 노드들에 비하여 다소 긴 경향을 가지는 단점을 가지고 있다. 다소 긴 링크를 가지는 노드의 인접 노드들은 전송 에너지가 다른 노드들에 비하여 일찍 고갈 되는 경향이 존재 하는데 A-PEGASIS는 이러한 단점을 극복하기 위하여 Kruskal Algoritm의 유망집합(Promising set)을 사용하고 링크 스와핑 기법을 통해서 이를 조금 더 개선한 알고리즘이다.

본 기술 문서는 아래와 같은 순서로 구성되어 있다. 섹션 2에서는 A-PEGASIS를 실제 구현하고 평가 하기 위해서 문제가 되는 것들을 제시하고 이에 대한 해결 방법을 모색해본다. 섹션 3에서는 실제 문제가 되는 애매한 제한된 스패닝 체인 트리의 알고리즘을 명확하게 기술하고 TinyOS와 TOSSIM에서 A-PEGASIS를 구현하기 위한 기타 방법들을 기술한다. 섹션 4는, TinyOS와 TOSSIM위에서 구현된 A-PEGASIS의 Coordinator 선출 과 체인 변경에 실제 예를 제시하며 성능 결과치를 제공한다.

2. IMPLEMENTATION CHALLENGES

제안된 A-PEGISIS 알고리즘을 구현 하기 위해서 우리는 아래와 같은 몇 가지 문제를 해결 해야 했다.

1. 슈퍼라운드 변경 시까지 생성된 체인을 모두 동기화 하기 위한 정보 공유.
2. A-PEGASIS에서 제안된 제한된 스패닝 체인을 구성하기 위한 실제 알고리즘의 부재
3. A-PAGASIS에서 사용되는 가중치를 구하기 위한 도출 식들의 가정을 실제 구현에 반영하는 문제
4. 기존 LEACH를 변경 하는 것이 아니라 새로운 모듈을 작성 하는 수준의 구현사항
5. 각 노드들의 위치 정보를 TinyOS가 제공하지 않음으로써 발생하는 환경 정보 가공 문제

첫째, TinyOS와 NesC의 구조상, 각 노드들은 하나의 코드를 공유하여 인스턴스를 생성한다. LEACH에 구현된 MHLeachPSM 모듈을 기반으로 구현을 되짚어보면 각 노드들은 다른 노드들의 정보를 하나의 전역 변수에 선언하여 이를 공유하게 되는데 이 정보들을 Advertise라는 커뮤니케이션 방식에 따라서 이를 공유한다. 여기서 공유하게 되는 것은 노드들의 에너지, 노드 주소, 클러스터헤더인지 아닌지, 노드가 살아 있는지 아닌지 정도를 공유하게 된다. A-PEGASIS와 본 기술 문서에서 제시된 변형된 Kruskal의 제한된 스패닝 체인 트리는 각 노드간의 edge정보, 방향성, 그리고 논문의 도출식에 의해서 계산된 가중치 정보들은 튜플 형태의 벡터로 구성되고 완전한 정보를 제공하기 위해 완전 그래프(Complete Graph)형태로 제시 되기 때문에 데이터 사이즈가 커서 advertise와 같은 프로토콜로 공유 될 수 없다. 따라서 TyniOS와 TOSSIM기반의 A-PEGASIS 구현에서는 매 노드에서 이를 공유하는 방법이 하나의 문제점으로 부각된다.

둘째, 제시된 A-PEGASIS의 알고리즘은 섹션 3의 구현과 해결책에서 다시 한번 제시 되겠지만 크게 3가지로 프로시저로 분류된다. 가중치 계산을 처음 진행하고 이에 따라 제한된 Kruskal 스패닝 체인 트리를 형성한 뒤 링크간 스와핑의 적용이 가능한 경우 이를 해결 해야 한다. 문제는 토폴로지를 형성에 핵심이 되는 제한된 스패닝 체인 트리의 형성에 있다. 우선적으로 Kruskal 알고리즘은 최소 가중치를 가지는 토폴로지를 형성하기 위해 유망 집합(Promising Set)을 사용하는데 Kruskal에 의해 원래 그래프와 완전이 서로소인 솔루션 유망 집합을 얻고 나면 이를 체인으로 변경하는데 문제가 발생한다. 왜냐하면 트리를 끊어내는 방식으로 체인을 형성하면 그래프간의 단절이 발생하고 이 때문에 하나의 coordinator로 base station과 통신할 수 없는 문제가 발생한다. 이 부분에 대해서 A-PEGASIS는 의사수준의 알고리즘도 제공하고 있지 않다. 이 문제에 대해서는 섹션 3에서 다시 좀 더 구체화 하여 토론 해보도록 하겠다.

마지막으로, A-PEGASIS는 가중치 계산과 Coordinator선출에 있어서 각 노드들의 위치를 기반으로 한 거리를 판단 할 수 있어야 하며 에너지 잔량을 측정 할 수 있어야 한다. TyniOS와 TOSSIM기반의 시뮬레이션에서 작성된 A-PEGASIS 모듈은 이러한 환경 정보를 읽어오는데 한계가 있다. 따라서 본 기술 문서의 프로젝트 코드에서는 TOSSIM의 네트워크 형성을 Grid로 가정하고 각 거리를 계산 하였으며 에너지는 모든 노드가 동일하게 가지고 시작하며 스패닝 체인 정보 공유를 위해 Coordinator가 변경 되는 순간에 일괄적으로 이를 반영하는 가정을 포함한다. 또한 본 프로젝트는 원래 LEACH 코드를 이해하고 이를 개선 방법을 공부하는 것과 함께 LEACH를 완전히 대체하는 A-PEGASIS 모듈을 따로 작성하였다.

3. DETAILED IMPLEMENTATION AND SOLUTIONS

3.1 Kruskal Spanning Tree

최소 신장 비용 트리(Minimum Spanning Tree)를 위하여 첫 번째로 구현된 Kruskal Algorithms은 구현 된 소스의 A-PEGASIS 모듈의 BuildMST() 인터페이스를 통해 이루어진다. 기존 PEGASIS 논문과 A-PEGASIS 논문에서 제시된 알고리즘은 모두 토폴로지 형성에 있어서 Node Degree와 Adjacent Node가 2인 특수 트리인 체인을 통해서 만들어진다. 기존 PEGASIS의 논문에서는 Prim Algorithms을 통해서 PEGASIS 체인을 형성하지만 서창진과 양진웅에 의해서 구현된 A-PAGASIS는 최소 신장 비용 트리를 형성하는 Kruskal Algorithm에 f가 2d인 제약사항을 가하여 토폴로지를 형성한다.

Table 1 Kruskal 스패닝 트리 구현 알고리즘

Figure 2은 스타를 내포한 육각형 네트워크의 중심에 base station이 있고 설명의 편의를 위하여각 edge마다 에너지와 distance를 고려한 가중치가 숫자로 주어져 있다. Kruskal Algorithms은 Figure 2에서 볼 수 있듯이 우선적으로 가중치가 낮은 순서대로 edge를 소팅하여 가중치가 낮은 edge부터 최소 비용 신장 트리에 삽입을 고려한다. 이때 가중치로만 고려를 하기 때문에 base station을 포함한 edge임은 고려 대상이 아니다. 최소 비용 신장 트리에 삽입 되기전에 Kruskal Algorithms에서는 포리스트(Forest)로 불리는 유망집합(Promising set)들(Figure에는 회색으로 표기된 것들 것 각각의 유망 집합들이다)을 각각 구성하고 최소 가중치를 가진 edge부터 유망 집합에 병합하는 작업을 진행한다.(여기서 유망 집합은 생성 되기 전까지 node개수만큼 많은 독립된 집합으로 형성이 가능하다) 이렇게 유망 집합은 공집합으로 시작하여 Figure 2에 주어진 모든 노드들을 유망 집합에 삽입하고 기존 집합과 서로소가 될 때 이를 종료한다. Table 1는 A-pegasis 모듈을 BuildMST 인터페이스에 구현된 소스의 의사코드를 기술하고 있다.

3.2 Limited Spanning Chain Tree

A-PEGASIS에서는 제한된 스패닝 체인 트리를 형성한다. 서창진과 양진웅에 의해서 제시된 스패팅 체인 트리 절차는 대략적으로 아래와 같다.

1. 거리와 남은 에너지를 가지고 각 edge마다 가중치를 계산
2. 가중치를 바탕으로 Kruskal 알고리즘을 통하여 스패닝 트리를 형성
3. 스패닝 트리의 링크 스와핑.

거리와 남은 에너지를 가지고 계산하는 가중치는 A-PEGASIS의 방식을 TyniOS와 TOSSIM에서 사용이 가능한 정보와 가정수준에서 새로 구성하였으며 에너지 도출 식(1,2)은 아래와 같다.

Table 2 본 기술문서에서 제시되고 작성된 제한된 스패닝 체인 트리 구성 알고리즘

에너지를 통한 가중치가 계산되면 스패팅 체인 트리를 형성 해야 하는데 여기에는 섹션 2에서 언급되었던 문제가 발생한다. 유망 집합과 원래 입력 그래프의 서로소 상태를 확인 하며 스패닝 트리를 형성한 뒤 다시 제한된 스페닝 체인을 형성하기 위하여 트리를 잘라 체인을 만들면 그래프가 분리되어 하나 이상의 Coordinator가 선출 되는 문제가 발생한다. 이 부분의 기술이 미흡한 관계로 우리는 Table 2에서 제시된 알고리즘 대로 방문 노드와 방문 노드로부터 인접한 노드들의 가중치를 고려하여 다시 스패닝 트리를 작성하였다.

Figure 3는 본 기술 문서에서 해결책으로 작성된 제한된 스패닝 체인 트리의 작성 세부 절차를 보여 준다.

4. EVALUATION

4.1 Coordinator 변경 실례

우리는 솔루션에 제시되고 논문이 기술 된 바대로 슈퍼 라운드마다 스패닝 체인을 형성하여 coordinator를 재선정한다. Figure XX는 TyniOS와 TOSSIM에서 실제 구현된 결과를 반영하여 슈퍼라운드시 마다 실제 체인 형성이 완전히 새로 구성되며 이를 통하여 새로 선정된 coordinator와 base station간의 통신 상태를 보여준다.

<Figure 4, 새로 생성되는 스패닝 체인과 Coordinator 변경 실례>

이러한 체인 재 형성과정과 재 선정된 coordinator는 이론적으로 A-PEGASIS의 100% 퓨전이 가능하다고 가정하면 LEACH에서 발생하는 문제인 특정 영역 밀집 현상과 클러스터마다 클러스터 헤더가 base station과 통신하는 비용 및 이로 인한 에너지 절감 효과가 충분히 가능하다는 사실을 보여준다.

4.2 데드 노드 빈도수

성능 결과치를 도출 하기 위해 우리는 각 edge간 거리를 기본 유닛을 1으로 설정하고 최소거리 1, 최대 거리가 3으로 가정하였다. 디스턴스 팩터(Distance Factor)는 거리 1일 때 40, 2일 때 80, 3일 때 120으로 설정하였다. 에너지를 구하는 식은 모든 노드가 초기 1000이라는 값으로 에서 시작을 하고 슈퍼라운드를 결정하는 각 라운드의 이전 노드가 가지고 있던 에너지에서 디스턴스 펙터를 감산한다.

<Figure 5, 데드노드 빈도수 – 1차 시도>

<Figure 6, 데드노드 빈도수 – 2차 시도>

Figure XX를 통한 결과치는 각각 1차 2차, 3차 시도를 표현하고 있다. LEACH의 경우 클러스터 헤더를 확률적 선택방법에 의존하여 랜덤하게 추출하기 때문에 하기 때문에 재선정 되고 전체 시뮬레이션 기간 동안 각 노드가 처리해야 하는 빈도수가 A-PEGASIS보다 높기 때문에 일찍 죽을 수 있다는 것을 설명한다. 반면에 A-PEGASIS는 coordinator는 클러스터가 아닌 전체 스패닝 체인에 따라 선출 기회가 균등하게 이루어 지기 때문에 시간이 지남에 따라 죽는 빈도가 낮다.

4.2 시간대 별 평균 잔존 에너지량.

평균 에너지는 총 노드에 잔존 에너지들의 합을 총 가정 노드 수(6)을 통해 산술적 평균으로 구해진다. Figure XX는 LEACH는 클러스터 헤더들이 A-PEGASIS 보다 많이 선출 되기 때문에 A-PEGASIS비하여 Base station과 통신을 하기 위해 에너지를 많이 소비하게 된다. 반면에 A-PEGASIS는 전체 체인에서 하나의 coordinator 를 균일하게 선출하기 때문에 좀 더 안정적인 결과를 보여준다.

<Figure 7, 시간대별 평균 잔존 에너지량>

<Figure 6, 각 실험 별 통계 수치>

5. CONCLUSION

위에 기술한 결과를 통해서 보면 A-PEGASIS가 LEACH보다 모트들의 에너지 특성을 더 효율적으로 고려한다는 것을 알 수 있고더 나은 성능을 보여주었다. LEACH도 역시 WSN의 효율적인 이용을 위해 고안된 프로토콜이긴 하지만 각 클러스터의 헤더를 선출하는 방법에 있어서 Random하게 선출하기에 때문에 각 모트의 에너지 상태를 반영하지 못한다는 한계를 가지고 있다. 즉, 헤더가 자신의 클러스터에 속한 다른 모트들로부터 받은 데이터를 퓨징하여 베이스 스테이션으로 한꺼번에 전달하게 되는데 네트워크의 규모가 커질 수 록 클러스터의 개수가 늘어나게 되고 클러스터의 헤더들은 다른 모트들보다 더 많은 에너지를 소비하게 된다. 이 때 헤더의 선출에 남은 에너지량을 고려하지 않고 Random하게 헤더를 선출하게 되므로 직전 라운드에 헤더였던 노드가 다시 선택된다면 그 모트는 빨리 에너지가 고갈될 수 밖에 없다. 이러한 문제점을 A-PEGASIS가 해결해 주었다는 것을 본 문서의 결과를 통해 알 수 있었다. 네트워크의 체인을 형성하고 헤더를 선출하는 과정에 있어서 각 모트와 베이스 스테이션사이의 거리, 그리고 각 모트의 남은 에너지량을 통해서 가장 베이스 스테이션과의 비용이 적은 모트를 각 라운드마다 선출함으로써 전체적인 모트들의 평균 에너지량을 균일하게 맞출 수 있었고 각 모트들의 수명 또한 더 오래 지속될 수 있었다. 실험치는 TinyOS와 TOSSIM환경 위에서 구현된 A-PEGASIS 통신 방식은 기준 LEACH에 비해서 에너지 소비량(산술적 평균) 24% 향상, Base station과 통신을 위해 각 노드들의 생존량이 1.85~3배 정도되는 것을 보여 준다.

6. REFERENCE

[1] 서창진, 양진웅, "개선된 센서 라우팅 방식 : A-PEGASIS (A-PEGASIS : Advanced Power Efficient GAthering in Sensor Information Systems)", 2007 12, 정보 과학회

[2] Stephanie Lindsey, Cauligi S. Raghavendra,, "PEGASIS: Power-Efficient Gathering in Sensor

Information Systems"

[3] D. Estrin, R. Govindan, J. Heidemann, and Satish Kumar. "Next Century Challenges: Scalable Coordination in Sensor Networks. In Proceedings of Mobicom" 99, 1999.

[4] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan." Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proceedings of the Hawaii Conference on System Sciences", Jan. 2000.