운영체제(구현) - 핀토스 - Virtual memory - Anoymous page(Lazy loading)

익명 페이지 - 백업 파일, 장치x.

• 이름이 있는 파일 소스를 가지고 있지 않기 때문에 익명이라고 함. 익명 페이지는 실행 가능한 파일에서 스택 and 힙 영역에서 사용된다.

지연 로딩

필요한 시점까지 데이터 자원을 불러오지 않고, 필요한 순간에만 해당 자원을 로딩. 애플리케이션 시작 시 초기 로딩 시간 최소화. 자원을 효율적으로 관리하여 성능을 향상 시킴.

이 타이밍에 Lazy loading를 왜 쓰나요?

• 물리 메모리는 공간적으로 한계가 있다. 필요한 시점이 되어서야 메모리에 로딩을 시키는 방식
• 가상 메모리의 경우 일종의 환상이다. 우리는 페이지에 대한 접근을 위하여 가상 메모리를 거쳐 물리 메모리의 접근이 필수적이다.
• 물리 메모리의 용량이 한정되어 있기 때문에 멀티프로세싱 등의 발전으로 다양한 프로세스들에 대한 데이터를 물리 메모리에 올리고 내리는 작업을 수행한다.
• 이러한 작업을 효율적으로 해주는 것이 Lazy loading
• 나중에 가득찬 물리 메모리를 비워주는 eviction이 필요하다. 이거는 뒤에 swap 과정에서 할 것이다. FIFO, Optimal Condition, LRU, Random 등의 방식이 있다.

들어가기 전 브리핑

Lazy Loading을 이용한 페이지 초기화

• 메모리 로딩을 필요한 시점까지 미루는 디자인 패턴.
• 페이지 할당 시 해당 페이지에 대응하는 페이지 구조체 만들고 and 물리 프레임 할당x, 실제 내용x(아직 로딩하지 않는다)

그렇다면 내용을 로드하는 시점?

• page fault가 발생하는 시점. 이 주소에 접근했다는 것 > 실제로 내용이 필요한 시점이 되었음

그래서 받았을 때, 시그널을 받았을 때 내용이 로드되게 구현하면 Lazy Loading 완성

페이지 생명주기

초기화 -> 페이지 폴트 -> 지연 로딩 -> 스왑 인 -> 스왑 아웃 -> 삭제

1. 초기화 - vm_alloc_page_with_initializer

페이지의 타입 and 초기화 함수 설정 + 초기 값 지정.

2. 페이지 폴트 - vm_try_handle_fault

프로세스가 해당 페이지에 접근시, 해당 페이지가 물리 메모리에 존재x → 페이지 폴트 발생.

3. 지연 로딩 - lazy_load_segment

페이지 폴트 발생 시 → 실제로 필요한 데이터를 메모리에 로드.

실제로 필요한 시점까지 데이터를 메모리에 로드x → 메모리의 사용 효율 높이기

4. 스왑 인 - anon_swap_in and file_backed_swap_in

페이지(스왑 영역) → 메모리로 로드 되는 과정.

5. 스왑 아웃 - anon_swap_out ****and file_backed_swap_out

메모리가 부족시 → 사용x 페이지를 스왑 영역으로 내보냄.

메모리 사용량 최적화.

6. 삭제 - anon_destroy and file_backed_destroy

페이지가 더 이상 필요 없을 때, 메모리 and 스왑 디스크에서 완전히 제거. 이를 통해 메모리 누수 방지.

익명 페이지를 위한 초기화 함수 - anon_initializer
파일 기반 페이지를 위한 초기화 함수 - file_backed_initializer

구현해야 할 함수들 순서

1. vm_alloc_page_with_initializer - page 구조체를 생성 and 적절한 초기화 함수 설정
2. load_segment - 파일에서 데이터를 읽어와 페이지에 로드
3. lazy_load_segment - 첫 번째 페이지 폴트가 발생할 때 호출되어 파일에서 데이터를 읽어와 페이지에 로드
4. setup_stack - 사용자 스택을 할당 and 페이지 테이블에 매핑하여 스택 포인터 초기화
5. vm_try_handle_fault - 보조 테이블(SPT)을 확인하고, 페이지가 존재x > 새로운 페이지 할당 + 매핑

1. vm_alloc_page_with_initializer

page 구조체를 생성 and 적절한 초기화 함수 설정.

해야할 것

• uninit 타입으로 초기화 & 초기화 함수 설정
• page 구조체의 필드 수정

매개변수 writable을 page 구조체의 writable 필드에 할당

필드의 값을 수정할 때는 uninit_new 함수가 호출된 이후에 수정

page를 SPT에 삽입

코드

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 wheter the upage is already occupied or not. */
	// 5. 페이지가 이미 존재하는 경우 **에러 처리**
	if (spt_find_page (spt, upage) == NULL)
	{
		/* TODO: Create the page, fetch the initialier according to the VM type,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */

		// 1-1. 페이지 **생성**
		struct page *p = (struct page *)malloc(sizeof(struct page));

		// 1-2. type에 따라 초기화 함수를 가져오기
		bool (*page_initializer)(struct page *, enum vm_type, void *);

		switch (VM_TYPE(type))
		{
		
		case VM_ANON: // **익명** 페이지(파일 시스템과 **독립적**으로 존재하는 페이지 관리)
			page_initializer = anon_initializer;
			break;
		
		case VM_FILE: // **매핑된** 페이지(파일의 내용을 메모리에 매핑하여 사용할 때 사용)
			page_initializer = file_backed_initializer;
			break;
		}

		// 2. **페이지 초기화**(uninit 타입)
		uninit_new(p, upage, init, type, aux, page_initializer);

		// 3. unit_new를 호출한 후 필드 수정 - uninit_new 함수 안에서 구조체 내용이 전부 새로 할당.
		p->writable = writable;

		/* TODO: Insert the page into the spt. */
		// 4. 초기화된 페이지 > spt에 추가.
		return spt_insert_page(spt, p);
		
	}
err:
	return false;
}

2.  load_segment

파일에서 데이터를 읽어와 페이지에 로드

• vm으로 load를 할 때 page 단위로 load를 하며 처음 load의 경우 vm_alloc_page_with_initializer로 allocation 함

우선 uninitialized 된 상태의 page를 alloc 하고 lazy_load_segment 및 file_info를 함께 인자로 넘기며 alloc

코드

static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
			 uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{

	// 1. 전제 조건 확인
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0); 
	ASSERT(pg_ofs(upage) == 0); // 'upage'가  페이지의 시작 주소인지 확인
	ASSERT(ofs % PGSIZE == 0); // 'ofs'가 페이지 크기(PGSIZE)의 배수인지 확인

	// 2. 루프 조건('read_bytes' 와 'zero_bytes'중 하나라도 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. */
		
		// 3. 페이지에 읽어야 할 바이트 수 and 0으로 채울 바이트 수 계산
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE; 
		
		size_t page_zero_bytes = PGSIZE - page_read_bytes; 

		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		// 4. 구조체 **초기화** 
		struct lazy_load_arg *lazy_load_arg = (struct lazy_load_arg*)malloc(sizeof(struct lazy_load_arg));

		lazy_load_arg->file = file; // 내용이 담긴(파일 객체)
		lazy_load_arg->ofs = ofs; // 읽기 시작할 위치
		lazy_load_arg->read_bytes = page_read_bytes; // 읽어야 하는 바이트 수
		lazy_load_arg->zero_bytes = page_zero_bytes; // read_bytes 만큼 읽고 공간이 남아 0으로 채워야 하는 바이트 수

		// 대기 중인 **객체 생성**
		// 페이지 초기화 and 데이터 로드 효율적 처리 > 초기화 함수로 'lazy_load_segment' 함수 사용
		if (!vm_alloc_page_with_initializer(VM_ANON, upage,
											writable, lazy_load_segment, lazy_load_arg))
			return false;

		/* Advance. */
		// 다음 반복을 위한 **값 갱신**
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE; // 다음 페이지의 시작 주소 설정
		ofs += page_read_bytes; // 'ofs'를 읽기 시작 위치로 설정
	}
	return true; // 페이지 초기화가 성공적으로 완료되었음을 알려줌
}

3. lazy_load_segment

첫 번째 페이지 폴트가 발생할 때 호출되어 파일에서 데이터를 읽어와 페이지에 로드

lazy_loading을 위해 필요한 함수. vm_alloc_page_with_initializer 을 통해서 aux(file_info)를 받고 info를 읽어서 파일 → 버퍼로 씀(물리메모리)

해야할 것

• 이 함수가 호출되기 이전에 물리 프레임 매핑이 진행. 여기서는 물리 프레임에 내용을 로딩하는 작업만 하면 됌.
• 이 함수는 페이지 구조체와 aux를 인자로 받음

aux는 load_segment에서 로딩을 위해 설정해둔 정보 lazy_load_arg

이 정보를 사용하여 읽어올 파일을 찾아서 메모리에 로딩

코드

static bool
lazy_load_segment(struct page *page, void *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. */

	// 1. 구조체 포인터 **반환**
	struct lazy_load_arg *lazy_load_arg = (struct lazy_load_arg *)aux;

	// 2. 파일 위치 지정 - 파일의 읽기 위치를 'lazy_load_arg->ofs'로 지정.
	// 이는 파일에서 데이터를 읽기 시작할 위치 설정
	file_seek(lazy_load_arg->file, lazy_load_arg->ofs);

	// 3. 파일을 read_bytes만큼 물리 프레임에 **읽어 들인다**.
	if(file_read(lazy_load_arg->file, page->frame->kva, lazy_load_arg->read_bytes) != (int)(lazy_load_arg->read_bytes))
	{
		palloc_free_page(page->frame->kva);
		return false;
	}

	// 3. 다 읽은 지점부터 zero_bytes만큼 0으로 채운다.
	memset(page->frame->kva + lazy_load_arg->read_bytes, 0, lazy_load_arg->zero_bytes);

	return true;
}

4. setup_stack

사용자 스택을 할당 and 페이지 테이블에 매핑하여 스택 포인터 초기화

해야할 것

• 스택은 아래로 성장하므로, 스택의 시작점인 USER_STACK에서 PGSIZE(4KB)만큼 아래로 내린 지점(stack_bottom)에서 페이지 생성.

• 첫 번째 스택 페이지는 Lazy Loading 필요x

프로세스가 실행할 때 이 함수가 불리고 나서 command line arguments를 스택에 추가하기 위해 이 주소에 바로 접근하기 때문

• rsp 값 → USER_STACK 변경.
• 페이지를 할당받을 때 이 페이지가 스택의 페이지임을 표시하기 위해서 보조 마커를 사용할 수 있다.

static bool
setup_stack(struct intr_frame *if_)
{
	bool success = false;
	void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

	/* TODO: Map the stack on stack_bottom and claim the page immediately.
	 * TODO: If success, set the rsp accordingly.
	 * TODO: You should mark the page is stack. */
	/* TODO: Your code goes here */

	/*
	stack_bottom에 스택을 매핑하고 페이지를 즉시 요청.
    성공하면, rsp를 그에 맞게 설정. 페이지가 스택임을 표시해야함.
	*/

	// VM_ANON | VM_MARKER_0 플래그 사용하여 페이지가 스택 페이지임을 표시.
	if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1))
	{
		// 2. 할당 받은 페이지에 바로 (**물리**) 프레임 매핑
		success = vm_claim_page(stack_bottom);
		
		// 3. rsp(스택 포인터) 변경. (argument_stack에서 이 위치부터 인자 push)
		if (success)
		{
			if_->rsp = USER_STACK;
		}

	}
	return success;
}

5. vm_try_handle_fault

보조 테이블(SPT)을 확인하고, 페이지가 존재x > 새로운 페이지 할당 + 매핑

• spt_find_page 를 통해 spt 참조하여 faulted address에 해당하는 페이지 구조체를 해결하기.
• page_fault가 발생하면 제어권을 전달받는 함수
• 물리 프레임이 존재하지 않아서 발생한 예외일 경우 매개변수

코드

bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
	// 1. SPT 참조
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	// 2. 페이지 확인 or 처리
	struct page *page = NULL;

	// 주소 유효성 검사 
	// 3. 주소 유효성 검사(자체가 있는지)
	if(addr == NULL)
	{
		return false;
	}
	// 4. 커널 주소 검사(커널 주소 공간에 속했는지)
	if (is_kernel_vaddr(addr))
	{
		return false; // 커널 주소 공간에 접근하려는 시도는 잘못된 접근이므로 'false' 반환
	}

	// 5. 페이지 폴트 원인 검사
	if(not_present) // 플래그 확인하여 접근한 페이지 자체가 메모리에 존재x
	{
		/* TODO: Validate the fault */

		void *rsp = f->rsp; // user access인 경우 rsp는 유저 스택을 가리킴

		// 6. spt에서 페이지 찾기
		page = spt_find_page(spt, addr); // spt에서 'addr'에 해당하는 페이지 찾기

		// 예외 처리(없을 경우 +  쓰기 접근 검사)
		if(page == NULL)
		{
			return  false;
		}

		// 7. 쓰기 접근 and 읽기 전용 페이지
		if(write == 1 && page->writable == 0)
		{
			return false; // 쓰기 접근 불가능 에러 처리
		}

		// 8. 페이지 클레임
		return vm_do_claim_page(page); // 페이지를 할당하고 매핑.
	}
	 return false;
}

Supplemental Page Table - Revisit

자식 프로세스를 생성 or 프로세스가 종료될 때 필요한 spt를 복사하는 함수 and 정리하는 함수

순서 이어서

1. supplementalpage_tablecopy
2. supplementalpage_tablekill

6. supplemental_page_table_copy

‘src’를 > 대상 보조 테이블 ‘dst’로 복사. 현재 실행 중인 프로세스의 페이지 테이블을 새로운 프로세스에 복사할 때 사용.

해야할 것

• 부모 프로세스의 SPT에 있는 모든 페이지를 각 타입에 맞게 할당을 받고, uninit 상태가 아니라면, 즉 내용이 로딩된 상태라면 바로 매핑을 진행해서 내용까지 그대로 복사

코드

bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED)
{
	// 해시 테이블 이터레이터 초기화
	struct hash_iterator i;
	hash_first(&i, &src->spt_hash);

	// 소스 spt의 해시 테이블 순회 > 각 페이지 처리
	while (hash_next(&i))
	{
		// 소스 페이지 정보 추출
		struct page *src_page = hash_entry(hash_cur(&i), struct page, bucket_elem);
		enum vm_type type = src_page->operations->type; // 페이지 타입
		void *upage = src_page->va; // 가상 주소
		bool writable = src_page->writable; // 쓰기 가능 여부

		// 1. type이 uninit이면(초기화 정보 사용하여 > 새로운 페이지 할당)
		if(type == VM_UNINIT)
		{
			vm_initializer *init = src_page->uninit.init; // 초기화 함수
			void *aux = src_page->uninit.aux; // 보조 데이터
			vm_alloc_page_with_initializer(VM_ANON, upage, writable, init, aux); // 새로운 페이지를 초기화 정보와 함께 할당
			continue; // 할당 완료시 다음 페이지로 넘어감.
		}

		// 2. type이 uninit이 아니면
		if(!vm_alloc_page(type, upage, writable))
		{
			return false;
		}

		// 'vm_cliam_page' = 페이지 폴트 처리 and 메모리 로드 
		// vm_claim_page으로 요청해서 물리 메모리 프레임에 매핑 + 페이지 초기화
		if(!vm_claim_page(upage))
		{
			return false;
		}

		// 소스 페이지의 내용을 > 대상 페이지에 복사
		struct page *dst_page = spt_find_page(dst, upage); // 복사된 페이지를 찾아서
		memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE); // 페이지 크기만큼 데이터 복사
	}
	return true;
}

7. supplemental_page_table_kill

spt제거 and 모든 페이지 해제 + 수정된 내용을 저장소에 기록 = 스레드가 종료될 때 호출되어 자원을 정리함

해야할 것

• 이 함수는 프로세스가 종료될 때와 실행될 때 process_cleanup()에서 호출

• 페이지 항목들을 순회하며 테이블 내의 페이지들의 타입에 맞는 destroy 함수를 호출

• 여기서는 hash table은 그대로 두고 안의 요소들만 지워줘야 함.

hash_destroy 함수를 사용하면 hash가 사용하던 메모리(hash->bucket) 자체도 반환하므로, hash_destroy가 아닌 hash_clear o

Why? process가 실행될 때 hash table을 생성한 이후에 process_cleanup()이 호출되는데, 이때는 hash table은 남겨두고 안의 요소들만 제거.

hash table까지 지워버리면 만들자마자 지워버리는 게 됌.

process가 실행될 때 빈 hash table이 있어야 하므로 hash table은 남겨두고 안의 요소들만 지워야 함.

void
supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) {
	/* TODO: Destroy all the supplemental_page_table hold by thread and
	 * TODO: writeback all the modified contents to the storage. */
	hash_clear(&spt->spt_hash, hash_page_destroy); // 해시 테이블의 모든 요소 제거
}

// 주어진 해시 요소(hash_elem) > page 제거 + 메모리 해제
void hash_page_destroy(struct hash_elem *e, void *aux)
{
    struct page *page = hash_entry(e, struct page, bucket_elem);
    destroy(page);
    free(page);
}