[CS] PintOS Project 3 - Virtual Memory(1) - Introduction

이제 Pintos의 내부 작동 방식에 익숙해져야 합니다. 운영 체제는 적절한 동기화로 여러 스레드의 실행을 제대로 처리할 수 있으며, 여러 사용자 프로그램을 한 번에 로드할 수 있습니다. 그러나 프로그램의 수와 크기는 컴퓨터의 메인 메모리 크기에 제한이 따릅니다. 이번 과제에서는 이러한 제한을 제거하기 위해 무한 메모리의 환상을 제공(구축)할 것입니다.

 

이번 과제는 지난 과제에 지속하여 진행할 것입니다. 프로젝트 2의 테스트 프로그램도 프로젝트 3과 함께 작동해야 합니다. 프로젝트 3을 시작하기 전에 프로젝트 2 제출 시 발생할 수 있는 버그를 수정해야 합니다. 이러한 버그가 프로젝트 3에서도 동일한 문제를 일으키기 때문입니다.

 

프로젝트 3에 대해, 여러분의 쉽게 진행할 수 있도록 자세한 지침을 제공합니다. 

 

Background (배경)

---

이번 프로젝트에서는 vm 디렉토리에서 작업할 것입니다. Makefile이 -DVM 설정을 켜도록 업데이트되었습니다. 제공하는 템플릿 코드는 매우 많습니다. 제공된 템플릿을 절대 준수해야 합니다. 즉, 제공된 템플릿을 기반으로하지 않은 코드를 제출하면 0점이 될 것입니다. 또한 "DO NOT CHANGE"로 표시된 곳은 절대로 수정해서는 안됩니다. 여기서는 수정할 각 템플릿 파일에 대한 자세한 정보를 제공합니다.

 

Source Files

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

가상 메모리의 일반적인 인터페이스를 제공합니다. 헤더 파일에서 지원해야 할 다양한 vm_type (VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE)의 정의와 설명을 볼 수 있습니다 (일단은 VM_PAGE_CACHE은 무시하고, 프로젝트 4에서 사용할 것입니다). 여기에서 추가 페이지 테이블을 구현할 것입니다 (아래 참고).

 

include/vm/anon.h, vm/anon.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

블록 장치에 대한 섹터 기반 읽기 및 쓰기 액세스를 제공합니다. 이 인터페이스를 사용하여 스왑 파티션을 블록 장치로 액세스할 것입니다.

 

Memory Terminology (메모리 용어)

---

먼저 메모리와 저장소에 대한 용어를 소개합니다. 이 용어 중 일부는 프로젝트 2에서 익숙해질 수 있을 것입니다 (Virtual Memory Layout 참고), 그러나 대부분은 새로운 용어입니다.

 

Page (페이지)

페이지는 종종 가상 페이지라고도 하며, 길이가 4,096 바이트(페이지 크기)인 가상 메모리의 연속된 영역입니다. 페이지는 페이지 정렬되어야 합니다. 즉, 페이지 크기로 정확히 나눌 수 있는 가상 주소로 시작해야 합니다. 따라서 64비트 가상 주소의 마지막 12비트는 페이지 오프셋(또는 그냥 오프셋)이 됩니다. 상위 비트는 곧 소개될 페이지 테이블의 색인을 지정하는 용도로 사용됩니다. 64비트 시스템에서는 4단계 페이지 테이블을 사용하므로, 가상 주소는 다음과 같이 보일 것입니다:

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

 

각 프로세스는 자신만의 사용자(가상) 페이지 집합을 가지고 있습니다. 이는 가상 주소 KERN_BASE(0x8004000000) 아래에 있는 페이지들을 의미합니다. 반면에 커널(가상) 페이지 집합은 전역적으로 존재하며, 어떤 스레드나 프로세스가 실행 중이더라도 위치는 고정됩니다. 커널은 사용자 페이지와 커널 페이지 모두에 액세스할 수 있지만, 사용자 프로세스는 자신의 사용자 페이지만 액세스할 수 있습니다. 자세한 정보는 Virtual Memory Layout을 참고하십시오.

 

Pintos는 가상 주소를 작업할 때 유용한 여러 가지 기능을 제공합니다. 자세한 내용은 Virtual Addresses 섹션을 참고하십시오.

 

Frames (프레임)

프레임은 종종 물리적 프레임이나 페이지 프레임이라고도 하며, 물리적 메모리의 연속된 영역입니다. 페이지와 마찬가지로 프레임도 페이지 크기와 페이지 정렬되어야 합니다. 따라서 64비트 물리 주소는 프레임 번호와 프레임 오프셋(또는 그냥 오프셋)으로 나눌 수 있습니다. 예를 들어:

                          12 11         0
    +-----------------------+-----------+
    |      Frame Number     |   Offset  |
    +-----------------------+-----------+
              Physical Address

x86-64은 물리 주소로 직접 메모리에 액세스할 수 있는 방법을 제공하지 않습니다. Pintos는 커널 가상 메모리를 직접 물리 메모리에 매핑하는 방법으로 이를 극복합니다. 즉, 커널 가상 메모리의 첫 번째 페이지는 첫 번째 물리 메모리 프레임, 두 번째 페이지는 두 번째 프레임, 이하 순서대로 매핑됩니다. 따라서 프레임은 커널 가상 메모리를 통해 액세스할 수 있습니다.

 

Pintos는 물리 주소와 커널 가상 주소 사이를 변환하는 기능을 제공합니다. 자세한 내용은 Virtual Addresses를 참고하십시오.

 

Page Tables (페이지 테이블)

페이지 테이블은 CPU가 가상 주소를 물리 주소로 변환할 때 사용하는 데이터 구조입니다. 즉, 페이지에서 프레임으로 변환할 때 사용합니다. 페이지 테이블 형식은 x86-64 아키텍처에 의해 정의됩니다. Pintos는 threads/mmu.c에 페이지 테이블 관리 코드를 제공합니다.

 

다음의 다이어그램은 페이지와 프레임 간의 관계를 보여줍니다. 왼쪽의 가상 주소는 페이지 번호와 오프셋으로 구성됩니다. 페이지 테이블은 페이지 번호를 프레임 번호로 변환하고, 이는 수정되지 않은 오프셋과 결합되어 오른쪽의 물리 주소를 얻게 됩니다.

 

                          +----------+
         .--------------->|Page Table|-----------.
        /                 +----------+            |
        |   12 11 0                               V  12 11 0
    +---------+----+                         +---------+----+
    | Page Nr | Ofs|                         |Frame Nr | Ofs|
    +---------+----+                         +---------+----+
     Virt Addr   |                            Phys Addr    ^
                  \_______________________________________/

Swap Slots (스왑 슬롯)

스왑 슬롯은 스왑 파티션의 디스크 공간 중 페이지 크기 영역입니다. 슬롯의 위치를 결정하는 하드웨어 제약 조건은 프레임과 비교해서는 유연하지만, 스왑 슬롯은 페이지 정렬되어 있어야 합니다. 이렇게 하는 것에는 단점이 없기 때문입니다.

 

Resource Management Overview (자원 관리 개요)

---

다음과 같은 데이터 구조를 설계/구현해야 합니다:

 

Supplemental page table

페이지 테이블을 보조하여 page fault 처리를 가능하게 합니다.
자세한 정보는 아래에서 보조 페이지 테이블의 관리를 참고하십시오.

Frame table

물리 프레임의 추방 정책을 효율적으로 구현할 수 있게 합니다.
자세한 정보는 아래에서 프레임 테이블의 관리를 참고하십시오.

Swap table

스왑 슬롯의 사용을 추적합니다.
자세한 정보는 아래에서 스왑 테이블의 관리를 참고하십시오.

세 개의 완전히 다른 데이터 구조를 구현할 필요는 없습니다:

연관된 자원을 통합하여 하나의 데이터 구조로 통합할 수 있을 것입니다.

 

각 데이터 구조에 대해, 각 요소가 포함해야 할 정보를 결정해야 합니다. 또한, 정의 영역이 지역(프로세스 당 하나)인지 전역(전체 시스템에 적용)인지, 그리고 그 정의 영역 내에서 필요한 인스턴스의 수를 결정해야 합니다.

 

디자인을 단순화하기 위해, 이러한 데이터 구조를 페이지 가능하지 않은 메모리(예: calloc 또는 malloc으로 할당된 메모리)에 저장할 수 있습니다. 이는 이들 사이의 포인터가 유효한 것이 보장된다는 의미입니다.

 

Choices of implementation (Performance perspective) - 구현 선택 (성능 측면) 

구현에 사용할 수 있는 선택지로는 배열, 리스트, 비트맵, 해시 테이블이 있습니다. 배열은 종종 가장 간단한 접근 방법이지만, 적극적으로 사용되지 않은 배열은 메모리를 낭비할 수 있습니다. 리스트도 간단하지만, 특정 위치를 찾기 위해 긴 리스트를 순회하는 것은 시간을 낭비할 수 있습니다. 배열과 리스트 모두 크기를 조정할 수 있지만, 리스트는 중간에 삽입과 삭제를 더 효율적으로 지원합니다.

 

Pintos는 lib/kernel/bitmap.c와 include/lib/kernel/bitmap.h에 비트맵 데이터 구조를 포함하고 있습니다. 비트맵은 참과 거짓이 있는 비트의 배열입니다. 비트맵은 일반적으로 (동일한) 자원의 사용 여부를 추적하기 위해 사용됩니다: 자원 n이 사용 중이면, 비트맵의 n번째 비트는 참이 됩니다. Pintos 비트맵은 크기가 고정되어 있지만, 크기 조정을 지원하도록 구현을 확장할 수 있습니다.

 

Pintos는 또한 해시 테이블 데이터 구조(참고: 해시 테이블)를 포함하고 있습니다. Pintos 해시 테이블은 테이블 크기가 좁은 범위 내에서 삽입과 삭제를 효율적으로 지원합니다.

 

복잡한 데이터 구조가 성능이나 기타 이점을 제공할 수 있지만, 구현을 불필요하게 복잡하게 만들 수도 있습니다. 따라서 고급 데이터 구조(예: 균형 이진 트리)를 설계 일부로 구현하는 것을 추천하지 않습니다.

 

Managing the Supplemental Page Table (보조 페이지 테이블 관리)

---

보조 페이지 테이블은 각 페이지에 대한 추가 데이터로 페이지 테이블을 보조합니다. 이것은 페이지 테이블의 형식으로 인해 제한된 기능 때문에 필요합니다. 이러한 데이터 구조는 종종 "페이지 테이블"라고도 불립니다; 우리는 오해를 줄이기 위해 "보조"라는 단어를 추가합니다.

 

보조 페이지 테이블은 적어도 두 가지 용도로 사용됩니다. 가장 중요한 것은 page fault 발생 시, 커널은 어떤 데이터가 있어야 하는지 찾기 위해 보충 페이지 테이블에서 장애가 발생한 가상 페이지를 검색합니다. 두 번째로, 커널은 프로세스가 종료될 때 보조 페이지 테이블을 참조하여, 어떤 자원을 해제해야 하는지 결정합니다.

 

Organization of Supplemental Page Table (보충 페이지 표 구성)

보조 페이지 테이블을 원하는 대로 정리할 수 있습니다. 적어도 두 가지 기본적인 접근 방법이 있습니다: 세그먼트 단위로 구성하거나 페이지 단위로 구성하기. 여기서 세그먼트는 연속된 그룹의 페이지를 의미합니다, 즉, 실행 가능한 파일이나 메모리에 매핑된 파일이 포함된 메모리 영역입니다.

 

선택적으로, 보조 페이지 테이블의 구성원을 추적하기 위해 페이지 테이블 자체를 사용할 수 있습니다. 이를 위해서는 threads/mmu.c에 있는 Pintos 페이지 테이블 구현을 수정해야 합니다. 이러한 접근법은 숙련된 학생들에게만 추천합니다.

 

Handling page fault (page fault 처리)

보조 페이지 테이블을 가장 많이 사용하는 곳은 페이지 오류 핸들러입니다. 프로젝트 2에서는 page fault가 커널이나 사용자 프로그램의 버그를 의미하는 경우만 있었지만, 프로젝트 3에서는 이는 더 이상 성립하지 않습니다. 이제부터 page fault는 페이지가 파일이나 스왑 슬롯에서 가져올 필요가 있을 때 일어날 수 있습니다. 이러한 경우를 처리하기 위해서는 더 세련된 페이지 오류 핸들러를 구현해야 합니다. userprog/exception.c 에 있는 page_fault() 함수가 vm/vm.c 에 있는 vm_try_handle_fault() 함수를 호출합니다. 페이지 오류 핸들러는 아래와 같은 일을 수행해야 합니다.

 

1. 보조 페이지 테이블에서 오류가 발생한 페이지를 찾습니다. 메모리 참조가 유효하다면, 보조 페이지 테이블 항목을 사용하여 페이지에 저장될 데이터의 위치를 찾습니다. 이 데이터는 파일 시스템에 있거나 스왑 슬롯에 있거나, 또는 모두 0으로 채워진 페이지일 수 있습니다. 만약 복사 전송(즉, Copy-on-Write)을 구현한다면, 페이지의 데이터는 이미 페이지 프레임에 있을 수 있지만, 페이지 테이블에는 없을 수 있습니다. 만약 보조 페이지 테이블이 사용자 프로세스가 접근하려고 한 주소에 어떠한 데이터도 없음을 나타낸다면, 혹은 페이지가 커널 가상 메모리 안에 있다면, 혹은 접근이 읽기 전용 페이지에 쓰기 시도라면, 접근은 유효하지 않습니다. 어떠한 유효하지 않은 접근도 프로세스를 종료하고, 그로인해 그의 모든 자원을 해제합니다.
2. 저장할 페이지를 위한 프레임을 얻어야 합니다. 공유(sharing)를 구현한 경우, 필요한 데이터가 이미 프레임에 있을 수 있으며, 이 경우 그 프레임을 찾아야 할 것입니다.
3. 파일 시스템이나 스왑에서 읽거나 0으로 채우거나 같은 방법으로 프레임에 데이터를 가져와야 합니다. 공유를 구현한 경우, 필요한 페이지가 이미 프레임에 있을 수 있으므로 이 단계에서 어떠한 조치도 필요 없습니다.
4. 결함이 있는 가상 주소에 대한 페이지 테이블 항목이 물리적 페이지를 가리키도록 합니다. threads/mmu.c에 있는 함수를 사용할 수 있습니다.

 

Managing the Frame Table (프레임 테이블 관리)

---

프레임 테이블은 각 프레임을 위한 한 개의 엔트리를 포함합니다. 프레임 테이블의 각 엔트리는 현재 차지하고 있는 페이지(있는 경우)를 가리키는 포인터와 선택한 기타 데이터를 포함합니다. 프레임 테이블은 Pintos가 빈 프레임이 없을 때 제거할 페이지를 선택함으로써 제거 정책을 효율적으로 구현할 수 있게 합니다.

 

사용자 페이지에 사용되는 프레임은 palloc_get_page(PAL_USER)를 호출하여 "사용자 자원"에서 가져와야 합니다. 프레임 테이블 구현을 위해 palloc.c를 수정할 경우, "커널 자원"과 "사용자 자원"을 구분해야 합니다. 이를 생각하지 않을 경우, 일부 테스트 케이스가 예상치 않게 실패할 수 있습니다.

 

프레임 테이블에서 가장 중요한 작업은 사용하지 않는 프레임을 얻는 것입니다. 프레임이 비어 있을 때 이것은 쉽습니다. 사용 가능한 프레임이 없을 때, 프레임에서 일부 페이지를 제거하여 프레임을 사용할 수 있어야 합니다.

 

스왑 슬롯을 할당하지 않고 프레임을 제거할 수 없지만 스왑이 가득 찬 경우 커널을 패닉 상태로 만듭니다. 실제 OS는 이러한 상황에서 복구하거나 방지하기 위해 광범위한 정책을 적용하지만, 이러한 정책은 이 프로젝트의 범위를 벗어납니다.

 

 

제거 과정은 아래와 같은 단계로 구성됩니다:

1. 페이지 교체 알고리즘을 사용하여 제거할 프레임을 선택합니다. 페이지 테이블에서 설명한 "accessed"와 "dirty" 비트가 유용할 것입니다.
2. 프레임을 참조하는 모든 페이지 테이블에서 프레임에 대한 참조를 제거합니다. 공유를 구현하지 않았다면 한 시점에 한 페이지만 프레임을 참조해야 합니다.
3. 수정할 필요가 있다면, 파일 시스템 또는 스왑에 페이지를 쓴다. 추방된 프레임은 이후에 새로운 페이지를 저장하기 위해 사용될 수 있다.

 

Accessed and Dirty Bits

x86-64 하드웨어는 각 페이지의 페이지 테이블 엔트리(PTE)에 있는 쌍의 비트를 이용하여 페이지 교체 알고리즘을 구현하는 데 일부 도움을 제공합니다. 어떤 페이지에 대한 읽기 또는 쓰기가 일어나면 CPU는 페이지 PTE의 accessed 비트를 1로 설정하고, 쓰기가 일어나면 CPU는 dirty 비트를 1로 설정합니다. CPU는 이러한 비트를 절대 0으로 재설정하지 않지만, OS는 이를 재설정할 수 있습니다.

 

aliases가 있다는 것을 인지해야 합니다. 즉, 둘 이상의 페이지가 동일한 프레임을 참조하는 경우입니다. alias가 있는 프레임에 접근할 때, accessed 비트와 dirty 비트는 접근한 페이지의 페이지 테이블 엔트리(PTE)에서만 업데이트됩니다. 다른 alias의 accessed 비트와 dirty 비트는 업데이트되지 않습니다.

 

Pintos에서는 모든 사용자 가상 페이지가 커널 가상 페이지에 alias됩니다. 이러한 alias를 어떻게 관리해야 할지에 대해서는 생각해야 합니다. 예를 들어, 코드에서는 양쪽 주소의 accessed와 dirty bit를 검사하고 업데이트할 수 있습니다. 또는, 커널은 사용자 가상 주소를 통해서만 사용자 데이터에 접근하도록 할 수도 있습니다. 공유를 구현하거나 코드에 버그가 있을 경우에만 기타 alias가 발생할 수 있습니다. accessed와 dirty bit를 작업하는 기능에 대한 자세한 내용은 Page Table Accessed and Dirty Bits 섹션을 참고하세요.

 

Managing the Swap Table (스왑 테이블 관리)

---

스왑 테이블은 사용 중인 스왑 슬롯과 빈 스왑 슬롯을 추적합니다. 프레임에서 페이지를 스왑 파티션으로 페이지를 제거하기 위해 사용되지 않는 스왑 슬롯을 선택할 수 있어야 합니다. 스왑 슬롯의 페이지가 읽혀졌거나 스왑된 프로세스가 종료될 때 스왑 슬롯을 해제할 수 있어야 합니다.

 

vm/build 디렉토리에서 pintos-mkdisk swap.dsk --swap-size=n 명령어를 사용하여 swap.dsk 이라는 이름의 디스크를 생성하고 그 디스크에 n-MB 크기의 스왑 파티션을 포함시킵니다. 이 후에는 pintos를 실행할 때마다 swap.dsk가 자동으로 추가 디스크로 연결됩니다. 또는 한 번의 실행만을 위한 임시 n-MB 스왑 디스크를 --swap-size=n 옵션으로 pintos에 알려줄 수도 있습니다.

 

나중에 필요한 경우에만 스왑 슬롯을 할당하는 것이 좋습니다. 즉, 제거 작업에 실제로 필요할 때만 스왑 슬롯을 할당하는 것입니다. 실행 파일에서 데이터 페이지를 읽고 지정된 페이지를 저장하기 위해 스왑 슬롯을 예약하지 않는 것이 좋습니다. 제거 작업을 시작할 때만 스왑 슬롯을 사용합니다. 실행 파일을 시작할 때 스왑 슬롯에 바로 쓰지 않는 것이 좋습니다.

 

내용이 프레임으로 다시 읽히면 스왑 슬롯을 확보합니다.

 

Managing Memory Mapped Files (메모리 매핑된 파일 관리)

---

기본적으로 파일 시스템은 read와 write 시스템 콜을 사용해 접근합니다. 보조 인터페이스로 mmap 시스템 콜을 사용해 파일을 가상 페이지로 "매핑"할 수 있습니다. 그러면 프로그램은 파일 데이터에 직접 메모리 instructions를 사용할 수 있습니다. 예를 들어, 파일 foo의 길이가 0x1000 바이트(4kB, 페이지 한 개)인 경우 주소 0x5000부터 foo를 메모리에 매핑한다고 가정해봅시다. 그러면 주소 0x5000부터 0x5fff까지의 메모리 접근은 foo의 해당 바이트에 접근할 것입니다.

 

콘솔에 파일을 출력하기 위해 mmap을 사용하는 프로그램입니다. 커맨드라인에 지정한 파일을 열고, 0x10000000 주소에 매핑한 다음, 매핑된 데이터를 콘솔(fd 1)에 쓰고 파일을 언매핑합니다.

#include <stdio.h>
#include <syscall.h>
int main (int argc UNUSED, char *argv[])
{
  void *data = (void *) 0x10000000;                 /* Address at which to map. */
  int fd = open (argv[1]);                          /* Open file. */
  void *map = mmap (data, filesize (fd), 0, fd, 0); /* Map file. */
  write (1, data, filesize (fd));                   /* Write file to console. */
  munmap (map);                                     /* Unmap file (optional). */
  return 0;
}

프로젝트 제출물은 메모리 매핑 파일에 의해 사용된 메모리를 추적할 수 있어야 합니다. 이는 매핑된 영역에서 page fault를 제대로 처리하고, 매핑된 파일이 프로세스 내의 어떤 세그먼트와도 겹치지 않는 것을 보장하기 위해 필요합니다.