PintOS P3 #A : Clock Algorithm

static struct frame *
vm_get_victim (void) {
	// Clock Algorithm : 2번 순회해서 찾아냄
	struct frame *victim = NULL;
 	struct list_elem *e;
	lock_acquire(&g_frame_lock);
 	for (e = list_begin (&g_frame_table); e != list_end (&g_frame_table); e = list_next (e))
	{
   		struct frame *frame = list_entry (e, struct frame, f_elem);
		if(pml4_is_accessed(&thread_current()->pml4, frame->page->va))
			pml4_set_accessed(&thread_current()->pml4, frame->page->va, false);
		else
		{
			lock_release(&g_frame_lock);
			return frame;
		}
 	}
	
	for (e = list_begin (&g_frame_table); e != list_end (&g_frame_table); e = list_next (e))
	{
		struct frame *frame = list_entry (e, struct frame, f_elem);
		 if(!pml4_is_accessed(&thread_current()->pml4, frame->page->va))
		 {
			lock_release(&g_frame_lock);
			return frame;
		 }
	}
	lock_release(&g_frame_lock);
	return NULL;
}

전체를 한 바퀴 돌면서, No를 찾는다. No를 찾으면 즉시 종료한다. Yes가 있으면 No로 바꾸고 다음으로 넘어간다.

만약 No를 하나라도 못찾으면 순회를 처음부터 다시한다. 이번엔 무조건 No가 한 개 이상 있을 수 밖에 없다.

그런식으로 No가 해당인 내용을 찾는것이 Clock Algorithm이다. 쫓아낼 페이지를 확인 할 때 필요하다.