우선순위 상속 프로토콜

정의

기본 우선순위 상속 프로토콜(basic priority inheritance protocol)은 한 job이 더 높은 우선순위 job들을 블로킹하고 있는 동안 자기에게 배정된 우선순위를 무시하고 자신이 막고 있는 job들 가운데 가장 높은 우선순위로 임계 구역을 실행하게 하고, 임계 구역을 벗어나면 원래 우선순위로 되돌리는 규약이다.[1]

우선순위 역전에서 문제가 되는 것은 락과 무관한 중간 우선순위 job이 락을 쥔 낮은 우선순위 job을 선점해 블로킹을 늘리는 대목이었다. 상속은 그 선점을 원천에서 막는다. 락을 쥔 job이 자기가 막고 있는 job의 우선순위로 실행되면 중간 우선순위 job은 더 이상 그를 선점할 자격이 없어진다.

규칙

프로토콜은 네 규칙으로 이루어진다.[1]

1. 실행할 준비가 된 job 중 우선순위가 가장 높은 것이 프로세서를 얻는다. 임계 구역에 들어가려면 먼저 그 구역을 지키는 세마포어의 락을 얻어야 하고, 이미 잠겨 있으면 블로킹된다.
2. job J가 하나 이상의 높은 우선순위 job을 블로킹하는 동안 J는 자신이 막고 있는 job들 중 최고 우선순위로 실행한다. 임계 구역을 나갈 때는 그 구역에 들어가던 시점의 우선순위로 되돌아간다.
3. 상속은 이행적이다. J3가 J2를 막고 J2가 J1을 막고 있으면 J3는 J2를 거쳐 J1의 우선순위까지 물려받는다. 상속과 원래 우선순위 복원은 분할 불가능한 연산이어야 한다.
4. 블로킹되지 않은 job J는, 상대가 배정받았든 상속받았든 지금 실행 중인 우선순위보다 자기 우선순위가 높으면 상대를 선점할 수 있다.

앞선 역전 예에 적용하면 J3는 J1의 우선순위로 임계 구역을 실행하므로 J2는 J3를 선점하지 못하고, J3가 임계 구역을 나가는 즉시 J1이 프로세서를 되찾는다.

POSIX 스레드 인터페이스도 같은 규약을 뮤텍스 속성으로 규정한다. PTHREAD_PRIO_INHERIT 속성으로 초기화된 뮤텍스에 어떤 스레드가 블로킹되면 그 뮤텍스의 소유자는 호출한 스레드의 우선순위를 물려받고, 소유자가 다시 같은 속성의 다른 뮤텍스에서 블로킹되면 상속 효과가 재귀적으로 전파된다.[2]

블로킹의 두 형태

상속을 도입하면 높은 우선순위 job이 낮은 job에 막히는 경로가 두 가지가 된다.[1]

직접 블로킹(direct blocking)은 높은 우선순위 job이 이미 잠긴 세마포어를 잡으려다 막히는 경우다. 공유 데이터의 일관성을 지키려면 반드시 필요한 블로킹이다.

push-through 블로킹은 중간 우선순위 job이, 자기보다 높은 job의 우선순위를 상속받은 낮은 job 때문에 막히는 경우다. 중간 job은 문제의 세마포어를 쓰지도 않지만, 이 블로킹이 없으면 가장 높은 job이 중간 job의 실행으로 간접 선점되는 결과가 되므로 이 역시 필요하다.

블로킹 시간의 상한

상속의 성과는 블로킹 횟수와 길이를 미리 셀 수 있게 만든 것이다. 어떤 job이 자기를 막을 수 있는 낮은 우선순위 job 각각에 대해 임계 구역 하나씩만 막히고, 자기를 막을 수 있는 세마포어 각각에 대해서도 한 번씩만 막힌다. 두 상한을 합치면 블로킹 시간은 임계 구역 $\min (n,m)$개의 길이로 묶인다 — 여기서 $n$은 자기를 막을 수 있는 낮은 우선순위 job 수, $m$은 자기를 막을 수 있는 세마포어 수다.[1]

상한이 컴파일 시점에 정해진다는 것이 실용적인 의미다. 이 값이 있어야 블로킹 항을 응답 시간 분석 같은 판정에 넣고 태스크 집합의 스케줄가능성을 논할 수 있다.

남는 문제

상속은 역전의 길이를 묶을 뿐 자원 사용의 구조적 문제까지 풀지는 못한다.[1]

첫째, 교착을 막지 못한다. 낮은 우선순위 job이 세마포어 하나를 잠근 상태에서 중첩 접근을 시도하려는 순간 높은 우선순위 job이 선점해 반대쪽 세마포어를 잠그고 첫 세마포어를 요청하면, 두 job은 서로를 기다리게 된다. 교착 예방은 세마포어 접근에 순서를 강제하는 것처럼 프로토콜 밖의 수단에 맡겨야 한다.

둘째, 사슬 블로킹(chained blocking)이 남는다. 한 job이 세마포어 두 개를 차례로 써야 하는데 각각을 서로 다른 낮은 우선순위 job이 쥐고 있으면, 그 job은 임계 구역 두 개만큼 연달아 막힌다. 상한은 유계지만 세마포어 수가 늘수록 실제 값이 커진다.

두 문제를 함께 겨냥해 진입 시점을 통제하는 확장이 우선순위 상한 프로토콜이다.

[1]

L. Sha, R. Rajkumar, and J. P. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” IEEE Transactions on Computers, vol. 39, no. 9, pp. 1175–1185, 1990, doi: 10.1109/12.57058.

[2]

IEEE and The Open Group, “IEEE Std 1003.1-2024, Standard for Information Technology — Portable Operating System Interface (POSIX).” The Open Group Base Specifications Issue 8, 2024. Accessed: Aug. 26, 2026. [Online]. Available: https://pubs.opengroup.org/onlinepubs/9799919799/