Swap In/Out
Anonymous Page
ANON의 경우에는 디스크 안에 해당 페이지에 대한 BACKING STORE가 없다. 이 말은, 디스크로 SWAP OUT 되었을 때 이 페이지를 저장할 공간이 디스크 내에 없다는 뜻이다. 따라서 디스크 내에 별도의 공간 SWAP DISK를 만들어 두고, 이 공간에 SWAP OUT된 ANON 페이지를 저장하도록 한다.
vm_anon_init과 anon_initializer를 먼저 수정한다.
struct anon_page 리마인드
만약 ANON 페이지가 디스크로 SWAP OUT 되었을 때, 디스크에 저장된 디스크 섹터 구역을 저장해주는 swap_index 변수가 존재한다.
맨 처음 ANON 페이지를 초기화하면(UNINIT으로부터) 물리 메모리 위에 있으므로 swap_index의 값은 -1로 지정해 둔다.
struct anon_page {
int swap_index; // swap된 데이터들이 저장된 섹터 구역을 의미한다.
};Swap Table 선언
디스크에서 사용 가능한 swap slot과 사용 불가능한 swap slot을 관리하는 자료구조인 Swap Table을 선언해준다. 이 때 스왑 테이블은 비트맵 객체로 선언된다.
스왑 테이블은 가상 메모리에 있는 객체이다.
vm.c/anon.c
struct bitmap *swap_table;
const size_t SECTORS_PER_PAGE = PGSIZE / DISK_SECTOR_SIZE; // sectors / page비트맵이란 Bit를 저장하는 연속된 메모리 공간 위의 배열 객체를 의미한다. Bit 하나는 0아니면 1의 값을 갖는데, 이 값은 해당 비트와 연결된 자원이 상황에 따라 absent/present한지, 아님 locked/unlocked한지, 아님 valid/invalid한지 등등을 나타내준다.
여기 스왑 테이블의 경우 각각의 비트는 스왑 슬롯 각각과 매칭된다. 스왑 테이블에서 해당 스왑 슬롯에 해당하는 비트가 1이라는 말은 그에 대응되는 페이지가 swap out되어 디스크의 스왑 공간에 임시적으로 저장되었다는 뜻이다.
SECTORS_PER_PAGE
한 페이지에 들어갈 수 있는 디스크 섹터의 개수를 의미한다. PGSIZE == 1<<12 == 4kb이고 DISK_SECTOR_SIZE == 512byte이다.
디스크 섹터는 하드 드라이브의 최소 기억 단위라고 한다. 마치 가상 메모리 공간을 여러 페이지로 나누어 놓은 것처럼, 디스크 위의 물리적인 저장 공간이라는 것이 중요하다. HDD의 경우에는 512 byte의 고정된 크기를 갖는다. 만약 디스크에 파일이 저장된다고 하면, 파일은 여러 디스크 섹터들을 거쳐서 저장된다. 파일의 크기가 2kb라고 하면 4개의 디스크 섹터에 파일이 나뉘어 저장되는 것이다.
가상 페이지의 크기는 4kb이므로, 하나의 페이지를 저장하기 위해 필요한 디스크 섹터의 개수는 8개가 되겠다.
vm_anon_init() 수정
ANON 페이지를 위한 디스크 내 스왑 영역을 생성해주는 함수이다. 디스크 내에 스왑 영역을 만들어주고 이를 관리하는 스왑 테이블도 만들어준다.
swap_size는 스왑 디스크 안에서 만들 수 있는 스왑 슬롯의 개수를 의미한다.
이다.
만약 스왑 공간이 4096byte라고 한다면 4096 / 8 = 512개의 페이지에 대한 정보를 저장할 수 있는 512개의 스왑 슬롯을 만들 수 있다.
void vm_anon_init (void) {
swap_disk = disk_get(1, 1);
size_t swap_size = disk_size(swap_disk) / SECTORS_PER_PAGE; // (size/page)*sector
swap_table = bitmap_create(swap_size);
}anon_initializer() 수정
swap_index의 값을 -1로 설정해준다. 페이지 폴트가 떠서 해당 페이지를 물리 메모리로 올리게 되므로, 해당 페이지는 디스크가 아닌 물리 메모리에 있기 때문!
bool anon_initializer (struct page *page, enum vm_type type, void *kva) {
/* page struct 안의 Union 영역은 현재 uninit page이다.
ANON page를 초기화해주기 위해 해당 데이터를 모두 0으로 초기화해준다.
Q. 이렇게 하면 Union 영역은 모두 다 0으로 초기화되나? -> 그릏다 */
struct uninit_page *uninit = &page->uninit;
memset(uninit, 0, sizeof(struct uninit_page));
/* Set up the handler */
/* 이제 해당 페이지는 ANON이므로 operations도 anon으로 지정한다. */
page->operations = &anon_ops;
/* 해당 페이지는 아직 물리 메모리 위에 있으므로 swap_index의 값을 -1로 설정해준다. */
struct anon_page *anon_page = &page->anon;
anon_page->swap_index = -1;
return true;
}💡 ANON 페이지를 스왑 아웃한다. 디스크에 백업 파일이 없으므로, 디스크 상에 스왑 공간을 만들어 그곳에 페이지를 저장한다.anon_swap_out( page ) 구현
현재 디스크 섹터와 그에 해당하는 페이지 및 스왑 슬롯은 다음과 같다.
disk sector : 1 2 3 4 5 6 7 8 910111213141516 1718192021222324
each page : | 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 |
page_no & swap slot : 1 2 3가상 메모리의 스왑 테이블에서 비트가 false인 스왑 슬롯을 찾는다. 비트가 false라는 말은 해당 스왑 슬롯에 swap out된 페이지를 할당할 수 있다는 의미이다.
그 후 해당 스왑 슬롯에 해당하는 디스크의 영역에 가상 주소 공간의 데이터를 페이지의 시작 주소부터 디스크 섹터 크기로 잘라서 저장한다.
그 후 해당 스왑 슬롯에 대응되는 스왑 테이블의 비트를 TRUE로 바꿔주고, ANON 페이지의 swap_index 멤버에 스왑 슬롯 번호를 저장해서 이 페이지가 디스크의 스왑 영역 중 어디에 swap 되었는지를 확인할 수 있도록 한다.
SWAP OUT된 페이지의 Present Bit의 값은 0으로, 프로세스가 해당 페이지의 데이터에 접근하려 하면 페이지 폴트가 뜨게 된다.
static bool anon_swap_out (struct page *page) {
struct anon_page *anon_page = &page->anon;
/* 비트맵을 처음부터 순회해 false 값을 가진 비트를 하나 찾는다.
즉, 페이지를 할당받을 수 있는 swap slot을 하나 찾는다. */
int page_no = bitmap_scan(swap_table, 0, 1, false);
if (page_no == BITMAP_ERROR) {
return false;
}
/* 한 페이지를 디스크에 써 주기 위해 SECTORS_PER_PAGE개의 섹터에 저장해야 한다.
이 때 디스크에 각 섹터의 크기 DISK_SECTOR_SIZE만큼 써 준다. */
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);
}
/* swap table의 해당 페이지에 대한 swap slot의 비트를 TRUE로 바꿔주고,
해당 페이지의 PTE에서 Present Bit을 0으로 바꿔준다.
이제 프로세스가 이 페이지에 접근하면 Page Fault가 뜬다. */
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;
}- bitmap_scan() 비트맵 객체 B의 START 인덱스부터 연속된 비트들의 그룹의 시작 주소를 찾는다. 이 때 그룹의 모든 value의 값이 VALUE여야 한다.
- bitmap_contains() START부터 CNT까지의 범위 내에 VALUE와 동일한 value값을 가진 비트가 하나라도 있으면 TRUE를 리턴한다.
- disk_write( disk, sec_no, buffer ) BUFFER에서부터 데이터를 디스크 D의 섹터 SEC_NO에 써 준다.
anon_swap_in() 구현
SWAP OUT된 페이지에 저장된 swap_index 값으로 스왑 슬롯을 찾아 해당 슬롯에 저장된 데이터를 다시 페이지로 원복시킨다.
static bool anon_swap_in (struct page *page, void *kva) {
struct anon_page *anon_page = &page->anon;
/* swap out된 페이지가 디스크 스왑 영역 어디에 저장되었는지는
anon_page 구조체 안에 저장되어 있다. */
int page_no = anon_page->swap_index;
/* 스왑 테이블에서 해당 스왑 슬롯이 진짜 사용 중인지 체크 */
if (bitmap_test(swap_table, page_no) == false) {
return false;
}
/* 해당 스왑 영역의 데이터를 가상 주소 공간 kva에 써 준다. */
for (int i = 0; i < SECTORS_PER_PAGE; ++i) {
disk_read(swap_disk, page_no * SECTORS_PER_PAGE + i, kva + DISK_SECTOR_SIZE * i);
}
/* 다시 해당 스왑 슬롯을 false로 만들어준다. */
bitmap_set(swap_table, page_no, false);
return true;
}File-Backed Page
Fil-Backed Page의 경우 디스크에 backed file이 있으므로, swap out될 때 해당 파일에 저장되면 된다.
Swap out되면 해당 페이지의 PTE의 Present Bit은 0이 되고, 해당 페이지에 프로세스가 접근하면 페이지 폴트가 일어나고 디스크의 파일 데이터를 다시 물리 메모리에 올리면서 swap in된다.
file_backed_swap_out() 수정
do_munmap()과 거의 유사하다는 것을 알 수 있다. 단지 do_munmap()은 연속된 가상 메모리 공간에 매핑된 페이지들을 모두 swap out해주는 것이고, file_backed_swap_out()은 한 페이지에 대해 매핑을 해제해준다는 것이 다르다.
static bool file_backed_swap_out (struct page *page) {
struct file_page *file_page UNUSED = &page->file;
if (page == NULL)
return false;
struct container* container = (struct container *)page->uninit.aux;
/* 수정된 페이지(더티 비트 1)는 파일에 업데이트 해 놓는다.
그리고 더티 비트를 0으로 만들어둔다. */
if (pml4_is_dirty(thread_current()->pml4, page->va)){
file_write_at(container->file, page->va,
container->page_read_bytes, container->offset);
pml4_set_dirty(thread_current()->pml4, page->va, 0);
}
/* present bit을 0으로 만든다. */
pml4_clear_page(thread_current()->pml4, page->va);
}file_backed_swap_in() 수정
lazy_load_segment()와 비슷하다는 것을 알 수 있다.
Present Bit이 0으로 세팅되어 있는 File-Backed Page에 프로세스가 접근하게 되면 Supplementary Page Table의 struct page 내에 있는 struct file_page에 접근한다. file_page 구조체의 container 구조체에서 이 가상 페이지와 관련된 디스크의 파일 데이터의 정보를 불러올 수 있다.
이 정보를 토대로 먼저 물리 공간에 프레임을 하나 할당받아 해당 페이지와 매핑해준 다음, 디스크의 파일에서 물리 프레임으로(vm_do_claim_page() 내 swap_in(page, frame->kva)) 데이터를 다시 복사해온다.
static bool file_backed_swap_in (struct page *page, void *kva) {
struct file_page *file_page UNUSED = &page->file;
if(page==NULL)
return false;
struct container *aux = (struct container *)page->uninit.aux;
struct file *file = aux->file;
off_t offset = aux->offset;
size_t page_read_bytes = aux->page_read_bytes;
size_t page_zero_bytes = PGSIZE - page_read_bytes;
file_seek (file, offset);
if(file_read(file, kva, page_read_bytes) != (int)page_read_bytes) {
// palloc_free_page(kva);
return false;
}
memset(kva + page_read_bytes, 0, page_zero_bytes);
return true;
}Page Replacement Policy
프로세스가 가상 페이지를 통해 물리 메모리에 접근하려 시도할 때, 물리 프레임이 모두 꽉 차 있으면 물리 메모리에서 적당한 하나의 프레임을 골라 디스크로 Swap Out 한다. 이 때 swap out할 적당한 프레임을 고르는 정책을 Page Replacement Policy라고 부른다.
frame_table list 구현 및 수정
앞에서 선언해주었던 struct frame과 frame_table 리스트를 다시 한번 가져와보자. 이 둘의 존재 이유는 물리 프레임들을 관리해주면서 swap out시킬 적당한 프레임을 고르기 편하게 해 주는 데에 있다.
include/vm/vm.h
struct frame {
void *kva;
struct page *page;
struct list_elem frame_elem;
}vm.c
frame들을 관리하는 frame table 리스트와 해당 리스트를 순회해주기 위한 start 변수를 선언해준다.
struct list frame_table;
struct list_elem *start;vm.c/vm_init()
맨 처음 가상 메모리에 대한 서브 시스템들을 초기화해주는 vm_init() 함수에서 프레임 테이블과 start 변수도 초기화해준다.
void vm_init(void)
{
vm_anon_init();
vm_file_init();
#ifdef EFILESYS /* For project 4 */
pagecache_init();
#endif
register_inspect_intr();
list_init(&frame_table); // 수정!
start = list_begin(&frame_table); // 수정!
}- vm_init()은 언제 실행되는가? init.c → main() → vm_init()의 순서로 실행된다. 핀토스의 메인 프로그램이 실행될 때 같이 실행된다.
vm_get_frame() 수정
이제 페이지를 claim할 때 페이지에 해당하는 물리 프레임을 가져오는 vm_get_frame()을 수정한다.
페이지를 물리 메모리 공간에 palloc하여 할당받는 과정에서 아무 것도 받아오지 못했다면, 물리 프레임에 자리가 없어 가져오지 못한 것으로 판단한다. 그렇담 vm_evict_frame()을 호출하여 프레임 하나의 데이터를 swap out해버리고 해당 프레임과 새 페이지를 매핑해줄 것이다.
이 때 프레임을 할당받은 다음에 물리 프레임을 관리하는 struct frame을 페이지 테이블에 insert시켜 관리한다.
static struct frame *vm_get_frame(void)
{
// struct frame *frame = NULL;
/* TODO: Fill this function. */
struct frame *frame = (struct frame *)malloc(sizeof(struct frame));
frame->kva = palloc_get_page(PAL_USER); /* USER POOL에서 커널 가상 주소 공간으로 1page 할당 */
/* if 프레임이 꽉 차서 할당받을 수 없다면 페이지 교체 실시
else 성공했다면 frame 구조체 커널 주소 멤버에 위에서 할당받은 메모리 커널 주소 넣기 */
if (frame->kva == NULL)
{
frame = vm_evict_frame(); // 수정!
frame->page = NULL;
return frame;
}
/* 새 프레임을 프레임 테이블에 넣어 관리한다. */
list_push_back (&frame_table, &frame->frame_elem);
frame->page = NULL;
ASSERT(frame != NULL);
ASSERT(frame->page == NULL);
return frame;
}vm_evict_frame() 구현
이 함수는 vm_get_victim() 함수를 호출하여 프레임 테이블에서 적당한 프레임을 찾아낸 다음, 해당 프레임을 swap out 해주는 함수이다.
static struct frame *vm_evict_frame(void)
{
struct frame *victim UNUSED = vm_get_victim();
/* TODO: swap out the victim and return the evicted frame. */
swap_out(victim->page);
return victim;
}vm_get_victim() 구현
이 함수는 페이지 교체 정책을 실제로 구현하는 함수이다.
vm.c/vm_get_victim()
static struct frame *vm_get_victim(void)
{
struct frame *victim = NULL;
/* FIFO eviction policy */
// victim = list_entry(list_pop_front (&frame_table), struct frame, frame_elem);
// // swap-file, swap-anon 실패
struct thread *curr = thread_current();
struct list_elem *e = start;
/* */
for (start = e; start != list_end(&frame_table); start = list_next(start))
{
victim = list_entry(start, struct frame, frame_elem);
if (pml4_is_accessed(curr->pml4, victim->page->va))
pml4_set_accessed(curr->pml4, victim->page->va, 0);
else
return victim;
}
for (start = list_begin(&frame_table); start != e; start = list_next(start))
{
victim = list_entry(start, struct frame, frame_elem);
if (pml4_is_accessed(curr->pml4, victim->page->va))
pml4_set_accessed(curr->pml4, victim->page->va, 0);
else
return victim;
}
return victim;
}PintOS Project3 GIthub 주소 PintOS
