[PintOS - VM] Swap In/Out

 

Swap In/Out

 

• 메모리 스왑은 물리 메모리 사용을 최적화하기 위함!
  • 메인 메모리의 frame (USER POOL)이 모두 할당되면, 추가 메모리 할당 요청을 처리할 수 없음
  • 해결책 : 사용되지 않는 메모리 frame을 disk로 swap_out 하여 다른 응용 프로그램이 사용할 수 있도록 메모리 자원을 확보
• 스왑 작업은 운영 체제에서 수행
  • 시스템이 메모리가 부족할 때 메모리 할당 요청을 받으면 페이지를 선택하여 스왑 디스크로 내보냄
  • 메모리 프레임의 정확한 상태를 디스크에 복사
  • 프로세스가 스왑 아웃된 페이지에 접근하려고 하면 운영 체제가 페이지를 메모리로 복원
• 익명 페이지와 파일 기반 페이지의 스왑 처리
  • Anon page 는 백업 스토리지가 없음, 임시 백업 스토리지로 swap_disk 사용
  • File-backed-page 는 매핑된 파일을 백업 스토리지로 사용
• 익명 페이지 스왑 작업
  • vm_anon_init과 anon_initializer 수정
    • vm_anon_init: Swap_disk 를 위한 Data Structure 필요! (bitmap을 활용)
    • anon_initializer: 익명 페이지에 스왑 지원 정보 추가 (swap_index)
  • anon_swap_in과 anon_swap_out 구현
    • anon_swap_out: 페이지 데이터를 스왑 디스크로 복사, 스왑 슬롯 정보 페이지 구조체에 저장
    • anon_swap_in: 스왑 디스크에서 데이터를 읽어 메모리로 복원, 스왑 테이블 업데이트
• 파일 매핑된 페이지 스왑 작업
  • file_backed_swap_in과 file_backed_swap_out 구현
    • file_backed_swap_out: 페이지 데이터를 파일에 씀, 페이지가 더럽지 않으면 파일 내용 수정 불필요
    • file_backed_swap_in: 파일에서 데이터를 읽어 메모리로 복원, 파일 시스템과 동기화 필요

 

 

 

 

Anonymous Page

 

vm_anon_init

/* Initialize the data for anonymous pages */
void
vm_anon_init (void) {
	/* TODO: Set up the swap_disk. */
	swap_disk = disk_get(1,1); /* Pintos uses disks this way: 1:1 - swap */ 
	size_t swap_size = disk_size(swap_disk);
	size_t swap_slots = swap_size / (PGSIZE / DISK_SECTOR_SIZE); 
    swap_bitmap = bitmap_create(swap_slots);
	bitmap_set_all(swap_bitmap,false);
}

 

 

swap_slots

디스크 섹터와 페이지의 관계

1. 디스크 섹터(DISK_SECTOR_SIZE):
   • 디스크의 물리적인 최소 저장 단위입니다.
   • 보통 크기는 512 바이트입니다. 
   • 추후, AF(Advanced Format) 4KB 섹터로 확장되었습니다.
2. 페이지(PGSIZE):
   • 메모리 관리의 논리적인 최소 단위입니다.
   • 보통 크기는 4KB(4096 바이트)입니다.

스왑과 페이지

운영체제는 메모리를 페이지 단위로 관리합니다. 즉, 메모리의 할당과 해제, 그리고 스왑 작업도 페이지 단위로 이루어집니다.

anon_swap_in의 매개변수를 보면 page로 들어오는 것을 알 수 있다.

 

그러나!!

 

디스크 자체는 섹터 단위로 관리가 됩니다.

디스크는 섹터 단위로 관리되기 때문에, 한 페이지가 몇 개의 섹터로 이루어지는지를 계산하여 스왑 디스크를 페이지 단위로 나누어야 합니다. 

 

그렇기 때문에 비트맵을 생성할 때, 단순히 disk_size를 페이지로 나눈 것이 아니라, 섹터 단위로 나누어서 생성합니다.

짤막 정리😼

• swap_size: 스왑 디스크의 전체 크기 (바이트 단위).
• PGSIZE: 한 페이지의 크기 (보통 4096 바이트).
• DISK_SECTOR_SIZE: 디스크 섹터의 크기 (보통 512 바이트).
• 한 페이지를 저장하는 데 필요한 디스크 섹터 수: 4096/512 = 8

 

Swap_bitmap = bitmap_create(swap_slots);

결과적으로, swap_bitmap은 위와 같이 swap_slots의 크기로 생성합니다!

 

 

 

anon_initializer

/* Initialize the file mapping */
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_index = BITMAP_ERROR;
	return true;
}

 

swap_index를 초기화 합니다. 새로운 구조체 속성이니 헤더파일에서 swap_index 속성을 추가 해야합니다!

 

 

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;
    size_t swap_index = bitmap_scan_and_flip(swap_bitmap, 0, 1, false);
	if (swap_index != BITMAP_ERROR) {
        for (size_t i = 0; i < (PGSIZE / DISK_SECTOR_SIZE); i++) {
            disk_write(swap_disk, swap_index * (PGSIZE / DISK_SECTOR_SIZE) + i, 
            page->va + (i * DISK_SECTOR_SIZE));            
        }
		anon_page->swap_index = swap_index;
		pml4_clear_page(thread_current()->pml4,page->va);
		return true;
	}
	return false;
}

 

 

bitmap_scan_and_flip()

/* Finds the first group of CNT consecutive bits in B at or after
   START that are all set to VALUE, flips them all to !VALUE,
   and returns the index of the first bit in the group.
   If there is no such group, returns BITMAP_ERROR.
   If CNT is zero, returns 0.
   Bits are set atomically, but testing bits is not atomic with
   setting them. */
size_t
bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)

 

주석과 매개변수만을 봐도 함수가 어떻게 동작하는지 유추할 수 있다.

 

1. 비트맵에서
2. 0의 인덱스에서 시작해서
3. CNT의 수만큼 연속적인 Index 를 찾아서 반환합니다
4. cnt가 zero면 0을, 조건에 맞는 그룹을 못찾으면 error를 반환합니다.

따라서, 해당 함수로 가용한 비트맵 공간을 찾을 수 있다.

 

 

그런데 함수 주석의 마지막을 보면 "atomically" 란 말이 나온다. 

asm ("lock ..... 중략 ..")

 

이미 인스트럭션단에서 동기화가 보장됨을 알 수 있다! 따라서 귀찮은 락 설정이 필요 없다는 것이다! 😁

 

1. 원자성(Atomicity): 비트맵 조작이 원자적으로 실행된다는 것을 의미합니다. 원자성은 여러 스레드 또는 프로세스가 동시에 비트맵에 접근할 때 일관성을 유지하기 위해 필요합니다. 이러한 조작이 원자적으로 수행되면 여러 스레드가 동시에 비트맵을 수정해도 올바른 결과를 보장할 수 있습니다.
2. 동기화(Synchronization): "atomically"라는 용어는 또한 비트맵 조작이 동기화되어 다른 스레드와의 동시성 문제를 다루지 않아도 된다는 것을 나타낼 수 있습니다. 즉, 이 코드에서는 "atomically"를 사용하여 동시성 문제를 해결하지 않아도 된다는 것을 나타낼 수 있습니다.

 

disk_write ()

/* Write sector SEC_NO to disk D from BUFFER, which must contain
   DISK_SECTOR_SIZE bytes.  Returns after the disk has
   acknowledged receiving the data.
   Internally synchronizes accesses to disks, so external
   per-disk locking is unneeded. */
void
disk_write (struct disk *d, disk_sector_t sec_no, const void *buffer) {

 

1. buffer 에 있는 데이터를
2. disk의 SEC_NO  위치에
3. DISK_SECTOR_SIZE bytes 크기만큼 write 

위에서 언급했던 것 처럼, disk_write의 작업 단위 자체가 DISK_SECTOR_SIZE 로 수행되고있다!

 

 

 

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_index = anon_page->swap_index;
	if (bitmap_test(swap_bitmap,swap_index)) {
    	for (size_t i = 0; i < (PGSIZE / DISK_SECTOR_SIZE); i++) {
        	disk_read(swap_disk, swap_index * (PGSIZE / DISK_SECTOR_SIZE) + i, 
        	kva + (i * DISK_SECTOR_SIZE));
    	}
		bitmap_set(swap_bitmap,swap_index,false);
		return true;
	}
	return false;
}

 

swap_in은 swap_out과 반대로 읽기 작업을 통해 disk에 있던 내용을 frame에 옮겨주는 것이 전부이다!

 

 

Filed-Mapped Page

 

 

file_backed_swap_out

/* Swap out the page by writeback contents to the file. */
bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page = &page->file;
	struct thread *cur = thread_current();
	if(pml4_is_dirty(cur->pml4, page->va)) {
		file_seek(file_page->file, file_page->ofs);
		/* Writes SIZE bytes from BUFFER into FILE   kva -> file (진짜 디스크에 있는 파일)   */
		/* 따라서, 물리 메모리에 있는 정보를 파일에 쓰는 작업을 수행함.*/
		if (file_write(file_page->file, page->frame->kva, file_page->read_bytes) != (int) file_page->read_bytes) {
			return false;
		}
        	pml4_set_dirty(cur->pml4, page->va, 0);
	}
	pml4_clear_page(cur->pml4, page->va);
	return true;
}

 

file_backed의 경우, 이미 디스크에 존재하는 파일이 있기 때문에 swap_disk가 필요하지 않다!

 

변경사항이 있다면 file에 수정 사항을 반영하고, set_drity를 초기화 한 뒤 리턴해준다.

 

 

 

 

 

 

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 = &page->file;

	file_seek(file_page->file, file_page->ofs);

	if (file_read(file_page->file, kva, file_page->read_bytes) != (int) file_page->read_bytes ) {
		return false;
	}

	memset(kva+file_page->read_bytes, 0, file_page->zero_bytes);

	return true;
}

 

page에 있던 file에 대한 정보를 통해, frame에 읽기 작업을 시도하는 것이 전부이다.

 

 

 

swap_in , swap_out을 모두 작성하였다.

 

그러나 아직, swap_out을 호출하기 위한 준비가 완벽하게 되지는 않았다!

 

Evict

 

vm_get_frame()

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
static struct frame *
vm_get_frame (void) {
	struct frame *frame = (struct frame *)malloc(sizeof(struct frame));;
	/* TODO: Fill this function. */
	frame->kva = palloc_get_page(PAL_USER);

	if(frame->kva == NULL) {
		frame = vm_evict_frame();
		frame->page = NULL;
		return frame;
	}
	frame->page = NULL; // ASSERT (frame->page == NULL); 가 있으므로, NULL로 초기화 해줍시다!
	list_push_back(&frame_list,&frame->frame_elem);
	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	return frame;
}

 

 

USER_POOL 에서 프레임을 할당받지 못하면, frame에서 추방할 녀석을 선정하여야 한다. 이에 따라 추방할 victim을 골라보자!

 

vm_init()

void
vm_init (void) {
	vm_anon_init ();
	vm_file_init ();
#ifdef EFILESYS  /* For project 4 */
	pagecache_init ();
#endif
	register_inspect_intr ();
	/* DO NOT MODIFY UPPER LINES. */
	/* TODO: Your code goes here. */
	list_init(&frame_list);
	clock_ptr = list_begin(&frame_list); // clock 알고리즘을 위한 초기화!
}

 

위와 같이,  clock_ptr를 init 해주고.

 

vm_get_victim()

 

/* Get the struct frame, that will be evicted. */
static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	 /* TODO: The policy for eviction is up to you. */
	// for문 돌면서 추방할녀석 선정하기
	struct thread *cur = thread_current();

    while (true) {
        if (clock_ptr == list_end(&frame_list)) {
            clock_ptr = list_begin(&frame_list);
        }

        victim = list_entry(clock_ptr, struct frame, frame_elem);

        if (victim->page == NULL) {
            return victim;
        }

        if (pml4_is_accessed(cur->pml4, victim->page->va)) {
            pml4_set_accessed(cur->pml4, victim->page->va, 0);
            clock_ptr = list_next(clock_ptr);
        } else {
			// 추방!!
            struct list_elem *next = list_next(clock_ptr);
            if (next == list_end(&frame_list)) {
                next = list_begin(&frame_list);
            }
            clock_ptr = next;
            return victim;
        }
    }
	return victim;
}

 

마치 시계를 돌듯, (Malloc의 next fit과 비슷해보인다) 선형 리스트를 탐색하며 마지막에 도달하면 포인터를 리스트의 첫 번째 로 이동시키며 victim을 선정한다.