Project 3: Virtual Memory

Introduction

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 building an illusion of infinite memory.

Background

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:

가상 페이지라 불리는 페이지는 가상 메모리의 연속적인 영역이다. 페이지는 페이지 크기로 나누어지는 가상 주소에서 시작하여 페이지 순으로 정렬된다. 그렇기 때문에 가상 주소의 마지막 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.

각 프로세스는 KERN_BASE 아래에 위치한 가상 주소들로 이뤄진 페이지들로 구성된 독립적인 사용자 (가상) 페이지의 집합을 가진다. 커널 (가상) 페이지의 집합은 전역에 공유되기 때문에 어떤 쓰레드나 프로세스가 실행 중인지와 상관없이 같은 곳에 위치한다. 사용자 프로세스는 사용자 페이지에만 접근할 수 있는 반면에 커널은 사용자와 커널 페이지 모두에 접근할 수 있다.

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비트 물리 주소는 20비트의 프레임 번호와 12비트의 프레임 오프셋으로 구성된다.

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

x86-64 doesn't provide any way to directly access memory at a physical address. Pintos works around this by mapping kernel virtual memory directly to physical memory - the first page of kernel virtual memory is mapped to the first frame of physical memory, the second page to the second frame, and so on. Thus, frames can be accessed through kernel virtual memory.

x86-64는 물리 메모리에 직접 접근할 수 있는 권한을 제공하지 않는다. 핀토스는 커널 가상 메모리를 물리 메모리에 매핑하는 방식으로 작동한다. 커널 가상 메모리의 첫 번째 페이지는 물리 메모리의 첫 번째 프레임에 매핑되고, 두 번째 페이지는 두 번째 프레임에 매핑되는 방식이다. 따라서 물리 프레임은 가상 메모리 페이지를 통해 접근할 수 있다.

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가 가상 주소를 물리 주소로 번역하기 위해 사용하는 자료 구조이다.

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    ^
                  \_______________________________________/

Swap Slots

A swap slot is a page-size region of disk space in the swap partition. Although hardware limitations dictating the placement of slots are more flexible than for frames, swap slots should be page-aligned because there is no downside in doing so.

스왑 슬롯은 스왑 파티션에 존재하는 페이지 크기의 저장 공간 상의 영역이다. 스왑 슬롯은 페이지 순으로 정렬된다.

Supplemental Page Table

Enables page fault handling by supplementing the page table.

Supplemental Page Table은 페이지 폴트를 다룬다.

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.

추가 페이지 테이블은 페이지 테이블에 각 페이지에 대한 추가적인 데이터를 제공한다. 기존 페이지 테이블의 한계로 인해 추가 페이지 테이블이 필요하다.

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.

추가 페이지 테이블은 두 가지 목적을 위해 사용된다. 커널은 일으킨 가상 페이지를 필요한 정보를 찾기 위해 추가 페이지 테이블에서 확인한다. 또한 커널은 프로세스가 종료될 시 어떤 리소스를 해제해야 할 지 결정하기 위해 추가 페이지 테이블을 확인한다.

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.

추가 페이지 테이블

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.

추가 페이지 테이블의 멤버를 검토하기 위해 페이지 테이블을 사용하기도 한다.

Frame Table

Allows efficient implementation of eviction policy of physical frames.

프레임 테이블은 효과적인 물리 프레임의 처리 방식을 구현한다.

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.

프레임 테이블은 각 프레임 당 한 엔트리를 포함한다. 프레임 테이블의 각 엔트리는 페이지를 가리키는 포인터를 포함한다. 프레임 테이블은 프레임이 부족할 때 제거할 페이지를 결정함으로써 핀토스가 효율적으로 관리한다.

Swap Table

Tracks usage of swap slots.

스왑 테이블은 스왑 슬롯의 사용을 검토한다.

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.

스왑 테이블은 사용 중인 스왑 슬롯과 그렇지 않은 스왑 슬롯을 검토한다. 스왑 테이블은 사용 중이지 않은 페이지를 프레임으로부터 제거하여 스왑 슬롯을 고르게 한다.

Virtual Memory

핀토스의 메모리 개요

• 현재 주소공간은 4개의 세그먼트로 구성되어 있다.

1. Stack
2. Initialized data
3. Uninitialized data
4. Code
5. Heap은 현재 없는 상태

• 프로세스의 메모리 탑재 과정

• 각 세그먼트가 물리 페이지에 탑재된다.
• 페이지 테이블을 초기화한다.

PintOS의 프로세스 주소 공간

1. Swap을 사용할 수 없다.

2. Demand Paging을 사용할 수 없다.

3. Virtual Memory가 구현되어 있지 않다.

Demand Paging

Demand Paging이란?

요구 페이징(Demand Paging)이란 저장 공간으로부터 물리 메모리로 요구된 페이지들만 로드하는 기법이다.

요구 페이징 과정

1. Instruction 실행
2. 가상 주소로부터 가상 페이지 번호 추출
3. 페이지 테이블 참조
4. 페이지 테이블에 물리 페이지 부재시 페이지 폴트 발생
5. 페이지 폴트 발생시 페이지 프레임 할당하고 페이지 테이블 갱신
6. 해당 페이지를 디스크에서 페이지 프레임에 탑재

1. 프로세스 주소 공간에서 인스트럭션을 수행한다.
2. 가상 주소에서 vm_entry를 거쳐 가상 주소를 물리 주소로 변환한다.
3. 페이지 테이블에 물리 페이지가 존재하지 않는 경우 패아자 폴트가 발생한다.
4. 저장 공간으로부터 4kb 크기의 페이지를 읽고 물리 메모리에 적재한다.

가상 주소 공간의 구현

물리 주소와 가상 주소 사이에 코드, 데이터, BSS로 구성된 페이지들을 포함하여 논리 주소를 추가한다.

각 페이지들은 vm_entry로 구성되며 hash table로 관리한다.

가상 주소 공간에서의 페이지

vm_entry

• 각 페이지 당 하나씩 존재한다.
• 각 페이지의 파일 포인터, 오프셋, 크기를 저장한다.
• 프로그램 초기 탑재시 가상 주소 공간의 각 페이지에 vm_entry를 할당한다.
• 프로그램 실행시 페이지 테이블을 탐색한다.
• 페이지 폴트가 발생시 가상주소에 해당하는 vm_entry를 탐색한다.
• vm_entry에 없는 가상 주소는 segmentation fault가 발생한다.
• vm_entry가 존재할 경우 (1) 페이지 프레임을 할당한다. (2) vm_entry에 있는 파일 포인터, 읽기 시작할 오프셋, 읽어야 할 크기 등을 참조해서 페이지를 로드한다. (3) 페이지 테이블을 갱신한다.

vm_entry

vm_entry의 등장 배경

가상 주소는 16진수, Virtual Page Number와 Offset으로 구성된다.

1. 가상 주소에 접근한다.
2. 해당 가상 주소에 페이지가 요청됨
3. 페이지 테이블을 참조한다.
4. 물리 주소가 매핑되어 있지 않다.
5. 페이지 폴트 발생

파일의 포인터, 오프셋, 읽어야 할 데이터의 크기에 대한 정보가 필요한다.

3. 물리 페이지를 할당한다.
4. 물리 메모리에 파일 내용을 적재한다.

물리 페이지 할당 시 파일의 오프셋에 대한 정보를 읽을 필요가 있다.

가상 주소 변환 과정

가상 주소는 20비트 크기의 페이지 테이블 인덱스와 12비트 크기의 페이지 오프셋으로 구성된다.

페이지 오프셋은 해당 프레임(또는 페이지)의 첫 주소를 0으로 봤을 때의 주소를 의미한다.

페이지 테이블(물리 주소)은 프레임 넘버와 플래그를 포함한다.

물리 주소는 프레임 넘버와 페이지 오프셋으로 구성된다.

PintOS의 페이지 테이블 구조

쓰레드 구조체의 멤버인 pagedir는 페이지 디렉토리가 시작하는 위치를 가리킨다.

페이지 디렉토리의 인덱스는 페이지 테이블이 시작하는 위치를 가리킨다.

페이지 디렉토리 인덱스와 페이지 테이블 인덱스와 오프셋으로 구성한다.

vm_entry의 타입

가상 주소 페이지를 3가지 타입으로 분류되고 vm_etry의 type 필드에 가상 주소의 타입을 저장한다.

1. VM_BIN: 바이너리 파일로부터 데이터를 로드한다.
2. VM_FILE: 매핑된 파일로부터 데이터를 로드한다
3. VM_ANON: 스왑 영역으로부터 데이터를 로드한다.

vm_entry 자료구조 정의

struct vm_entry 구조체는 VM_BIN, VM_FILE, VM_ANON을 구분하는 type, 관리하는 가상 페이지 번호 *vaddr, 해당 주소의 write 가능 여부를 나타내는 writable, 물리 메모리의 탑재 여부를 알려주는 플래그인 is_loaded, 가상 주소와 매핑된 파일인 file을 멤버로 갖는다.

또한 mmap 리스트의 엘리먼트인 mmap_elem, 읽어야 할 파일의 오프셋 offset, 가상 페이지에 쓰여져 있는 데이터 크기인 ready_bytes, 0으로 채울 남은 페이지의 바이트인 zero_bytes를 포함한다.

가상 메모리에서 가상 주소 페이지를 접근하여 페이지 테이블을 참조한다.

페이지 테이블에 물리 주소에 대한 정보가 없는 경우 매핑을 필요로 하고 가상 페이지에 대한 정보가 필요하다.

해당 가상 주소의 virtual page를 표현하는 vm_entry를 필요로 한다.

페이지 폴트가 일어날 때마다 가상 주소에 해당하는 vm_entry를 탐색해야 한다.

메모리에 접근할 경우 해당 주소의 가상 페이지를 표현하는 vm_entry를 탐색해야 한다.

vm_entry들은 탐색이 가능하도록 묶어서 관리되어야 한다.

따라서 탐색이 빠른 해시로 vm_entry를 관리하고 vaddr으로 해시 값을 추출한다.

PintOS에서의 해시 테이블

핀토스는 체이닝 해시 테이블을 제공한다.

체이닝 해시 테이블은 해시 값이 충돌할 경우, 충돌한 해시 값의 element들을 리스트로 관리한다.

hash_init() 함수는 해시 테이블을 초기화한다.

hash_destroy() 함수는 해시 테이블을 삭제한다.

hash_insert() 함수는 해시 테이블에 element를 삽입한다.

hast_delete() 함수는 해시 테이블에서 element를 제거한다.

hash_find() 함수는 해시 테이블에서 element를 검색한다.

해시 테이블을 이용해서 구현해야 할 부분

1. thread 구조체에 해시 테이블 자료구조를 추가한다.

2. 프로세스 생성시 해시 테이블을 초기화하고 vm_entry들을 해시 테이블에 추가한다.

3. 프로세스 실행 중 페이지 폴트가 발생할 시, vm_entry를 해시 테이블에서 탐색한다.

4. 프로세스 종료시 해시 테이블의 버킷리스트와 vm_entry들을 제거한다.

thread 구조체에 해시 테이블 자료구조 추가

프로세스마다 가상 주소 공간이 할당되므로, struct thread 구조체에 가상 페이지들을 관리할 수 있는 자료구조인 해시 테이블을 정의한다.

vm_init() 함수는 hash_init() 함수를 사용하여 해시 테이블을 초기화한다.

vm_hash_func() 함수는 vm_entry의 vaddr을 인자로 입력하여 hash_int() 함수를 사용하여 해시 값을 반환한다.

vm_less_func() 함수는 입력된 두 hash_elem의 vaddr을 비교하여 true와 false를 반환한다.

start_process() 함수에 vm_init() 함수를 추가하여 해시 테이블을 초기화하도록 수정한다.

insert_vme() 함수는 hash_insert() 함수를 이용하여 vm_entry를 해시 테이블에 삽입한다.

delete_vme() 함수는 hash_delete() 함수를 이용하여 vm_entry를 해시 테이블에서 제거한다.

*find_vme() 함수는 인자로 입력 받은 vaddr에 해당하는 vm_entry를 검색한 후 반환한다.

vm_destroy() 함수는 hash_destroy() 함수를 사용하여 해시 테이블의 버킷리스트와 vm_entry들을 제거한다.

process_exit() 함수가 프로세스 종료시 vm_entry들을 제거하도록 수정한다.

기존의 PintOS 운영체제는 가상 주소공간을 초기화하지 않는다.

1. 물리 메모리에서 물리 프레임을 통해 물리 페이지를 할당한다.

2. 파일의 내욜을 4kb 크기의 페이지를 읽고 물리 메모리에 적재한다.

3. 페이지 테이블에 가상주소와 물리주소를 매핑한다.

파일의 포인터, 파일의 오프셋, 읽어야 할 크기 등 정보를 vm_entry에 저장하도록 한다.

물리 페이지는 가상주소에 접근할 때 할당하도록 한다.

가상 주소 접근 시, 물리 페이지가 맵핑되어 있지 않다면 해당 가상 주소에 해당하는 vm_entry 탐색 후 vm_entry 정보들을 참조하여 디스크의 데이터를 읽어 물리 프레임에 적재하도록 한다.