운영체제(구현) - 핀토스 - Virtual memory - SWAP-In/Out

물리 메모리의 활용을 극대화하기 위한 회수 기법. 현재 사용되지 않고 있는 메모리 프레임들을 디스크로 스왑 아웃 하는 것.

이는 일부 메모리 자원들을 해제 시켜서 다른 어플리케이션들이 이 자원들을 사용할 수 있게 해준다.

• 스와핑은 운영체제에 의해서 이루어진다.
• 메모리 고갈 시 메모리 할당 요청을 받았다는 것을 운영체제가 감지 후 > swap 디스크로 퇴거시킬 페이지 골라내기. 그리고 메모리의 프레임의 상태를 동일하게 디스크에 복사(스왑 아웃).
• 프로세스가 스왑 아웃된 페이지에 접근하려고 할 때, 운영체제는 디스크레 복사해둔 내용을 그대로 다시 메모리에 가져옴으로써 다시 복원시킴
• 모든 스와핑 연산은 명시적으로 호출되는 것이 아니라 함수 포인터로 호출된다.

퇴거 대상

• 익명 페이지(anonymous page)
• 파일 기반 페이지(file-backed page)

헤더 파일

slot 번호, slot 구조체

코드

// vm/anon.h
struct anon_page 
{
    uint32_t slot_no; // swap out될 때 이 페이지가 저장된 slot의 번호
};

// vm/vm.h
struct slot
{
	struct page *page;
	uint32_t slot_no;
	struct list_elem swap_elem;
};

 /* 스왑 관련된 구조체 초기화 */
 struct list swap_table;
 struct lock swap_table_lock;

Anonymous Page(매핑x)

vm_anon_init , anon_initializer 함수 수정

• 익명 페이지는 백업 저장소 필요 없다. →?
• 익명 페이지의 스와핑을 지원하기 위해 스왑 디스크라는 임시 백업 저장소 제공.
• 스왑 디스크 활용하여 익명 페이지에 대한 스왑 구현

vm_anon_init

스왑 디스크 설정 필요. 또한 스왑 디스크에서 사용 가능한 영역 and 사용된 영역 관리하기 위한 데이터 구조 필요.

• 스왑 영역도 PGSIZE 단위로 관리

코드

// vm/anon.c
void
vm_anon_init (void)
{
	/* TODO: Set up the swap_disk. */
	// 1. 스왑 디스크 설정
	swap_disk = disk_get(1, 1);

	// 2. 스왑 테이블 초기화
	list_init(&swap_table);

	// 3. 스왑 테이블 락 초기화
	lock_init(&swap_table_lock);

	// swap_disk 크기만큼 slot을 만들어서 swap_table에 넣어둔다.
	// 1 slot에 1 page를 담을 수 있는 slot 개수 구하기
	// : **1** sector = 512bytes, **1** page = 4096bytes -> **1** slot = **8** sector

	// 스왑 슬룻 생성 및 초기화
	disk_sector_t swap_size = disk_size(swap_disk) / 8;

	// 각 슬룻은 **8개**의 섹터 사용(각 섹터는 512 바이트, 한 슬룻은 4096 바이트)
	for (disk_sector_t i = 0; i < swap_size; i++)
	{
		struct slot *slot = (struct slot *)malloc(sizeof(struct slot));
		slot->page = NULL;
		slot->slot_no = i;
 
		lock_acquire(&swap_table_lock);
		list_push_back(&swap_table, &slot->swap_elem);
		lock_release(&swap_table_lock);
	}
	
}

anon_initializer

페이지를 익명 페이지로 초기화

코드

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	// 1. 페이지 작업 구조체 설정
	page->operations = &anon_ops;

	// 2. 익명 페이지 구조체 가져오기
	struct anon_page *anon_page = &page->anon;

	// 3. 슬룻 번호 초기화
	anon_page->slot_no = -1; // 초기화 함수가 호출되는 시점은 page가 매핑된 상태이므로 swap_slot을 차지x
	return true;
}

anon_swap_in

스왑 디스크에서 페이지를 읽어와 메모리에 로드

• 이 함수들을 작동하여 익명 페이지의 스왑 인/스왑 아웃 및 제거 처리.

• 스왑 공간을 효율적 관리 + 페이지 폴트가 발생시 필요한 데이터를 디스크 → 메모리로 가져옴

코드

// vm/anon.c
static bool
anon_swap_in (struct page *page, void *kva)
{
	struct anon_page *anon_page = &page->anon;
	
	// 1. 스왑 슬룻 번호 가져오기
	disk_sector_t page_slot_no = anon_page->slot_no; // page가 저장된 slot_no
	
	struct list_elem *e;
	struct slot *slot;

	lock_acquire(&swap_table_lock);

	// 2. 스왑 슬룻 검색
	for (e = list_begin(&swap_table); e != list_end(&swap_table); e = list_next(e))
	{
		slot = list_entry(e, struct slot, swap_elem);

		// 2. `slot_no`를 가진 슬룻을 찾기
		if(slot->slot_no == page_slot_no) 
		{
			// 3 페이지가 저장된 슬룻을 찾으면, 8개의 섹터를 읽어와 메모리에 로드
			for (int i = 0; i < 8; i++)
			{
				// 디스크, 읽을 섹터 번호, 담을 주소(512bytes씩 읽는다. disk 관련은 동기화 처리가 되어 있어서 lock 불필요)
				disk_read(swap_disk, page_slot_no * 8 + i, kva + DISK_SECTOR_SIZE * i);
			}

			// 4. 슬룻 업데이트
			slot->page = NULL; // 빈 slot으로 업데이트.
			anon_page->slot_no = -1; // 이제는 이 page는 swap_slot을 차지하지 않는다.

			// 5. 락 해제 및 반환
			lock_release(&swap_table_lock);
			return true;
		}
	}

	// 5. 락 해제 및 반환
	lock_release(&swap_table_lock);
	return false;
}

anon_swap_out

익명 페이지 -> 스왑 디스크에 저장.

코드

// vm/anon.c
static bool
anon_swap_out (struct page *page)
{

	// 1. 유효성 검사
	if (page == NULL)
	{
		return false;
	}
	
	struct anon_page *anon_page = &page->anon;
	struct list_elem *e;
	struct slot *slot;

	lock_acquire(&swap_table_lock);

	// 2. 스왑 테이블을 **순회**하며 **빈 슬룻**을 찾는다.
	for (e = list_begin(&swap_table); e != list_end(&swap_table); e = list_next(e))
	{

		slot = list_entry(e, struct slot, swap_elem);
		if (slot->page == **NULL**)
		{
			
			// 3. 빈 슬룻을 찾으면, 페이지를 **8개의 섹터**에 나눠 스왑 디스크에 저장.
			for (int i = 0; i < 8; i++)
			{
				disk_write(swap_disk, slot->slot_no * 8 + i, page->va + DISK_SECTOR_SIZE * i);
			}

			// 4. 슬룻 업데이트
			anon_page->slot_no = slot->slot_no; // page의 `slot_no`를 저장.
			slot->page = page; // 페이지 필드 업데이트

			// 5. page and frame의 연결을 끊는다.

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

			// 6. 락 해제 및 반환
			pml4_clear_page(thread_current()->pml4, page->va);
			lock_release(&swap_table_lock);
			return true;

		}
	}

	lock_release(&swap_table_lock);
	PANIC("insufficient swap space"); // 디스크에 더 이상 빈 슬룻이 없는 경우
}

anon_destroy

익명 페이지를 destroy.

• PAGE는 호출자에 의해 해제될 것이다. 주로 익명 페이지가 더 이상 필요하지 않게 되었을 때 호출됌.

코드

static void
anon_destroy (struct page *page) {

	// 1. 익명 페이지 접근
	struct anon_page *anon_page = &page->anon;

	// anonymous page에 의해 유지되던 리소스 해제.
	// page_struct를 명시적으로 해제할 필요는 없으며, 호출자가 이를 수정해야 한다.
	struct list_elem *e;
	struct slot *slot;

	// 3. 스왑 테이블 잠금 흭득
	lock_acquire(&swap_table_lock);

	// 4. 스왑 테이블에서 **슬룻** 찾기
	for (e = list_begin(&swap_table); e != list_end(&swap_table); e = list_next(e))
	{
		slot = list_entry(e, struct slot, swap_elem);

		// 각 슬룻의 'slot_no'가 익명 페이지의 'slot_no'와 **일치**하는지 확인
		if (slot->slot_no == anon_page->slot_no)
		{
			slot->page = NULL; // 해당 슬룻의 'page' 필드를 NULL로 설정하여 슬룻이 더 이상 사용되지 않음을 나타낸다.
			break;
		}
	}

	// 5. 스왑 테이블 잠금 해제
	lock_release(&swap_table_lock);
}

File-Mapped Page(매핑o)

file_backed_swap_in , file_backed_swap_out 구현

file_backed_swap_in

파일에서 내용을 읽어와 페이지를 스왑 인. 'lazy_load_segment' 함수를 호출하여 페이지의 내용을 파일에서 읽음

• 파일 시스템과 동기화.

코드

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

file_backed_swap_out

페이지의 내용을 파일에 다시 기록 + 페이지 and 프레임의 연결을 끊기

• 더럽지 않으면 파일의 내용을 수정x
• 페이지를 교체한 후에는 페이지의 더티 비트를 꺼야 한다.

코드

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

	// 1. 페이지가 수정된 경우, **내용**을 파일(디스크)에 기록
	if (pml4_is_dirty(thread_current()->pml4, page->va))
	{
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs ); // 페이지의 내용을 파일에 기록
		pml4_set_dirty(thread_current()->pml4, page->va, 0); // 페이지의 수정 플래그 초기화
	}

	// 2. 페이지와 프레임의 **연결 끊기** - 이는 페이지가 더 이상 해당 프레임 사용x
	page->frame->page = NULL;
	page->frame = NULL;

	// 3. 페이지 테이블에서 페이지 제거
	pml4_clear_page(thread_current()->pml4, page->va);
	return true;
}

file_backed_destroy

파일로 백업된 페이지 파괴. 페이지를 메모리에서 해제 and 페이지가 수정된 경우 해당 내용을 파일에 다시 기록.

코드

static void
file_backed_destroy (struct page *page)
{
	// 1. 'file_page' 구조체 가져오기
	struct file_page *file_page UNUSED = &page->file;

	// 2. 페이지가 수정되었는지 확인
	if (pml4_is_dirty(thread_current()->pml4, page->va))
	{
		// 3. 페이지가 수정('dirty 상태인 경우')된 경우 파일에 쓰기
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, 0); // 페이지의 'dirty' 상태 해제
	}

	// 4. 페이지를 페이지 테이블에서 제거
	pml4_clear_page(thread_current()->pml4, page->va);
}

Victim, Frame

vm_get_victim , vm_evict_frame , vm_get_frame 구현

Second Chance 알고리즘

(원형 큐) 구조를 사용하여 페이지 프레임을 관리.

원형 큐의 각 위치는 프레임을 나타내며, 프레임마다 참조 비트가 있다. 알고리즘은 포인터를 사용하여 현재 프레임 가리킨다.

Dirty Bit

vm_get_victim

페이지 교체 알고리즘에 따라 희생할 프레임을 선택하는 역할. 접근 비트를 이용한 Second Chance 알고리즘 사용

코드

static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	 /* TODO: The policy for eviction is up to you. */

	// 현재 실행 중인 스레드 가져옴.
	struct thread *curr = thread_current();

	// 1. 프레임 테이블 접근을 보호하기 위해 락을 흭득
	lock_acquire(&frame_table_lock);

	struct list_elem *start = list_begin(&frame_table);

	// 2. 프레임 테이블을 순회하며 희생할 프레임을 찾음.
	for (start; start != list_end(&frame_table); start = list_next(start))
	{
		// 3. 프레임 선택 
		victim = list_entry(start, struct frame, frame_elem);

		// 4. 할당되지 않은 프레임 확인.
		if (victim->page == NULL)
		{
			lock_release(&frame_table_lock);
			return victim; // 프레임이 할당되지 않은 경우, 해당 프레임을 바로 반환
		}

		// 5. 접근 비트 확인
		if (pml4_is_accessed(curr->pml4, victim->page->va))
		{
			// 6. 접근 비트 초기화
			pml4_set_accessed(curr->pml4, victim->page->va, 0);
		}
		
		// 7. 접근되지 않은 프레임 선택
		else
		{
			// 8. 락 해제 or 반환
			lock_release(&frame_table_lock);
			return victim;
		}

	}
	lock_release(&frame_table_lock);
	return victim;
}

vm_evict_frame

가상 메모리 시스템에서 페이지 교체. 메모리 > 디스크로 내보내느 과정. 새로운 페이지를 메모리에 불러올 때 사용. 희생 프레임 선택 > 선택된 프레임을 스왑 아웃 후 > 반환.

코드

static struct frame *
vm_evict_frame (void) {

	// 1. 희생 프레임 선택(페이지 교체 정책에 따라 프레임 선택)
	struct frame *victim = vm_get_victim();
	/* TODO: swap out the victim and return the evicted frame. */

	// 2. 희생 프레임의 페이지가 존재하는 경우
	if (victim->page)
	{
		swap_out(victim->page); // 스왑아웃
	}

	// 3. 희생 프레임 반환 - 이제 물리 메모리에서 해제된 상태이므로, 새로운 페이지를 이 프레임에 매핑할 수 있다.
	return victim;

}

vm_get_frame - 수정

페이지 할당 실패 처리가 NULL이었는데 > 페이지 교체 알고리즘을 사용하여 희생 프레임을 선택 and 반환.

코드

// 3. 페이지 할당 실패 처리
	if(kva == NULL)
	{
		struct frame *victim = vm_evict_frame();
		victim->page = NULL;
		return victim;
	}