정의
이용률(utilization)은 각 태스크의 실행 시간을 주기로 나눈 값을 태스크 집합 전체에 대해 더한 값이다.[1] 스케줄가능 이용률 상한은 집합의 이용률이 그 값 이하이기만 하면 스케줄가능함이 보장되는 경계를 말한다.
이용률은 프로세서 시간 가운데 태스크 실행에 쓰이는 몫이므로, 1을 넘으면 요구되는 계산량이 쓸 수 있는 프로세서 시간을 초과해 어떤 알고리즘으로도 감당할 수 없다.[2] 흥미로운 질문은 반대쪽이다 — 어디까지 채워도 데드라인이 지켜진다고 말할 수 있는가. 이 경계를 알면 스케줄가능성 분석을 덧셈 한 번과 비교 한 번으로 끝낼 수 있다.
Liu와 Layland 상한
독립적이고 선점 가능하며 데드라인이 주기와 같은 개의 주기 태스크를 rate monotonic으로 배정할 때, 이용률의 최소 상한은 다음 값이다.[2]
이 값은 태스크 수가 늘수록 작아진다. 태스크가 둘이면 약 0.83, 셋이면 약 0.78이고, 태스크 수가 커지면 다음 값으로 수렴한다.
즉 이용률이 약 69퍼센트 이하인 집합은 태스크가 몇 개든 고정 우선순위 스케줄링으로 데드라인을 지킬 수 있다.[1] 나머지 30퍼센트가 늘 버려진다는 뜻은 아니다 — 이것은 최악의 태스크 집합에 맞춘 보장선이다.
충분조건의 한계
이 판정은 충분조건이므로 상한을 넘겼다는 사실이 스케줄 불가를 뜻하지 않는다. 약 0.69와 1 사이 구간에는 스케줄 가능한 집합과 불가능한 집합이 섞여 있고, 모든 주기 쌍이 서로 배수 관계인 조화 집합에서는 이용률 1에서도 스케줄이 성립한다.[3] 정확한 답이 필요하면 응답 시간 분석으로 넘어가야 한다.
조화 관계의 조건
모든 주기가 가장 짧은 주기의 배수라는 것만으로는 상한이 1이 되지 않는다. 주기가 4, 8, 12이고 실행 시간이 모두 2인 집합은 이용률을 12분의 11 위로 올릴 수 없다. 상한이 1이 되려면 주기의 모든 쌍이 서로 배수 관계여야 한다.[3]
판정의 쓸모
값이 하나뿐인 판정에는 값싼 것 말고도 쓸모가 있다. 계산이 다항 시간에 끝나므로 런타임에 새 태스크를 받아들일지 그 자리에서 결정하는 온라인 수락 제어에 쓸 수 있다.[3] 이 상한이 고정 우선순위 부류에서 치르는 대가라는 점은 Earliest Deadline First의 이용률 상한과 견주면 분명해진다.
개선된 충분 판정
같은 복잡도로 더 많은 집합을 통과시키는 충분 판정도 있다. Bini 등이 제안한 hyperbolic bound는 태스크별 이용률에 1을 더해 모두 곱한 값이 2 이하인지를 묻는다. 계산 비용은 Liu와 Layland 상한과 같으면서 통과시키는 집합의 범위가 넓다.[3]
통계값과 보장의 구분
무작위로 생성한 파라미터의 태스크 집합에서 rate monotonic이 이용률 약 88퍼센트까지 스케줄해 낸다는 통계 결과가 알려져 있다. 이것은 평균적 거동을 보여 줄 뿐 절대적 경계가 아니므로 보장 판정의 근거로 쓸 수 없다.[3]