(TIL)swap에 대해서

Swap In/Out

git book 내용 정리

• swap slot? → disk 공간에 있는 page size 정도의 공간을 말함.
  • page size에 따라 정렬해야 한다.
• 같은 프레임을 참조하는 여러 page들(aliases)를 조심해라.
  • 유저 가상 주소로 접근한 것인지 check
• swap table을 관리해야 한다
  • process exit()될 경우 swap slot을 free() 해줘야 한다.
  • 스왑 슬롯은 필요할 때마다 할당이 이루어져야 한다. page하나를 저장하기 위해 미리 메모리에 할당하는 것은 매우 비효율적이다.

구상

• 퇴거시킬 page선택한다() - evict frame
  • vm type이 VM anon인지 check
  • page table entry에 있는 비트쌍인 accessed bit와 dirty bit를 이용해서 page 재배치 알고리즘을 구현해야 한다.
  • page를 read 시에는 accessed bit를 1로 설정, write 시에는 dirty bit를 1로 설정해줘야 한다.
  • 사용 가능 여부를 확인하기 위해서는 accessed bit가 1인지 확인한다. 만약 1이라면 다음 page를 탐색하고, 0이라면 퇴거시킨다.
  • 퇴거시킬 때 dirty bit를 check해야하는데 dirty bit가 1이면 swap out()을 진행하고, 0이면 그냥 버려도 된다.
• swap out()
  • page→swap slot idx를 -1로 초기화한다. - swap in할 때 idx로 page를 가져옴
  • page→frame을 메모리에서 Disk로 복사해야 한다.
  • 이때 block write()에서 sector 단위가 512byte이기 때문에 pgsize(4096)짜리 데이터를 읽기 위해서는 8개 섹터(4096/512)를 거쳐야 한다.
  • page→frame 연결 해제
  • pml4에서 해당 entry를 제거해서 가상 주소와의 매핑을 해제해야 함.
  • frame→page = NULL로 초기화함으로써 해당 frame을 다른 page에서도 사용할 수 있게 해줘야 함?
  • swap table이나 disk 접근은 swap lock으로 보호해야 한다.
  • 만약 slot이 없거나 block write(), read()의 실패처리는 panic()으로 처리한다.
• swap in()
  • page→frame을 재할당하고, swap 데이터 복원?
  • 이때 block read()에서 sector 단위가 512byte이기 때문에 pgsize(4096)짜리 데이터를 읽기 위해서는 8개 섹터(4096/512)를 거쳐야 한다.
  • 만약 할당 실패했다면 page→frame에 palloc get page(pal user)을 설정해줌으로써 다른 frame을 evict해준다.
  • page→frame을 할당했다면 pml4_set_page()를 사용해서 가상주소와 매핑을 진행시켜줘야 한다.
  • swap table이나 disk 접근은 swap lock으로 보호해야 한다.
  • 만약 slot이 없거나 block write(), read()의 실패처리는 panic()으로 처리한다.

함수의 역할

→ vm_anon_init()

• swap Disk init?
• swap disk get()
• swap slot 수 계산?? -> 이건 왜 필요한거지?
• swap table create() -> 이해 못 함

→ anon_initializer()

• anon page → swap slot idx 초기화??
• page→frame == NULL check?

→ anon swap out()

• anon page를 swap disk로 교체?
  • 사용 가능한 swap slot을 bitmap에서 찾는다?
  • memcpy()로 anon page를 swap slot에 복사?
  • swap slot idx를 필드에 저장?
  • swap 실패 시 frame 연결 해제 및 fasle 반환
  • dirty bit check?

→ anon swap in()

• swap table에 할당된 swap slot idx를 가져와서
• read at()으로 anon page를 읽는다.
• memcpy()로 해당 데이터를 frame→kva로 복사.
• swap table의 해당 slot을 bitmap reset()을 사용하여 재사용 가능하게 설정?
• swap slot idx 초기화
• anon page가 물리 frame과 연결되어있음을 명시한다.

static struct frame *vm_get_victim(void)

목표

page table entry에 있는 비트쌍인 accessed bit와 dirty bit를 이용해서 page 재배치 알고리즘을 구현하고, 내쫓을 frame을 반환한다.

flow

• frame table을 만든다
• frame struct에 frame elem 멤버를 추가한다.
• frame table을 list end()까지 순회하면서
• frame이 NULL인지 check. 만약 frame이 NULL이라면 frame table이 존재하지 않는다는 말이되기 때문이다.
• accessed bit가 1인지 check한다. 이미 접근한 page는 사용중일 확률이 높으므로 접근하지 않은 page를 희생시킨다.
• page가 anon page인지 확인한다. file backed page일 경우에는 파일에 대한 데이터 일관성 유지로 인해서 eviction 대상에서 제외한다는 데 이 부분은 그림을 그려봐야 이해가 될 것 같다.
• 위 조건을 만족하지 않을 경우 희생 page로 설정한다.
  • frame table에서 삭제하고, 해당 frame을 반환한다.
• 만약 frame table에 희생시킬 page가 존재하지 않는다면 panic()을 발생시킨다.

구현

static struct frame *
vm_get_victim(void)
{
	/* TODO: 페이지 교체 정책은 여러분이 결정할 수 있습니다. */
	struct thread *curr = thread_current();
	struct list_elem *e = list_begin(&frame_table);
		
	while(e != list_end(&frame_table)){
		struct frame *f = list_entry(e, struct frame, frame_elem);
		struct page *page = f->page;

		// 만약 frame이 존재하지 않는다면...
		if(f == NULL){
			PANIC("[vm_get_victim] frame이 존재하지 않습니다...\n");
		}

		if (VM_ANON != page->operations->type){
			e = list_next(e);
			continue;
		}

		if(pml4_is_accessed(curr->pml4, page->va)){ 
			/* accessed bit를 reset()을 사용해서 0으로 만들고 넘어간다.
			* 내 생각으로는 이미 한 번 접근한 page는 접근 bit를 1로 만들지만 다시 접근했을 때 0으로 초기화 해주는 이유는
			* 기존의 page가 메모리 공간을 차지함으로써 새로운 page가 로드되는 걸 막기 때문이지 않을까?? */
			pml4_set_accessed(curr->pml4, page->va, false);
			e = list_next(e);
			continue;
		}
		
		list_remove(e);
		return f;
	}
	PANIC("[vm_get_victim] frame victim이 존재하지 않아요 ㅠㅠ\n");
}

static struct frame *vm_get_frame(void)

static struct frame *
vm_get_frame(void)
{
	struct frame *frame = malloc(sizeof(struct frame));

	if (frame == NULL)
	{
		PANIC("TODO");
	}

	// NOTE: PAL_USER인 이유는 주석에 user space pages를 본 함수로 할당받아야 한다고 명시되어 있어서 이렇게 함. 악성 프로그램이 고의로 커널풀 메모리 고갈시키는 거 막기 위한 분리.
	frame->page = NULL;
	ASSERT(frame->page == NULL);

	frame->kva = palloc_get_page(PAL_USER);
	if (frame->kva == NULL)
	{
		free(frame);			  // frame 메타 데이터 자료구조 해제
		frame = vm_evict_frame(); // TODO: evict frame 함수가 아직 구현되지 않음.
	}
	ASSERT(frame->kva != NULL);

	// frame lock 걸어줘야 함.
	list_push_back(&frame_table, &frame->frame_elem);
	
	return frame;
}

frame은 vm_get_frame()에서 push해준다.

---

static struct frame *vm_evict_frame(void)

구상

• frame을 change해줘야 한다.
  • 현재 입력 받은 victim frame의 dirty bit을 check
  • 만약 dirty bit가 1이면 swap out()
  • 0이면 그냥 버린다.
• page→frame을 NULL로 초기화한다.
• page를 NULL로 초기화한다.
• 재사용할 frame을 반환한다.

구현

/* 하나의 페이지를 교체하고 해당 프레임을 반환합니다.
 * 실패 시 NULL을 반환합니다. */
static struct frame *
vm_evict_frame(void)
{
	/* TODO: victim을 스왑 아웃하고 교체된 프레임을 반환하세요. */
	struct frame *victim UNUSED = vm_get_victim();
	struct thread *curr = thread_current();
	struct page *page = victim->page;
	struct frame *change_f;
	// 퇴거시킬 때 dirty bit를 check해야하는데 dirty bit가 1이면 swap out()을 진행하고, 0이면 그냥 버려도 된다.
	if(pml4_is_dirty(curr->pml4, page->va)){
		if(!swap_out(page)){
			PANIC("[vm_evict_frame]swap out fail!!!\n");
		}
	}

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

	return victim;
}

vm_anon_init()

구상

• 스왑 disk가 뭐지??
• 사용 가능한 영역과 사용된 영역을 어떻게 구분해??
  • swap size을 계산해서 top부터 size까지는 사용된 영역, 그 밑으로는 사용 가능한 영역으로 나누면 어떨까?

flow

→ disk를 초기화 한다.

→ disk의 정보를 가져와서

→ disk size를 계산한다.

구현

/* 익명 페이지를 위한 데이터를 초기화합니다 */
void vm_anon_init(void)
{

    // TODO: swap 구현 시 아래 내용을 추가해야 함. 사유는 그때 가서 이해하기.
    /* swap_disk를 설정하세요. */
    disk_init();
    swap_disk = disk_get(1, 1); // NOTE: disk_get 인자값 적절성 검토 완료. 
    size_t swap_size = disk_size(swap_disk); // SECTORS_PER_PAGE;
    // swap_table = bitmap_create(swap_size);
}