우선순위 역전 문제와 해결 방법

우선순위 역전(Priority Inversion)은 실시간 시스템에서 중요한 문제 중 하나로, 특히 Preempt RT와 같은 실시간 운영체제에서 신속하게 대응해야 할 과제이다. 이 문제는 높은 우선순위를 가진 스레드가 낮은 우선순위의 스레드 때문에 간접적으로 차단되어 실행되지 못하는 상황을 의미한다. 우선순위 역전은 시스템의 예측 가능성을 저하시켜 실시간 성능을 심각하게 저해할 수 있다.

우선순위 역전 문제

우선순위 역전은 주로 다음과 같은 상황에서 발생한다.

리소스 공유: 높은 우선순위의 스레드 A가 실행 중일 때, 낮은 우선순위의 스레드 B가 공유 리소스를 잠금(뮤텍스 등)으로 획득한다. 그 후 중간 우선순위의 스레드 C가 스케줄링 되어 실행된다.
대기 상태: 이 시점에서 스레드 A는 공유 리소스를 필요로 하여 B의 작업이 끝날 때까지 대기해야 한다. 그러나 스레드 C가 스케줄링에 의해 계속 실행되므로, 스레드 A는 실제로 중간 우선순위의 스레드 C에 의해 우선순위가 낮아진 셈이 된다.
역전 현상: 결과적으로, 낮은 우선순위의 스레드 B가 리소스를 해제할 때까지 높은 우선순위의 스레드 A는 실행되지 못하며, 이는 우선순위 역전으로 불린다.

이러한 상황은 실시간 시스템에서 엄청난 문제가 될 수 있다. 예를 들어, 항공기 제어 시스템과 같은 크리티컬한 시스템에서 우선순위 역전은 시스템의 안전성과 신뢰성을 크게 저하시킬 수 있다.

우선순위 역전의 수학적 모델

우선순위 역전 문제를 수학적으로 설명하기 위해, 우선 몇 가지 변수를 정의해보겠다.

$\tau_i$ : 우선순위가 높은 스레드
$\tau_j$ : 우선순위가 낮은 스레드
$\tau_k$ : 중간 우선순위 스레드

$\tau_i$ 가 $\tau_j$ 에 의해 블록된 후 $\tau_k$ 가 실행되면, 실제로 시스템에서 발생하는 대기 시간 $W_i$ 는 다음과 같이 정의된다.

$W_i = B_j + \sum_{k} C_k$

여기서: - $B_j$ 는 $\tau_j$ 가 리소스를 점유하는 시간 - $C_k$ 는 $\tau_k$ 가 차지하는 CPU 시간

이 식은 $\tau_i$ 의 실제 대기 시간이 $\tau_j$ 와 $\tau_k$ 에 의해 결정됨을 보여준다. 이는 시스템의 예측성을 저해하고, 최악의 경우 실시간 시스템이 제 시간에 작업을 완료하지 못하는 상황을 초래할 수 있다.

우선순위 역전 문제의 해결 방법

우선순위 역전 문제를 해결하기 위해 몇 가지 접근법이 존재한다. 가장 널리 사용되는 방법은 우선순위 상속(Priority Inheritance)과 우선순위 천장(Priority Ceiling) 프로토콜이다. 이 두 가지 방법을 통해 우선순위 역전 문제를 효과적으로 해결할 수 있다.

우선순위 상속 (Priority Inheritance)

우선순위 상속은 우선순위 역전 문제를 완화하기 위한 간단한 기법이다. 이 방법에서는 낮은 우선순위의 스레드가 높은 우선순위의 스레드를 블로킹할 때, 블로킹하는 스레드의 우선순위를 상속하여 임시로 높은 우선순위를 갖게 한다. 즉, 리소스를 소유한 스레드가 해당 리소스를 해제할 때까지 우선순위가 상속된다.

수학적으로, 만약 $\tau_i$ 가 $\tau_j$ 에 의해 블로킹된다면, $\tau_j$ 의 우선순위는 $\tau_i$ 의 우선순위로 상속된다.

$P_j = P_i$

여기서: - $P_i$ 는 스레드 $\tau_i$ 의 우선순위 - $P_j$ 는 스레드 $\tau_j$ 의 우선순위

우선순위 상속을 통해, 중간 우선순위의 스레드 $\tau_k$ 는 더 이상 $\tau_j$ 보다 높은 우선순위를 가지지 못하므로, 높은 우선순위의 스레드 $\tau_i$ 가 우선순위 역전 없이 실행될 수 있다.

우선순위 천장 (Priority Ceiling)

우선순위 천장(Priority Ceiling) 프로토콜은 우선순위 역전 문제를 방지하는 또 다른 강력한 기법이다. 이 방법에서는 각 리소스에 우선순위 천장이라는 개념을 도입한다. 우선순위 천장은 해당 리소스를 잠글 수 있는 스레드들 중에서 가장 높은 우선순위를 의미한다.

우선순위 천장 프로토콜의 작동 원리는 다음과 같다:

우선순위 할당: 모든 리소스에 대해 천장 우선순위를 정의한다. 예를 들어, 리소스 $R$ 에 대해 천장 우선순위 $P_c(R)$ 를 다음과 같이 정의한다:

$P_c(R) = \max(P_i, P_j, \dots)$

여기서 $P_i, P_j, \dots$ 는 리소스 $R$ 을 필요로 하는 모든 스레드의 우선순위이다.

리소스 잠금 시점: 어떤 스레드가 리소스를 잠글 때, 해당 스레드의 현재 우선순위와 리소스의 천장 우선순위를 비교한다. 스레드의 우선순위가 천장 우선순위보다 낮으면, 이 스레드는 리소스를 잠글 수 없다. 이 경우, 해당 스레드의 우선순위를 천장 우선순위로 상승시켜야 한다.

$P_{\text{current}} = \max(P_{\text{current}}, P_c(R))$

리소스 해제: 스레드가 리소스를 해제할 때, 원래의 우선순위로 되돌아간다.

우선순위 천장 프로토콜의 주요 장점은 우선순위 역전을 근본적으로 차단한다는 점이다. 스레드가 리소스를 잠글 수 있는지 여부를 사전에 결정하기 때문에, 우선순위 역전이 발생하지 않는다. 또한, 이 프로토콜은 교착 상태(Deadlock)를 방지하는 데도 효과적이다.

우선순위 천장 프로토콜은 수학적으로 다음과 같이 표현할 수 있다:

$P_{\text{effective}}(\tau_i) = \max(P_i, P_c(R))$

여기서: - $P_{\text{effective}}(\tau_i)$ 는 스레드 $\tau_i$ 의 효과적인 우선순위 - $P_i$ 는 스레드 $\tau_i$ 의 원래 우선순위 - $P_c(R)$ 는 리소스 $R$ 의 우선순위 천장

우선순위 상속 vs 우선순위 천장

우선순위 상속과 우선순위 천장 프로토콜은 각각 장단점이 있다. 우선순위 상속은 구현이 비교적 간단하며, 대부분의 상황에서 우선순위 역전을 해결할 수 있다. 그러나 여러 리소스를 공유하는 복잡한 시스템에서는 교착 상태가 발생할 수 있다.

반면에, 우선순위 천장 프로토콜은 시스템 전체의 리소스 우선순위를 고려하기 때문에 교착 상태를 방지하고, 더 나은 실시간 성능을 보장할 수 있다. 그러나, 우선순위 천장 프로토콜의 경우 모든 리소스에 대해 천장 우선순위를 정의해야 하므로 구현이 더 복잡할 수 있다.

우선순위 역전 문제를 해결하기 위해 두 가지 방법을 혼용하거나 상황에 맞게 선택하는 것이 실시간 시스템의 성능을 극대화하는 데 중요하다.

실시간 시스템에서의 우선순위 역전 예시

우선순위 역전 문제는 다양한 실시간 시스템에서 발생할 수 있으며, 그 영향을 구체적으로 이해하기 위해 실제 사례를 통해 설명할 수 있다.

예시 1: 우주 탐사 로봇

예를 들어, NASA의 우주 탐사 로봇에서 우선순위 역전 문제가 발생했던 사례가 있다. 우주 탐사 로봇의 임무 스케줄러가 낮은 우선순위의 데이터 로깅 작업에 의해 블로킹되었고, 그 사이에 중요한 임무 수행 작업이 차단되었다. 이로 인해 로봇의 임무 수행이 지연되었고, 이 문제를 해결하기 위해 우선순위 상속이 적용되었다.

예시 2: 항공기 제어 시스템

또 다른 예시로, 항공기 제어 시스템에서의 우선순위 역전 문제를 들 수 있다. 항공기 제어 시스템에서 고도 제어와 같은 중요한 작업이 우선순위 역전으로 인해 지연될 경우, 안전에 치명적인 영향을 미칠 수 있다. 이러한 시스템에서는 우선순위 천장 프로토콜이 적용되어 우선순위 역전 및 교착 상태를 방지하고 있다.

이와 같은 예시를 통해, 실시간 시스템에서의 우선순위 역전 문제가 얼마나 중요한지 알 수 있으며, 이를 해결하기 위한 적절한 기법을 선택하는 것이 필수적이다.