# 1. 방향성 비순환 그래프(DAG) 기반 패키지 작업 스케줄링 프로세스

수십 혹은 수백 개의 소프트웨어 패키지가 상호 작용하는 대규모 ROS 2 워크스페이스에서 빌드의 무결성(Integrity)과 효율성을 동시에 달성하기 위해서는 어떠한 순서로 패키지를 컴파일할 것인지 결정하는 엄밀한 수학적 모델이 요구된다. Colcon 빌드 시스템은 워크스페이스 내 패키지들의 의존성 정보를 위상 수학(Topology)의 방향성 비순환 그래프(Directed Acyclic Graph, 이하 DAG) 형태로 모델링하여 최적의 빌드 실행 순서를 도출하는 작업 스케줄링 알고리즘을 구현한다.

1.1 DAG(Directed Acyclic Graph) 모델링 이론

DAG는 노드(Node)와 간선(Edge)으로 구성된 그래프 이론의 한 형태로, 간선에 방향성이 존재하며 임의의 노드에서 출발하여 자기 자신으로 되돌아오는 순환 경로(Cycle)가 존재하지 않는 구조를 의미한다. Colcon의 태스크 스케줄링 아키텍처에서 DAG 모델은 다음의 두 가지 요소로 매핑(Mapping)된다.

노드(Node): 빌드의 대상이 되는 개별 소프트웨어 패키지(예: rclcpp, std_msgs, 사용자 정의 제어기 패키지)를 나타낸다.
방향성 간선(Directed Edge): 패키지 간의 빌드 의존성(Build Dependency)을 의미한다. 노드 A에서 노드 B로 향하는 간선(A $\rightarrow$ B)이 존재한다면, 이는 “패키지 B가 성공적으로 빌드되기 위해서는 반드시 패키지 A의 빌드 및 설치(Install)가 선행되어야 함“을 수학적으로 엄밀하게 정의한 것이다.

이러한 DAG 구조를 형성하기 위해 Colcon은 빌드 시작 시 워크스페이스 내의 모든 package.xml (ROS 패키지의 경우) 또는 기타 메타데이터 파일을 탐색하고 파싱하여, 명시된 build_depend, exec_depend 태그 정보를 바탕으로 간선들을 동적으로 생성한다. 순환 경로(유사: A가 B를 의존하고, B가 다시 A를 의존하는 상태)가 감지될 경우, 시스템은 데드락(Deadlock)을 방지하기 위해 즉시 치명적 오류(Fatal Error)를 발생시키고 실행을 중단한다.

1.2 위상 정렬(Topological Sorting) 알고리즘 적용

성공적으로 DAG 모델이 구성되면, Colcon 스케줄러는 위상 정렬(Topological Sorting) 알고리즘을 적용하여 노드들의 선형적 실행 순서를 도출한다. 위상 정렬은 DAG의 모든 간선 $U \rightarrow V$ 에 대해 노드 $U$ 가 노드 $V$ 보다 순서상 반드시 먼저 위치하도록 정렬하는 알고리즘이다.

진입 차수(In-degree) 평가: 컴파일러는 그래프 내 모든 노드의 진입 차수(자신을 향하는 간선의 수)를 계산한다. 진입 차수가 0인 노드들은 어떠한 선행 의존성도 가지지 않으므로, 가장 먼저 실행 가능한(Ready) 태스크 큐(Task Queue)에 배치된다.
동시성 평가 및 병렬 큐잉: 의존 관계가 독립적인 다수의 노드가 동일한 위상 레벨(Topological Level)에 존재할 경우, 스케줄러는 이 노드들을 묶어 가용한 워커 스레드(Worker Thread)의 수만큼 병렬 빌드를 지시한다.
간선 소거(Edge Elimination): 특정 태스크 큐에 할당된 패키지 빌드가 성공적으로 종료되면, DAG 모델 내에서 해당 노드 및 그 노드에서 출발하는 모든 진출 간선(Out-going Edge)을 가상으로 제거한다.
상태 전이 및 순환: 간선이 소거됨에 따라 새롭게 진입 차수가 0이 된 (즉, 모든 선행 패키지 의존성이 해결된) 자식 노드들이 다시 태스크 큐로 격상되며, 이 과정은 큐가 완전히 비워질 때까지 재귀적으로 반복된다.

1.3 DAG 스케줄링의 병목 임계 경로(Critical Path) 분석

DAG 기반 스케줄링에서 전체 워크스페이스의 빌드 완료 시점을 결정짓는 가장 중요한 요소는 임계 경로(Critical Path)이다. 이는 시작 노드부터 종료 노드까지 연결된 수많은 경로 중 수행 시간의 총합이 가장 긴 경로를 시사한다.

가용 CPU 코어가 무한히 많아 병렬성이 극대화된 상황일지라도, 시스템의 총 체류 시간(Makespan)은 결코 임계 경로 상에 놓인 노드들의 순차적 빌드 시간 총합보다 짧아질 수 없다. 예를 들어, 핵심 미들웨어 코어 패키지(예: 로우 레벨 메시지 인터페이스)의 빌드 시간이 비정상적으로 길어질 경우, 하위 그래프 분기들에 있는 수많은 의존성 노드들이 대기 상태(Starvation)에 빠지게 되어 전체 병렬 컴파일의 효율이 급감하게 된다.

따라서 현대의 고도화된 스케줄링 프로세스에서는 이러한 DAG의 위상 학적 계층 구조의 깊이(Depth)를 최소화하고 병렬 분기 지점(Branching Factor)을 넓게 설계하는 것이 다중 패키지 아키텍처 최적화의 핵심 공학적 목표로 평가받는다. Colcon은 이러한 DAG 기반 작업 파이프라인 덕분에 개발자가 수동으로 빌드 스크립트의 실행 절차를 관리해야 했던 기존의 고전적 Make 시스템의 절차적 오류를 완벽하게 추상화하고 있다.