Introduction

프로젝트2까지 구현된 것
: 여러개의 thread에 대해서 동기화가 정상적으로 되며, 여러개의 프로그램을 동시에 load할 수 있다.

프로젝트3의 목표
: 기계의 main memory의 크기에 따른 제약이 있는 현재 상태에서 무한한 메모리를 가지고 있다는 환영을 만들어 메모리 크기에 대한 제약을 제거하는 것

Backgroud

Source Files

• vm.*
  • 가상 메모리 시스템이 지원해야하는 vm_type 에 대한 정의
  • supplementary page table 구현
• uninit.*
  • uninitialized pages 초기화 되지 않은 페이지들에 대한 연산 제공
  • 현재 디자인으로는 모든 페이지가 uninitialized pages로 초기 설정이 되어있으며, 그 후 anonymous 또는 file-backed 페이지로 변경된다.
• anon.*
  • anonymous 페이지에 대한 연산 제공
• file.*
  • file-backed 페이지에 대한 연산 제공
• inspect.*
  • 성적 산출을 위한 메모리 검사 코드
• block.* => modify
  • block device에 대한 sector 기반 read/write 접근 제공
  • swap partition을 block device로서 접근할 수 있도록 해주는 interface

Memory Terminology

Pages (Virtual Page)

• 가상 메모리에서 4,096byte(= 4Kibibyte(KiB) = page size) 만큼 연속된 공간
• page-aligned : page size로 나누어 떨어지는 가상 주소에서 시작해야한다는 것

Frames (Physical Frame, Page Frame)

• 물리 메모리에서의 연속적인 영역
• 프레임 역시 page size 이며 page-aligned 이다.
• 64비트 물리주소는 12비트의 offset과 frame number로 나뉘어진다.
• 커널 가상 메모리의 첫번째 페이지가 물리 메모리의 첫번째 프레임에 매핑되어있으며 두번째는 두번째끼리 매핑되어있다. (address translation을 간편하게 할 수 있다.)
• 따라서 frame은 커널 가상 주소를 통해 접근할 수 있다.

Page Tables

• CPU가 가상 주소에서 물리주소로 변환하는데 사용하는 자료구조
• threads/mmu.c에 페이지 테이블 관리 코드가 제공되어있다.

Swap Slots

• 디스크 공간의 swap partition에 존재하는 페이지 크기의 영역
• 프레임을 위치시키는 것보다는 제약이 유연한 편이지만 swap slot도 가능한 page-align을 하는 것이 좋다. (안할 이유가 없다.)

Resource Management Overview

You will need to design/implement the following data structures:

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.

Swap table

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

Possible Design Choices

• 위 3가지 자료구조를 구현할 때 꼭 각각의 자료구조를 만들 필요는 없다.
  • 전체나 일부를 합쳐서 하나의 자료구조로 만들 수 있다.
• 각각의 자료구조에 대해서 어떤 요소가 들어갈지 결정해야한다.
• 자료구조의 범위도 결정해야한다
  • local (per-process) vs. global(whole system) => spt는 당연히 로컬, 프레임은 글로벌?
  • 그리고 그 범위 내에서 몇개의 인스턴스가 필요한지 결정
• 디자인을 간소화하기 위해서 non-pageable memory (calloc, malloc, 등)을 사용할 수 있다
  • WHAT IS NON PAGEABLE MEMORY?
    메모리 공간을 페이지 테이블에 저장되는 페이지로 할당받는 것이 아니라, malloc 이나 calloc을 통해서 할당받는 것 -> 페이지 테이블 자체는 swap out되면 안되기 때문에 메모리에 테이블 엔트리를 못박아두는 것이라고 볼 수 있을 것 같다.
• array, list, bitmap, hash table 등 중에서 고를 수 있음
  • list는 중간에 삽입하고 삭제가 용이
  • butmap은 주로 identical 한 세트를 가진 자원(?)에 적용하기에 적합
  • 해시테이블은 크기가 큰 테이블에서도 삽입과 삭제가 용이하다
• Segment vs. Page 단위 메모리 관리
  • Extra) 페이지테이블 자체를 사용해 supplemental page table의 요소를 기록할 수 있다.

Our Team's Design Choices

• Hash Table
  • 제일 빠르고, 유연하다.
  • 참고할만한 코드가 해시테이블이 가장 많다.
• Segment 단위 보다는 페이지 단위로 메모리를 관리하는 것이 좋을 것 같다.
  • segment는 연속된 페이지의 그룹을 의미한다.
  • 페이지 단위가 더 정교하게 컨트롤할 수 있다.
  • 주소가 서로 떨어져있을 때 더 용이하다.
  • 검색 시간 길고, 스트럭쳐가 커진다는 단점이 있긴 하다.
• Extra 과제인 자원공유는 안하기로 결정

Managing the Supplemental Page Table

Supplemental page table은 다음 두가지 용도로 사용될 수 있으며, 그 외에도 디자인에 따라 용도를 추가할 수 있다.

1. Page fault가 발생하면 커널은 supplemental page table에서 fault가 발생한 페이지를 찾고, 그 안에 어떤 데이터가 있어야 하는지 알아본다.
2. 프로세스가 종료될 때 supplemental page table을 확인해서 어떤 자원을 free 해야하는지 결정한다.

👉🏻 Supplemental page table은 메모리 자원을 효과적으로/효율적으로 load, swap, free 등을 할 수 있도록 도와주는 역할을 한다.

Supplemental page table을 주로 사용하는 것은 page fault handler이다. 프로젝트2에서는 항상 버그로 표기했지만, 프로젝트3에서는 더이상 버그가 아니다. 이제 page fault는 페이지가 파일이나 swap 슬롯에서 가져와져야 한다는 뜻이다.

Page Fault Handler
: exception.c의 page_fault() -> vm.c의 vm_try_handle_fault()를 호출

1. Spt에서 fault가 발생한 페이지 찾기
   • Memory reference가 유효하다면, spt entry를 사용해 페이지에 들어갈 데이터를 찾을 수 있다.
   • 파일시스템에 있을수도 있고, swap 영역에 있을 수도 있고, 그냥 모두 0인 페이지일 수 있다.
   • Sharing을 구현한다면 페이지의 데이터가 이미 frame에 들어있는데 페이지테이블에는 없는 상태일 수도 있다.
   • Memory reference가 유효하지 않다면, 프로세스를 종료하고 자원을 free 해준다.
     • Spt가 해당 주소에 대해 데이터를 가지고 있지 않은 경우
     • 커널 메모리 공간에 있는 페이지를 가리키는 경우 👉🏻 user space를 벗어나는 경우 (아직까지 spt를 유저 프로세스에 종속되게 구현했으며, user pool에서 할당받은 user page만 spt에 삽입하기 때문에, spt에 해당 주소에 대한 entry가 없다면 예외상황들이 모두 걸리지고 있다고 볼 수 있지 않을까 싶다!)
     • 읽기 전용 페이지에 write 하려는 경우
2. 페이지를 담을 frame을 얻기
   • 요청된 페이지의 contents를 담을 frame(physical page)을 할당받는다.
   • Sharing을 구현한다면, 데이터가 들어있는 프레임이 이미 존재할 수 있다. 이때 이 프레임의 위치를 찾을 수 있어야 한다.
3. Frame에 데이터를 담기
   • 파일시스템이나 swap 영역에서 데이터를 읽어오거나 프레임을 0으로 초기화해준다.
   • Sharing을 구현한다면, 데이터가 들어있는 프레임이 이미 존재할 수 있으며, 이 경우 해당 단계에서 아무런 일도 발생하지 않아도 된다.
4. Fault가 발생한 가상주소에 대해서 page table entry가 물리 프레임을 가리킬 수 있도록 업데이트
   • mmu.c의 함수를 사용할 수 있다.

Managing the Frame Table

frame table은 각각의 frame의 entry를 관리한다.
frame table의 entry는 각 페이지에 대한 포인터를 가지고 있다. 그리고 그 외 내가 넣고싶은 정보들을 넣어줄 수 있다.
여유 프레임이 없는 경우 퇴출시킬 페이지를 결정하는데 frame table을 사용한다.

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.

프레임 테이블에 있어서 비어있는 프레임을 취득하는 것이 가장 중요한 작업인데,
비어있을 때는 쉽지만 비어있는게 없다면 페이지를 프레임에서 퇴출시켜야 한다.
swap 영역이 다 찼는데 swap을 해서 프레임에 자리를 만들어야 하는 상황이라면 pamic kernel을 일으키면 된다. 실제 OS들은 이러한 상황을 방지하거나 복구하기 위한 다양한 정책들이 있지만 우리의 프로젝트 범위는 벗어난다.

Eviction Process

1. 나만의 replacement 알고리즘을 사용해서 퇴출시킬 프레임을 결정한다.
   • 페이지 테이블의 access 와 dirty 비트를 유용하게 사용할 수 있다.
2. 페이지테이블에서 해당 프레임에 대한 reference를 모두 제거해야한다.
   • sharing을 구현하지 않았다면 하나의 페이지만 frame을 refer 하고 있어야 한다.
3. 필요한 경우 해당 페이지(프레임)의 내용을 파일 시스템 또는 스왑 영역에 쓰기. 이 후에 퇴출된 프레임에 다른 페이지를 담기 위해 사용될 수 있다.

Accessed and Dirty Bits

하드웨어의 지원이 있음 -> 각각의 PTE에 저장되는 비트

• 모든 읽기/쓰기 -> accessed bit 이 1로 설정됨
• 모든 쓰기 -> dirty bit 이 1로 설정됨
  CPU는 0으로 절대 다시 초기화해주지 않으며, OS가 그 작업을 할 수 있다.

aliases : two (or more) pages that refer to the same frame
aliased 프레임에 접근한다면(읽기/쓰기) access를 하는데 사용된 PTE에서만 accessed, dirty 비트가 변경되게 됨. 다른 alias에서는 업데이트가 이루어지지 않음

• PintOS에서는 모든 사용자의 가상 페이지는 커널 가상 페이지에 alias 되어있으므로, 이 alias를 조정하는 작업을 추가해야한다.
  1. 유저와 커널 모두에서 accessed and dirty 비트를 체크하고 업데이트 해주는 방법 👉🏻 하나를 사용하면 다른 하나도 같이 업데이트 해주는 방법
  2. 커널은 유저의 가상 주소를 통해서만 데이터에 접근하는 방법 👉🏻 그러면 커널 비트는 아예 관리하지 않는건가?
• 그 외 sharing 관련된 alias

Managing the Swap Table

사용중인/사용중이지 않은 swap slot을 관리하는 역할
프레임을 퇴출시킬 때 swap slot을 선정할 수 있도록 해준다.
페이지가 다시 읽어들이는 경우나 swap 영역에 페이지를 저장했던 프로세스가 종료되는 경우 이 swap 영역들 역시 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.

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.

Managing Memory Mapped Files

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.

Your submission must be able to track what memory is used by memory mapped files. This is necessary to properly handle page faults in the mapped regions and to ensure that mapped files do not overlap any other segments within the process.

• 어떤 경우에 mmap을 사용하게 될지?

1. Memory Management

Page Structure and Operations

struct page {
  const struct page_operations *operations;
  void *va;              /* Address in terms of user space */
  struct frame *frame;   /* Back reference for frame */

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

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

A union is a special data type that allows us to store different types of data in a memory region. There are multiple members in the union, but only one member can contain a value at a time. This means that a page in our system can be a uninit_page, anon_page, file_page, or page_cache. For example, if a page is an anonymous page (See Anonymous Page), then the page struct will have the field struct anon_page anon as one of its members. anon_page will contain all the necessary information we need to keep for an anonymous page.

A function pointer is a pointer, just like any other pointers you've learned sofar, that points to a function, or an executable code within the memory. Function pointers are useful because they provide a simple way to call a specific function to execute based on run-time values without any checking. In our case, simply calling destroy (page) is sufficient at code-level, and the compiler will choose the appropriate destroy routine depending on the page type by calling the right function pointer.

Page Types

Uninitialized Page

An uninitialized page, also known as a zero-filled page or a demand-zero page, is a type of memory page that is allocated but not explicitly initialized with any data. When an uninitialized page is allocated, it is not associated with any specific file or content.

Uninitialized pages are typically used in virtual memory systems as a form of optimization. Instead of wasting time and resources to explicitly initialize every newly allocated page with zeros or random values, the operating system can allocate uninitialized pages and rely on the virtual memory hardware to automatically provide zero-filled pages on demand.

When a program accesses an uninitialized page for the first time, the virtual memory hardware intercepts the access and triggers a page fault. The operating system then maps a zero-filled page into the virtual memory space of the program, satisfying the page fault. From the program's perspective, it appears as if the uninitialized page was initially filled with zeros.

Anonymous Page

An anonymous page, also known as a private page, is a type of memory page that is not associated with any specific file on disk. It is typically used for storing data that is generated or modified during the execution of a program. Anonymous pages are commonly used for program stacks, heap memory, and dynamically allocated memory.

Anonymous pages are called "anonymous" because they do not have a direct relationship with a file. Their contents are not persisted on disk, and they exist only in memory. When the program terminates, the contents of anonymous pages are typically deallocated and lost.

File-Backed Page

A file-backed page, also known as a mapped page, is a type of memory page that is associated with a specific file on disk. It represents a portion of the file that has been loaded into memory for efficient access by the program. File-backed pages are commonly used for memory-mapped files, shared libraries, and other file-based resources.

When a file-backed page is accessed, the operating system loads the corresponding portion of the file into memory, allowing the program to read from or write to that memory location as if it were a regular memory access. Changes made to file-backed pages are typically written back to the disk, ensuring persistence across program executions.

File-backed pages provide benefits such as memory sharing between multiple processes, efficient file I/O operations, and the ability to treat file data as if it were part of the program's memory space.

Implement Supplemental Page Table

void supplemental_page_table_init (struct supplemental_page_table *spt);

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

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

👉🏻 When is supplemental page table initiated?

supplemental_page_table_init is called at initd and __do_fork
Which means spt is initiated when a user process is created.

What about kernel thread?
Page tables and supplemental page tables are dedicated to each thread(process).
Kernel accesses these tables of each process and doesn't need to have a copy of the tables or anything.
What about the virtual memory space of the operating system itself?
I am guessing that it just uses the kernel virtual address from the kernel pool which directly maps to the physical address.

Frame Management

/* The representation of "frame" */
struct frame {
  void *kva;
  struct page *page;
};

static struct frame *vm_get_frame (void);

bool vm_do_claim_page (struct page *page);

bool vm_claim_page (void *va);