Improved schedulability analysis of EDF on multiprocessor platforms

느낀점

 

• 기존의 GFB와 BAK 테스트가 완벽하지 않다는 점을 실제 반례와 함께 명확히 보여줘서 이해가 쉬웠다.
• 새로운 BCL 테스트는 수학적으로도 설득력 있고, heavy task가 있을 때 훨씬 실용적이라는 점이 인상 깊었다.
• 전체적으로 복잡한 이론을 실험과 함께 잘 설명해줘서 멀티코어 스케줄링 연구의 흐름을 배우기에 좋은 논문이었다.

 

Background Knowledge

본 논문을 이해하는데 필요한 여러 측면의 시각을 정리해보겠다. 

• Multi Processor 하드웨어 플랫폼이 임베디드 시스템에서 널리 사용되고 있으며, 실시간 어플리케이션을 스케줄링할 때 글로벌 스케줄링 방식을 사용할 수 있다. 글로벌 스케줄링에서는 스케줄링 알고리즘이 Task를 프로세서와 동적으로 할당하며, Task는 실행 중에 다른 프로세서로 마이그레이션 할 수 있다. 
• 이 논문은 글로벌 EDF 스케줄링 시스템에서 sporadic(산발적) Task의 Schedulability analysis 문제를 다루고 있다. 
• 최근에 제안된 (이 논문 이전의) 두 가지 스케줄 가능성 테스트인 GFB(Goossens, Funk, Baruah) 테스트와 BAK(Baker) 테스트는 Heavy Tasks(Utilization이 높은 Task)를 포함하는 Task Set에서 성능이 좋지 않다는 것을 보여준다. 또한, 이 Task는 서로를 dominate(지배)하지 않는다는 것을 증명했다.
• 이 논문의 주요 기여 중 하나는 새로운 스케줄 가능성 테스트(BCL 테스트)를 도입하는 것이다. 이 테스트는 허용되는 Task Set의 비율을 크게 개선하며, 특히 Heavy Task를 고려할 때 효과적이다.
• BCL 테스트는 Interference 및 Workload에 대한 Upper Bound를 사용하여 도출되었다. 핵심 아이디어는 Task $\tau_k$에 대한 Task $\tau_i$의 간섭을 분석할 때, Heavy Task의 전체 Load를 과대평가하지 않도록 $(1-\lambda_k)$라는 항으로 기여를 제한하는 것이다. 여기서 $\lambda_k=C_k/D_k$는 Task $\tau_k$의 worst-case request이다. 이 $(1-\lambda_k)$항은 Heavy Task ($\lambda_k$가 높을수록 1에 가까워짐)가 다른 Task에게 줄 수 있는 간섭의 최대치를 제한하여, 총 간섭량을 보다 정확하게 예측하는데 도움을 준다. 
• 실험 결과는 BCL 테스트가 Heavy Task가 있는 경우 GFB 및 BAK보다 훨씬 더 많은 Task Set를 스케줄 가능하다고 판단함을 보여준다. 반면 GFB 테스트는 Light Taks(활용률이 0.5 미만인 Task)만으로 구성된 Task Set에 대해 매우 효과적이다. BAK 테스트는 BCL보다 약간 더 나은 carry-in 추정치를 활용하지만, Heavy Task가 있는 경우 BCL만큼 효과적이지는 않다.
• 세 가지 테스트 모두 계산 복잡성이 낮기 때문에, 세 가지 테스트를 조합하여 사용하는 것이 가능하다. GFB는 Light Task set에 효과적이고, BCL은 Heavy Task에 효과적이며, BAK는 다른 두 테스트가 실패하는 매우 드믄 경우에 긍정적인 응답을 줄 수 있다. 따라서 세 테스트 중 하나라도 Task Set를 수락하면 스케줄 가능함이 보장될 수 있다. 이 조합된 테스트의 전체 복잡성은 $O(n^2)$이다.
• 하지만 제공된 모든 테스트는 시뮬레이션이라는 필요충분 조건에 비해 여전히 실제 스케줄이 가능한 Task Set 중 상당 부분을 놓치고 있다. 이는 스케줄 가능성 분석 개선을 위한 추가 연구 여지가 있음을 시사한다. 

Heavy Task가 EDF Based Scheduling의 성능에 어떤 영향을 미칠 수 있을까?

1. Heavy Task의 정의 및 기존 분석의 성능 저하:

• Heavy Task는 Utilization이 0.5보다 큰 Task를 의미한다.
• 멀티 프로세서에서 Global EDF Scheduling 시스템을 위한 최근 두 가지 Scheduabillity Test인 GFB(Goossens, Funk, Baruah) 테스트와 BAK(Baker) 테스트는 Task Set에 Heavy Task가 포함될 때 성능이 좋지 않음을 보였다. 
• GFB 테스트는 최대 활용률($U_max$)이 증가함에 따라 성능이 급격히 저하되는 경향이 있다. Heavy Task가 당연히 $U_max$를 높이는 요인이 된다.
• BAK 테스트는 GFB보다 $U_max$에 직접적으로 의존하지는 않지만, Heavy Task가 포함된 Task Set에서는 여전히 GFB만큼 효과적이지 못하거나, 심지어 Heavy Task가 여러 개 있는 경우에는 두 테스트 모두 거의 긍정적인 응답을 주지 못한다.
• 두 테스트(GFB와 BAK)는 서로를 지배(dominate)하지 않으며, Heavy Task가 있는 경우 Task set에 따라 한 테스트는 통과하지만 다른 테스트는 통과하지 못하는 경우가 많다.

2. BCL 테스트의 등장 및 Heavy Task 처리 개선:

• 이러한 GFB 및 BAK 테스트의 한계를 해결하기 위해 새로운 스케줄 가능성 테스트인 BCL 테스트가 제안되었다. 
• BCL 테스트의 주요 기여 중 하나는 Heavy Task를 포함하는 Task Set에서 허용되는 Task Set의 비율을 크게 개선한다는 것이다.
• BCL 테스트는 Task $\tau_k$에 대한 다른 Task $\tau_i$의 Interference을 분석할 때, 특히 Heavy Task의 Interference 기여분을 과대평가하지 않도록 제한하는 아이디어를 사용한다. 이는 Interference Upper Bound을 도출하는 과정에서 $(1-\lambda_k)$라는 항 $(\lambda_k=C_k/D_k)$을 통해 이루어진다. Heavy Task(높은 활용률)의 경우 $\lambda_k$값이 높아져 $(1-\lambda_k)$항이 작아지므로, 해당 Task가 다른 Task에게 줄 수 있는 최대 간섭량을 보다 정확하게 제한할 수 있었다.
• 실험 결과에 따르면, BCL 테스트는 Heavy Task가 있는 경우 GFB 및 BAK 테스트보다 훨씬 더 많은 Task Set를 스케줄 가능하다고 판단한다. 특히 Heavy Task의 수가 증가할 수록 이러한 차이는 두드러진다. 
• 반면, Heavy Task없이 Light Tasks만으로는 구성된 Task Set의 경우, GFB 테스트가 가장 효과적이며 BCL 테스트는 상대적으로 성능이 떨어진다. 

3. 정리

• 요약하면, 멀티 프로세서 EDF 스케줄링 분석에서 Heavy Task는 기존의 GFB 및 BAK 테스트의 효율성을 크게 떨어뜨리는 요인이다.
• 제안된 BCL 테스트는 Heavy Task가 포함된 Task Set의 스케줄 가능성을 더 효과적으로 판별하기 위해 개발되었으며, 실험적으로 우수한 성능을 보인다. 이는 Heavy Task의 간섭 기여분을 더 정밀하게 제한되는 분석 기법때문이다

 

Problem Statement

멀티프로세서 시스템에서 global EDF(Earliest Deadline First) 알고리즘을 사용할 경우, 주어진 Task Set의 Schedulability를 판단하는 것이 어렵다.

기존의 제안된 두 가지 테스트, 즉 GFB(Goossens, Funk, Baruah)와 BAK(Baker) 테스트는 다음의 문제점이 있다:

• Heavy task(utilization > 0.5)가 포함된 경우 매우 비효율적이다.
• 두 테스트 모두 서로를 완전히 대체하지 못한다.

따라서 이 논문은:

1. 기존 테스트의 한계를 증명하고, 
2. 보다 강력한 새 Schedulability test(BCL)을 제안한다.

 

Contribution

• 상호 비교: 기존 GFB와 BAK 테스트가 서로 우월하지 않다는 점을 이론적 반례와 실험적 결과를 통해 증명
• 새로운 분석 방법(BCL):
  • 특히 Heavy Task가 포함된 경우, Schedulability 분석 정확도를 현저히 향상
  • Theorem 7을 기반으로 한 새로운 Upper Bound 테스트 도출
• 실험:
  • 다양한 구성(Task 수, Processor 수, Heavy/ Light Task 비율)에 대해 실험 수행
  • GFB, BAK 대비 BCL이 더 많은 Task Set을 Schedulable로 판정

 

• 기존의 2개의 EDF(Early Deadline First) 기반 Test인 GFB(Goossens, Funk, Baruah) 및 BAK(Baker) Test를 비교
  • GFB와 BAK는 상호 보완적이며, 어느 하나가 항상 더 우수한 것이 아님을 증명 
• 새로운 스케줄러 Test 제안 (BCL - Bertogna, Cirinei, Lipari, 저자들의 이름이다)
  • 특히 heavy task(과도한 계산량을 요구하는 작업)를 포함한 경우, 기존  GFB 및 BAK 테스트보다 더 많은 Task Set을 스케줄할 수 있음을 증명
  • 이 Test는 총 간섭(interference) 개념을 기반으로 하며, Test 계산식이 더욱 타이트하게 조정되었다.
• 광범위한 실험을 통해서 효과 검증
  • 다양한 조건(Processor 수, Task 수, light, heavy Task 비율 등)에서 수천 개의 Task Set을 실험하여 BCL Test 성능 우위를 입증 

 

 

Key Ideas

1. Global EDF는 optimal하지 않다, 하지만 이론적으로 분석 가치가 있다.
2. GFB Test: 전체 utilization을 기준으로 한 간단한 불평등식 사용
3. BAK Test: 각 Task에 대해 Interference 기반으로 조건을 도출
4. BCL Test(신규 제안): $D_k - C_k$ 만큼만 Interference로 고려함으로써 Overestimation 방지 -> 특히 Heavy Task에 효과적

 

Mathematical View

GFB Test

Theorem 4 (GFB):

$$\sum_{i=1}^{n}\lambda_i\leq (1-\lambda_{max})+\lambda_{max}$$

• $\lambda_i=C_i/D_i$
• $m: number\,\, of\,\, processor$
•  증명 요지: uniform multiprocessor에서의 feasibility 조건과 EDF의 equivalence를 활용

 

BAK Test

Theorem 5 (BAK):

$$\sum_{i=1}^{n}min(1,beta_i)\leq m(1-\lambda_k)+\lambda_k\,\,\,\forall\tau_k $$

$$\beta_i=\begin{Bmatrix}
U_i(1+\frac{T_i-D_i}{D_k})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\lambda_k \geq U_i \\U_i(1+\frac{T_i-D_i}{D_k})+\frac{C_i-\lambda_kT_i}{D_k}\,\,\,\,\,\lambda_k < U_i
\end{Bmatrix}$$

• $\lambda_k=C_k/D_k$
• 아이디어: 각 Job의 Busy Window에 대한 최대 Load Upper Bound 유도

 

BCL Test (Main Contribution)

Lemma 2:

$$I_{i,k}(a,b) \leq W_i(a,b) \leq b-a$$

• Interference는 해당 interval 내 workload를 초과할 수 없다.

증명

• 정의상, $W_i(a,b)$는 Interval [a,b] 내 Task $\tau_i$의 실행 요구랑 (Demand + Carry-in)이다.
• $I_{i,k}(a,b)$는 $\tau_i$가 $\tau_k$를 block하는 시간의 총합으로, $\tau_i$가 실행 중이면서 $\tau_k$가 Ready 상태일 때 발생한다. 
• 이 때 $\tau_i$의 실행 시간을 넘을 수 없으므로: 

$$ I_{i,k}(a,b) \leq = W_i(a,b) $$

• 또한 Task는 Interval 길이 이상을 실행할 수 없으므로:

$$ W_i(a,b) \leq b-a $$

 

Lemma 3: 

$$I_k(a,b)=\frac{1}{m}\sum_{i\neq k}^{}I_{i,k}(a,b)$$

• m-processor에서, ready but not scheduled일 때 m개의 processor는 다른 Task 실행 중

증명

• EDF는 Work-Conserving이므로, $\tau_k$가 Ready인데 실행되지 않는 순간에는 m개의 프로세서가 모두 다른 Task들을 실행 중이어야 한다. 
• 즉  $\tau_k$가 block당한 전체 시간 $I_k(a,b)$동안 m개 processor가 모두 $\tau_k$ 외의 다른 Task를 실행함
• 따라서 이 시간동안 각 $\tau_i$가 $\tau_k$를 block한 시간 $I_{i,k}$의 합은 $m \times I_k$이고:

$$\sum_{i\neq k}^{}I_{i,k}(a,b)=m\cdot I_k(a,b)\Rightarrow I_k(a,b)=\frac{1}{m}\sum_{i\neq k}^{}I_{i,k}(a,b)$$

 

Lemma 4:

$$I_k(a,b)\geq x\Leftrightarrow \sum_{i}^{}min(I_{i,k}(a,b),x)\geq mx$$

증명

$\Rightarrow $ 방향:

• 가정: $I_k(a,b)\geq x$
• 정의: $I_k(a,b)=\frac{1}{m}\sum I_{i,k}(a,b)$
• 목표:

$$\sum min(I_{i,k},x)\geq mx$$

• 이 때 일부 Task는 $I_{i,k} > x$, 일부는 $ \leq x$일 수 있으므로 다음과 같이 분리:
  •  Let $A=\{i | I_{i,k} \geq x\}$ ->  이들에 대해 $min(I_{i,k},x)=x$
  • 나머지 $i$들을 그대로 $I_{i,k}$로 계산됨
• 그러면:

$$\sum min(I_{i,k},x)=|A|\cdot x + \sum_{i\notin A}^{}I_{i,k}=m\cdot I_k-\sum_{i\in A}^{}(I_{i,k}-x)\geq m \cdot x$$

 

$\Leftarrow$ 방향:

• 가정: $\sum min(I_{i,k},x)\geq mx$
• 정의대로:

$$I_k=\frac{1}{m}\sum I_{i,k}\geq \frac{1}{m}\sum min(I_{i,k},x)\geq x$$

 

 

Theorem 6:

Schedulability Condition:

Task $\tau_k$가 Schedulable 하기 위한 필요충분조건:

 

1. $\sum_{i\neq k}^{}min(I_{i,k}^{*}, D_k-C_k)< m(D_k-C_k)$
2. $\sum_{i\neq k}^{}min(I_{i,k}^{*}, D_k-C_k)= m(D_k-C_k)\,\,and\,\, \exists h\neq k:0<I_{h,k}^{*}\leq D_k-C_k $

 

 

Lemma 5 (Carry-in 상계):

$$\varepsilon_i \leq min(C_i,(D_k-N_iT_i)_{0})$$

• $N_i=\left \lfloor \frac{D_k-D_i}{T_i}\right \rfloor + 1$

증명

• Task $\tau_i$가 $[r_k^j, d_k^j]$ interval에 들어올 수 있는 Job 수 $\, N_i$
• 그 외, Carry-in job이 하나 더 존재 가능 -> 해당 Job의 실행 시간 = $\varepsilon_i$
• 최대값은 $C_i$, 혹은 남은 시간 $(D_k-N_iT_i)$ 중 작은 값

 

 

Theorem 7(최종 Schedullability 조건):

$$\sum_{i\neq k}^{}min(\beta_i,1-\lambda_k)< m(1-\lambda_k)$$

또는

$$=m(1-\lambda_k)\,\,and\,\,\exists i\neq k:0<\beta_i\leq 1-\lambda_k$$

여기서, 

$$\beta_i=\frac{NiCi+\varepsilon_i}{D_k}$$

• $\lambda_k=C_k/D_k$
• $N_i$: 해당 Window 내 $\tau_i$의 Job 수
• 핵심 기여: interference의 상계를 보수적으로 조정하여 Overestimation을 방지함

증명

• Theorem 6의 Interference 조건을 Load 형태로 치환
• Workload $W_i=N_iC_i+\varepsilon_i$ -> 이를 $D_k$로 나누면 단위 시간 당 $Load=\beta_i$
• Interference 상한인 $D_k-C_k$는 $\lambda_k=C_k/D_k$로 표현 가능 -> $Slack = 1 - \lambda_k$

-> interference 총합이 $m(1-\lambda_k)$보다 작거나 같고, 그 중 적어도 하나는 완전히 차지하지 않으면 Schedulable

 

결론 및 의의

1. BCL 테스트는 기존보다 더 현실적인 Schedulability 분석 도구
2. GFB는 Light Task에 효과적, BCL은 Heavy Task에 효과적
3. 제안된 BCL은 $O(n^2)$ 복잡도로 online admission control에서도 사용 가능
4. 추후 연구 방향: Busy-window 기반 Carry-in 추정 개선

 

Ref

[1] M. Bertogna, M. Cirinei, and G. Lipari, “Improved schedulability analysis of EDF on multiprocessor platforms,” in Proc. 17th Euromicro Conf. Real-Time Systems (ECRTS), Palma de Mallorca, Spain, Jul. 2005, pp. 209–218, doi: 10.1109/ECRTS.2005.25.