Git book | Notion

Introduction
- Page
  
  가상 메모리를 4KB 사이즈로 나눈 영역. 64비트 운영체제 에서는 4 레벨의 맵을 통해 실제 물리 주소로 변환한다. Page Offset 을 제외한 4 레벨의 주소는 9bit이다.
  
  각 프로세스는 고유의 유저 페이지를 갖는다. 유저(가상) 페이지의 주소는 KERN_BASE(0x8004000000) 아래에 위치한다. 반면 커널 페이지는 전역이며 어떤 스레드가 사용하더라도 동일한 위치에 위치한다. 커널은 유저와 가상 페이지를 모두 갈수 있지만 유저는 유저 페이지만 접근 할 수 있다.
- Frame
  
  프레임은 물리적 프레임 또는 페이지 프레임이라한다. 페이지와 마찬가지로 페이지 크기로 구분되어있다. 64비트 물리주소는 프레임 넘버와 오프셋으로 나뉜다. X86-64 에서는 물리 주소로 직접 접근할 방법이 없다. 커널 가상 메모리의 첫 페이지는 RAM의 첫 프레임에 매핑된다. 두번째 커널 가상메모리는 RAM의 두번째 프레임에 매핑된다. 핀토스에는 물리 주소와 커널 가상 주소를 변환하는 함수가 있다.
- Page Table
  
  CPU가 가상 주소를 물리 주소로 변환할때 사용하는 자료구조이다. 즉 페이지를 프레임으로 변환하는 것. 핀토스에는 mmu.c에 페이지 테이블 관리 코드들이 있다. 페이지 테이블을 통해 프레임 값은 변하지만 offset은 변하지 않는다.
- Swap Slot
  
  swap slot은 디스크 영역에 있는 페이지 단위 슬롯이다. 프레임 위치를 찾는것 보다 슬롯 위치를 찾는 것이 더 효율적이지만?, 페이지 단위로 있는다 해서 나쁠건 없다.
- supplemental page table, frame table, swap table 각각 만들지 말고 하나의 자료 구조로 만들어라. 말록이나 캘록을 활용하면 더 간단해진다. 각 테이블에 기입해야할 내용은 알아서 정해라.
- Supplemental Page Table
  
  페이지 테이블에 있는 내용만으로는 한계가 있어서 몇가지 데이터를 더 넣은 것을 supplemental page table이라 하기로 한다. 커널은 페이지 폴트 난 페이지에 어떤 값이 있어야 하는지 확인하기 위해 보충 페이지 테이블에서 해당 페이지를 찾아본다. 또한, 프로세스가 종료 되었을때 할당 해제할 자원을 결정하기 위해 보충 페이지 테이블을 사용한다.
- Handling Page Fault
  
  프로젝트 2와 다르게 페이지 폴트가 일어나면 파일이나 스왑 슬롯에서 페이지를 가져와야 한다.
  1. 페이지 테이블에서 폴트난 페이지의 위치를 조정한다. 메모리가 유효하다면 해당 페이지 테이블 엔트리가 스왑 슬롯이나 파일을 가르키게 한다.
    
    만약 공유 중이라면, 페이지의 데이터는 페이지 프레임에 있을 것이다. 만약 페이지 테이블이 유저 프로세스가 접근 하려는 주소에 데이터가 없다고 알려주거나, 페이지가 커널 가상 메모리 구역에 있거나, 읽기전용 페이지에서 쓰기를 하려고 한다면 그 접근은 불효하다. 이러한 접근이 일어나면 프로세스를 종료하고 할당 받았던 자원들을 할당 해제해야한다.
  2. 페이지를 저장할 프레임을 받는다. 공유 중일때는 해당 프레임에 위치시켜준다?
  3. 파일, 스왑디바이스의 데이터를 프레임으로 가져오거나 해당 프레임 데이터를 0으로 만들어준다. 공유 중이라면 따로 해줄건 없다.
  4. 페이지 폴트 났던 페이지 테이블 엔트리를 물리 주소를 가르키게한다. mmu.c 함수사용
- Managing Frame Table
  
  프레임 테이블에는 각 프레임마다 하나의 엔트리가 있다. 각 엔트리에는 각 페이지를 가르키는 포인터가 있다. 유저 페이지들이 사용하는 프레임들은 palloc_get_page(PAL_USER)을 사용해야한다. 프레임 테이블 작동에서 가장 중요한 것은 미사용 프레임을 포함시키는 것이다. 할당 할 프레임이 있으면 쉽지만 없다면 희생할 프레임을 찾아야한다.
  
  만약 스왑 슬롯이 꽉차서 희생할 프레임이 없으면 커널 패닉이 발생한다. 실제 OS들은 이러한 상황을 예방하기 위한 정책들이 있지만 핀토스의 영역을 벗어난다.
  1. accessed, dirty 비트를 사용하여 희생할 프레임을 고른다.
  2. 해당 프레임을 참조한 ? 페이지 테이블의 내용을 삭제해 준다. 공유 중이더라도, 오직 한개의 페이지만이 해당 프레임을 참조하고 있다.
  3. 필요하다면, 페이지를 파일이나 스왑디바이스에 작성한다. 희생된 프레임은 다른 페이지를 저장하는데 사용된다.
- Accessed and Dirty Bits
  
  X86-64에서는 페이지 대체 알고리즘을 보조하는 비트가 있다. 페이지를 읽거나 페이지에 작성 할때, CPU는 accessed 비트를 1로 변경한다. 어느 작성에도 cpu 는 dirty bit를 1로 설정한다. CPU는 이 비트를 다시 0으로 바꾸지 않는다.(OS는 바꿀 수 있음)
  
  2개 이상의 페이지가 같은 프레임을 가르키는 aliases를 알아야한다. aliased frame에 접근한 페이지의 dirty bit는 1이 되지만 나머지 페이지의 dirty bit와 accessed bit는 갱신되지 않는다.
  
  핀토스에서는 모든 유저 페이지가 커널 가상 페이지에 aliased 되어있다. 우리는 이러한 aliases를 관리해 주어야 한다.예를 들어, 코드가 모든 주소의 accessed bit와 dirty bit를 변경 할 수 도 있다. 대신에 커널은 유저 가상 주소만을 통해 유저 데이터에 접근 함으로서 해당 문제를 피할 수 있다.
- Managing Swap Table
  
  malloc lab 처럼 가용 swap slot과 비가용 swap slot을 관리한다. 페이지가 램으로 다시 올라가면 해당 swap slot을 가용 상태로 바꿔준다.
- Managing Memory Mapped Files
  
  파일 시스템에서는 read와 write 시스템 콜이 많이 발생한다. 2차 인터페이스는 mmap 시스템 콜을 사용하여 파일을 가상 페이지로 매핑하는 것이다. 그러면 프로그램은 파일 데이터에 메모리 인트스럭션을 직접 사용 할 수 있다.
  
  foo 파일이 0x1000(4KB)라 가정해 보자. 만약 foo의 시작주소가 0x5000이면 0x5000 부터 0x5fff까지는 모두 foo의 메모리 들이다.
  
  아래는 mmap을 이용하여 파일을 콘솔에 출력하는 코드이다. 이것은 커맨드 라인에 입력한 파일을 열어서 0x10000000의 가상주소에 매핑하며 매핑한 데이터를 fd1(표준 출력)에 작성한다. 콘솔 출력이 끝나면 unmap 해준다.
```
#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;
}
```
우리는 어떤 메모리가 매핑된 파일을 사용하는지 확인해야한다. 이러한 작업은 매핑된 지역에서 페이지 폴트를 조절하는데 필요하다. 또한, 매핑된 파일들이 프로세스 내에서 다른 영역을 침범하지 않는다는 것을 보장하기 위해서도 필요하다.
Memory Management
- struct page
```
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
  };
};
```
  page 구조체에는 page operations, 가상주소, 물리 주소 프레임이 있다. 추가로 union field가 있다. union은 메모리 영역에 다른 종류의 데이터를 저장할 수 있게 하는 특별한 형식이다. union에는 여러 멤버들이 있지만, 한 시점에는 1개의 멤버만 포함한다. 즉, page는 uninit_page or anon_page or file_page or page_cache 중 하나이다. 예를 들어, 만약 페이지가 anonymous page이면 page 구조체는 anon 구조체를 가지며 anon_page는 해당 정보를 가지고 있다.
- Page Operation
  
  page는 VM_UNINIT, VM_ANON, VM_FILE 중 하나이다. 페이지는 스왑 인, 스왑아웃, 삭제 같은 여러 행동을 취한다. 각 타입의 페이지에 대하여, 페이지가 동작하는 방법이 다르다. 즉, VM_ANON의 삭제와 VM_FILE의 삭제의 동작이 다르다. 이런 방식을 구현하는 방법중 하나는 switch 를 활용하는 것이다. 우리는 class 상속 이라는 개념을 사용할 것이다. 그런데 c언어에는 클래스나 상속이 없다. 그래서 실제 리눅스 시스템에서 활용하는 함수 포인터를 사용하려 한다.
  
  함수 포인터는 우리가 알고 사용하던 포인터와 크게 다르지 않다. 단지 함수나 메모리에 있는 실행할 코드를 가르킨다. 함수포인터는 실시간으로 발생하는 상황에 대해 다른 확인 없이 원하는 함수를 실행 시킬 수 있다. 예를 들면, 우리는 destroy(page) 함수를 호출 하기만 하면 컴파일러가 페이지 타입에 따라서 알맞은 함수를 호출 할 것이다.
  
  page_operation 구조체에는 3가지 함수 포인터가 있다.
```
struct page_operations {
  bool (*swap_in) (struct page *, void *);
  bool (*swap_out) (struct page *);
  void (*destroy) (struct page *);
  enum vm_type type;
};
```
  vm.h 파일에 있는 page 구조체 내부에 operation이라는 필드가 있다. vm/file.c를 살펴보면 page_operation 구조체인 file_ops를 볼 수 있다.이것이 file-backed page들을 위한 함수 포인터들의 테이블 이다. .destroy 필드는 페이지를 삭제하는 함수인 file_backed_destroy 값을 갖는다. 그리고 이것은 같은 파일에 정의되어 있다.
```
/* vm/file.c */
static bool file_backed_swap_in (struct page *page, void *kva);
static bool file_backed_swap_out (struct page *page);
static void file_backed_destroy (struct page *page);

/* DO NOT MODIFY this struct */
static const struct page_operations file_ops = {
	.swap_in = file_backed_swap_in,
	.swap_out = file_backed_swap_out,
	.destroy = file_backed_destroy,
	.type = VM_FILE,
};
```
  file_backed_destroy 가 함수 포인터를 통해서 어떻게 호출 되는지 살펴보자. 현재 페이지가 VM_FILE 인 상태에서 vm/vm.c에 있는 vm_dealloc_page (page) 가 호출 된다고 생각해 보자. 함수 내부에서는 destroy (page) 를 호출하며 이것은 include/vm/vm.h 에 아래와 같이 정의된 매크로 이다.
```
#define destroy(page) if ((page)->operations->destroy) (page)->operations->destroy (page)
```
  destroy (page) 를 호출하면 페이지 구조체에서 시작되는 destroy 함수를 호출한다. 페이지가 VM_FILE 페이지이기 때문에 .destroy 필드는 file_backed_destroy 를 가르킨다. 결과적으로 file-backed를 위한 destroy 루틴이 실행된다.
- Implement Supplemental Page Table
  
  핀토스에서는 가상메모리와 물리메모리를 매핑하기 위해 pml4를 사용한다. 그러나 정보가 충분하지 않아서 Supplemental Page Table을 사용한다.
  
  우선 핀토스에서 Supplemental Page Table를 어떻게 디자인할지 생각해 봐야한다. Supplemental Page Table이 결정되면 아래 3함수를 직접 구현해 보아라.
```
void supplemental_page_table_init (struct supplemental_page_table *spt);
```
  SPT를 초기화 한다. SPT를 구성할 자료구조를 선택해야한다. 새로운 프로세스가 초기화 되거나 (in initd of userprog/process.c) and 프로세스가 fork될 때 호출 된다. (in __do_fork of userprog/process.c).
```
struct page *spt_find_page (struct supplemental_page_table *spt, void *va);
```
  SPT를 통해 주어진 가상 메모리에 해당하는 페이지 구조체를 찾는다. 탐색이 실패하면 NULL을 반환한다.
```
bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);
```
  주어진 SPT에 페이지 구조체를 삽입힌다. 이 함수는 기존 SPT에 요청받은 페이지 구조체가 없다는 것을 확인 해야한다.
- Frame Management
  
  모든 페이지들이 만들어 질때 메타데이터를 가지고 있다. 그러므로 우리는 물리 메모리를 관리하기 위해 다른 관점이 필요하다. include/vm/vm.h 에는 물리 메모리를 표현하는 프레임 구조체가 있다.
```
/* The representation of "frame" */
struct frame {
  void *kva;
  struct page *page;
};
```
  프레임 구조체에는 커널 가상 주소인 kva 와 페이지 구조체인 page 가 있다. 필요하면 요소를 추가해도 된다.
```
static struct frame *vm_get_frame (void);
```
  palloc_get_page 를 이용하여 유저 영역에 있는 새로운 물리 페이지를 얻는다. 페이지를 얻는데 성공하면 프레임을 할당하며 구조체 요소를 초기화 하여 반환한다. vm_get_fram 을 실행한 후에, 모든 유저영역의 페이지(PALLOC_USER)를 할당해야 한다. 페이지 할당 실패시 스와핑은 필요없다. 현재는 PANIC ("todo") 만 호출하면 된다 .
```
bool vm_do_claim_page (struct page *page);
```
  물리프레임(페이지)를 할당하라. 우선 vm_get_frame 을 통해 프레임을 얻는다. 그리고 MMU에 가상주소와 물리주소 변환을 입력한다. 함수실행 성공여부를 반환한다.
```
bool vm_claim_page (void *va);
```
  가상 주소를 할당하기 위한 페이지를 요청한다. 우선 페이지를 얻은 다음에 해당 페이지에 대하여 vm_do_claim_page 를 호출 한다.
Anonymous Page
- Page Initialization with Lazy Loading
  
  페이지가 할당되지만(페이지 구조체가 있지만), 대응되는 물리 프레임은 없다. 그리고 실제 페이지의 내용은 아직 로드되지 않았다. 내용들은 실제로 페이지가 필요할때, 즉 페이지 폴트 시그널이 발생할 때 로드된다.
  
  우리는 3가지 타입의 페이지 별로 각자의 초기화 방법이 다르다. 아래 섹션에서 다시 언급하겠지만 여기서 우리는 페이지 초기화 과정을 상위 레벨의 관점에서 설명한다.
  
  커널이 새로운 패이지를 요청 받으면 vm_alloc_page_with_initializer 를 호출한다. initializer는 페이지 구조체를 할당함으로서 새로운 페이지를 초기화 한다. 그리고 페이지 타입에 따른 initializer를 설정하고 제어권을 유저 프로그램으로 넘긴다. 유저 프로그램이 실행되는 시점에서 페이지 폴트가 발생한다. 프로그램이 내용이 비어있는 페이지에 접근하려 하기 때문이다. 페이지 폴트 핸들러의 동작 도중 uninit_initialize 함수가 실행 되며 이 함수는 전에 설정한 initializer가 호출 된다.
  
  페이지는 initialize->(page_fault->lazy-load->swap-in>swap-out->...)->destroy 의 사이클을 갖는다. 위의 초기화 예시처럼 페이지 타입마다 요구되는 처리 방법이 다르다. 이번 프로젝트에서 각 페이지 타입 별 전환 프로세스들을 구현한다.
- Lazy Loading for Executable
- Supplemental Page Table
- Page Cleanup
Stack Growth
Memory Mapped Files
Swap In/Out