Worst-Case Execution Time (WCET) Analysis

1. Overview

최악 실행 시간 분석(Worst-Case Execution Time, WCET)은 "내 코드는 평균적으로 1밀리초면 끝나"라는 소프트웨어 프로그래머의 안일한 변명을 박살 내고, 우주방사선이 내리쬐고 캐시 메모리가 폭발하는 극한의 악조건 속에서도 **"절대로 X 마이크로초를 넘기지 않는다"**는 수학적 보증 수표(Guarantee)를 발행하는 하드 리얼타임(Hard Real-time)의 심판대입니다.

학습자는 C 언어 소스 코드를 넘어, 컴파일러가 뱉어낸 어셈블리 명령어 한 줄 한 줄이 CPU 파이프라인에서 며칠(Cycle)을 잡아먹는지 뜯어보는 **정적 타이밍 분석(Static Timing Analysis)**을 해부합니다. 나아가 코드의 무한 루프나 재귀 함수(Recursion)를 금지하는 안전 코딩 헌법(MISRA C)을 체득하고, 캐시 미스(Cache Miss)나 분기 예측 실패(Branch Misprediction)와 같은 아키텍처 레벨의 지터(Jitter) 덩어리들을 모조리 최악의 패널티로 더해버리는 엄혹한 결정성(Determinism) 튜닝을 통달하여, 사람의 목숨이 달린 항공기(DO-178C)와 자동차(ISO 26262) 제어 시스템 아키텍트 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 타이밍 역학 (Timing Physics): 최악 실행 시간(WCET), 평균 실행 시간(ACET), 최고 실행 시간(BCET), 마진(Margin)과 안전 데드라인(Deadline).
• 정적 분석 한계 (Static Analysis): 제어 흐름 그래프(CFG, Control Flow Graph), 루프 바운드(Loop Bounds), 비실행 경로(Infeasible Path).
• 아키텍처 지터 패널티 (Architectural Jitter): L1/L2 캐시 미스 패널티, 파이프라인 플러시(Branch Flush), 비순차 실행(OoO) 변수.
• 안전 헌법 및 제약 (Safety Standards): 동적 메모리 할당(malloc) 금지, 재귀 호출(Recursion) 금지, MISRA C/DO-178C 스펙 한계.

Out-of-Scope

• 프로파일러를 통한 단순 성능 최적화(Profiling): 리눅스의 perf나 Valgrind를 돌려서 평균 성능(Throughput)을 높이는 최적화 $\rightarrow$ 03-01-04. Profiling & Performance Tuning 영역.
• 스케줄러의 타임 슬라이싱 연산: 여러 태스크의 WCET가 겹칠 때 RTOS가 언제 문맥(Context)을 뺄지 결정하는 스케줄링 이론 $\rightarrow$ 02-06-01. RTOS Kernel Scheduling Mechanics 영역.

Boundaries

• WCET vs. Profiling (03-01-04): 일반 앱 프로파일링(03-01-04)이 "테스트 코드를 1만 번 돌려보고 평균적으로 5ms가 나오니 굿(Good)!"이라고 외치는 '실험 통계학'이라면, WCET는 "단 1번이라도 If문이 최악의 분기로 꼬이고 캐시가 전부 다 증발했을 때 50ms가 걸리면, 이 시스템 스펙은 5ms가 아니라 무조건 50ms다"라고 못 박는 '보수적 물리학'입니다.

3. Counterexample

• 테스트 케이스 맹신에 의한 붕괴 (Measurement-based Blindness): 개발자가 연구실에서 모터 제어 코드를 100만 번 실행(측정 기반 분석)해보니 최대 2ms가 나와서 데드라인을 3ms로 잡고 칩을 양산해버리는 미친 짓. 현장에 투입된 어느 날, 하필 네트워크 인터럽트 수십 개가 동시에 터져 캐시가 모조리 비워지고(Cache Eviction) 그 상태에서 if-else 역방향 최악 경로를 탔을 때 코드가 10ms 동안 블로킹되어 모터가 폭주(데드라인 오버)합니다. 측정은 절대 '최악(Worst)'을 보장하지 않으며, 오직 '운이 나쁘지 않았던 기록'일 뿐입니다.
• 재귀 함수와 가변 루프의 수렁 (Unbounded Loops): 배열의 사이즈(N)가 센서에서 날아오는 동적 데이터에 따라 변하는데, 펌웨어 안에서 for(int i=0; i<N; i++) 이라며 가변 루프를 돌리는 폭탄 코드. N이 해킹 펄스에 의해 1억(100M)으로 들어오는 순간 루프는 WCET 한계선을 뚫어버리고 태스크 워치독(Watchdog)이 터져 시스템이 사살당합니다. 하드 리얼타임에서는 루프의 상한(Max Bound)이 상수로 픽스(Hardcoded)되어있지 않은 코드는 아예 컴파일(정적 분석) 단계에서 거부당합니다.

4. Prerequisites

• 인터럽트 지터(Jitter)의 개념 (Basic): 캐시나 파이프라인 때문에 실행 시간이 널뛰는 원인(Jitter)을 이해해야 최악의 시간을 상정할 수 있습니다. (02-05-03 Interrupt Latency & Jitter)
• 컴퓨터 구조와 명령어 사이클 (Recommended): C 코드가 어셈블리로 번역되고 각 명령어(ADD, LDR, DIV)가 소비하는 클럭(Cycle)을 알아야 정적 계산이 가능합니다. (02-01-03 Instruction Cycle Logic)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 보수적 물리 헌법, 평균(ACET)과 최악(WCET)의 괴리

• Why to Learn: 스마트폰 앱에서 프레임이 1개 빠지면 "렉 걸리네"로 끝나지만, 인공위성 자세 제어에서 데드라인을 1ms 놓치면 1000억 원짜리 고철이 우주 미아가 되는 비대칭적 위험성을 깨우치기 위함입니다.
• What to Learn:
  • Concepts: WCET(Worst-Case Execution Time), ACET(Average), BCET(Best), 데드라인 마진(Deadline Margin).
  • Skills: 측정 기반(Measurement-based)의 한계, 정적 예측(Static Prediction)의 안전(Safe) 오버에스티메이트(Over-estimate).
  • Tools: 타이밍 궤적 히스토그램.
  • Trade-offs: 완벽한 WCET 보장을 위해 정적 분석으로 "캐시 다 미스 난다"고 최악으로 쳐버리면(Over-estimation), 실제로는 1ms 만에 끝날 코드를 10ms로 잡게 되어 OS 스케줄러가 너무 남는 장사를 하느라 값비싼 CPU 자원을 90% 놀리는(Utilization 폭락) 극악의 가성비.
• How to Learn:
  • 1단계: 100만 번 실행한 테스트의 최고 기록이 3ms(ACET)라고 해서, 100만 1번째에 내부 분기(if-else)가 최악의 역방향으로 꼬였을 때 15ms(WCET)가 튀어나오지 않는다는 수학적 보장은 절대 없다는 통계학의 배신을 해부합니다.
  • 2단계: 안전한 WCET 추정치는 실제 터질 수 있는 진정한 최악 시간(True WCET)보다 무조건 크거나 같아야 하며, 이를 맞추기 위해 버려지는 시간(Pessimism)을 어떻게든 깎아내는 수학적 튜닝을 뜯어봅니다.
• Implement: 파이썬 random.gauss()로 평상시 ACET(3ms)를 내뱉다가 10만 분의 1 확률로 if evil_path:를 타서 50ms 딜레이(지터)를 쏘는 벤치마크 루프를 만듭니다. '측정(Sampling) 1000번'만 해보고 최대 4ms가 나왔다며 데드라인을 5ms로 설정한 스케줄러가, 밤새 돌리다 데드락 참사(Deadlock)를 뿜어내는 가상 패닉 모사.

Recommended

Core Topic 02: 지옥의 궤적 추적, 정적 제어 흐름 분석 (CFG & Static Analysis)

• Why to Learn: 프로그램에 입력값(Input)을 넣어보지 않고도, 컴파일러 소스 단에서 수학적 그래프 기하학을 그려 가장 오랫동안 CPU를 괴롭히는 최장 실행 경로(Longest Path)를 100%의 신뢰도로 찢어내기 위해서입니다.
• What to Learn:
  • Concepts: 제어 흐름 그래프(CFG, Control Flow Graph), 최장 경로 찾기 알고리즘(Longest Path Problem).
  • Skills: 기본 블록(Basic Block) 분해, 인피저블 경로(Infeasible Path) 소거 연산.
  • Tools: AbsInt aiT 정적 타이밍 분석기 구조.
  • Trade-offs: CFG 트리를 끝까지 추적하면 완벽한 WCET가 나오지만, 분기문(if)이 20개만 겹쳐도 경우의 수가 $2^{20}$(100만 개)으로 지수 폭발(State Explosion)하여 툴 연산 시간이 며칠이 걸리는 계산 복잡도의 지옥.
• How to Learn:
  • 1단계: C 코드를 어셈블리로 까발려 점프(Branch)가 없는 명령어 덩어리들을 '기본 블록(Basic Block)' 노드로 뭉치고, If-Else 점프 선으로 연결된 거대한 다이렉트 그래프(DAG) 배관망을 펴는 기하학을 해부합니다.
  • 2단계: if (a > 0)을 거친 후 밑에서 다시 if (a < 0)을 만났을 때, 두 블록을 모두 타는 경로는 물리적으로 불가능하므로(Infeasible Path) 쳐내고, 남은 유효 궤적 중 명령어 사이클 누적 합이 가장 거대한 단 하나의 최악 궤적(Worst Path)을 산출하는 과정을 뜯어봅니다.
• Implement: 3개의 If-Else 깊이를 가진 파이썬 텍스트 파서를 작성합니다. 각 분기의 블록 비용(Cost = 10, 20 등)을 파싱하여 트리(CFG)를 구성하고, 8개의 가능한 종단 경로(Leaf) 중 가장 Cost 합산액(Maximum Path)이 높은 궤적을 텍스트 덤프로 찾아내어 WCET 바운드를 선언하는 역학 증명.

Practical

Core Topic 03: 하드웨어 억까 패널티 산정 (Architecture Penalty & Cache Jitter)

• Why to Learn: 코드 논리만으론 100클럭이면 끝날 작업이, 반도체 CPU의 파이프라인 예측 실패와 램(RAM) 병목 때문에 1000클럭으로 널뛰어버리는 물리 계층의 숨겨진 패널티를 정산하기 위함입니다.
• What to Learn:
  • Concepts: 분기 예측 패널티(Branch Prediction Penalty), 캐시 미스 오버헤드(Cache Miss Penalty).
  • Skills: 다중 파이프라인 플러시 마진 합산, 분할(Fractional) 분석 모델링.
  • Tools: 하드웨어 사이클 카운터(DWT).
  • Trade-offs: 캐시 분석기(Cache Analyzer)를 돌려 "여기는 루프라 2번째부턴 무조건 히트(Hit)다"라고 똑똑하게 최적화(Pessimism 감소)를 때려버리면 WCET 마진이 예쁘게 줄어들지만, 중간에 찰나의 인터럽트가 난입해 캐시를 엎어버리는 순간 예측 모델이 모조리 붕괴하는 방어선 파탄 리스크.
• How to Learn:
  • 1단계: CFG에서 If 분기를 만났을 때, 분기 예측기가 틀려서 기존 파이프라인(명령어 큐) 5개를 학살(Flush)하고 메모리에서 처음부터 다시 읽어오는 수십 클럭의 물리적 오버헤드를 WCET 계산 덩어리에 강제로 쑤셔 넣는 과정을 해부합니다.
  • 2단계: 최악의 최악을 겹쳐서, "모든 메모리 로드(LDR) 명령은 캐시 미스(Cache Miss)가 나서 램에서 가져온다(+50클럭)"라고 보수적(Pessimistic)으로 산정해 버리는 엄혹한 보증 계산 철학을 뜯어봅니다.
• Implement: 100개의 어셈블리 명령어가 들어있는 리스트에서, LDR(메모리 읽기) 명령을 만날 때마다 베스트(Hit=1 클럭)와 워스트(Miss=50 클럭)를 구분해 Total_Cycle을 누적. 분기문 BEQ를 만나면 파이프라인 플러시(Flush=+10 클럭) 패널티를 때려, 동일한 코드라도 Best_Case(100 클럭) 대비 Worst_Case(1500 클럭)로 15배 뻥튀기되는 아키텍처 패널티 덤프.

Advanced

Core Topic 04: 통제할 수 없는 우주는 찢어버려라, 안전 코딩 헌법 (Safety Standards)

• Why to Learn: 아무리 훌륭한 WCET 분석 툴을 돌려도 "이 배열 사이즈가 무한대로 커질 수 있어서 계산을 못 하겠는데요?"라고 툴이 뻗어버리면 말짱 황이므로, 예측할 수 없는 다이내믹 코딩 자체를 금지하는 항공기 급 코딩 족쇄를 스스로 채우기 위해서입니다.
• What to Learn:
  • Concepts: DO-178C (항공기), ISO 26262 (자동차 ASIL), MISRA C 표준 제약.
  • Skills: 상한선 픽스 루프(Bounded Loop), 재귀 함수(Recursion) 및 동적 할당(malloc) 원천 금지.
  • Tools: SonarQube, 린터(Linter) AST 검사.
  • Trade-offs: while(센서 == 1)처럼 직관적인 루프 대기를 절대 쓰지 못하고 무조건 for(i=0; i<MAX_TIMEOUT; i++) 타임아웃 코드를 덕지덕지 박아야 하므로 코드가 지저분해지고 개발 피로도가 미친 듯이 올라가지만, WCET의 수학적 상한선(Upper Bound) 뚫림을 원천 봉쇄하는 무결점 타협.
• How to Learn:
  • 1단계: C 언어에서 자랑하는 재귀 함수(Recursion)를 썼을 때, 스택 깊이(Depth)가 런타임에 얼마나 파고들지 정적 컴파일러가 절대로 계산할 수 없어(할팅 프라블럼), 에어백 코드에서는 아예 재귀(Recursion) 키워드 자체를 컴파일 에러로 때려버리는 폭력을 해부합니다.
  • 2단계: 외부 통신 패킷을 기다리기 위해 while(Rx_Flag == 0)을 치는 순간 WCET 분석기(Analyzer)가 "무한 루프 폭탄!"이라며 분석을 거부해 버립니다. 이를 타파하기 위해 #pragma loop_bound_max(1000) 어노테이션이나 억지 Timeout 브레이크를 걸어 툴에게 상한선을 맹세하는 코딩 헌법을 뜯어봅니다.
• Implement: 파이썬 AST(추상 구문 트리) 파서 스크립트를 작성하여, 타겟 파이썬 코드를 텍스트로 읽어 들임. while True: 블록이나 def recursive_func(): (함수 내 자가 호출) 패턴이 텍스트로 파싱되는 순간 [WCET_VIOLATION] Unbounded Structure Detected! 경고 덤프를 뿜어내며 린터(Linter) 빌드를 강제 실패 처리하는 미스라(MISRA) 룰 규제 시뮬레이션.

7. Terminology

8. References

Primary

• [P3] CyBOK v1.1 - Hardware Security / Real-time and Safety-critical Support — Timing predictability standards.
• [P2] SWEBOK v4.0 - Computing Foundations / Real-Time Systems — Performance analysis.

Secondary

• [Worst-case Execution Time Analysis for Real-time Systems] Wilhelm et al. — The fundamental survey/paper.
• [Real-Time Systems Design and Analysis] Laplante — Chapters on predictable timing.

Industry

• [ISO 26262: Road vehicles — Functional safety (Timing requirements)] — Automotive WCET practice.
• [DO-178C: Software Considerations in Airborne Systems (Verification)] — Aerospace execution time standards.

9. Final Checklist

Primary

• 캐시(Cache)와 파이프라인(Pipeline)이 있는 CPU에서 왜 '명령어 개수'만으로는 실행 시간을 물리적으로 산출할 수 없는지 이유를 설명 가능한가? (P3)
• WCET 분석 시 '재귀 함수(Recursion)' 사용을 임베디드 표준에서 왜 금기시하는지 분석 가능성 측면에서 입증할 수 있는 가? (P2)

Secondary

• '정적 분석'으로 산출된 WCET 수치가 실제 측정된 최댓값보다 작게 나왔을 때, 이 분석 결과가 왜 시스템 보안/안전에 무효한 것인지 소통 가능한가?
• 인터럽트가 중첩되는 시스템에서 순수 태스크의 WCET와 '인터럽트 지연'이 결합된 총 마감 시간을 수리적으로 도출할 수 있는 가?

Industry

• 항공기 비행 제어 소프트웨어 검증 시, 최신 CPU의 '비결정론적 기능(예: SMT)'을 비활성화했을 때 WCET 분석이 비약적으로 단순해지는 물리적 근거를 제안할 수 있는 가? (SFIA)
• 코드 변경 후 WCET가 마감 시간(Deadline)에 근접했을 때, 하드웨어 타이머의 해상도(Resolution)를 고려한 안전 마진(Safety Margin)을 재설정할 수 있는 가?