Priority Donation이란
thread 스케줄링에서 thread lock을 사용할 시 발생하는 우선순위 역전을 해결하는 방법이다.
이미 lock holder가 존제하는 lock 습득할려고 하면 해당 쓰레드는 lock의 waiters 리스트에
들어가게 되는데 waiters 리스트에 들어가 있는 상태에서는 lock의 홀더가 release 하기 전까지
절대로 readylist로 돌아갈 수 없다.
이러한 상태에서 발생하는 문제가 만약 holder의 우선순위가 낮고 waiters 리스트의 쓰레드의
우선순위가 매우 높아도 holder가 다른 ready 상태의 thread 보다 우선순위가 낮아 release를
수행할 수가 없어 높은 우선순위의 쓰레드보다 우선순위가 낮은 쓰레드가 먼저 실행되는 우선순위
역전이 발생한다.
이를 해결하기 위해 waiters의 우선순위가 lock holder 보다 높다면 lock holder에게 우선순
위를 기부해서 일시적으로 holder의 우선순위를 waiters 리스트중 가장 높은 우선순위를 가진
쓰레드 이상으로 증가시키는 것으로 위에서 발생하는 우선순위 역전 문제를 해결하는것이 바로
Priority Donation이다.
이를 배열을 사용해서 구현한 방식에 대해 설명해 보겠다.
donation을 받은 상태
위 사진에서 A,B는 lock을 나타내고 소문자 a,b,c,d,e는 쓰레드를 나타내며
각 쓰레드와 홀더는 64 크기의 donation 배열을 가지고 있다.
이때 배열의 크기가 64인 이유는 가질 수 있는 우선순위의 범위가 0 - 63이기 때문이다.
쓰레드 뿐만 아니라 홀더 또한 donation 배열을 가지고 있는 이유는 나중의 과정에서 설명
한다.
각각의 lock에 waiters가 추가될때 마다 lock의 donation 리스트에서 waiters의 우선순위
와 일치하는 인덱스의 값을 하나 증가 시킴으로써 어떤 우선순위에 대해 기부를 받았는지 체크한다.
그와 동시에 쓰레드의 donation 리스트의 값 또한 lock과 동일하게 중가시킨다.
위의 작업을 수행하면 위의 그림과 같은 상황이 만들어진다.
그리고 쓰레드는 자신의 donation 리스트를 확인함으로써 자신이 어떤 우선순위를 기부받았는지
확인할 수 있고 기부받은 우선순위중 가장 높은 우선순위를 스케줄링에 사용하게 된다.
donation의 반납
위의 사진은 holder a가 lock A를 release 했을때의 그림이다.
lock을 release 하면 더이상 holder가 아니기에 lock holder 였기에 받았던
기부를 모두 반납해야 한다.
여기서 lock에도 donation 배열을 가지고 있는 이유가 있는데 a가 lock을 하나
release 해도 아직 B의 holder이다. 따라서 모든 donation을 반납하는것이 아니라
B에서 받은 donation은 유지해야한다. 따라서 A를 release 할때는 A의 홀더로써 받은
donation만 반납해야 하고 이를 lock A에 기록되어있는 donation 배열을 확인함으로써
A와 연관이 있는 donation만 선택적으로 반납할 수 있게 된다.
