The Rate Monotonic (RM) Scheduling Algorithm : Exact Characterization And Average Case Behavior

한종우·2021년 3월 16일

Paper Rate Monotonic Real-Time System rm scheduling

Paper Review

목록 보기

3/7

사담

새로 진행하게 된 연구에 대해 선배가 추천해준 논문이다. Rate Monotonic에 대한 정의나 Liu & Layland의 증명들은 기존의 수업이나 논문들에서 봤었던 내용이기도 했는데, 1989년이라는 꽤나 오래된 논문이라 그런 듯 하다. 내용적으로는 Asymptotic Approximation을 한다고 notation이 많이 생기는데 해당 notation을 사용하는 이유가 없어서 이해가 잘 안된다. 그래도 exact characterization까지는 처음 보더라도 꽤나 납득 가능하다.

Intro

Real-Time System에서 더 좋은, 나아가 optimal한 스케줄링 알고리즘을 찾는 문제는 가장 흔하면서도 중요한 주제다. constraint에 따라 optimal algorithm 역시 달라지기 때문에 남들이 하지 않은 constraint만 찾는다면 그 상황에서의 스케줄링 알고리즘을 찾는 연구를 진행할 수 있다. 이 논문은 새로운 알고리즘을 찾았다기보다는 Dynamic Priority (Job마다 priority가 부여되는 경우)에 대해 optimal algorithm인 Rate Monotonic algortihm에 대해 통계적으로 분석하고, utilization bound보다 더 정확한 schedulability test를 찾은 논문이다.

EDF와 RM

스케줄링 알고리즘을 Priority의 부여 방식에 따라 아래처럼 나눌 수 있다.

Fixed Priority Algorithm : Task 단위로 부여 (ex : EDF (Earliest Deadline First)
이 경우 같은 task의 모든 job의 priority가 같다.
Dynamic Priority Algorithm : Job 단위로 부여 (ex : RM (Rate Monotonic))

Liu & Layland에 따르면

RM으로는 utilization이 $n(2^{1/n}-1)$ 이하인 task set은 스케줄 가능하며
EDF로는 utilization이 1 이하인 task set은 스케줄 가능하다.

$n(2^{1/n}-1)$ 이 n=2일 때 0.83, $n \rightarrow \infty$ 일 때 0.693인걸 생각하면 EDF가 훨씬 좋아보인다. 하지만, 저자는 아래의 5개 이유를 들며 practical에서는 RM도 중요하며, 이 논문이 그래서 필요하다고 말한다. (이런게 논문의 기술이 아닐까)

순간적인 overload가 있더라도 대부분의 중요 task의 deadline을 만족
deferrable, sporadic server의 경우 periodic task의 deadline을 만족하면서 aperiodic task에게 빠른 response time을 제공 가능
task synchronization requirements를 다룰 수 있도록 고칠 수 있다.
(이건 뭔지 잘 모르겠다.)
imprecise computation을 할 때 쉽게 사용할 수 있다.
프로세서에 구현하기가 쉽다.

Contribution

Rate Monotonic 알고리즘으로 스케줄 가능한 task set의 정확한 특성에 대해 기술한다. (기존의 Liu&Layland bound처럼 단순히 utilization bound만 보는 것보다 더 정확한 schedulability 판단 방법을 제시)
random task set에 대해 시뮬레이션하여 utilization bound에 대한 통계적인 결과를 제공한다. (실험적인 utilization bound를 제시)

System Model

고전 논문이라 그런지 system model 자체는 일반적으로 사용하는 정의들과 같다. notation이 좀 다를 뿐..

n개의 periodic task $\tau = {\tau_1, \dots, \tau_n}$ 를 고려한다.
각 task $\tau_i$ 는 period $T_i$ , 실행 시간 $C_i$ , offset $I_i$ (논문에서는 phasing이라고 표현한다.)를 가진다.
편의를 위해 주기가 짧은 순으로 indexing되어있다고 가정한다.
( $T_1 \le T_2 \le \dots \le T_n$ )
RM을 사용하므로 index가 작을수록 priority는 높다.

그 외 notation과 가정은 아래와 같다.

critical instant : 모든 task의 offset이 0일 때 worst case response time을 가진다. 본 논문에서는 critical instant 상황을 가정한다.
Liu & Layland에 의하면 각 task의 first job이 deadline을 만족하면 스케줄 가능하다.
processor demand $W_i(t) = \sum_{j=1}^{i}C_j \lceil t/T_j \rceil$
(시간 t까지 $\tau_i$ 가 실행되거나 preemption당하는 시간을 의미한다.)
$L_i(t) = W_i(t) / t$
$L_i = min_{\{ 0 < t \le T_i \}} L_i(t)$
$L = max_{\{ 1 \le i \le n \}} L_i$

Exact Characterization of schedulability

Theorem 1
periodic task $\tau_1, \dots, \tau_n$ 에 대해
1. RM 하에서 $\tau_i$ 가 스케줄 가능할 필요충분조건은 $L_i \le 1$
2. RM 하에서 task set 전체가 스케줄 가능할 필요충분조건은 $L \le 1$

pf for 1)
system model의 가정 상 $\tau_i$ 보다 priority가 높은 task들은 $\tau_1, \dots, \tau_{i-1}$ 이다. 따라서 $\tau_1, \dots, \tau_i$ 의 실행 시간의 합이 deadline을 넘지 않으면 된다. 이 때 가정에 따라 first job들만 확인한다.

$\tau_i$ 이 schedulable
$\iff$ $\tau_1, \dots, \tau_i$ 이 $T_i$ 전에 완료
$\iff$ $W_i(t) = t, W_i(s) > s \ for \ 0 \le s < t$ 인 $t \in [0, T_i]$ 가 존재
$\iff$ $L_i(t) = 1, L_i(s) > 1 \ for \ 0 \le s < t$ 인 $t \in [0, T_i]$ 가 존재
$\iff$ $L_i \le 1$
( $t \le s < T_i$ 에 $L_i(s)$ 가 1보다 작아질 수 있기 때문에 등호는 아니다.)

pf for 2)
task set 전체가 schedulable하려면 각 task들이 스케줄 가능해야 하므로 모든 $L_i \le 1$ 이고 따라서 L 역시 1보다 작다.

Schdeuling Point

이제 우리는 L을 구하여 task set이 스케줄 가능한지 쉽게 확인할 수 있다. 그런데 $[0, T_i]$ 인 모든 연속적인 시간에 대해 확인하는 것은 현실적으로 어렵다. 하지만 생각해보면 모든 시간을 확인할 필요가 없는 것이

새로운 job이 release되기 전까지는 $\lceil t/T_j \rceil/t$ 가 계속 감소한다.
따라서 각 task의 period의 배수는 $L_i(t)$ 의 극소점이라고 생각할 수 있다.

$L_i$ 는 $L_i(t)$ 의 최소값을 찾는 것이므로 극소점들 중 최소값을 찾아도 값은 동일하다. 따라서 아래의 scheduling point들에 대해서만 $L_i(t)$ 를 확인해도 무방하다.
$S_i = \{ k \cdot T_j | j = 1, \dots, i \ ; \ k = 1, \dots , \lfloor \frac{T_i}{T_j} \rfloor \}$

이제 Thm 1을 아래처럼 개선할 수 있다.

Theorem 2
periodic task $\tau_1, \dots, \tau_n$ 에 대해
1. RM 하에서 $\tau_i$ 가 스케줄 가능할 필요충분조건은
$L_i = min_{\{ t \in S_i \}}W_i(t)/t \le 1$
2. RM 하에서 task set 전체가 스케줄 가능할 필요충분조건은
$L = max_{\{ 1 \le i \le n \}}L_i(t)\le 1$

example
$\tau_1 : C_1 = 40,T_1=100,U_1=0.400$
$\tau_2 : C_2 = 40,T_2=150,U_2=0.267$
$\tau_3 : C_3 = 100,T_3=350,U_3=0.286$

L&L bound로 보면 $U_1+U_2 = 0.667 < 2(2^{1/2}-1) = 0.828$ 이므로 $\tau_2$ 까지는 스케줄 가능하나 $U = 0.953 > 3(3^{1/2}-1) = 0.779$ 이므로 $\tau_3$ 이 스케줄 가능한지는 알 수 없다.
하지만 $S_3 = \{ 100, 150, 200, 300, 350 \}$ 중 t = 300일 때 $3C_1 + 2C_2 + C_3 \le 2T_2$ 를 만족하므로 스케줄 가능하다. (t = 350일 때에는 오히려 등호가 반대로 되지만 이미 $\tau_3$ 의 실행을 다 마친 상태이므로 다른 job에 preemption되는 것은 무방하다.)

Stochastic Characterization

이 단락에서는 random task를 만들어서 utilization bound를 통계적으로 찾고자 한다. critical instant를 가정하므로 offset은 모두 0이라 하면 각 task에 남은 변수는 period $T_i$ 와 실행 시간 $C_i$ 다. 따라서 누적분포함수 (c.d.f.) $F_T(t)$ 에서 period를 random하게 만들고, $F_C(c)$ 에서 실행 시간을 random하게 만들고자 한다. 하지만 완전히 랜덤하게 뽑으면 utilization 값이 이상할 것이기 때문에 모든 $C_i$ 에 $\Delta$ 를 곱해준다.
이 때 $\Delta$ 를 작은 값으로부터 늘려가면서 dealine miss가 일어나는 시점에 멈추는데, 이 때의 utilzation $U_n^{*}$ 을 breakdown utilizaiton라고 정의하며 이 때의 곱하는 scaling factor 값은 $\Delta^*$ 로 표기한다.

Theorem 2로부터 task set이 schedulable할 필요충분조건은
$L = max_{\{1 \le i \le n\}}min_{\{t \in S_i\}} \sum_{j=1}^{i} \Delta C_j \lceil t/T_j \rceil/t \le 1$
$\iff$ $\Delta \le [max_{\{1 \le i \le n\}}min_{\{t \in S_i\}} \sum_{j=1}^{i} C_j \lceil t/T_j \rceil/t]^{-1}$
이다.
따라서 $\Delta$ 의 최대값에 해당하는 $\Delta^*$ 는
$\Delta^* = [max_{\{1 \le i \le n\}}min_{\{t \in S_i\}} \sum_{j=1}^{i} C_j \lceil t/T_j \rceil/t]^{-1}$
임을 알 수 있다. 이 때의 breakdown utilization은 아래와 같다.
$U_n^{*} = \sum\frac{C_i*\Delta}{T_i} = \sum_{i=1}^{n}U_i/[max_{\{1 \le i \le n\}}min_{\{t \in S_i\}} \sum_{j=1}^{i} C_j \lceil t/T_j \rceil/t]$

분자는 일반적인 total utilization 식이며, scaling factor의 최대값을 구해야 하기 때문에 모든 i에 대해 max 값을 구하며, 이 때의 t는 실제로 deadline miss가 발생하는 시간을 의미한다.

Theorem 3
$1 \le T_1 \le \dots \le T_n \le 2$ 에 대해
$U_n^{*} = [\sum_{i=1}^{n}C_i/T_i]/[min_{\{t \in S_n\}} \sum_{j=1}^{n} C_j \lceil t/T_j \rceil/t]$

즉, $F_T(1)=0, F_T(2)=1$ 인 경우 분모는 i=n일 때 최대라는 것이다.
pf)
$\delta_i=min_{\{t \in S_i\}} \sum_{j=1}^{i} C_j \lceil t/T_j \rceil/t$ 라 정의하고 모든 i에 대해 $\delta_{i+1} \ge \delta_i$ 임을 보이자.
먼저 한 task의 period 내에 다른 task가 두 번 release할 수 없으므로 ( $\because \lfloor T_n / T_1 \rfloor = 1$ ) $S_i = \{ T_1, \dots, T_i \}$ 다.

(i)
$\delta_{i+1}$ 의 최소값이 $t=T_j (1 \le j \le i)$ 에서 구해진다고 가정하면,

\delta_{i+1} = [2(C_1+\dots+C_{j-1})+C_j+\dots+C_{i+1}]/T_j \\ \ge [2(C_1+\dots+C_{j-1})+C_j+\dots+C_i]/T_j \\ = \delta_i

( $\because$ 1부터 i+1까지 최소가 j에서 구해지므로 1부터 i까지 중에서도 최소는 j에서 구해짐)

(ii) $t = T_{i+1}$ 에서 최소인 경우
$\delta_{i}$ 의 최소값은 $t=T_j (1 \le j \le i)$ 에서 구해진다고 가정하자. 그렇다면
$\delta_{i} = [2(C_1+\dots+C_{j-1})+C_j+\dots+C_{i}]/T_j$ 이고

\delta_{i+1} = [2C_1+\dots+2C_i+C_{i+1}]/T_{i+1} \\ \ge [2C_1+\dots+2C_i]/T_{i+1} \\ \ge [2(C_1+\dots+C_{j-1})+C_j+\dots+C_{i}]/T_{i+1} \\ \ge [2(C_1+\dots+C_{j-1})+C_j+\dots+C_{i}]/T_{j} \\ = \delta_i

$C_i \ge 0$ 이고 $T_i$ 가 오름차순으로 정렬되어 있어 가능한 얘기다. 참고로 논문에서는 중간 과정이 좀 생략되어있다.

모든 i에 대해 $\delta_{i+1} \ge \delta_i$ 이므로 i=n일 때 최대임은 자명하다.

Asymptotic Approximation

notation이 많이 나오는데 이해하지 못해서 결과만 적자면

U_n^{*} = \sum_{i=1}^{n}U_i/[max_{\{1 \le i \le n\}}min_{\{t \in S_i\}} \sum_{j=1}^{i} C_j \lceil t/T_j \rceil/t]

에 대해 적절한 변환을 통해 정규분포로 나타낼 수 있다.

n^{1/2}(U_n^* - E(1/T)/w) \rightarrow N(0, \sigma^2)

$T_i$ 가 $1 \le T_i \le B$ 로 어떤 B에 대해 bound되어있다고 가정하는데, B를 바꿔가면서 실험해보면 가능한 최대 utilization bound가

B가 1.0일 때 1.000으로 시작하며
B가 2.0일 때까지 0.693 (L&L의 worst case bound)으로 감소하다가
B가 증가함에 따라 천천히 1로 수렴한다.

즉, 단순히 0.693을 사용할 것이 아니라 period가 bound된 값에 따라서 utilization bound를 더 키울 수도 있다.

Question

Asymptotic Approximation에 나오는 수식들을 정의하는 이유를 모르겠다
B를 늘리면서 실험하는 것이 정규 분포임을 증명하는 것과 어떤 연관이 있는지 모르겠다

Ref

J. Lehoczky, L. Sha and Y. Ding, "The rate monotonic scheduling algorithm: exact characterization and average case behavior," [1989] Proceedings. Real-Time Systems Symposium, Santa Monica, CA, USA, 1989, pp. 166-171, doi: 10.1109/REAL.1989.63567.