[WEEK 08] PintOS - Project 1: Threads (Priority Scheduling) - Part 2. Priority Donation

Backgrounds

Priority Inversion

Priority Inversion이란 우선순위가 높은 쓰레드가 CPU를 사용하기 위해 우선순위가 낮은 쓰레드의 실행을 기다려야 하는 상황이다.

우선순위가 다른 세 개의 쓰레드 H, M, L이 있는 경우 H가 L의 실행을 기다려야 하는 상황에서 H가 L에게 CPU 점유를 넘겨주면 L보다 우선순위가 높은 M이 CPU를 선점하여 사용하게 된다. 쓰레드의 마무리가 M -> L -> H 순서로 실행되면서 M이 더 높은 우선순위를 가진 H보다 먼저 실행되는 문제가 발생한다.

Priority Donation

Priority Donation을 이용해 Priority Inversion 상황을 해결할 수 있다.

우선순위 기부란 우선순위가 높은 쓰레드가 자신의 실행을 위해 우선순위가 낮은 쓰레드에게 일시적으로 높은 우선순위를 양도함으로써 H 우선순위가 낮은 쓰레드가 자신과 동일한 우선순위를 가지고 우선적으로 실행할 수 있도록 하는 방법이다.

핀토스에서 우선순위 기부를 구현하기 위해 고려해야 할 Multiple Donation과 Nested Donation 두 가지 상황이 존재한다.

Multiple Donation

예시에서 쓰레드 L이 lock A와 lock B 두 개의 락을 점유하고 있다고 가정한다. H가 lock A를 M이 lock B를 각각 요청하였을 때, L은 자신에게 락을 요청한 M과 L로부터 모두 우선순위를 일시적으로 양도받고, 이 중 가장 높은 우선순위를 일시적으로 자신의 우선순위로 갖는다.

이러한 경우 L이 lock B를 반환해도 아직 31이 아닌 M에게 양도받은 32를 우선순위로 가진다.

Nested Donation

Nested Donation은 그림과 같이 가장 높은 우선순위를 가진 H가 lock B를 얻기 위해 M에게 우선순위를 기부하고 M은 lock A를 얻기 위해 L에게 우선순위를 기부하는 경우이다.

시간적으로 lock A를 점유한 L이 가장 먼저 실행되고 L이 실행됨으로써 락을 반환하고 이를 점유한 M이 실행되면서 lock B를 반환한다. 마지막으로 락을 점유하게 된 H가 실행된다.

Implementations

struct thread

쓰레드는 우선순위를 주고받은 정보를 담기 위해 쓰레드 구조체 thread를 수정해야 한다.

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */
	int init_priority;
	int64_t wakeup_time;

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
	struct lock *wait_on_lock;
	struct list donations;
	struct list_elem donation_elem;

init_priority는 쓰레드가 우선순위 기부를 통해 양도받은 우선순위를 사용하여 실행하고 반환할 때 기존의 우선순위로 복원할 수 있도록 초기 우선순위를 저장하는 변수이다. wait_on_lock은 해당 쓰레드가 실행을 위해 획득하기를 기다리고 있는 락을 의미한다. donations는 해당 쓰레드에게 우선순위 기부를 통해 양도한 쓰레드들의 리스트이며 donation_elem은 이 리스트를 관리하기 위한 element 구조체이다.

해당 예시에서 L -> init_priority = 31, L -> donations = [M, H]이다. 또한 M -> wait_on_lock = A, H -> wait_on_lock = B이다.

static void init_thread(struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t -> status = THREAD_BLOCKED;
	strlcpy(t -> name, name, sizeof t -> name);
	t -> tf.rsp = (uint64_t)t + PGSIZE - sizeof(void *);
	t -> priority = priority;
	t -> magic = THREAD_MAGIC;

	t -> init_priority = priority;
	t -> wait_on_lock = NULL;
	list_init(&t -> donations);
}

새롭게 추가된 요소들을 초기화하기 위해 init_thread() 함수에 초기화하는 코드를 추가한다.

lock_acquire(struct lock *lock)

lock_acquire 함수는 쓰레드가 락을 요청할 때 실행된다. 락을 점유하고 있는 쓰레드가 없으면 상관 없지만, 다른 쓰레드가 해당 락을 점유하고 있다면 자신의 우선순위를 양도하여 락을 점유하고 있는 쓰레드가 우선적으로 실행되어 락을 반환하도록 해야한다.

void lock_acquire(struct lock *lock) {
	struct thread *curr = thread_current();

	ASSERT (lock != NULL);
	ASSERT (!intr_context());
	ASSERT (!lock_held_by_current_thread(lock));

	if (lock -> holder) {
		curr -> wait_on_lock = lock;
		list_insert_ordered(&lock -> holder -> donations, &curr -> donation_elem, compare_donation_priority, 0);
		donate_priority();
	}

	sema_down(&lock -> semaphore);

	curr -> wait_on_lock = NULL;
	lock -> holder = thread_current();
}

lock -> holder는 현재 락을 점유하고 있는 쓰레드를 가리킨다. 현재 락을 점유하고 있는 쓰레드가 없다면 바로 해당 락을 차지하고 그렇지 않다면 해당 락을 점유하고 있는 쓰레드에게 우선순위를 양도해야 한다.

compare_donation_priority()

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

compare_donation_priority() 함수는 현재 쓰레드에게 우선순위를 양도한 쓰레드들의 도네이션 리스트에 추가된 쓰레드들의 우선순위를 내림차순으로 정렬하기 위해 비교한다.

donate_priority()

donate_priority() 함수는 자신이 필요로 하는 lock을 점유하고 있는 쓰레드를 실행시키기 위해 자신의 우선순위를 양도하는 함수이다.

void donate_priority(void) {
	int depth;
	struct thread *curr = thread_current();
	struct thread *holder = curr -> wait_on_lock -> holder;

	for (depth = 0; depth < 8; depth++) {
		if (!curr -> wait_on_lock)
			break;
		holder -> priority = curr -> priority;
		curr = holder;
	}
}

정수형 변수 depth는 nested의 최대 깊이(max_depth = 8)를 설정하기 위한 변수이다. 쓰레드의 wait_on_lock이 NULL이 아니라면 락을 필요로 한다는 것을 의미하고 해당 락을 점유하고 있는 holder 쓰레드에게 우선순위를 양도하는 방식을 깊이 8의 쓰레드까지 반복하도록 설정한다. wait_on_lock이 NULL이라면 더 이상 우선순위 기부를 진행할 필요가 없으므로 break로 멈춘다.

lock_release()

void lock_release(struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread(lock));

	lock -> holder = NULL;
	sema_up(&lock -> semaphore);
}

쓰레드가 우선순위를 양도 받아 critical section을 마치고 락을 반환할 때의 경우를 고려한다. lock_release() 함수는 락을 점유한 holder를 NULL로 변경하고 sema_up()을 실행한다. sema_up()을 실행하여 락을 반환하기 전에 현재 쓰레드에게 우선순위를 양도한 쓰레드들을 donations에서 제거하고, 기존의 우선순위로 복구하는 과정이 필요하다.

Results

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/threads/mlfqs/mlfqs-load-1
FAIL tests/threads/mlfqs/mlfqs-load-60
FAIL tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
FAIL tests/threads/mlfqs/mlfqs-fair-2
FAIL tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-block
9 of 27 tests failed.