Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency

1. 문제 정의 (Problem Statement)

• 배경: 자율주행 및 제어 시스템과 같은 실시간 시스템에서는 개별 태스크의 실행뿐만 아니라 데이터 전파 (Cause-Effect, CE 체인) 도 엄격한 타이밍 제약을 만족해야 합니다. 이를 분석하는 주요 지표는 **최대 반응 시간 (MRT, Maximum Reaction Time)**과 **최대 데이터 나이 (MDA, Maximum Data Age)**입니다.
• 핵심 문제: 타이밍 이상 현상 (Timing Anomalies, TAs)
  • TAs 는 특정 태스크의 실행 시간이 예상보다 짧아졌음에도 불구하고, 전체 시스템의 종단 간 지연 시간 (End-to-End Latency) 이 오히려 증가하는 비직관적인 현상입니다.
  • 원인: 작업 (Job) 의 실행 시간 변화가 데이터 의존성 경로를 변경시켜, 최악의 경우 (WCET) 보다 더 긴 경로를 형성하거나, 읽기/쓰기 시점을 불규칙하게 만들어 지연을 유발합니다.
• 기존 연구의 한계:
  1. WCET 강제 실행 (Method M21): 모든 태스크를 최악의 실행 시간 (WCET) 으로 강제 실행하여 TAs 를 제거합니다. 이는 분석을 단순화하지만, 실제 실행 시간이 WCET 보다 짧은 경우가 많아 평균 지연 시간 (Average Latency) 이 비효율적으로 증가합니다.
  2. 안전한 분석 방법 (Method M23): 스케줄링을 변경하지 않고 TAs 를 고려한 안전한 상한값을 분석합니다. 하지만 TAs 가 시스템에 존재하기 때문에 지연 시간의 상한값이 여전히 매우 높게 책정되며, 정확한 상한값을 구하기 어렵습니다.

2. 제안 방법론 (Methodology)

저자들은 TAs 의 두 가지 근본 원인을 규명하고, 이를 해결하기 위해 **결정론적 데이터 흐름 (Deterministic Data Flow, DDF)**을 기반으로 한 새로운 처리 기법을 제안했습니다. 이 기법은 평균 지연 시간의 손실을 거의 없이 TAs 를 완전히 제거합니다.

2.1 TAs 의 두 가지 원인 규명

1. 구조적 변화: 비 WCET 실행 시, WCET 실행 시에는 존재하지 않던 새로운 '즉시 전방 작업 체인 (Immediate Forward Chain)'이 생성될 수 있음.
2. 시점 불확실성: 동일한 작업 체인이라도, 읽기/쓰기 이벤트 시점이 실행 시간에 따라 변하여 WCET 시나리오보다 더 긴 지연을 유발할 수 있음.

2.2 결정론적 데이터 흐름 (DDF) 구현

DDF 는 오프라인에서 WCET 시뮬레이션을 통해 작업 간의 통신 관계를 고정하고, 온라인 실행 시 이를 유지하는 두 가지 목표를 가집니다.

1. RAW (Read-After-Write) 보장:

   • 목표: 소비자 작업 (Consumer) 이 생산자 작업 (Producer) 의 데이터 쓰기가 완료된 후에만 읽기를 시작하도록 강제.
   • 구현: 태스크 속성 (Release time, Priority) 을 수정하여 TT-FP(시간 기반 고정 우선순위) 스케줄링 하에서도 의존성을 유지합니다.
     • 읽기 작업의 릴리스 시간을 쓰기 작업의 완료 시간 이후로 조정.
     • 읽기 작업에 쓰기 작업보다 낮은 우선순위를 부여하여 선점 (Preemption) 을 방지.
   • 효과: 작업 간의 실행 의존성을 고정하여 새로운 작업 체인이 생성되는 것을 방지 (원인 1 해결).

2. RFI (Read-From-Intended) 보장:

   • 목표: 각 소비자 작업이 의도한 생산자 작업 (DDF 에서 정의된 특정 작업) 의 데이터만 읽도록 보장.
   • 구현: 멀티 버퍼 (Multi-buffer) 통신 메커니즘 도입.
     • 동일한 태스크의 여러 작업이 생성한 데이터를 버퍼에 저장.
     • 소비자 작업은 DDF 에서 정의된 '의도된' 생산자의 버퍼에서 데이터를 읽음.
   • 효과: 중간에 다른 작업이 데이터를 덮어쓰더라도 의도된 데이터를 읽도록 하여, 읽기/쓰기 시점의 상한/하한을 보장 (원인 2 해결).

2.3 오프라인/온라인 프로세스

• 오프라인: WCET 으로 시뮬레이션을 수행하여 DDF(작업 간 통신 관계) 를 추출하고, 태스크 속성을 수정하며 버퍼 크기를 계산.
• 온라인: 수정된 속성과 멀티 버퍼를 적용하여 실제 실행. 이때 TAs 가 제거되므로, **WCET 실행 시나리오로 얻은 지연 시간 상한값이 모든 가능한 실행에 대한 정확한 상한값 (Precise Upper Bound)**이 됩니다.

3. 주요 기여 (Key Contributions)

1. TAs 의 근본 원인 규명: 종단 간 지연 시간에서의 TAs 가 '작업 의존성 구조의 변화'와 '읽기/쓰기 시점의 변동'에서 기인함을 식별.
2. 최초의 TAs 제거 처리 기법: 고정 우선순위 (FP) 스케줄링 하에서 CE 체인의 종단 간 지연 시간 TAs 를 제거하면서, 평균 지연 시간 손실을 무시할 수준으로 줄인 첫 번째 방법론 제시.
3. 일반화된 모델링: 레지스터 통신뿐만 아니라 멀티 버퍼 통신도 지원하는 보다 일반적인 '즉시 전방 작업 체인 (Immediate Forward Chain)' 정의.
4. 정형 증명: DDF 하에서 작업 흐름 관계의 불변성과 읽기/쓰기 시점의 안전 경계를 통해 TAs 가 발생하지 않음을 수학적으로 증명 (Theorem 5.4).
5. 실험적 검증: 기존 최첨단 (SOTA) 방법론 대비 성능 개선 효과 입증.

4. 실험 결과 (Experimental Results)

자동차 벤치마크 (Automotive Benchmarks) 와 합성 작업 세트를 사용하여 다양한 작업 부하 (Utilization) 와 BCET/WCET 비율 ($\alpha$) 에서 실험을 수행했습니다.

• 최대 반응 시간 (MRT) 감소:
  • 기존 TAs 를 고려한 안전한 분석 방법 (M23) 대비 평균 9%~12% 감소 (최대 61% 감소).
  • TAs 를 제거하기 위해 WCET 을 강제하는 방법 (M21) 과 동일한 정확한 상한값을 제공하지만, 평균 성능은 훨씬 우수함.
• 평균 반응 시간 (ART) 개선:
  • WCET 강제 실행 (M21) 대비 평균 11%~41% 감소.
  • 기존 분석 방법 (M23) 대비 평균 지연은 2%~5% 정도만 증가하여, TAs 제거와 평균 성능 간의 균형을 성공적으로 달성.
• 지터 (Jitter) 감소:
  • 지연 시간 변동성 (Jitter) 이 53%~68% 감소. 작업 의존성 구조가 고정되어 타이밍 불확실성이 크게 줄어듦.
• 메모리 오버헤드:
  • 멀티 버퍼 통신으로 인한 메모리 사용량 증가는 미미함 (평균 작업 수 대비 약 0.86~0.93 개 정도의 데이터 항목 증가).
• 스케줄링 가능성 (Schedulability):
  • 원래 스케줄링에서 실행 가능한 작업 세트는 본 기법 적용 후에도 여전히 실행 가능 (Schedulable) 함.

5. 의의 및 결론 (Significance)

이 논문은 실시간 시스템의 종단 간 지연 시간 분석에서 발생하는 **TAs 의 딜레마 (정확한 상한값 vs 평균 성능 저하)**를 해결했습니다.

• 정확한 상한값 보장: TAs 가 제거되었기 때문에, 복잡한 시나리오 분석 없이도 WCET 실행 시나리오만으로 정확한 (Precise) 최대 지연 시간 상한값을 얻을 수 있습니다. 이는 시스템의 안전성 검증 (Safety Certification) 에 매우 중요합니다.
• 실용성: 평균 지연 시간을 크게 희생하지 않으면서 TAs 를 제거하므로, 자율주행 등 지연 민감도가 높은 실시간 시스템에 적용하기 매우 유리합니다.
• 기존 방법론의 한계 극복: 기존 방법론이 가진 '과도한 보수성 (높은 지연 상한값)' 또는 '평균 성능 저하'라는 두 가지 극단을 모두 피할 수 있는 새로운 패러다임을 제시했습니다.

결론적으로, 이 연구는 **결정론적 데이터 흐름 (DDF)**을 통해 실시간 시스템의 타이밍 예측 가능성을 획기적으로 높이고, 시스템 설계 및 검증 비용을 절감하는 중요한 기여를 했습니다.