정의
응답 시간 분석(response time analysis)은 각 태스크의 최악 응답 시간을 계산해 상대 데드라인과 견주는 판정이다. 최악 응답 시간은 job이 도착한 때부터 실행을 마칠 때까지 걸릴 수 있는 가장 긴 시간이며, 태스크는 이 값이 상대 데드라인 이하일 때, 그리고 그때만 스케줄 가능하다.[1]
상대 데드라인이 주기 이하인 태스크 집합에 대해, 이 판정은 선점형 고정 우선순위 스케줄링의 정확 판정이다 — 통과하면 데드라인이 보장되고, 통과하지 못하면 실제로 지킬 수 없다.[1] Joseph와 Pandya가 1986년에, 이어서 Lehoczky가 1989년에, Audsley 등이 1993년에 각각 이 부류의 판정을 내놓았다.[2]
두 가지 관찰
계산의 출발점은 두 가지다. 첫째, 최악 응답 시간은 임계 순간에서 나오므로 그 시나리오 하나만 계산하면 된다. 둘째, 어떤 태스크의 실행을 미루는 것은 자신보다 우선순위가 높은 태스크들의 집합 뿐이다 — 우선순위가 낮은 태스크는 선점당하므로 방해가 되지 않는다.[1]
두 번째 관찰의 따름 결과로, 최고 우선순위 태스크는 가 비어 있으므로 최악 응답 시간이 자신의 최악 실행 시간과 같다. 나머지 태스크는 자기 실행 시간에, 임계 순간에서 시작하는 구간 동안 상위 태스크들이 가져가는 시간을 더한 값이 된다.
재귀식
구간 길이 안에 태스크 의 job이 몇 번 들어오는지는 로 세어진다. 이 횟수에 의 실행 시간을 곱한 것이 가 주는 간섭이고, 상위 태스크 전체에 대해 더하면 다음 식이 나온다.
구하려는 가 양변에 나타나므로 닫힌 형태로 풀리지 않는다. 대신 고정점 반복으로 푼다.[1]
초기값은 최악 응답 시간의 하한이면 되고 태스크 자신의 실행 시간 를 흔히 쓴다.[2] 수열은 단조 증가하므로 갈 곳은 둘뿐이다 — 이 되어 값이 멎으면 그 값이 최악 응답 시간이고, 그 전에 상대 데드라인을 넘어서면 그 태스크는 스케줄 불가능이다. 태스크 집합 전체의 이용률이 1 이하이면 반복은 수렴이 보장된다.
적용 범위
간섭을 세는 올림 항은 가 주기적이든 최소 도착 간격만 보장되는 sporadic 태스크이든 그대로 성립하므로, 주기 태스크와 sporadic 태스크가 섞인 집합에 같은 식을 쓸 수 있다.[3]
이 방법은 우선순위 순서를 어떤 규칙으로 정했는지 묻지 않고 가 무엇인지만 쓴다. 그래서 rate monotonic으로 배정했든 다른 규칙으로 배정했든, 임의의 고정 우선순위 순서에 대한 정확 판정이 된다.[1] 태스크가 자원을 공유해 낮은 우선순위 태스크에 막히는 경우에는 그 블로킹 시간을 항으로 더해 같은 꼴로 확장하며, 이 몫은 우선순위 역전을 어떤 프로토콜로 다루느냐가 결정한다.
값싼 이용률 상한 판정과 견주면 비용이 크다. 반복 계산의 복잡도가 유사 다항 시간이라 태스크가 많은 시스템의 온라인 수락 제어에는 맞지 않는다.[2] 스케줄가능성 분석이 값싼 판정을 먼저 돌리는 순서를 택하는 이유가 여기 있다.