[WEEK12] Lazy Loading (Pintos PROJECT3 : VIRTUAL MEMORY)

Lazy loading이라는 개념이 있다.

우리말로 옮기면 지연 로딩 정도로 말할 수 있는데,

이 Lazy loading은 어떤 개념이며 왜 사용하는 것일까?

 

Lazy loading은 운영체제가 메모리를 할당하는 기법이라고 할 수 있다.

찾아보니 web이나 java (JPA) 쪽에서도 사용하는 용어라고 한다. 하지만 이 글에서는 운영체제 측면에 한해 다루겠다.

 

앞선 글에서, 가상메모리와 관련된 페이징 개념을 다뤘다.

페이징을 활용해서 연속적이지 않은 공간에 파일을 로드함으로써 공간을 효율적으로 사용할 수 있었다.

여기에 더해 Lazy loading을 활용하면 추가적인 공간적 이점과 더불어 시간적인 이점도 가져올 수 있다.

Lazy 라는 말만 들으면 뭔가 더 지연될 것 같은데, 어떻게 시간적으로도 이점이 생기는 걸까?

 

---

 

Lazy loading의 핵심 개념은, 파일을 디스크에서 메모리에 로드할 때 바로 물리 프레임을 획득하여 그곳에 로드하지 않고,

로딩에 필요한 정보만 따로 테이블에 저장해놓고 나중에 필요할 때 로드하는 것이다.

 

Lazy loading의 과정을 대략적으로 나열하면 다음과 같다.

 

 

1.  로드 시점에, 디스크에서 파일을 읽어와서 메모리에 쓰기 위해 필요한 로딩 정보를 페이지 테이블 (kaist-pintos에서는 supplemental page table)에 저장한다.

2.  이후 프로그램이 실행되면서, 해당 메모리 공간을 참조하려고 하면 page fault가 발생한다.

    - 아직 mmu 상에 해당 가상주소와 물리주소가 매핑되어 있지 않기 때문이다.

3.  fault가 발생한 가상주소를 토대로 페이지 테이블에서 페이지를 찾아본다. 만약 찾았다면 Lazy load를 하기 위해 저장해 둔 것이다. 못 찾았다면 정말 잘못된 주소가 참조된 것이므로, 정말로 page fault 처리를 한다.

4.  Lazy load를 위한 fault였음이 검증되면, 이제 물리 프레임을 할당받아서 매핑하고 (mmu에 매핑정보를 남기고), 아까 저장해둔 로딩에 필요한 정보를 토대로 해당 주소의 메모리에 파일을 로드한다.

 

 

간단한 구현 방법을 코드와 함께 살펴보자.

(* 주의 : pintos에서, 특히 project 3 virtual memory 에서부터는 세부 구현이 사람마다 매우 달라지고, 그 세부 구현에 따라 코드의 작동이 크게 달라질 수 있으므로 이 코드를 그대로 사용하는 것에는 각별한 주의를 요합니다.)

static bool
load_segment (struct file *file, off_t ofs, uint8_t *upage,
		uint32_t read_bytes, uint32_t zero_bytes, bool writable) {
	ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0) {
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* Set up aux to pass information to the lazy_load_segment. */
		struct aux *aux = calloc(1, sizeof(struct aux));
		aux->file = file;
		aux->ofs = ofs;
		aux->page_read_bytes = page_read_bytes;
		aux->page_zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, aux))
			return false;

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		ofs += PGSIZE;
	}
	return true;
}

user program을 실행하기 위한 process의 initial load 과정이다.

 

실행 파일(executable file)로부터 헤더 정보를 읽어와서,

어떤 파일의 (*file)

어떤 오프셋에서 (ofs)

어떤 가상주소에 (*upage)

몇 바이트가 읽혀 올라가야 하는지 (read_bytes)

그리고 페이지 사이즈에 공간을 정렬하기 위해 몇 바이트가 0으로 초기화되어야 하는지 (zero_bytes)

쓰기가 금지되어야 하는지 (writable) 등의 정보들을 전달받은 상태다.

 

pintos project 2에서는 이들을 파일에서 바로 물리 메모리에 올렸지만

project 3에서는 lazy load를 할 것이다.

 

그래서 aux 구조체를 calloc으로 할당받아 생성하고, 그 안에 필요한 정보들을 담았다.

그리고 vm_alloc_page_with_initializer 라는 함수에 인자들을 담아 전달해주었다.

 

여기서 눈여겨 보아야 하는 것이 인자로 전달된 함수포인터 lazy_load_segment인데,

이 함수가 나중에 page fault 발생 시 실행되면서 lazy load를 해 줄 것이다.

 

bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {

	ASSERT (VM_TYPE(type) != VM_UNINIT)

	struct supplemental_page_table *spt = &thread_current ()->spt;

	/* Check whether the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		/* Create the page, fetch the initializer according to the VM type,
		   and then create "uninit" page struct by calling uninit_new. */
		struct page *page = calloc (1, sizeof(struct page));
		switch (VM_TYPE(type)) {
			case VM_ANON:
				uninit_new (page, upage, init, type, aux, anon_initializer);
				break;
			case VM_FILE:
				uninit_new (page, upage, init, type, aux, file_backed_initializer);
				break;
			default:
				printf("vm_alloc_page_with_initializer: Unexpected page type.\n");
				goto err;
		}

		/* Set some initial stuff. */
		page->writable = writable;
		page->page_cnt = 0;
		page->sec_no = -1;

		/* Insert the page into the spt. */
		if (!spt_insert_page (spt, page))
			goto err;

		/* Claim immediately if the page is the first stack page. */
		if (VM_IS_STACK(type))
			return vm_do_claim_page (page);

		return true;
	}
err:
	return false;
}

이 함수는 initial 함수이기 때문에,

아직 spt(supplemental page table)에 들어가지 않은 가상주소만을 인자로 받아 실행되어야 한다.

 

그리고 type에 따라 uninit_new 함수를 실행하는데,

이 함수를 거치면 페이지 구조체에 적절한 initial 인자들이 알맞게 들어가게 된다.

아까 말한 lazy_load_segment 함수포인터가 세번째 인자인 init으로 들어가는 모습을 확인할 수 있다.

 

그리고 spt에 페이지를 삽입하고 이 함수는 리턴된다.

 

 

 

그리고 프로그램이 진행되면서, mmu가 모르는 가상주소 (물리주소와 매핑되어있지 않은 주소)를 참조하게 되면 하드웨어적인 page fault 가 발생하면서 page fault exception으로 진입하게 된다.

 

나는 해당 exception이 발생하면 vm_try_handle_fault 함수가 실행되도록 했다.

만약 적법한(legal) fault일 경우, lazy load가 진행되게 될 것이다.

 

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;

	/* Grow the stack if it's a valid stack growth case. */
	void *rsp = f->rsp;
	if (rsp-8 == addr ||
		((rsp <= addr) && (VM_STACKSIZE_LIMIT <= addr) && (addr < USER_STACK))) {
		
		/* Check that the page is evicted stack. */
		if (page = spt_find_page (spt, pg_round_down(addr)))
			vm_do_claim_page (page);
		else
			vm_stack_growth (addr);
			
		return true;
	}

	/* Check the address entry's existance in the SPT. */
	void *va = pg_round_down(addr);
	if ((page = spt_find_page (spt, va)) == NULL)
		return false;	/* Real Page Fault */

	/* Check that user tries to write on the unwritable. (i.e. code segment) */
	if (user && write && !(page->writable))
		return false;

	return vm_do_claim_page (page);
}

윗쪽의 stack growth 관련 코드는 일단 무시하고, 아래쪽의 코드를 보자.

 

가상주소를 page entry에 맞게 round_down 하고, 해당 entry를 spt에서 찾는다.

만약 spt에 없으면 진짜 잘못된 fault일 것이다.

 

하지만 그렇지 않다면, vm_do_claim_page 함수가 실행되면서 lazy load 과정에 들어간다.

 

static bool
vm_do_claim_page (struct page *page) {
	ASSERT (page != NULL);

	struct frame *frame = vm_get_frame ();
	struct supplemental_page_table *spt = &thread_current()->spt;

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* Insert page table entry to map page's VA to frame's PA. */
	pml4_set_page (thread_current()->pml4, page->va, frame->kva, page->writable);

	return swap_in (page, frame->kva);
}

이 함수에서는 물리 frame을 받아오고,

frame 과 page 간에 연결 관계를 형성한다.

 

그리고 pml4에 page entry, frame entry 주소를 연결되도록 함으로써

추후 해당 페이지를 참조하더라도 fault가 발생하지 않도록 해주었다.

 

마지막으로 swap_in 함수가 실행되는데,

이는 미리 정의된 매크로로, page의 type에 따라 다른 함수를 실행시켜준다.

여기서는 아직 초기화되지 않은 (uninit) 페이지이므로,

uninit_initialize 함수가 실행될 것이다.

 

static bool
uninit_initialize (struct page *page, void *kva) {
	struct uninit_page *uninit = &page->uninit;

	/* Fetch first, page_initialize may overwrite the values */
	vm_initializer *init = uninit->init;
	void *aux = uninit->aux;

	return uninit->page_initializer (page, uninit->type, kva) &&
		(init ? init (page, aux) : true);
}

uninit_initialize 함수는

anon 또는 file page로 전환되기 위한 initializer 함수를 실행해주고,

드디어 아까 인자로 전달했던 init 함수

 

lazy_load_segment 를 실행하게 된다.

인자로 page 구조체와 aux까지 넣어서 말이다.

 

static bool
lazy_load_segment (struct page *page, struct aux *aux) {
	/* TODO: Load the segment from the file */
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */

	/* Load aux data. */
	struct file *file = aux->file;
	off_t ofs = aux->ofs;
	size_t page_read_bytes = aux->page_read_bytes;
	size_t page_zero_bytes = aux->page_zero_bytes;

	/* Load this page. */
	if (file_read_at (file, page->va, page_read_bytes, ofs) != (int) page_read_bytes)
		return false;

	memset (page->va + page_read_bytes, 0, page_zero_bytes);

	return true;
}

 

 

lazy_load_segment 함수에서는 아까 aux에 담아두었던 인자들을 가지고

file_read_at 함수를 실행한다.

file의 ofs 위치로부터 page_read_bytes 만큼 읽어서 page의 va(가상주소)에 쓴다.

그리고 page_zero_bytes만큼 0으로 채워준다.

 

---

 

이 함수를 보면 알겠지만, lazy load가 이루어졌다고 해서 파일의 모든 내용이 메모리에 올라가는 것이 아니다.

필요할때마다 한 페이지씩 로드해서, 공간을 효율적으로 사용한다는게 이 lazy load의 포인트다.

 

시간적으로도 이득을 볼 수 있는데,

만약 디스크에 저장된 파일 크기가 엄청 크다고 생각해보자.

그럼 그 큰 파일을 메모리에 불러오는데만 해도 로딩 시간이 엄청 길어질 것이다.

 

lazy load 방식을 사용하면, 읽어오는데 필요한 정보만 저장되게 되므로 훨씬 로딩 시간이 빨라진다.

물론 런타임에 필요할때마다 한번씩 읽어오게 되므로, 어떤 조건에서는 한번에 로드해놓고 실행하는 것보다 현저히 느릴 가능성도 있다.

 

만약 진짜로 운영체제를 설계하게 된다든지, 아니면 위에서 말했던 JPA나 웹 환경에서 lazy load를 할지 eager load를 할지 선택해야 하는 경우에는 이같은 case들을 충분히 고려하고 방식을 설계해야 하겠다.