우선순위 역전

정의

우선순위 역전은 높은 우선순위 작업이 낮은 우선순위 작업 때문에 기다리는 현상이다.

낮은 작업이 쥔 공유 자원 때문에 실행이 지연되어 우선순위 순서가 뒤집힌다.

역전은 현상이고, 상속과 상한은 이를 해결하는 기법이라는 점을 구분하자.

발생 과정

낮은 우선순위 작업 L이 공유 자원 R을 잡고 임계 구역에 들어간다.

그때 높은 우선순위 H가 같은 R을 요청하면 H는 블록된다.

이때 중간 우선순위 M이 실행 가능해지면 L보다 높으므로 L을 선점한다.

M이 끝나면 L이 재개되어 R을 해제한다.

H는 자기보다 낮은 L과 M 때문에 기다렸다. 이것이 우선순위 역전이다.

우선순위 상속

우선순위 상속 프로토콜은 블록된 고순위 태스크의 우선순위를 점유 태스크에 넘겨준다.

L이 자원을 얻은 뒤 H가 같은 자원을 요청하면 H는 블록된다.

그러면 L의 우선순위를 H 수준으로 올려 M이 L을 선점하지 못하게 한다.

M이 준비돼도 L의 우선순위가 높아 선점되지 않는다.

L이 자원을 해제하면 원래 우선순위로 돌아가고 H가 자원을 넘겨받는다.

계산 예제

가상의 예로 task1은 높음, task2는 중간, task3는 낮은 우선순위다.

task3가 뮤텍스 M을 잠근 상태에서 task1이 M을 요청하면 task1은 블록된다.

이때 task2가 실행 가능해지면 task3를 선점하므로 task1은 task2가 끝날 때까지 기다린다.

역전이 없다면 task1의 대기 시간은 임계 구역 C3, 즉 4ms다.

역전이 있으면 task2의 실행 시간 C2와 C3를 더한 14ms로 늘어난다.

PIP를 적용하면 대기 시간이 다시 4ms 수준으로 줄어든다.

우선순위 상한

앞 문제의 답은 없다. PIP 적용 후 task2는 task3를 선점하지 못한다.

두 번째 기법은 우선순위 상한 프로토콜이다. 자원마다 상한을 미리 정해 둔다.

상한은 그 자원을 쓸 수 있는 태스크 중 가장 높은 우선순위다.

태스크는 자신의 우선순위가 점유 중인 모든 자원의 상한보다 높을 때만 새 자원을 얻는다.

이 규칙으로 블록 시간이 임계 구역 하나의 길이로 제한되고 교착도 막힌다.

다만 자원별 사용 태스크를 미리 알아야 하고 불필요한 블록이 생길 수 있다.

방식 비교

세 방식을 판단 기준, 구현 부담, 과도한 블록 세 항목으로 비교한다.

PIP는 블록이 생긴 뒤 반응하고, PCP는 자원 상한으로 점유 전에 진입을 제한한다.

NPCS는 임계구역 안에서 선점을 금지해 구현은 단순하지만 무관한 고우선순위까지 막는다.

세 방식 모두 임계구역 길이가 길수록 블록 시간이 늘어난다.

PIP는 블록 사슬이 길면 계산이 복잡해진다는 점을 기억하자.

정리

정리하면 우선순위 역전은 저순위 태스크의 자원 점유로 생기는 현상이다.

해결 기법은 PIP와 PCP다. PIP는 블록 뒤 상속, PCP는 자원 상한으로 미리 막는다.

시험에서는 정의, 발생 과정, PIP와 PCP 비교가 함께 나오는 경우가 많다.