(2021.10.23) Mlfqs - Mlfqs 관련 함수 추가

1. 서론 및 필요 내용 설명

Mlfqs에서 주요한 변수는 priority, recent_cpu, 그리고 load_avg 3개이다. 이 3개 중 priority와 recent_cpu는 각 Thread에 귀속되지만, load_avg는 전역적인 변수로, 모든 Thread에서 참조하게 될 것이다. 이 3개의 주요한 변수는 모두 tick의 변화에 따라 달라져야 하므로 timer_interrupt(), 즉 매 tick마다 불리는 함수에서 관리를 해야 할 것이며, 해당 변수가 어떻게 변해야 하는지는 이전 포스팅에 수식으로 설명하였다. 다시 갔다 오기 번거로운 사람들을 위해 다시 설명하자면,

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice
load_avg = (59/60) * load_avg + (1/60) * ready_threads

 

따라서 이번에는 priority, recent_cpu, load_avg 변수를 추가하고, 해당 변수를 관리하는 함수들을 구현하여, timer_interrupt()에 추가하는 것까지가 목적이다.

 

---

2. 구현해야 하는 것

• priority, recent_cpu, load_avg 추가
• 위 변수를 update하는 함수 추가
• timer_interrupt()에 위 함수를 호출하는 루틴 추가

 

---

3. 구현 과정

3-1. 필요 변수 추가

우선 서론에서 언급했듯, priority와 recent_cpu는 각 Thread마다 가져야 하는 변수이기 때문에 Thread 구조체에 추가해줬으며,

struct thread {
	...

	/* For mlfqs */
	int nice;
	fp_t recent_cpu;
}

load_avg는 전역적으로 선언했다.

/* thread.c */
fp_t load_avg;

각자 초기화는 priority와 recent_cpu는 init_thread()에서, load_avg는 thread_init()에서 하도록 구현한다. 이 때, 가장 처음에 생성되는 Thread인 main을 제외하고는 모두 부모 Thread의 priority와 recent_cpu를 상속받는다고 매뉴얼에서 언급하고 있으며, 해당 기능은 thread_mlfqs가 True일 때만 실행되어야 하기에 이를 참조하여 구현하였다.

static void
init_thread (struct thread *t, const char *name, int priority) {
	...
	
	if (thread_mlfqs) 
	{
		if (strcmp(name, "main") == 0) 
		{
			t->nice = 0;
			t->recent_cpu = 0;
		}
		else 
		{
			t->nice = thread_current()->nice;
			t->recent_cpu = thread_current()->recent_cpu;
		}
		mlfqs_update_thread_priority (t);
	}
	
	else
	{
		t->priority = priority;
		t->org_priority = priority;
	}
	
	...
    
	t->magic = THREAD_MAGIC;
}

void
thread_init (void) {
	...
	load_avg = 0;
	...
}

mlfqs_update_thread_priority()는 곧 설명할 것이다.

 

이제 해당 변수의 초기화가 끝났으면 각 변수를 update하는 함수를 구현할 차례이다. 여기서 문제에 직면했다. 어떻게 현존하는 모든 Thread를 순회하면서 각 Thread의 priority를 update해 줄 수 있을까? 각 Thread는 실행 중인 Thread, ready_list에 있는 Thread를 제외하면 락이나 타이머에 의해 파편화된 Block Thread일 것이다. 이들을 전부 일괄적으로 관리하려면 또다른 리스트가 필요할 것이라 판단하였고, list_elem을 추가하기로 했다. 바로 all_elem이다.

struct thread {
	...
	/* For mlfqs */
	int nice;
	fp_t recent_cpu;
	struct list_elem all_elem;
	...
};

해당 all_elem을 사용해 Thread를 넣을 list인 all_list도 전역적으로 추가하고, 초기화하는 루틴을 넣었다.

/* load_avg used for mlfqs, all_list is for updating every thread's priority & recent_cpu */
fp_t load_avg;
static struct list all_list;

void
thread_init (void) {
	...
    /* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&sleep_list);
	list_init (&all_list);
	list_init (&destruction_req);
	load_avg = 0;
	...
}

all_elem을 사용해 현존하는 모든 Thread가 all_list에 들어가게 하려면, Thread가 생성될 때 all_list에 넣고, Thread가 파괴되려고 할 때 all_list에서 빼면 된다. 해당 루틴을 추가한다.

static void
init_thread (struct thread *t, const char *name, int priority) {
	...
	if (thread_mlfqs) 
	{
		if (strcmp(name, "main") == 0) 
		{
			t->nice = 0;
			t->recent_cpu = 0;
		}
		else 
		{
			t->nice = thread_current()->nice;
			t->recent_cpu = thread_current()->recent_cpu;
		}
		mlfqs_update_thread_priority (t);
	}
	
	else
	{
		t->priority = priority;
		t->org_priority = priority;
	}
	
	list_push_back(&all_list, &t->all_elem);
	list_init(&t->lock_list);
	t->wait_on_lock = NULL;

	t->magic = THREAD_MAGIC;
}

void
thread_exit (void) {
	...
	/* Just set our status to dying and schedule another process.
	   We will be destroyed during the call to schedule_tail(). */
	intr_disable ();
	list_remove(&thread_current()->all_elem);
	do_schedule (THREAD_DYING);
	NOT_REACHED ();
}

이제 모든 Thread를 순회하기 위해서는 all_list를 참조하면 된다. 이를 기반으로 update 함수를 구현하자.

3-2. update 함수

우선 priority를 update하는 함수를 만들자. mlfqs에서 priority가 update/계산되는 경우는 Thread가 처음 생성될 때, 그리고 시스템 부팅 후 매 4틱마다 이다. 매 4틱마다는 현존하는 모든 Thread의 priority가 update되어야 하기에, 우선 한 Thread의 priority를 update하는 함수를 구현하고, 이를 사용해 순회하는 함수를 구현하면 된다.

void
mlfqs_update_thread_priority (struct thread *t)
{
	fp_t pri_fp;
	int pri_int;

	pri_fp = n_to_fp(PRI_MAX);
	pri_fp -= (t->recent_cpu / 4);
	pri_fp -= n_to_fp(t->nice * 2);

	pri_int = fp_to_nearest(pri_fp);
	t->priority = pri_int;

	return;
}

/* Update each priority of all threads */
void
mlfqs_update_priority (void)
{
	struct list_elem *e;
	struct thread *t;
	
	for (e = list_begin(&all_list); e != list_end(&all_list); e = list_next(e))
	{
		t = list_entry(e, struct thread, all_elem);
		mlfqs_update_thread_priority (t);		
	}

	return;
}

mlfqs_update_thread_priority()는 파라미터로 주어진 t의 priority를 update하며, mlfqs_update_priority는 모든 Thread의 priority를 update한다. init_thread()는 위에서 작성했듯 mlfqs_update_thread_priority()를 호출하도록 하여 새롭게 생성된 Thread의 priority를 설정한다. mlfqs_update_priority()는 다른 함수 작성이 끝나면 timer_interrupt()에 같이 넣을 것이다.

 

다음으로 recent_cpu를 업데이트하는 함수이다. 우선 매 틱마다 현재 실행되고 있는 Thread가 idle이 아닐 경우 recent_cpu를 올려줘야 한다. 또 tick % TIMER_FREQ == 0, 즉 매 초마다 수식에 의해 recent_cpu를 update할 필요가 있다. 함수를 두 개로 만드는 것이 더 간단할 것 같아 분리하여 구현하였다.

void
mlfqs_increment_recent_cpu (void)
{
	if (thread_current () != idle_thread)
		thread_current ()->recent_cpu += 1;
}

/* Update each recent_cpu of all threads */
void
mlfqs_update_recent_cpu (void)
{
	struct list_elem *e;
	struct thread *t;
	fp_t coeff, new_recent_cpu;

	for (e = list_begin(&all_list); e != list_end(&all_list); e = list_next(e))
	{
		t = list_entry(e, struct thread, all_elem);
		coeff = div_fp_fp(2 * load_avg, 2 * load_avg + n_to_fp(1));
		new_recent_cpu = mult_fp_fp(coeff, t->recent_cpu) + n_to_fp(t->nice);

		t->recent_cpu = new_recent_cpu;
	}

	return;
}

복잡해 보이지만 매뉴얼에 주어진 식 대로 구현한 것이다.

 

마지막으로 load_avg update 함수의 구현이다. 지금 실행되고 있는 Thread와 ready_list에 있는 Thread의 개수의 총합을 구하여 ready_threads를 계산할 필요가 있으므로 보조함수를 만들고, 이를 사용하여 구현하도록 한다. idle thread는 세지 않는다는 것을 주의하여 코딩한다. idle_thread는 yield의 구현에 의해 ready_list에 들어가지 않으므로 현재 실행되고 있는 Thread만 주의하면 된다.

void
mlfqs_update_load_avg ()
{
	fp_t l_a = load_avg;
	fp_t new_l_a = mult_fp_fp(frac_to_fp (59, 60), l_a) + frac_to_fp(1, 60) * count_ready_threads();
	load_avg = new_l_a;
	return;
}

int
count_ready_threads ()
{
	int cnt = 0;
	struct thread *cur = thread_current ();

	if (cur != idle_thread)
		cnt += 1;
	
	cnt += list_size(&ready_list);
	return cnt;
}

이제 모든 update 함수가 준비되었다. 이제 timer_interrupt()를 수정하자.

3-3. timer_interrupt() 수정

timer_interrupt()에서는 내부적으로 맨 마지막에 thread_tick()을 호출하고, 지난 priority 관련 프로젝트를 진행할 때 thread_tick()에서 ready_list를 priority 순으로 정렬하고 preemption되도록 해 놨기 때문에 따로 건드릴 것은 없다. 그 이전에 priority가 변하도록만 해 놓는다면 될 것이다. 가이드라인에서도 정했듯, load_avg, recent_cpu, priority 순으로 update가 이루어지도록 할 것이며, 해당 기능은 thread_mlfqs가 True일 때만 발현되도록 해 놓는다. load_avg와 recent_cpu는 매 초마다, priority는 4틱 마다 한 번씩 update가 이루어진다.

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_wakeup (ticks);
	
	if (thread_mlfqs)
	{
		mlfqs_increment_recent_cpu ();

		if (ticks % TIMER_FREQ == 0)
		{
			mlfqs_update_load_avg ();
			mlfqs_update_recent_cpu ();
		}

		if (ticks % 4 == 0)
		{
			mlfqs_update_priority ();
		}
	}

	// ready list is sorted by priority, preempted in thread_tick
	thread_tick ();
}

이제 기본적인 구현은 전부 마무리되었다.

 

---

4. 디버깅

아직 synch.c의 수정이 되지 않아 실행할 수는 없다. 다음 포스팅에서 모두 수정하고 실행해서 디버깅하도록 하자.

 

---

5. 후기

이제 프로젝트 1의 끝이 보인다. 조금만 더 힘내자...