정의
임계 순간(critical instant)은 어떤 태스크의 job이 가장 긴 응답 시간을 갖게 되는 시점이다.[1]
주기 태스크는 시스템이 도는 동안 끝없이 job을 만들어 내므로, 데드라인을 앞으로도 계속 지킬지 확인하려면 원리상 무한한 job을 다 봐야 한다. 임계 순간은 이 조사를 유한하게 만드는 장치다 — 최악이 벌어지는 상황이 어디인지 특정할 수 있다면, 그 한 상황만 통과시키면 나머지는 볼 필요가 없어진다.
정리
Liu와 Layland는 고정 우선순위 스케줄링에서 이 시점을 특정했다. 어떤 태스크의 임계 순간은 그 태스크가 자신보다 우선순위가 높은 모든 태스크와 동시에 요청될 때 발생한다.[1]
근거
증명의 뼈대는 상위 우선순위 태스크의 요청 시각을 옮겨 보는 것이다. 낮은 우선순위 태스크가 요청된 시각과 상위 태스크가 요청된 시각이 어긋나 있을 때, 상위 태스크의 요청을 앞으로 당기면 낮은 태스크의 완료가 빨라지는 일은 결코 없다 — 그대로이거나 더 늦어진다. 따라서 두 요청이 겹치는 지점에서 지연이 최대가 되고, 같은 논증을 모든 상위 태스크에 반복하면 정리가 나온다.[1]
직관적으로는 조사 구간에 끼어드는 상위 우선순위 job의 수로 읽는 편이 쉽다. 위상이 어긋나 있으면 낮은 태스크가 실행되는 동안 상위 태스크의 job이 하나 덜 도착할 수 있지만, 동시에 release되면 그 하나가 반드시 구간 안으로 들어온다.
판정에서의 쓰임
이 정리가 판정에 주는 것은 간단한 직접 계산이다. 모든 태스크의 요청이 각자의 임계 순간에 일어났다고 놓고 그 요청들이 데드라인 전에 완료되면, 그 우선순위 배정에서는 데드라인 위반이 일어나지 않는다.[1] 임계 순간에서 출발한 job 하나만 보면 되므로 이후 job은 조사할 필요가 없고, 스케줄가능성 분석은 무한한 시간 축 대신 유한한 구간 하나를 다루는 문제로 바뀐다.
현대의 서술은 같은 사실을 우선순위 레벨 i의 busy period로 다시 쓴다. 임계 순간은 가장 긴 우선순위 레벨 i busy period 안에 있으며, 그 busy period는 해당 태스크와 모든 상위 우선순위 태스크의 첫 job이 동시에 release되고 이후 job들이 가능한 한 빨리 release되는 도착열에 대응한다.[2]
첫 job과 최악의 경우
상대 데드라인이 주기보다 길 수 있는 임의 데드라인 태스크 집합에서는 한 job이 끝나기 전에 다음 job이 release되므로, 최악 응답 시간이 busy period 안의 첫 job이 아니라 뒤쪽 job에서 나올 수 있다. 이때는 busy period 안의 job을 모두 계산해 최댓값을 취해야 한다.[2]