Priority Inheritance Protocols: An Approach to Real-Time Synchronization

느낀점

현재 보고 싶은 논문이 있는데, 해당 논문에 나온 몇 가지 개념들을 익히기 위해서 이 논문을 리뷰하고 있다.

문제 정의나 해결하는 방법에 대해서는 큰 어려움없이 쉽게 읽히고 이해가 간다. 

---

Problem Statement

실시간 시스템에서 공통적으로 사용되는 동기화 방식(세마포어, 모니터 등)은 Priority Inversion(우선순위 역전) 문제를 유발할 수 있다

특히, High Priority Task가 Low Priority Task에 의해 Blocking되는 상황 발생

기존 연구에서는 Deadlock 방지가 미흡했고, Blocking 시간의 Worst-Case 분석이 어려웠다. 

목표: 실시간성 보장을 해치지 않으면서, 우선순위 역전 문제와 Deadlock을 해결할 수 있는 효율적이고 분석 가능한 동기화 프로토콜 제안 

 

왜 동기화가 시스템을 마비시킬 수 있었는가???

기존 동기화 방식의 문제 (Ex. Semaphore, Ada Rendezvous)

- Priority Inversion: 낮은 우선순위 Task가 자원을 점유하고 있을 때, 높은 우선순위 Task가 해당 자원을 기다리느라 Blocking

- Chained Blocking: 여러 자원이 연결되면, 중간 우선순위 Task들까지 엮이면서 예측이 안되는 지연이 발생

-  Deadlock: 자원 요청 순서가 꼬이면서 서로 자원을 기다리다가 시스템이 멈춤

위와 같은 이유로 인해 실시간 시스템이 동작하지 못하고 마비될 가능성이 있다. 

---

Key Contributions

1. 기본 Priority Inheritance Protocol(PIP) 정의

: Blocking 발생 시, 낮은 우선순위 Task가 높은 우선순위 Task를 상속(Inherit)하여 실행

2. Priority Ceiling Protocol(PCP) 제안

: Deadlock 방지 + Blocking 시간 상한 보장

각 자원(Semaphore)에 우선순위 Ceiling 값 설정 -> 사전 차단(Preventive Blocking)

3. Schedulable 분석 가능

: Rate-Monotonic Scheduling(RMS)환경에서의 충분조건(schedulability condition) 도출

4. Blocking 시간 최소화

: 최악의 경우에도, 하나의 Critical Section 시간만큼만 Blocking 발생

5. Implementation 가이드라인 제시

: 실제 OS 적용 시 고려사항 제시

---

Algorithms

 

기본 Notation 정리

Job($J_{i}$): 실시간 작업 인스턴스

Semapore($S_{i}$): 공유 자원 보호

Critical Section($Z_{i}$): 자원 접근 코드 블록

 Priority ($P_{i}$): 작업 우선순위

Priority Inversion: 높은 우선순위 작업이 낮은 우선순위 작업에 의해 대기 

 

기본 Priority Inheritance Protocol(PIP)

: 높은 우선순위 Job이 Blocking 되면, 자원을 점유한 낮은 우선순위 Job은 높은 우선순위를 상속

Critical Section 종료 시, 원래 우선순위로 복귀

▶ 주요 성질

1. 우선순위 역전 방지

2. Deadlock 발생 가능

3. Blocking Chain 문제 존재 

 

Priority Ceiling Protocol(PCP) 정의

: 각 세마포어 S에 대해 Ceiling 값 = 해당 자원을 사용하는 Job 중 최고 우선순위

핵심 아이디어는 다음과 같다. 

자원을 차단하기 전에 차단(Preventive Blocking)해서, 아예 위험한 상황을 만들지 않는다. 

각 자원(Semaphore)에 Ceiling Priority를 설정

현재 시스템에 Lock이 된 자원들의 Ceiling Priority보다 우선순위가 높은 때만 자원 요청을 허용한다. 

Blocking이 발생해도, 최대 1번만, 그리고 Deadlock은 원천차단한다. 

▶ 실행규칙

1. Job J가 Critical Section 진입 시도 시, 

(1) 현재 락(Lock)된 세마포어들의 Ceiling 중 최대값보다 자신의 우선순위가 높을 때만 진입 허용

(2) 그렇지 않으면 사전 차단(Blocking)

2. Blocking 시, 자원을 점유한 Job이 높은 우선순위를 상속

3. Deadlock 자동 방지 + Chained Blocking 방지

 

Blocking  시간 상한 분석

:  Job J는 최대 1개의 Critical Section 만큼만 Blocking

수학적 상한:

$$B_{i} = max\{Duration\,of\,Critical\,Section\,blocking\,J_{i}\}$$

 

Schedulable Condition (RMS 기준)

: Liu & Layland 기반 충분조건 확장

$$ \sum_{j=1}^{i}\frac{C_{j}}{T_{j}}+\frac{B_{i}}{T_{i}}\leq i(2^{\frac{1}{i}}-1)$$

$C_{j}$: 작업 실행 시간

$T_{j}$: 주기

$B_{i}$: 최악의 Blocking 시간

$i$: 작업 인덱스 

▶ Blocking 시간을 고려하여도 Schedulable한 지 판별 가능

 

PCP  특성 

(1) Deadlock 방지: Ceiling 규칙으로 Cycle 형성 불가

(2) Blocking 상한 보장: 최대 1 Critical Section

(3) 우선순위 역전 해결: Inheritance 매커니즘

(4) Chained Blocking 제거: 사전 차단 방식

(5) Schedulable 분석 용이: RMS와 통합 분석 가능

▶ PCP는 실시간 시스템의 동기화 문제를 해결하는 표준 프로토콜로 자리잡음

 Deadlock-free, Predictable Blocking, Low Overhead 제공

이후  RTOS, AUTOSAR OS등에 폭넓게 채택되었음

---

Pseudocode & Examples 

Task	Priority	Resource
T1	High	S (공유자원)
T2	Low	S
T3	Medium	없음

 

[기존 Semaphore 적용]

1. T2가 먼저 실행 -> S 자원 점유

2. T1 실행 -> S가 점유 중이라 대기 (Blocking 발생)

3. T3가 계속 실행된 (T2보다 우선순위 높음)

4. 결과 T1 (High Priority Task)가 무기한 대기 -> Priority Inversion 발생

 

[PCP 적용]

1. 자원 S의 Ceiling Priority = T1의 우선순위(High) 설정

2. T2가 S를 요청하면? 

- T2의 우선순위( Low)가 S의 Ceiling(High)보다 낮음

- T2는 자원 요청 불가 ->  사전 차단(Blocking)

3. T1만이 S에 접근 가능하여 시스템 마비없이 실시간 성 보장 

 

function request_resource(Task T, Resource S):
    if T.priority > system_ceiling:
        lock(S)
        system_ceiling = max(system_ceiling, S.ceiling_priority)
    else:
        block(T)   // Preventive blocking

function release_resource(Task T, Resource S):
    unlock(S)
    update_system_ceiling()

PCP 알고리즘 PseudoCode

 

[ 기존 세마포어 문제 ]
T2(Low) -- lock(S)
        T1(High) -- Blocked(wait for S)
               T3(Medium) -- 계속 실행 (Priority Inversion 발생)

[ PCP 적용 ]
T2(Low) -- 요청 거부 (Ceiling 위반)
        T1(High) -- lock(S) 실행
               T3(Medium) -- T1 끝난 후 실행

 

단 오해하면 안되는게 그렇다고 Task2가 영원히 S에 접근하지 못한다는 말은 아니다. 

Task2 (Low Priority)가 자원 S를 요청할 수 있는 시점은

- 시스템에 더 높은 우선순위 Task가 실행 대기 중이 아닐 때,

즉 Task1 (High Priority)가 실행 중이거나 준비 상태(Ready Queue)에 없을 때,

시스템이 "안전한 상태"일 때만 자원 접근을 허용한다. 

 

Preventive Blocking은 

- 우선순위 역전이나 Deadlock 상황을 방지하기 위한 장치

- 무조건 막는게 아니라 위험 상황에서만 차단

여기까지는 전체적인 내용을 간략하게 정리해보았고, 아래에는 각 장을 자세하게 정리해보겠다. 

---

2장 The Priority Inversion Problem 수식 해설

$J_{i}$	Task Instance (Job)
$P_{i}$	Task $T_{i}$의 우선순위
$T_{i}$	Task Period
$S_{i}$	Binary Semaphore(공유 자원)
$P(S_{i})$	Semaphore Lock(Wait)
$V(S_{i})$	Semaphore Unlock(Signal)
$z_{i\,j}$	Job $J_{i}$의 j번째 Critical Section
$d_{i\,j}$	Critical Section $z_{i\,j}$의 실행 시간
$z_{i\,j} \subset z_{i\,k}$	중첩된 Critical Section 관계
$\Phi_{i\,j}$	Job $J_{i}$를 Blocking 할 수 있는 최대 Critical Sections
$\Phi_{i}^{*}$	전체 Blocking 가능 Critical Sections 집합

 

Blocking Definition 

높은 우선순위 Job $J$가 낮은 우선순위 Job의 Critical Section 때문에 대기하는 것

[Def 1] Job $J$는 Job $J_{i}$의 Critical Section $z_{i\,j}$ 때문에 Blocking된다. 

▶ Condition: $P(J_{i})\,<\,P(J)$이고, $J$가 $z_{i\,j}$의 종료를 기다려야 한다. 

[Def 2] Job $J$가 Semaphore $S$를 통해 Job $J_{i}$에게 Blocking된다면, $z_{i\,j}$이 $S$를 사용하고 있을 때 발생

 

Worst-Case Blocking 분석 준비

Schedulable 분석을 위해, 최악의 Blocking Time을 구해야 한다. 

이를 위해 Critical Section 집합을 아래와 같이 정의한다.

$$P_{i,j}\,=\,\{z_{j\,k}\,|\,J_{j}가\,J_{i}를\,Blocking할\,수\,있는\,Critical\,Sections\}$$

중첩된 Critical Section 중 가장 긴 영역만 고려:

$$\Phi_{i,j}\,=\,\{z_{j,k}\,\in\,P_{i,j}\,|\,z_{j,k}이\,최대\,요소\}$$

최종적으로, Job $J_{i}$를 Blocking 할 수 있는 전체 집합:

$$\Phi _{i}^{*}=\bigcup_{j>i}\Phi ^{}_{i,j}$$

---

3장 The Basic Priority Inheritance Protocol 정리

▶  PIP(Priority Inheritance Protocol)의 기본 개념과 동작방식 정의

핵심은 높은 우선순위 Job이 Blocking될 때, 낮은 우선순위 Job이 Priority를 상속받아 실행한다는 점

Blocking을 최소화하고, Priority Inversion을 해결

하지만 DeadLock 방지를 할 방법은 없다

 

◆ Lemma 1

"A job $J_{H}$ can be blocked by a lower priority job $J_{L}$ only if $J_{L}$ is executing within a critical section $Z_{L,j}\,\in\,P_{i,L}$." 

• 즉, 낮은 우선순위 Job이 Critical Section 안에 있을 때만 Blocking 발생
• 만약 $J_{L}$이 Critical Section 밖에 있다면, $J_{H}$가 즉시 선점 가능

 

◆ Lemma 2

"Under the basic priority inheritance protocol, a high priority job $J_{H}$ can be blocked by a lower priority job $J_{L}$ for at most the duration of one critical section"

$$Blocking(J_{H})\,\leq\,max(d_{L,i})$$

• $d_{L,j}$: $J_{L}$ 의 Critical Section 실행 시간
• 여러 Semaphore를 공유해도, 최대 1개의 Critical Section 동안만 Blocking

 

◆ Theorem 3

"Given $n$ lower priority jobs, job $J_{0}$ can be blocked for at most the duration of one critical section per job"

$$Blocking(J_{0})\,\leq\,\sum_{i=1}^{n}max(d_{L,i})$$

• 각 낮은 우선순위 Job마다 최대 1번 Blocking 가능

 

◆ Lemma 4

"A semaphore $S$ can cause push-through blocking to job $J$ only if $S$ is accessed both by a job with lower priority than $J$ and by a job which has or can inherit a priority equal to or higher than $J$."

• Push-Through Blocking 발생 조건:
  • Semaphore $S$가 낮은 우선순위 Job과 높은 우선순위 Job 모두에 의해 접근될 때

 

◆ Lemma 5

"Under the basic priority inheritance protocol, a job $J_{i}$ can encounter blocking by at most one critical section in $\Phi_{i,k}$ for each semaphore $S_{k}$, where $1\,\leq\,k\,\leq\,m$."

• 세마포어 $S_{k}$당 최대 1번 Blocking

$$Blocking(J_{i},S_{k})\,\leq\,1$$

 

◆ Theorem 6

"If there are $m$ semaphores which can block job $J$, then $J$ can be blocked at most $m$ times."

$$Total\,Blocking(J)\,\leq\,m$$

• 전체 Blocking 상한 = Semaphore 개수

 

☆ 최종 Blocking 시간 상한 정리

$$Blocking(J)\,\leq\,min(n,m)$$

• $n$ = Blocking 가능한 낮은 우선순위 Job 수
• $m$ = Blocking 가능한 semaphore 수 

---

4장 The Priority Ceiling Protocol

기호	의미
$S^{*}$	현재 다른 Task가 점유하고 있는 Semaphore 중 가장 높은 Priority Ceiling을 갖는 Semaphore
$P_{c}(S)$	Semaphore $S$의 Priority Ceiling(해당 Semaphore를 사용할 수 있는 Task 중 최고 우선순위)
$\beta_{i}$	Task $J_{i}$가 Blocking 될 수 있는 Critical Section들의 집합
$B_{i}$	Task $J_{i}$의 최악의 Blocking Bound

 

◆ Lemma 7

"A job $J$ can be blocked by a lower priority job $J_{L}$ only if the priority of $J$ is no higher than the highest priority ceiling of all semaphores locked by lower priority jobs when $J$ is initiated."

• 즉, $J$의 우선순위가 이미 점유된 Semaphore들의 Priority Ceiling보다 작거나 같을 경우에만 Blocking 발생

 

◆ Lemma 8

"Under the priority ceiling protocol, a job $J_{j}$ cannot inherit a priority level which is higher than or equal to that of job $J_{i}$ that preempts $J_{j}$."

• 즉, 우선순위 상속은 제한적으로 동작하며, 상속한 우선순위는 선점자보다 크거나 같아질 수 없음

 

◆ Lemma 9

"The priority ceiling protocol prevents transitive blocking."

• $J_{1}$ -> $J_{2}$ -> $J_{3}$ 이런 Blocking Chain을 근본적으로 방지

 

◆ Theorem 10

"The priority ceiling protocol prevents deadlocks."

• 원리:
  • Task는 자신의 우선순위가 현재 점유된 Semaphore들의 모든 Priority Ceiling보다 높을 때만 자원 진입 가능
  • 따라서 Cycle을 구성할 수 없음 -> Deadlock 원천 차단

 

◆ Lemma 11

"Under the priority ceiling protocol, a job $J$ can be blocked only when it is initiated."

• PCP에서는 Task가 실행 도중 blocking이 되는 것이 아니라, 시작 시점(Initiation)에서만 Blocking 될 수 있다. 
• 즉, Task가 실행을 시작한 이후에는 절대로 Blocking되지 않음
• 이 말은, 모든 Blocking이 Task의 진입 시점에서 미리 발생하며, 실행 도중에는 자원 접근에 의한 추가 Blocking이 없다는 것을 의미한다.

 

기존 PIP	PCP (Lemma 11)
실행 도중에도 Blocking 발생 가능	시작 시점에서만 Blocking 발생
Blocking 시점이 불확실	Blocking 시점이 명확 (분석 용이)
Blocking 체인 발생 가능	Blocking 체인 방지

 

◆ Theorem 12

"A job $J$ can be blocked for at most the duration of one element of $\beta_{i}$."

$$B_{i}\,=\,max\{d_{j,k}\,|\,z_{j,k}\,\in\,\beta_{i}\}$$

• $\beta_{i}$: Task $J_{i}$가 Blocking될 수 있는 Critical Section 집합
• 따라서 모든 Blocking은 하나의 Critical Section 길이로 상한이 정해짐

 

위까지 내용을 살펴보면, 3장은 Basic PIP에 대한 수학적 정의, 4장은 PCP의 수학적 정리에 대한 이야기를 하였다. 

이제 5장에서는 PCP를 적용하였을 때, RMS 하에서 Schdulable한 조건을 제시한다. 

기존의 L&L 이론을 기반으로 Blocking 효과까지 반영한 확장된 Schedulable 조건을 다룬다. 

---

5장 Schedulability Theorems

 

◆ Theorem 14 (Liu & Layland 기반)

"A set of $n$ periodic tasks scheduled by RMS can always meet deadlines if:"

$$\sum_{i=1}^{n}\frac{C_{i}}{T_{i}}\leq n(2^{1/n}-1)$$

• $C_{i}$: Task $i$의 실행시간
• $T_{i}$: Task $i$의 주기

-> Blocking이 없는 경우의 L&L RMS Schedulable 조건

 

◆ Theorem 15 (정확한 조건)

"...will meet all deadlines for all task phasings if and only if:"

$$\forall i, \,R_{i}\leq T_{i}$$

• $R_{i}$: Task $i$의 WCRT(Worst Case Response Time)

-> 14, 15 정리는 Blocking이 없는 경우

 

☆ 아래부터 Blocking이 있는 PCP 적용으로 확장

 

◆ Theorem 16

"A set of $n$ periodic tasks using PCP can be scheduled by RMS if:"

$$\sum_{j=1}^{i}\frac{C_{j}}{T_{j}}+\frac{B_{i}}{T_{i}}\leq i(2^{1/i}-1)$$

• $B_{i}$: Task $i$의 최악 Blocking 시간 (PCP에 의해 최대 1개의 Critical Section 길이)

☆ Proof

1. Blocking이 없는 경우 Theorem 14가 적용됨
2. 각 Task의 실행시간을 $C_{i} + B_{i}$로 확장
3. 따라서 Task는 최대 $B_{i}$만큼 지연되어도 Deadline 준수
4. 위 수식이 만족되면 RMS 하에서 Schedulable

예시

3개의 주기적 Task:
* $\tau_{1}\,:\,C_{1}\,=1,\,T_{1}=2,\,B_{1}=1$
* $\tau_{2}\,:\,C_{2}\,=1,\,T_{2}=4,\,B_{1}=1$
* $\tau_{3}\,:\,C_{3}\,=2,\,T_{3}=8,\,B_{1}=0$

각 Task에 대해 Theorem 16 적용:

$$\frac{1}{2}+\frac{1}{2}=1\,\,\,(\tau_{1})$$
$$\frac{1}{2}+\frac{1}{4}+\frac{1}{4}=1\,\,\,(\tau_{2})$$
$$\frac{1}{2}+\frac{1}{4}+\frac{2}{8}=1\,\,\,(\tau_{1})$$

이때, 첫번째 식은 Scheduable하지만, 두번째, 세번째 식은 L&L 기준으로 Schdulable하지 않다. 

 

◆ Corollary 17

"If the sum of utilizations and blocking terms satisfies the same inequality schedulability is guaranteed."

$$\sum_{i=1}^{n}\frac{C_{i}+B_{i}}{T_{i}}\leq n(2^{1/n}-1)$$

• 전체 job 집합 기준으로도 동일한 조건 적용

 

◆ Theoram 18 (더 일반적인 충분조건)

Task 집합이 Schedulable하려면, 각 Task $\tau_{i}$에 대해 다음 조건을 만족해야 함:

$$\forall i,\, R_{i}=C_{i}+B_{i}+\sum_{\forall j\in hp(i)}^{}\left \lceil \frac{R_{i}}{T_{j}}\right \rceil C_{j}\leq T_{i}$$

• $hp(i)$: Task $i$보다 우선순위가 높은 Task 집합
• 반복적 계산(Iterative Calculation)을 통해 $R_{i}$ 도출

---

최종적으로 해당 논문에서는 아래와 같은 문제를 풀고자 했다. 

• 실시간 시스템에서 Priority Inversion, Deadlock, Unbounded Blocking 문제는 기존 동기화 매커니즘(Ada rendezvous, Semaphore 등)으로는 해결이 어려움
• 특히, Multi Tasking 환경과 Shared Resources가 많아질수록 심각해짐

☆ Priority Inheritance Protocol(PIP) 제안

• 우선순위 역전 문제를 완하
• 하지만 여전히 Blocking Chain과 Deadlock 가능성 존재

☆ Priority Ceiling Protocol(PCP) 개발

• Deadlock 방지 + Blocking 상한 보장 + Transitive Blocking 제거
• Blocking은 Task 시작 시점에서 최대 1회만 발생
• Schedulable Analysis Tool 제공

☆ PCP 기반 Schedulable 이론 확장

• L&L의 고전 이론을 Blocking 모델로 확장
• 실시간 시스템 설계 시 정확한  응답 시간 계산 가능 

 

PCP에서 Blocking이 최대 1회 발생한다는 의미

[Def] 하나의 Task 기준으로, Task가 실행을 시작할 때, 발생할 수 있는 Blocking은 단 1번이라는 의미

즉, PCP에서는:

• Task가 실핼 중일 때 반복적으로 여러번 Blocking되지 않는다.
• 오직 실행 시작 시점에만, 시스템 Ceiling 규칙에 의해 다른 Task가 점유 중인 자원때문에 Preventive Blocking이 발생
• Blocking이 발생 시, 가장 긴 Critical Section 하나만큼 기다리면 바로 실행

 

예시

Task	우선순위	사용 자원
$T_{1}$	High	$S_{1}$
$T_{2}$	Medium	$S_{2}$
$T_{3}$	Low	$S_{1}$, $S_{2}$

 

• 자원 Ceiling 설정:
• $P_{C}(S1)\,=\,High$
• $P_{C}(S2)\,=\,Medium$

 

시나리오: T2기준

$T_{3}$가 $S_{2}$를 Lock → 시스템 Ceiling = Medium

$T_{2}$가 실행 시작:

$P(T_{2})\,=\,Medium$

시스템 Ceiling = Medium

조건 충족: 
$P(T_{2})\,\leq\,System Ceiling$

➡️ Blocking 발생 (단 1번)

T3가 S2 사용 완료 → T2는 즉시 실행.

이후 T2가 실행 중에는 더 이상 블로킹 없음.

 

주요 해결 문제	Priority Inversion, Deadlock, Unbounded Blocking
제안한 프로토콜	PIP, PCP
수학적 기여	블로킹 상한 증명, 스케줄러블 조건 정립
향후 연구	EDF 확장, 멀티코어 적용, SRP 통합

 

Ref

• [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, Sep. 1990, doi: 10.1109/12.57058.