Priority inversion 문제와 이를 해결하기 위한 동기화 프로토콜에 대한 설명이다.
1. Priority Inversion
Priority-based preemptive scheduling에서 priority는 task의 중요도나 긴급하게 실행해야 함을 의미한다. Priority inversion은 high priority task가 low priority task에 의해 실행이 되지 못하는 경우를 말한다.
대부분의 경우 해로운 것은 아니나, 특정 상황에서 심각한 지연이 발생할 수 있다. Shared resource에 대한 mutex나 non-preemptive sub-system access와 같은 이유로 발생할 수 있다. 가령 화성의 패쓰파인더는 이 문제로 제어 불능 상태에 바졌던 적이 있다.
2. Synchronization Protocol
- Priority inheritance protocol (PIP) : Priority inversion이 발생하면, low prioriy task가 high priority task의 우선순위를 상속받아 실행된다. 상속이 끝나면 원래의 priority를 회복한다.
- Priority ceiling protocol (PCP) : Task가 resource를 점유하기 위해서는, task의 priority가 다른 task에 의해 잠긴 resource priority보다 높아야 실행된다. 연쇄 차단과 데드락을 예방한다.
PIP는 $T_h$가 $T_l$에 의해 실행되지 않을 경우, $T_l$이 $p_h$를 상속받아 실행을 마치고 점유하던 resource를 포기하고 $T_h$가 resource를 가져가는 방식이다. 원래 사용하려고 했던 $T_h$보다 낮은 우선순위의 task에게 실행 우선순위를 밀리지 않기 때문에 효과적이다. 예시는 다음과 같다.
그러나 PIP는 2개 이상의 critical sections이 있으면, 데드락에 빠질 수 있다.
이를 해결하는 것이 PCP이다. PCP는 lock이나 semaphore를 사용하는 경우, 지정된 우선순위로 변경해 주는 방식이다. $T_h$와 $T_l$만 있다면, 지정 우선순위는 $T_h$나 그 이상으로 설정하면 된다. 예시는 다음과 같다.
그러나 구현이 어려워서 보통은 PIP를 사용한다.
3. PCP Example
s1과 s2의 ceiling은 10이라고 했을 때, PCP를 사용하면 chained blocking과 deadlock을 피할 수 있음을 보여라.
- B의 s2 lock
- A에서 s2에 접근하려 했지만, 실패
- B의 실행 + s1 lock, unlock + s2 unlock
- A의 실행
만약 PCP가 아니라 PIP를 사용했고 A가 s1을 먼저 lock했으면 데드락에 빠질 수 있게 된다.