Priority Inversion

Priority Inversion은 선점형 우선 스케쥴링(preemptive priority scheduling) 방식에서 발생하는 작업의 우선 순위가 역전되는 현상이다. 예를 들어, 우선 순위가 높고 낮은 작업인 H와 L이 있다. 각각은 배타적으로 접근해야 하는 공유 자원 R을 사용하고 있다. 만약, H가 R에 대한 접근을 L의 접근 이후에 한다면, H의 작업은 L이 R의 소유권을 놓을 때까지 지연된다. 우선 순위가 높은 H가 낮은 L을 기다리는 상황이 되는 것이다. 이러한 상황을 피하기 위해 L이 R의 소유권을 즉시 양도(relinquish)하도록 시스템을 설계하기도 한다.

하지만, 도중에 중간 우선 순위를 가지며 R을 사용하지 않는 작업 M이 작업 큐에 들어온다면, L보다 우선 순위가 높으므로 M이 CPU를 선점하게 된다. 이미 M에게 작업 권을 빼앗긴 L은 R의 소유권을 양도할 수도 없게 되고, H는 우선 순위가 자신 보다 낮은 M을 기다려야 하는 상황이 된다.

이는 실제로 오래전 화성 탐사선(Mars Pathfinder)의 소프트웨어에서 발견된 심각한 버그와도 연관이 되어 있다. 한가지 해결책으로 우선 상속(priority inheritance)이 있는데, 일시적으로 L의 우선 순위를 H와 동일하게 하여 도중에 M에 의한 interrupt를 방지하는 것이다. 물론, L의 critical section이 끝나 R을 release하게 되면 L의 우선 순위는 원래대로 돌아간다.