(2022.03.11) Swap In/Out 가이드라인

구현은 어디가고 다른 챕터 가이드라인이냐고 할 수 있다. 맞다. 사실 구현 포스팅을 작성하기 위해 열심히 코드를 조지고 있었다. 근데 작성을 하면서 수정을 하던 도중, VM_FILE을 destroy하는 상황에 사용하는 file_backed_destroy 함수를 구현하게 되었다. 

 

해당 함수가 해야 하는 역할은 현재 VM_FILE의 dirty bit가 켜져있으면, 해당 내용을 원래 파일에 작성 (write_back)을 하고, 그 페이지에서 보유하고 있는 자원을 해소하는 것이었다. 그런데, 중요한 것은 이 write_back 역할을 하는 함수가 있다는 것이다. 바로 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 = &page->file;

	...
}

결국 해당 함수 또한 evict되는 프레임을 write_back할 때 사용이 되어야 하는 것이기에 기능이 겹친다. 이걸 따로따로 구현을 하느니 차라리 한 번에 구현하는 것이 좋겠다 싶었고, 더 나아가 그 지긋지긋한 swap in/out을 가져와서 구현하는 것이 좋겠다는 생각이었다. 때문에 오늘 매뉴얼까지 살펴보고, 전부 구현하도록 한다.

 

swap in/out은 메모리의 크기는 한계가 있어, disk에 현재 올라가 있는 프레임을 잠시 저장했다가 필요할 때 다시 메모리로 불러와 활용할 수 있도록 하는 기법이다. VM_ANON의 경우에는 disk의 일부 공간을 차지하는 swap_disk에, VM_FILE은 각 프레임이 기원한 파일에 해당 프레임의 내용을 저장한다. 더 이상 할당할 프레임이 남아있지 않아 현재 메모리에 있는 프레임 중 하나를 evict할 때 swap out이 사용된다. 프레임을 할당해 줄 필요성이 있었던 페이지가 이전에 evict되어 프레임의 내용이 disk에 있는 경우, 그 내용을 불러오기 위해 swap_in이 사용된다.

 

여러 함수를 뜯어 고쳐야 한다. 

 

• evict될 프레임을 선택하는 알고리즘
• evict될 프레임이 결정된 후, 해당 프레임을 소유하던 thread에 통보 및 후처리
• swap_out 후 해당 정보를 페이지에 저장
• swap_in 후 필요 없어진 자원 정리
• ...

위에 보이는 사항들을 보면 생각할 것이 굉장히 많다.

 

eviction 알고리즘은 이전에 정한대로 one hand clock 또는 two hand clock으로 구현할 것이다. 이를 위해 우리는 지금까지 미뤄놨던 frame table을 구현해야 한다. 사실 이것도 어느 방식으로 구현할 지 물 밑으로 많이 고민했다. 그 중에서 가장 그럴듯한 것은 array 방식과 bitmap을 섞어서 쓰는 것이다. (드디어 마지막 자료구조까지 쓰는구나) struct frame의 array에 내용을 저장하고, 할당되었지의 여부는 bitmap으로 표기한다. 아니, 왜 다른 좋은 자료구조 다 납두고 기본적인 array냐고 물을 수 있는데, 이는 다음의 이유 때문이다. 

 

우선 one hand clock이든, two hand clock이든 struct frame이 중간에 해제가 되어버리면 애매한 경우가 많이 발생한다. 따라서, 굳이 해제가 용이한 list로 할 필요가 없다. 또한 해당 알고리즘에는 일관적인 순회가 필수적이기 때문에 rehash로 순회순서가 계속 바뀔 수 있는 hash도 사용할 수 없다. 그러면 가장 간단한 구조인 array가 남는다. 다만, array만으로는 할당되지 않은 struct frame을 표현하기에는 번거롭기에, 이를 pintos에서 제공한 나머지 자료구조인 bitmap으로서 보완하는 것이다. 이를 종합하면 대략적인 frame table의 자료구조는 다음과 같을 것이다.

struct frame_table {
	struct bitmap *alloc_checker;
	struct frame *frames; /* array of frames -> have to be initialized */
};

여기다가 광역 자원인 frame table의 특성을 생각하여 lock만 추가하면 기능상으로 문제는 없어보인다.

 

---

 

겸사겸사 bitmap의 사용법도 알아보자.

struct bitmap * bitmap_create (size_t bit_cnt);

BIT_CNT 만큼의 bit를 갖도록 bitmap을 생성한다. 각 bit에는 

void bitmap_set (struct bitmap *b, size_t idx, bool value);
void bitmap_mark (struct bitmap *b, size_t bit_idx);
void bitmap_reset (struct bitmap *b, size_t bit_idx);

를 통해 접근해서 값을 변경할 수 있다. 각 bit에 해당하는 값을 보는 방법은

bool bitmap_test (const struct bitmap *b, size_t idx);

이다. 이 외에도, 현재의 bit값을 not 시킨 값을 저장할 수 있는

void bitmap_flip (struct bitmap *b, size_t bit_idx);

이라거나, START부터 탐색을 시작해 CNT만큼 연속되는 VALUE 값을 갖는 bitmap의 부분의 시작 인덱스를 반환해주는

size_t bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value);

이 편의기능으로 제공된다.

 

특히 마지막의 bitmap_scan과, bit를 뒤집는 함수를 결합한 다음의 함수

size_t bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value);

를 많이 사용하게 될 것이다.

 

---

 

다음으로 중요한 문제는 evict 할 프레임에 연동된 페이지가 어느 thread에 속해있는가이다. 현재 방식으로는 frame에서 thread로 연결되는 방법이 없다. 그래서 현재 방식으로는 해당 thread의 pml4에 접근해 clear_page를 할 수 없다. frame에서 직접 소유 thread의 포인터를 가지고 있는 방식도 생각할 수 있지만, 이는 COW가 도입되면 더 복잡해진다. 그러면 또 thread에 list_elem 추가해야해...

 

따라서 frame은 해당 frame과 연동되는 page 포인터(들)을 보유하고, page는 소유하고 있는 thread 포인터를 갖고 있게 하자. 그러면 page 구조체는 다음과 같이 정리가 되며, (일단 COW에 사용될 cow_list_elem도 넣어놓는다)

struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */
	struct hash_elem hash_elem; /* for using hash (spt) */
	bool rw; /* For setting up page a */

	struct list_elem cow_list_elem;
	struct thread *owner;

	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

evict하는 프레임에서 thread에 접근하는 방식은 COW 여부에 따라 다음과 같이 나뉜다.

 

• COW O : frame->[list of pages]->page->owner
• COW X : frame->page->owner

owner에 접근할 수 있으면, pml4에 접근할 수 있으며, 해당 pml4에서 bit 조작이 가능하므로, present와 dirty 여부 변경이 가능하다. 

 

---

 

이제 VM_ANON과 VM_FILE에서 이루어져야 하는 swap in/out 과정을 생각해보자. 위에서 언급했듯, VM_ANON은 파일에서 유래하지 않은 특성상, 그 내용이 swap disk에 들어가게 된다. (물론 실행 파일에서 유래한 것도 있지만 일괄적으로 처리하기 위해서 swap disk에 모두 넣는다) 때문에 anon 쪽에서 해당 swap disk를 초기화시키고, 관리하는 것이 필요하다.

 

swap disk는 disk의 일종으로, 파일 시스템을 초기화할 때 생성된다. disk.c의 주석에 나와있는 내용을 따르면 swap disk는 disk_get의 인자를 1, 1로 맞추면 얻을 수 있다고 한다. 그런데 이것을 가지고 무엇을 할 수 있는가를 생각해야 한다. disk에 내용을 읽고 쓸 수 있는 인터페이스로 pintos는 disk_read와 disk_write를 제공한다. 해당 함수들은 disk 포인터, 버퍼와 함께 disk_sector_t 타입의 sec_no라는 것을 넘겨받는다.

/* Reads sector SEC_NO from disk D into BUFFER, which must have
   room for DISK_SECTOR_SIZE bytes.
   Internally synchronizes accesses to disks, so external
   per-disk locking is unneeded. */
void
disk_read (struct disk *d, disk_sector_t sec_no, void *buffer) {
	struct channel *c;

	ASSERT (d != NULL);
	ASSERT (buffer != NULL);

	c = d->channel;
	lock_acquire (&c->lock);
	select_sector (d, sec_no);
	issue_pio_command (c, CMD_READ_SECTOR_RETRY);
	sema_down (&c->completion_wait);
	if (!wait_while_busy (d))
		PANIC ("%s: disk read failed, sector=%"PRDSNu, d->name, sec_no);
	input_sector (c, buffer);
	d->read_cnt++;
	lock_release (&c->lock);
}

/* 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) {
	struct channel *c;

	ASSERT (d != NULL);
	ASSERT (buffer != NULL);

	c = d->channel;
	lock_acquire (&c->lock);
	select_sector (d, sec_no);
	issue_pio_command (c, CMD_WRITE_SECTOR_RETRY);
	if (!wait_while_busy (d))
		PANIC ("%s: disk write failed, sector=%"PRDSNu, d->name, sec_no);
	output_sector (c, buffer);
	sema_down (&c->completion_wait);
	d->write_cnt++;
	lock_release (&c->lock);
}

해당 인자를 이용해 select_sector를 호출하는 것을 볼 수 있다. 이를 풀이하자면 disk가 여러 개의 "sector"로 나뉘어 있고, sec_no는 접급하려는 sector의 인덱스 같은 역할을 하며, 한 번에 한 개의 섹터에 접근해 읽기/쓰기를 할 수 있도록 disk_read와 disk_write를 제공하는 것이다. 이 섹터는 disk.h의 코드에 의하면 512 Byte의 크기를 가지고 있으며, 

/* Size of a disk sector in bytes. */
#define DISK_SECTOR_SIZE 512

이 함수들만을 이용해 swap_disk에 읽고 쓰는 것을 해 내야한다. 물론 한 페이지의 크기는 4096 Byte이므로, 한 페이지를 저장하는데 총 8개의 sector가 사용될 것이다. 되도록 문제를 간단하게 하기 위해 sector의 인덱스는 한 페이지에 대해 연달아 배정하도록 한다. ex) 0 ~ 7을 한 페이지를 위해 사용

 

주요한 생각거리는 swap_out을 할 때는 어떻게 비어있는 sector를 찾을 수 있는지, swap_in을 할 때는 어떤 sector의 내용을 가져와서 복원하는지이다. swap_in의 경우 해법이 간단하다. swap_out이 될 때 최종적으로 배정된 sector를 페이지 구조체에 저장해서 복원할 때 이용하는 것이다. swap_disk는 VM_ANON에서만 사용되므로, anon.h의 anon_page 구조체의 멤버로 sec_no를 저장하도록 한다.

 

swap_out을 할 때 빈 sector를 찾기 위한 것은 조금 더 복잡하다. 어떤 테이블이 있어서 각 sec_no 마다 할당 여부를 표기해 줄 수 있는 것이 있다면 편할 것이다. 이를 위해 pintos는 우리에게 bitmap 자료구조를 선사한다. 위에서 소개한 대로 bitmap에는 연달아 특정 value를 가지는 부분을 탐색하고, 해당 값들을 뒤집기 위한 함수가 제공된다. 이 함수로 연달아 8개의 false를 가지는 구간을 탐색해 시작 인덱스를 가져올 수 있을 것이다. 그런데 이렇게 하면 bitmap의 크기가 다소 커진다. 이를 위해 위에서 설명한 연속성을 활용하여 bitmap의 인덱스 0은 disk에서의 sec_no 0 ~ 7, 1은 sec_no 8 ~ 15... 이런 식으로 매칭하도록 한다. 이러면 기존보다 bitmap의 크기를 8배나 단축할 수 있다.

 

어쨌거나 swap disk에 대해서는 disk.c와 bitmap.c의 함수들을 조합하면 비어있는 sector를 찾아 내용을 넣거나, 적절한 sector를 찾아 내용을 가져오는 것은 간단할 것이다. 이렇게 VM_ANON의 swap in/out이 작동하도록 anon.c의 함수들을 정정/구현하면 된다.

 

다음으로 VM_FILE이다. VM_FILE의 경우 그 배경이 되는 파일이 (해당 파일이 삭제되어도 적어도 file 포인터가) 존재하기 때문에 해당 공간에서 읽고 쓰기가 이루어질 것이다. 이 읽고 쓰기는 기존에 파일을 읽고 쓰는 함수인 file_read, file_write로 이루어질 것이기에 익숙하다. 단, 이를 위해 필요한 정보는 모두 page 구조체를 통해 접근할 수 있어야 하며, 중요한 점이 하나 있다. 바로 dirty bit를 검사하여, 쓰지 않아도 될 페이지는 file에 write하지 말아야 한다는 것이다. 생각해보면 굳이 변경이 이루어지지 않은 페이지에 대하여 다시 파일에 내용을 쓸 필요가 없으니 당연한 것이다. swap_out을 할 때 dirty bit를 검사하기 위해서는 위에서 구현한 대로 owner를 통해 pml4에 접근해, pml4_is_dirty를 사용하도록 한다. 매뉴얼에서는 검사 후, dirty bit가 켜져 있어 내용을 파일에 쓴 뒤에는 dirty bit를 0으로 재설정하라고 하니 유의한다. 

 

이제 매뉴얼 상의 내용과 생각해볼만한 것들은 전부 적은 것 같다. 구현으로 다시 넘어간다... 주말 동안에는 마무리할 수 있을까.......... ㅠㅠㅠㅠㅠㅠ