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

#include <stdint.h>

#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 int_to_fixed(int n);
int fixed_to_int_round(int x);
int fixed_to_int_trunc(int x);
int fixed_div_int (int x, int n);
int fixed_mul_int (int x, int n);

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

// fixed_point 간 덧셈
int fixed_add(int x, int y) { 
    return x + y;
}
// fixed_point 간 뺄셈
int fixed_sub(int x, int y) {
    return x - y;
}

// fixed_point + 정수 
int fixed_add_int(int x, int n) {
    return x + n * F;
}

// fixed_point - 정수
int fixed_sub_int(int x, int n) {
    return x - n * F;
}

// fixed_point끼리 곱하기
int fixed_mul(int x, int y) {
    return ((int64_t) x) * y / F;
}

// fixed_point끼리 나누기
int fixed_div(int x, int y) {
    return ((int64_t) x) * F / y;
}

// 정수를 fixed_point로
int int_to_fixed(int n) {
    return n * F;
}

// fixed_point * 정수
int fixed_mul_int (int x, int n) {
  return x * n;
}

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

// fixed_point를 정수로 바꾸되, 반올림처리
int fixed_to_int_round(int x) {
    if (x >= 0) {
        return (x + F / 2) / F;
    } else {
        return (x - F / 2) / F;
    }
}

// fixed_point를 정수 바꾸되, 내림
int fixed_to_int_trunc(int x) {
    return x / F;
}

이전 포스팅에서 언급 했듯이, recent_cpu , load_avg 및 decay는 fixed_point이기 때문에 fixed_point 와 정수를 연산하려면 위와 같은 함수를 사용하여 연산하여야 합니다.

calc_all_priority() & calc_priority()

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

void
calc_all_priority() {
	// In every fourth tick, recompute the priority of all threads
	// priority = PRI_MAX – (recent_cpu / 4) – (nice * 2)
	struct list_elem *e;
	struct thread *cur;
    for (e = list_begin (&all_list); e != list_end (&all_list); e = list_next (e)) {
    	cur = list_entry (e, struct thread, allelem); 
		calc_priority(cur);
	}
}

void
calc_priority(struct thread *cur) {
	// In every fourth tick, recompute the priority of all threads
	// priority = PRI_MAX – (recent_cpu / 4) – (nice * 2)
	if(cur==idle_thread) return;
	int tmp = fixed_to_int_trunc (
		fixed_add_int(fixed_div_int (cur->recent_cpu, -4),
	  	PRI_MAX - cur->nice * 2)
	);
	if (tmp > PRI_MAX) {
		tmp = PRI_MAX;
	} else if (tmp < PRI_MIN) {
		tmp = PRI_MIN;
	}
	cur->priority = tmp;
}

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

calc_all_recent_cpu() & calc_recent_cpu()

calc_all_recent_cpu()

void
calc_all_recent_cpu() {
	// In every second, update every thread’s recent_cpu
	// recent_cpu = decay * recent_cpu + nice,
	struct list_elem *e;
	struct thread *cur;
    for (e = list_begin (&all_list); e != list_end (&all_list); e = list_next (e)) {
    	cur = list_entry (e, struct thread, allelem);
		calc_recent_cpu(cur);
	}
}

모든 쓰레드가 담긴 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

void
calc_recent_cpu(struct thread *cur) {
	// In every second, update every thread’s recent_cpu
	// recent_cpu = decay * recent_cpu + nice,
	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를 업데이트 해주는 코드이다.

load_avg

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

void
calc_load_avg() {
	int ready_threads;
  
  	if (thread_current () == idle_thread)
    	ready_threads = list_size (&ready_list);
  	else
    	ready_threads = list_size (&ready_list) + 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)), ready_threads));
}

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

수정해줘야 하는 함수

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

thread_init & thread_create & thread_exit

thread_init

void
thread_init (void) {
	ASSERT (intr_get_level () == INTR_OFF);

	/* Reload the temporal gdt for the kernel
	 * This gdt does not include the user context.
	 * The kernel will rebuild the gdt with user context, in gdt_init (). */
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);

	/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&sleep_list);
	list_init (&destruction_req);
	list_init (&all_list); // all_list 추가

	/* Init global_ticks to track the minimum ticks */
	global_ticks = INT64_MAX; // global_ticks의 타입은 

	/* Set up a thread structure for the running thread. */
	initial_thread = running_thread ();
	init_thread (initial_thread, "main", PRI_DEFAULT);
	list_push_back(&all_list, &(initial_thread->allelem)); // all_list 추가
	initial_thread->status = THREAD_RUNNING;
	initial_thread->tid = allocate_tid ();

모든 쓰레드를 순회하기 위해선 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->allelem); // 이 부분 추가

	/* Add to run queue. */
	thread_unblock (t);
	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()->allelem); // 이부분 추가
	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();

	// thread_mlfqs 일때만 실행되도록
	if (thread_mlfqs) {	
		if (lock->holder) {
			cur->wait_on_lock = lock;
		}
		sema_down (&lock->semaphore); // mlfqs면 도네이트 안하고 바로 리턴해야함
		lock->holder = cur;
		lock->holder->wait_on_lock = NULL;
		return; // mlfqs면 도네이트 안하고 바로 리턴해야함
	}

	if (lock->holder) {
		cur->wait_on_lock = lock;
		list_insert_ordered(&lock->holder->donation_list, &cur->donation_elem,cmp_priority_by_donation_elem,NULL);
		// 그러면, list 내에서 next,prev 설정을 자동적으로 해주겠구나.
		donate();
	}

	sema_down (&lock->semaphore);
	cur->wait_on_lock = NULL;     // sema down이 끝나면, 현재 cur는 작업을 끝낸 것 이므로 기다리는 것이 없음.
	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 list_elem *e;
    struct thread *cur = thread_current ();

  	if (thread_mlfqs) {
		lock->holder = NULL;
    	sema_up (&lock->semaphore);
    	return;
  	}

	/* donation 리스트를 순회하며 */
    for (e = list_begin (&cur->donation_list); e != list_end (&cur->donation_list); e = list_next (e)){
		struct thread *t = list_entry (e, struct thread, donation_elem);
		/* 인자로 받은 lock을 원해서 donate를 한 경우라면 */
		if (t->wait_on_lock == lock)
			list_remove (&t->donation_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 ()->original_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();
		if (timer_ticks() % 4 == 0) {
			// 모든 스레드에 대해 이거 재계산 하라함
			calc_all_priority();
		}
		if (timer_ticks() % TIMER_FREQ == 0) {
			calc_all_recent_cpu();
			calc_load_avg();
		}
	}

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

---

😊 도움을 준 고마운 사람들 🥳
김광윤 : https://github.com/leorivk
정승호 : https://github.com/seungho-jg
황연경 : https://github.com/yunnn426
전병준 : https://github.com/jun9898