Project_3 : Virtual Memory - Introduction

앞선 프로젝트 수행을 통해 현재 Pintos는 동기화를 이용한 여러 스레드의 실행, 다양한 사용자 프로그램의 로드 등을 할 수 있게 되었다.

그러나 여전히 실행할 수 있는 프로그램의 수와 크기는 메인 메모리 크기에 의해 제한된 상태이다.

이번 프로젝트는 이러한 제한을 극복하는 과정이 될 것이다.

Source Files

이번 프로젝트는 vm 디렉터리에서 작업이 이루어질 것이다. 많은 양의 템플릿 코드들이 제공되는데, 지정된 템플릿을 따라야 한다.

주어진 템플릿을 기반으로 하지 않은 코드는 정상적으로 실행되지 않을 수 있다. 

"DO NOT CHANGE"라고 표시된 템플릿은 절대 변경하지 말아야 한다. 아래는 수정해야 할 템플릿 파일에 관한 세부 정보들이다.

include/vm/vm.h
vm/vm.c

 

가상 메모리에 대한 인터페이스를 제공한다.

헤더 파일에서 가상 메모리 시스템이 지원해야 하는 다양한 VM_type(VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE)에

대한 정의와 설명을 볼 수 있다. 다만, VM_PAGE CACHE는 네 번째 프로젝트를 위한 것으로 현재 프로젝트에서는 다루지 않는다.

추가 페이지 테이블 역시 여기서 구현한다.

include/vm/uninit.h
vm/uninit.c

 

초기화되지 않은 페이지에 대한 작업을 제공한다(vm_type = VM_UNINIT).

현재 상태에서는 모든 페이지가 초기화되지 않은 페이지로 설정된 다음, 익명 페이지 또는 파일 백업 페이지로 변환된다.

include/vm/anon.h
vm/anon.c

 

익명 페이지에 대한 작업을 제공한다(vm_type = VM_ANON).

include/vm/file.h
vm/file.c

 

파일 백업 페이지에 대한 작업을 제공한다(vm_type = VM_FILE).

include/vm/inspect.h
vm/inspect.c

 

메모리 검사 작업을 포함한 파일로 변경해서는 안된다.

 

앞서 언급하였듯 이번 프로젝트는 대부분 vm 디렉터리와 이전 프로젝트에서 다루었던 파일들에서 이루어진다.

일부 새롭게 보게 될 파일들도 있는데 아래 파일이 그중 하나이다.

include/devices/block.h
devices/block.c

 

block device에 대한 섹터 기반 읽기/쓰기 액세스를 제공한다. swap partition에 접근하기 위해 해당 인터페이스를 사용할 것이다.

Memory Terminology

Pages

페이지는 크기가 4KB인 가상 메모리의 연속적인 영역을 의미한다.

페이지는 정렬 상태, 즉 페이지 크기로 균등하게 구분되는 가상 주소에서 시작해야 한다.

64비트 가상 주소의 마지막 12비트는 페이지 오프셋이며, 상위 비트는 페이지 테이블의 인덱스를 나타내는 데 사용한다.

64비트 시스템에서는 아래와 같이 각각이 9비트인 4단계 페이지 테이블을 이용하여 가상 주소를 만든다.

 

Pintos에서 가상 메모리는 사용자 가상 메모리와 커널 가상 메모리, 두 영역으로 나뉜다.

두 영역 사이의 경계는 KERN_BASE(0x8004000000)이다.

따라서 각 프로세스에는 가상 주소 KERN_BASE 아래의 독립적인 사용자(가상) 페이지 세트가 있다.

반면에 커널(가상) 페이지 세트는 전역적이므로 어떤 스레드나 프로세스가 실행 중인지에 관계없이 같은 위치에 남아 있다.

커널은 사용자 페이지와 커널 페이지 모두에 액세스 할 수 있지만 사용자 프로세스는 자신의 사용자 페이지에만 액세스 할 수 있다.

 

Frames

프레임(물리적 프레임 or 페이지 프레임)은 물리 메모리의 연속적인 영역을 의미한다.

페이지와 마찬가지로 프레임도 페이지 크기와 같아야 하고 해당 크기로 정렬되어야 한다.

64비트 물리적 주소는 12비트의 프레임 오프셋과 나머지 비트의 프레임 넘버로 구성된다.

 

x86-64는 물리적 주소의 메모리에 직접 액세스 할 수 있는 방법을 제공하지 않는다.
핀토스는 커널 가상 메모리를 물리적 메모리에 직접 매핑함으로써 이 문제를 해결한다.

커널 가상 메모리의 첫 번째 페이지는 물리적 메모리의 첫 번째 프레임에 매핑되고, 두 번째 페이지는 두 번째 프레임에 매핑된다.

 

 

Page Tables

페이지 테이블은 CPU가 가상 주소를 실제 주소로 변환하기 위해 사용하는 데이터 구조이다.

페이지 테이블 형식은 x86-64 아키텍처에 의해 결정된다.

Pintos는 페이지 테이블 관리 코드를 threads/mmu.c 에서 제공하고 있다.

아래 다이어그램은 페이지와 프레임 간의 관계를 보여준다. 왼쪽의 가상 주소는 페이지 번호와 오프셋으로 구성된다.

페이지 테이블은 페이지 번호를 프레임 번호로 변환하고 이를 오프셋과 결합하여 오른쪽의 실제 주소를 가져온다.

 

Swap Slots

스왑 슬롯은 스왑 파티션에 위치한 디스크 공간의 페이지 크기 슬롯을 의미한다. 

Resource Management Overview

아래와 같은 데이터 구조를 설계/구현해야 한다. 반드시 완전히 다른 데이터 구조를 구현할 필요는 없다.

관련 리소스를 전체적으로 또는 부분적으로 병합하는 것이 편리할 수 있다. 각 데이터 구조가 포함해야 하는 정보를 결정해야 한다.

또한, 프로세스 별 혹은 전체 시스템에 적용할 데이터 구조의 범위를 정해야 한다. 그리고 해당 범위에 필요한 인스턴스 수를 결정해야 한다.

설계를 단순화하기 위해 이러한 데이터 구조를 non-pageable memory(calloc 또는 malloc에 의해 할당된 메모리)에 저장할 수 있다.

 

Supplemental Page Table

페이지 테이블을 보완하여 페이지 폴트 처리를 가능하게 한다.

 

Frame Table

물리적 프레임의 제거 정책을 효율적으로 구현할 수 있게 한다.

 

Swap table

스왑 슬롯의 사용을 추적한다.

 

Choices of implementation

위의 내용을 구현할 때 선택할 수 있는 옵션으로는 array, lists, bitmaps, hash tables 등이 있다.

array는 가장 간단한 접근 방식이지만 많은 것을 담고 있지 않은 배열은 메모리를 낭비한다. 

lists 또한 간단하다. 그러나 특정한 위치를 찾기 위해 긴 목록을 탐색하는 것은 시간을 낭비한다.

 

Pintos는 lib/kernel/bitmap.c에 bitmaps 자료 구조를 구현해놓았다. bitmaps은 비트의 배열로, 각각이 참 혹은 거짓이다.

bitmaps은 일반적으로 동일한 리소스 집합의 사용을 추적하는데 사용된다. 예를 들어, 리소스 n이 사용중이면 비트 n은 참이다.

Pintos에서 제공하는 bitmaps은 크기가 고정되어 있다. 다만, 크기 조정을 지원하도록 구현을 확장할 수 있다.

 

Pintos는 hash tables 자료 구조를 제공한다. 이는 삽입과 삭제를 효율적으로 지원한다.

더 복잡한 자료구조가 더 나은 성능과 이득을 산출해낼 수 있지만, 구현이 불필요하게 복잡해질 수 있다.

Managing the Supplemental Page Table

Supplemental Page Table은 각 페이지에 대한 추가적인 데이터를 바탕으로 페이지 테이블(page table)을 보완한다.

이는 페이지 테이블 형식이 갖는 제약 때문에 필요하다. 이러한 데이터 구조를 page table이라고 부르기도 한다.

혼동을 줄이기 위해 supplemental이라는 단어를 추가하여 Supplemental Page Table이라 하였다.

 

Supplemental Page Table은 최소한 두 가지 목적으로 사용된다. 

가장 중요한 것은 페이지 폴트(page fault) 발생 시, 어떤 데이터가 있어야 하는지 확인하기 위해 페이지 폴트가 발생한 가상 페이지를

조회할 때 사용한다. 두 번째로, 프로세스가 종료할 때 어떤 자원을 해제할지 결정하기 위해 사용한다.

 

Organization of Supplemental Page Table

원하는 대로 Supplemental Page Table을 구성할 수 있다. 구성은세그먼트 혹은 페이지 기준으로 가능하다.

여기서 세그먼트란 연속적인 페이지 그룹을 의미한다. 

페이지 테이블 그 자체를 Supplemental Page Table의 멤버를 추적하기 위해 사용할 수 있다.

이를 위해서는 threads/mmu.c 에 구현되어 있는 Pintos 페이지 테이블을 수정해야만 한다.

 

Handling Page Fault

Supplemental Page Table의 가장 중요한 사용자는 페이지 폴트 핸들러이다. 

두 번째 프로젝트에서 페이지 폴트는 항상 커널이나 사용자 프로그램의 버그를 나타냈다. 

이번 프로젝트부터는 페이지 폴트가 발생하면, 파일 또는 스왑 슬롯에서 페이지를 가져와야 함을 나타내는 것일 수 있다.

이러한 경우를 처리하려면 더 정교한 페이지 폴트 핸들러를 구현해야 한다. 

userpog/exception.c의 page_fault( ) 함수는 vm/vm.c의 vm_try_handle_fault( ) 함수를 호출한다. 

페이지 폴트 처리기는 대략 다음의 작업을 수행해야 한다.

 

1. Supplemental Page Table에서 폴트가 발생한 페이지를 찾는다.

메모리 참조가 유효한 경우, 파일 시스템 또는 스왑 슬롯에 있는 데이터를 찾기 위해 Supplemental Page Table Entry를 사용한다.

공유(예: Copy-on-Write)를 구현할 경우, 페이지의 데이터가 페이지 프레임에는 있지만 페이지 테이블에는 없을 수 있다.

Supplemental Page Table이 유저 프로세스가 접근하려는 주소에 데이터가 없다고 알려주거나, 페이지가 커널 가상 메모리 내에 있거나,

읽기 전용 페이지에 쓰기를 시도하는 경우 해당 접근은 유효하지 않다. 유효하지 않은 접근은 프로세스를 종료하고 모든 자원을 해제한다.

 

2. 페이지를 저장할 프레임을 가져온다.

공유를 구현하는 경우, 필요한 데이터가 이미 프레임에 있을 수 있으며, 이 경우 해당 프레임을 찾을 수 있어야 한다.

 

3. 데이터를 프레임으로 가져온다.

파일 시스템 또는 스왑에서 데이터를 읽거나, 데이터를 0으로 초기화하는 방법이 가능하다.

공유를 구현할 경우, 필요한 페이지가 이미 프레임에 있을 수 있으며, 해당 경우 이 단계의 수행은 필요하지 않다.

 

4. 페이지 폴트가 발생한 페이지 테이블 항목을 실제 페이지(물리 주소)를 가리키게 한다.

이는  thread/mmu.c의 기능을 사용할 수 있다.

Managing the Frame Table

프레임 테이블에는 각 프레임에 대한 하나의 항목이 있다. 프레임 테이블의 각 항목에는 페이지에 대한 포인터와 다른 데이터가 포함된다.

프레임 테이블은 핀토스가 가용한 프레임이 없을 때, 방출 페이지를 선택하는 것을 도와 효율적으로 방출 정책을 구현할 수 있도록 한다.

 

사용자 페이지에 사용되는 프레임은 palloc_get_page(PAL_USER) 함수를 호출함으로써 "user pool"에서 가져와야 한다.

"kerner pool"에서 할당받는 것을 피하기 위해 PAL_USER를 사용해야 한다.

프레임 테이블 구현의 일부로 palloc.c 를 수정한다면, 두 pool 사이의 차이를 유지해야 한다.

 

프레임 테이블에서 가장 중요한 작업은 사용하지 않는 프레임을 얻는 것이다. 프레임이 가용할 때 이것은 쉽다.

그러나 어떤 프레임도 가용하지 않을 때 프레임에서 페이지를 방출하여 프레임을 가용한 상태로 만들어야 한다.

 

스왑 슬록을 할당하는 방법 외에 어떤 프레임도 제거할 수 없는 상황에서, 스왑이 가득차있다면 커널은 패닉 상태에 빠진다.

실제 운영체제는 이러한 상황을 복구하거나 예방하기 위해 광범위한 정책을 적용하지만 이러한 정책들은 이번 프로젝트의 범위를 넘는다.

 

방출 과정은 대략 다음과 같은 단계로 구성된다.

1. 페이지 교체 알고리즘을 사용하여 방출할 프레임을 선택한다. 이때 페이지 테이블의 "accessed"와 "dirty" 비트가 유용하다.

2. 해당 프레임을 참조하고 있는 페이지 테이블의 참조를 제거한다. 공유를 구현하지 않았다면 한 페이지만 해당 프레임을 참조해야 한다.

3. 필요한 경우 페이지를 파일 시스템 또는 스왑에 기록한다. 제거된 프레임은 다른 페이지를 저장하는 데 사용될 수 있다.

Accessed and Dirty Bits

x86-64 하드웨어는 페이지 테이블 항목(Page Tabe Entre)의 비트 쌍을 통해 페이지 교체 알고리즘 구현을 지원한다.

페이지를 읽거나 무언가를 쓰는 경우, CPU는 PTE의 접근 비트(accessed bit)를 1로 설정한다.

페이지에 무언가를 쓰는 경우, CPU는 더티 비트(dirty bit)를 1로 설정한다. 

CPU는 절대 해당 비트들을 0으로 재설정하지 않지만, OS는 재설정 할 수 있다.

 

별칭(aliases), 즉 동일한 프레임을 참조하는 두 개 이상의 페이지에 대해 알고 있어야 한다.

별칭 프레임(aliased frame)이 액세스 될 때, 액세스에 사용되는 오직 한 PTE에서만 접근 비트와 더티 비트를 업데이트 해야 한다.

다른 PTE의 접근 비트와 더티 비트는 업데이트되지 않는다.

 

Pintos에서 모든 사용자 가상 페이지는 커널 가상 페이지의별칭으로 지정된다.

따라서 두 주소 모두에서 접근 비트와 더티 비트를 확인하고 업데이트 할 수 있다.

하지만 커널은 사용자 가상 주소를 통해서만 사용자 데이터에 접근해야 한다.

Managing the Frame Table

스왑 테이블은 사용 중인 스왑 슬롯과 사용 가능한 스왑 슬롯을 추적한다.

프레임에서 스왑 파티션으로 페이지를 방출하기 위해 사용하지 않는 스왑 슬롯을 선택할 수 있어야 한다.

페이지를 다시 읽거나 페이지가 스왑된 프로세스가 종료될 경우, 스왑 슬롯을 해제할 수 있어야 한다.

 

vm/build 디렉토리에서 n-MB 크기의 스왑 파티션을 갖는 swap.dsk 를 생성하기 위해 아래의 명령어를 입력해라.

pintos-mkdisk swap.dsk --swap-size=n

이후, Pintos를 실행하면 swap.dsk가 자동으로 추가 디스크로 첨부된다.

스왑 슬롯은 게으르게 할당되어야 한다. 즉, 방출로 인해 필요한 경우에만 할당되어야 한다.

실행 파일에서 데이터 페이지를 읽고 프로세스 시작 시 즉시 스왑 하도록 데이터를 쓰는 것은 게으른 것이 아니다.

스왑 슬롯은 특정 페이지를 저장하기 위해 예약되어서는 안된다.

스왑 슬롯의 내용을 프레임으로 다시 읽으면 슬롯을 해제한다.

Managing Memory Mapped Files

읽기 및 쓰기 시스템 콜 시 파일 시스템 접근이 가장 빈번하게 일어난다. 2차적인 인터페이스는 mmap 시스템 콜을 사용하여

파일을 가상 페이지에 매핑하는 것이다. 그러면 프로그램은 파일 데이터에 직접 메모리 명령을 사용할 수 있다.

foo 파일의 길이가 0x1000 바이트(4KB, 또는 한페이지)라고 가정해보자.

foo의 매핑된 주소가 0x5000에서 시작한다면, 주소 0x5000에서 0x5fff 사이의 메모리 접근은 foo에 대응하는 접근일 것이다.

 

매핑된 지역에서의 페이지 폴트를 적절히 처리하고,

매핑된 파일이 프로세스 내 다른 세그먼트와 겹치지 않도록 하려면 매핑된 파일이 어떤 메모리를 사용하고 있는지 추적할 수 있어야 한다.