Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment 리뷰
배경
논문이 발표된 1970년대 전후, 산업 공정에 제어/감시 목적으로 컴퓨터가 널리 활용되기 시작했다. 이러한 적용 방법은 이전과는 비교해서 새로운 것이었는데, 초기의 컴퓨터는 주로 계산을 수행하기 위해 배치 처리에 사용되어, 시간 제약이 엄격한 요구사항이 발생하는 경우가 거의 없었기 때문이다. 하지만 산업 공정에서는 실시간으로 공정을 제어하고 감시해야 하므로, 컴퓨터에게 시간 측면에서 높은 신뢰성이 요구되었다.
실시간 시스템은 크게 두 가지 측면에서 접근되었다. 시스템 응답이 통계적으로 일정한 비율 내로만 보장되면 충분한 “soft-real-time” 시스템과 모든 작업이 정해진 시간 내에 완료되어야 하는 “hard-real-time” 시스템이다. 당시에는 멀티프로그래밍 환경에서 시분할 시스템의 처리 능력에 대한 통계적인 분석을 다루는 연구는 많았지만, “hard-real-time” 시스템에서의 스케줄링 알고리즘에 관한 연구는 소수에 불과하였다.
가정
컴퓨팅 환경에 대해서 이 연구에서는 다섯 가지의 가정을 설정하였다.
(A1) 엄격한 마감 기한(hard deadline)이 존재하는 모든 작업은 주기적(periodic)으로 발생하고, 일정한 간격을 갖는다.
(A2) 모든 작업은 다음 작업 요청이 발생하기 전에 완료되어야 한다. (마감 기한은 “실행 가능성” 제약 조건으로 설정한다.)
(A3) 모든 작업은 독립적이다. (다른 작업의 시작, 완료에 의존하지 않는다.)
(A4) 각 작업의 실행 시간(run-time)은 일정하고, 시간에 따라 변하지 않는다. (실행 시간은 프로세서가 중단 없이 작업을 처리하는 데 걸리는 시간이다.)
(A5) 시스템에서 발생하는 비주기적인 작업(aperiodic task)은 초기화, 장애 복구 등 특수한 경우로 한정한다. 이 작업들은 실행되는 동안 주기적인 작업을 대체하지만, 이 작업 자체로는 엄격한 마감 기한을 갖지 않는다.
이러한 가정 하에서 각 작업 $\tau_i$ 는 요청 주기 $T_i$ 와 실행 시간 $C_i$ 만으로 설명될 수 있다. $m$ 개의 주기적인 작업 $\tau_1, \tau_2, …, \tau_m$ 이 존재할 때, 각 작업의 요청 주기 $T_1, T_2, …, T_m$ 과 실행 시간 $C_1, C_2, …, C_m$ 이 존재한다. 또한 작업의 요청률(request rate)은 요청 주기의 역수($1/T_i$)로 정의할 수 있다.
또한 스케줄링은 우선순위 기반(priority-driven), 선점형으로 한정한다. 이 때 우선순위 배정 방식에 따라 스케줄링 알고리즘은 정적 방식, 동적 방식, 혼합 방식으로 구분해 정의할 수 있다. 정적 방식은 우선순위가 작업이 생성될 때 결정되어 이후에 변하지 않고, 동적 방식은 매번 작업이 요청될 때마다 우선순위가 변할 수 있으며, 혼합 방식은 일부 작업을 정적 방식으로 고정하고 나머지를 동적으로 처리한다.
고정 우선순위 스케줄링(Rate-Monotonic Scheduling)
정리 1
어떤 작업 $\tau_i$ 의 마감 기한은 동일한 작업에 대한 다음 요청 시간까지로 정의되었다. 어떤 알고리즘에 따라 스케줄링되는 작업 집합에 대해서, 시간 $t$ 가 미완료된 작업의 마감 기한일 경우, “시간 $t$ 에 오버플로(overflow)가 발생한다.”고 서술할 수 있다. 주어진 작업 집합에 대해 어떠한 오버플로도 발생하지 않게 스케줄링할 수 있다면, 이 작업 집합을 스케줄링하는 알고리즘은 실행 가능(feasible)하다.
특정 작업을 요청한 시점으로부터 이 작업이 완료되어 응답하는 시점까지의 시간 간격을 응답 시간(response time)이라고 정의한다면, 어떤 작업에 대한 임계 순간(critical instant)은 이 작업의 응답 시간이 최대가 되는 순간으로 정의한다. 작업에 대한 임계 시간대(critical time zone)은 임계 순간부터 이 작업의 응답이 완료될 때까지의 시간 간격이다.
이때, 아래와 같이 정리할 수 있다.
정리 1
어떤 작업에 대한 임계 순간은 해당 작업이 더 높은 우선순위의 작업들과 동시에 요청될 때 발생한다.
우선순위가 정해진 작업 집합 $\tau_1, \tau_2, …, \tau_m$ 에 대해 $\tau_m$ 을 우선순위가 가장 낮은 작업일 때, 시간 $t_1$ 에 $\tau_m$ 작업 요청이 발생한다고 가정한다. $\tau_m$ 작업은 $t_1 + T_m$ 에 다시 요청되므로 $t_1 + T_m$ 이전에 완료되어야 한다. $\tau_m$ 작업의 임계 순간은 $t_1$ 이다.
$[t_1, t_1 + T_m]$ 사이에서 다른 어떤 작업 $\tau_i (i < m)$ 요청이 $t_2$ 에 발생(즉, $t_1 < t_2 < t_1 + T_m$)하여 $t_2, t_2 + T_i, t_2 + 2T_i, …$ 에 반복해서 발생한다면, $\tau_m$ 이 $t_2$ 이전에 완료되지 않으면 $\tau_i$ 작업이 $\tau_m$ 작업보다 우선순위가 높으므로, $\tau_m$ 작업은 어느 정도 지연될 것이다.
$t_2$ 가 $t_1$ 으로부터 충분히 시간이 경과한 후라면, $\tau_m$ 작업이 $\tau_i$ 작업보다 먼저 완료될 수 있지만, $t_2$가 $t_1$ 에 충분히 가깝다면 $\tau_m$ 작업은 계속해서 지연된다. $t_1 = t_2$ 인 상황에서는 항상 $\tau_m$ 의 최악의 지연이 발생한다.
이 정리를 이용하면 계산으로 스케줄링 알고리즘을 사용할 수 있는지를 판단할 수 있다. 모든 작업이 임계 순간에서의 요청을 마감 기한 내에 완료될 수 있다면, 이 작업 집합은 스케줄링 알고리즘을 사용하여 실행 가능하다.
정리 2
두 개의 작업 $\tau_1$ 과 $\tau_2$ 에 대해 주기가 각각 $T_1$, $T_2$ $(T_1 < T_2)$ 이고, $\tau_1$ 이 더 높은 우선순위를 갖는다면, 정리 1에 의해 다음의 관계가 성립한다.
\[\lfloor \frac{T_2}{T_1} \rfloor C_1 + C_2 \leq T_2\]$\tau_2$ 가 더 높은 우선순위를 갖는다면, 다음의 관계가 성립한다.
\[C_1 + C_2 \leq T_1\]$k = \lfloor T_2/T_1 \rfloor$ 라 하자. $T_1 < T_2$ 이므로 $k \ge 1$ 이다. $\tau_2$ 가 더 높은 우선순위를 가질 때 작업 집합이 실행 가능하다면 $C_1 + C_2 \leq T_1$ 이므로
\[k(C_1 + C_2) \leq k T_1 \leq T_2\]이다. 또한 $k \geq 1$ 이므로
\[kC_1 + C_2 \leq kC_1 + kC_2 = k(C_1 + C_2)\]이다. 두 부등식을 결합하면
\[\lfloor T_2/T_1 \rfloor C_1 + C_2 = kC_1 + C_2 \leq T_2\]가 성립한다. 즉, $\tau_2$ 를 높은 우선순위로 두었을 때 실행 가능하다면, $\tau_1$ 을 더 높은 우선순위로 두어도 항상 실행 가능하다.
정리하여 $T_1 \lt T_2$ 이고 $\tau_2$ 의 우선순위가 $\tau_1$ 보다 높을 때 작업이 실행 가능하다면 $\tau_1$ 의 우선순위가 더 높을 때도 작업은 실행 가능하다. 하지만 그 역은 성립하지 않는다.
\[\begin{aligned} \text{able}(P(\tau_1) < P(\tau_2)) \implies \text{able}(P(\tau_1) > P(\tau_2)) \\ \text{able}(P(\tau_1) > P(\tau_2)) \not\implies \text{able}(P(\tau_1) < P(\tau_2)) \end{aligned}\]따라서 위 상황에서는 $\tau_1$ 에 더 높은 우선순위를, $\tau_2$ 에 더 낮은 우선순위를 할당해야 한다.
일반화하여 합리적인 우선순위 할당 규칙은 실행 시간과 무관하게 요청률(앞서 주기 $T$ 의 역수로 정의함)에 따라 작업에 우선순위를 할당해야 한다. 더 높은 요청률을 가진 작업이 더 높은 우선순위를 갖게 하고, 이러한 우선순위 할당 방식을 rate-monotonic 우선순위 할당(rate-monotonic priority assignment)으로 정의한다.
임의의 실행 가능한 고정 우선순위 할당에서 요청률이 더 낮은 작업이 더 높은 작업보다 높은 우선순위를 갖는 인접한 두 작업을 선택하여 그 우선순위를 교환하더라도 실행 가능성은 유지된다. 이러한 교환을 반복하면 실행 가능성을 유지하면서 모든 작업을 요청률 순으로 정렬할 수 있으므로, rate-monotonic 우선순위 할당 역시 실행 가능하다.
정리 2
어떤 작업 집합에 대해 실행 가능한 고정 우선순위 스케줄링이 존재한다면, rate-monotonic 스케줄링을 사용하여도 실행 가능하다.
프로세서 이용률(Processor Utilization)의 상한
정리 2를 통해 rate-monotonic 우선순위 할당이 고정 우선순위 알고리즘 중 최적임을 확인했다. 이 알고리즘으로 프로세서 이용에 이득이 있는지 확인하기 위해, 프로세서 이용률의 상한을 구할 수 있다.
프로세서 이용률은 전체 시간 중 작업 실행에 사용되는 비율로 정의하며, $m$ 개의 작업에 대해 다음과 같이 나타낼 수 있다.
\[U = \sum_{i=1}^{m} \frac{C_i}{T_i}\]어떤 작업 집합이 특정 우선순위 배정 하에서 실행 가능하면서, 그중 어느 한 작업의 실행 시간을 조금이라도 늘리면 더 이상 실행 불가능해지는 경우, 이 작업 집합은 프로세서를 “완전히 활용(fully utilize)”한다고 말한다.
고정 우선순위 스케줄링 알고리즘에 대해, 프로세서를 완전히 활용하는 모든 작업 집합들의 이용률 중 최솟값을 이 알고리즘의 “이용률의 최소 상한(least upper bound)”이라고 정의한다. 이 값 이하의 이용률을 갖는 모든 작업 집합은 항상 고정 우선순위로 실행 가능한 스케줄이 존재한다.
rate-monotonic 스케줄링이 최적의 스케줄링이므로, 임의의 작업 집합에 대해 rate-monotonic 스케줄링으로 얻는 이용률은 다른 어떤 고정 우선순위 스케줄링으로 얻는 이용률보다 항상 크거나 같다. 따라서 고정 우선순위 알고리즘의 이용률의 최소 상한은, 가능한 모든 요청 주기와 실행 시간의 조합에 대해, rate-monotonic 스케줄링의 이용률의 하한이다.
정리 3
정리 3
고정 우선순위를 갖는, 두 개의 작업으로 구성된 작업 집합에 대해, 프로세서 이용률의 최소 상한은 $U = 2(2^{1/2} - 1) \approx 0.83$ 이다.
$\tau_1, \tau_2$ 의 주기를 $T_1, T_2$, 실행 시간을 $C_1, C_2$ 라 하고 $T_2 > T_1$ 이라 하자. rate-monotonic 배정에 따라 $\tau_1$ 이 더 높은 우선순위를 갖는다. $\tau_2$ 의 임계 시간대 안에서는 $\tau_1$ 에 대한 요청이 $\lceil T_2/T_1 \rceil$ 번 발생한다. 프로세서를 완전히 활용하도록 $C_2$ 를 조정하면 두 가지 경우가 발생한다.
경우 1: $C_1$ 이 충분히 짧아, $\tau_2$ 의 임계 시간대 내에서 발생하는 $\tau_1$ 의 모든 요청이 두 번째 $\tau_2$ 요청 이전에 완료되는 경우, 즉
\[C_1 \leq T_2 - T_1 \lfloor T_2/T_1 \rfloor\]이 경우 가능한 $C_2$ 의 최댓값은 $C_2 = T_2 - C_1 \lceil T_2/T_1 \rceil$ 이며, 대응하는 이용률은
\[U = 1 + C_1\left[\frac{1}{T_1} - \frac{1}{T_2}\left\lceil \frac{T_2}{T_1} \right\rceil\right]\]이고, 이는 $C_1$ 에 대해 단조 감소한다.
경우 2: $\tau_1$ 의 $\lceil T_2/T_1 \rceil$ 번째 요청의 실행이 $\tau_2$ 의 두 번째 요청과 겹치는 경우, 즉 $C_1 \geq T_2 - T_1\lfloor T_2/T_1 \rfloor$ 인 경우, 이용률은 $C_1$ 에 대해 단조 증가한다.
따라서 $U$ 의 최솟값은 두 경우의 경계, 즉 $C_1 = T_2 - T_1\lfloor T_2/T_1 \rfloor$ 에서 발생한다. $I = \lfloor T_2/T_1 \rfloor$, $f = {T_2/T_1}$ (소수 부분)로 두면
\[U = 1 - \frac{f(1-f)}{I + f}\]이 식은 $I$ 에 대해 단조 증가하므로, $T_1 < T_2$ 인 한 가능한 가장 작은 값인 $I = 1$ 에서 최소가 된다. 이때 $f$ 에 대해 최소화하면 $f = 2^{1/2} - 1$ 에서
\[U = 2(2^{1/2} - 1) \approx 0.83\]에 도달한다.
$f = 0$, 즉 $T_2$ 가 $T_1$ 의 배수인 경우에는 이용률이 1까지 도달할 수 있다.
정리 4
두 작업에 대한 결과는 임의의 개수의 작업으로 확장할 수 있다. 우선 임의의 두 주기 사이의 비율이 2 미만이라는 제약을 추가하여 다음을 증명한다.
정리 4
고정 우선순위를 가지며, 임의의 두 요청 주기 간 비율이 2 미만인, $m$ 개의 작업으로 구성된 작업 집합에 대해, 프로세서 이용률의 최소 상한은 $U = m(2^{1/m} - 1)$ 이다.
$\tau_1, \dots, \tau_m$ 의 주기를 $T_m > T_{m-1} > \cdots > T_1$ 이라 하고, 프로세서를 완전히 활용하면서 이용률을 최소화하는 실행 시간을 $C_1, \dots, C_m$ 이라 하자. $C_1$ 이 $T_2 - T_1$ 에서 조금이라도 벗어나면(늘어나거나 줄어들면), 그 차이만큼을 다른 작업의 실행 시간으로 이전하여 여전히 프로세서를 완전히 활용하면서 이용률을 더 낮출 수 있음을 보일 수 있다. 이는 $C_1$ 이 최적일 때의 값이 정확히 $T_2 - T_1$ 이어야 함을 의미하며, 같은 논리를 반복하면
\[C_1 = T_2 - T_1,\quad C_2 = T_3 - T_2,\quad \dots,\quad C_{m-1} = T_m - T_{m-1}\]이 성립하고, 마지막 작업의 실행 시간은 $C_m = T_m - 2(C_1 + \cdots + C_{m-1})$ 로 정해진다. $g_i = (T_m - T_i)/T_i$ 로 치환하여 이용률을 정리하면
\[U = 1 + g_1\frac{g_1 - 1}{g_1 + 1} + \sum_{i=2}^{m-1} g_i \frac{g_i - g_{i-1}}{g_i + 1}\]이 식을 각 $g_j$ 에 대해 편미분하여 0으로 두면 연쇄적인 차분방정식이 얻어진다. 이때 첫 항의 경계값으로 $g_0 := 1$ 을 도입하면(실제 작업에서 유도된 $g_1, \dots, g_{m-1}$ 과 달리, 재귀식을 통일된 형태로 쓰기 위해 정의한 값이다) 위 식을 $g_1(g_1 - g_0)/(g_1+1) + \cdots$ 형태로 통일해서 쓸 수 있고, 이 차분방정식을 풀면
\[g_j = 2^{(m-j)/m} - 1,\qquad j = 0, 1, \dots, m-1\]이라는 일반해를 얻는다. ($j=0$ 을 대입하면 $g_0 = 2^{m/m}-1 = 1$ 로, 앞서 도입한 경계값과 일치함을 확인할 수 있다.) 이를 대입하면
\[U = m(2^{1/m} - 1)\]이 도출된다. $m = 2$ 일 때는 정리 3의 결과와 일치하며($U \approx 0.83$), $m = 3$ 일 때 $U = 3(2^{1/3} - 1) \approx 0.78$, $m$ 이 커질수록
\[\lim_{m \to \infty} U = \ln 2 \approx 0.693\]으로 수렴한다.
정리 5
정리 4는 두 요청 주기 간 비율이 2 미만이라는 제약 하에 증명되었는데, 이 제약은 다음과 같이 제거할 수 있다.
정리 5
고정 우선순위를 갖는, $m$ 개의 작업으로 구성된 작업 집합에 대해, 프로세서 이용률의 최소 상한은 (주기 비율에 대한 제약 없이) $U = m(2^{1/m} - 1)$ 이다.
어떤 작업 $\tau_i$ 에 대해 $\lfloor T_m/T_i \rfloor > 1$ 인 경우, 즉 $T_m = qT_i + r\ (q > 1,\ r \geq 0)$ 인 경우를 생각하자. $\tau_i$ 를 $T_i’ = qT_i$, $C_i’ = C_i$ 인 작업 $\tau_i’$ 로 대체하고, 이로 인해 비게 되는 시간만큼 $C_m$ 을 늘려 다시 프로세서를 완전히 활용하도록 만들면, 이렇게 얻은 새 이용률 $U’$ 은 원래의 $U$ 보다 작거나 같음을 보일 수 있다. 즉 두 주기 간 비율이 2 이상인 임의의 작업 집합은, 이용률을 늘리지 않으면서 비율이 2 미만인 작업 집합으로 항상 환원할 수 있다. 따라서 이용률의 최소 상한을 구할 때는 비율이 2 미만인 경우만 고려해도 충분하며, 정리 4의 결과가 일반적인 경우에도 그대로 성립한다.
동적 우선순위 스케줄링(Deadline-Driven Scheduling)
앞선 결과들은 고정 우선순위 알고리즘, 그중 최적인 rate-monotonic 알고리즘조차도 작업 개수가 많아질수록 보장 가능한 이용률이 $\ln 2 \approx 69.3\%$ 수준까지 낮아짐을 보여준다. 즉 특정 작업 집합에 대해서는 이용률이 70%에도 못 미치는 상황에서 스케줄링에 실패할 수 있다. 이 한계를 극복하기 위해, 우선순위를 작업 생성 시 한 번 고정하는 대신 매 요청마다 동적으로 재계산하는 알고리즘을 고려한다.
‘deadline-driven 스케줄링 알고리즘’은 각 작업에, 현재 순간 미완료 요청의 마감 기한에 따라 우선순위를 부여한다. 마감 기한이 가장 가까운 요청을 가진 작업이 가장 높은 우선순위를 가지며, 매 순간 아직 완료되지 않은 요청들 중 가장 높은 우선순위(즉 마감 기한이 가장 임박한) 작업이 실행된다. 우선순위가 요청마다 달라질 수 있으므로 이는 동적(dynamic) 스케줄링 방식이다. (오늘날에는 이러한 방식을 일반적으로 Earliest Deadline First, EDF라 부른다.)
정리 6
정리 6
deadline-driven 알고리즘으로 작업 집합을 스케줄링할 때, 오버플로(마감 기한 위반)가 발생하기 직전까지 프로세서가 유휴(idle) 상태로 남아있는 구간은 존재하지 않는다.
시간 $0$ 부터 시작하여 오버플로가 발생하는 첫 시점을 $t_3$ 라 하고, $t_3$ 에 가장 가까운 유휴 구간을 $[t_1, t_2]$ 라고(즉 $t_2$ 와 $t_3$ 사이에는 유휴 구간이 없다), $t_2$ 이후 각 작업 $1, \dots, m$ 의 첫 요청 시각을 $a, b, c, \dots$ 라고 가정한다.
작업 1의 모든 요청 시각을 앞당겨서 $a$ 가 $t_2$ 와 일치하도록 만들면, $t_2$ 와 $t_3$ 사이에 유휴 구간이 없었으므로 $a$ 이후에도 유휴 구간이 생기지 않으며, 오버플로는 $t_3$ 시점이거나 그 이전에 여전히 발생한다. 이 논증을 나머지 모든 작업에 대해서도 반복하면, 모든 작업이 $t_2$ 시점에 동시에 요청을 시작하더라도 그 이전에 유휴 구간 없이 오버플로가 발생한다고 서술할 수 있다. 그런데 이는 시간 $0$ 부터 오버플로 이전에 유휴 구간이 존재한다는 가정과 모순된다. 따라서 오버플로 이전에는 유휴 구간이 존재할 수 없다.
정리 7
정리 6을 이용하면 deadline-driven 알고리즘의 실행 가능성에 대한 필요충분조건을 유도할 수 있다.
정리 7
주어진, $m$ 개의 작업으로 구성된 작업 집합에 대해, deadline-driven 스케줄링 알고리즘이 실행 가능하기 위한 필요충분조건은 다음과 같다. \(\frac{C_1}{T_1} + \frac{C_2}{T_2} + \cdots + \frac{C_m}{T_m} \leq 1\)
필요조건: $t = 0$ 부터 $t = T_1 T_2 \cdots T_m$ 까지 모든 작업이 요구하는 총 연산 시간은
\[(T_2 T_3 \cdots T_m)C_1 + (T_1 T_3 \cdots T_m)C_2 + \cdots + (T_1 T_2 \cdots T_{m-1})C_m\]이다. 여기서 $T_1 T_2 \cdots T_m$ 은 모든 $T_i$ 의 공배수이므로, 이 구간에서 각 작업의 요청 횟수를 정수로 계산할 수 있다.
이 값이 가용 프로세서 시간 $T_1 T_2 \cdots T_m$ 을 초과하면, 즉 양변을 $T_1 T_2 \cdots T_m$ 으로 나눈 $\sum (C_i/T_i)$ 가 1을 초과하면 실행 가능한 스케줄이 존재할 수 없다.
충분조건: 반대로 $\sum (C_i/T_i) \leq 1$ 이 성립함에도 스케줄이 실행 불가능하다고 가정하면, $0$ 과 $T_1 T_2 \cdots T_m$ 사이 어딘가에서 오버플로가 발생한다. 정리 6에 의해 이 오버플로가 일어나는 시점 $T$ 이전에는 유휴 구간이 없다.
이때 (i) $T$ 이전에 마감 기한이 $T$ 이후인 요청들이 전혀 처리되지 않은 경우와, (ii) 그중 일부가 이미 처리된 경우로 나누어 각각 $0$부터 $T$까지의 총 연산 수요가 $T$ 를 초과함을 보일 수 있는데, 이는 곧 $\sum (C_i/T_i) > 1$ 을 의미하여 가정과 모순된다. 따라서 $\sum (C_i/T_i) \leq 1$ 이면 항상 실행 가능하다.
따라서 deadline-driven 알고리즘은 이용률이 100%에 도달할 때까지 실행 가능성이 보장된다. 즉 이 알고리즘의 이용률의 최소 상한은 1이며, 이 논문에서 설정한 주기적·독립적 작업 등의 가정 하에서, 어떤 작업 집합이 어떤 방식으로든 스케줄링 가능하다면 deadline-driven 알고리즘으로도 반드시 스케줄링할 수 있다는 의미에서 전역적으로 최적(globally optimum)이다.
혼합 스케줄링 알고리즘(Mixed Scheduling Algorithm)
deadline-driven 알고리즘은 이론적으로 최적이지만, 당시 컴퓨터의 인터럽트 하드웨어는 대체로 고정 우선순위 방식으로 동작했다. 이를 소프트웨어 스케줄러로 완전히 대체하는 데는 비용이 요구되었고, 상대적으로 느리게 반복되는 작업들을 deadline-driven 방식으로 처리하는 데 드는 구현 비용은 크지 않았다.
이러한 관찰에 착안하여, 두 방식을 절충한 혼합 스케줄링 알고리즘도 고안되었다. 요청 주기가 가장 짧은 $k$ 개의 작업 $\tau_1, \dots, \tau_k$ 는 rate-monotonic 방식의 고정 우선순위로 스케줄링하고, 나머지 $\tau_{k+1}, \dots, \tau_m$ 은 상위 $k$ 개의 작업이 프로세서를 점유하지 않는 시간 동안 deadline-driven 방식으로 스케줄링한다.
이를 분석하기 위해 가용 함수(availability function) $a(t)$ 를 정의하였다. 음이 아닌 값을 갖는 비감소 함수 $a(t)$ 가 모든 $t, T$ 에 대해
\[a(T) \leq a(t + T) - a(t)\]를 만족하면 $a(t)$ 를 준선형(sublinear) 이라 한다. $k$ 개의 작업이 고정 우선순위로 스케줄링된 상태에서, 나머지 작업 $\tau_{k+1}, \dots, \tau_m$ 에게 실질적으로 남는 누적 프로세서 시간을 $a_k(t)$ 라 하면, 임계 시간대 논증을 통해 $a_k(t)$ 가 준선형임을 보일 수 있다.
정리 8
정리 8
어떤 작업 집합이 준선형인 가용 함수를 갖는 프로세서 위에서 deadline-driven 알고리즘으로 스케줄링된다면, 오버플로 이전에 프로세서 유휴 구간은 존재하지 않는다.
정리 6과 유사한 논증(가용 함수의 준선형성을 이용해 요청 시각을 앞당기는 방식)으로 증명된다.
정리 9
정리 9
가용 함수 $a_k(t)$ 를 갖는 프로세서에 대해, deadline-driven 알고리즘의 실행 가능성에 대한 필요충분조건은 $T_{k+1}, T_{k+2}, \dots, T_m$ 의 배수인 모든 $t$ 에 대해 다음이 성립하는 것이다. \(\left\lfloor \frac{t}{T_{k+1}} \right\rfloor C_{k+1} + \left\lfloor \frac{t}{T_{k+2}} \right\rfloor C_{k+2} + \cdots + \left\lfloor \frac{t}{T_m} \right\rfloor C_m \leq a_k(t)\)
정리 7과 마찬가지로, 임의의 시점에서 총 연산 수요가 가용 프로세서 시간을 초과할 수 없다는 필요성과, 정리 8을 이용한 충분성 증명으로 이루어진다.
예시
정리 9는 일반적으로 대단히 많은 부등식의 해를 요구하므로, 실제로는 특수한 경우에 대해 더 간단한 충분조건을 유도해 사용하는 편이 실용적이다. 다음은 세 개의 작업 중 가장 짧은 주기를 가진 하나만 고정 우선순위로, 나머지 두 개를 deadline-driven 방식으로 스케줄링하는 예시이다.
$T_1 = 3,\ T_2 = 4,\ T_3 = 5,\ C_1 = C_2 = 1$ 일 때, $a_1(20) = 13$ 임을 계산할 수 있고, 이로부터 $C_3$ 의 최댓값은 2가 된다. 이때 이용률은
\[U = \frac{1}{3} + \frac{1}{4} + \frac{2}{5} = 98.3\%\]에 이른다. 반면 세 작업을 모두 고정 우선순위(rate-monotonic) 방식으로만 스케줄링하면 $C_3$ 은 1 이하로 제한되어 이용률이
\[U = \frac{1}{3} + \frac{1}{4} + \frac{1}{5} = 78.3\%\]에 그친다.
따라서 혼합 스케줄링 알고리즘이 기존 인터럽트 하드웨어와의 호환성을 유지하면서도 deadline-driven 알고리즘에 근접한 수준의 이용률을 달성할 수 있다고 판단할 수 있다.