[PintOS] Project 3 - Virtual Memory git book, Introduction

Virtual Memory

 

프로젝트 3을 시작하기 이전에, 깃북을 읽어보아야한다!

By now you should have some familiarity with the inner workings of Pintos. Your OS can properly handle multiple threads of execution with proper synchronization, and can load multiple user programs at once. However, the number and size of programs that can run is limited by the machine's main memory size. In this assignment, you will remove that limitation by buiding an illusion of infinite memory.

 

여러 개의 유저 프로그램을 한번에 로드할 수 있지만 프로그램의 개수와 사이즈는 머신의 메인 메모리의 크기에 맞춰 제한되어 있었으나 이제 프로세스에게 메모리가 무한한 것처럼 느끼게 해줄 것인가 보다.

You will build this assignment on top of the last one. Test programs from project 2 should also work with project 3. You should take care to fix any bugs in your project 2 submission before you start work on project 3, because those bugs will most likely cause the same problems in project 3. For the project 3, we make step-by-step directions for your ease.

 

프로젝트 2에서 해결되지 않은 버그들은 3에서도 문제를 일으킬 가능성이 높다고 한다.

새로 만난 팀원의 코드는 multi-oom 빼고 다 되긴 한다. 이는 메모리 최적화를 위한 테스트여서, 일단은 넘어가는 것이 좋을 것 같다.

source files

You will work in the vm directory for this project. The 
Makefile is updated to turn on the setting -DVM. We provide an enormous amount of template code. 
You MUST follow the given template. That is, if you submit the code, that is not based on the given template, you get 0pts. Also, you should never change the template where it is marked "DO NOT CHANGE". Here, we provide some details about each template file that you will be modifying.

 

주어진 템플릿에 기반해야 한단다. ifdef 의 VM이 활성화 되고, DO NOT CHANGE 부분은 절대 수정하면 안된다.

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

Provides a general interface for virtual memory. In the header file, you can see the defintion and explanation for different vm_type -- VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE -- that your virtual memory system has to support (ignore VM_PAGE_CACHE for now, this is for project 4). You will also implement your supplementary page table here (read below).

 

vm.h 헤더파일에는 가상메모리의 기본적인 인터페이스가 있다.
우리의 가상 메모리 시스템은 다음과 같은 타입을 지원해야 한다.

VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE 등이 있는데, VM_PAGE_CACHE는 프로젝트 4 용이므로 지금은 필요 없다고 한다. 그리고 보조 테이블 페이지를 구현하게 된다고 한다.

 

파일을 살펴보니 enum타입으로 설정되어 있다.

enum vm_type {
	/* page not initialized */
	VM_UNINIT = 0,
	/* page not related to the file, aka anonymous page */
	VM_ANON = 1,
	/* page that realated to the file */
	VM_FILE = 2,
	/* page that hold the page cache, for project 4 */
	VM_PAGE_CACHE = 3,

	/* Bit flags to store state */

	/* Auxillary bit flag marker for store information. You can add more
	 * markers, until the value is fit in the int. */
	VM_MARKER_0 = (1 << 3),
	VM_MARKER_1 = (1 << 4),

	/* DO NOT EXCEED THIS VALUE. */
	VM_MARKER_END = (1 << 31),
};

 

이 vm.h에는 페이지 구조체와 프레임 구조체, 그리고 페이지 오퍼레이션(페이지가 할 역할?)도 같이 있다.

/* The representation of "page".
 * This is kind of "parent class", which has four "child class"es, which are
 * uninit_page, file_page, anon_page, and page cache (project4).
 * DO NOT REMOVE/MODIFY PREDEFINED MEMBER OF THIS STRUCTURE. */
struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */

	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

struct frame {
	void *kva;
	struct page *page;
};

/* The function table for page operations.
 * This is one way of implementing "interface" in C.
 * Put the table of "method" into the struct's member, and
 * call it whenever you needed. */
struct page_operations {
	bool (*swap_in) (struct page *, void *);
	bool (*swap_out) (struct page *);
	void (*destroy) (struct page *);
	enum vm_type type;
};

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
};

 

주석을 좀 보자면,

• struct page
  부모 클래스이다. 자식 클래스로 공용체로 선언된 구조체들인 uninit_page, file_page, anon_page 및 프로젝트 4를 위한 page_cache가 있다. 미리 정의된 멤버를 제거하거나 수정하면 안된다.
  공용체에 대해서 간략하게 살펴보자면, 구조체랑 비슷하지만 멤버들 중에서 가장 큰 자료형의 공간을 공유한다고 한다.
• struct page_operations
  page operation을 위한 함수 테이블이다. c에서 인터페이스를 구현하는 한 방법이다.
  메서드 테이블을 구조체의 멤버에 넣고 필요할 때마다 호출한다. -> 무슨 말인지 구현하면서 살펴봐야 될 것 같다.
• supplemental_page_table
  어떤 디자인이나 구조체가 없기 때문에 우리가 알아서 만들어야 한다.

vm.c는 구현하면서 좀 더 자세히 살펴보겠다.

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

Provides operations for uninitialized pages (vm_type = VM_UNINIT). Under the current design, all pages are initially set up as uninitialized pages, then it transforms to anonymous pages or file-backed pages.

 

vm_type이 VM_UNINIT이다.

초기화되지 않은 페이지들을 위한 기능을 제공한다.

현재 설계에서는 모든 페이지가 초기화되지 않은 페이지로 설정되어 있고, 이후 anonymous page나 file-backed page로 변환된다고 한다.

 

uninit.h를 보자면

/* Uninitlialized page. The type for implementing the
 * "Lazy loading". */
struct uninit_page {
	/* Initiate the contets of the page */
	vm_initializer *init;
	enum vm_type type;
	void *aux;
	/* Initiate the struct page and maps the pa to the va */
	bool (*page_initializer) (struct page *, enum vm_type, void *kva);
};

uninit_page 구조체는 초기화되지 않은 페이지를 나타내며, "lazy loading"을 구현하는데 사용되는 타입이다.

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

Provides operations for anonymous pages (vm_type = VM_ANON).

 

vm_type이 VM_ANON으로

anonymous page를 위한 기능을 제공하는 파일이다.

 

anon.h에는 아무것도 없다. TO_DO조차도 없다... 그냥 다 구현해야 할 것 같다.

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

Provides operations for file-backed pages (vm_type = VM_FILE).

 

vm_type가 VM_FILE로

file-backed page를 위한 기능을 제공한다.

 

file.h도 역시 마찬가지로 아무것도 없다..

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

Contains memory inspection operations for grading. Do not change this files.

 

채점을 위한 메모리 검사 기능을 포함하는 파일로, 수정해서는 안된다.

Most of the code you write for this project will be files in vm directory and in files introduced in earlier projects. You will probably be encountering just a few files for the first time such as:

 

이번 프로젝트에서 우리가 작성할 코드들은 대부분 vm경로와 이전 프로젝트틀에서 소개되었던 파일들에 있다고 한다.

다음의 파일들만 새로운 수정할 파일들이다.

include/devices/disk.h, devices/disk.c

Provides sector-based read and write access to block device. You will use this interface to access the swap partition as a block device.

 

블록 디바이스로의 섹터 기반의 읽기, 쓰기 기능을 제공한다.

이 인터페이스는 블록 디바이스로 스왑 파티션에 접근할 때 사용하게 될 것이다.

 

스왑 파티션이란?

운영체제의 메모리가 완전히 가득 차면 추가적으로 실행되는 프로그램은 메모리가 아닌 스왑 파티션에서 실행된다.

메모리 공간이 가득 차 부족할 때 프로그램이 실행가능하도록 예비 공간의 역할을 한다.

스왑 파티션은 하드디스크에 저장되므로, 속도가 RAM에 비해 매우 느리다.

 

블록 디바이스란?

블록 디바이스란, 하드디스크나 cd, dvd등의 장치를 말하며 블록이나 섹터 등의 정해진 단위로 데이터를 전송한다.

I/O 전송속도가 높은 것이 특징이고, 다른 종류로 캐릭터 디바이스라는 것이 있다.

disk.c와 disk.h는 봐도 잘 모르겠다...

Memory Terminology

Pages

A page, sometimes called a virtual page, is a continuous region of virtual memory of size 4,096 bytes (the 
page size) in length. A page must be page-aligned, that is, start on a virtual address evenly divisible by the page size. Thus, the last 12 bits of a 64-bit virtual address is the page offset (or just offset). The upper bits are used to indicate the index in the page table, which will be introduced soon. With 64-bit system, we use 4-level page table, which makes a virtual address to look like this:

 

가상 페이지라고도 불리는 페이지는, 4096바이트(페이지 크기)의 길이를 가지는 가상 메모리의 연속된 영역이다.

페이지는 반드시 페이지에 정렬되어 있어야 한다.

즉, 각 페이지는 반드시 페이지 크기(4KiB)로 균등하게 나누어지는 가상 주소에서 시작해야 한다는 말이다.

그러므로 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

 

권영진 교수님 강의에서는 다음과 같이 표현한다.

Each process has an independent set of user (virtual) pages, which are those pages below the virtual address  KERN_BASE(0x8004000000). The set of kernel (virtual) pages, on the other hand, is global, and thus remain in the same position regardless of what thread or process is running. The kernel may access both user and kernel pages, but a user process may access only its own user pages. See Virtual Memory Layout, for more information.

 

각 프로세스는 KERN_BASE(커널 영역) 미만의 가상 주소값을 가지는 독립적인 유저(가상)페이지 집합을 가진다.

반면에 커널(가상) 페이지 집합은 전역적이고 어떤 쓰레드나 프로세스가 실행되고 있든 간에 항상 같은 위치에 남아있다.

커널은 유저 페이지와 커널 페이지 모두에 접근할 수 있지만, 유저 프로세스는 본인의 유저 페이지에만 접근할 수 있다.

Pintos provides several useful functions for working with virtual addresses. See Section Virtual Addresses, for details.

 

물리주소와 커널 가상주소 사이를 변환해주는 함수는 이전에 프로젝트 2에서 사용한 바 있다.

Frames

A frame, sometimes called a physical frame or a page frame, is a continuous region of physical memory. Like pages, frames must be page-size and page-aligned. Thus, a 64-bit physical address can be divided into a frame number and a frame offset (or just offset), like this:

 

물리 프레임 또는 페이지 프레임이라고도 불리는 프레임은, 물리 메모리 상의 연속적인 영역이다.

페이지와 동일하게 프레임은 페이지 사이즈여야 하고 페이지 크기에 따라 정렬되어 있어야 한다.

그러므로 64비트 물리주소는 프레임 넘버와 프레임 오프셋(또는 그냥 오프셋)으로 나누어질 수 있다. 다음과 같다.

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

 

x86-64 시스템은 물리주소에 있는 메모리에 직접적으로 접근하는 방법을 제공하지 않는다.

Pintos는 커널 가상 메모리를 물리 메모리에 직접 매핑하는 방식을 통해서 이 문제를 해결한다.

커널의 가상메모리의 첫 페이지는 물리메모리의 첫 프레임에 매핑되어 있고, 두 번째 페이지는 두 번째 프레임에 매핑되고... 계속 순차적으로 매핑되어 있다.

그러므로 커널 가상메모리를 통하면 프레임들에 접근할 수 있다.

Pintos provides functions for translating between physical addresses and kernel virtual addresses. See 
Virtual Addresses for details.

 

핀토스는 물리주소와 커널 가상주소 사이를 변환해주는 함수를 제공한다.

 

Page Tables

A page table is a data structure that the CPU uses to translate a virtual address to a physical address, that is, from a page to a frame. The page table format is dictated by the x86-64 architecture. Pintos provides page table management code in threads/mmu.c.

 

페이지 테이블은 CPU가 가상주소를 물리주소로 즉, 페이지를 프레임으로 변환하기 위해 사용하는 자료구조이다.

페이지 테이블 포맷은 x86-64 아키텍쳐에 의해 결정되었다.

threads/mmu.c 안에 페이지 테이블을 관리하는 코드가 있다.

 

The diagram below illustrates the relationship between pages and frames. The virtual address, on the left, consists of a page number and an offset. The page table translates the page number into a frame number, which is combined with the unmodified offset to obtain the physical address, on the right.

 

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

 

이 도표는 페이지와 프레임 사이의 관계를 나타낸다.

왼쪽에 보이는 가상 주소는 페이지 넘버와 오프셋을 포함하고 있다.

페이지 테이블은 페이지 넘버를 프레임으로 변환하고, 프레임 넘버는 오른쪽에 보이는 것처럼 물리 주소를 획득하기 위한 미수정된 오프셋과 결합되어 있다.

 

Resource Management Overview

우리는 다음과 같은 자료구조들을 설계하고 구현해야 한다:

supplemental page table

Enables page fault handling by supplementing the page table. See Managing the Supplemental Page Table below.

 

보조 페이지 테이블

페이지 테이블을 보조해서, 페이지 폴트 핸들링이 가능하도록 해준다.

frame table

Allows efficient implementation of eviction policy of physical frames. See Managing the Frame Table below.

 

물리 프레임의 eviction policy(쫓아내는 정책)을 효율적으로 구현하도록 해준다.

swap table

Tracks usage of swap slots. See Managing the Swap Table below.

 

스왑 슬롯이 사용되는 것을 추적한다. 

You do not necessarily need to implement three completely distinct data structures: it may be convenient to wholly or partially merge related resources into a unified data structure. For each data structure, you need to determine what information each element should contain. You also need to decide on the data structure's scope, either local (per-process) or global (applying to the whole system), and how many instances are required within its scope. To simplify your design, you may store these data structures in non-pageable memory (e.g., memory allocated by calloc or malloc). That means that you can be sure that pointers among them will remain valid.

 

이 세 자료구조를 별개로 구현하기 보다 연관된 자원들을 통합된 자료구조로 전부 또는 부분적으로 합치는 것이 편하다고 한다.

즉, 하나 만들어서 여러군데서 쓰라는 말 같다.

또 우리는 각 자료구조에서 각각의 원소가 어떤 정보를 담을지를 정해야 한다.

자료구조의 범위를 프로세스별로(지역별) 할지, 전체로(전역)으로 할지도 정해야 하고, 해당 범위에 필요한 인스턴스의 수도 정해야 한다.

설계를 쉽게 하기 위해 non-pageable 메모리(calloc이나 malloc으로 할당된)에 이런 자료구조들을 저장할 수 있다.

즉 자료구조들 사이에 포인터가 유효하게 유지하게끔 만들 수 있다.

 

Choices of implementation (performance perspective)

Possible choices for implementation include arrays, lists, bitmaps, and hash tables. An array is often the simplest approach, but a sparsely populated array wastes memory. Lists are also simple, but traversing a long list to find a particular position wastes time. Both arrays and lists can be resized, but lists more efficiently support insertion and deletion in the middle.

 

구현을 위한 가능한 선택지로는 배열, 리스트, 해시 테이블이 있다.

대개는 배열이 가장 단순한 접근법이지만, 밀도가 희박한 배열은 메모리를 낭비시킨다.

리스트 또한 단순하지만 특정 위치를 찾기 위해 긴 리스트를 순회하는 것은 시간을 소모한다.

배열과 리스트 둘 다 크기 재조정이 가능하지만, 중간 부분의 삽입과 삭제에 있어서는 리스트가 더 효율적이다.

 

코치님께서 해시 테이블을 구현하게 될 거라고 하셨는데, 리스트가 지금까진 가장 익숙하다..

 

Pintos includes a bitmap data structure in lib/kernel/bitmap.c and include/lib/kernel/bitmap.h. A bitmap is an array of bits, each of which can be true or false. Bitmaps are typically used to track usage in a set of (identical) resources: if resource n is in use, then bit n of the bitmap is true. Pintos bitmaps are fixed in size, although you could extend their implementation to support resizing.

 

lib/kernel/bitmap.c, include/lib/kernel/bitmap.h 파일에 비트맵 자료구조가 있다.

비트맵은 각각이 true/false의 값을 가질 수 있는 비트들로 이우러진 배열이다.

일반적으로 비트맵은 동일한 자원 집합 내부에서 사용 현황을 추적하기 위해 사용된다.

자원 n이 사용중이면, 비트맵의 비트 n은 true 값을 가진다.

핀토스 비트맵은 크기가 고정되어 있지만 구현을 확장해서 리사이징을 지원할 수 있도록 할 수 있다 -> 동적으로 바꿀 수 있다는 말 같다.

 

Pintos also includes a hash table data structure (See Hash Table). Pintos hash tables efficiently support insertions and deletions over a wide range of table sizes.

 

핀토스는 또한 해시 테이블 자료구조를 포함하고 있다.

핀토스 해시 테이블은 다양한 테이블 크기에서의 삽입과 삭제를 효율적으로 지원한다.

해시 테이블과 관련된 내용은 appendix에서 살펴보면 된다.

 

Although more complex data structures may yield better performance or other benefits, they may also needlessly complicate your implementation. Thus, we do not recommend implementing any advanced data structure (e.g. a balanced binary tree) as part of your design.

 

비록 더 복잡한 자료구조들이 더 나은 성능과 기타 이점들을 가져올 수 있겠지만, 불필요하게 복잡하게 할 필요 없다.

균형이진트리 같은 고급 자료구조를 사용하는 것은 비추천한다.

Managing the Supplemental Page Table

The supplemental page table supplements the page table with additional data about each page. It is needed because of the limitations imposed by the page table's format. Such a data structure is often called a "page table" also; we add the word "supplemental" to reduce confusion.

 

보조 페이지 테이블은 각 페이지에 대한 추가 데이터를 이용해서 페이지 테이블을 보조한다.

페이지 테이블의 포맷으로 인해 생기는 제한들 때문에 보조 페이지 테이블이 필요하다.

어느 곳에서는 그냥 페이지 테이블로도 불린다는데, 권영진 교수님의 정의에 의하면

"frame, disk, swap 중 어디에 존재하는지에 대한 데이터가 존재하는 곳의 위치 정보와 이에 상응하는 커널 가상주소를 가리키는 포인터 정보, active인지 inactive인지 등에 대한 정보를 각각의 페이지에 대해서 담고 있는 프로세스마다 존재하는 자료구조"

라고 한다.

 

The supplemental page table is used for at least two purposes. Most importantly, on a page fault, the kernel looks up the virtual page that faulted in the supplemental page table to find out what data should be there. Second, the kernel consults the supplemental page table when a process terminates, to decide what resources to free.

 

보조 페이지 테이블의 최소한의 목적 두 가지는 다음과 같다.

1. 페이지 폴트가 발생했을 때, 그곳에 어떤 데이터가 있었어야 했는지를 알아내기 위해 커널은 보조 페이지 테이블에서 페이지 폴트가 발생한 가상 페이지를 탐색한다.
2. 커널이 프로세스가 종료될 때 어떤 자원을 해제(free)할지 고르기 위해서 보조 페이지 테이블을 조사한다.

Organization of Supplemental Page Table

You may organize the supplemental page table as you wish. There are at least two basic approaches to its organization: in terms of segments or in terms of pages. A segment here refers to a consecutive group of pages, i.e., memory region containing an executable or a memory-mapped file.

 

우리는 원하는 방식으로 보조 페이지 테이블을 구성할 수 있다.

구조에 접근하는 두 가지 기본적인 방법이 있다.

1. 세그먼트(조각) 측면
2. 페이지 측면

세그먼트는 연속된 페이지 그룹을 의미한다.
예를 들어 실행파일을 포함하는 메모리 영역이나, memory-mapped file이 있다.

Optionally, you may use the page table itself to track the members of the supplemental page table. You will have to modify the Pintos page table implementation in threads/mmu.c to do so. We recommend this approach for advanced students only.

 

선택적으로, 보조 페이지 테이블을 추적하기 위해 페이지 테이블 자체를 사용할 수 있는데

이렇게 하기 위해서는 threads/mmu.c에 있는 핀토스의 페이지 테이블 구현을 수정해야한다.

잘 하는 학생들만 선택하라니.. 하지 말라는걸까 싶다.

 

페이지 테이블 자체를 사용하면 mmu.c에 있는 페이지 테이블과 관련된 함수들도 수정해야 하는 것 같다.

 

Handling page fault

The most important user of the supplemental page table is the page fault handler. In project 2, a page fault always indicated a bug in the kernel or a user program. In project 3, this is no longer true. Now, a page fault might only indicate that the page must be brought in from a file or swap slot. You will have to implement a more sophisticated page fault handler to handle these cases. The page fault handler, which is page_fault() in userprog/exception.c, calls your page fault handler, vm_try_handle_fault() in vm/vm.c.

 

페이지 폴트 핸들러에서 보조 페이지 테이블을 주로 사용한다.

프로젝트 2에서는 페이지 폴트가 항상 커널 또는 응용 프로그램의 버그였지만 이제는 파일 또는 스왑 슬롯에서 페이지를 가져와야 된다는 의미로 바뀌게 된다. 이를 위해 더 복잡한 페이지 폴트 핸들러를 구현해야 한다.

userprog/exception.c에 있는 페이지 폴트 핸들러 page_fault()는 vm/vm.c에 있는 우리의 페이지 폴트 핸들러 vm_try_handle_fault()를 호출한다.

 

page_fault() 함수 안의 vm_try_handle_fault() 핸들러는 다음과 같다.

/* Return true on success */
bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */

	return vm_do_claim_page (page);
}

 

페이지 폴트를 적절히 경우에 따라 처리해주면 될 것 같다. 그리고 그 경우들은 다음과 같다.

 

Your page fault handler needs to do roughly the following: Locate the page that faulted in the supplemental page table. If the memory reference is valid, use the supplemental page table entry to locate the data that goes in the page, which might be in the file system, or in a swap slot, or it might simply be an all-zero page. If you implement sharing (i.e., Copy-on-Write), the page's data might even already be in a page frame, but not in the page table. If the supplemental page table indicates that the user process should not expect any data at the address it was trying to access, or if the page lies within kernel virtual memory, or if the access is an attempt to write to a read-only page, then the access is invalid. Any invalid access terminates the process and thereby frees all of its resources. Obtain a frame to store the page. If you implement sharing, the data you need may already be in a frame, in which case you must be able to locate that frame. Fetch the data into the frame, by reading it from the file system or swap, zeroing it, etc. If you implement sharing, the page you need may already be in a frame, in which case no action is necessary in this step. Point the page table entry for the faulting virtual address to the physical page. You can use the functions in threads/mmu.c.

 

1. 보조 페이지 테이블에서 폴트가 발생한 페이지를 찾는다.
   만일 메모리 참조가 유효하다면 보제 페이지 엔트리를 사용해서 데이터가 들어갈 페이지를 찾아야 한다.
   페이지는 파일 시스템, 스왑 슬롯에 있거나 단순히 0으로만 이루어져야 할 수도 있다.
   만약 CoW를 구현한다면 또 신경써줘야 할 것이있다. - extra이므로 일단은 넘어가보자.
   만약 보조 페이지 테이블이 다음과 같다면 유효하지 않은 접근이라는 의미이다.
   
   유저 프로세스가 접근하려던 주소에서 데이터를 얻을 수 없을 때
   페이지가 커널 가상 메모리 영역에 존재 할 때
   읽기 전용 페이지에 대해 쓰기를 시도할 때
   
   이와 같은 유효하지 않은 접근은 프로세스를 종료하고 프로세스의 모든 자원을 해제해야 한다.
2. 페이지를 저장하기 위해 프레임을 획득한다.
   만약 공유를 구현하면, 필요한 데이터는 이미 프레임 안에 있을 것이다.
3. 데이터를 파일 시스템이나 스왑에서 읽어오거나, 0으로 초기화 하는 등의 방식으로 만들어서 프레임으로 가져온다.
   공유를 구현한다면 필요한 페이지가 이미 프레임 안에 있기 때문에, 별 다른 조치가 필요하지 않다.
4. 폴트가 발생한 가상주소에 대한 페이지 테입르 엔트리가 물리 페이지를 가리키도록 지정한다.
   threads/mmu.c의 함수를 사용하라.

Managing the Frame Table

The frame table contains one entry for each frame.
Each entry in the frame table contains a pointer to the page, if any, that currently occupies it, and other data of your choice. The frame table allows Pintos to efficiently implement an eviction policy, by choosing a page to evict when no frames are free.

 

프레임 테이블에는 각 프레임의 엔트리 정보가 담겨 있다.

프레임 테이블의 각 엔트리에는 현재 해당 엔트리를 차지하고 있는 페이지에 대한 포인터 그리고 기타 데이터들이 담겨 있다.

프레임 테이블은 비어있는 프레임이 없을 때 쫓아낼 페이지를 골라줘서 핀토스가 효율적으로 eviction policy를 구현할 수 있도록 해준다.

 

The frames used for user pages should be obtained from the "user pool," by calling palloc_get_page(PAL_USER). You must use PAL_USER to avoid allocating from the "kernel pool," which could cause some test cases to fail unexpectedly. If you modify palloc.c as part of your frame table implementation, be sure to retain the distinction between the two pools.

 

유저 페이지를 위해 사용된 프레임들은 palloc_get_page(PAL_USER)를 호출함으로써 'user pool'에서 획득된 것이어야 한다.

'kernel pool'에서 할당했다가 예상치 못하게 테스트 케이스에서 실패하는 일을 막기 위해서는, 반드시 PAL_USER을 사용해야 한다.

 

The most important operation on the frame table is obtaining an unused frame. This is easy when a frame is free. When none is free, a frame must be made free by evicting some page from its frame.

 

프레임 테이블에서 가장 중요한 작업은 사용되지 않은 프레임을 획득하는 것이다.

이는 프레임이 free 상태라면 간단하다.

하지만 free 상태인 프레임이 없다면, 몇몇 페이지들을 프레임에서 쫓아내 그 프레임을 free 상태로 만들어 주어야 한다.

 

If no frame can be evicted without allocating a swap slot, but swap is full, panic the kernel. Real OSes apply a wide range of policies to recover from or prevent such situations, but these policies are beyond the scope of this project.

 

만약 스왑 슬롯의 할당 없이 쫓아낼 수 있는 프레임이 없는데, 스왑 슬롯마저 꽉 차있다면 커널을 패닉시킨다.

실제 OS들은 이런 상황을 막거나 복구하기 위해 다양한 정책들을 적용하고 있지만, 우리와는 상관 없는 사항이다.

 

The process of eviction comprises roughly the following steps: Choose a frame to evict, using your page replacement algorithm. The "accessed" and "dirty" bits in the page table, described below, will come in handy. Remove references to the frame from any page table that refers to it. Unless you have implemented sharing, only a single page should refer to a frame at any given time. If necessary, write the page to the file system or to swap. The evicted frame may then be used to store a different page.

 

eviction 절차는 다음과 같다.

1. 일단 우리가 페이지 재배치 알고리즘을 구현해야하고, 이를 이용해 evict할 대상을 고른다.
   알고리즘을 구현하는 데 accessed, dirty 비트들을 사용하는 것이 유용하다.
2. 선택된 프레임을 참조하는 모든 페이지 테이블에서 참조를 제거한다.
   공유가 구현되지 않았을 경우, 해당 프레임을 참조하는 페이지는 항상 한개만 존재해야 한다.
3. 필요하다면, 페이지를 파일 시스템이나 스왑에 write 한다.
   evicted된 프레임은 이제 다른 페이지를 저장하는 데에 사용할 수 있다.

Accessed and Dirty Bits

x86-64 hardware provides some assistance for implementing page replacement algorithms, through a pair of bits in the page table entry (PTE) for each page. On any read or write to a page, the CPU sets the accessed bit to 1 in the page's PTE, and on any write, the CPU sets the dirty bit to 1. The CPU never resets these bits to 0, but the OS may do so.

 

x86-64 하드웨어는 각 페이지의 페이지 테이블 엔트리(PTE)에 있는 비트 쌍을 이용해 페이지 재배치 알고리즘 구현을 위한 도움을 제공한다.

페이지에 read 하거나 write 할 때, CPU는 페이지의 PTE에 있는 accessed 비트를 1로 설정한다.

그리고 write 할 때, CPU는 dirty 비트를 1로 설정한다.

CPU는 절대 이 비트들을 0으로 되돌리지 않고, 대신 OS가 되돌릴 수 있다.

 

You need to be aware of aliases, that is, two (or more) pages that refer to the same frame. When an aliased frame is accessed, the accessed and dirty bits are updated in only one page table entry (the one for the page used for access). The accessed and dirty bits for the other aliases are not updated.

 

같은 프레임을 참조하는 두 개(또는 그 이상)의 페이지들인 aliases를 조심해야 한다.

aliased 프레임이 accessed 될 떄, accessed와 dirty 비트는 하나의 페이지 테이블 엔트리에서만 업데이트 된다(access에 쓰인 페이지만).

다른 alias들에 대한 accessed와 dirty 비트는 업데이트 되지 않는다.

 

같은 프레임을 두 개 이상의 페이지가 참조하면 aliased 되었다고 한다.

컴퓨터에서는 동일한 주소를 다른 이름으로 명명하는 상황을 alias된다고 한다.

 

In Pintos, every user virtual page is aliased to its kernel virtual page. You must manage these aliases somehow. For example, your code could check and update the accessed and dirty bits for both addresses. Alternatively, the kernel could avoid the problem by only accessing user data through the user virtual address.

 

핀토스에서 모든 유저 가상 페이지는 커널 가상 페이지에 alias 되어 잇다.

우리는 이 alias들을 무조건 관리해야한다.

예를 들면, 우리의 코드는 양쪽 주소 모두를 위한 accessed와 dirty 비트를 확인하고 업데이트 할 수 있어야 한다.

또는, 오직 유저 가상 주소를 통해서만 유저 데이터에 접근하게 함으로써 커널이 이 문제를 피하게 할 수 있다.

 

커널이 아닌 다른 alias들은 공유를 구현하는 경우에만 나타나야 한다.

아니면, 우리 코드에 버그가 있을 때도 나타날 수 있다.

accessed와 dirty 비트를 활용하기 위한 함수들은 Page Table Accessed and Dirty Bits를 확인하면 된다.

 

Managing the Swap Table

The swap table tracks in-use and free swap slots. It should allow picking an unused swap slot for evicting a page from its frame to the swap partition. It should allow freeing a swap slot when its page is read back or the process whose page was swapped is terminated.

 

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

프레임에 있는 페이지를 스왑 파티션으로 evict 하기 위해서, 스왑 테이블은 미사용된 스왑 슬롯을 고를 수 있도록 해줘야 한다.

페이지가 다시 읽혀서 돌아가거나, 페이지 주인인 프로세스가 종료되어 버릴 경우에는 스왑 테이블이 스왑 슬롯을 free 해줄 수도 있어야 한다.

 

From the vm/build directory, use the command pintos-mkdisk swap.dsk --swap-size=n to create a disk named  swap.dsk that contains a n-MB swap partition. Afterward, swap.dsk will automatically be attached as an extra disk when you run pintos. Alternatively, you can tell pintos to use a temporary n-MB swap disk for a single run with --swap-size=n.

 

vm/build 디렉토리에서 n 메가바이트의 스왑 파티션을 포함하는 swap.dsk라는 디스크를 생성하기 위해서

pintos-mkdisk swap.dsk --swap-size=n 명령을 사용해야한다.

그러면, swap.dsk는 핀토스를 실행할 때 자동으로 추가 디스크로써 연결될 것이다.

또는 --swap-size=n 명령어를 사용하여 일회성 실행을 위한 임시 스왑 디스크를 사용하게 할 수 있다.

 

Swap slots should be allocated lazily, that is, only when they are actually required by eviction. Reading data pages from the executable and writing them to swap immediately at process startup is not lazy. Swap slots should not be reserved to store particular pages.

 

스왑 슬롯은 lazy하게 할당되어야 한다.

그 말은 즉, evict는 실제로 필요할 때만 할당되어야 한다는 말이다.

프로세스가 시작될 때 실행 파일에서 데이터 페이지들을 읽고 스왑에 곧바로 쓰는 행위는 lazy 한 것이 아니다.

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

Free a swap slot when its contents are read back into a frame.

 

스왑 슬롯의 내용물이 프레임으로 읽혀 돌아오면 그 때 스왑 슬롯을 free 해주면 된다.

 

Managing Memory Mapped Files

The file system is most commonly accessed with read and write system calls. A secondary interface is to "map" the file into virtual pages, using the mmap system call. The program can then use memory instructions directly on the file data. Suppose file foo is 0x1000 bytes (4 kB, or one page) long. If foo is mapped into memory starting at address 0x5000, then any memory accesses to locations 0x5000. . .0x5fff will access the corresponding bytes of foo.

 

파일 시스템은 read와 write 시스템 콜에 의해 가장 많이 access 된다.

두 번째 인터페이스는 mmap 시스템 콜을 사용해서 파일을 가상 페이지에 '매핑'하는 것이다.

그러면 프로그램이 파일 데이터에서 직접 메모리 인스트럭션(명령)을 사용할 수 있게 된다.

파일 'foo'가 0x1000바이트(4KB 또는 한 개 페이지) 크기를 가졌다고 가정해 보자.

만약 foo가 0x5000 주소에서 시작하는 메모리에 매핑되어 있다면, 0x5000. . . 0x5fff 공간에 메모리 접근을 하면 그에 대응되는 foo 파일의 바이트들에 접근 될 것이다.

 

Here's a program that uses mmap to print a file to the console. It opens the file specified on the command line, maps it at virtual address 0x10000000, writes the mapped data to the console (fd 1), and unmaps the file.

 

이는 파일을 콘솔에 출력하기 위해 mmap을 사용하는 프로그램이다.

커맨드라인에 명시된 파일을 열고, 가상 주소 0x10000000에 매핑해서 매피된 데이터를 콘솔에 write하고 (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;
}

 

이는 매핑된 영역에서 발생하는 페이지 폴트를 적절히 다루기 위해서,

그리고 매핑된 파일이 프로세스의 다른 세그먼트들에 덮어쓰이는 일이 없도록 하기 위해서

우리의 구현은 어떤 메모리가 메모리-매핑 파일에 의해 사용되었는지 반드시 추적할 수 있어야 한다.

---

읽다가 이해가 안되는 부분이 더 많았지만, 이제 코드를 보면서 구현을 해나가야 될 것 같다.

다른 chapter들은 코드를 좀 보고난 후 진행해야할 것 같다.

 

Reference

https://yjohdev.notion.site/PROJECT-3-VIRTUAL-MEMORY-d16fc8d04f4d4829b7e25691a235901c

PROJECT 3 : VIRTUAL MEMORY | Notion

https://sergeswin.com/1034/

리눅스 스왑(SWAP) 파티션이란 무엇? 어떤 일을 하나요?