개발하는데 다 이유가 있겠지

---

Virtual Memory

---

가상 메모리 관리

가상 메모리 관리에서 가장 중요한 것은 얼마나 disk를 덜 방문하느냐
disk에 데이터를 read, write를 하는 작업들은 느리기 때문임

 

페이징

고정된 크기(page 단위)로 메모리 공간을 분할해 가상 메모리를 관리하는 기법

필요성

1. 메모리 공간이 고르게 분할되어 있기 떄문에 빈 공간이 작게 분할되어 유용하게 사용될 수 있어 외부 단편화 해결 2. 필요한 메모리보다 조금 더 큰 크기의 메모리를 할당하여 내부 단편화가 발생하더라도 크게 문제되지 않음 3. 물리 메모리보다 더 큰 주소 공간을 제공해 프로세스가 물리 메모리에 직접 접근하지 않고, 가상 주소를 통해 메모리 접근 4. 필요한 페이지만 물리 메모리에 로드해 메모리 사용을 최적화 5. 각 프로세스마다 독립적인 페이지 테이블을 사용해 다른 프로세스의 메모리에 접근하지 못함 6. 컨텍스트 스위칭시 새로운 프로세스의 페이지 테이블을 로드해 빠르게 전환이 가능 7. 동적으로 메모리를 할당하고 해제할 수 있음

 

프레임

물리 메모리를 페이지와 같은 크기로 나눈 블록의 단위(frame 단위)

특징	1. 페이지 테이블을 사용해 가상 주소 공간의 page와 물리 메모리의 프레임에 맵핑 2. 필요에 의해 페이지를 물리 메모리에서 제거하고 디스크의 스왑 영역에 저장(필요시 다시 물리 메모리에 로드)

 

MMU(Memory Management Unit)

페이지 테이블에 담긴 정보를 기반으로 가상-물리 주소 변환을 수행하는 하드웨어 장치
메모리 보안, 보호(memory protection) 역할을 수행(잘못된 요청 : 접근 권한, 존재하지 않는 가상 주소 등..)

 

TLB(Translation Lookaside Buffer)

CPU가 특정 데이터를 접근할 때 페이지 테이블, 물리 메모리를 총 2번 접근해야 하기 때문에 시간 손실 발생
시간 손실을 줄이기 위해 가장 최근에 많이 사용한 일부분들을 TLB에 캐시해 원하는 정보를 페이지 테이블에 접근할 필요없이 즉시 원하는 데이터에 접근할 수 있도록 함

---

Memory Management

Implement Supplemental Page Table

supplemental_page_table_init

가상 주소에 대한 정보를 다루는 해시 테이블(보조 테이블)을 초기화

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	hash_init(&spt->pages, vm_hash_func, vm_less_func, NULL);
}

unsigned vm_hash_func(struct hash_elem *e, void *aux)
{
	struct page *page_e = hash_entry(e, struct page, h_elem);
	return hash_bytes(&page_e->va, sizeof(page_e->va));
}

bool vm_less_func(struct hash_elem *a, struct hash_elem *b, void *aux)
{
	struct page *page_a = hash_entry(a, struct page, h_elem);
	struct page *page_b = hash_entry(b, struct page, h_elem);
	return page_a->va < page_b->va;
}

 

spt_find_page

보조 테이블(spt)에서 가상 주소를 통해 페이지를 검색

struct page *spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	struct page *search_page = malloc(sizeof(struct page)); // 검색용 page 할당
	search_page->va = pg_round_down(va);

	struct hash_elem *find_elem = hash_find(&spt->pages, &search_page->h_elem);
	free(search_page); // 임시 page 메모리 해제

	if (find_elem == NULL)
		return NULL;
	return hash_entry(find_elem, struct page, h_elem);
}

 

spt_insert_page

해쉬 테이블에 페이지를 삽입

bool spt_insert_page(struct supplemental_page_table *spt UNUSED, struct page *page UNUSED)
{
	return hash_insert(&spt->pages, &page->h_elem) == NULL;
}

---

Frame Management

프레임 구조체 및 프레임 테이블

static struct list frame_table;

struct frame
{
	void *kva;	  // 물리 프레임에 대응하는 가상 주소
	struct page *page; // 프레임이 할당된 페이지를 가리키는 포인터
	struct list_elem f_elem;
};

 

vm_get_frame

프레임을 할당받아 주소를 저장하고 프레임 테이블에 저장

static struct frame *vm_get_frame(void)
{
	struct frame *frame = NULL;
	void *kva = palloc_get_page(PAL_USER);

	frame = (struct frame *)malloc(sizeof(struct frame));
	frame->kva = kva;
	frame->page = NULL;
	list_push_back(&frame_table, &frame->f_elem);

	ASSERT(frame != NULL);
	ASSERT(frame->page == NULL);
	return frame;
}

 

vm_do_claim_page

할당된 프레임과 페이지를 매핑하고 스왑

static bool vm_do_claim_page(struct page *page)
{
	struct frame *frame = vm_get_frame();

	frame->page = page;
	page->frame = frame;

	if (pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable))
		return swap_in(page, frame->kva);
	else
		return false;
}

 

vm_claim_page

보조 테이블에서 페이지를 찾아서 할당 및 매핑 요청

bool vm_claim_page(void *va UNUSED)
{
	struct page *page = spt_find_page(&thread_current()->spt, va);
	if (page == NULL)
		return false;
	return vm_do_claim_page(page);
}

---

Anonymous Page

vm_alloc_page_with_initializer

타입에 따라 초기화되지 않은 페이지를 생성하고 보조 테이블에 삽입

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;
	if (spt_find_page(spt, upage) == NULL)
	{
		struct page *page = malloc(sizeof(struct page));
		if (page == NULL)
			goto err;
		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;
		}
		page->writable = writable;
		return spt_insert_page(spt, page);
	}
err:
	return false;
}

 

uninit_initialize

첫 번째 페이지 폴트가 발생했을 때 페이지를 초기화

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

	vm_initializer *init = uninit->init;
	void *aux = uninit->aux;

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

 

load_segment

파일을 물리 메모리에 lazy-load하는 함수

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);							// 오프셋이 페이지 크기의 배수인지 확인

	// read_bytes 또는 zero_bytes가 남아있는 동안 반복
	while (read_bytes > 0 || zero_bytes > 0) {
		/* 이 페이지를 어떻게 채울지 계산
		 * FILE에서 PAGE_READ_BYTES 바이트를 읽고
		 * 마지막 PAGE_ZERO_BYTES 바이트를 0으로 채움 */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* Create & Initialize page */
		struct load_info *info = malloc(sizeof(struct load_info));
		info->file = file;
		info->offset = ofs;
		info->read_bytes = page_read_bytes;
		info->zero_bytes = page_zero_bytes;

		// lazy_load_segment 함수를 사용하여 페이지를 초기화하는 vm_alloc_page_with_initializer 호출
		if (!vm_alloc_page_with_initializer (VM_ANON, upage, writable, lazy_load_segment, info))
			return false;

		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		ofs += page_read_bytes;
		upage += PGSIZE;
	}
	return true;
}

 

vm_anon_init

익명 페이지를 초기화

 

anon_initializer

익명 페이지(VM_ANON)의 초기화 함수

 

---

Stack Growth

vm_try_handle_fault

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)
{
	struct supplemental_page_table *spt UNUSED = &thread_current()->spt;

	// 유효성 검사
	if (addr == NULL || is_kernel_vaddr(addr))
		return false;

	// Stack Growth
	if (page == NULL)
	{
		/*
		 * [ Stack Growth ]
		 * - USER 모드에서의 페이지 폴트라면 현재 rsp를 그대로 사용 가능
		 * - But, KERNEL 모드에서의 페이지 폴트라면 유저 모드에서 커널 모드로 전환될 때 저장해둔 rsp를 가져와야 함!!
		 */
		void *rsp_stack = user ? f->rsp : thread_current()->rsp;
		if (USER_STACK > addr && addr > USER_STACK - (1 << 20))
		{
			if (addr >= rsp_stack - 8)
			{
				vm_stack_growth(pg_round_down(addr));
				page = spt_find_page(spt, addr);
				return vm_do_claim_page(page);
			}
		}
		return false;
	}

	// 쓰기 접근인데 페이지가 읽기 전용인 경우
	if (write == true && page->writable == false)
		return false;

	return vm_do_claim_page(page);
}

 

stack_growth

page fault가 발생한 주소가 rsp-8보다 크다면 스택을 성장시킴

static void
vm_stack_growth(void *addr UNUSED)
{
	vm_alloc_page(VM_ANON | VM_MARKER_0, addr, true);
}

 

---

Memory Mapped Files

mmap

받아온 인자들을 조건에 충족하는 확인하고 충족한다면 do_mmap()을 통해 파일을 매핑
아래와 같은 경우 NULL을 반환
- 파일의 length 가 0인 경우
- addr, offset이 페이지 배수로 정렬되지 않은 경우
- addr이 기존의 매핑된 페이지와 겹치는 경우
- addr이 0인 경우
- fd가 STDIN(0), STDOUT(1)인 경우 등등

void *
mmap(void *addr, size_t length, int writable, int fd, off_t offset)
{
	if ((int)length <= 0)
		return NULL;

	if (offset % PGSIZE != 0)
		return NULL;

	if (addr == NULL || addr != pg_round_down(addr))
		return NULL;

	if (!is_user_vaddr(addr) || !is_user_vaddr(addr + length))
		return NULL;

	if (spt_find_page(&thread_current()->spt, addr) != NULL)
		return NULL;

	if (fd == STDIN_FILENO || fd == STDOUT_FILENO)
		return NULL;

	struct file *file = get_file(fd);
	if (file == NULL)
		return NULL;

	return do_mmap(addr, length, writable, file, offset);
}

 

do_mmap

파일을 읽어들여 프레임에 로드하고 매핑을 하는 함수
*파일의 길이에 따라 여러 페이지를 로드할 수 있음

void *
do_mmap(void *addr, size_t length, int writable, struct file *file, off_t offset)
{
	struct file *map_file = file_reopen(file);

	off_t file_bytes = file_length(map_file);
	size_t read_bytes = length > file_bytes ? file_bytes : length;
	size_t zero_bytes = PGSIZE - (read_bytes % PGSIZE);
	void *file_address = addr;
	int page_cnt = (length + PGSIZE - 1) / PGSIZE;

	while (read_bytes > 0 || zero_bytes > 0)
	{
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		struct load_info *map_info = malloc(sizeof(struct load_info));
		map_info->file = map_file;
		map_info->offset = offset;
		map_info->read_bytes = page_read_bytes;
		map_info->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable, lazy_load_segment, map_info))
		{
			file_close(map_file);
			return NULL;
		}

		spt_find_page(&thread_current()->spt, addr)->map_page_cnt = page_cnt;

		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		offset += page_read_bytes;
		addr += PGSIZE;
	}
	return file_address;
}

 

munmap

단순히 do_munmap()을 호출

void munmap(void *addr)
{
	do_munmap(addr);
}

 

do_munmap

로드된 파일에 해당하는 페이지 개수만큼 매핑을 해제하는 함수

void do_munmap(void *addr)
{
	struct supplemental_page_table *spt = &thread_current()->spt;
	struct page *page = spt_find_page(spt, addr);
	int count = page->map_page_cnt;

	for (int i = 0; i < count; i++)
	{
		if (page != NULL)
			destroy(page);
		addr += PGSIZE;
		page = spt_find_page(spt, addr);
	}
}

 

vm_file_init

가상 메모리의 파일을 초기화하는 함수

 

file_backed_initializer

파일 페이지를 초기화하는 함수

bool file_backed_initializer(struct page *page, enum vm_type type, void *kva)
{
	page->operations = &file_ops;
    
	struct load_info *load_info = page->uninit.aux;
	struct file_page *file_page = &page->file;
    
	file_page->file = load_info->file;
	file_page->offset = load_info->offset;
	file_page->read_bytes = load_info->read_bytes;
	file_page->zero_bytes = load_info->zero_bytes;
    
	return true;
}

 

file_backed_destroy

파일 페이지를 페이지 테이블에서 삭제하고 수정사항이 있다면 디스크에 기록하는 함수

static void file_backed_destroy(struct page *page)
{
	struct file_page *file_page UNUSED = &page->file;
    
	if (pml4_is_dirty(thread_current()->pml4, page->va))	// 수정사항이 있다면
	{
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->offset); // 디스크(해당 파일)에 기록함
		pml4_set_dirty(thread_current()->pml4, page->va, false);
	}
    
	pml4_clear_page(thread_current()->pml4, page->va);	// 페이지 테이블에서 제거
}

 

---

Swap In/Out

Anonymous Page

vm_anon_init

익명 페이지가 스왑되는 스왑 영역의 크기로 비트맵을 생성하는 함수

const size_t SECTORS_PER_PAGE = PGSIZE / DISK_SECTOR_SIZE;

void vm_anon_init(void)
{
	swap_disk = disk_get(1, 1); // 디스크의 1번째 컨트롤러와 1번째 디스크를 swap 디스크로 설정합니다.

	// swap 디스크의 크기를 페이지 단위로 계산합니다. 디스크 크기(disk_size)는 섹터 단위로 반환되므로,
	// 이를 페이지 크기로 나누어 swap 영역에 사용할 수 있는 페이지 수를 계산합니다.
	size_t swap_size = disk_size(swap_disk) / SECTORS_PER_PAGE;

	// swap 영역에 사용할 수 있는 페이지 수 크기의 비트맵을 생성합니다.
	// 이 비트맵은 각 페이지 슬롯의 사용 여부를 추적하는 데 사용됩니다.
	swap_table = bitmap_create(swap_size); // 비트맵을 생성
}

 

anon_initializer

초기 페이지를 할당시 Uninit page를 할당함
익명 페이지를 초기화해주기 위해서 해당 데이터를 0으로 초기화(일관성 유지) -> Union 영역 모두 0으로 초기화

bool anon_initializer(struct page *page, enum vm_type type, void *kva)
{
	struct uninit_page *uninit = &page->uninit;
	memset(uninit, 0, sizeof(struct uninit_page));

	page->operations = &anon_ops;

	struct anon_page *anon_page = &page->anon;
	anon_page->swap_index = -1; // 디스크가 아닌 물리 메모리에 있기 때문에 -1로 설정
	return true;
}

 

anon_swap_in

익명 페이지를 스왑 영역에서 내용을 읽어와 스왑 인하는 함수

static bool anon_swap_in(struct page *page, void *kva)
{
	struct anon_page *anon_page = &page->anon;

	// 페이지가 스왑되어 있는지 확인하기 위해 페이지의 스왑 인덱스를 가져옴
	int page_no = anon_page->swap_index;

	// 스왑 테이블에서 해당 스왑 슬롯을 사용 중인지 확인
	if (bitmap_test(swap_table, page_no) == false)
		return false;

	// 스왑 디스크에서 페이지 데이터를 읽어와 메모리에 복원
	for (int i = 0; i < SECTORS_PER_PAGE; i++)
	{
		disk_read(swap_disk, page_no * SECTORS_PER_PAGE + i, kva + DISK_SECTOR_SIZE * i);
	}

	// 스왑 테이블에서 해당 스왑 슬롯을 다시 사용 가능하도록 표시
	bitmap_set(swap_table, page_no, false);

	return true;
}

 

anon_swap_out

희생자 페이지로 선정된 페이지를 스왑아웃해 내용을 스왑 영역(비트맵)에 기록하는 함수

static bool anon_swap_out(struct page *page)
{
	struct anon_page *anon_page = &page->anon;

	// swap_table에서 처음(0)부터 시작해서 false인 비트를 하나(1) 찾음
	int page_no = bitmap_scan(swap_table, 0, 1, false);

	// 스왑 테이블에서 사용 가능한 스왑 슬롯을 찾을 수 없을 경우
	if (page_no == BITMAP_ERROR)
		return false;

	// 페이지의 내용을 스왑 디스크에 쓰기
	for (int i = 0; i < SECTORS_PER_PAGE; i++)
	{
		disk_write(swap_disk, page_no * SECTORS_PER_PAGE + i, page->va + DISK_SECTOR_SIZE * i);
	}

	// 스왑 테이블에서 해당 스왑 슬롯을 사용 중으로 표시
	bitmap_set(swap_table, page_no, true);

	// 페이지 테이블에서 해당 가상 주소에 매핑된 페이지 엔트리를 제거
	pml4_clear_page(thread_current()->pml4, page->va);

	/* 페이지의 swap_index 값을 이 페이지가 저장된 swap slot의 번호로 써 준다. */
	anon_page->swap_index = page_no;

	return true;
}

 

File-backed Page

file_backed_swap_in

파일에서 데이터를 읽고 남는 공간을 0으로 초기화한 후 스왑 인하는 함수

static bool file_backed_swap_in(struct page *page, void *kva)
{
	struct file_page *file_page = &page->file;

	off_t size = file_read_at(file_page->file, kva, (off_t)file_page->read_bytes, file_page->offset); // 파일에서 데이터를 읽어와 페이지에 복원
	if (size != file_page->read_bytes)																  // 읽은 데이터의 크기와 페이지에 저장된 데이터 크기가 일치하는지 확인
		return false;

	memset(kva + file_page->read_bytes, 0, file_page->zero_bytes); // 파일의 나머지 부분은 0으로 채움
	return true;
}

 

file_backed_swap_out

희생자 페이지로 선정된 파일 페이지가 수정 사항이 있다면 디스크에 해당 파일에 수정사항을 저장하고 페이지 테이블에서만 지움
수정사항이 없다면 

static bool file_backed_swap_out(struct page *page)
{
	struct file_page *file_page = &page->file;
	struct thread *curr_thread = thread_current();

	if (pml4_is_dirty(curr_thread->pml4, page->va)) // 수정사항이 있다면
	{
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->offset); // 파일에 쓰고
		pml4_set_dirty(curr_thread->pml4, page->va, false);									// 더티 비트를 false로 수정
	}
	pml4_clear_page(curr_thread->pml4, page->va); // 페이지 테이블에서 지움
	
	page->frame = NULL;

	return true;
}

 

---

FLOW