396.87 실시간 운영체제(RTOS) 기반 임무 태스크 스케줄링

396.87 실시간 운영체제(RTOS) 기반 임무 태스크 스케줄링

1. 개요

로봇 시스템이 임무를 수행하기 위해서는 다수의 소프트웨어 태스크가 시간적 제약 조건을 만족하면서 동시다발적으로 실행되어야 한다. 실시간 운영체제(Real-Time Operating System, RTOS)는 이러한 시간 결정성(temporal determinism)을 보장하는 핵심 소프트웨어 기반 구조이며, 임무 관리 시스템에서 태스크 스케줄링의 기저를 형성한다. 본 절에서는 RTOS의 기본 개념과 실시간 스케줄링 이론, 그리고 로봇 임무 태스크에 대한 적용 방법론을 체계적으로 다룬다.

2. RTOS의 정의와 실시간 시스템 분류

2.1 실시간 시스템의 정의

실시간 시스템(Real-Time System)이란 계산의 정확성뿐 아니라 결과가 산출되는 시점의 정확성이 시스템의 올바른 동작을 결정하는 시스템을 의미한다. 실시간 시스템은 시간 제약의 엄격성에 따라 다음과 같이 분류된다.

  • 경성 실시간 시스템(Hard Real-Time System): 마감 시한(deadline)을 위반하면 시스템 장애 또는 치명적 결과를 초래한다. 로봇의 비상 정지(emergency stop) 처리, 드론의 자세 제어 루프 등이 이에 해당한다.
  • 연성 실시간 시스템(Soft Real-Time System): 마감 시한 위반이 시스템 성능 저하를 야기하지만 치명적 장애로 이어지지는 않는다. 영상 스트리밍, 사용자 인터페이스 갱신 등이 대표적이다.
  • 견고 실시간 시스템(Firm Real-Time System): 마감 시한을 초과한 결과는 무용(no value)하지만 시스템 자체의 안전성에는 영향을 미치지 않는다.

2.2 RTOS의 핵심 특성

RTOS는 범용 운영체제(General-Purpose Operating System, GPOS)와 달리 다음의 특성을 보장한다.

  1. 결정론적 스케줄링(Deterministic Scheduling): 태스크의 실행 순서와 시점이 예측 가능하다.
  2. 한정된 인터럽트 지연 시간(Bounded Interrupt Latency): 인터럽트 발생 시점부터 해당 인터럽트 서비스 루틴(ISR)의 실행 시작까지 소요되는 시간이 상한 값 이내로 보장된다.
  3. 한정된 컨텍스트 전환 시간(Bounded Context Switch Time): 태스크 간 전환에 소요되는 시간이 상한 값 이내이다.
  4. 우선순위 기반 선점(Priority-Based Preemption): 우선순위가 높은 태스크가 낮은 태스크를 즉시 선점할 수 있다.

대표적인 RTOS로는 FreeRTOS, VxWorks, QNX Neutrino, Zephyr, RTEMS, \muC/OS 등이 있으며, 리눅스 커널에 PREEMPT_RT 패치를 적용한 실시간 리눅스(RT-Linux)도 로봇 분야에서 널리 사용된다.

3. 실시간 태스크 모델

3.1 주기적 태스크 모델

로봇 임무 태스크의 대부분은 주기적(periodic) 특성을 갖는다. 주기적 태스크 \tau_i는 다음의 매개변수로 정의된다.

\tau_i = (C_i, T_i, D_i)

여기서 C_i는 최악 실행 시간(Worst-Case Execution Time, WCET), T_i는 주기(period), D_i는 상대적 마감 시한(relative deadline)이다. 특수한 경우로 D_i = T_i인 시스템을 암묵적 마감(implicit deadline) 시스템이라 한다.

3.2 비주기적 태스크와 산발적 태스크

  • 비주기적 태스크(Aperiodic Task): 임의의 시점에 도착하며, 연성 마감 시한을 갖는다. 예를 들어, 운용자로부터의 임무 변경 명령 처리가 이에 해당한다.
  • 산발적 태스크(Sporadic Task): 비주기적이되, 연속된 두 인스턴스 사이에 최소 도착 간격(minimum inter-arrival time)이 보장된다. 장애 감지 이벤트, 비상 임무 전환 등이 대표적이다.

3.3 CPU 이용률

n개의 주기적 태스크로 구성된 태스크 집합의 총 CPU 이용률 U는 다음과 같이 정의된다.

U = \sum_{i=1}^{n} \frac{C_i}{T_i}

이 값은 스케줄 가능성(schedulability) 판정의 기본 지표로 사용된다.

4. 단일 프로세서 실시간 스케줄링 알고리즘

4.1 Rate-Monotonic Scheduling (RMS)

Rate-Monotonic Scheduling(RMS)은 Liu와 Layland(1973)가 제안한 고정 우선순위(fixed-priority) 스케줄링 알고리즘이다. 주기가 짧은 태스크에 높은 우선순위를 부여하는 방식으로, 다음의 충분 조건을 만족하면 스케줄 가능하다.

U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n} - 1)

n \to \infty일 때 이 상한은 \ln 2 \approx 0.693에 수렴한다. RMS는 고정 우선순위 스케줄링 알고리즘 중 최적(optimal)임이 증명되어 있다.

RMS의 장점:

  • 구현이 간단하며, 대부분의 RTOS에서 기본 지원한다.
  • 런타임 오버헤드가 낮다.
  • 스케줄 가능성 분석이 오프라인에서 가능하다.

RMS의 한계:

  • CPU 이용률 상한이 약 69.3%로 제한적이다.
  • 조화 주기(harmonic periods)가 아닌 경우 이용률이 더욱 낮아질 수 있다.

4.2 Deadline-Monotonic Scheduling (DMS)

Deadline-Monotonic Scheduling(DMS)은 Leung과 Whitehead(1982)가 제안하였으며, 상대적 마감 시한 D_i가 짧은 태스크에 높은 우선순위를 할당한다. D_i \leq T_i인 제약 마감(constrained deadline) 시스템에서 DMS는 고정 우선순위 알고리즘 중 최적이다.

4.3 Earliest Deadline First (EDF)

Earliest Deadline First(EDF)는 동적 우선순위(dynamic-priority) 알고리즘으로, 현재 시점에서 절대 마감 시한이 가장 임박한 태스크에 최고 우선순위를 부여한다. Liu와 Layland(1973)는 암묵적 마감 시스템에서 EDF의 스케줄 가능 조건이 다음과 같음을 증명하였다.

U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1

EDF는 단일 프로세서 환경에서 최적의 동적 우선순위 알고리즘이며, CPU 이용률을 100%까지 활용할 수 있다는 이론적 장점을 갖는다. 그러나 과부하(overload) 상황에서 예측 불가능한 마감 위반이 발생할 수 있다는 단점이 있다.

4.4 Least Laxity First (LLF)

Least Laxity First(LLF) 알고리즘은 여유 시간(laxity)이 가장 적은 태스크에 최고 우선순위를 할당한다. 태스크 \tau_i의 여유 시간 L_i(t)는 시점 t에서 다음과 같이 정의된다.

L_i(t) = d_i - t - c_i(t)

여기서 d_i는 절대 마감 시한, c_i(t)는 시점 t 이후 남은 실행 시간이다. LLF는 EDF와 동일한 최적성을 갖지만, 빈번한 컨텍스트 전환(context switching)이 발생하여 실용성이 제한적이다.

5. 다중 프로세서 실시간 스케줄링

현대 로봇 시스템은 멀티코어 프로세서를 탑재하는 경우가 일반적이므로, 다중 프로세서 스케줄링 기법이 필수적이다.

5.1 분할 스케줄링(Partitioned Scheduling)

태스크를 각 프로세서에 정적으로 할당한 후, 각 프로세서에서 단일 프로세서 스케줄링 알고리즘을 독립적으로 적용하는 방식이다.

  • 장점: 분석이 용이하고, 캐시 친화성(cache affinity)이 높으며, 마이그레이션 오버헤드가 없다.
  • 단점: 태스크 할당이 빈 패킹(bin-packing) 문제의 특수 형태로, NP-hard이다.

대표적인 할당 알고리즘으로 First-Fit Decreasing(FFD), Best-Fit Decreasing(BFD), Worst-Fit Decreasing(WFD) 등이 있다.

5.2 글로벌 스케줄링(Global Scheduling)

모든 태스크가 단일 준비 큐(ready queue)에 배치되며, 임의의 프로세서에서 실행될 수 있다. 글로벌 EDF(G-EDF)와 글로벌 RMS(G-RMS)가 대표적이다.

  • 장점: 부하 균형(load balancing)이 자동으로 이루어진다.
  • 단점: Dhall의 효과(Dhall’s effect)에 의해 이용률이 매우 낮은 상황에서도 마감 위반이 발생할 수 있다. 마이그레이션 오버헤드도 고려해야 한다.

5.3 반분할 스케줄링(Semi-Partitioned Scheduling)

분할 스케줄링과 글로벌 스케줄링의 장점을 결합한 접근법이다. 대부분의 태스크는 특정 프로세서에 고정 할당되지만, 일부 태스크는 여러 프로세서 간에 마이그레이션이 허용된다.

6. 우선순위 역전과 해결 기법

6.1 우선순위 역전(Priority Inversion)

우선순위 역전은 우선순위가 높은 태스크가 낮은 우선순위 태스크가 점유 중인 공유 자원을 대기하는 동안, 중간 우선순위 태스크가 실행됨으로써 고우선순위 태스크의 실행이 무한정 지연될 수 있는 현상이다. 1997년 화성 탐사 로버 Mars Pathfinder에서 발생한 우선순위 역전 사례는 이 문제의 심각성을 실증적으로 보여준 대표적 사건이다.

6.2 우선순위 상속 프로토콜(Priority Inheritance Protocol, PIP)

Sha, Rajkumar, Lehoczky(1990)가 제안한 우선순위 상속 프로토콜은, 낮은 우선순위 태스크가 공유 자원을 점유한 상태에서 고우선순위 태스크가 해당 자원을 요청하면, 자원을 점유한 태스크의 우선순위를 요청 태스크의 우선순위로 일시적으로 승격시키는 기법이다.

6.3 우선순위 상한 프로토콜(Priority Ceiling Protocol, PCP)

우선순위 상한 프로토콜은 각 공유 자원에 대해 해당 자원을 사용할 수 있는 태스크의 최고 우선순위를 상한 우선순위(ceiling priority)로 사전 정의한다. 태스크가 자원을 획득하려면 자신의 우선순위가 현재 시스템 내 모든 잠긴 자원의 상한 우선순위보다 높아야 한다. PCP는 연쇄 차단(chained blocking)과 교착 상태(deadlock)를 원천적으로 방지한다.

6.4 즉시 상한 프로토콜(Immediate Ceiling Priority Protocol, ICPP)

ICPP는 PCP의 변형으로, 태스크가 자원을 획득하는 즉시 해당 자원의 상한 우선순위로 승격된다. 구현이 PCP보다 단순하며, 대부분의 RTOS에서 이 방식을 채택하고 있다.

7. 로봇 임무 태스크의 RTOS 스케줄링 적용

7.1 임무 태스크의 계층적 분류

로봇 시스템의 임무 관련 태스크는 시간 제약의 엄격성에 따라 계층적으로 분류된다.

계층태스크 유형주기실시간 유형예시
최하위안전 태스크1–10 ms경성 실시간비상 정지, 충돌 회피
하위제어 태스크1–20 ms경성 실시간모터 제어, 자세 안정화
중위인지 태스크20–100 ms연성/견고 실시간장애물 탐지, 측위
상위임무 관리 태스크100 ms–1 s연성 실시간임무 상태 전이, 재계획
최상위통신/보고 태스크1–10 s연성 실시간GCS 상태 보고, 로그 기록

7.2 임무 관리자 태스크의 설계 패턴

RTOS 기반 임무 관리자의 설계에서는 다음의 패턴이 권장된다.

  1. 임무 디스패처 태스크(Mission Dispatcher Task): 임무 큐에서 대기 중인 임무를 꺼내어 실행 가능한 과업 태스크로 분배하는 역할을 수행한다. 중위 우선순위를 부여하며, 공유 데이터 구조에 대한 접근 시 뮤텍스(mutex)를 활용한다.

  2. 임무 모니터 태스크(Mission Monitor Task): 주기적으로 임무 수행 상태를 점검하고, 이상 상태 발생 시 임무 디스패처에 이벤트를 전달한다. 세마포어(semaphore) 또는 이벤트 플래그(event flag) 기반 동기화를 사용한다.

  3. 비상 처리 태스크(Emergency Handler Task): 최고 우선순위로 동작하며, 비상 정지 명령 수신 시 모든 임무 태스크를 선점하고 안전 절차를 수행한다.

7.3 태스크 간 통신 메커니즘

RTOS 환경에서 임무 태스크 간 통신은 다음의 메커니즘을 통해 이루어진다.

  • 메시지 큐(Message Queue): 임무 명령, 상태 정보 등 구조화된 데이터의 비동기 전달에 사용된다. 우선순위 기반 메시지 큐는 긴급 임무 명령의 즉시 처리를 보장한다.
  • 뮤텍스(Mutex): 공유 자원(예: 임무 상태 테이블, 센서 데이터 버퍼)에 대한 상호 배제(mutual exclusion)를 보장한다.
  • 세마포어(Semaphore): 태스크 동기화 및 이벤트 신호 전달에 사용된다. 이진 세마포어(binary semaphore)와 카운팅 세마포어(counting semaphore)로 구분된다.
  • 이벤트 그룹(Event Group): 다수의 이벤트 플래그를 비트마스크로 관리하여 복수 조건의 동시 충족 여부를 판정한다. 임무 전환 시 다수의 전제 조건 확인에 적합하다.

8. 스케줄 가능성 분석

8.1 정적 분석 기법

8.1.1 이용률 기반 분석

RMS에 대한 Liu-Layland 충분 조건과 EDF에 대한 이용률 조건은 가장 기본적인 정적 분석 기법이다. 그러나 이용률 기반 분석은 충분 조건이므로, 조건을 만족하지 않더라도 실제로는 스케줄 가능한 경우가 존재한다.

8.1.2 응답 시간 분석(Response Time Analysis, RTA)

고정 우선순위 스케줄링에서 태스크 \tau_i의 최악 응답 시간 R_i는 다음의 반복 방정식으로 계산된다.

R_i^{(k+1)} = C_i + \sum_{j \in \text{hp}(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j

여기서 \text{hp}(i)는 태스크 \tau_i보다 우선순위가 높은 태스크의 집합이다. R_i^{(0)} = C_i로 초기화하며, R_i \leq D_i이면 태스크 \tau_i는 스케줄 가능하다. RTA는 이용률 기반 분석보다 정밀한 필요 충분 조건을 제공한다.

8.2 동적 분석 기법

8.2.1 시뮬레이션 기반 검증

실제 태스크 집합의 실행을 시뮬레이션하여 마감 위반 여부를 확인하는 기법이다. 하이퍼피리어드(hyperperiod), 즉 모든 태스크 주기의 최소 공배수 구간을 시뮬레이션하면 주기적 태스크 집합의 스케줄 가능성을 완전히 검증할 수 있다.

8.2.2 런타임 모니터링

RTOS 내장 프로파일링 도구를 활용하여 태스크별 실행 시간, 마감 여유(slack), 선점 빈도 등을 실시간으로 모니터링한다. Tracealyzer, SEGGER SystemView 등의 도구가 대표적이다.

9. RTOS 기반 임무 스케줄링의 실용적 고려사항

9.1 WCET 추정의 어려움

WCET의 정확한 산출은 실시간 스케줄링 분석의 근간이지만, 현대 프로세서의 복잡한 파이프라인, 캐시 메모리 계층, 분기 예측기(branch predictor) 등으로 인해 정적 분석만으로는 정밀한 WCET 추정이 어렵다. 정적 분석 도구(aiT, Bound-T)와 측정 기반 접근법(measurement-based approach)의 결합이 권장된다.

9.2 전력 인식 스케줄링(Power-Aware Scheduling)

배터리로 구동되는 로봇(이동 로봇, 드론)의 경우, 임무 태스크 스케줄링 시 에너지 소비를 최적화하는 전략이 필수적이다. 동적 전압 및 주파수 스케일링(Dynamic Voltage and Frequency Scaling, DVFS)을 활용하여, 마감 시한 내에 임무를 완료하면서 프로세서의 동작 주파수를 동적으로 조정한다. EDF 기반 DVFS 스케줄링에서 태스크 \tau_i의 최적 주파수 f_i^*는 다음과 같이 결정된다.

f_i^* = f_{\max} \cdot \frac{C_i}{D_i - \sum_{j \in \text{hp}(i)} C_j}

여기서 f_{\max}는 프로세서의 최대 주파수이다.

9.3 혼합 임계도 스케줄링(Mixed-Criticality Scheduling)

로봇 시스템에서는 안전 관련 경성 실시간 태스크와 임무 관리 관련 연성 실시간 태스크가 동일 플랫폼에서 공존한다. 혼합 임계도 스케줄링(Vestal, 2007)은 태스크의 임계도 수준에 따라 차별화된 WCET 추정치를 사용하며, 고임계도 태스크의 시간 보장을 우선시한다. 시스템 모드가 저임계도 모드(LO-mode)에서 고임계도 모드(HI-mode)로 전환될 때, 저임계도 태스크의 실행이 중단되거나 주기가 연장될 수 있다.

9.4 이종 프로세서 환경

GPU, FPGA, DSP 등 이종 가속기를 포함하는 로봇 시스템에서는 태스크의 특성에 따라 적합한 프로세서에 할당하는 이종 스케줄링(heterogeneous scheduling)이 필요하다. 영상 처리 태스크는 GPU에, 제어 루프는 실시간 코어에, 임무 관리 로직은 범용 코어에 할당하는 것이 일반적 패턴이다.

10. RTOS 플랫폼과 로봇 임무 관리의 통합 사례

10.1 FreeRTOS 기반 경량 임무 스케줄러

마이크로컨트롤러 기반 소형 로봇에서는 FreeRTOS가 널리 사용된다. FreeRTOS의 태스크 우선순위 수준, 소프트웨어 타이머, 태스크 알림(task notification) 메커니즘을 활용하여 임무 상태 머신을 구현할 수 있다. FreeRTOS의 configMAX_PRIORITIES 설정을 통해 임무 태스크의 우선순위 구간을 체계적으로 관리한다.

10.2 ROS 2와 DDS 미들웨어의 실시간 성능

ROS 2는 DDS(Data Distribution Service) 미들웨어를 기반으로 하며, 실시간 실행기(Executor)를 제공한다. rclcpp의 실시간 실행기(StaticSingleThreadedExecutor, MultiThreadedExecutor)를 활용하면 콜백 기반 태스크의 실행 순서를 제어할 수 있다. 다만, ROS 2 자체는 경성 실시간 보장을 제공하지 않으므로, 경성 실시간 태스크는 별도의 RTOS 계층에서 실행하고 ROS 2와 공유 메모리 또는 전용 통신 채널을 통해 연동하는 설계가 권장된다.

10.3 QNX Neutrino 기반 임무 관리 아키텍처

QNX Neutrino는 마이크로커널 아키텍처를 채택한 POSIX 호환 RTOS로, 자동차 및 항공 분야에서 광범위하게 사용된다. QNX의 적응형 분할 스케줄러(Adaptive Partitioning Scheduler)는 태스크 그룹 단위로 CPU 시간을 보장하면서도, 유휴 시간을 다른 분할에 재배분하여 자원 이용률을 극대화한다. 이 특성은 임무 관리 태스크와 제어 태스크 간의 자원 격리에 특히 유용하다.

11. 향후 연구 방향

RTOS 기반 임무 태스크 스케줄링 분야에서는 다음의 연구 주제가 활발히 탐구되고 있다.

  1. 학습 기반 적응형 스케줄링: 강화 학습(reinforcement learning)을 활용하여 런타임 환경 변화에 적응적으로 태스크 우선순위와 주기를 조정하는 기법이 연구되고 있다.
  2. 확률적 WCET 분석: 기존의 최악 경우 분석 대신 확률적 분포(probabilistic distribution)를 활용한 WCET 추정이 연성 실시간 임무 태스크에 적용되고 있다.
  3. 다중 에이전트 실시간 스케줄링: 다중 로봇 시스템에서 네트워크를 통한 분산 실시간 스케줄링과 임무 할당의 통합 최적화가 핵심 과제로 부상하고 있다.
  4. 임계도 인식 임무 관리: 혼합 임계도 스케줄링 이론을 임무 관리 계층에 확장하여, 임무의 중요도에 따라 동적으로 시스템 자원을 재배분하는 프레임워크 설계가 진행되고 있다.

12. 참고 문헌

  • Liu, C. L., & Layland, J. W. (1973). “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.” Journal of the ACM, 20(1), 46–61.
  • Sha, L., Rajkumar, R., & Lehoczky, J. P. (1990). “Priority Inheritance Protocols: An Approach to Real-Time Synchronization.” IEEE Transactions on Computers, 39(9), 1175–1185.
  • Leung, J. Y.-T., & Whitehead, J. (1982). “On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks.” Performance Evaluation, 2(4), 237–250.
  • Vestal, S. (2007). “Preemptive Scheduling of Multi-Criticality Systems with Varying Degrees of Execution Time Assurance.” Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS), 239–243.
  • Burns, A., & Davis, R. I. (2019). “Mixed-Criticality Systems: A Review (Ninth Edition).” University of York Technical Report.
  • FreeRTOS Reference Manual (v10.x), Amazon Web Services.
  • QNX Neutrino RTOS System Architecture Guide, BlackBerry QNX.

본 절의 내용은 2025년 기준 RTOS 기반 실시간 스케줄링 이론과 로봇 임무 관리 적용 사례를 반영하였다.