Project 1 Advanced Scheduler

Main goal

• Implement 4.4 BSD scheduler MLFQ like scheduler without the queues.
• MLFQS (Multi-level Feedback Queue Scheduling) 와 유사한 스케쥴러를 구현한다.

MLFSQS like 일까?

• ❌ Priority의 값에 따라 Ready-Queue 여럿 존재하며, 순위를 기준으로 Ready-Queue를 실행하며, Queue에 여러 쓰레드가 존재할 경우 Round-Robin 으로 큐를 실행한다. (Multi-Level)
• ✅ Priority의 값을 일정 tick 마다 조정한다. (Feedback)

여기서, 우리는 여러개의 Ready_Queue를 관리하는 것이 아니라, 한 개의 all_list 로 feedback system을 관리할 것 이기 때문에 MLFQS like 이라고 표현을 하였다!

priority feedback에 사용되는 식

Priority

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

recent_cpu

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

load_avg

load_avg = (59/60) * load_avg + (1/60) * ready_threads,

추가 함수

fixed_point.h & fixed_point.c

#define F (1 << 14)  // 고정 소수점 표현을 위한 상수, 여기서 14는 소수 부분의 비트 수

int fixed_add(int x, int y);
int fixed_sub(int x, int y);
int fixed_add_int(int x, int n);
int fixed_sub_int(int x, int n);
int fixed_mul(int x, int y);
int fixed_div(int x, int y);
int fixed_mul_int(int x, int y);
int fixed_div_int(int x, int y);
int int_to_fixed(int n);
int fixed_to_int_round(int x);
int fixed_to_int_trunc(int x);

#include <stdint.h>
#include "threads/fixed_point.h"

int int_to_fixed(int n) {
    return n * F;
}

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

int fixed_to_int_round(int x) {
    if (x >= 0) {
        return (x + F / 2) / F;
    } else {
        return (x - F / 2) / F;
    }
}

int fixed_add(int x, int y) {
    return x + y;
}

int fixed_sub(int x, int y) {
    return x - y;
}

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

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

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

int fixed_mul_int(int x, int n) {
    return x * n;
}

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

int fixed_div_int(int x, int n) {
    return x / n;
}

커널에서는 부동소수점 연산을 지원하지 않기 때문에 fixed_point 연산을 사용해야 한다.

이로 인해 실수로 이루어진 recent_cpu, load_avg, decay는 fixed_point 연산을 지원하는 위 수식을 사용해야 한다.

fixed_point란? -> https://velog.io/@junhyeok_kim/PintOS-1-3-Advanced-Scheduler

 

update_priority() & calc_priority()

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

// Priority = PRI_MAX – (recent_cpu/4) – (nice*2)
void 
calc_priority(struct thread *cur) {
	if (cur == idle_thread)  return ;
	int tmp_priority = fixed_to_int_trunc (
		fixed_add_int(fixed_div_int (cur->recent_cpu, -4),
	  	PRI_MAX - cur->nice * 2)
	);
	if (tmp_priority < PRI_MIN) tmp_priority = PRI_MIN;
	if (tmp_priority > PRI_MAX) tmp_priority = PRI_MAX;
	cur->priority = tmp_priority;
}

void 
update_priority() {
	struct list_elem *e;
   	for (e = list_begin (&all_list); e != list_end(&all_list);  e = list_next(e)) {
      	struct thread *t = list_entry(e, struct thread, all_elem);
		calc_priority(t);
	}
}

우선순위를 구해서 thread에 지정해주는 함수.
우선순위를 구하기 위해선 우선 recent_cpu를 최신화해주어야 한다.

그렇게 구한 우선순위를 all_list의 쓰레드를 순회하며 업데이트 해주는 update_priority 또한 작성해줘야 한다.

 

update_recent_cpu() & calc_recent_cpu()

update_recent_cpu()

void update_recent_cpu() {
	struct list_elem *e;
   	for (e = list_begin (&all_list); e != list_end(&all_list);  e = list_next(e)) {
      	struct thread *t = list_entry(e, struct thread, all_elem);
		calc_recent_cpu(t);
	}
}

모든 쓰레드가 담긴 all_list를 순회하며 calc_recent_cpu를 실행해주는 함수이다.

calc_recent_cpu(struct thread *cur)

Priority = PRI_MAX – (recent_cpu/4) – (nice2)
recent_cpu = (2load_avg)/(2load_avg+1)recent_cpu + nice
load_avg = (59/60)load_avg + (1/60)ready_threads

// recent_cpu = (2*load_avg)/(2*load_avg+1)*recent_cpu + nice
void 
calc_recent_cpu(struct thread *cur) {
	if (cur == idle_thread) return ;
	int tmp = fixed_mul_int(load_avg,2);
	int decay = fixed_div(tmp , fixed_add_int(tmp,1));
	int ret = fixed_add_int(fixed_mul(decay , cur->recent_cpu) , cur->nice);
	if ((ret >> 31) == (-1) >> 31) {
		ret = 0;
	}
	cur->recent_cpu = ret;
}

idle 쓰래드가 아닐 경우에 최신화된 decay를 사용해 recent_cpu를 업데이트 해주는 코드이다.
중간에 쉬프트 연산을 진행하는 이유는 recent_cpu는 음수가 될 수 없어 맨 앞 부호비트가 음수라면 0으로 고정해주는 로직이다.

calc_load_avg()

load_avg = (59/60) load_avg + (1/60) ready_threads,

// load_avg = (59/60)*load_avg + (1/60)*ready_threads
void
calc_load_avg(void) {
	int list_length	= (int) list_size(&ready_list);
	list_length = (thread_current() == idle_thread) ? list_length : list_length + 1;
	load_avg = fixed_add(fixed_mul     (fixed_div (int_to_fixed (59),int_to_fixed (60)), load_avg), 
               	         fixed_mul_int (fixed_div (int_to_fixed (1), int_to_fixed (60)), list_length));
}

load_avg를 계산해서 최신화해주는 함수.

수정해줘야 하는 함수

우리가 구현할 MLFQS like에서는 priority를 donate하는 방식이 아닌 사전에 협의된 방적식에 의거해서 priority를 설정해준다.
그래서 MLFQS 를 테스트 할때는 해당 기능을 잠시 비활성화 해줘야 한다.

thread_init & thread_create & thread_exit

thread_init

void // 쓰레드 초기화
thread_init (void) {

	.
    .
    .
    
	lock_init (&tid_lock);			
	list_init (&ready_list);		
	list_init (&sleep_list);		
	list_init (&all_list);			// all_list 를 초기화한다.
	list_init (&destruction_req);	
	
    .
    .
    .
    
	list_push_back(&all_list, &(initial_thread->all_elem)); 	// main_thread 또한 all_list에 넣어줘야함



	lock_init(&sleep_lock);
}

모든 쓰레드를 순회하기 위해선 all_list를 추가해줘야 한다.

thread_create

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

	ASSERT (function != NULL);					

	.
    .
    .
    
	list_push_back(&all_list, &t->all_elem);	// 이 부분 추가

	/* Add to run queue. */
	thread_unblock(t);							
	if (!thread_mlfqs) preempt();	// preempt 조건 걸어주기

	return tid;									
}

thread_create 함수가 실행될때 현재 쓰레드를 all_list에 추가해줘야 한다.

thread_exit

void
thread_exit (void) {
	ASSERT (!intr_context ());					
#ifdef USERPROG
	process_exit ();							
#endif										

	/* Just set our status to dying and schedule another process.
	   We will be destroyed during the call to schedule_tail(). */
	list_remove(&thread_current()->all_elem);	// 쓰레드가 종료될때 all_list에서 제거
	intr_disable ();							
	do_schedule (THREAD_DYING);					
	NOT_REACHED ();								
}

쓰레드가 종료될때 all_list에서 해당 쓰레드를 제거해주는 로직을 추가해줘야 한다.

lock_acquire & lock_release & thread_set_priority

lock_acquire (struct lock *lock)

void
lock_acquire (struct lock *lock) {
  	ASSERT (lock != NULL);
  	ASSERT (!intr_context ());
  	ASSERT (!lock_held_by_current_thread (lock));
   struct thread *cur = thread_current ();
  	if (lock->holder) {                     
  	  	cur->wait_on_lock = lock;            
  	  	list_insert_ordered (&lock->holder->donations, &cur->d_elem, compare_donation_priority, NULL);  
      if (!thread_mlfqs)	// mlfqs는 priority donate를 직접 해주지 않는다.
  	  	   donate();                             
  	}

  	sema_down (&lock->semaphore);
  
  	cur->wait_on_lock = NULL;
  	lock->holder = cur;                     
}

lock_release (struct lock *lock)

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));
   struct thread *cur = thread_current();
   struct list_elem *e;

   if (!thread_mlfqs) { // 이 부분 추가
      for (e = list_begin (&cur->donations); e != list_end (&cur->donations);) {
         struct thread *t = list_entry (e, struct thread, d_elem);
         if (t->wait_on_lock == lock)
            e = list_remove (&t->d_elem);
         else
            e = list_next(&t->d_elem);
      }
      update_donation();
   }
	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

thread_set_priority(int new_priority)

void
thread_set_priority (int new_priority) {
	if (thread_mlfqs) return;
	thread_current()->init_priority = new_priority;
	update_donation();
	preempt();
}

mlfqs like 옵션이 켜졌을때 donate관련 기능을 비활성화 시켜줘야 한다.

timer_interrupt

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

	if (thread_mlfqs) {

		// In every clock tick, increase the running thread’s recent_cpu by one.
		incr_recent_cpu();

		// In every fourth tick, recompute the priority of all threads
		if (ticks % TIME_SLICE == 0) {
			update_priority();
		}

		// In every second, update every thread’s recent_cpu
		if (ticks % TIMER_FREQ == 0) {
			calc_load_avg();
			update_recent_cpu();
		}
    }

	if (get_global_ticks() <= ticks) {
		thread_wakeup(ticks);
	}
}

이렇게 작성된 함수를 timer_interrupt에 조건에 맞게 실행해주면 된다.

 

 

감격의 pintOS thread All pass

어떻게든 마치긴 했지만 아직 코드에 대한 완벽한 이해가 이뤄졌다곤 할 수 없는것 같다.

시간이 좀만 더 있었다면 처음부터 다시 짜보고싶은 마음이 굴뚝같다.