Priority Scheduling

thread.h

struct thread {
	// 동일 코드...
	int64_t wakeup_tick;			/* 깨워야 할 tick */

	int base_priority; // 기존 우선순위
	struct lock* waiting_lock; // 대기중인 lock
	struct list_elem donation_elem; // 내가 다른 스레드의 donation_list에 들어갈 때 쓰이는 원소
	struct list donation_list; // 나에게 donation해준 스레드들의 리스트
	// 동일 코드...
};

구조체 필드가 저렇게 4개가 되어야하는 이유에 대한 그림 설명

구조체 필드가 저렇게 4개가 되어야하는 이유에 대한 그림 설명

thread.c

init_thread()

static void
init_thread (struct thread *t, const char *name, int priority) {
	// 동일 코드...
	t->base_priority = priority;
	t->waiting_lock = NULL;
	// 동일 코드...
}

thread_create()

tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	// 동일한 코드...
	
	/* 새로 생성된 스레드가 현재 스레드보다 우선순위가 높으면 양보 */
	if (t->priority > thread_current()->priority)
	{
		thread_yield();
	}
	
	// 동일한 코드...
}

thread_get_priority()

int
thread_get_priority (void) {
	// 인터럽트 끄기
	enum intr_level old_level = intr_disable();
	struct thread* current_thread = thread_current(); // 현재 스레드

	// 인터럽트 다시 켜기
	intr_set_level(old_level);

	// 이미 계산된(기부 상황이면 기부까지 반영된) 우선순위 값 반환
	return current_thread->priority;
}

인터럽트를 끄는 이유

해당 스레드의 우선순위를 읽는 과정 중에 스케줄링 등으로 우선순위 값이 변할 수 있기 때문. 인터럽트를 꺼서 atomic하게 스레드의 우선순위 값을 읽은 후에 다시 복원하는게 안전

priority_compare()

// 우선순위 비교 함수(내림차순)
static bool priority_compare(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
	struct thread *thread_a = list_entry(a, struct thread, elem);
	struct thread *thread_b = list_entry(b, struct thread, elem);

	return thread_a->priority > thread_b->priority;
}

thread_yield()

void
thread_yield (void) {
	// 동일 코드...
	if (curr != idle_thread)
		list_insert_ordered(&ready_list, &curr->elem, priority_compare, NULL);
	// 동일 코드...
}

thread_set_priority()

void
thread_set_priority (int new_priority) {
	// 현재 스레드
	struct thread* current_thread = thread_current();
	current_thread->base_priority = new_priority;

	// 인터럽트 끄기
	enum intr_level old_level = intr_disable();

	// donation이 적용된, 최종 우선순위 계산
	// 나한테 기부한 스레드가 없다면, 기존 우선순위
	if(list_empty(&current_thread->donation_list))
	{
		current_thread->priority = new_priority;
	}
	// 나한테 기부한 스레드가 있다면, 기부받은 우선순위와 기존 우선순위 중 더 높은 값을 최종 우선순위 값으로 설정
	else
	{
		// donation_list는 우선순위 순으로 정렬된 상태(내림차순)
		struct thread* highest_donated_thread = list_entry(list_front(&current_thread->donation_list), struct thread, donation_elem);

		if(highest_donated_thread->priority > new_priority)
		{
			current_thread->priority = highest_donated_thread->priority;
		}
		else
		{
			current_thread->priority = new_priority;
		}
	}

	// 현재 스레드의 우선순위가 최고가 아니라면, 즉시 CPU 양보
	// ready_list는 우선순위 순으로 정렬된 상태(내림차순)
	bool should_yield = false;
	if(!list_empty(&ready_list))
	{
		struct thread *highest_priority_thread = list_entry(list_front(&ready_list), struct thread, elem);

		if(current_thread->priority < highest_priority_thread->priority)
		{
			should_yield = true;
		}
	}

	// 인터럽트 다시 켜기
	intr_set_level(old_level);
	
	// yield는 인터럽트 복원 후에 수행
	if(should_yield)
	{
		thread_yield();
	}
}