Project_1 : Threads - Priority Scheduling(1)

첫 번째 Pintos 프로젝트는 스레드와 관련한 것으로 Alarm Clock, Priority Scheduling, Advanced Scheduler 세 가지로 구분된다.

그중 Priority Scheduling의 목표는 "Implement priority scheduling and priority donation in Pintos."이다.

 

Priority Scheduling 구현의 기본 아이디어는 다음과 같다.

만약 현재 프로세서를 사용 중인 스레드보다 높은 우선순위를 가진 스레드가 ready_list에 추가된다면, 

현재 스레드는 프로세서를 즉시 새로운 스레드에게 넘겨야 한다.

또한, 스레드들이 Semaphore, Lock, 또는 Condition Variable들을 기다리고 있을 때,

높은 우선순위를 가진 스레드가 가장 먼저 활성화되어야 한다.

 

Pintos에서 스레드 우선순위 범위는 PRI_MIN(0) ~ PRI_MAX(63)이다.

우선순위 0이 가장 낮은 우선순위이고 우선순위 63이 가장 높은 우선순위이다.

초기 스레드 우선순위는 thread_create( ) 함수의 인수로 전달된다.

다른 우선순위를 선택할 이유가 없는 경우, PRI_DEFAULT(31)를 사용하면 된다.

우선순위 매크로는 thread/thread.h에 정의되어 있으나 그 값을 변경하면 안 된다.

 

Priority Scheduling의 한 가지 문제는 우선순위 반전(Priority Inversion)이다.

예를 들어, 높은 우선순위, 중간 우선순위, 낮은 우선순위 스레드를 각각 H, M, L이라고 하자.

L이 락(Lock)을 가지고 있고 H가 해당 락이 필요할 때, 만약 M이 ready_list에 있다면 H는 절대 락을 얻을 수 없다.

우선순위가 낮은 L은 CPU 시간을 얻지 못하기 때문이다.

 

해당 문제는 Priority Donation을 통해 해결할 수 있다.

위의 예시에서 H가 우선순위를 L에게 넘겨 L이 잠금을 해제하고, H가 다시 락을 얻는 방식으로 진행하면 된다.

그런데 Priority Donation을 구현하려면 Priority Donation이 요구되는 모든 상황을 고려해야 한다.

다양한 우선순위가 하나의 스레드에 전달되는 Multiple Donations과 Nested Donation도 다루어져야 한다.

(Nested 란? H가 필요한 락을 M이, M이 필요한 락을 L이 가지고 있을 때, M과 L 모두 H의 우선순위를 부여받아야 하는 경우)

다른 어떤 핀토스 동기화 구조보다 락에 대한 Priority Donation을 구현해야만 한다.

 

마지막으로 threads/thread.c 에 있는 스켈레톤 코드를 갖고 스레드가 우선순위를 검사하고 수정할 수 있는 함수를 구현해야 한다.

void thread_set_priority (int new_priority);

현재 스레드의 우선순위를 새 우선순위로 설정한다.
Sets the current thread's priority to new priority.

int thread_get_priority (void);

현재 스레드의 우선순위를 반환한다. 
Returns the current thread's priority. 

 

Priority Scheduling을 구현하기에 앞서, 현재 Pintos 스케줄러가 어떻게 구현되어 있는지 살펴볼 필요가 있다.

Pintos는 리스트를 이용하여 스레드를 관리한다고 하였다.

그렇다면 새로운 스레드를 ready_list에 어떤 방식으로 집어넣는지 확인해보자.

아래 코드는 스레드를 새롭게 생성하거나, BLOCKED 된 스레드를 UNBLOCK 하는 함수들이다.

특별히 우선순위를 고려하지 않고 ready_list 맨 마지막에 스레드를 삽입하는 것을 알 수 있다.

/* 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);	// <- 리스트 맨 마지막에 삽입
	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);		// <- 리스트 맨 마지막에 삽입
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

이제 ready_list에서 스레드를 꺼내는 과정을 살펴보자.

ready_list에서 스레드를 꺼낸다는 것은 현재 CPU를 점유하고 있는 스레드가 CPU를 양보했다는 의미이다.

이러한 양보는 thread_exit( ), thread_yield( ), thread_block( ) 함수를 통해 이루어진다.

아래는 해당 함수 구현 코드이다. 자세히 살펴보면 모두 schedule( ) 함수를 호출하는 것을 알 수 있다.

/* threads/thread.c */

/* PROJECT1: THREADS - Priority Scheduling */

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(). */
	intr_disable ();
	do_schedule (THREAD_DYING);		// <- 결국 schedule( ) 함수 호출
	NOT_REACHED ();
}

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);
	do_schedule (THREAD_READY);		// <- 결국 schedule( ) 함수 호출
	intr_set_level (old_level);
}

static void do_schedule(int status) {
	ASSERT (intr_get_level () == INTR_OFF);
	ASSERT (thread_current()->status == THREAD_RUNNING);
	while (!list_empty (&destruction_req)) {
		struct thread *victim =
			list_entry (list_pop_front (&destruction_req), struct thread, elem);
		palloc_free_page(victim);
	}
	thread_current ()->status = status;
	schedule ();
}

void thread_block (void) {
	ASSERT (!intr_context ());
	ASSERT (intr_get_level () == INTR_OFF);
	thread_current ()->status = THREAD_BLOCKED;
	schedule ();
}

schedule( ) 함수의 주요 목적은 현재 CPU를 점유 중인 스레드와 다음에 실행될 스레드의 상태를 바꾸는 것이다.

이때, 다음에 실행될 스레드는 next_thread_to_run( ) 함수의 의해 결정되며 이는 ready_list 안의 첫 번째 스레드이다.

/* threads/thread.c */

/* PROJECT1: THREADS - Priority Scheduling */

static struct thread * next_thread_to_run (void) {
	if (list_empty (&ready_list))
		return idle_thread;
	else
		return list_entry (list_pop_front (&ready_list), struct thread, elem);		// <- ready_list 맨 앞의 스레드 반환
}

static void schedule (void) {
	struct thread *curr = running_thread ();
	struct thread *next = next_thread_to_run ();

	ASSERT (intr_get_level () == INTR_OFF);
	ASSERT (curr->status != THREAD_RUNNING);
	ASSERT (is_thread (next));
	/* Mark us as running. */
	next->status = THREAD_RUNNING;		// <- 상태 변경

	/* Start new time slice. */
	thread_ticks = 0;

#ifdef USERPROG
	/* Activate the new address space. */
	process_activate (next);
#endif

	if (curr != next) {
		/* If the thread we switched from is dying, destroy its struct
		   thread. This must happen late so that thread_exit() doesn't
		   pull out the rug under itself.
		   We just queuing the page free reqeust here because the page is
		   currently used bye the stack.
		   The real destruction logic will be called at the beginning of the
		   schedule(). */
		if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
			ASSERT (curr != next);
			list_push_back (&destruction_req, &curr->elem); 	
		}

		/* Before switching the thread, we first save the information
		 * of current running. */
		thread_launch (next);
	}
}

정리하자면, 현재 Pintos는 우선순위 고려 없이 FIFO(First Come First Out) 방식으로 ready_list를 관리하고 있다.

그런데 아래 코드에서 확인할 수 있듯이 CPU를 점유 중인 스레드는 특정 시간이 지나면 CPU를 양보하도록 되어 있다.

이를 종합하면 현재 Pintos의 스케줄링 방식은 라운드 로빈이라고 할 수 있다.

/* devices/timer.c */

static void timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_awake(ticks); /* PROJECT1: THREADS - Alarm Clock */
}


/* threads/thread.c */

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++;

	/* Enforce preemption. */
	if (++thread_ticks >= TIME_SLICE)
		intr_yield_on_return ();
}