Priority Donation: 우선순위 역전을 막는 기부 기법
임계구역에 대한 권한은 있지만 priority가 낮아 실행되지 못하면 시스템 전체가 멈출 위험이 있다. 이 우선순위 역전을 방지하기 위해 Priority Donation이 등장한다.
1. Donation이란?
Donation은 스레드 우선순위 스케줄링(priority scheduling) 시스템에서 중요한 개념으로, 정확히는 Priority Donation(우선순위 기부) 을 의미한다. PintOS 프로젝트나 스레드 동기화 구현에서 자주 등장한다.
2. 왜 Donation이 필요할까?
운영체제에서 스레드는 각자 priority 값을 가지고 CPU 사용 기회를 두고 경쟁한다. 그런데 높은 우선순위 스레드가 낮은 우선순위 스레드 때문에 block되는 상황이 생기면 문제가 된다. 이를 우선순위 역전(Priority Inversion) 이라고 한다.
우선순위 역전 예시
| 순서 | 상황 |
|---|---|
| 1 | 낮은 우선순위 스레드 L이 lock을 잡고 실행 중 |
| 2 | 높은 우선순위 스레드 H가 같은 lock을 acquire하려다 block됨 |
| 3 | CPU는 H를 먼저 실행해야 하지만, L이 lock을 쥐고 있어 실행 불가 |
| 4 | 그런데 L보다 약간 높은 중간 우선순위 스레드 M들이 계속 실행됨 |
| 5 | 결과적으로 H가 오랫동안 block되는 우선순위 역전 발생 |
여기서 핵심 문제는, 정작 가장 급한 H가 자기보다 덜 급한 M 때문에 계속 밀린다는 점이다.
3. 해결 방법: Priority Donation
높은 우선순위 스레드가 자신을 막고 있는 낮은 우선순위 스레드에게 자신의 우선순위를 잠시 기부해, 그 스레드가 lock을 빨리 풀도록 만든다.
동작 방식:
H가L이 잡고 있는 lock을 기다릴 때,L에게H의 우선순위를 임시로 부여한다 (donation)L은 높아진 우선순위로 빠르게 실행되어 lock을 release한다 (M에게 밀리지 않음)- lock을 release하면
L은 다시 원래 우선순위로 복원된다 - 이제
H가 lock을 얻어 실행된다
즉, 기부는 “급한 일을 막고 있는 사람에게 잠시 권한을 빌려줘 빨리 비키게 하는” 방식으로 역전을 해소한다.
