[pintos] 우선순위 역전과 우선순위 기부

우선순위 역전(Priority Inversion)은 낮은 우선순위의 스레드가 높은 우선순위의 스레드보다 먼저 CPU를 점유하거나, 높은 우선순위 스레드의 실행을 지연시키는 현상을 의미한다. 이는 멀티스레딩 환경에서 공유 자원과 락(lock)이 있을 때 주로 발생한다.

---

발생 시나리오

1. L (Low priority) 스레드가 공유 자원(R)을 사용 중이다.
2. H (High priority) 스레드가 실행되며, 같은 자원 R에 접근하려고 한다.
3. 하지만 자원 R은 이미 L이 점유 중이므로, H는 대기하게 된다.
4. 그 사이 M (Medium priority) 스레드가 스케줄러에 의해 실행된다.
5. M은 자원 R과 무관하지만 H보다 우선순위가 낮으므로 원래 H 다음에 실행되어야 하지만,
   현재 H는 자원 대기 상태이므로 M이 계속 실행됨 → L은 CPU를 얻지 못해 자원을 반납 못함.
6. 결과적으로 H는 자원을 기다리며 우선순위가 낮은 L, M보다 늦게 실행되는 상황이 벌어짐.

즉, 낮은 우선순위의 스레드(L)가 자원을 점유하고 있음에도, 중간 우선순위의 스레드(M)가 계속 실행되면서, 높은 우선순위의 스레드(H)가 무한정 대기하게 되는 비정상적인 상황이 발생하는 것이다.

실제 사례

NASA Mars Pathfinder 버그

• NASA의 Mars Pathfinder 탐사선이 우선순위 역전 문제로 멈춘 적이 있다.
• 실시간 시스템에서 저우선 순위 태스크가 공유 자원을 점유하고, 고우선 태스크가 대기했으며, 중간 우선 태스크가 실행을 계속해 고우선 태스크가 실행되지 못하는 상황이었음.
• 결국 Priority Inheritance 기법을 적용하여 문제 해결.

---

우선순위 기부(Priority Donation)

우선순위 기부(Priority Donation)는 우선순위 역전(Priority Inversion) 문제를 해결하기 위한 대표적인 기법 중 하나다. 이는 낮은 우선순위의 스레드가 높은 우선순위의 스레드에게 자원을 점유한 경우, 높은 우선순위 스레드가 자신의 우선순위를 임시로 "기부(donate)"하여, 낮은 우선순위 스레드가 자원을 빨리 해제할 수 있도록 실행 우선순위를 높여주는 방식이다.

• 기본 개념:
  자원을 점유한 저우선 스레드가 자원을 기다리는 고우선 스레드의 실행을 지연시키고 있다면,
  고우선 스레드의 우선순위를 저우선 스레드에게 일시적으로 부여하여
  저우선 스레드가 먼저 자원을 해제하도록 유도함.
• 자원 반납 후:
  기부받은 스레드는 자원을 해제하면 원래 우선순위로 복귀함.

• Thread H (주황색): 높은 우선순위 (High Priority)
• Thread M (파란색): 중간 우선순위 (Medium Priority)
• Thread L (연두색): 낮은 우선순위 (Low Priority)

시나리오 순서

• Thread L이 먼저 실행되어 락(lock)을 획득한다. (왼쪽 아래 연두색 박스 시작)
• Thread H가 나중에 실행되며 동일한 락을 요청한다.
  하지만 락은 이미 Thread L이 점유 중이므로 Thread H는 blocked 상태로 전환된다.
• 이 시점에 우선순위 역전 위험이 발생한다.
  → 원래 Thread H가 즉시 실행되어야 하지만, Thread L이 자원을 들고 있어 H는 기다려야 함.
• Priority Donation 발생
  Thread H는 락을 점유하고 있는 Thread L에게 자신의 높은 우선순위를 기부한다.
  → Thread L의 우선순위가 H만큼 상승한다 (그래프에서 연두색 우선순위가 위로 튀는 부분 = Priority boost).
• 이제 스케줄러는 우선순위가 높아진 Thread L을 먼저 실행시킨다.
  → Thread L은 작업을 마치고 락을 해제한다.
• 락이 해제되자, Thread H는 락을 획득하고 실행을 이어간다.
• 이후, Thread M이 뒤늦게 실행되며 자신의 작업을 진행한다.

상황	설명
우선순위 역전 회피	Thread H가 직접 실행되지 못하고 대기 상태가 될 위험을 방지
우선순위 기부	Thread H가 Thread L에게 우선순위를 "빌려줌"
우선순위 복원	Thread L이 락을 반환하면, 원래의 우선순위로 복귀
Thread M 보호	Thread M은 H보다 낮지만, L보다 높기 때문에 기부가 없으면 실행되며 역전 유발 가능

 

---

정리된 정의

우선순위 기부는 낮은 우선순위의 스레드가 고우선 스레드에게 필요한 자원을 점유하고 있을 때,
고우선 스레드가 자신의 우선순위를 임시로 기부하여, 락 점유자가 선점되어 자원을 빠르게 해제하도록 유도하는 기법이다.