Project_1 : Threads - Priority Scheduling(2)

이제부터 본격적으로 Priority Scheduling을 구현해보도록 하겠다.

가장 먼저 우선순위가 가장 높은 스레드가 CPU를 점유할 수 있도록 만들어야 한다.

이를 위해 ready_list 관련 함수들을 수정하고자 한다. ready_list는 CPU를 사용하고자 대기하고 있는 스레드들을 관리하는 리스트이다.

해당 리스트에서 스레드를 꺼낼 때 우선순위가 가장 높은 스레드를 꺼낼 수 있다면 상기의 목적을 달성할 수 있다.

 

이를 손쉽게 가능하게 하는 방법은 ready_list를 우선순위 기준으로 내림차순 정렬하는 것이다.

따라서 ready_list에 새로운 스레드를 넣을 때, 우선순위를 고려하고자 한다.

우선순위를 고려하여 ready_list에 스레드를 넣는다면, 리스트는 항상 정렬된 상태를 유지할 수 있게 된다.

또한, ready_list에서 스레드 꺼내는 방식을 추가로 수정하지 않더라도 항상 우선순위가 높은 스레드를 꺼낼 수 있게 된다.

 

삽입 과정에서 list_insert_ordered( ) 함수를 이용하고자 한다.

해당 함수는 Pintos에서 리스트를 다루기 위해 미리 구현된 함수이다.

list_insert_ordered( ) 함수의 인자로는 스레드를 넣을 리스트와, 넣고자 하는 스레드, 삽입시 기준이 될 함수가 들어간다.

해당 함수의 내부를 살펴보면 list_insert( ) 함수를 호출하는 것을 알 수 있다.

그리고 list_insert( ) 함수의 결과, 두 번째 인자에 해당하는 스레드가첫 번째 인자에 해당하는 스레드 앞에 위치하게 된다.

그런데 앞서 ready_list는 우선순위가 높은 순으로 정렬되어 있어야 한다고 하였다.

따라서 list_insert_ordered( ) 함수 내부의 less( ) 함수는 아래와 같이 elem > e 일 때 true를 반환하는 함수여야 한다.

/* threads/thread.c */

/* PROJECT1: THREADS - Priority Scheduling */

bool thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED) {
    return list_entry (l, struct thread, elem)->priority > list_entry (s, struct thread, elem)->priority;
}

 

이제 이 내용을 바탕으로 ready_list에 스레드를 삽입하는 과정을 수정하고자 한다.

아래 thread_yield( ) 함수와, thread_unblock( ) 함수 코드에서 list_push_back( ) 함수를 주석 처리하였다.

그리고 새롭게 list_insert_orered( ) 함수를 넣어주었다.

/* threads/thread.c */

/* PROJECT1: THREADS - Priority Scheduling */

void thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		// list_push_back (&ready_list, &curr->elem);
		list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, 0);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

void thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t));

	old_level = intr_disable ();
	ASSERT (t->status == THREAD_BLOCKED);
	// list_push_back (&ready_list, &t->elem);
	list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

 

그런데 추가적으로 고려해야 할 사항이 있다.

새롭게 ready_list에 삽입된 스레드의 우선순위가 현재 CPU를 점유하고 있는 스레드의 우선순위보다 높다면 CPU 점유를 넘겨야 한다.

이를 위해 ready_list의 맨 앞 스레드의 우선순위와 현재 CPU를 점유하고 있는 스레드의 우선순위를 비교하는 함수를 만들었다.

그리고 이를 thread_create( )와 thread_set_priority( ) 함수에 추가해주었다.

/* threads/thread.c */

/* PROJECT1: THREADS - Priority Scheduling */

void thread_test_preemption (void){
    if (!list_empty (&ready_list) && 
    thread_current ()->priority < 
    list_entry (list_front (&ready_list), struct thread, elem)->priority)
        thread_yield ();
}

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);
	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);
	thread_test_preemption();

	return tid;
}

void thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	thread_test_preemption();
}

 

지금까지의 과정을 통해 우선순위가 가장 높은 스레드가 CPU를 점유할 수 있게 되었다.

터미널의 다음과 같이 입력하면 결과를 확인할 수 있다.