핀토스 구현: Priority Inversion

Priority Inversion Problem

우선순위가 높은 thread가 우선순위가 낮은 thread를 기다리는 현상이다.

이 문제를 해결하기위해 Priority Donation을 사용해야 한다. 그러면 아래 그림과 같이 실행된다

제일 먼저, thread구조체를 수정해준다.

struct thread

struct thread{
	...
    //도네이션
	int init_priority; // 초기 우선순위 값을 저장
	struct lock *wait_on_lock; // 해당 쓰레드가 대기하고 있는 lock자료구조의 주소를 저장
	struct list donations; // multiple donation을 고려하기위한 리스트
	struct list_elem donation_elem; // 해당 리스트를 위한 elem
    ...
}

또한, thread를 초기화하는 함수도 수정한다.

init_thread()

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; // 해당 thread가 대기하고 있는 lock자료구조의 주소를 저장
	list_init(&t->donations); // multiple donation을 고려하기위한 리스트
}

이제 lock과 관련된 함수를 수정해야 한다.
lock을 점유하고 있는 스레드와 요청하는 스레드의 우선순위를 비교해 priority donation을 수행하도록 lock_acquire()함수를 수정한다.

lock_acquire()

lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	//도네이션
	struct thread *curr = thread_current();
	if(lock->holder){
		curr->wait_on_lock = lock;
		list_insert_ordered(&lock->holder->donations, &curr->donation_elem, thread_compare_donate_priority, 0);
		donate_priority();
	}

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

lock_acquire() 함수는 잠금을 획득하여 현재 스레드가 임계 영역에 진입할 수 있도록 하는데, 만약 잠금이 이미 다른 스레드에 의해 소유되어 있는 경우, 현재 스레드는 기다리는 동안 해당 잠금의 소유자에게 우선순위를 기부하도록 한다.
위 코드에서 사용한 우선순위를 기부하는 함수인 donate_priority()는 다음과 같이 구현한다.

donate_priority()

void donate_priority(void){
	int depth;
	struct thread *curr = thread_current();

	for (depth = 0; depth < 8; depth++){
		if(curr->wait_on_lock == NULL){
			break;
		}
		else{
			struct thread *holder = curr->wait_on_lock->holder;
			holder->priority = curr->priority;
			curr = holder;
		}
	}
}

잠금을 기다리는 동안 스레드의 우선순위를 잠금을 소유한 스레드에게 기부함으로써 우선순위 역전 문제를 해결한다. 이때 depth 변수는 기부가 발생하는 깊이를 나타내는데, 8로 제한된 이유는 무한한 우선순위 전파를 방지하기 위함이다.

이제 잠금을 해제할 때도 donation list에서 스레드를 제거하고 우선순위를 다시 계산하도록 lock_release()함수를 수정한다.

lock_release()

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

	remove_with_lock(lock);
	refresh_priority();

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

잠금을 해제해 다른 스레드가 잠금을 획득할 수 있도록 remove_with_lock()함수를 이용해 현재 쓰레드의 대기 리스트를 갱신하고, 잠금을 해제한 후에는 우선순위를 기부받았을 수 있으므로 원래의 priority로 초기화하도록 refresh_priority()함수를 사용한다.

remove_with_lock()

void remove_with_lock(struct lock *lock){
	struct list_elem *e;
	struct thread *curr = thread_current();

	for(e = list_begin(&curr->donations); e != list_end(&curr->donations); e = list_next(e)){// donation 리스트를 전부 확인
		struct thread *t = list_entry(e, struct thread, donation_elem);
		if(t->wait_on_lock == lock){ // 현재 thread의 lock과 리스트의 lock이 동일한 경우
			list_remove(&t->donation_elem); // 해당 elem을 리스트에서 제거
		}
	}
}

현재 스레드와 관련된 기부된 우선순위 목록에서 특정 잠금과 관련된 항목을 제거한다.

refresh_priority()

void refresh_priority(void){
	struct thread *curr = thread_current();

	curr->priority = curr->init_priority;

	if(!list_empty(&curr->donations)){ // 현재 스레드에 기부된 우선순위가 있는 경우
		list_sort(&curr->donations, thread_compare_donate_priority, 0); // donations 리스트를 우선순위에 따라 정렬

		struct thread *front = list_entry(list_front(&curr->donations), struct thread, donation_elem); // 정렬된 리스트의 가장 앞 쓰레드를 가져옴
		if(front->priority > curr->priority){ // 기부된 우선순위가 현재 우선순위보다 더 높을 경우
			curr->priority = front->priority; // 현재 스레드의 우선순위를 기부된 변경
		}
	}
}

스레드의 우선순위를 재계산하고 기부된 우선순위를 고려해 최종 우선순위를 설정한다.
마지막으로 thread_set_priority()함수를 수정해주면 된다.

thread_set_priority()

void
thread_set_priority (int new_priority) {
	thread_current ()->init_priority = new_priority;
    
	// donation을 고려해 우선순위를 재설정
	refresh_priority();

	preemption_priority();
}

여기까지 하면 20개의 테스트가 통과된다.