정의
스케줄가능성 분석(schedulability analysis)은 런타임에 데드라인이 지켜질지를 실행 전에 수학적으로 판정하는 방법을 가리킨다.[1]
hard 실시간 시스템에서 시간적 정확성은 기능적 정확성과 마찬가지로 시스템이 옳게 동작하기 위한 필수 조건이므로, 배치 전에 모든 데드라인이 지켜진다는 것을 확인할 수 있어야 한다. 판정에 들어가는 입력은 세 가지다 — 각 태스크의 job이 어떤 패턴으로 도착할 수 있는가, 각 job이 실행에 얼마나 걸릴 수 있으며 태스크끼리 어떻게 얽히는가, 그리고 어떤 스케줄링 정책이 쓰이는가.[1] 첫째는 주기 태스크 모델이, 둘째는 최악 실행 시간이 공급한다.
목표는 스케줄 다이어그램을 그려 눈으로 확인하는 일을 대신하는 것이다. 주기 태스크는 끝없는 job 열을 만들어 내므로 그림으로는 유한한 구간밖에 볼 수 없고, 어느 구간을 봐야 하는지도 따로 정해 줘야 한다 — 그 자리를 임계 순간 정리가 메운다.
실행 가능과 스케줄 가능
두 낱말은 자주 섞여 쓰이지만 가리키는 명제가 다르다. 태스크 집합이 만들어 낼 수 있는 모든 job 열을 데드라인 위반 없이 스케줄하는 알고리즘이 하나라도 존재하면 그 집합은 실행 가능(feasible)하고, 지정된 알고리즘이 그 일을 해내면 그 집합은 그 알고리즘에 대해 스케줄 가능(schedulable)하다. 태스크 하나로 좁히면, 그 태스크의 최악 응답 시간이 상대 데드라인 이하일 때 스케줄 가능하고 모든 태스크가 그러할 때 집합이 스케줄 가능하다.[1]
구분이 실무에서 갖는 뜻은 이렇다. 실행 가능은 존재 명제이므로 판정에 통과하지 못한 집합이라도 다른 알고리즘에서는 살아날 수 있다. 반면 스케줄 가능은 지금 쓰는 알고리즘에 매인 명제이므로, 고정 우선순위 스케줄링에서 나온 부정 판정은 그 우선순위 배정 아래에서만 유효하다.
충분 판정과 정확 판정
판정은 세 부류로 나뉜다. 스케줄 가능하다고 말한 집합이 실제로 모두 스케줄 가능하면 그 판정은 충분(sufficient) 판정이고, 스케줄 불가능하다고 말한 집합이 실제로 모두 스케줄 불가능하면 필요(necessary) 판정이며, 둘을 겸하면 정확(exact) 판정이다.[1]
실무에서 자주 어긋나는 지점이 충분 판정의 부정 결과다. 충분 판정을 통과했다면 데드라인은 보장되지만, 통과하지 못했다는 사실은 아무것도 보장하지 않는다 — 통과하지 못한 집합 중 상당수는 여전히 스케줄 가능하다. rate monotonic의 이용률 상한 판정이 대표적이어서, 이용률이 상한 이하인 집합은 전부 스케줄 가능하지만 상한과 1 사이의 집합은 가능한 것과 불가능한 것이 섞여 있다.[2]
불통과의 뜻
충분 판정에서 떨어진 태스크 집합을 곧바로 감당 불가로 판단해 워크로드를 손대면, 실제로는 문제가 없는 설계를 되돌리는 것이 된다. 부정 결과는 정확 판정으로 넘기라는 신호일 뿐이다.
판정 절차
정확 판정이 있는데도 충분 판정을 쓰는 이유는 비용이다. 판정의 계산 복잡도와 판정력 사이에는 맞바꿈이 있어서, 정확 판정이 너무 오래 걸리는 자리에서는 충분한 결과만 주는 값싼 판정을 쓴다.[1] 고정 우선순위에서 그 맞바꿈의 양 끝에 놓이는 것이 이용률 상한 판정과 정확 판정인 응답 시간 분석이며, 둘의 복잡도가 실제로 얼마나 벌어지는지는 각 페이지에서 다룬다.
그래서 통상적인 순서는 값싼 충분 판정을 먼저 돌리고, 거기서 걸러지지 않은 집합만 정확 판정으로 넘기는 것이다.