Pintos-Kaist 진행하기 (3): mlfqs

0. 서론

---

Pintos-Kaist 진행하기 (2) : 프로젝트 1 (매우 김)

저번 글에서 이어진다.

make check를 했을 때 -T 480씩 걸려있는 것들이 있다. 이번엔 이 고급 스케줄러를 진행하려고 한다.

구현해야 하는 Mlfqs.는 4.4BSD 스케줄러다. 이 스케줄러는 차후 프로젝트에서는 사용하지 않으므로, 이 전 단계만 제대로 구현하면 된다. priority donation역시 사용하지 않기 때문에 thread_mlfqs 변수에 따라 분기를 나누어 실행을 조절해야 한다.

---

1. Mlfqs란

---

 

우리가 구현할 4.4BSD 스케줄러는 시간에 따라 변하는 Thread의 변화에 따라 어떤 스레드가 실행되어야 하는지를 계속 계산하는 Multilevel feedback queue schedule(Mlfqs) 방식을 사용한다. 뜻을 나누면 다단계 피드백 큐 스케줄러다.

단계는 우선순위(priority)에 의해 나뉜다. 각 큐 마다 지정된 우선도가 있으며, 해당 우선도를 가진 스레드를 큐에 넣고 관리하는 것이다. 해시 테이블처럼.

중요한 점은 이 우선순위는 임의로 수정할 수 없다. 각 우선순위는 아래의 공식을 따라 스케줄러에서 관리하게 된다.

@warning
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

---

1.1. 주요 변수

---

nice 변수

스레드가 CPU를 양보하려는 정도를 나타내는 정수값.

nice가 높으면 다른 스레드에게 CPU를 잘 양보하고, 낮으면 다른 스레드로부터 CPU를 많이 뺏어온다.

nice 값이 커질수록 우선순위는 줄어들어 CPU를 차지하고 있는 빈도는 줄어들고, nice 값이 작아질수록 우선순위가 높아져 해당 스레드에 cpu 할당 시간이 커진다. 

• NICE_MIN = -20. NICE_MAX=+20
• NICE_DEFAULT:0

다른 스레드는 부모 스레드의 nice를 물려받는다. 

 

recent_cpu

해당 스레드가 최근에 CPU를 얼마나 사용했는지를 나타내는 실수값. 

 @warning
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice

매 tick 마다 runnning 스레드의 recent_cpu 값이 1 증가한다.(idle 스레드가 아니면)

매 1초마다 모든 스레드의 recent_cpu 값을 재계산한다.

 

load_avg 

최근 1분동안 수행 가능한 스레드의 평균 개수를 나타내는 실수값.

수행 가능한 스레드의 평균 개수가 많으면 모든 스레드가 골고루 CPU time을 배분받을 수 있도록 이미 사용한 스레드의 priority 가 천천히 증가해야 하고, 평균 개수가 적을 때에는 좀 더 빠르게 증가해도 모든 스레드가 골고루 CPU time을 배분받을 수 있다. 

즉, 이 값이 크면 recent_cpu값은 천천히 감소하고, 작으면 recent_cpu 값이 빠르게 감소한다.

매 1초 마다 load_avg 값을 재계산한다. 

@warning
load_avg = (59/60) * load_avg + (1/60) * ready_threads

 

---

1.2. 고정 소수점

---

priority, nice는 정수 값을, recent_cpu와 load_avg는 실수값을 갖는다. 여기서 문제는 부동 소수점 연산이 매우 복잡해서, kernel을 느리게 만들기 때문에 pintos에서는 부동소수점 연산을 지원하지 않는다는 점이다. 때문에 우리는 고정 소수점 연산으로 계산을 해야 한다.

고정 소수점 연산은 위의 그림과 같이 총 32비트의 정수형 자료형에 뒤의 14비트는 소수 부분, 그 다음 17비트는 정수 부분, 마지막 1비트는 값의 부호를 나타내는 방식이다. 

단, 이렇게 고정 소수점을 사용하는 방식에는 문제가 있다.

 

위와 같이 고정 소수점으로 나타낸 5.5와 1.5를 곱하면 아래의 결과를 얻을 수 있다. 이 값을 그대로 사용하면 우리가 기대하는 값과 아주 다른 값이 나오게 된다.

때문에 고정 소수점을 사용할 두 수를 곱할 때는 먼저 앞의 수를 (int64)자료형으로 타입 캐스팅 진행 후, 두 수를 곱하고 $2^{14}$로 나누는 연산이 필요하다.

---

3. 수식 함수 

---

 @ 코드 보기

 

//fixed-point.h

#ifndef FIXED_POINT_H
#define FIXED_POINT_H

#define F (1 << 14) // 17.14 고정소수점 포맷의 스케일 팩터

typedef int fixed_t;

// 변환
fixed_t int_to_fp(int n);       // 정수 -> 고정소수점
int fp_to_int(fixed_t x);       // 고정소수점 -> 정수 (내림)
int fp_to_int_round(fixed_t x); // 고정소수점 -> 정수 (반올림)

// 기본 연산
fixed_t add_fp(fixed_t x, fixed_t y); // x + y
fixed_t sub_fp(fixed_t x, fixed_t y); // x - y
fixed_t add_fp_int(fixed_t x, int n); // x + n
fixed_t sub_fp_int(fixed_t x, int n); // x - n

// 곱셈/나눗셈
fixed_t mul_fp(fixed_t x, fixed_t y); // x * y
fixed_t mul_fp_int(fixed_t x, int n); // x * n
fixed_t div_fp(fixed_t x, fixed_t y); // x / y
fixed_t div_fp_int(fixed_t x, int n); // x / n

#endif

 

// fixed-point.c

#include "fixed-point.h"
#include <stdint.h> // int64_t 사용

// 변환
fixed_t int_to_fp(int n)
{
    return n * F;
}

int fp_to_int(int x)
{
    return x / F;
}

int fp_to_int_round(int x)
{
    return (x >= 0) ? (x + F / 2) / F : (x - F / 2) / F;
}

// 기본 연산
fixed_t add_fp(int x, int y)
{
    return x + y;
}

fixed_t sub_fp(int x, int y)
{
    return x - y;
}

fixed_t add_fp_int(int x, int n)
{
    return x + n * F;
}

fixed_t sub_fp_int(int x, int n)
{
    return x - n * F;
}

// 곱셈 / 나눗셈
fixed_t mul_fp(int x, int y)
{
    return ((int64_t)x) * y / F;
}

fixed_t mul_fp_int(int x, int n)
{
    return x * n;
}

fixed_t div_fp(int x, int y)
{
    return ((int64_t)x) * F / y;
}

fixed_t div_fp_int(int x, int n)
{
    return x / n;
}

---

4. thread 구조체 수정 & 초기화 

---

@ 코드 보기 

struct thread
{
	/* Owned by thread.c. */
	tid_t tid;				   /* Thread identifier. */
	enum thread_status status; /* Thread state. */
	char name[16];			   /* Name (for debugging purposes). */
	int priority;			   /* 기부받은 우선순위 */
	int original_priority;	   /* 원래의 우선순위 */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem; /* List element. */
	struct list donations; /* 자신한테 기부해준 리스트 */
	struct lock *pending_lock;

	int nice;			// 양보하려는 정도?
	fixed_t recent_cpu; // CPU를 얼마나 점유했나?
	struct list_elem all_elem;
	struct semaphore *fork_sema; // fork 동기화를 위한 세마포어

#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint64_t *pml4; /* Page map level 4 */

#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
#endif

	/* Owned by thread.c. */
	struct intr_frame tf; /* Information for switching */
	unsigned magic;		  /* Detects stack overflow. */
};

 

static void
init_thread(struct thread *t, const char *name, int priority)
{
	ASSERT(t != NULL);
	ASSERT(PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT(name != NULL);

	memset(t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy(t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t)t + PGSIZE - sizeof(void *);
	t->priority = priority;
	t->original_priority = priority;
	t->pending_lock = NULL;
	t->magic = THREAD_MAGIC;

	if (thread_mlfqs)
	{
		if (t == initial_thread)
		{
			// 최초 스레드는 기본값으로 초기화
			t->nice = 0;
			t->recent_cpu = int_to_fp(0);
		}
		else if (t != initial_thread)
		{
			// 새로 생성되는 스레드는 부모(현재 스레드)의 값을 상속받음
			t->nice = thread_current()->nice;
			t->recent_cpu = thread_current()->recent_cpu;
		}
	}

	list_init(&t->donations);
	list_push_back(&all_list, &t->all_elem);
}

 

구조체를 수정했으니 초기화 역시 수정해 주어야 한다.

 

---

5. 분기 설정

---

 

mlfqs에서는 priority donation을 사용하지 않고, donation에서도 mlfqs를 사용하지 않기 때문에 분기를 설정해 주어야 한다. 

분기는thread_mlfqs라는 bool 변수로 관리한다.

@코드 보기

 

thread.c

/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
	// 고급 스케줄러에서는 priority를 수동으로 설정할 수 없기 때문에 무시
	if (thread_mlfqs)
		return;

	// (기존 donation 처리 등은 기본 스케줄러일 때만 유효)
	struct thread *cur = thread_current();
	thread_current()->original_priority = new_priority;

	if (list_empty(&cur->donations))
	{
		cur->priority = new_priority;
	}
	else
	{
		int first_priority = list_entry(list_front(&cur->donations), donation, elem)->priority;
		if (first_priority > new_priority)
			cur->priority = first_priority;
		else
			cur->priority = new_priority;
	}

	compare_cur_next_priority();
}

void thread_tick(void)
{
	struct thread *t = thread_current();

	/* Update statistics. */
	if (t == idle_thread)
		idle_ticks++;
#ifdef USERPROG
	else if (t->pml4 != NULL)
		user_ticks++;
#endif
	else
		kernel_ticks++;

	// 매 timer tick마다 MLFQS 업데이트 트리거
	if (thread_mlfqs)
	{
		mlfqs_on_tick(); // running thread의 recent_cpu++, 주기적 갱신 처리
	}
	/* Enforce preemption. */
	if (++thread_ticks >= TIME_SLICE)
		intr_yield_on_return();
}

tid_t thread_create(const char *name, int priority,
					thread_func *function, void *aux)
{
	struct thread *t;
	tid_t tid;

	ASSERT(function != NULL);

	/* Allocate thread. */
	t = palloc_get_page(PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;

	/* Initialize thread. */
	init_thread(t, name, priority);

	// 2. 고급 스케줄러가 켜져 있다면:

	// MLFQS가 활성화되어 있다면, 새 스레드의 priority를 자동 계산해줌
	if (thread_mlfqs)
	{
		update_priority(t); // recent_cpu, nice 기반으로 계산
	}

	tid = t->tid = allocate_tid();

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t)kernel_thread;
	t->tf.R.rdi = (uint64_t)function;
	t->tf.R.rsi = (uint64_t)aux;
	t->tf.ds = SEL_KDSEG;
	t->tf.es = SEL_KDSEG;
	t->tf.ss = SEL_KDSEG;
	t->tf.cs = SEL_KCSEG;
	t->tf.eflags = FLAG_IF;

	/* Add to run queue. */
	thread_unblock(t);

	struct thread *cur = thread_current();

	if (compare_priority(&t->elem, &cur->elem, NULL))
		thread_yield();

	return tid;
}

 

기존의 코드들에 분기를 나누어 적절히 조절하였다.

 

---

6. 구현

---

6.1. mlfqs_on_tick

---

@코드 보기

timer.c

/* mlfqs에서 틱마다 발생하는 상황에 대응하기 위한 함수입니다 */
void mlfqs_on_tick()
{
	update_recent_cpu();

	if (timer_ticks() % TIMER_FREQ == 0)
	{
		update_load_avg();
		update_recent_cpu_all();
	} // 모든 스레드 recent_cpu 계산

	if (timer_ticks() % 4 == 0)
	{
		update_all_priority();
		compare_cur_next_priority();
	}
}

mlfqs에서 매 틱마다 할 행동을 결정한다. 

---

6.2. update_recent_cpu

---

@ 코드 보기

thread.c

/* 인자로 받은 스레드의 recent_cpu를 수정하는 함수입니다.
모든 스레드 업데이트에서 사용하기 위해 인자를 void를 thread로 수정했습니다 */
void update_recent_cpu(void)
{
	thread_current()->recent_cpu = add_fp_int(thread_current()->recent_cpu, 1);
}

인자로 받은 스레드의 recent_cpu를 수정한다. 

 

---

6.3. update_load_avg

---

@ 코드 보기 

thread.c

/* load_avg를 계산하는 함수입니다. mlfqs_on_tick에서 1초마다 호출되어야 합니다
다음 수식을 구현해야 합니다
load_avg = (59/60) * load_avg + (1/60) * ready_threads_size
*/
void update_load_avg(void)
{
	int ready_threads = list_size(&ready_list);
	if (thread_current() != idle_thread)
		ready_threads++;

	fixed_t term1 = div_fp_int(mul_fp_int(load_avg, 59), 60); // (59 * load_avg) / 60
	fixed_t term2 = mul_fp_int(div_fp_int(int_to_fp(1), 60), ready_threads);

	load_avg = add_fp(term1, term2);
}

 

load_avg를 계산한다. 

위에서 언급한 수식을 생성한 고정소수점 함수를 사용하여 구현한다.

---

6.4. update_recent_cpu_all

---

@ 코드 보기

thread.c

/* 모든 스레드의 CPU 점유율을 계산하는 함수입니다.
mlfqs_on_tick에서 사용되어야 합니다 */
void update_recent_cpu_all(void)
{
	/*
	recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice
	*/
	struct list_elem *e;
	for (e = list_begin(&all_list); e != list_end(&all_list); e = list_next(e))
	{
		struct thread *entry = list_entry(e, struct thread, all_elem);
		if (entry->status == THREAD_DYING || entry == idle_thread)
			continue;
		fixed_t coeff = div_fp(
			mul_fp_int(load_avg, 2),
			add_fp_int(mul_fp_int(load_avg, 2), 1));

		entry->recent_cpu = add_fp(
			mul_fp(coeff, entry->recent_cpu),
			int_to_fp(entry->nice));
	}
}

 

모든 스레드의 recent_cpu 를 계산한다. 

매 1초마다 계산되어야 하기 때문에, mlfqs_on_tick에서 사용되어야 한다.

식 그대로 쓰면 된다.

 @warning
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice

---

6.6. update_priority

---

@ 코드 보기

thread.c

/* 인자로 받은 스레드의 우선순위를 계산하는 함수입니다.
모든 스레드 업데이트에서 사용하기위해 인자를 void 에서 thread로 수정했습니다 */
void update_priority(struct thread *thread) // 4틱마다 계산
{
	if (thread == idle_thread)
		return;

	int new_priority = PRI_MAX - fp_to_int_round(div_fp_int(thread->recent_cpu, 4)) - (thread->nice * 2);

	// Clamp to [PRI_MIN, PRI_MAX]
	if (new_priority > PRI_MAX)
		new_priority = PRI_MAX;
	if (new_priority < PRI_MIN)
		new_priority = PRI_MIN;

	thread->priority = new_priority;
}

인자로 받은 스레드의 우선순위를 계산한다. 

4틱마다 아래의 공식대로 우선순위를 계산하게 된다.

@warning
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

 

---

6.6. update_all_priority

---

@ 코드 보기

thread.c

/* 모든 스레드의 우선순위를 계산하는 함수입니다.
mlfqs_on_tick에서 사용되어야 합니다 */
void update_all_priority(void)
{

	struct list_elem *e;
	for (e = list_begin(&all_list); e != list_end(&all_list); e = list_next(e))
	{
		struct thread *entry = list_entry(e, struct thread, all_elem);
		if (entry->status == THREAD_DYING || entry == idle_thread)
			continue;
		update_priority(entry);
	}
	compare_cur_next_priority();
}

모든 스레드의 우선순위를 계산한다. 모든 리스트를 순회하며 update_priority를 호출한다.

---

7.인터페이스 

---

@ 코드 보기

thread.c

/* Returns the current thread's priority. */
int thread_get_priority(void)
{
	return thread_current()->priority;
}

/* Sets the current thread's nice value to NICE. */
void thread_set_nice(int nice UNUSED)
{
	struct thread *cur = thread_current();
	cur->nice = nice;

	// nice값이 바뀌었으니 priority도 다시 계산함
	update_priority(cur);

	// 만약 ready_list에 더 높은 priority가 있으면 양보
	compare_cur_next_priority();
}

/* Returns the current thread's nice value. */
int thread_get_nice(void)
{
	return thread_current()->nice;
}

/* Returns 100 times the system load average. */
int thread_get_load_avg(void)
{
	return fp_to_int_round(load_avg * 100);
}

/* Returns 100 times the current thread's recent_cpu value. */
int thread_get_recent_cpu(void)
{
	return fp_to_int_round(thread_current()->recent_cpu * 100);
}