Project3: Virtual Memory - Introduction (기입완료-수정중)

<<지속적으로 참고하기 위해서 깃북의 번역을 여기에 작성한다>>

 

지금쯤이면 핀토스의 내부 작동 방식에 어느 정도 익숙해졌을 것입니다. OS는 적절한 동기화를 통해 여러 스레드의 실행을 적절히 처리할 수 있으며 한 번에 여러 사용자 프로그램을 로드할 수 있습니다. 그러나 실행할 수 있는 프로그램의 수와 크기는 컴퓨터의 주 메모리 크기에 의해 제한됩니다. 이 과제에서는 무한한 메모리라는 환상을 구축하여 이러한 제한을 제거합니다.

지난 과제 위에 이 과제를 구축하게 됩니다. 프로젝트 2의 테스트 프로그램은 프로젝트 3에서도 작동해야 합니다. 프로젝트 2 제출물의 버그가 프로젝트 3에서도 동일한 문제를 일으킬 가능성이 높으므로 프로젝트 3 작업을 시작하기 전에 프로젝트 2 제출물의 모든 버그를 수정해야 합니다.

프로젝트 3의 경우, 여러분의 편의를 위해 단계별 지침을 제공합니다.

Background

Source Files

이 프로젝트의 VM 디렉토리에서 작업하게 됩니다. Makefile 을 업데이트하여 -DVM 설정을 켭니다. 저희는 방대한 양의 템플릿 코드를 제공합니다. 반드시 주어진 템플릿을 따라야 합니다. 즉, 주어진 템플릿에 기반하지 않은 코드를 제출하면 0점을 받습니다. 또한 "변경하지 마세요"라고 표시된 템플릿은 절대로 변경해서는 안 됩니다. 여기에서는 수정할 각 템플릿 파일에 대한 몇 가지 세부 정보를 제공합니다.

 

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

 

가상 메모리에 대한 일반적인 인터페이스를 제공합니다. 헤더 파일에서 가상 메모리 시스템이 지원해야 하는 다양한 vm_ 유형(VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE)에 대한 정의와 설명을 확인할 수 있습니다(지금은 VM_PAGE_CACHE는 무시하세요. 프로젝트 4용이므로). 또한 여기에 보조 페이지 테이블을 구현할 것입니다(아래 참조).

 

- include/vm/uninit.h, vm/uninit.c

 

초기화되지 않은 페이지에 대한 작업을 제공합니다(vm_type = VM_UNINIT). 현재 설계에서는 모든 페이지가 처음에 초기화되지 않은 페이지로 설정된 다음 익명 페이지(anonymous pages) 또는 파일 백업 페이지(file-backed pages)로 변환됩니다.

 

- 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 (현재 kaist-pintos 프로젝트에서는 block.c, block.h를 찾을 수 없는데 disk.h, disk.c가 이 파일이 하는 역할을 하는것으로 보임)

 

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

 

Memory Terminology

먼저 메모리와 스토리지에 대한 몇 가지 용어를 소개합니다. 이 용어 중 일부는 프로젝트 2(가상 메모리 레이아웃 참조https://casys-kaist.github.io/pintos-kaist/project2/introduction.html)에서 익숙한 것이지만 대부분은 새로운 용어입니다.

 

Pages

가상 페이지라고도 하는 페이지는 길이가 4,096바이트(페이지 크기)인 가상 메모리의 연속적인 영역입니다. 페이지는 페이지 정렬, 즉 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작해야 합니다. 따라서 64비트 가상 주소의 마지막 12비트는 페이지 오프셋(또는 그냥 오프셋)입니다. 상위 비트는 페이지 테이블의 인덱스를 나타내는 데 사용되며 곧 도입될 예정입니다. 64비트 시스템에서는 4단계 페이지 테이블을 사용하므로 가상 주소는 다음과 같이 표시됩니다:

각 프로세스에는 독립적인 사용자(가상) 페이지 세트가 있으며, 이 페이지는 가상 주소 KERN_BASE(0x8004000000) 아래에 있는 페이지입니다. 반면 커널(가상) 페이지 집합은 전역이므로 실행 중인 스레드나 프로세스에 관계없이 동일한 위치에 유지됩니다. 커널은 사용자 페이지와 커널 페이지 모두에 액세스할 수 있지만 사용자 프로세스는 자신의 사용자 페이지에만 액세스할 수 있습니다. 자세한 내용은 가상 메모리 레이아웃을 참조(https://casys-kaist.github.io/pintos-kaist/project2/introduction.html)하세요.

 

핀토스는 가상 주소 작업에 유용한 몇 가지 기능을 제공합니다. 자세한 내용은 가상 주소 섹션(https://casys-kaist.github.io/pintos-kaist/appendix/virtual_address.html)을 참조하세요.

 

Frames

물리적 프레임 또는 페이지 프레임이라고도 하는 프레임은 물리적 메모리의 연속적인 영역입니다. 페이지와 마찬가지로 프레임도 페이지 크기와 페이지 정렬을 유지해야 합니다. 따라서 64비트 물리적 주소는 다음과 같이 프레임 번호와 프레임 오프셋(또는 그냥 오프셋)으로 나눌 수 있습니다:

x86-64는 물리적 주소의 메모리에 직접 액세스할 수 있는 방법을 제공하지 않습니다. 핀토스는 커널 가상 메모리를 물리적 메모리에 직접 매핑하여 이 문제를 해결합니다. 커널 가상 메모리의 첫 번째 페이지는 물리적 메모리의 첫 번째 프레임에, 두 번째 페이지는 두 번째 프레임에 매핑하는 식으로 말이죠. 따라서 커널 가상 메모리를 통해 프레임에 액세스할 수 있습니다.

 

핀토스는 물리적 주소와 커널 가상 주소 간 변환 기능을 제공합니다. 자세한 내용은 가상 주소(https://casys-kaist.github.io/pintos-kaist/appendix/virtual_address.html)를 참조하십시오.

 

Page Tables

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

 

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

 

 

Swap Slots

스왑 슬롯은 스왑 파티션에 있는 페이지 크기의 디스크 공간 영역입니다. 슬롯을 배치하는 데 있어 하드웨어 제한은 프레임보다 유연하나, 스왑 슬롯은 페이지에 맞게 정렬되어야 합니다. 이렇게 정렬하는 것에는 단점이 없기 때문입니다.

 

Resource Management Overview

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

 

Supplemental page table

 

페이지 테이블을 보완하여 페이지 오류 처리를 활성화합니다. 아래의 보충 페이지 테이블 관리를 참조하십시오.

 

Frame table

 

물리적 프레임의 퇴거 정책을 효율적으로 구현할 수 있습니다. 아래 프레임 표 관리하기를 참조하세요.

 

Swap table

 

스왑 슬롯의 사용량을 추적합니다. 아래의 스왑 테이블 관리를 참조하세요.

 

완전히 다른 세 가지 데이터 구조를 구현할 필요는 없으며, 관련 리소스를 전체 또는 부분적으로 통합 데이터 구조로 병합하는 것이 편리할 수 있습니다.

 

각 데이터 구조에 대해 각 요소에 어떤 정보가 포함되어야 하는지 결정해야 합니다. 또한 데이터 구조의 범위를 로컬(프로세스별) 또는 전역(전체 시스템에 적용)으로 결정하고 해당 범위 내에 필요한 인스턴스 수를 결정해야 합니다.

 

설계를 단순화하기 위해 이러한 데이터 구조를 페이지링할 수 없는 메모리(예: calloc 또는 malloc으로 할당된 메모리)에 저장할 수 있습니다. 즉, 데이터 구조체 사이의 포인터가 유효하게 유지된다는 것을 확신할 수 있습니다.

 

Choices of implementation (Performance perspective)

배열,lists, 비트맵, 해시 테이블 등을 통해 구현할 수 있습니다. 배열은 가장 간단한 접근 방식이지만, 빈도가 낮은 배열은 메모리를 낭비합니다. lists도 간단하지만 특정 위치를 찾기 위해 긴 목록을 탐색하면 시간이 낭비됩니다. 배열과 lists 모두 크기를 조정할 수 있지만 lists이 중간에 삽입 및 삭제를 더 효율적으로 지원합니다.

 

핀토스는 lib/kernel/bitmap.c와 include/lib/kernel/bitmap.h에 비트맵 데이터 구조를 포함하고 있습니다. 비트맵은 비트의 배열로, 각 비트는 참 또는 거짓일 수 있습니다. 비트맵은 일반적으로 (동일한) 리소스 집합의 사용량을 추적하는 데 사용됩니다. 리소스 n이 사용 중이면 비트맵의 비트 n은 참입니다. 핀토스 비트맵은 크기가 고정되어 있지만 크기 조정을 지원하도록 구현을 확장할 수 있습니다.

 

핀토스에는 해시 테이블 데이터 구조도 포함되어 있습니다(해시 테이블 참조https://casys-kaist.github.io/pintos-kaist/appendix/hash_table.html). Pintos 해시 테이블은 다양한 테이블 크기에 걸쳐 삽입 및 삭제를 효율적으로 지원합니다.

 

데이터 구조가 복잡할수록 성능이나 기타 이점이 향상될 수 있지만, 구현이 불필요하게 복잡해질 수도 있습니다. 따라서 고급 데이터 구조(예: 균형 잡힌 이진 트리)를 설계의 일부로 구현하는 것은 권장하지 않습니다.

 

Managing the Supplemental Page Table

보충 페이지 테이블은 각 페이지에 대한 추가 데이터를 페이지 테이블에 보완적으로 제공합니다. 이는 페이지 테이블의 형식으로 인해 가해지는 제한 때문에 필요합니다. 이러한 데이터 구조는 종종 "페이지 테이블"이라고도 불리며, 혼동을 줄이기 위해 "보충적"이라는 단어를 추가합니다.

 

보충 페이지 테이블은 적어도 두 가지 용도로 사용됩니다. 가장 중요한 것은 페이지 오류가 발생하면 커널이 보충 페이지 테이블에서 오류가 발생한 가상 페이지를 조회하여 거기에 어떤 데이터가 있어야 하는지 알아내는 것입니다. 둘째, 커널은 프로세스가 종료될 때 보충 페이지 테이블을 참조하여 어떤 리소스를 해제할지 결정합니다.

 

Organization of Supplemental Page Table

보충 페이지 표는 원하는 대로 구성할 수 있습니다. 구성에는 세그먼트 또는 페이지 측면에서 최소한 두 가지 기본 접근 방식이 있습니다. 여기서 세그먼트는 연속된 페이지 그룹, 즉 실행 파일 또는 메모리 매핑된 파일이 포함된 메모리 영역을 의미합니다.

 

선택적으로 페이지 테이블 자체를 사용하여 보조 페이지 테이블의 멤버를 추적할 수 있습니다. 이렇게 하려면 threads/mmu.c에서 핀토스 페이지 테이블 구현을 수정해야 합니다. 이 접근 방식은 고급 학생에게만 권장합니다.

 

Handling page fault

보충 페이지 테이블의 가장 중요한 사용자는 the page fault handler입니다. 프로젝트 2에서 페이지 오류는 항상 커널 또는 사용자 프로그램의 버그를 의미했습니다. 프로젝트 3에서는 더 이상 그렇지 않습니다. 이제 페이지 오류는 파일 또는 스왑 슬롯에서 페이지를 가져와야 함을 나타낼 수 있습니다. 이러한 경우를 처리하려면 보다 정교한 page fault handler를 구현해야 합니다. userprog/exception.c의 page_fault()인 페이지 결함 처리기는 vm/vm.c의 페이지 결함 처리기인 vm_try_handle_fault()를 호출합니다. 페이지 결함 처리기는 대략적으로 다음과 같은 작업을 수행해야 합니다:

 

1.보조 페이지 테이블에서 오류가 발생한 페이지를 찾습니다. 메모리 참조가 유효한 경우, 보조 페이지 테이블 항목을 사용하여 파일 시스템이나 스왑 슬롯에 있거나 단순히 0 페이지일 수 있는 페이지에 있는 데이터를 찾습니다. 공유(즉, 쓰기 시 복사)를 구현하는 경우 페이지의 데이터가 이미 페이지 프레임에 있지만 페이지 테이블에는 없을 수도 있습니다. 추가 페이지 테이블에 사용자 프로세스가 액세스하려는 주소에 데이터가 없거나 페이지가 커널 가상 메모리 내에 있는 경우 또는 액세스가 읽기 전용 페이지에 쓰려는 시도인 경우 액세스가 유효하지 않은 것으로 표시됩니다. 잘못된 액세스는 프로세스를 종료하여 모든 리소스를 해제합니다.

 

2.페이지를 저장할 프레임을 가져옵니다. sharing를 구현하는 경우 필요한 데이터가 이미 프레임에 있을 수 있으며, 이 경우 해당 프레임을 찾을 수 있어야 합니다.

 

3.파일 시스템이나 스왑에서 데이터를 읽거나 제로화하여 데이터를 프레임으로 가져옵니다. sharing를 구현하는 경우 필요한 페이지가 이미 프레임에 있을 수 있으며, 이 경우 이 단계에서는 아무런 작업이 필요하지 않습니다.

 

4.Point the page table entry for the faulting virtual address to the physical page. threads/mmu.c에서 함수를 사용할 수 있습니다.

 

Managing the Frame Table

프레임 테이블에는 각 프레임에 대해 하나의 항목이 포함됩니다. 프레임 테이블의 각 항목에는 현재 사용 중인 페이지에 대한 포인터(있는 경우)와 사용자가 선택한 기타 데이터가 포함됩니다. 프레임 테이블을 통해 핀토스는 빈 프레임이 없을 때 퇴거할 페이지를 선택하여 퇴거 정책을 효율적으로 구현할 수 있습니다.

 

사용자 페이지에 사용되는 프레임은 palloc_get_page(PAL_USER)를 호출하여 "사용자 풀"에서 가져와야 합니다. 일부 테스트 케이스가 예기치 않게 실패할 수 있는 "커널 풀"에서 할당하지 않으려면 PAL_USER를 사용해야 합니다. 프레임 테이블 구현의 일부로 palloc.c를 수정하는 경우 두 풀 간의 구분을 유지해야 합니다.

 

프레임 테이블에서 가장 중요한 작업은 사용하지 않는 프레임을 확보하는 것입니다. 프레임이 비어 있으면 이 작업은 쉽습니다. 사용 가능한 프레임이 없는 경우 프레임에서 일부 페이지를 제거하여 프레임을 사용 가능하게 만들어야 합니다.

 

스왑 슬롯을 할당하지 않고는 프레임을 퇴거시킬 수 없는데 스왑 슬롯이 가득 차면 커널이 패닉 상태에 빠집니다. 실제 OS는 이러한 상황을 복구하거나 방지하기 위해 다양한 정책을 적용하지만 이러한 정책은 이 프로젝트의 범위를 벗어납니다.

 

1.페이지 교체 알고리즘을 사용하여 퇴거할 프레임을 선택합니다. 아래에 설명된 페이지 표의 '액세스됨' 및 '더티' 비트가 유용하게 사용될 것입니다.

 

2.프레임을 참조하는 모든 페이지 테이블에서 프레임에 대한 참조를 제거합니다. 공유를 구현한 경우가 아니라면 한 번에 하나의 페이지만 프레임을 참조해야 합니다.

 

3.필요한 경우 페이지를 파일 시스템에 쓰거나 스왑합니다. 그러면 퇴거된 프레임은 다른 페이지를 저장하는 데 사용될 수 있습니다.

 

Accessed and Dirty Bits

x86-64 하드웨어는 각 페이지의  the page table entry(PTE)에 있는 한 쌍의 비트를 통해 페이지 교체 알고리즘을 구현하는 데 약간의 지원을 제공합니다. 페이지에 대한 읽기 또는 쓰기 시 CPU는 페이지의 PTE에서 액세스된 비트를 1로 설정하고 쓰기 시 더티 비트를 1로 설정합니다. CPU는 이러한 비트를 0으로 재설정하지 않지만 OS는 그렇게 할 수 있습니다.

 

동일한 프레임을 참조하는 두 개(또는 그 이상의) 페이지인 별칭(aliases - 에일리어스(파일인터넷 주소 등에 쓰는 가명 ))에 대해 알고 있어야 합니다. 앨리어싱된 프레임에 액세스하면 액세스된 비트와 더티 비트는 하나의 페이지 테이블 항목(액세스에 사용된 페이지에 대한 항목)에서만 업데이트됩니다. 다른 앨리어스에 대한 액세스 및 더티 비트는 업데이트되지 않습니다.

 

핀토스에서는 모든 사용자 가상 페이지가 커널 가상 페이지에 별칭이 지정됩니다. 이러한 별칭을 어떻게든 관리해야 합니다. 예를 들어, 코드에서 두 주소 모두에 대해 액세스된 비트와 더티 비트를 확인하고 업데이트할 수 있습니다. 또는 커널이 사용자 가상 주소를 통해서만 사용자 데이터에 액세스하여 문제를 피할 수도 있습니다.

 

다른 별칭은 공유를 구현하거나 코드에 버그가 있는 경우에만 발생해야 합니다.

 

액세스된 비트와 더티 비트로 작업하는 함수에 대한 자세한 내용은 액세스된 비트 및 더티 비트 섹션(https://casys-kaist.github.io/pintos-kaist/appendix/page_table.html)을 참조하세요.

 

Managing the Swap Table

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

 

vm/build 디렉터리에서 pintos-mkdisk swap.dsk --swap-size=n 명령을 사용하여 n-MB 스왑 파티션이 포함된 swap.dsk라는 이름의 디스크를 생성합니다. 그 후 핀토스를 실행하면 swap.dsk가 자동으로 추가 디스크로 첨부됩니다. 또는 --swap-size=n을 사용하여 한 번 실행할 때 임시 n-MB 스왑 디스크를 사용하도록 핀토에 지시할 수 있습니다.

 

스왑 슬롯은 실제로 퇴거(eviction) 에 필요한 경우에만 느리게 할당해야 합니다. 실행 파일에서 데이터 페이지를 읽고 프로세스 시작 시 즉시 스왑하기 위해 쓰는 것은 느리지 않습니다. 특정 페이지를 저장하기 위해 스왑 슬롯을 예약해서는 안 됩니다.

스왑 슬롯의 내용을 프레임으로 다시 읽을 때 스왑 슬롯을 해제합니다.

 

Managing Memory Mapped Files

파일 시스템은 읽기 및 쓰기 시스템 호출을 통해 가장 일반적으로 액세스합니다. 두 번째 인터페이스는 mmap 시스템 호출을 사용하여 파일을 가상 페이지에 '매핑'하는 것입니다. 그러면 프로그램은 파일 데이터에 직접 메모리 명령을 사용할 수 있습니다. 파일 foo의 길이가 0x1000바이트(4KB, 즉 한 페이지)라고 가정해 보겠습니다. foo가 주소 0x5000에서 시작하는 메모리에 매핑되어 있으면 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;
}

 

제출물은 메모리 매핑된 파일에서 어떤 메모리를 사용하는지 추적할 수 있어야 합니다. 이는 매핑된 영역에서 페이지 오류를 적절히 처리하고 매핑된 파일이 프로세스 내에서 다른 세그먼트와 겹치지 않도록 하기 위해 필요합니다.