PintOS_Priority_Scheduling_part_3_donation

문제 정의: Priority Inversion

• 상황: 낮은 우선순위의 스레드 A가 Lock을 잡고 있는 상태에서, 높은 우선순위의 스레드 B가 같은 Lock을 요청하면 B는 대기 상태가 된다. 그런데 A는 더 낮은 우선순위의 스레드 C에게 CPU를 빼앗기게 되어, 높은 우선순위인 B는 오히려 무한정 기다리는 상황이 발생할 수 있다.
• 문제: 우선순위 역전(Priority Inversion)

 

 

해결 방법: Priority Donation

• 높은 우선순위의 스레드가 낮은 우선순위의 스레드에게 자신의 우선순위를 일시적으로 기부(donate) 하는 방식
• donation은 단순한 경우뿐만 아니라 nested donation (chain) 도 처리해야 함

---

우선 먼저 원래의 우선순위를 저장해놓을 변수와 어떤 락을 기다리는 중인지, 현재 잡고 있는 락은 무엇인지 저장해놓을 것들을 구조체에 넣어줍니다

// thread.h
struct thread {
    ...
    int init_priority;               // 원래 우선순위 저장
    struct lock *waiting_on_lock;    // 어떤 락 기다리는 중인지
    struct list hold_list;           // 현재 잡고 있는 락 리스트
    ...
};

 

 

Lock 획득 시 Priority 기부 / Lock 획득 시 기록

lock_acquire()

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);                        // lock이 NULL이 아닌지 확인
	ASSERT (!intr_context ());                    // 인터럽트 핸들러 안에서 호출되지 않아야 함
	ASSERT (!lock_held_by_current_thread (lock)); // 현재 스레드가 이미 이 락을 가지고 있어선 안 됨

	struct thread *curr = thread_current();       // 현재 실행 중인 스레드

	// [Priority Donation 처리]
	if (lock->holder != NULL) {                   // 이미 누군가 이 락을 들고 있다면
		curr->waiting_on_lock = lock;             // 현재 스레드는 이 락을 기다리는 중이라고 표시
		donate_priority();                        // 우선순위 기부 발생 (nested donation도 처리됨)
	}

	sema_down(&lock->semaphore);                  // 락 획득을 위해 세마포어 down (0이면 BLOCK 대기)

	// 세마포어 획득이 끝나고 나면 락을 얻은 상태
	curr->waiting_on_lock = NULL;                 // 더 이상 락을 기다리지 않음
	lock->holder = curr;                          // 이제 이 락의 소유자는 현재 스레드
	list_push_back(&curr->hold_list, &lock->elem); // 현재 스레드가 가지고 있는 락 목록에 추가
}

• 누군가 락을 이미 들고 있으면, 나는 그 락을 기다리는 입장이 됨
• 내가 현재 기다리는 락 (waiting_on_lock)을 기록하고,
• 락을 들고 있는 애한테 내 우선순위를 기부힘
• 락을 성공적으로 획득했으면, 이제 더 이상 기다리는 상태가 아님 (waiting_on_lock = NULL)
• 내가 이 락을 소유함을 기록
• 나중에 refresh_priority()에서 hold_list를 기반으로 우선순위를 다시 계산하기 위해 기록함

•  

 

Priority 기부 로직

donate_priority()

void donate_priority(void) {
    struct thread *curr = thread_current();         // 현재 실행 중인 스레드
    struct lock *lock = curr->waiting_on_lock;      // 현재 스레드가 기다리고 있는 락

    if (lock == NULL) return;                       // 기다리는 락이 없다면 기부할 상황이 아님

    struct thread *holder = lock->holder;           // 락을 소유하고 있는 스레드

    if (holder == NULL) return;                     // 락의 소유자가 없다면 기부할 대상이 없음

    // nested donation (우선순위 기부의 전이) 처리
    while (lock != NULL && 
           lock->holder != NULL &&
           lock->holder->priority < curr->priority) {
        
        // 현재 스레드의 우선순위가 더 높다면 holder에게 기부
        lock->holder->priority = curr->priority;

        // holder를 기준으로 다시 donation 확인 (chain donation을 위해)
        curr = lock->holder;
        lock = curr->waiting_on_lock;               // holder가 또 다른 락을 기다리는 경우 다음 단계로 진행
    }
}

• 내가 락을 기다리고 있다면, 그 락을 들고 있는 애에게 우선순위 기부
• 기부를 받은 애가 또 다른 락을 기다리고 있으면 → 그 락의 holder에게 또 기부 (nested donation)
• 최대 깊이 제한은 걸지 않았지만, 필요시 depth를 두어 제한 가능

 

Lock 해제 시 우선순위 복구

lock_release()

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock)); // 현재 스레드가 해당 락의 소유자인지 확인

	// 현재 스레드의 hold_list에서 해당 락 제거
	list_remove(&lock->elem); 

	// donation이 있었다면, 원래 우선순위로 복구하거나, 남은 donation 기준으로 재계산
	refresh_priority(); 

	// 이제 더 이상 이 락의 소유자가 아님을 명시
	lock->holder = NULL;

	// 락을 기다리고 있는 스레드 중 하나를 깨워 READY 상태로 만듦
	sema_up (&lock->semaphore);
}

• 내가 소유하고 있는 락 리스트에서 해당 락 제거
• 우선순위 복구 필요 → refresh_priority() 호출
• 내 우선순위는 더 이상 누군가의 기부가 반영되지 않게 바뀜

 

우선순위 복구 로직

void refresh_priority(void) {
	struct thread *curr = thread_current();  // 현재 실행 중인 스레드를 가져옴
	int max_priority = curr->init_priority;  // 기본 우선순위(init_priority)를 기준으로 시작

	struct list_elem *e;
	for (e = list_begin(&curr->hold_list); e != list_end(&curr->hold_list); e = list_next(e)) {
		// curr가 현재 보유하고 있는 모든 락에 대해 순회

		struct lock *l = list_entry(e, struct lock, elem);  // hold_list의 요소를 lock 구조체로 캐스팅
		if (!list_empty(&l->semaphore.waiters)) {
			// 해당 락을 기다리는(waiters) 스레드가 있다면

			struct thread *t = list_entry(list_front(&l->semaphore.waiters), struct thread, elem);
			// waiters 리스트에서 가장 우선순위가 높은(정렬되어 있으므로 맨 앞) 스레드 선택

			if (t->priority > max_priority)
				max_priority = t->priority;  // 가장 높은 우선순위로 갱신
		}
	}

	curr->priority = max_priority;  // 갱신된 우선순위를 현재 스레드에 반영
}

• 내가 가지고 있는 모든 락의 waiters 중 가장 높은 우선순위를 찾아, 내 priority를 재설정한다
• 내가 직접 변경한 init_priority보다 높다면 → 우선순위는 기부 상태 유지
• 모든 락이 해제되면 → 다시 원래 우선순위 (init_priority)로 복귀

donation을 고려해 현재 우선순위를 갱신

void thread_set_priority(int new_priority)
{
	struct thread *curr = thread_current();

	curr->init_priority = new_priority;

	if (list_empty(&curr->hold_list)) {
		// 도네이션 받은 게 없다면 즉시 반영
		curr->priority = new_priority;
	} else {
		// 도네이션 받은 게 있을 수 있으므로 우선순위 재계산
		refresh_priority();
	}
    thread_test_preemption(); // priority가 변경되었으니까 우선순위 변경 확인
}

 

1. 현재 스레드의 init_priority를 갱신
   • init_priority는 donation 전 원래 스레드의 우선순위를 기억해두는 값
   • 즉, 이 값은 항상 “본래 우선순위”를 뜻함
2. 그리고 나서 현재 스레드가 어떤 락도 안 들고 있다면, 즉 donation을 받지 않은 상태라면:
   • 그냥 priority = new_priority를 해도 괜찮음 (기부 받은 게 없으니 바로 반영 가능)
3. 반대로 hold_list에 무언가 있다면, 누군가 나한테 donation을 줬을 수 있으니까:
   • refresh_priority()를 호출해서 donation 받은 스레드들의 우선순위를 고려해서 현재 우선순위를 재계산함
4. 마지막으로 thread_test_preemption()을 호출해서,
   • 지금 ready_list에 나보다 높은 우선순위 스레드가 있다면, CPU를 양보할지 판단하게 함

---

자 이렇게 해서 Alram Clock부터해서 Donation까지 구현이 끝났습니다

여기까지 마친다면

 

이렇게 패스가 뜨는걸 볼 수 있습니다

 

다음엔 트러블슈팅으로 돌아오겠습니다