Intro.
내 집 마련이란, 유저 프로세스에게도 나에게도 환상과 같은 것이다.
지난번 프로젝트에 이어서 Virtual Memory는 운영체제가 유저프로세스를 다루는지, 뿐만아니라 전반적인 Memory Management 에 대해서 배워볼 수 있었다.
Project 2 가 User 와 Kernel 간의 protection 을 위한 과정이었다면 이번 Project 3 는 서로 다른 User 들 간의 isolation 을 위한 과정이다.
기본적으로 운영체제는 (project 2와 동일한 기조로) 사용자 프로그램을 '부주의'하고, '악의적'일 수도 있다고 항상 생각한다. 그에따라서 user mode 와 kernel mode를 분리했다면, 이젠 각 사용자들의 프로그램이 돌아가는 메모리 공간을 분리한다.
이와같은 분리를 통해 각 사용자는 자신 이외에 다른 사용자가 있다는 사실을 알 수 없게 되고 이를 'Transparent'하다고 한다. 그리고 이러한 분리를 가능하게하는 기술적인 방법으로서 'Virtual Memory' 개념이 존재한다.
각 사용자에게 주소 공간, 메모리를 분배하는 방법은 여러가지가 있을 수 있다. 하지만 지구상에서 일어나는 대부분의 일과 같이 자원은 한정적이다. 물리 메모리 (DRAM)의 용량은 분명한 한계가 존재하고 이를 각 프로그램마다 일정부분을 할당한다는 것은 컴퓨터의 능력을 매우 매우 제한하는 방법이라 할 수 있다.
그러니 물리 메모리에 한정되지 말고 '가상 주소 공간'을 만들어서 (64비트 운영체제의 경우에는 무제한에 가까운) 사용자 프로그램으로 하여금 '너 혼자 전체 메모리 공간 다쓸수 있어!'라는 환상을 주고, 이를통해 컴퓨터의 능력을 끌어올리는 방법이 더 나을 것이다.
Memory Management.
핀토스에서는 페이징 기법을 사용한 'Multi Level Paging' 을 채택하고 있다. 코드에선 pml4 관련 함수들이 이 페이지 테이블을 다루고 있다.
Project 3 에서 가상 메모리는 struct page 를 통해 나타내고, 물리 메모리는 struct frame을 통해 나타낸다.
struct page {
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
/* Your implementation */
// for vm_entry
uint8_t type; // VM_BIN, VM_FILE, VM_ANON
bool writable; // True일 경우 해당 주소에 write 가능. False일 경우 해당 주소에 write 불가능
bool is_loaded; // 물리 메모리의 탑재 여부를 알려주는 플래그
// Swapping 과제에서 다룰 예정
// size_t swap_slot; //스왑슬롯
// Memory Mapped Fiile에서 다룰 예정
// struct list_elem mmap_elem; // mmap 리스트 element
struct hash_elem hash_elem; // 해시 테이블 element
int reference_cnt;
/* 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; // 페이지 구조체
struct list_elem frame_elem; // frame table 만들기 위해
};간략한 요약을 하자면 page 구조체에 있는 va 와 frame 구조체에 있는 kva 를 맵핑 시켜주는 과정을 pml4 함수를 사용해서 한다고 생각하면 된다. 이렇게 만들어진 page table 은 va 로 접근시 kva 를 돌려줌으로써 물리 메모리에 접근 할 수 있게 만들어 준다.
이때 중요한 부분이 page table에 꼭 전부다 올려할까? 이다.
Supplemental Page Table
기존 project 2 까지는 유저 프로그램을 실행시키는 과정에서 load 함수를 통해서 실행에 필요한 모든 파일에 관한 데이터, 유저 스택에 관한 부분까지 다 물리 메모리에 적재하고 이를 pml4 를 사용해서 맵핑해주었다.
메모리 공간이 충분하다면 이는 전혀 문제가 되지 않겠지만, 한정적 메모리 공간을 최대한 활용해야하는 입장으로서 이 방법은 좋지 않다. 한 치 앞도 모르는 인간으로서 지금 물리메모리를 차지하고 있는 저 공간을 사용자가 쓸지, 안 쓸지도 모르는데 왜 굳이 다 올려야할까? 라는 생각이 든다.
이에 대한 해결방법으로 Lazy loading (Demanding page) 기법을 주로 사용하게 된다. 이를 직접 구현하는 lazy_load_segment 함수는 조금 있다가 보도록 하고, 지금은 위 기법의 기초가 되는 'Supplemental Page Table'에 대해 알아보자.
이보다 적절한 lazy 설명이 있을까? 마지막 부분에 right now 만 추가하면 더욱 완벽할듯 하다. "I can... but I won't do right now!"
Supplemental Page Table 이란 page table을 보충해주는 페이지 테이블이라고 생각하면 된다. 기본적으로 lazy loading 은 실행에 필요한 모든 파일정보를 한번에 page table에 다 올리지 않는다.
그래도 어떤 것들이 실행하는데 필요한지, 어떤 접근 권한을 가지고 있는지 등등은 어딘가에 저장해놓아야 한다. 최초 유저 프로그램의 실행시 말이다. 이때 SPT를 생성한다.
이후에 만들어놓은 page table이외에 정보가 필요한 메모리 접근이 유저로부터 일어나면 커널은 page fault handling을 진행한다. 이때 실제로 '유효한 page fault' 는 에러 메시지를 띄우는 원래 알고 있던 그 page fault 다. 하지만 page table에만 안 올려놓았을뿐, SPT에는 존재하는 page 에 대한 접근같은 경우에는 Bogus fault 로서 다뤄주어야한다. 이러한 fault detection을 exception.c 에 있는 page_fault 함수에서 진행한다.
static void
page_fault (struct intr_frame *f) {
bool not_present; /* True: not-present page, false: writing r/o page. */
bool write; /* True: access was write, false: access was read. */
bool user; /* True: access by user, false: access by kernel. */
void *fault_addr; /* Fault address. */
/* Obtain faulting address, the virtual address that was
accessed to cause the fault. It may point to code or to
data. It is not necessarily the address of the instruction
that caused the fault (that's f->rip). */
fault_addr = (void *) rcr2();
/* Turn interrupts back on (they were only off so that we could
be assured of reading CR2 before it changed). */
intr_enable ();
/* Determine cause. */
not_present = (f->error_code & PF_P) == 0;
write = (f->error_code & PF_W) != 0;
user = (f->error_code & PF_U) != 0;
#ifdef VM
/* For project 3 and later. */
if (vm_try_handle_fault (f, fault_addr, user, write, not_present))
return;
#endif
exit (-1);
/* Count page faults. */
page_fault_cnt++;
/* If the fault is true fault, show info and exit. */
printf ("Page fault at %p: %s error %s page in %s context.\n",
fault_addr,
not_present ? "not present" : "rights violation",
write ? "writing" : "reading",
user ? "user" : "kernel");
kill (f);
}즉, SPT 에서 처리할 수 있는 lazy loading 으로 인한 page fault 라면 vm_try_handle_fault가 정상적으로 종료될 것이고 이는 page_fault 함수도 곧바로 return 시킨다.
하지만 처리할 수 없는 page fault 였다면 vm_try_handle_fault함수가 정상종료되지않아, exit(-1)으로 유저 프로세스를 강제 종료 시켜버린다.
다시 SPT 로 돌아와서, SPT 구현에 사용할 수 있는 자료구조는 해시 테이블, 비트맵 인덱싱, 배열, 연결 리스트 등이 있다. 시간 복잡도를 고려했을때 hash function이 있다면 O(1)으로 element 에 접근 가능한 해시 테이블을 사용하였다.
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
hash_init(&spt->pages, page_hash, page_less, NULL);
}해시 테이블을 초기화한다. 이렇게 만들어진 해시테이블에서 va 를 입력으로 찾고자하는 page 를 리턴해주거나 다양한 명령을 수행할 수 있는 interface 를 구현하였다.
struct page *spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
// struct page *page = NULL;
/* TODO: Fill this function. */
struct page* page = (struct page*)malloc(sizeof(struct page));
struct hash_elem *e;
page->va = pg_round_down(va); // va가 가리키는 가상 페이지의 시작 포인트(오프셋이 0으로 설정된 va) 반환
e = hash_find(&spt->pages, &page->hash_elem); // hash_elem 구조체 얻음
free(page);
return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL; // 존재하지 않는다면 NULL 리턴
}
/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
struct page *page UNUSED) {
// int succ = false;
/* TODO: Fill this function. */
return insert_page(&spt->pages, page);
}
void
spt_remove_page (struct supplemental_page_table *spt, struct page *page) {
vm_dealloc_page (page);
return true;
}이렇게 만들어진 SPT를 사용한 가상 페이지와 물리 프레임의 맵핑, lazy loading 을 비롯한 anonymous page, file backed page 등은 다음 포스트에서 이어서 설명하도록 하겠다.
