1293.97 우선순위 역전 방지와 Tick

1. 우선순위 역전의 정의

우선순위 역전(priority inversion)이란, 높은 우선순위의 스레드가 낮은 우선순위의 스레드가 보유한 공유 자원(mutex 등)을 대기하는 동안, 중간 우선순위의 스레드가 실행됨으로써 높은 우선순위 스레드의 실행이 무기한 지연되는 현상이다. 이 현상은 실시간 시스템에서 데드라인 위반의 주요 원인 중 하나이며, 행동 트리의 Tick 실행에서도 발생할 수 있다(Williams, 2019).

2. Tick 실행에서의 우선순위 역전 시나리오

행동 트리의 Tick 실행 스레드가 높은 우선순위로 설정되어 있고, 블랙보드나 공유 데이터에 대한 mutex를 통해 다른 스레드와 자원을 공유하는 경우, 우선순위 역전이 발생할 수 있다.

시나리오:
  스레드 H (높음): Tick 실행 스레드 — 블랙보드 mutex 대기
  스레드 M (중간): ROS2 콜백 처리 — CPU 점유 중
  스레드 L (낮음): 센서 데이터 처리 — 블랙보드 mutex 보유 중

  실행 흐름:
    1. 스레드 L이 블랙보드 mutex를 획득하고 센서 데이터 갱신 시작
    2. 스레드 H(Tick)가 실행되어 블랙보드 mutex 대기
    3. 스레드 M이 도착하여 스레드 L을 선점 (M > L)
    4. 스레드 L은 실행 불가 → mutex 해제 불가
    5. 스레드 H는 mutex 대기 → Tick 데드라인 위반

이 시나리오에서 스레드 H는 스레드 M보다 높은 우선순위를 가지지만, 스레드 L이 mutex를 보유하고 있고 스레드 M에 의해 선점되어 mutex를 해제하지 못하므로, 스레드 H는 간접적으로 스레드 M에 의해 블로킹된다.

3. 우선순위 상속 프로토콜

우선순위 상속(priority inheritance)은 mutex를 보유한 낮은 우선순위 스레드가, 해당 mutex를 대기하는 높은 우선순위 스레드의 우선순위를 일시적으로 상속받는 메커니즘이다. 이를 통해 중간 우선순위 스레드에 의한 선점을 방지하여 우선순위 역전을 해소한다.

#include <pthread.h>

// 우선순위 상속 속성의 mutex 생성
pthread_mutex_t createPriorityInheritMutex() {
    pthread_mutex_t mutex;
    pthread_mutexattr_t attr;
    
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
    pthread_mutex_init(&mutex, &attr);
    pthread_mutexattr_destroy(&attr);
    
    return mutex;
}

우선순위 상속 적용 후의 동작:

적용 후:
  1. 스레드 L이 블랙보드 mutex 획득
  2. 스레드 H가 mutex 대기 → 스레드 L의 우선순위가 H로 상승
  3. 스레드 M이 도착하지만 스레드 L(이제 H와 동일 우선순위)을 선점 불가
  4. 스레드 L이 작업 완료 후 mutex 해제 → 우선순위 원복
  5. 스레드 H가 mutex 획득 → Tick 정상 실행

4. 우선순위 천장 프로토콜

우선순위 천장(priority ceiling) 프로토콜은 mutex에 천장 우선순위(ceiling priority)를 설정하고, mutex를 획득하는 스레드가 즉시 해당 천장 우선순위로 상승하는 메커니즘이다. 우선순위 상속과 달리 대기가 발생하기 전에 미리 우선순위를 상승시키므로, 교착 상태(deadlock)를 예방하는 추가적인 이점이 있다.

pthread_mutex_t createPriorityCeilingMutex(int ceiling) {
    pthread_mutex_t mutex;
    pthread_mutexattr_t attr;
    
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_PROTECT);
    pthread_mutexattr_setprioceiling(&attr, ceiling);
    pthread_mutex_init(&mutex, &attr);
    pthread_mutexattr_destroy(&attr);
    
    return mutex;
}

// 블랙보드 mutex: Tick 스레드의 우선순위를 천장으로 설정
auto bb_mutex = createPriorityCeilingMutex(TICK_THREAD_PRIORITY);

5. C++ std::mutex와 우선순위 역전

C++ 표준 라이브러리의 std::mutex는 우선순위 상속이나 천장 프로토콜을 보장하지 않는다. 실시간 요구가 있는 행동 트리에서는 POSIX mutex를 직접 사용하거나, 우선순위 상속을 지원하는 래퍼 클래스를 구현해야 한다.

class RealtimeMutex {
public:
    RealtimeMutex() {
        pthread_mutexattr_t attr;
        pthread_mutexattr_init(&attr);
        pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
        pthread_mutex_init(&mutex_, &attr);
        pthread_mutexattr_destroy(&attr);
    }

    ~RealtimeMutex() {
        pthread_mutex_destroy(&mutex_);
    }

    void lock() { pthread_mutex_lock(&mutex_); }
    void unlock() { pthread_mutex_unlock(&mutex_); }
    bool try_lock() { return pthread_mutex_trylock(&mutex_) == 0; }

private:
    pthread_mutex_t mutex_;
};

6. 락 프리 기법에 의한 역전 회피

우선순위 역전을 근본적으로 회피하는 방법은 mutex를 사용하지 않는 것이다. 락 프리(lock-free) 자료 구조와 원자적 연산(atomic operation)을 사용하면 스레드 간 블로킹이 발생하지 않으므로 우선순위 역전이 원천적으로 방지된다.

6.1 원자적 변수를 통한 블랙보드 접근

단순 타입의 블랙보드 값은 std::atomic을 사용하여 락 없이 공유할 수 있다.

// 락 프리 공유 데이터
std::atomic<double> battery_level{1.0};
std::atomic<bool> emergency_stop{false};

// Tick 스레드에서 읽기 (블로킹 없음)
BT::NodeStatus tick() override {
    double level = battery_level.load(std::memory_order_acquire);
    return (level > threshold_) ? NodeStatus::SUCCESS : NodeStatus::FAILURE;
}

// 센서 스레드에서 쓰기 (블로킹 없음)
void sensorCallback(double level) {
    battery_level.store(level, std::memory_order_release);
}

6.2 이중 버퍼링

복합 데이터(메시지, 구조체)의 공유에는 이중 버퍼(double buffer) 패턴을 사용한다. 쓰기 스레드가 백 버퍼에 데이터를 작성하고, 원자적으로 버퍼를 교환하면, 읽기 스레드는 항상 완전한 데이터를 락 없이 읽을 수 있다.

template<typename T>
class DoubleBuffer {
public:
    void write(const T& data) {
        int back = 1 - front_.load(std::memory_order_acquire);
        buffers_[back] = data;
        front_.store(back, std::memory_order_release);
    }

    const T& read() const {
        return buffers_[front_.load(std::memory_order_acquire)];
    }

private:
    std::array<T, 2> buffers_;
    std::atomic<int> front_{0};
};

7. Tick 실행에서의 실무 지침

우선순위 역전의 방지는 실시간 Tick 보장의 필수 요소이며, 행동 트리 설계 단계에서 공유 자원의 접근 패턴과 스레드 우선순위 구조를 체계적으로 설계해야 한다.

참고 문헌

• Colledanchise, M., & Ogren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Faconti, D. (2022). BehaviorTree.CPP documentation and API reference. https://www.behaviortree.dev/
• Williams, A. (2019). C++ Concurrency in Action (2nd ed.). Manning Publications.