1295.22 단일 스레드 내 순차적 Tick과 논리적 동시성

1. 순차적 Tick의 실행 구조

Parallel 노드가 자식에 틱을 전파하는 과정은 단일 스레드 내에서 엄격한 순차적(sequential) 실행으로 이루어진다. N개의 자식 C_1, C_2, \ldots, C_N에 대해, 하나의 틱 주기 t_k에서의 실행 타임라인은 다음과 같이 직선적으로 전개된다(Colledanchise & Ögren, 2018).

t_k: \quad [\text{tick}(C_1)] \rightarrow [\text{tick}(C_2)] \rightarrow \cdots \rightarrow [\text{tick}(C_N)] \rightarrow [\text{정책 평가}]

각 대괄호는 해당 단계가 완전히 완료된 후 다음 단계로 진행됨을 나타낸다. C_1의 tick()이 상태를 반환하고 제어권을 Parallel 노드에 양도한 후에야 C_2의 tick()이 호출된다.

2. 순차적 Tick에서 논리적 동시성이 성립하는 원리

단일 틱 내에서 자식들이 순차적으로 실행되면서도 논리적 동시성이 성립하는 원리는 다음과 같다.

2.1 매 틱 전원 참여

Sequence나 Fallback 노드와 달리, Parallel 노드는 모든 자식에 매 틱마다 틱을 전달한다. 어떤 자식도 틱 수신에서 배제되지 않으므로, 모든 자식이 동등한 진행 기회를 갖는다.

2.2 RUNNING 상태의 지속

자식 노드가 RUNNING을 반환하면, 해당 자식은 내부 상태를 유지한 채 다음 틱을 기다린다. 다음 틱에서 틱을 수신하면 이전 상태로부터 실행을 재개한다. 이는 코루틴의 yield와 resume 패턴과 동일하다.

2.3 틱 단위의 진행

각 자식은 매 틱마다 한 단위(one step)의 작업을 수행하고 RUNNING을 반환한다. 다수의 틱에 걸쳐 모든 자식이 한 단위씩 진행하면, 외부에서 관찰하면 여러 행동이 동시에 진행되는 것으로 보인다.

3. 실행 타임라인 시각화

3개의 자식 C_1, C_2, C_3을 갖는 Parallel 노드에서, 각 자식이 3틱에 걸쳐 완료되는 경우의 타임라인을 시각화한다.

시간축 →

Tick 1: [C1: step1] [C2: step1] [C3: step1]
Tick 2: [C1: step2] [C2: step2] [C3: step2]
Tick 3: [C1: step3] [C2: step3] [C3: step3]
         (SUCCESS)   (SUCCESS)   (SUCCESS)

각 틱 내에서 C_1 \rightarrow C_2 \rightarrow C_3 순서로 순차 실행되지만, 틱 단위로 보면 세 자식이 모두 한 단계씩 진행하므로 논리적 동시성이 성립한다.

비교를 위해, 동일한 작업을 Sequence 노드로 실행하면 다음과 같다.

시간축 →

Tick 1-3: [C1: step1] [C1: step2] [C1: step3] (SUCCESS)
Tick 4-6: [C2: step1] [C2: step2] [C2: step3] (SUCCESS)
Tick 7-9: [C3: step1] [C3: step2] [C3: step3] (SUCCESS)

Sequence에서는 C_1이 완전히 완료된 후 C_2가 시작되므로, 총 9틱이 소요된다. Parallel에서는 3틱 만에 모든 자식이 완료된다.

4. 순차적 실행의 함의

4.1 블랙보드 갱신의 순서 의존성

C_1이 블랙보드에 값을 기록하면, 동일 틱 내에서 이후에 실행되는 C_2와 C_3가 그 값을 읽을 수 있다. 이 순서 의존성은 결정론적이지만, 설계 시 명시적으로 의도하지 않은 경우 예상치 못한 동작을 유발할 수 있다.

Tick k:
  C1.tick() → 블랙보드에 obstacle_detected = true 기록
  C2.tick() → 블랙보드에서 obstacle_detected 읽기 (true)
  C3.tick() → 블랙보드에서 obstacle_detected 읽기 (true)

만약 C_2가 C_1보다 먼저 정의되었다면, C_2는 이전 틱의 obstacle_detected 값을 읽게 되어 동작이 달라진다. 이는 자식의 정의 순서가 실행 의미론에 영향을 미치는 것을 의미한다.

4.2 tick() 실행 시간의 누적 효과

Parallel 노드의 단일 틱 실행 시간은 모든 자식의 tick() 실행 시간의 합이다.

T_{\text{parallel\_tick}} = \sum_{i=1}^{N} t_i

자식 수 N이 증가하면 틱 실행 시간이 선형적으로 증가한다. 실시간 시스템에서 틱 주기 \Delta t가 고정되어 있는 경우, T_{\text{parallel\_tick}} > \Delta t이면 틱 오버런(overrun)이 발생하여 시스템의 실시간성이 위반된다.

4.3 비차단 tick() 구현의 중요성

순차적 실행에서 하나의 자식이 tick() 내부에서 차단(blocking) 연산을 수행하면, 후속 자식의 틱이 지연된다. 예를 들어, C_2의 tick()이 100ms 동안 차단되면, C_3는 100ms 지연 후에야 틱을 수신한다.

[C1: 1ms] [C2: 100ms (차단)] [C3: 1ms]
→ 전체 틱 시간: 102ms (틱 주기 초과 가능)

이를 방지하기 위해 모든 자식의 tick()은 비차단적으로 구현하고, 장시간 작업은 별도 스레드에 위임한 후 RUNNING을 반환해야 한다.

5. 라운드 로빈 스케줄링과의 유사성

Parallel 노드의 순차적 틱 전파는 운영체제의 라운드 로빈(round-robin) 스케줄링과 유사하다.

핵심적 차이는 라운드 로빈이 선점형(preemptive)인 반면, Parallel 노드는 협력적(cooperative)이라는 점이다. Parallel 노드에서 자식은 tick() 반환으로 자발적으로 제어권을 양도하며, 외부에 의한 강제 전환은 없다.

6. 참고 문헌

• Colledanchise, M., & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. CRC Press.
• Faconti, D., & contributors. (2024). BehaviorTree.CPP Documentation. https://www.behaviortree.dev/

Version: 1.0-2026.04.03