Donation

in Blog / CS on 운영체제

임계구역에 대한 권한은 있지만, priority가 낮아서 일을 하고 있지 않는 상태라면, 모든 시스템이 작동이 중지될 위험이 있다. 이 상황을 방지하기 위해 Donation이 등장한다.

Donation이란?

Donation은 운영체제, 특히 스레드 우선순위(priority schedulling)가 있는 시스템에서 중요한 개념으로, (Priority Donation)를 의미합니다. 이 개념은 특히 PintOS 프로젝트나 스레드 동기화 구현에서 자주 등장합니다.

왜 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 되어 우선순위 역전 현상 발생

해결 방법 : Priority Donation

높은 우선순위 스레드가 낮은 우선순위 스레드에게 자신의 우선순위를 잠시 기부해서 CPU를 더 빨리 사용할 수 있도록 합니다.

동작 방식

  • H가 L이 잡고 있는 lock을 기다릴 때, L에게 H의 우선순위를 임시로 부여 (donation)

  • L은 높은 우선순위로 빨리 실행되어 lock을 release

  • lock을 release하면 다시 원래의 우선순위로 복원

© 2022 JeongHwan Yun.