[pintos] Week4~5: Virtual Memory - Part.6 Swap In/Out

이제 남은 구현은 Swap In/Out 이 남았다. 메모리 스와핑은 물리 메모리의 활용을 극대화하기 위한 메모리 회수기법이다. 메인 메모리의 프레임들이 모두 할당되면 시스템은 유저 프로그램이 요청하는 메모리 할당 요청을 더 이상 처리할 수 없다. 이에 대한 해결 방법은 현재 사용되지 않고 있는 메모리 프레임들을 디스크로 스왑 아웃 하는 것이다. 이는 일부 메모리 자원들을 해제시켜서 다른 애플리케이션들이 이 자원들을 사용할 수 있게 해 준다.

메모리는 고갈되었는데 메모리 할당 요청을 받았다는 것을 운영체제가 감지하면 swap 디스크로 퇴서(evict)시킬 페이지를 골라낸다. 그리고 메모리 프레임의 상태를 동일하게 디스크에 복사해 둔다.(스왑 아웃), 프로세스가 스왑 아웃된 페이지에 접근하려고 할 때, 운영체제는 디스크에 복사해둔 내용을 그대로 다시 메모리에 가져옴으로써 페이지를 다시 복원시킨다.

---

스왑 디스크란?

스왑 디스크(Swap Disk) 또는 스왑 공간(Swap Space)은 운영체제가 메인 메모리(RAM)가 부족할 때 임시로 데이터를 저장하는 디스크 공간을 말한다. 

Pintos에서의 스왑 디스크

• 스왑 공간은 일반적으로 블록 장치(block device)로서 관리된다.
• pintos에서는 devices/block.h 를 통해 스왑 장치(swap_block)를 초기화하고, 페이지 단위로 블록에 쓰고 읽는 코드를 구현한다.
• bitmap 자료구조를 활용하여 어떤 스왑 슬롯이 비어 있는지 추적한다.

---

anon.c 구현

• vm/anon.c

#include "devices/disk.h"
#include "kernel/bitmap.h"


struct bitmap *swap_table;
struct lock bitmap_lock;

• bitmap은 스왑 공간을 추적하는 전역 비트다.
• swap_table 접근 시 동기화를 위한 락을 선언한다.

---

vm_anon_init 구현

• vm/anon.c

/* Initialize the data for anonymous pages */
void
vm_anon_init (void) {
	/* TODO: Set up the swap_disk. */
	swap_disk = disk_get(1,1);
	if (swap_disk == NULL){
		PANIC("No swap disk found!");
	}
	swap_table = bitmap_create(disk_size(swap_disk) / 8); 
	if (swap_table == NULL)
		PANIC("Failed to create swap bitmap!");
	lock_init(&bitmap_lock);
}

vm_anon_init 은 익명 페이지의 스왑 공간을 초기화하는 함수다.

swap_disk = disk_get(1,1);

• 스왑 디스크 장치를 가져온다.
• disk_get(CHANNEL, DEVICE)에서 (1, 1)은 보통 IDE 채널 1번의 슬레이브 디바이스를 의미한다.
• Pintos에서 이 위치는 보통 스왑 디스크로 예약되어 있다.
• 결과적으로 swap_disk는 이 디스크를 조작하는 데 사용하는 핸들이 된다.

swap_table = bitmap_create(disk_size(swap_disk) / 8);

• 스왑 디스크의 크기를 바탕으로 페이지 단위 비트맵을 생성한다.
• 디스크는 512바이트 sector 단위이므로:
  • 페이지 1개 = 4KB = 8 섹터
  • 전체 스왑 슬롯 개수 = disk_size(swap_disk) / 8
• 이 수만큼의 비트맵을 만들어, 각 스왑 슬롯이 사용 중인지 추적한다.

lock_init(&bitmap_lock);

• swap_table 접근 시 동시성을 보장하기 위해 락을 초기화한다.
• 여러 스레드가 동시에 swap 작업을 할 수 있으므로 필수다.

---

anon_initializer 수정

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	page->operations = &anon_ops;

	struct anon_page *anon_page = &page->anon;
	anon_page->swap_idx = BITMAP_ERROR;

	return true;
}

struct anon_page *anon_page = &page->anon;
anon_page->swap_idx = BITMAP_ERROR;

• page->anon은 이 페이지가 VM_ANON일 때 사용되는 union 구조체의 멤버이다.
• anon_page->swap_idx: 이 페이지가 스왑 아웃되었을 때 디스크의 어느 스왑 슬롯(index)에 저장됐는지를 기록하는 필드다.
• BITMAP_ERROR는 일반적으로 유효하지 않은 인덱스(-1)를 의미하며, 현재 이 페이지는 스왑 되지 않았음을 나타낸다.

---

anon_swap_out 구현

/* Swap out the page by writing contents to the swap disk. */
static bool
anon_swap_out (struct page *page) {
	struct anon_page *anon_page = &page->anon;

	lock_acquire(&bitmap_lock);
	size_t swap_idx = bitmap_scan_and_flip(swap_table, 0, 1, false);
	lock_release(&bitmap_lock);
	if (swap_idx == BITMAP_ERROR){
		return false;
	}
	anon_page->swap_idx = swap_idx;

	for (int i = 0; i < 8; i++){
		disk_write(swap_disk, swap_idx * 8 + i, page->frame->kva + DISK_SECTOR_SIZE * i);
	}

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

	pml4_clear_page(thread_current()->pml4, page->va);
	return true;
}

anon_swap_out 함수는 현재 메모리에 존재하는 익명 페이지를 스왑 디스크로 내보내는 작업을 수행한다. 이 함수는 페이지 교체가 필요할 때 호출되어 메모리 공간을 확보한다.

lock_acquire(&bitmap_lock);
size_t swap_idx = bitmap_scan_and_flip(swap_table, 0, 1, false);
lock_release(&bitmap_lock);

• bitmap_lock을 획득하여 swap_table에 동기적으로 접근한다.
• bitmap_scan_and_flip() 함수는 비어 있는(값이 false) 슬롯을 찾아 true로 설정하고 인덱스를 반환한다.
• 사용 가능한 스왑 슬롯이 없으면 BITMAP_ERROR를 반환한다.
• 락을 해제하고 다음 단계로 넘어간다.

if (swap_idx == BITMAP_ERROR){
	return false;
}
anon_page->swap_idx = swap_idx;

• 스왑 슬롯이 없는 경우에는 false를 반환하고 함수 실행을 중단한다.
• 스왑 슬롯을 정상적으로 얻었다면, 해당 페이지의 anon_page 구조체에 스왑 인덱스를 저장한다.

for (int i = 0; i < 8; i++){
	disk_write(swap_disk, swap_idx * 8 + i, page->frame->kva + DISK_SECTOR_SIZE * i);
}

• 1개의 페이지는 4KB이며, 디스크 섹터 크기는 512바이트이므로, 총 8개의 섹터로 구성된다.
• 루프를 통해 페이지 내용을 스왑 디스크의 해당 인덱스에 순차적으로 기록한다.
• 각 섹터의 위치는 swap_idx * 8 + i로 계산하며, 메모리 내 주소도 섹터 단위로 이동하며 쓴다.

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

• 페이지와 연결된 프레임 정보를 제거한다.
• 프레임이 다른 페이지와 연결되도록 준비시키거나, 해제 후 재사용 가능하게 만든다.

	pml4_clear_page(thread_current()->pml4, page->va);
	return true;
}

• 현재 스레드의 페이지 테이블에서 해당 페이지의 가상 주소 매핑을 제거한다.
• 이로써 해당 주소를 접근하면 page fault가 발생하게 되며, 다시 불러올 필요가 생긴다.

---

anon_swap_in 구현

/* Swap in the page by read contents from the swap disk. */
static bool
anon_swap_in (struct page *page, void *kva) {
	struct anon_page *anon_page = &page->anon;

	size_t swap_idx = anon_page->swap_idx;
	if (!bitmap_test(swap_table, swap_idx)) {
		return false;
	}
	if (swap_idx == BITMAP_ERROR) {
		PANIC("swap_in idx is crazy");
		return false;
	}

	for (int i = 0; i < 8; i++) {
		disk_read(swap_disk, swap_idx * 8 + i, kva + i * DISK_SECTOR_SIZE);
	}

	page->frame->kva = kva;

	lock_acquire(&bitmap_lock);
	bitmap_set(swap_table, swap_idx, false);
	lock_release(&bitmap_lock);

	return true;
}

anon_swap_in 함수는 이전에 디스크로 스왑 아웃되었던 익명 페이지를 스왑 디스크에서 다시 메모리로 불러오는 작업을 수행한다. 페이지 폴트가 발생했을 때 해당 페이지가 스왑에 저장되어 있었다면 이 함수가 호출되어 내용을 복원한다.

struct anon_page *anon_page = &page->anon;
size_t swap_idx = anon_page->swap_idx;

• anon_page를 통해 익명 페이지 내부 데이터를 참조한다.
• 이전에 anon_swap_out() 시 저장된 swap_idx 값을 읽는다.
• 이 인덱스는 이 페이지의 내용이 디스크 상의 어느 위치에 있는지를 나타낸다.

if (!bitmap_test(swap_table, swap_idx)) {
	return false;
}

• 해당 스왑 슬롯이 현재 사용 중인지 확인한다.
• 사용 중이 아니라면 잘못된 접근이므로 실패로 간주하고 false를 반환한다.

if (swap_idx == BITMAP_ERROR) {
	PANIC("swap_in idx is crazy");
	return false;
}

만약 스왑 인덱스가 BITMAP_ERROR (일반적으로 -1)인 경우, 이는 명백한 논리 오류이므로 즉시 커널 패닉을 발생시킨다.

for (int i = 0; i < 8; i++) {
	disk_read(swap_disk, swap_idx * 8 + i, kva + i * DISK_SECTOR_SIZE);
}

• 페이지 하나는 4KB이며, 디스크는 512바이트 섹터 단위로 읽기 때문에 8번 반복해서 읽는다.
• swap_idx * 8 + i는 디스크의 섹터 번호를 계산한 것.
• 읽어온 데이터를 kva에 순차적으로 저장한다.

page->frame->kva = kva;

• 페이지 구조체 내의 프레임 포인터에 현재 복원된 커널 가상 주소를 연결한다.
• 이 작업으로 페이지와 프레임이 다시 연결된다.

lock_acquire(&bitmap_lock);
bitmap_set(swap_table, swap_idx, false);
lock_release(&bitmap_lock);

• 스왑 슬롯을 더 이상 사용하지 않으므로, 비트맵에서 해당 인덱스를 false로 설정하여 해제한다.
• 동시 접근을 방지하기 위해 락을 사용한다.

---

anon_destory 구현

/* Destroy the anonymous page. PAGE will be freed by the caller. */
static void
anon_destroy (struct page *page) {
	struct anon_page *anon_page = &page->anon;
	
	// 스왑 테이블에서 스왑 인덱스 해제
	if (anon_page->swap_idx != BITMAP_ERROR) {
		lock_acquire(&bitmap_lock);
		bitmap_reset(swap_table, anon_page->swap_idx);
		lock_release(&bitmap_lock);
	}

	// 프레임이 존재하면 프레임을 리스트에서 제거하고 해제
	if (page->frame) {
		list_remove(&page->frame->elem);
		page->frame->page = NULL;
		palloc_free_page(page->frame->kva);
		free(page->frame);
		page->frame = NULL;
	}

	pml4_clear_page(thread_current()->pml4, page->va);

}

anon_destroy 함수는 익명 페이지를 메모리와 스왑에서 정리하는 작업을 수행한다. 이 함수는 페이지의 해제가 필요할 때 호출되며, 스왑 슬롯 반납과 프레임 메모리 헤제, 페이지 테이블 정리를 수행한다.

struct anon_page *anon_page = &page->anon;

if (anon_page->swap_idx != BITMAP_ERROR) {
	lock_acquire(&bitmap_lock);
	bitmap_reset(swap_table, anon_page->swap_idx);
	lock_release(&bitmap_lock);
}

• anon_swap_out()을 통해 스왑 디스크에 저장된 적이 있다면, swap_idx는 BITMAP_ERROR가 아닌 유효한 인덱스를 가진다.
• 이 경우 스왑 테이블에서 해당 인덱스를 false로 되돌려 해제한다.
• 동시 접근을 방지하기 위해 bitmap_lock을 사용한다.

if (page->frame) {
	list_remove(&page->frame->elem);
	page->frame->page = NULL;
	palloc_free_page(page->frame->kva);
	free(page->frame);
	page->frame = NULL;
}

• 페이지가 메모리에 존재하는 경우, 프레임이 연결되어 있다.
• 이 경우 다음을 수행한다:
  • 프레임을 프레임 테이블에서 제거한다 (list_remove)
  • 프레임과 페이지의 연결을 끊는다
  • 실제 페이지 데이터를 담고 있는 물리 페이지(kva)를 반환한다 (palloc_free_page)
  • 프레임 구조체 자체도 free()로 해제한다

pml4_clear_page(thread_current()->pml4, page->va);

• 해당 가상 주소가 현재 프로세스의 페이지 테이블에 남아 있다면 매핑을 제거한다.
• 이로써 더 이상 해당 주소로 접근 시 페이지 폴트가 발생한다.

---

file.c 구현

• vm/file.c

#include "vm/file.h"
#include "filesys/filesys.h"
#include "userprog/syscall.h"

헤더 파일을 추가한다.

---

file_backed_swap_out 구현

/* Swap out the page by writeback contents to the file. */
static bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;
	if (pml4_is_dirty(thread_current()->pml4, page->va) && page->writable) {
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, false);
	}
	page->frame->page = NULL;
	page->frame = NULL;
	pml4_clear_page(thread_current()->pml4, page->va);

	return true;
}

file_backed_swap_out 함수는 파일에 매핑된 페이지를 메모리에서 내보낼 때 호출되며, 필요시 페이지 내용을 원래 파일로 write-back(재기록)하는 역할을 한다. 즉, 파일과 연결된 페이지를 스왑 아웃할 때 해당 내용을 디스크의 파일에 반영하고 메모리 자원을 해제한다.

struct file_page *file_page UNUSED = &page->file;

• 페이지는 union 형태로 file_page 구조체를 포함한다.
• file_page 구조체에는 다음과 같은 정보가 담겨 있다:
  • 원래 읽어왔던 파일 포인터 (file_page->file)
  • 파일 내 오프셋 (file_page->ofs)
  • 읽은 바이트 수 (file_page->read_bytes)

if (pml4_is_dirty(thread_current()->pml4, page->va) && page->writable) {
	file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs);
	pml4_set_dirty(thread_current()->pml4, page->va, false);
}

• 해당 페이지가 dirty bit가 설정되어 있고, 쓰기 가능한 페이지일 경우,
• 즉, 메모리에서 페이지 내용이 수정되었고, 이를 파일에 반영할 수 있는 경우라면:
  1. file_write_at()을 사용해 페이지 내용을 원래 파일에 다시 씀(write-back)
     • 대상: file_page->file (원래 읽어온 파일)
     • 소스: page->va (페이지의 사용자 가상 주소)
     • 크기: file_page->read_bytes (파일에서 읽어온 원래 크기)
     • 오프셋: file_page->ofs (파일 내 오프셋 위치)
  2. 쓰기 후에는 해당 페이지의 dirty bit를 false로 초기화한다.

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

• 페이지와 프레임 구조체 간 연결을 끊는다.
• 이때 실제 프레임 구조체나 물리 메모리를 free하지는 않으며, 프레임 테이블이나 외부에서 처리한다는 전제이다.

pml4_clear_page(thread_current()->pml4, page->va);

• 현재 스레드의 페이지 테이블에서 이 가상 주소에 대한 매핑을 제거한다.
• 이후 이 주소에 접근하면 페이지 폴트가 발생한다.

---

file_backed_swap_in 구현

/* Swap in the page by read contents from the file. */
static bool
file_backed_swap_in (struct page *page, void *kva) {
	struct file_page *file_page UNUSED = &page->file;
	file_read_at (file_page->file, kva, file_page->read_bytes, file_page->ofs);
	return true;
}

file_backed_swap_in 함수는 파일 매핑 페이지가 페이지 폴트 등으로 메모리에 다시 올라올 때 해당 내용을 파일로부터 읽어와 메모리에 복원하는 역할을 한다.

struct file_page *file_page UNUSED = &page->file;

• page 구조체 내부의 file_page를 통해 이 페이지가 매핑된 파일 정보에 접근한다.
• file_page 구조체에는 다음이 포함된다:
  • file_page->file: 페이지가 매핑된 파일 포인터
  • file_page->ofs: 파일 내에서 읽기 시작할 오프셋
  • file_page->read_bytes: 읽을 바이트 수 (일반적으로 최대 한 페이지 크기)

file_read_at (file_page->file, kva, file_page->read_bytes, file_page->ofs);

• 파일에서 read_bytes만큼 데이터를 읽어 kva 주소에 저장한다.
• file_read_at()은:
  • file: 읽을 파일 핸들
  • kva: 읽은 데이터를 저장할 메모리 위치
  • read_bytes: 읽을 길이
  • ofs: 파일 내 오프셋 위치를 의미한다.
• 이로써 페이지의 내용이 파일로부터 복원된다.

---

file_backed_destroy 구현

/* Destory the file backed page. PAGE will be freed by the caller. */
static void
file_backed_destroy (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;
	// TODO: 해당 페이지가 dirty 상태인지 확인
    // - pml4_is_dirty() 또는 page->frame->is_dirty 사용
	if (pml4_is_dirty(thread_current()->pml4, page->va) && page->writable){
		// TODO: dirty라면, 파일에 해당 내용을 file_write_at()으로 저장
		// - page->va, aux->file, aux->offset 등에서 정보 추출
		// - writable 여부도 확인
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, 0);
	}
	hash_delete(&thread_current()->spt.pages, &page->hash_elem);
	if (page->frame) {
		list_remove(&page->frame->elem);
		page->frame->page = NULL;
		page->frame = NULL;
		free(page->frame);
	}

	pml4_clear_page(thread_current()->pml4, page->va);
}

file_backed_destroy는 파일에 매핑된 페이지를 삭제할 때 호출된다. 이 함수는 페이지의 메모리와 매핑을 해제하고, 필요한 경우 페이지 내용을 파일에 write-back(재기록) 한다.

struct file_page *file_page UNUSED = &page->file;

• page 내부의 file_page 구조체를 참조하여 파일 정보, 오프셋, 읽은 바이트 수 등을 가져온다.

if (pml4_is_dirty(thread_current()->pml4, page->va) && page->writable){

• 현재 페이지가 dirty 상태인지 확인한다:
  • 페이지가 수정되었고(dirty),
  • 쓰기 가능한(writable) 페이지일 때만 파일에 다시 쓴다.
• pml4_is_dirty()는 페이지 테이블의 dirty bit를 확인한다.

file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs);
pml4_set_dirty(thread_current()->pml4, page->va, 0);

• 페이지 내용을 해당 파일에 재기록(write-back) 한다:
  • file_page->file: 기록 대상 파일
  • page->va: 현재 페이지의 가상 주소 (데이터 소스)
  • read_bytes: 원래 읽어온 바이트 수 (이만큼만 저장)
  • ofs: 파일 내 오프셋
• write-back 후 dirty 비트를 클리어한다.

hash_delete(&thread_current()->spt.pages, &page->hash_elem);

• 현재 프로세스의 supplemental page table(SPT)에서 이 페이지를 제거한다.
• 해시 테이블에서 더 이상 이 페이지를 찾을 수 없게 된다.

if (page->frame) {
	list_remove(&page->frame->elem);
	page->frame->page = NULL;
	page->frame = NULL;
	free(page->frame);
}

• 페이지가 메모리에 존재하면, 연결된 프레임을 정리한다:
  • 프레임 리스트에서 제거
  • 페이지와 프레임 간 연결 해제
  • 프레임 구조체 메모리를 free()로 해제

pml4_clear_page(thread_current()->pml4, page->va);

• 프로세스의 페이지 테이블에서 이 가상 주소의 매핑을 제거한다.
• 이 주소는 더 이상 유효하지 않으며, 접근 시 page fault가 발생한다.

---

spt_remove_page 수정

void
spt_remove_page (struct supplemental_page_table *spt, struct page *page) 
{
	hash_delete(&spt->pages, &page->hash_elem);
	vm_dealloc_page(page);
	return true;
}

기존 함수에 hash_delete() 함수를 포함한다. SPT에서 페이지를 제거한다. 즉 해당 페이지를 프로세스의 보조 테이블에서 더 이상 참조하지 않도록 만들기 위한 작업이다.