PintOS 제작기 - 3

PintOS

서론

PintOS 중 우리는 카이스트에서 개발한 운영체제를 직접 만들어본다. 이는 주차들로 나뉘어 각각의 프로젝트를 만들게 된다.

Project 1 - 서론

Project 1에서는 Base kernel의 Source Code를 제작하게 된다. 이는 threads directory에 있다.

또한, I/O device interfacing 과정을 진행하게 되는데, 이는 devices directory에 있다.

Project 2 - 서론

Project 2 에서는 User Program Loader를 제작하게 된다. 이는 userprog directory에 있다.

lib directory에서 standard C library의 일부를 implement 하게 된다.

Project 3 - 서론

Project 3 에서는 Virtual Memory를 구현하게 된다. 이는 vm directory에 있다.

Project 4 - 서론

Project 4 에서는 basic file system을 구현하게 된다. 이는 filesys directory에 있다.

이는 사실 project 2에서 실제로 처음 사용하게 되지만, 내부를 수정하는 것은 Project 4에 와서 진행한다.

본론

Project 3: 가상 메모리

도입

이제 PintOS의 내부 작동 방식에 어느 정도 익숙해졌을 것이다. 운영체제는 적절한 동기화로 여러 스레드를 처리할 수 있고, 동시에 여러 사용자 프로그램을 로드할 수 있다. 그러나, 실행할 수 있는 프로그램의 수와 크기는 머신의 주 메모리 크기에 의해 제한된다. 이번 과제에서는 이러한 제한을 없애고 무한한 메모리가 있는 것처럼 보이도록 구현하게 된다.

이번 과제는 이전 과제 위에 구축된다. Project 2의 테스트 프로그램도 Project 3에서 동작해야 한다. Project 2 제출물에서 발생한 버그를 수정하지 않으면 Project 3에서도 동일한 문제가 발생할 가능성이 높다. 그러므로 Project 3 작업을 시작하기 전에 Project 2에서 발생한 버그를 해결해야 한다.

소스 파일

이번 프로젝트는 vm 디렉토리에서 작업하게 된다. Makefile은 -DVM 설정을 활성화하도록 업데이트되어 있다. 우리는 많은 양의 템플릿 코드를 제공한다. 반드시 주어진 템플릿을 따라야 한다. 템플릿을 기반으로 하지 않은 코드를 제출할 경우, 0점을 받게 된다. 또한 “DO NOT CHANGE”로 표시된 부분은 절대 변경해서는 안 된다. 여기서는 수정하게 될 각 템플릿 파일에 대한 세부 정보를 제공한다.

• include/vm/vm.h, vm/vm.c
  가상 메모리에 대한 일반적인 인터페이스를 제공한다. 헤더 파일에서는 여러 vm_type (예: VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE)에 대한 정의와 설명을 볼 수 있다. VM_PAGE_CACHE는 Project 4를 위한 것이므로 지금은 무시한다. 보충 페이지 테이블은 이곳에서 구현하게 된다.

• 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
  블록 장치에 대한 섹터 기반 읽기 및 쓰기 접근을 제공한다. 스왑 파티션에 블록 장치로 접근하기 위해 이 인터페이스를 사용한다.

메모리 용어

우리는 메모리와 스토리지와 관련된 몇 가지 용어를 소개한다. 이들 중 일부는 Project 2에서 이미 다루었을 것이다(가상 메모리 레이아웃 참조). 하지만 대부분은 새로운 내용이다.

• 페이지
  페이지는 가상 메모리의 연속적인 영역으로, 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) 아래에 있는 독립적인 사용자(가상)페이지 집합을 가진다. 반면 커널(가상) 페이지는 전역적이며, 어떤 스레드나 프로세스가 실행 중이든 동일한 위치에 유지된다. 커널은 사용자 페이지와 커널 페이지 모두에 접근할 수 있지만, 사용자 프로세스는 자신의 사용자 페이지에만 접근할 수 있다. 가상 메모리 레이아웃에 대한 자세한 내용은 가상 메모리 레이아웃 을 참조한다.

Pintos는 가상 주소를 다룰 때를 위한 다양한 실용적인 함수를 제공한다. 가상 주소섹션을 참고하여 자세히 알아보라.

• 프레임
  프레임 은 물리 메모리의 연속적인 영역이며, 물리 프레임 이나 페이지 프레임 이라고도 부른다. 페이지와 마찬가지로, 프레임은 페이지 크기여야 하며 페이지 정렬이 되어야 한다. 그러므로 64비트 물리 주소는 프레임 번호와 프레임 오프셋 으로 나눌 수 있다:

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

x86-64 아키텍처는 물리 주소에서 메모리에 직접 접근하는 방법을 제공하지 않는다. Pintos는 커널 가상 메모리를 물리 메모리로 직접 매핑하여 이를 해결한다. 즉, 커널 가상 메모리의 첫 번째 페이지는 물리 메모리의 첫 번째 프레임에, 두 번째 페이지는 두 번째 프레임에 매핑된다. 따라서 커널 가상 메모리를 통해 프레임에 접근할 수 있다. 가상 주소에 대한 자세한 내용은 가상 주소를 참조한다.

• 페이지 테이블
  페이지 테이블 은 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    ^
                  \_______________________________________/

• 스왑 슬롯
  스왑 슬롯 은 스왑 파티션의 디스크 공간에서 페이지 크기의 영역이다. 하드웨어의 제한으로 인해 슬롯의 배치가 프레임보다 유연하지만, 슬롯은 페이지 정렬이 되어야 한다. 페이지 교체 정책을 효율적으로 구현하기 위해 스왑 테이블을 사용하여 사용 중인 스왑 슬롯과 여유 슬롯을 추적할 수 있어야 한다.

• 도대체 스왑 슬롯이 뭔가? OS에서 물리 메모리가 부족할 때, 디스크 공간을 메모리처럼 사용한다는 것은 알고 있을 것이다. 이 디스크 공간을 우리는 스왑 영역(swap space)이라고 한다. 이때, 스왑 슬롯은 스왑 영역 안에서 각각의 데이터 블록이 위치하는 곳을 의미한다.

리소스 관리 개요

다음 데이터 구조를 설계하고 구현해야 한다:

보충 페이지 테이블

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

프레임 테이블

• 물리적 프레임의 교체 정책을 효율적으로 구현할 수 있도록 한다.

스왑 테이블

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

세 가지 데이터 구조를 완전히 구분된 구조로 구현할 필요는 없다. 관련된 리소스를 하나의 통합된 데이터 구조로 합치는 것이 편리할 수 있다.

각 데이터 구조에 대해 각 요소가 어떤 정보를 포함해야 하는지 결정해야 하며, 해당 데이터 구조의 범위가 로컬(프로세스별)인지 전역(시스템 전체에 적용)인지, 그리고 범위 내에서 몇 개의 인스턴스가 필요한지도 결정해야 한다.

설계를 단순화하기 위해 이러한 데이터 구조를 페이지 불가능한 메모리(예: calloc 또는 malloc으로 할당된 메모리)에 저장할 수 있다. 이렇게 하면 이들 간의 포인터가 유효한 상태로 유지된다.

구현 선택 (성능 관점)

구현을 위한 선택 사항으로는 배열, 리스트, 비트맵, 해시 테이블 등이 있다. 배열은 가장 간단한 방법이지만, 인구 밀도가 낮은 배열은 메모리를 낭비할 수 있다. 리스트도 간단하지만, 특정 위치를 찾기 위해 긴 리스트를 순회하는 것은 시간을 낭비할 수 있다. 배열과 리스트는 크기를 조정할 수 있지만, 리스트는 중간에 삽입 및 삭제를 효율적으로 지원한다.

Pintos는 lib/kernel/bitmap.c와 include/lib/kernel/bitmap.h에 비트맵 데이터 구조를 포함하고 있다. 비트맵은 각 비트가 true 또는 false일 수 있는 비트 배열이다. 비트맵은 일반적으로 동일한 리소스 집합의 사용을 추적하는 데 사용된다. 예를 들어, 리소스 n이 사용 중이라면 비트맵의 n번째 비트가 true로 설정된다. Pintos 비트맵은 고정 크기이지만, 크기 조정을 지원하도록 구현을 확장할 수 있다.

Pintos는 해시 테이블 데이터 구조(해시 테이블)도 포함하고 있다. Pintos 해시 테이블은 넓은 범위의 테이블 크기에서 효율적인 삽입 및 삭제를 지원한다.

더 복잡한 데이터 구조는 성능이나 기타 이점을 제공할 수 있지만, 불필요하게 구현을 복잡하게 만들 수 있다. 따라서 균형 잡힌 이진 트리와 같은 고급 데이터 구조를 구현하는 것은 권장하지 않는다.

보충 페이지 테이블 관리

보충 페이지 테이블은 페이지 테이블의 형식에 의해 부과되는 제한을 보완하기 위해 각 페이지에 대한 추가 데이터를 제공한다. 이러한 데이터 구조는 종종 “페이지 테이블”이라고도 불리지만, 혼동을 줄이기 위해 “보충”이라는 단어를 추가한다.

보충 페이지 테이블은 최소 두 가지 목적을 위해 사용된다. 가장 중요한 것은 페이지 폴트가 발생했을 때 커널이 보충 페이지 테이블에서 해당 가상 페이지를 찾아 그 위치에 어떤 데이터가 있어야 하는지 확인하는 것이다. 두 번째는, 프로세스가 종료될 때 커널이 보충 페이지 테이블을 참조하여 해제해야 할 리소스를 결정하는 것이다.

보충 페이지 테이블의 구성

보충 페이지 테이블은 원하는 대로 구성할 수 있다. 기본적인 접근 방식으로는 세그먼트 또는 페이지를 기준으로 한 구성이 있다. 세그먼트는 연속된 페이지 그룹을 의미하며, 실행 파일이나 메모리에 매핑된 파일을 포함하는 메모리 영역이다.

선택적으로, 페이지 테이블 자체를 사용하여 보충 페이지 테이블의 멤버를 추적할 수 있다. 이를 위해 threads/mmu.c의 Pintos 페이지 테이블 구현을 수정해야 한다. 이 방법은 고급 학생들에게만 권장된다.

페이지 폴트 처리

보충 페이지 테이블의 가장 중요한 사용자는 페이지 폴트 핸들러이다. Project 2에서 페이지 폴트는 항상 커널이나 사용자 프로그램의 버그를 나타냈다. 하지만 Project 3에서는 더 이상 그렇지 않다. 이제 페이지 폴트는 단순히 페이지를 파일이나 스왑 슬롯에서 가져와야 함을 나타낼 수 있다. 이를 처리하기 위해 더 복잡한 페이지 폴트 핸들러를 구현해야 한다. 페이지 폴트 핸들러는 userprog/exception.c의 page_fault()에서 vm/vm.c의 vm_try_handle_fault()를 호출하여 처리된다. 페이지 폴트 핸들러는 대략 다음과 같은 작업을 수행해야 한다:

1. 보충 페이지 테이블에서 폴트가 발생한 페이지를 찾는다. 메모리 참조가 유효한 경우, 보충 페이지 테이블 항목을 사용하여 페이지에 들어갈 데이터를 찾는다. 해당 데이터는 파일 시스템, 스왑 슬롯에 있을 수 있으며, 단순히 0으로 채워진 페이지일 수도 있다. 공유(Copy-on-Write)를 구현한 경우, 페이지의 데이터가 이미 페이지 프레임에 있을 수 있지만, 페이지 테이블에는 없을 수 있다. 보충 페이지 테이블이 사용자 프로세스가 해당 주소에서 데이터를 기대하지 말아야 한다고 나타내거나, 페이지가 커널 가상 메모리 내에 있거나, 읽기 전용 페이지에 대한 쓰기 시도가 있는 경우, 접근이 유효하지 않다. 모든 유효하지 않은 접근은 프로세스를 종료시키고 그에 따라 모든 리소스를 해제한다.

2. 페이지를 저장할 프레임을 확보한다. 공유를 구현한 경우, 필요한 데이터는 이미 프레임에 있을 수 있으며, 이 경우 해당 프레임을 찾아야 한다.

3. 파일 시스템 또는 스왑에서 데이터를 프레임으로 가져오거나, 0으로 초기화하는 등의 작업을 수행한다. 공유를 구현한 경우, 필요한 페이지가 이미 프레임에 있을 수 있으며, 이 단계에서 추가 작업이 필요하지 않을 수 있다.

4. 폴트가 발생한 가상 주소에 대한 페이지 테이블 항목을 물리 페이지로 가리키도록 설정한다. threads/mmu.c의 함수를 사용할 수 있다.

프레임 테이블 관리

프레임 테이블은 각 프레임에 대한 항목을 포함한다. 각 항목은 현재 해당 프레임에 있는 페이지에 대한 포인터 및 기타 선택한 데이터를 포함한다. 프레임 테이블은 Pintos가 페이지 교체 정책을 효율적으로 구현할 수 있도록 하며, 프레임이 부족할 때 페이지를 교체하는 페이지를 선택할 수 있도록 한다.

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

프레임 테이블의 가장 중요한 작업은 사용되지 않은 프레임을 확보하는 것이다. 사용되지 않은 프레임이 있을 때는 이를 확보하는 것이 쉽다. 사용 가능한 프레임이 없으면, 해당 프레임에서 페이지를 교체하여 프레임을 확보해야 한다.

프레임을 교체하지 않고 스왑 슬롯을 할당할 수 없고, 스왑이 가득 찬 경우, 커널을 패닉 상태로 만들어야 한다. 실제 운영 체제는 이러한 상황을 예방하거나 복구하기 위해 다양한 정책을 적용하지만, 이 과제의 범위를 벗어난다.

교체 과정의 대략적인 단계는 다음과 같다:

1. 페이지 교체 알고리즘을 사용하여 교체할 프레임을 선택한다. 페이지 테이블의 “accessed” 및 “dirty” 비트가 유용하게 사용될 수 있다.
2. 해당 프레임을 참조하는 모든 페이지 테이블에서 프레임에 대한 참조를 제거한다. 공유를 구현하지 않은 경우, 한 번에 하나의 페이지만 프레임을 참조해야 한다.
3. 필요한 경우, 페이지를 파일 시스템이나 스왑으로 기록한다. 그런 다음 교체된 프레임을 다른 페이지에 사용할 수 있게 한다.

Accessed 및 Dirty 비트

x86-64 하드웨어는 페이지 교체 알고리즘을 구현하는 데 도움을 줄 수 있는 두 가지 비트를 페이지 테이블 항목(PTE)에 제공한다. 페이지에 읽기 또는 쓰기가 발생하면 CPU는 페이지의 PTE에서 accessed 비트를 1로 설정하고, 쓰기가 발생하면 dirty 비트를 1로 설정한다. CPU는 이 비트를 0으로 재설정하지 않지만, 운영 체제는 이를 재설정할 수 있다.

동일한 프레임을 참조하는 두 개 이상의 페이지, 즉 “alias”에 주의해야 한다. 프레임이 alias된 경우, 해당 프레임에 접근할 때 accessed 및 dirty 비트는 하나의 페이지 테이블 항목(접근에 사용된 페이지에 대한 항목)에서만 업데이트된다. 다른 alias의 accessed 및 dirty 비트는 업데이트되지 않는다.

Pintos에서는 모든 사용자 가상 페이지가 커널 가상 페이지에 alias된다. 이러한 alias를 관리하는 방법을 결정해야 한다. 예를 들어, 코드는 두 주소에 대해 accessed 및 dirty 비트를 확인하고 업데이트할 수 있다. 또는 커널이 사용자 데이터를 사용자 가상 주소를 통해서만 접근하도록 하여 문제를 방지할 수 있다.

다른 alias는 공유를 구현한 경우 또는 코드에 버그가 있을 때만 발생해야 한다.

Accessed 및 Dirty 비트와 관련된 함수에 대한 자세한 내용은 페이지 테이블 Accessed 및 Dirty 비트 섹션을 참조한다.

스왑 테이블 관리

스왑 테이블은 사용 중인 스왑 슬롯과 여유 스왑 슬롯을 추적한다. 페이지를 스왑 파티션으로 내보내기 위해 사용되지 않은 스왑 슬롯을 선택할 수 있어야 하며, 페이지가 다시 읽히거나 해당 페이지가 스왑된 프로세스가 종료될 때 슬롯을 해제할 수 있어야 한다.

vm/build 디렉토리에서 pintos-mkdisk swap.dsk --swap-size=n 명령을 사용하여 스왑 파티션이 있는 n-MB 크기의 디스크 swap.dsk를 생성한다. 생성된 swap.dsk는 pintos를 실행할 때 자동으로 추가 디스크로 연결된다. 또는, --swap-size=n 옵션을 사용하여 임시로 n-MB 크기의 스왑 디스크를 한 번의 실행 동안 사용할 수 있다.

스왑 슬롯은 페이지 교체가 실제로 필요할 때에만 할당되어야 한다(즉, 지연 할당되어야 한다). 프로세스 시작 시 실행 파일에서 데이터 페이지를 읽어와서 바로 스왑에 기록하는 것은 지연 할당이 아니다. 스왑 슬롯은 특정 페이지를 저장하기 위해 미리 예약되어서는 안 된다.

페이지가 프레임으로 다시 읽힐 때, 스왑 슬롯을 해제해야 한다.

메모리 매핑된 파일 관리

파일 시스템은 주로 read 및 write 시스템 콜을 통해 접근된다. 보조 인터페이스로는 mmap 시스템 콜을 사용하여 파일을 가상 페이지에 “매핑”하는 방법이 있다. 프로그램은 파일 데이터를 직접 메모리 명령을 통해 접근할 수 있다. 예를 들어, 파일 foo가 0x1000 바이트(4KB, 즉 1페이지) 크기라면, 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;                 /* 매핑할 주소 */
int fd = open (argv[1]);                          /* 파일 열기 */
void *map = mmap (data, filesize (fd), 0, fd, 0); /* 파일 매핑 */
write (1, data, filesize (fd));                   /* 파일을 콘솔에 출력 */
munmap (map);                                     /* 파일 언매핑 (선택적) */
return 0;
}

제출물은 메모리 매핑된 파일이 사용하는 메모리를 추적할 수 있어야 한다. 이는 매핑된 영역에서 발생하는 페이지 폴트를 적절히 처리하고, 매핑된 파일이 프로세스 내의 다른 세그먼트와 겹치지 않도록 보장하는 데 필요하다.

메모리 관리

가상 메모리 시스템을 지원하기 위해서는 가상 페이지와 물리 프레임을 효과적으로 관리해야 한다. 이는 어떤(가상 또는 물리) 메모리 영역이 사용되고 있는지, 어떤 목적으로 누구에 의해 사용되고 있는지를 추적해야 한다는 것을 의미한다. 먼저 보충 페이지 테이블을 처리한 다음 물리 프레임을 다루게 될 것이다. 참고로, 이 설명에서는 가상 페이지를 “페이지”라고 부르고, 물리 페이지를 “프레임”이라고 부를 것이다.

페이지 구조 및 작업

struct page

include/vm/vm.h에 정의된 페이지는 가상 메모리의 페이지를 나타내는 구조체이다. 이 구조체는 페이지에 대해 알아야 할 모든 필요한 데이터를 저장한다. 현재 템플릿에서 구조체는 다음과 같다:

struct page {
  const struct page_operations *operations;
  void *va;              /* 사용자 공간의 주소 */
  struct frame *frame;   /* 프레임에 대한 역참조 */

  union {
    struct uninit_page uninit;
    struct anon_page anon;
    struct file_page file;
#ifdef EFILESYS
    struct page_cache page_cache;
#endif
  };
};

이 구조체는 페이지 작업, 가상 주소, 물리 프레임을 포함하고 있다. 추가로 union 필드도 있다. union은 메모리 영역에 서로 다른 데이터 타입을 저장할 수 있는 특별한 데이터 타입이다. 여러 멤버를 가지고 있지만, 한 번에 하나의 멤버만 값을 가질 수 있다. 이 말은 시스템의 페이지가 uninit_page, anon_page, file_page, 또는 page_cache일 수 있다는 뜻이다. 예를 들어, 페이지가 익명 페이지(Anonymous Page)라면, struct page는 struct anon_page anon 필드를 가질 것이며, anon_page는 익명 페이지에 대해 필요한 모든 정보를 포함하게 된다.

페이지 작업

위에서 설명한 것처럼, 페이지는 VM_UNINIT, VM_ANON, 또는 VM_FILE일 수 있다. 페이지에는 swap in, swap out, destroy 등과 같은 여러 작업이 있다. 각 페이지 타입마다 이러한 작업에 필요한 단계와 작업이 다르다. 즉, VM_ANON 페이지와 VM_FILE 페이지에는 다른 destroy 함수가 호출되어야 한다. 각 함수에서 케이스마다 switch-case 구문을 사용할 수도 있지만, 우리는 이를 처리하기 위해 객체 지향 프로그래밍의 “클래스 상속” 개념을 도입한다. 실제로 C 언어에는 “클래스”나 “상속”이 없지만, 함수 포인터를 사용하여 이러한 개념을 구현할 수 있다. 이는 실제 운영체제 코드, 예를 들어 리눅스에서와 유사한 방식으로 구현된다.

함수 포인터는 지금까지 배운 다른 포인터들과 마찬가지로 메모리 내 함수나 실행 가능한 코드를 가리키는 포인터이다. 함수 포인터는 런타임 값에 따라 특정 함수를 실행하는 간단한 방법을 제공하며, 별도의 검사 없이 실행할 수 있다. 우리의 경우, 코드에서 destroy(page)를 호출하는 것만으로도 충분하다. 컴파일러는 페이지 타입에 따라 적절한 destroy 루틴을 선택하고 해당 함수 포인터를 호출하여 실행한다.

struct page_operations는 include/vm/vm.h에 정의된 페이지 작업을 위한 구조체이다. 이 구조체는 3개의 함수 포인터를 포함한 함수 테이블로 생각할 수 있다.

struct page_operations {
  bool (*swap_in) (struct page *, void *);
  bool (*swap_out) (struct page *);
  void (*destroy) (struct page *);
  enum vm_type type;
};

이제 page_operations 구조체를 어디에서 찾을 수 있는지 알아보자. include/vm/vm.h에서 struct page 구조체를 살펴보면 operations라는 필드가 있다. 그리고 vm/file.c로 가보면 함수 프로토타입 앞에 page_operations 구조체인 file_ops가 선언되어 있는 것을 볼 수 있다. 이것은 파일 기반 페이지에 대한 함수 포인터 테이블이다. .destroy 필드는 파일 기반 페이지를 제거하는 함수인 file_backed_destroy를 가리키며, 이는 같은 파일에서 정의된 함수이다.

함수 포인터 인터페이스로 file_backed_destroy가 어떻게 호출되는지 이해해 보자. 예를 들어, vm_dealloc_page(page)가 호출되었고, 이 페이지가 파일 기반 페이지(VM_FILE)인 경우를 생각해 보자. 함수 내부에서는 destroy(page)가 호출된다. destroy(page)는 include/vm/vm.h에 다음과 같은 매크로로 정의되어 있다:

#define destroy(page) if ((page)->operations->destroy) (page)->operations->destroy (page)

이 코드는 destroy 함수를 호출하면 실제로는 (page)->operations->destroy(page)를 호출하게 된다는 것을 의미한다. 이는 페이지 구조체에서 가져온 destroy 함수 포인터를 호출하는 방식이다. 해당 페이지가 VM_FILE 페이지이므로, 이 페이지의 .destroy 필드는 file_backed_destroy를 가리킨다. 결과적으로, 파일 기반 페이지에 대한 destroy 루틴이 실행된다.

보충 페이지 테이블 구현

현재 Pintos는 가상 메모리와 물리 메모리 매핑을 관리하기 위한 페이지 테이블(pml4)을 가지고 있다. 하지만 이것만으로는 충분하지 않다. 앞에서 논의한 것처럼, 페이지 폴트와 리소스 관리를 처리하기 위해 각 페이지에 대한 추가 정보를 보관할 수 있는 보충 페이지 테이블이 필요하다. 따라서 Project 3의 첫 번째 작업으로 보충 페이지 테이블의 기본 기능을 구현할 것을 제안한다.

vm/vm.c에서 보충 페이지 테이블 관리 기능을 구현하라.

먼저 Pintos에서 보충 페이지 테이블을 어떻게 설계할 것인지 결정해야 한다. 보충 페이지 테이블을 설계한 후, 해당 설계에 맞춰 다음 세 가지 기능을 구현하라.

void supplemental_page_table_init (struct supplemental_page_table *spt);

• 보충 페이지 테이블을 초기화한다. 보충 페이지 테이블에 사용할 데이터 구조는 선택할 수 있으며, 이 함수는 새로운 프로세스가 시작될 때(userprog/process.c의 initd에서) 및 프로세스가 포크될 때(userprog/process__do_fork에서) 호출된다.

struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

• 주어진 보충 페이지 테이블에서 가상 주소 va에 해당하는 struct page를 찾는다. 실패할 경우 NULL을 반환한다.

bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

• 주어진 보충 페이지 테이블에 struct page를 삽입한다. 이 함수는 가상 주소가 이미 보충 페이지 테이블에 존재하지 않는지 확인해야 한다.

프레임 관리

이제부터 모든 페이지는 단순히 메모리의 메타데이터를 가지고 있을 뿐만 아니라, 물리 메모리를 관리할 수 있는 구조로 변해야 한다. include/vm/vm.h에는 물리 메모리를 나타내는 struct frame이 존재한다. 현재 템플릿에서의 구조체는 다음과 같다:

/* "frame"의 표현 */
struct frame {
  void *kva;
  struct page *page;
};

이 구조체는 두 가지 필드만 가지고 있는데, kva는 커널 가상 주소를 나타내고, page는 페이지 구조체를 가리킨다. 프레임 관리 인터페이스를 구현하면서 더 많은 멤버를 추가할 수 있다.

vm_get_frame, vm_claim_page and vm_do_claim_page 를 vm/vm.c에서 구현하라:

static struct frame *vm_get_frame (void);

• 사용자 풀에서 palloc_get_page를 호출하여 새로운 물리 페이지를 얻는다. 사용자 풀에서 페이지를 성공적으로 얻었을 때, 프레임도 할당하고, 멤버들을 초기화한 후 반환한다. vm_get_frame을 구현한 후에는 모든 사용자 공간 페이지(PALLOC_USER)를 이 함수를 통해 할당해야 한다. 페이지 할당 실패 시 스왑 아웃을 처리할 필요는 없으며, 해당 경우에는 PANIC("todo")로 표시해두면 된다.

bool vm_do_claim_page (struct page *page);

• 페이지를 클레임하여(즉, 물리 프레임을 할당하여) 해당 페이지를 처리한다. 먼저 vm_get_frame을 호출하여 프레임을 가져온다(이는 템플릿에서 이미 제공된 기능이다). 이후 MMU(Memory Management Unit)를 설정해야 한다. 즉, 가상 주소에서 물리 주소로의 매핑을 페이지 테이블에 추가한다. 이 함수의 반환 값은 작업의 성공 여부를 나타내야 한다.

bool vm_claim_page (void *va);

• 가상 주소 va에 대한 페이지를 클레임한다. 먼저 페이지를 가져온 후, vm_do_claim_page를 해당 페이지와 함께 호출한다.

익명 페이지 (Anonymous Page)

이 부분에서는 디스크 기반 이미지가 아닌, 익명 페이지(anonymous page)를 구현하게 된다.

익명 매핑은 백업 파일이나 장치가 없다. 즉, 익명 페이지는 파일을 소스로 가지지 않기 때문에 ‘익명’이라고 불린다. 익명 페이지는 스택과 힙 같은 실행 파일에서 사용된다.

익명 페이지를 설명하기 위한 구조체는 include/vm/anon.h에 있는 anon_page이다. 현재는 비어 있지만, 익명 페이지를 구현하면서 필요한 정보나 상태를 저장할 멤버를 추가할 수 있다. 또한 include/vm/page.h에 있는 struct page를 참조하여 페이지의 일반적인 정보를 확인할 수 있다. 익명 페이지의 경우, struct anon_page anon이 페이지 구조체에 포함된다.

지연 로딩(Lazy Loading)을 통한 페이지 초기화

지연 로딩은 메모리 로딩을 실제로 필요할 때까지 미루는 디자인이다. 페이지가 할당되어 대응하는 페이지 구조체가 존재하지만, 물리적 프레임이 할당되지 않았고, 실제 페이지 내용도 아직 로드되지 않는다. 내용은 페이지 폴트가 발생할 때 로드된다.

우리는 세 가지 페이지 타입을 다루기 때문에 초기화 루틴은 각 페이지마다 다르다. 아래에서 다시 설명되겠지만, 여기서는 페이지 초기화 흐름의 높은 수준의 개요를 제공한다. 먼저 vm_alloc_page_with_initializer는 커널이 새 페이지 요청을 받으면 호출된다. 초기화자는 페이지 타입에 따라 적절한 초기화를 설정하고 페이지 구조체를 할당한 후 사용자 프로그램에 제어를 돌려준다. 사용자 프로그램이 실행되는 동안, 어느 시점에 프로그램이 페이지에 접근하려 시도하지만 해당 페이지에는 아직 내용이 없어 페이지 폴트가 발생하게 된다. 폴트 처리 절차에서 uninit_initialize가 호출되며, 이때 설정된 초기화자가 호출된다. 익명 페이지의 경우 anon_initializer, 파일 기반 페이지의 경우 file_backed_initializer가 호출된다.

페이지는 초기화->(페이지 폴트->지연 로드->스왑 인->스왑 아웃->...) ->소멸의 생명 주기를 가질 수 있다. 각 생명 주기 전환에서 필요한 절차는 페이지 타입(또는 VM_TYPE)에 따라 다르다. 이번 프로젝트에서는 각 페이지 타입에 대해 이러한 전환 과정을 구현하게 된다.

실행 파일에 대한 지연 로딩

지연 로딩에서는 프로세스가 실행을 시작할 때, 즉시 필요한 메모리 부분만 메인 메모리에 로드된다. 이는 모든 바이너리 이미지를 한 번에 메모리에 로드하는 “빠른 로딩”에 비해 오버헤드를 줄일 수 있다.

지연 로딩을 지원하기 위해, include/vm/vm.h에 VM_UNINIT라는 페이지 타입이 도입되었다. 모든 페이지는 처음에 VM_UNINIT 페이지로 생성된다. 우리는 또한 초기화되지 않은 페이지를 위한 구조체인 struct uninit_page를 include/vm/uninit.h에 제공한다. 초기화되지 않은 페이지를 생성하고 초기화하며 파괴하는 함수들은 include/vm/uninit.c에서 찾을 수 있다. 이러한 함수들을 나중에 완성해야 한다.

페이지 폴트가 발생하면, 페이지 폴트 핸들러(userprog/exception.c의 page_fault)는 vm/vm.c의 vm_try_handle_fault로 제어를 넘긴다. 여기서는 해당 폴트가 유효한지 확인한다. 유효한 폴트란 잘못된 접근이 아닌 경우를 의미한다. 잘못된 폴트가 아니라면 페이지에 어떤 내용을 로드한 후 사용자 프로그램에 제어를 돌려준다.

잘못된 페이지 폴트는 세 가지 경우가 있다: 지연 로딩된 페이지, 스왑 아웃된 페이지, 쓰기 보호된 페이지(복사-온-라이트 참조). 지금은 첫 번째 경우인 지연 로딩된 페이지만 고려하면 된다. 지연 로딩을 위한 페이지 폴트라면, 커널은 vm_alloc_page_with_initializer에서 설정된 초기화자 중 하나를 호출하여 세그먼트를 지연 로드하게 된다. userprog/process.c에서 lazy_load_segment를 구현해야 한다.

vm_alloc_page_with_initializer()를 구현하라. 전달된 vm_type에 따라 적절한 초기화자를 선택하고, uninit_new와 함께 호출해야 한다.

bool vm_alloc_page_with_initializer (enum vm_type type, void *va,
        bool writable, vm_initializer *init, void *aux);

• 주어진 타입으로 초기화되지 않은 페이지를 생성하라. uninit 페이지의 swap_in 핸들러는 페이지 타입에 따라 자동으로 페이지를 초기화하며, 주어진 INIT과 AUX 값을 사용하여 초기화 작업을 수행한다. 페이지 구조체를 생성한 후, 해당 페이지를 프로세스의 보충 페이지 테이블에 삽입해야 한다. 이때, vm.h에 정의된 VM_TYPE 매크로를 사용하는 것이 유용할 수 있다.

페이지 폴트 핸들러는 호출 체인을 따라가며, 최종적으로 swap_in을 호출할 때 uninit_initialize 함수에 도달한다. 이를 위한 완전한 구현은 제공되었지만, 디자인에 따라 uninit_initialize 함수를 수정해야 할 수 있다.

static bool uninit_initialize (struct page *page, void *kva);

• 첫 번째 페이지 폴트가 발생했을 때 페이지를 초기화한다. 템플릿 코드는 먼저 vm_initializer와 aux를 가져와 함수 포인터를 통해 해당하는 page_initializer를 호출한다. 디자인에 따라 이 함수를 수정해야 할 수도 있다.

필요에 따라 vm/anon.c의 vm_anon_init 및 anon_initializer를 수정할 수 있다.

void vm_anon_init (void);

• 익명 페이지 서브시스템을 초기화한다. 이 함수에서 익명 페이지와 관련된 모든 설정을 수행할 수 있다.

  bool anon_initializer (struct page *page,enum vm_type type, void *kva);
  

• 이 함수는 먼저 익명 페이지에 대한 핸들러를 page->operations에 설정한다. anon_page(현재는 빈 구조체)의 정보를 업데이트해야 할 수도 있다. 이 함수는 익명 페이지(VM_ANON)의 초기화자로 사용된다.

userprog/process.c에서 load_segment와 lazy_load_segment를 구현하라. 실행 파일에서 세그먼트를 로드하는 과정을 구현해야 한다. 이러한 페이지들은 모두 지연 로딩되어야 하며, 커널이 페이지 폴트를 가로챌 때만 실제로 로드된다.

userprog/process.c의 프로그램 로더의 핵심 부분인 load_segment의 루프를 수정해야 한다. 루프가 실행될 때마다 vm_alloc_page_with_initializer를 호출하여 대기 중인 페이지 객체를 생성한다. 페이지 폴트가 발생하면, 이때 파일에서 세그먼트를 실제로 로드하게 된다.

static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
        uint32_t read_bytes, uint32_t zero_bytes, bool writable);

• 현재 코드는 메인 루프 내에서 파일에서 읽을 바이트 수와 0으로 채울 바이트 수를 계산한다. 그런 다음, vm_alloc_page_with_initializer를 호출하여 대기 중인 객체를 생성한다. vm_alloc_page_with_initializer에 전달할 aux 인수로 전달할 보조 값을 설정해야 한다. 바이너리 로딩에 필요한 정보를 포함하는 구조체를 만들고 사용할 수 있다.

static bool lazy_load_segment (struct page *page, void *aux);

• lazy_load_segment가 vm_alloc_page_with_initializer의 네 번째 인수로 load_segment에서 전달된 것을 눈치챘을 것이다. 이 함수는 실행 파일의 페이지에 대한 초기화자로서, 페이지 폴트가 발생할 때 호출된다. 이 함수는 page 구조체와 aux 인수를 받는다. aux는 load_segment에서 설정한 정보이며, 이 정보를 사용하여 세그먼트를 읽을 파일을 찾아 결국 세그먼트를 메모리에 읽어 들여야 한다.

userprog/process.c의 setup_stack을 조정하여 새로운 메모리 관리 시스템에 맞게 스택 할당을 조정해야 한다. 첫 번째 스택 페이지는 지연 할당될 필요가 없다. 명령 줄 인수로 로드 시점에 할당하고 초기화할 수 있으며, 페이지 폴트가 발생할 때까지 기다릴 필요는 없다. 스택을 식별하는 방법을 제공해야 할 수도 있다. 스택을 식별하기 위해 vm/vm.h의 vm_type에 있는 보조 마커(예: VM_MARKER_0)를 사용할 수 있다.

마지막으로 vm_try_handle_fault 함수를 수정하여, 보충 페이지 테이블에서 spt_find_page를 통해 폴트가 발생한 주소에 해당하는 페이지 구조체를 찾아야 한다.

모든 요구 사항을 구현한 후에는, Project 2의 모든 테스트(fork 제외)를 통과해야 한다.

보충 페이지 테이블 - 재방문

이제 보충 페이지 테이블 인터페이스(supplemental page table interface)로 돌아가, 복사 및 정리 작업을 지원해야 한다. 이러한 작업은 프로세스를 생성할 때(특히 자식 프로세스를 생성할 때)나 프로세스를 종료할 때 필요하다. 아래에서 그 세부 사항이 설명된다. 보충 페이지 테이블을 이 시점에 다시 다루는 이유는 위에서 구현한 초기화 함수를 사용할 수 있기 때문이다.

vm/vm.c에 있는 supplemental_page_table_copy 와 supplemental_page_table_kill 을 구현하라.

bool supplemental_page_table_copy (struct supplemental_page_table *dst,
    struct supplemental_page_table *src);

• src의 보충 페이지 테이블을 dst로 복사한다. 이 과정은 자식 프로세스가 부모 프로세스의 실행 컨텍스트를 상속받아야 할 때(fork()) 사용된다. src의 보충 페이지 테이블에 있는 각 페이지를 순회하면서 dst의 보충 페이지 테이블에 정확히 동일한 엔트리를 복사해야 한다. 이 과정에서 초기화되지 않은 페이지를 할당하고 즉시 클레임해야 한다.

void supplemental_page_table_kill (struct supplemental_page_table *spt);

• 보충 페이지 테이블이 보유한 모든 리소스를 해제한다. 이 함수는 프로세스가 종료될 때(userprog/process.c의 process_exit()에서) 호출된다. 페이지 테이블의 엔트리를 순회하면서, 각 페이지에 대해 destroy(page)를 호출해야 한다. 이 함수에서는 실제 페이지 테이블(pml4)과 물리 메모리(palloc으로 할당된 메모리`)에 대해 걱정할 필요가 없다. 호출자가 보충 페이지 테이블을 정리한 후 이를 처리한다.

페이지 정리(Page Cleanup)

vm/uninit.c에서 uninit_destroy와 vm/anon.c에서 anon_destroy를 구현하라. 이 함수들은 초기화되지 않은 페이지에 대한 destroy 작업의 핸들러 역할을 한다. 초기화되지 않은 페이지가 다른 페이지 객체로 변환되더라도, 프로세스가 종료될 때 여전히 uninit 페이지가 존재할 수 있다.

static void uninit_destroy (struct page *page);

• 페이지 구조체가 보유한 리소스를 해제한다. 페이지의 vm_type을 확인하고, 그에 따라 처리해야 할 수 있다.

현재로서는 익명 페이지만 처리할 수 있다. 나중에 이 함수를 다시 방문하여 파일 기반 페이지를 정리하는 작업을 진행할 것이다.

static void anon_destroy (struct page *page);

• 익명 페이지가 보유한 리소스를 해제한다. 페이지 구조체를 명시적으로 해제할 필요는 없으며, 호출자가 이를 처리해야 한다.

이제 Project 2의 모든 테스트를 통과해야 한다.

스택 확장 (Stack Growth)

Project 2에서는 스택이 USER_STACK에서 시작하는 단일 페이지로 제한되었고, 프로그램 실행은 이 크기 내에서만 이루어졌다. 이제 스택의 크기가 현재 크기를 초과하면 필요한 만큼 추가 페이지를 할당해야 한다.

추가 페이지는 오직 스택 접근으로 “보이는” 경우에만 할당되어야 한다. 스택 접근과 다른 접근을 구분하기 위한 휴리스틱 방법을 고안해야 한다.

유저 프로그램이 스택 포인터보다 아래에 스택을 쓰면, 프로그램이 오류가 발생한 것으로 간주된다. 왜냐하면 일반적인 운영 체제에서는 프로세스를 언제든지 중단하여 스택의 데이터를 수정하는 “시그널”을 전달할 수 있기 때문이다. 그러나 x86-64의 PUSH 명령어는 스택 포인터를 조정하기 전에 접근 권한을 확인하므로, 스택 포인터보다 8바이트 아래에서 페이지 폴트가 발생할 수 있다.

유저 프로그램의 스택 포인터의 현재 값을 얻을 수 있어야 한다. 유저 프로그램이 생성한 시스템 콜 또는 페이지 폴트 내에서는, syscall_handler() 또는 page_fault()에 전달된 struct intr_frame의 rsp 멤버에서 이를 가져올 수 있다. 잘못된 메모리 접근을 감지하기 위해 페이지 폴트에 의존할 경우, 커널에서 발생하는 페이지 폴트도 처리해야 한다. 프로세서가 예외로 인해 사용자 모드에서 커널 모드로 전환될 때만 스택 포인터를 저장하므로, page_fault()에 전달된 struct intr_frame에서 rsp 값을 읽으면 정의되지 않은 값이 나올 수 있다. 사용자 모드에서 커널 모드로 처음 전환될 때 rsp를 struct thread에 저장하는 방법과 같은 대체 방식을 마련해야 한다.

스택 확장 기능을 구현하라. 스택 확장을 구현하려면 먼저 vm/vm.c의 vm_try_handle_fault를 수정하여 스택 성장을 식별해야 한다. 스택 성장을 식별한 후에는 vm/vm.c의 vm_stack_growth 함수를 호출하여 스택을 확장해야 한다. vm_stack_growth를 구현하라.

bool vm_try_handle_fault (struct intr_frame *f, void *addr,
    bool user, bool write, bool not_present);

• 이 함수는 페이지 폴트 예외를 처리하는 동안 userprog/exception.c의 page_fault에서 호출된다. 이 함수에서 페이지 폴트가 스택 성장을 통해 처리될 수 있는 유효한 경우인지 확인해야 한다. 페이지 폴트가 스택 성장으로 처리될 수 있다고 확인되면, 폴트가 발생한 주소를 사용하여 vm_stack_growth를 호출해야 한다.

void vm_stack_growth (void *addr);

• 스택 크기를 증가시키기 위해 하나 이상의 익명 페이지를 할당하여 addr이 더 이상 폴트가 발생한 주소가 되지 않도록 한다. 할당을 처리할 때 addr을 PGSIZE로 반올림하여 처리해야 한다.

대부분의 운영 체제는 스택 크기에 대한 절대적인 제한을 부여한다. 일부 운영 체제는 유저가 스택 크기 제한을 조정할 수 있도록 하며, 예를 들어 많은 유닉스 시스템에서는 ulimit 명령을 통해 이를 설정할 수 있다. 많은 GNU/Linux 시스템에서 기본 제한은 8MB이다. 이 프로젝트에서는 스택 크기를 최대 1MB로 제한해야 한다.

이제 스택 확장에 관련된 모든 테스트 케이스를 통과해야 한다.

메모리 맵핑된 파일 (Memory Mapped Files)

이 섹션에서는 메모리 맵핑된 페이지를 구현할 것이다. 익명 페이지와는 달리, 메모리 맵핑된 페이지는 파일 기반 매핑을 사용한다. 페이지의 내용은 기존 파일의 데이터를 반영하며, 페이지 폴트가 발생하면 물리 프레임이 즉시 할당되고 파일에서 메모리로 내용을 복사한다. 메모리 맵핑된 페이지가 매핑 해제되거나 스왑 아웃될 때, 페이지의 변경 사항은 파일에 반영된다.

mmap 및 munmap 시스템 호출

메모리 맵핑된 파일에 대한 두 가지 시스템 호출인 mmap과 munmap을 구현하라. VM 시스템은 mmap 영역에서 페이지를 지연 로딩해야 하며, 매핑된 파일 자체를 매핑의 백업 저장소로 사용해야 한다. 이 두 시스템 호출을 구현하기 위해 vm/file.c에 정의된 do_mmap과 do_munmap을 구현하고 사용해야 한다.

void *mmap (void *addr, size_t length, int writable, int fd, off_t offset);

• fd로 열린 파일의 offset 바이트부터 length 바이트를 프로세스의 가상 주소 공간의 addr에 매핑한다. 파일 전체는 addr에서 시작하는 연속적인 가상 페이지들로 매핑된다. 파일의 길이가 PGSIZE의 배수가 아니면, 마지막 매핑된 페이지의 일부 바이트가 파일 끝을 넘어설 수 있다. 이 바이트들은 페이지가 폴트될 때 0으로 설정해야 하며, 페이지가 디스크로 다시 쓰일 때는 무시해야 한다. 성공하면 이 함수는 파일이 매핑된 가상 주소를 반환한다. 실패하면, 파일을 매핑할 수 없는 유효하지 않은 주소인 NULL을 반환해야 한다.

mmap 호출은 fd로 열린 파일의 길이가 0인 경우 실패할 수 있다. addr이 페이지 정렬되지 않거나, 매핑된 페이지의 범위가 스택 또는 실행 파일 로드 시 매핑된 페이지들을 포함하여 기존에 매핑된 페이지 집합과 겹칠 경우 반드시 실패해야 한다. 리눅스에서는 addr이 NULL이면 커널이 매핑할 적절한 주소를 찾아준다. 그러나 간단히 처리하기 위해 주어진 addr에서 mmap을 시도해야 한다. 따라서 addr이 0이면 실패해야 하며, 이는 일부 Pintos 코드가 가상 페이지 0이 매핑되지 않았다고 가정하기 때문이다. mmap은 길이가 0일 때도 실패해야 한다. 마지막으로, 콘솔 입력과 출력을 나타내는 파일 디스크립터는 매핑할 수 없다.

메모리 맵핑된 페이지는 익명 페이지와 마찬가지로 지연 방식으로 할당되어야 한다. vm_alloc_page_with_initializer 또는 vm_alloc_page를 사용하여 페이지 객체를 생성할 수 있다.

void munmap (void *addr);

• 지정된 주소 범위 addr의 매핑을 해제한다. 이 주소는 이전에 동일한 프로세스에서 mmap 호출로 반환된 가상 주소여야 하며, 아직 매핑이 해제되지 않은 상태여야 한다.

모든 매핑은 프로세스가 exit를 통해 종료되거나 다른 방법으로 종료될 때 자동으로 해제된다. 매핑이 해제될 때, 명시적이든 묵시적이든, 프로세스에 의해 쓰여진 모든 페이지는 파일에 다시 쓰여지며, 쓰이지 않은 페이지는 파일에 기록되지 않는다. 그 후, 해당 페이지들은 프로세스의 가상 페이지 목록에서 제거된다.

파일을 닫거나 제거해도 그 파일의 매핑은 해제되지 않는다. 한 번 생성된 매핑은 munmap이 호출되거나 프로세스가 종료될 때까지 유효하며, 이는 유닉스 규칙을 따른다. 자세한 내용은 Removing an Open File을 참조하라. 각 매핑에 대해 별도의 독립적인 파일 참조를 얻기 위해 file_reopen 함수를 사용해야 한다.

두 개 이상의 프로세스가 동일한 파일을 매핑할 경우, 일관된 데이터를 볼 필요는 없다. 유닉스에서는 두 매핑이 동일한 물리 페이지를 공유하도록 처리하며, mmap 시스템 호출에는 페이지가 공유되는지 아니면 개인적인지(즉, copy-on-write) 여부를 지정하는 인수가 있다.

필요에 따라 vm/vm.c의 vm_file_init과 vm_file_initializer를 수정해야 할 수도 있다.

void vm_file_init (void);

• 파일 기반 페이지 서브시스템을 초기화한다. 이 함수에서 파일 기반 페이지와 관련된 모든 설정을 할 수 있다.

bool file_backed_initializer (struct page *page, enum vm_type type, void *kva);

• 파일 기반 페이지를 초기화한다. 이 함수는 먼저 page->operations에 파일 기반 페이지에 대한 핸들러들을 설정한다. 페이지를 지원하는 파일과 같이, 페이지 구조체의 일부 정보를 업데이트해야 할 수도 있다.

static void file_backed_destroy (struct page *page);

• 파일과 연결된 파일을 닫음으로써 파일 기반 페이지를 제거한다. 페이지의 내용이 수정되었다면, 파일에 변경 사항을 기록해야 한다. 이 함수에서 페이지 구조체를 해제할 필요는 없다. file_backed_destroy의 호출자가 이를 처리해야 한다.

스왑 인/아웃 (Swap In/Out)

메모리 스왑은 물리 메모리 사용을 극대화하기 위한 메모리 회수 기법이다. 주 메모리의 프레임이 할당되었을 때, 시스템은 사용자 프로그램의 추가적인 메모리 할당 요청을 처리할 수 없다. 이 문제를 해결하는 한 가지 방법은 현재 사용되지 않는 메모리 프레임을 디스크로 스왑 아웃하는 것이다. 이렇게 하면 일부 메모리 리소스를 해제하고 다른 애플리케이션에 사용할 수 있게 된다.

스왑은 운영 체제에 의해 이루어진다. 시스템이 메모리가 부족하지만 메모리 할당 요청을 받으면, 운영 체제는 스왑 디스크로 퇴출할 페이지를 선택한다. 그런 다음 메모리 프레임의 정확한 상태가 디스크에 복사된다. 프로세스가 스왑 아웃된 페이지에 접근하려 하면, 운영 체제는 페이지의 정확한 내용을 메모리로 다시 가져와 복구한다.

퇴출 대상으로 선택된 페이지는 익명 페이지일 수도 있고 파일 기반 페이지일 수도 있다. 이 섹션에서는 각각의 경우를 처리할 것이다.

모든 스왑 작업은 명시적으로 호출되지 않고, 함수 포인터로 호출된다. 이들은 struct page_operations의 멤버로 file_ops에 등록되어 각 페이지의 초기화자에 대한 작업으로 사용된다.

익명 페이지 (Anonymous Page)

vm_anon.c에서 vm_anon_init과 anon_initializer를 수정하라. 익명 페이지는 이를 위한 백업 저장소가 없다. 익명 페이지의 스왑을 지원하기 위해, 우리는 스왑 디스크라는 임시 백업 저장소를 제공한다. 이 스왑 디스크를 활용하여 익명 페이지에 대한 스왑을 구현해야 한다.

void vm_anon_init (void);

• 이 함수에서는 스왑 디스크를 설정해야 한다. 또한, 스왑 디스크에서 사용 중인 영역과 여유 영역을 관리하기 위한 데이터 구조가 필요하다. 스왑 영역은 PGSIZE(4096 바이트) 단위로 관리되어야 한다.

bool anon_initializer (struct page *page, enum vm_type type, void *kva);

• 이 함수는 익명 페이지의 초기화자이다. 스왑을 지원하기 위해 anon_page에 추가적인 정보를 저장해야 한다.

이제 vm/anon.c에서 익명 페이지의 스왑을 지원하기 위해 anon_swap_in과 anon_swap_out을 구현하라. 페이지가 스왑 인되기 전에 스왑 아웃되어야 하므로, 먼저 anon_swap_out을 구현하는 것이 좋다. 데이터 내용을 스왑 디스크로 이동시키고, 이를 안전하게 메모리로 다시 가져와야 한다.

static bool anon_swap_in (struct page *page, void *kva);

스왑 디스크에서 익명 페이지를 스왑 인하여, 디스크의 데이터를 메모리로 읽어온다. 데이터의 위치는 페이지가 스왑 아웃될 때 페이지 구조체에 저장되어 있어야 한다. 스왑 테이블을 업데이트하는 것을 잊지 말아야 한다. (참고: 스왑 테이블 관리)

static bool anon_swap_out (struct page *page);

• 익명 페이지의 내용을 메모리에서 스왑 디스크로 복사하여 스왑 아웃한다. 먼저, 스왑 테이블을 사용하여 디스크에서 빈 스왑 슬롯을 찾은 후, 페이지 데이터를 해당 슬롯에 복사한다. 데이터의 위치는 페이지 구조체에 저장해야 한다. 디스크에 빈 슬롯이 더 이상 없으면, 커널을 패닉 상태로 만들어야 한다.

파일 기반 페이지 (File-Mapped Page)

파일 기반 페이지의 내용은 파일에서 가져오기 때문에, 메모리 맵핑된 파일은 백업 저장소로 사용되어야 한다. 즉, 파일 기반 페이지를 퇴출할 때는 해당 페이지를 매핑된 파일로 다시 기록해야 한다. vm/file.c에서 file_backed_swap_in과 file_backed_swap_out을 구현하라. 필요에 따라 file_backed_init과 file_initializer를 수정할 수 있다.

static bool file_backed_swap_in (struct page *page, void *kva);

• kva에서 페이지를 스왑 인하기 위해 파일에서 내용을 읽어온다. 파일 시스템과의 동기화가 필요하다.

static bool file_backed_swap_out (struct page *page);

• 페이지의 내용을 파일로 다시 기록하여 스왑 아웃한다. 먼저 페이지가 수정되었는지(더티 비트)를 확인하는 것이 좋다. 페이지가 수정되지 않았다면 파일의 내용을 수정할 필요가 없다. 페이지를 스왑 아웃한 후, 해당 페이지의 더티 비트를 꺼야 한다.

Copy-on-write (EXTRA)

Pintos에 copy-on-write 메커니즘을 구현하라.

Copy-on-write는 동일한 물리 페이지 인스턴스를 사용하여 자원 복사 작업을 더 빠르게 수행할 수 있게 하는 자원 관리 기법이다. 여러 프로세스가 동일한 자원을 사용하고 있을 경우, 일반적으로 각 프로세스는 충돌을 방지하기 위해 자원의 복사본을 가져야 한다. 그러나 자원이 수정되지 않고 단순히 읽기만 하는 경우, 물리 메모리에 여러 복사본을 유지할 필요가 없다.

예를 들어, fork를 통해 새로운 프로세스가 생성된다고 가정해보자. 자식 프로세스는 부모 프로세스의 자원을 상속받아, 해당 데이터를 가상 주소 공간에 복제해야 한다. 일반적으로, 가상 메모리에 데이터를 추가하는 과정은 물리 페이지를 할당하고, 프레임에 데이터를 기록하며, 페이지 테이블에 가상->물리 매핑을 추가하는 단계를 포함하며, 이 과정은 시간이 많이 걸릴 수 있다.

그러나 copy-on-write 기법을 사용하면 자원의 새로운 복사본을 위해 물리 페이지를 할당하지 않는다. 이는 데이터가 이미 물리 메모리에 존재하기 때문이다. 따라서 자식 프로세스의 페이지 테이블에 가상->물리 매핑만 추가하면 된다. 이때 부모와 자식 프로세스는 동일한 물리 페이지에서 동일한 데이터를 참조하지만, 여전히 별도의 가상 주소 공간을 통해 서로 분리되어 있으며, 운영체제만 이들이 동일한 프레임을 참조하고 있다는 사실을 알고 있다. 자원 중 하나가 공유 자원의 내용을 수정하려 할 때만 해당 자원을 위해 새로운 물리 페이지에 별도의 복사본을 생성하게 된다. 즉, 실제 복사 작업은 첫 번째 쓰기 작업이 일어날 때까지 연기된다.

따라서 운영체제는 copy-on-write 페이지에 대한 쓰기 시도를 감지할 수 있어야 한다. 이를 위해 운영체제는 “write-protect” 메커니즘을 사용한다. 이 개념은 간단하다: 쓰기 액세스 시 페이지 폴트가 발생하게 만드는 것이다. 메모리 관리 시스템의 지원으로, 쓰기 방지된 페이지를 모두 쓰기 불가능한 상태로 표시함으로써 쉽게 구현할 수 있다.

fork에서만 copy-on-write를 구현하면 된다. 자식 프로세스가 부모 프로세스의 자원을 상속받을 때, 자식이 자원을 수정하려 시도할 때까지 동일한 물리 데이터를 참조할 수 있다. 모든 쓰기 방지된 페이지는 퇴출될 수 있는 후보가 된다.

Pintos에서는 copy-on-write에 대한 기본 테스트 케이스만 제공된다. 우리가 모든 가능한 경우를 고려해야 한다 (작은 힌트: 파일 기반 페이지의 공유를 구현해야 한다). 이 추가 프로젝트의 평가는 숨겨진 테스트 케이스를 통해서도 이루어진다.

FAQ

프로젝트 3을 구현하기 위해서 프로젝트 2가 완성되어 있어야 하나요?

그렇다.

페이지 폴트를 처리한 후에 프로세스를 어떻게 다시 재개하나요?

page_fault()에서 반환하면 현재 유저 프로세스가 다시 재개된다. 그러면 명령어 포인터가 가리키고 있는 명령어를 다시 시도한다.

왜 유저 프로세스가 스택 포인터 위에서 폴트를 일으키나요?

스택 확장 테스트에서 유저 프로그램이 현재 스택 포인터 위의 주소에서 폴트를 일으키는 것을 볼 수 있다.

가상 메모리 시스템이 데이터 세그먼트의 확장을 지원해야 하나요?

그렇지않다. 데이터 세그먼트의 크기는 링커에 의해 결정된다. Pintos에는 아직 동적 할당이 없지만(유저 레벨에서 메모리 매핑 파일을 사용해 이를 “가짜로” 구현할 수는 있다), 데이터 세그먼트 확장을 지원하는 것은 잘 설계된 시스템에서는 추가적인 복잡성을 크게 증가시키지 않는다.

페이지 프레임을 할당할 때 왜 PAL_USER를 사용해야 하나요?

PAL_USER를 palloc_get_page()에 전달하면 메모리를 메인 커널 풀 대신 유저 풀에서 할당하게 된다. 유저 풀의 페이지가 부족해지면 유저 프로그램이 페이징을 시도하지만, 커널 풀의 페이지가 부족하면 많은 커널 함수들이 메모리를 얻지 못해 다양한 오류가 발생할 수 있다.

원한다면 palloc_get_page() 위에 다른 할당자를 추가할 수 있지만, palloc_get_page()는 기본 메커니즘으로 남아야 한다. 또한 -ul 커널 명령줄 옵션을 사용해 유저 풀의 크기를 제한하면, 다양한 유저 메모리 크기에서 가상 메모리 구현을 쉽게 테스트할 수 있다.