정의
최악 실행 시간(worst-case execution time, WCET)은 유효한 입력 상태와 초기 하드웨어 상태 전부에 대해 프로그램 한 번의 실행 시간을 위에서 막는 값이며, 그 값을 실제로 내는 실행이 적어도 하나 존재한다.[1]
주기 태스크 모델은 태스크마다 실행 시간을 수 하나로 적는다. 그런데 실제 태스크는 입력 데이터와 환경의 거동에 따라 실행 시간이 흔들리므로, 그 수를 무엇으로 채울지가 따로 풀어야 할 문제가 된다.[2] 이 문제의 답이 hard 실시간 시스템의 시간 제약 검증을 떠받친다.
실행 시간이 흔들리는 이유
한 실행의 거동은 두 가지 상태에 달려 있다. 입력 변수와 소프트웨어 상태 변수로 이뤄진 입력 상태가 코드 안의 어느 경로를 탈지와 출력값을 정하고, 내부 버퍼·파이프라인·캐시·스크래치패드·레지스터 값으로 이뤄진 하드웨어 상태가 같은 경로를 도는 데 걸리는 시간을 바꾼다. 하드웨어 상태는 기능적 결과에는 영향을 주지 않고 시간에만 영향을 준다.[1]
그래서 상한을 구하는 일은 프로세서 구조가 복잡해질수록 어려워진다. 캐시와 파이프라인, 분기 예측, 그 밖의 투기적 실행 요소가 붙으면 실행 시간이 실행 이력에 의존하기 때문이다.[2] 최근 하드웨어에서는 이 편차가 커져 최악 실행 시간이 평균 실행 시간보다 몇 자릿수 클 수 있고, 그런 값을 그대로 쓴 분석은 자원 이용률을 크게 떨어뜨린다.[3]
관측 구간과 실제 구간
가능한 모든 실행의 실행 시간을 모으면 하나의 구간이 생긴다. 그 구간의 가장 짧은 끝이 최선 실행 시간(best-case execution time, BCET), 가장 긴 끝이 최악 실행 시간이다. 상태 공간이 너무 커서 모든 실행을 남김없이 돌려 보고 두 값을 정확히 알아내는 것은 대개 불가능하다.
산업에서 흔히 쓰는 방법은 가능한 실행의 부분집합, 곧 테스트 케이스들에 대해 종단 간 실행 시간을 측정하는 것이다. 이렇게 얻는 값은 최소 관측 실행 시간과 최대 관측 실행 시간이며, 전자는 최선 실행 시간을 과대평가하고 후자는 최악 실행 시간을 과소평가한다.[2]
관측 최대값의 한계
측정으로 얻은 최대값을 최악 실행 시간으로 삼으면 hard 실시간 시스템에서 보장이 성립하지 않는다. 측정은 가능한 실행의 부분집합만 훑으므로 최대 관측값은 실제 최악 실행 시간을 아래로 벗어나 있을 수 있다.[2]
상한과 타이밍 예측 가능성
실행 시간의 경계를 실제로 계산하려면 가능한 실행 전부를 고려하는 방법을 써야 한다. 그런 방법은 분석이 감당할 수 있도록 태스크를 추상화하는데, 추상화는 정보를 잃으므로 계산된 상한은 보통 실제 최악 실행 시간보다 크게 나오고 하한은 반대로 작게 나온다. 이렇게 얻은 상한이 그 방법이 줄 수 있는 최악의 경우 보장이다. 상한이 얼마나 벌어지는지는 분석 방법과 함께 하드웨어 아키텍처·소프트웨어 특성 같은 시스템 성질에 달려 있고, 이 성질들을 묶어 타이밍 예측 가능성(timing predictability)이라 부른다. 분석 방법을 평가하는 기준도 여기서 나온다 — 경계를 내놓는지 추정치를 내놓는지, 그리고 그 값이 참값에 얼마나 가까운지다.[2]
한편 하드웨어 쪽에서 예측 가능성을 말할 때는 더 좁은 뜻으로 쓴다. 같은 입력 상태와 같은 하드웨어 상태에서 출발하면 언제나 같은 시간이 걸리는 플랫폼을 time-predictable하다고 한다.[1]
확률 분포로 보는 방식
실행 시간을 수 하나로 요약하는 것이 유일한 선택지는 아니다. 확률적 타이밍 분석은 특성화의 대상을 실행 한 번에서 반복 실행되는 시나리오로 옮기고, 그 결과를 스칼라 값이 아니라 확률 분포로 내놓는다. 이 분포를 pWCET 분포라 하며, 초과 확률을 지정하면 그에 대응하는 실행 시간 추정값을 읽어 낼 수 있다.[1]
결정적 방식에서 워크로드 모델에 들어가는 값은 분포가 아니라 이 상한 하나다. 이 값이 응답 시간 분석의 입력이 되고, 실행이 이 값을 넘지 않도록 실행 중에 강제하는 장치는 AUTOSAR OS가 다룬다. 값을 어떻게 정하든 실시간 스케줄링 참조 모델 안에서 이 파라미터가 맡는 자리는 같다.