Improved schedulability analysis of EDF on multiprocessor platforms

석사 과정 3학기 차로, 현재 이창건 교수님의 실시간 시스템 수업을 수강 중입니다. 처음에는 다소 생소하고 낯설게 느껴졌던 내용들이었지만, 학기를 거치며 schedulability test, utilization bound, time demand analysis 등의 개념을 fixed priority와 dynamic priority 스케줄러 각각에 적용하는 방식들을 익히며 점차 익숙해지고 있습니다.

이번에는 학습한 내용을 확장하여, 멀티프로세서 환경에서는 schedulability 분석을 어떻게 수행할 수 있을까에 대한 고민을 담아보고자 합니다. 이를 위해 Bertogna et al.의 논문 "Improved Schedulability Analysis of EDF on Multiprocessor Platforms"를 바탕으로, 멀티코어 시스템에서 global EDF 스케줄러의 분석 방법과 그 한계, 그리고 실용적 접근 방식을 정리해보려 합니다.

Global EDF 스케줄러 하에서 기존의 GFB 및 BAK 테스트가 가지는 한계를 분석하고, 이를 보완하여 더 넓은 범위의 task set을 수용할 수 있는 새로운 schedulability test(BCL)를 제안한 논문입니다.

---

1. 연구 배경

최근 실시간 시스템에서도 멀티코어 기반의 SMP (Symmetric Multiprocessing) 플랫폼이 점점 더 일반화되고 있습니다. 단일 프로세서의 성능 향상이 정체된 상황에서, 여러 개의 프로세서를 하나의 칩에 집적한 멀티코어 구조는 전력 대비 성능 면에서 매우 효율적이기 때문입니다. 스마트폰, 자동차 제어장치, IoT 디바이스 등 다양한 분야에서 이러한 구조가 빠르게 확산되고 있으며, 실시간 제약이 요구되는 임베디드 시스템 또한 예외가 아닙니다.

이러한 환경에서 주목받는 스케줄링 방식이 바로 Global Scheduling입니다. Global Scheduling은 모든 프로세서가 하나의 공통된 ready queue를 공유하고, task를 실행 가능한 어떤 코어에나 자유롭게 할당할 수 있도록 합니다. 이는 processor 간 부하 분산(load balancing)을 자연스럽게 수행할 수 있고, task의 동적 생성 및 종료에 유연하게 대응할 수 있다는 장점이 있습니다.

하지만 여기서 문제가 발생합니다. 단일 프로세서 환경에서는 EDF (Earliest Deadline First)가 optimal한 스케줄러로 널리 알려져 있지만, 멀티프로세서 환경에서는 그 optimality가 무너집니다. 즉, 스케줄링이 가능함에도 불구하고, Global EDF는 특정한 task set에 대해 deadline miss를 발생시킬 수 있습니다. 이론적으로도 global EDF의 schedulability 판단은 NP-hard 문제이며, 특히 task migration에 따른 캐시 무효화, context switch 증가, 우선순위 왜곡 등의 부작용은 시스템의 실시간성을 위협할 수 있습니다.

이러한 이유로, 멀티프로세서 환경에서 Global EDF를 사용할 때는, 주어진 task set이 deadline을 만족하면서 실행될 수 있는지를 사전에 이론적으로 판단할 수 있는 schedulability test가 필요합니다. 이 논문에서는 대표적인 두 가지 테스트인 GFB (Goossens, Funk, Baruah)와 BAK (Baker) 테스트를 분석 대상으로 삼고, 이들의 장단점을 비교 평가하며, 새로운 개선안을 제안합니다.

GFB와 BAK는 서로 다른 현실의 문제를 반영하고자 한 두 가지 관점입니다. GFB는 단순성과 보편성을 택했고, BAK는 정밀성과 worst-case 보장을 택한 것입니다. 이 둘은 각각의 상황에 적합한 해법이 될 수 있지만, 서로를 완전히 대체할 수는 없습니다. 이 논문은 이러한 간극을 인식하고, 두 접근의 장점을 모두 흡수하는 새로운 분석(BCL test)을 제안하게 된 것입니다.

이러한 상반된 특성을 가진 GFB와 BAK는 각각 장점이 있으나, 둘 다 전체 task set을 충분히 포괄하지 못합니다. 따라서 논문에서는 이를 보완한 BCL test를 제안하여, 특히 heavy task가 포함된 환경에서도 보다 많은 schedulable task set을 수용할 수 있도록 분석 방법을 개선합니다.

---

2. 연구 목적 및 기여

두 가지 기존 test 분석:

• GFB (Goossens, Funk, Baruah)

Global EDF 스케줄링에서 가장 큰 어려움은, 단일 프로세서 환경처럼 task의 utilization만으로 schedulability를 간단히 판단할 수 없다는 데 있습니다. 특히 멀티코어에서는 task들이 서로 다른 core에 동적으로 배정되고, 때로는 동시에 실행되며, 심지어 migration까지 발생하므로 간단한 utilization 총합만으로는 실제 수행 가능 여부를 제대로 예측하기 어렵습니다.

이런 배경에서 등장한 것이 GFB test입니다. GFB는 “멀티코어 환경에서도 가급적 단순한 수학적 조건으로 schedulability를 판단할 수는 없을까?”라는 문제의식에서 출발했습니다. 그래서 전체 task set의 utilization 총합과, 가장 부하가 큰 task 하나의 utilization(Umax)을 함께 고려한 직관적이고 계산이 쉬운 부등식을 제안하게 된 것입니다. 이 방식은 특히 가벼운(light) task들로 구성된 시스템에서는 꽤 유용하게 작동하며, 빠른 판단이 필요한 시스템에서는 매력적인 선택지가 됩니다.

하지만 실제 시스템에서는 하나 이상의 heavy task(예: U > 0.5)가 포함되는 경우가 많고, GFB는 이러한 상황에서 Umax로 인해 bound가 급격히 낮아져 유효하지 않게 되는 경우가 많습니다. 이를 보완하고자 제안된 것이 바로 BAK test입니다.

• BAK (Baker)

BAK는 GFB의 한계를 인식하고, 보다 세밀한 분석을 시도합니다. "어떤 job이 deadline을 miss하려면, 그 직전 시간 구간에 얼마나 많은 간섭(interference)을 받아야 하는가?"라는 시나리오적 관점에서 출발하여, 각 task의 busy window에서 발생 가능한 최대 load를 추정합니다. 이를 통해 단순한 전체 utilization이 아닌 각 task별 worst-case 상황을 예측하게 됩니다.

이러한 접근은 heavy task가 포함된 상황에서는 더욱 현실적인 분석을 가능하게 해주지만, 그만큼 수식이 복잡하고 보수적입니다. 특히 간섭량(Interference), carry-in workload, overlapping window 등 여러 요소들을 일일이 고려하다 보니, 실제로는 schedulable한 task set임에도 불구하고 부정적인 판단을 내리는 경우도 있습니다.

교과서적이었던 오개념을 수정:

이전까지는 BAK 테스트가 보다 정교한 계산을 기반으로 하기 때문에, GFB 테스트가 통과하는 task set은 언제나 BAK도 통과할 것이라는 암묵적인 믿음이 있었습니다. 즉, BAK가 GFB보다 더 강력하고 보편적인 sufficient condition이라는 가정이었던 것입니다. 하지만 논문 저자들은 이에 대해 명확한 반례(counter-example)를 제시합니다.

개선된 테스트 새롭게 제안:

• BCL (Bertogna, Cirinei, Lipari)

실험을 통해 세 가지를 비교:

• 어떤 test가 어떤 조건(task 구성)에 더 잘 작동하는지

---

3. GFB 테스트

멀티코어(특히, Global EDF) 환경에서 주어진 task set이 deadline을 만족하며 스케줄 가능한지를 판단하는 것은 매우 어렵습니다. 단일 코어에서는 EDF가 optimal한 스케줄러이지만, 멀티코어에서는 그렇지 않기 때문에 새로운 분석 방식이 필요합니다. 이때 등장한 것이 GFB(Goossens, Funk, Baruah) 테스트입니다.

하지만 이 테스트는 단순히 경험적으로 제안된 것이 아니라, 멀티코어 스케줄링의 이론적 기반에서 출발한 정리들을 통해 유도됩니다. GFB 테스트는 총 4개의 Theorem으로 연결된 이론적 흐름을 따릅니다.

---

Theorem 1: Uniform Processor 환경에서의 Feasibility

"A periodic task system τ is feasible on a uniform multiprocessor platform π having total speed $S_\pi$ and max speed $s_\pi$ if certain speed bounds are met."

직관!

• 각 processor가 서로 다른 속도를 가질 수 있는 환경을 가정
• 각 task의 utilization을 해당 속도의 processor에 할당하면 schedulability가 보장됨
• 즉, task set 전체의 부하량을 processor 성능이라는 개념으로 재해석

왜 필요한가?

• 현실의 멀티코어는 반드시 동일한 core로 구성되어 있지 않음 (특히 embedded, DSP 등)
• scheduling 가능 여부를 부하 vs 성능이라는 관점으로 모델링하기 위한 출발점

---

Theorem 2: Uniform Processor → Symmetric Processor 변환

"If a task set is feasible on a uniform platform with total capacity $S_\pi$ and fastest processor speed $s_\pi$, then it is schedulable on an SMP with m unit-speed cores if:"

직관!

• uniform processor로부터 얻은 부하량이 있다면, 그 부하를 모두 처리하려면 몇 개의 동일 속도 core가 필요한가?
• 가장 빠른 core는 최대 부하 task를 담당하고, 나머지는 균등하게 나눠야 함

왜 필요한가?

• 실제 target은 SMP 시스템에서의 schedulability이므로, Theorem 1을 unit-speed core 기반으로 변환하는 논리적 다리 역할

---

Theorem 3: GFB Test의 기본 수식

"A periodic task set τ is EDF-schedulable on an SMP composed of m unit-capacity processors if:"

• $U_i = \frac{C_i}{T_i}$: task $\tau_i$의 utilization
• $U_{\max} = \max_i U_i$: 가장 무거운 task의 utilization
• $m$: processor 수

직관!

• 가장 무거운 task 하나가 core 하나를 독점한다고 가정하고,
• 나머지 $m - 1$개의 core가 남은 부하를 분산해서 처리 가능한지 계산
• “가장 나쁜 상황을 가정한 conservative bound”
  $m(1 - U_{\max}) + U_{\max} = \underbrace{(m - 1)(1 - U_{\max})}_{\text{남은 core들의 합산 여유}} + \underbrace{1}_{\text{Umax task 전용 core}}$

왜 필요한가?

• 복잡한 migration 분석 없이도, 단순한 수치 조건으로 schedulability를 빠르게 판단할 수 있음
• 실제로는 일부 task가 migration 가능하더라도 가장 보수적인 worst-case만 고려함

---

Theorem 4: GFB의 Constrained Deadline 확장

"A task set τ composed of periodic/sporadic tasks is EDF-schedulable on m unit-capacity processors if:"

• $\lambda_i = \frac{C_i}{D_i}$: deadline 기준 density
• $\lambda_{\max} = \max_i \lambda_i$

직관!

• deadline이 period보다 짧은 경우 (constrained deadline)에도 동일한 원리 적용
• 이때는 $U_i = \frac{C_i}{T_i}$ 대신 $\lambda_i = \frac{C_i}{D_i}$ 사용
• 가장 빨리 마감되는 task가 가장 높은 부하를 일으킬 수 있으므로, deadline 기준 density로 재정의

왜 필요한가?

• 실제 시스템에서는 $D_i < T_i$인 task가 흔함
• GFB 테스트를 보다 일반적인 task set에 적용 가능하도록 확장

---

GFB 테스트는 "하나의 core가 가장 무거운 task를 처리하는 데 전념한다면, 나머지 core들이 나머지 부하를 처리할 수 있는가?"를 수학적으로 표현한 것입니다. 이 접근은 단순하지만 보수적이며, 특히 가벼운 task set에서는 효과적이지만, heavy task가 포함되면 reject 확률이 높아지는 한계도 존재합니다.

그럼에도 불구하고 GFB 테스트는 멀티코어 실시간 시스템 분석에서 가장 계산이 단순하고 빠르게 적용 가능한 sufficient test로 여전히 널리 사용됩니다. 이 논문은 이러한 GFB의 수학적 기반과 실제 적용 가능성을 이론적으로 정교하게 정리한 대표적인 사례입니다.

---

4. BAK 테스트

GFB 테스트는 전체 부하와 가장 무거운 task 하나의 부하만을 고려하는 보수적 접근입니다. 반면, BAK(Baker) 테스트는 각 task에 대해 보다 세밀한 간섭 분석을 수행함으로써, 특히 heavy task가 포함된 task set에서 더 정확한 schedulability 판단을 가능하게 합니다. 이 테스트는 각 task가 deadline을 miss하지 않기 위한 조건을 개별적으로 계산하며, worst-case busy window에 집중합니다.

---

Theorem 5: BAK 테스트의 수식

"A task set τ composed of n tasks is schedulable with EDF on an SMP with m processors if, for every task $\tau_k$, the following holds:"

• $\lambda_k = \frac{C_k}{D_k}$: task $\tau_k$의 density
• $\beta_i$: task $\tau_i$가 task $\tau_k$에게 줄 수 있는 최대 간섭량 (interference bound)

---

직관!

• 이 수식은 task $\tau_k$의 deadline을 miss하기 위해서는 interval [r, d] 안에 얼마나 많은 간섭이 필요한지를 기반으로 분석합니다.

• 즉, 그 간섭량을 초과하는 부하가 도달하지 않으면, $\tau_k$는 반드시 deadline을 지킨다는 것을 보장하는 sufficient condition입니다.

• $\beta_i$는 각각의 다른 task $\tau_i$가 $\tau_k$에게 줄 수 있는 부하를 계산한 것이며, 그 값이 1을 넘을 경우에도 최대 1로 clip하여 계산합니다.

• 이 방식은 busy window 내에서 task 간의 간섭 상한선을 설정하는 구조입니다.

• $\beta_i$의 두 가지 경우

$\beta_i$는 $\tau_i$의 상대적 무게($U_i$)와 $\tau_k$의 처리 요구량($\lambda_k$)의 크기에 따라 두 가지 방식으로 정의됩니다.

경우 1: $\lambda_k \geq U_i$

$U_i = \frac{C_i}{T_i}$: task $\tau_i$의 평균 부하
$\left(1 + \frac{T_i - D_i}{D_k} \right)$: busy window 내에서 $\tau_i$의 job이 들어올 수 있는 횟수 추정치

여기서 $\frac{T_i - D_i}{D_k}$는 carry-in job이 겹쳐 들어올 수 있는 여지를 반영

즉, 이 수식은 "task $\tau_i$가 busy window에 job을 하나 이상 넣을 수 있을 때 그 task가 줄 수 있는 최대 간섭량"을 의미합니다.

이 경우는 $\tau_i$가 상대적으로 덜 무거운 task이므로, $\tau_k$가 간섭을 조금만 받아도 deadline miss가 발생할 수 있기에 conservative하게 간섭량을 추정합니다.

경우 2: $\lambda_k < U_i$

앞의 항은 경우 1과 동일합니다.
두 번째 항 $\frac{C_i - \lambda_k T_i}{D_k}$는 추가적인 간섭량을 보정하는 요소입니다.

• 이는 $\tau_i$가 매우 무거운 task이고, $\tau_k$보다 더 높은 평균 부하를 가지는 경우를 모델링한 것입니다.
• 단순 평균 부하만으로는 간섭량이 충분히 추정되지 않기 때문에, task burst (한 번에 몰아치는 실행)를 반영해야 하므로 보정항을 추가합니다.

이 상황에서는 $\tau_i$가 짧은 시간 안에 큰 부하를 발생시킬 수 있기 때문에, 그 영향력이 더 큼. 이를 모델링하기 위해 $\tau_i$의 실행 시간 중 $\tau_k$가 감당할 수 없는 초과분을 직접 보정항으로 포함시킵니다.

---

왜 필요한가?

• GFB는 단일 부등식 하나로 전체 task set의 schedulability를 판별하지만, heavy task에 매우 민감하여 실제 schedulable한 task set도 reject할 수 있음.
• BAK는 task마다 개별 조건을 적용하므로, 각 task의 worst-case busy window를 정확히 모델링할 수 있음.
• 특히 $U_{\max}$가 큰 상황에서도 불필요한 reject를 줄일 수 있다는 장점이 있음.

---

BAK 테스트는 GFB보다 복잡하지만 그만큼 정밀한 분석을 가능하게 하며, 특히 실시간성이 중요한 시스템에서 false negative를 줄이는 데 큰 기여를 합니다. 각 task의 busy window 내에서 발생 가능한 부하를 직접 추정함으로써, task 간 간섭의 구조적 특성을 반영한 현실적인 모델링이라 할 수 있습니다.

이 수식 역시 worst-case 기반의 sufficient condition이지만, GFB처럼 overly conservative하지 않고, 각 task의 deadline miss 가능성을 세밀하게 검증함으로써 더 많은 schedulable task set을 수용할 수 있습니다.

---

5. BCL 테스트 (Proposition) 개요

본 장에서는 Baker의 간섭 기반 EDF schedulability test를 수학적으로 계승하여, 실제 간섭량 계산의 어려움을 극복하고 보다 일반적인 작업 집합에 대해 schedulability를 판별할 수 있는 새로운 sufficient condition, 즉 BCL 테스트를 제안합니다.

---

5.1 문제 설정

시스템 모델은 다음과 같습니다.

• $m$개의 동등한 프로세서 (SMP)
• 작업 집합 $\tau = {\tau_1, \tau_2, \dots, \tau_n}$, 각 작업 $\tau_k = (C_k, D_k, T_k)$
• $C_k$: 최대 실행 시간 (WCET), $D_k$: 상대 데드라인, $T_k$: 주기 또는 최소 도착 간격
• 각 작업의 utilization $U_k = \frac{C_k}{T_k}$, 요청률 $\lambda_k = \frac{C_k}{D_k}$

EDF는 work-conserving 알고리즘이므로, 특정 시간 구간 $[a, b]$에서 $\tau_k$가 ready 상태임에도 실행되지 못한 총 시간 (interference $I_k(a, b)$)은 반드시 다른 작업들이 CPU를 점유하고 있는 구간과 일치합니다.

---

5.2 간섭 기반 필요조건과 Lemma 3

어떤 작업 $\tau_k$의 job $J_k^j$가 데드라인 $d_k^j$을 놓쳤다면, 다음이 반드시 성립해야 합니다:

즉, 해당 작업이 실행되지 못한 시간 $I_k$가 slack 시간보다 클 경우에만 데드라인 미스가 가능합니다.

이 때 $I_k$는 $m$개의 프로세서에서 동시에 실행 중이던 다른 작업들로 인한 간섭이며,

이며, $I_{i,k}(a, b)$는 $\tau_i$가 실행 중이고 $\tau_k$는 ready 상태였던 시간의 합입니다.

---

5.3 Lemma 4: min-sum 조건식, Theorem 6: 간섭 기반 스케줄러 조건

Lemma 4: min-sum 조건식
이러한 $I_k$에 대해 다음과 같은 등가 조건이 제시됩니다:

이는 각 작업 $\tau_i$가 $\tau_k$에게 주는 간섭 $I_{i,k}$이 임계값 $x$를 초과하는지 여부에 따라, 전체 평균 간섭 $I_k$가 $x$ 이상인지 판단할 수 있다는 주장입니다. 이를 통해 직접 계산이 어려운 $I_k$를 $\min(I_{i,k}, x)$의 합으로 변환하여 분석이 용이한 조건으로 환원할 수 있게 됩니다. (Global Scheduling 가정에 따른 정리)

Theorem 6 (간섭 기반 스케줄러 조건)
작업 집합 $\tau$가 EDF 스케줄러 하에서 스케줄 가능하기 위한 조건은 다음과 같습니다:

---

• 이 정리는 “간섭의 총합이 slack보다 작으면 schedulable하다”는 아주 자연스러운 조건입니다. Lemma 4를 활용해 증명합니다.
• 즉, $\tau_k$가 deadline을 지키려면 그 job이 ready 상태인데도 실행되지 못하는 시간(=간섭)이 slack보다 작아야 한다는 것.

---

5.4 실제 간섭 계산의 어려움

모든 $\tau_i$에 대해 $I_{i,k}(a,b)$를 정확히 계산하는 것은 $\tau_i$의 도착 간격, deadline alignment, carry-in을 포함하는 복잡한 문제입니다. 이에 따라 간섭의 상계를 workload $W_i(a,b)$로 대체합니다:

---

5.5 Carry-in 및 workload 상계

Carry-in $\epsilon_i(a,b)$는 $\tau_i$의 job이 $[a,b]$ 시작 전에 도착했지만 아직 끝나지 않은 잔여 실행 시간입니다.

상계는 다음과 같이 주어집니다:

따라서 workload의 상계는 다음과 같습니다:

---

5.6 BCL Test: 최종 스케줄러 조건

Workload를 데드라인 길이 $D_k$로 정규화하여 각 작업에 대해 interference load를 정의합니다:

이 때, $\lambda_k = \frac{C_k}{D_k}$를 이용하여 다음과 같은 schedulability condition을 유도한다.

Theorem (BCL Schedulability Test)
작업 집합 $\tau$는 EDF 스케줄러 하에서 $m$개의 프로세서 상에서 스케줄 가능하다, 만약 $\forall \tau_k \in \tau$에 대해 다음 중 하나가 성립하면:

---

5.7 의의

• 본 테스트는 BAK의 정밀도와 GFB의 단순함 사이의 절충안으로, carry-in 및 slack 기반 상계 추론을 통해 계산 가능하고 보수적이지 않은 sufficient condition을 제시합니다.
• 특히 $\min(\beta_i, 1 - \lambda_k)$ 조건은 heavy task의 간섭 기여를 보수적으로 제한함으로써 schedulability를 개선합니다.
• GFB는 주로 light task에 유리하며, BCL은 heavy task를 포함하는 실용적 작업 집합에 대해 우수한 성공률을 보입니다.

---

6. GFB/BAK/BCL의 비교

항목	GFB	BAK	BCL
분석 방식	전체 load + 최대 task만 고려	각 task의 busy window load	busy window load + 간섭 clip (slack-aware)
수식 구조	단일 부등식	각 task별 부등식 (n개)	각 task별 부등식 (n개)
간섭 clip	없음	$\min(1, \beta_i)$	$\min(1 - \lambda_k, \beta_i)$
heavy task 대응	매우 취약	중간	가장 효과적
계산 복잡도	O(n)	O(n²)	O(n²)
실험 성능	light task에 유리	혼합 task에 보통	전반적으로 가장 우수함

7. 실험 비교

조건	결과 요약
Light task만 있는 경우	GFB가 가장 높음
Heavy task 1~2개 포함	BCL 우세
Heavy task 3개 이상	GFB, BAK 모두 fail → BCL만 통과

---

8. 느낀 점

멀티코어 환경에서는 아직 단일 코어처럼 완전한 수학적 해법(필요충분 조건)이 존재하지 않습니다. GFB나 BCL 같은 테스트는 보수적인 충분조건에 불과하며, 실용적으로는 온라인 필터나 사전 검증 도구 정도로 사용됩니다. 실제 스케줄링 가능 여부를 판단하려면 결국 시뮬레이션 기반의 분석이 병행되어야 합니다. 이 논문은 GFB와 BAK의 한계를 짚고, 그 사이에서 절충점을 찾으려는 실용적 접근의 예로 볼 수 있습니다.