**우선순위 스케줄링(Priority Scheduling)**과 우선순위 기부(Priority Donation) 구현

• 새로운 스레드가 ready list에 추가되었는데, 그 스레드의 우선순위가 현재 실행 중인 스레드보다 높다면, 현재 스레드는 즉시 CPU를 양보(yield) 필요
• 마찬가지로, 스레드들이 lock, semaphore, condition variable을 기다릴 때에는 대기 중인 스레드들 중 가장 높은 우선순위를 가진 스레드가 먼저 깨워져야함
• 스레드는 언제든 스스로 우선순위를 올리거나 내릴 수 있음. 하지만, 스스로 우선순위를 낮추었을 때 더 이상 최고 우선순위 스레드가 아니라면, 즉시 CPU를 양보해야함

스레드 우선순위 범위는 PRI_MIN (0) ~ PRI_MAX (63)

• 작은 값일수록 낮은 우선순위(즉, priority 0은 최저 우선순위, priority 63은 최고 우선순위)
• 초기 스레드 우선순위는 thread_create()의 인자로 전달됨
• 특별한 이유가 없다면 PRI_DEFAULT (31)을 사용
• 이 매크로들은 threads/thread.h에 정의되어 있으며 값을 변경하면 안됨

우선순위 역전 문제 (Priority Inversion)

우선순위 스케줄링에는 우선순위 역전(priority inversion) 문제 존재

예 : 스레드 H(높음), M(중간), L(낮음)이 있다고 가정

• 만약 H가 L을 기다려야 한다면(예: L이 H가 필요한 lock을 보유 중), 동시에 M이 ready list에 있다면, L은 CPU를 얻지 못해 실행되지 못함 → 그 결과 H도 영원히 실행되지 못함

이 문제를 부분적으로 해결하기 위해, H는 L이 lock을 보유하는 동안 자신의 우선순위를 L에게 "기부(donate)". 그리고 L이 lock을 해제하여 H가 lock을 획득하면, L은 다시 원래의 우선순위를 복구

우선순위 기부 구현

• 반드시 lock에 대해 priority donation을 구현
• Pintos의 다른 동기화 구조체(semaphore, condition variable 등)에 대해서는 donation을 구현할 필요는 없음. 그러나 모든 경우에 대해 priority scheduling은 구현 필요

우선순위 기부를 구현할 때 고려해야 할 점:

• 여러 번의 donation을 처리할 수 있어야함(여러 스레드가 동시에 donation 하는 경우)