mlfqs 구현

nice,recent_cpu thread 구조에 추가하기

struct thread {
...
	//mlfqs
	int nice;
	int recent_cpu;
...
};

nice,recent_cpu 초기화하기

• 초기 스레드의 nice, recent_cpu 값은 0

static void init_thread (struct thread *t, const char *name, int priority) {
...
	t->nice = 0;
	t->recent_cpu = 0;
...
}

load_average

시스템이 얼마나 바쁜지 나타낸다.
load_avg = (59/60) load_avg + (1/60) ready_threads

• load_avg는 시스템 틱 카운터가 1초의 배수에 도달할 때, 즉 timer_ticks () % TIMER_FREQ == 0일 때 정확히 업데이트되어야 한다.
• 다른 시간에는 업데이트되지 않아야 한다.
• thread_get_load_avg()를 구현해야 한다.

load_avg선언

• int load_avg; 전역 변수로 thread.c 상단에 선언한다.
  load_avg 초기화
• 부팅시 0으로 설정된다.
• load_avg = 0; `thread_init(void)에서 초기화 해준다.

calculate_load_avg(void)

void calculate_load_avg(void)
{
	int ready_threads = list_size(&ready_list);
	if (thread_current() != idle_thread)
		ready_threads++;
	load_avg =add_fixed_point( multiply_fixed_point (divide_fixed_point_integer(convert_to_fixed_point(59), 60), load_avg),
                     multiply_fixed_point_integer (divide_fixed_point_integer(convert_to_fixed_point(1) , 60), ready_threads));
}

pintOS는 성능 향상을 위해 부동소수점연산을 지원하지 않기 때문에 직접 고정 소수점 연산을 해야한다.

매크로를 사용하기 위해서
#include "threads/fixed-point.h"를 추가해준다.

#define F (1 << 14) // 2^14 = 16384
#define convert_to_fixed_point(n) (n * F)
#define convert_to_integer_towards_zero(x) (x / F)
#define convert_to_integer_towards_nearest(x) (x >= 0 ? ((x + F / 2) / F) : ((x - F / 2) / F))
#define add_fixed_point(x, y) (x + y)
#define add_fixed_point_integer(x, n) (x + n * F)
#define subtract_fixed_point(x, y) (x - y)
#define subtract_fixed_point_integer(x, n) (x - n * F)
#define multiply_fixed_point(x, y) (((int64_t) x) * y / F)
#define multiply_fixed_point_integer(x, n) (x * n)
#define divide_fixed_point(x, y) (((int64_t) x) * F / y)
#define divide_fixed_point_integer(x, n) (x / n)

int thread_get_load_avg(void)
{

	return convert_to_integer_towards_nearest(multiply_fixed_point_integer(load_avg, 100));
	
}

static void timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_wake_up (ticks);

	if(thread_mlfqs){
		// timer_ticks 는 10ms 마다 호출되므로 10ms 마다 load_avg를 업데이트
		// 1초 마다 계산
		if(timer_ticks()%TIMER_FREQ==0){
			calculate_load_avg();
		}
	}
}

이렇게 하면 pass tests/threads/mlfqs/mlfqs-load-1 통과!!

recent_cpu계산하기

• 매 timer interrupt마다 현재 실행중인 프로세스의 recent_cpu 값을 1씩 증가시킨다.
• 매초마다 모든 스레드의 recent_cpu를 업데이트 한다.
  • 모든 스레드를 조작해야하기 때문에 모든 스레드를 담을 allist를 추가/초기화한다.
    • static struct list sleep_list; 추가
    • thread_init(void)에 초기화 list_init (&all_list);
    • 스레드 구조체에 all리스트의 요소를 추가한다. struct list_elem allelem;
    • idle thread를 제외한 모든 스레드 삽입하기

      static void init_thread (struct thread *t, const char *name, int priority) {
	...

	t->nice = 0;
	t->recent_cpu = 0;
	if (strcmp(name, "idle"))
		list_push_back(&all_list, &t->allelem);
        ...
}

DYING 예정인 스레드 all_list에서도 제거

static void schedule(void)
{
	...
	if (curr && curr->status == THREAD_DYING && curr != initial_thread)
	{
		ASSERT(curr != next);
		list_push_back(&destruction_req, &curr->elem);
		list_remove(&curr->a_elem);
	}
	...
}

static void timer_interrupt (struct intr_frame *args UNUSED)에 코드 추가

static void timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_wake_up (ticks);

	if(thread_mlfqs){
		// timer_ticks 는 10ms 마다 호출되므로 10ms 마다 load_avg를 업데이트
		// 1초 마다 계산
	
		if(timer_ticks()%TIMER_FREQ==0){
			calculate_load_avg();
			calculate_recent_cpu();
		}
		
		recent_cpu_plus();
	}
}

recent_cpu_plus();, calculate_recent_cpu();함수 구현

void calculate_recent_cpu(void)
{
	//recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice;
	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, allelem);
		t->recent_cpu = multiply_fixed_point (divide_fixed_point (multiply_fixed_point_integer (load_avg, 2), 
		add_fixed_point_integer (multiply_fixed_point_integer (load_avg, 2), 1)), t->recent_cpu) + convert_to_fixed_point(t->nice);
		t->priority = calculate_priority(t);
	}

}

void recent_cpu_plus(void){
	struct thread *t = thread_current();
	if (t == idle_thread)
		return;
	t->recent_cpu = add_fixed_point_integer(t->recent_cpu, 1);
}

int thread_get_recent_cpu(void)
{
	return convert_to_integer_towards_zero(multiply_fixed_point_integer(thread_current()->recent_cpu, 100));
}

현재 cpu사용량을 구하기 위해 nice 설정함수 구현

void thread_set_nice(int nice)
{
	struct thread *t = thread_current();
	t->nice = nice;
	thread_set_priority(calculate_priority(t));
}

nice 변경시 우선순위 바뀔 수 있으니 바뀐 우선순위 설정해주기

구한 nice get

int thread_get_nice(void)
{
	return thread_current()->nice;
}

바뀐 우선순위 계산하기

• 4번째 틱마다 모든 스레드의 우선순위를 다시 계산한다.

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();		// 실행 중인 프로세스의 CPU 사용량을 업데이트 
	thread_wakeup(ticks);
	if(thread_mlfqs){
		// timer_ticks 는 10ms 마다 호출되므로 10ms 마다 load_avg를 업데이트
		// 1초 마다 계산
		if(timer_ticks()%4 == 0){
			recalculate_all_priority();
			if(timer_ticks()%TIMER_FREQ==0){
				calculate_load_avg();
				calculate_recent_cpu();
			}
		}
		recent_cpu_plus();
	}
}

void recalculate_all_priority(void)
{
	if(list_empty(&all_list))
		return;
	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, allelem);
		t->priority = calculate_priority(t);
	}
}

int calculate_priority(struct thread *t){
	int temp = PRI_MAX - convert_to_integer_towards_nearest(divide_fixed_point(t->recent_cpu, convert_to_fixed_point(4))) - t->nice * 2;
	if (temp > PRI_MAX)
		temp = PRI_MAX;
	else if (temp < PRI_MIN)
		temp = PRI_MIN;
	return temp;
}

void calculate_load_avg(void);
void calculate_recent_cpu(void);
void recalculate_all_priority(void);
int calculate_priority(struct thread *t);

header에 선언

void thread_wake_up(int64_t os_ticks)
{
	if (list_empty(&sleep_list))
		return;
	struct thread *t, *curr;
	enum intr_level old_level;

	old_level = intr_disable();
	while (!list_empty(&sleep_list))
	{
		t = list_entry(list_front(&sleep_list), struct thread, elem);
		if (t->wake_up_tick > os_ticks)
			break;
		list_pop_front(&sleep_list);
		list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
		t->status = THREAD_READY;
	}
	// curr = thread_current();
	// if (curr != idle_thread)
	// {
	// 	if (curr->priority < list_entry(list_front(&ready_list), struct thread, elem)->priority)
	// 	{
	// 		thread_yield();
	// 	}
	// }

	intr_set_level(old_level);
} 로 주석처리

이렇게 하면 ALLPASS

새벽 4:30 정리 완료 ,,,,