priority donation이 해결하는 문제는?

우선순위가 낮은 스레드가 lock을 기다리는 상황을 해소하는데 도움을 준다. lock을 소유하는 스레드의 우선순위가 낮고, 그 lock을 우선순위가 높은 스레드가 기다리는 상황이 발생할 수 있다.

이때, lock을 소유한 스레드가 빨리 lock을 내려놓을 수 있도록 우선적으로 실행하게 만든다. 이를 위해 우선순위가 높은 스레드의 priority를 낮은 스레드에게 전달한다. 결과적으로 lock을 소유한 스레드의 우선순위가 높아지면서, 빠르게 실행될 가능성이 높아진다.

priority donation에 중첩될 때, 왜 깊이 제한이 필요할까?

priroity donation을 구현하면서 발생하는 문제를 회피하여 구현 난이도를 낮추는게 목적으로 보인다. 의존관계가 순환구조를 띄거나, 매우 길면 우선순위 전달 비용이 극히 커질 수 있다. 이를 해소하기 위해, pintos에서는 깊이를 제한하는걸로 보인다.

전달 비용은 우선순위, lock 보유자 확인, lock 보유자 우선순위 갱신, 다른 lock을 기다리는지 확인등으로 구성된다.

priority 구분

priority를 분할 필요가 있다. 스레드가 갖던 우선순위와 기부받은 우선순위는 다르다. 스레드가 기존에 갖고 있던 우선운위를 base priority, 기부받은 우선순위를 effective priority라 부른다.

effective priority는 실제로 효력을 발생하는 우선순위다. 이때, 두 우선순위는 더해지는게 아닌, 기부받은 우선순위를 의미한다.

기부받은 우선순위가 작을 수 있지 않냐는 생각을 할 수 있는데, 그렇지 않다. 왜냐면 기부를 받는건, 기다리는 스레드의 우선순위가 더 높을 때만 발생하기 때문이다.

참고

https://casys-kaist.github.io/pintos-kaist/project1/priority_scheduling.html