Project1: Threads - Priority Donation

Priority Donation 구현

기부(Donation)가 필요한 순간: 우선순위 역전 (Priority Inversion)

다음과 같이 우선순위가 다른 세 스레드가 있다고 가정합니다.

• H 스레드(50)
• M 스레드(30)
• L 스레드(10)

문제 상황 (우선순위 역전):

1. L 스레드가 특정 lock을 획득하여 실행 중입니다.
2. H 스레드가 실행되다가, L이 가진 lock이 필요해 lock_acquire()를 호출하고 대기(BLOCKED) 상태가 됩니다.
3. 이제 L이 마저 실행되어 lock을 풀어줘야 하는데, M 스레드가 CPU를 선점합니다. (M(30) > L(10))
4. 결과: 가장 우선순위가 높은 H(50)는 L(10)이 끝나길 기다리는데, L은 M(30) 때문에 실행되지 못합니다.

   즉, H 스레드가 자신보다 훨씬 우선순위가 낮은 M 스레드 때문에 실행을 못 하는 '우선순위 역전'이 발생합니다.

해결책 (우선순위 기부):

1. H 스레드가 L이 가진 lock을 기다릴 때, 자신의 높은 우선순위(50)를 L에게 기부(Donation)합니다.
2. L 스레드의 우선순위는 일시적으로 max(10, 50) = 50이 됩니다.
3. L(50)은 M(30)보다 우선순위가 높아졌으므로, CPU를 선점하여 lock을 해제하는 작업을 빠르게 완료할 수 있습니다.
4. L이 lock을 해제(lock_release)하면, 기부받았던 우선순위를 반납하고 원래 우선순위(10)로 돌아갑니다.
5. H 스레드는 lock을 획득하고 정상적으로 실행됩니다.

---

1. 목표

우선순위 역전(Priority Inversion)이 일어나지 않도록 우선순위 기부(Priority Donation)를 구현하자.

---

2. 핵심 아이디어

• 우선순위 기부를 위해서 필요한 필드를 thread 구조체에 선언한다.
• 우선순위 역전이 일어나는 lock_acquire 시점에 기부 로직을 구현한다.
• 기부가 연쇄적으로(Nested) 발생하는 문제를 해결한다.
• 락을 반납하는 lock_release 시점에 기부를 철회하고 우선순위를 복원한다.
• thread_set_priority 함수가 기부 상황에서도 올바르게 동작하도록 수정한다.

---

3. 구현 과정

1. thread 구조체 필드 추가

thread.h의 struct thread에 기부에 필요한 필드들을 추가합니다.

• original_priority: 기부받기 전의 고유 우선순위를 저장합니다.
• waiting_on: 락 획득을 대기할 때, 해당 락을 가리키는 포인터입니다. (연쇄 기부 용)
• donations: 나에게 우선순위를 기부한 스레드들의 리스트입니다.
• donation_elem: 나를 다른 스레드의 donations 리스트에 넣을 때 사용할 리스트 요소입니다.

// thread.h
struct thread
{
	...

	// 기부 전용 명찰
	struct list_elem donation_elem;

	// 기부자들
	struct list donations;

	// 원래 우선순위
	int original_priority;

	// 어떤 락을 기다리고있는지 처음에는 NULL
	struct lock *waiting_on;

	...
    
};

(이후 thread.c의 init_thread에서 original_priority = priority, waiting_on = NULL, list_init(&t->donations)로 초기화합니다.)

---

2. lock_acquire 수정 (기부 및 연쇄 전파)

synch.c의 lock_acquire 함수를 수정합니다. 락 소유자(holder)가 이미 존재하여 락 획득에 실패하는 경우( if (lock->holder != NULL) ), sema_down으로 잠들기 전에 기부 로직을 수행합니다.

donations 리스트를 정렬하기 위한 헬퍼 함수 donate_priority_less와, 연쇄 기부를 처리할 헬퍼 함수 update_holder_priority를 먼저 정의합니다.

lock_acquire 본체 수정 (in synch.c):

void 
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));
	
	struct thread *cur = thread_current();

	if (lock->holder != NULL) { // 락 소유자가 있어 대기 및 기부 발생
		
		// 1. 내가 이 락을 기다린다고 기록 (연쇄 기부용)
		cur->waiting_on = lock;
	
		// 2. 락 소유자의 기부 리스트에 나를 추가
		list_insert_ordered(&lock->holder->donations, &cur->donation_elem, donate_priority_less, NULL); 

		// 3. 락 소유자의 우선순위를 (필요시 연쇄적으로) 갱신
		update_holder_priority(lock->holder);

		// 4. 락이 풀릴 때까지 잠들기
		sema_down (&lock->semaphore);

	} else {
		// 락 소유자가 없으므로 바로 획득
		sema_down (&lock->semaphore); 
	}

	// 락을 획득했으므로 (깨어났거나, 바로 획득했거나)
	cur->waiting_on = NULL; // 더 이상 기다리는 락 없음
	lock->holder = cur;     // 내가 이 락의 소유자임
}

연쇄 갱신 헬퍼 함수 (in synch.c):

/* * 락 소유자(holder)의 우선순위를 재계산하고,
 * 만약 우선순위가 갱신되었다면 이 갱신을 연쇄적으로 전파(propagate)합니다.
 */
void update_holder_priority(struct thread *holder) {

	int current_priority = holder->priority; // 갱신 전 우선순위
	
	// 1. 기본값은 자신의 원래 우선순위
	int new_priority = holder->original_priority; 
	
	// 2. donations 리스트에서 가장 높은 우선순위와 비교
	if (!list_empty(&holder->donations)) {
		struct thread *max_donor = list_entry(list_front(&holder->donations), struct thread, donation_elem);
		
		if (new_priority < max_donor->priority) {
			new_priority = max_donor->priority;
		}
	}

	holder->priority = new_priority; // 3. 최종 우선순위로 갱신

	// 4. [연쇄 전파]
	// 만약 우선순위가 갱신되었고, 이 스레드(holder) 또한 다른 락을 기다리고 있다면
	if (current_priority != holder->priority) {
		if (holder->waiting_on != NULL && holder->waiting_on->holder != NULL) {
			// 그 락의 소유자(holder->waiting_on->holder)도 재귀적으로 갱신
			update_holder_priority(holder->waiting_on->holder);
		}
	}
}

비교 헬퍼 함수 (in synch.c):

/* donations 리스트를 우선순위 내림차순으로 정렬하기 위한 비교 함수 */
int donate_priority_less(const struct list_elem *a,
					   const struct list_elem *b, void *aux UNUSED)
{
	struct thread *thread_a = list_entry(a, struct thread, donation_elem);
	struct thread *thread_b = list_entry(b, struct thread, donation_elem);

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

---

3. lock_release 수정 (기부 철회)

락을 해제할 때, 락 소유자(현재 스레드)의 donations 리스트를 정리하고 우선순위를 원래대로(혹은 남은 기부 중 최고값으로) 복원합니다.

// synch.c
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	struct thread *current = thread_current();

	// 1. 'donations' 리스트에서 "이 락(lock)"을 기다리던 기부자들을 제거
	struct list_elem *e = list_begin(&current->donations);
	while (e != list_end(&current->donations)) {
		struct thread *t= list_entry(e, struct thread, donation_elem);

		if (t->waiting_on == lock) {
			e = list_remove(e); // 이 락을 기다렸던 기부자 제거
		} else {
			e = list_next(e);
		}
	}

	// 2. 기부자 정리 후 우선순위 재계산
	if (list_empty(&current->donations)) {
		// 남은 기부자가 없으면, 원래 우선순위로 복원
		current->priority = current->original_priority;

	} else {
		// 남은 기부자(다른 락 대기자)가 있다면
		struct thread *max_donor = list_entry(list_front(&current->donations), struct thread, donation_elem);
		
		// original_priority와 남은 기부자 중 최고값으로 갱신
		if (max_donor->priority > current->original_priority) {
 	 		current->priority = max_donor->priority;
 		} else {
 	 		current->priority = current->original_priority;
 	 	}
	}

	lock->holder = NULL; // 3. 락 소유자 반납
	sema_up (&lock->semaphore); // 4. 대기 중인 다음 스레드(최고 우선순위)를 깨움
}

---

4. thread_set_priority 수정 (기부와 선점 연동)

스레드가 스스로 우선순위를 변경할 때, priority가 아닌 original_priority를 변경하도록 수정합니다. 그 후, 기부 리스트를 포함하여 실제 priority를 갱신하고, 필요시 선점을 수행합니다.

// thread.c
void 
thread_set_priority(int new_priority)
{
	struct thread *cur = thread_current();

	// 1. 스레드의 '원래' 우선순위를 갱신
 	cur->original_priority = new_priority;

	// 2. '원래' 우선순위와 '기부받은' 우선순위 중 최고값으로 현재 우선순위(priority)를 갱신
	int max_priority = new_priority;
	
	if (!list_empty(&cur->donations)) {
		struct thread *front_thread = list_entry(list_begin(&cur->donations), struct thread, donation_elem);
		if (front_thread->priority > max_priority) {
			max_priority = front_thread->priority;
		}
	}

	cur->priority = max_priority;

 	// 3. [선점 로직]
 	// 만약 우선순위가 낮아졌다면, ready_list의 1등과 비교하여 양보
 	if (!list_empty(&ready_list)) 
 	{
 	 	struct thread *front_thread = list_entry(list_begin(&ready_list), struct thread, elem);
 	 	
 	 	if (cur->priority < front_thread->priority) {
 	 	 	thread_yield();
 	 	}
 	}
}