Response-Time Analysis for globally scheduled Symmetric Multiprocessor Platforms

1. 논문 개요:

현대의 실시간 시스템은 더 이상 단일 프로세서 위에 존재하지 않습니다. 멀티코어 환경에서 태스크들이 병렬로 실행되며, 특히 Symmetric Multiprocessor (SMP) 시스템에서는 글로벌 스케줄링이 주요한 운영 전략으로 자리잡고 있습니다.

Global Scheduling이란 여러 개의 프로세서(m cores)가 하나의 공통된 ready queue(대기열)를 공유하며, 우선순위에 따라 태스크를 동적으로 실행하는 스케줄링 방식입니다.

이 논문은 멀티프로세서 환경(Global Scheduling)에서의 정확한 응답시간 분석(Response Time Analysis, RTA)을 통해, 기존 분석 기법들의 한계를 극복하고보다 많은 작업 집합(Task Set)이 스케줄 가능하다는 것을 입증합니다.

기존의 글로벌 스케줄링 기반 분석에서는 RTA가 제대로 동작하지 않거나 과도하게 보수적이어서 실제 스케줄 가능한 작업들도 탈락하는 경우가 많았음.

• Uniprocessor RTA에서는 "Critical Instant"를 기반으로 응답시간 상한을 계산함.
• 그러나 멀티프로세서에서는 간섭(interference)의 양상이 훨씬 복잡하며, 기존 방식은 이를 과도하게 단순화했음.
• 특히, carry-in/out을 모두 최악값(WCET)으로 가정하면 많은 작업 집합이 "스케줄 불가"로 잘못 판정됨.

---

이 논문의 contribution은 아래와 같습니다.

1. 멀티프로세서 글로벌 스케줄링에서의 새로운 RTA 알고리즘 제안

   • Earliest Deadline First (EDF)와 Fixed Priority (FP)에 모두 적용 가능

2. 인터페어런스(간섭)와 워크로드를 정밀하게 정의

   • carry-in, carry-out을 포함한 workload 상한을 계산
   • slack 정보를 반영한 반복적 고정점 계산 방식 사용

3. 실험적으로 수십만 개의 작업 집합을 통해 검증

   • 기존 GFB, BAK, BCL 등의 분석법보다 월등한 스케줄 검출 능력

4. Fixed Priority가 오히려 EDF보다 우수한 결과를 보이는 구간 확인

   • 간섭 계산 시 낮은 우선순위 작업을 배제할 수 있는 점 활용

---

2. Interference와 Workload: 간섭과 작업량의 정량적 정의

글로벌 스케줄링 환경에서는 여러 태스크가 동시에 실행을 대기하고, 프로세서 수보다 많은 태스크가 ready 상태일 수 있습니다. 이때 어떤 태스크가 실행 가능한 상태임에도 불구하고 다른 태스크 때문에 실행되지 못하는 시간, 즉 간섭(interference)과, 실제로 요구되는 연산량(workload)을 정확히 계산하는 것이 핵심입니다.

---

Notation

기호	의미
$\tau_k$	분석 대상 태스크
$[a, b)$	분석 구간
$m$	프로세서 수
$C_k$	태스크 $\tau_k$의 WCET
$W_k(a, b)$	해당 구간에서 $\tau_k$의 Workload
$I_k(a, b)$	해당 구간에서 $\tau_k$의 Interference

---

Interference $I_k(a, b)$

작업 $\tau_k$가 실행은 가능한 상태(ready)인데, 동시에 실행 중인 $m$개의 더 높은 우선순위 작업들 때문에 실행되지 못한 누적 시간.

• 직관적으로, 프로세서가 모두 바빠서 내가 못 들어가는 시간의 총합
• 이 간섭 시간 동안 $\tau_k$는 backlogged 상태 (대기 중)

$I^i_k(a, b)$

• 태스크 $\tau_i$가 $\tau_k$에 유발한 간섭
• 즉, $\tau_k$가 blocked 상태일 때 실제로 $\tau_i$가 실행 중이었던 시간
• $I^i_k(a, b) \le I_k(a, b), \quad \forall i \ne k$

---

Workload $W_k(a, b)$

해당 구간 $[a, b)$에서 $\tau_k$가 요구하는 연산량

Workload는 3부분으로 나뉩니다:

1. Body:

   • 구간 안에서 release & deadline 모두 포함되는 job들
   • 이 job들은 완전한 WCET $C_k$ 만큼 수행

2. Carry-in:

   • 구간 이전에 release,구간 안에 deadline이 있는 job
   • 이 job은 해당 구간에서 일부 수행됨
   • 수행량: $\varepsilon_k$

3. Carry-out:

   • 구간 내에 release, 구간 이후에 deadline이 있는 job
   • 이 job도 해당 구간에서 일부만 수행됨
   • 수행량: $z_k$

따라서, 전체 workload는 다음과 같이 구성됩니다:
$W_k(a, b) = \varepsilon_k + (N \cdot C_k) + z_k$

이후 Theorem 2~4는 이 관점을 기반으로 RTA 수식에서 간섭을 보수적으로 upper bound하는 데 사용됩니다. 한편, 이 논문에서는 실시간 시스템의 현실적인 동작을 반영하기 위해 시간을 연속적인 실수 단위가 아닌, 정수 단위의 클럭 틱으로 모델링합니다. 즉, 시간 값 $t$는 실제로는 구간 $[t, t+1)$을 의미하며, 이는 시스템의 가장 정밀한 클럭 주기 수준에서 이벤트가 발생한다는 가정을 반영한 것입니다. 이러한 정수 시간 모델은 수학적 귀납법을 적용할 수 있게 해주며, 응답시간 계산에서 고정점 반복이 유한한 횟수 내에 수렴하도록 보장합니다. 결과적으로, 이 가정은 실시간 응답시간 분석의 정확성, 현실성, 계산 종료성을 모두 확보하는 데 핵심적인 역할을 했습니다.

---

3. Lemma 및 Theorem

Theorem 1 (기존 FP 기반 멀티코어 RTA 수식)

고정 우선순위 글로벌 스케줄링 환경에서, 태스크 $\tau_k$의 응답시간 상한 $R^{\max}_k$은 다음과 같은 고정점 반복으로 계산됩니다:
$R^{\max}_k \leftarrow C_k + \frac{1}{m} \sum_{\tau_j \in hp(k)} \left( \left\lceil \frac{R^{\max}_k}{T_j} \right\rceil C_j + C_j \right)$

carry-in/out을 모두 WCET으로 보수적으로 추정한 기존 방식으로, 실제보다 과도하게 큰 응답시간을 유도할 수 있습니다.

---

Theorem 2 (Interference $\le$ Workload)

임의의 태스크 $\tau_i$가 $\tau_k$에게 주는 간섭은, 그 태스크의 해당 구간 내 워크로드를 넘을 수 없습니다: $I^i_k(a, b) \le W_i(a, b)$

간섭은 오직 $\tau_i$가 실행 중일 때만 발생할 수 있고, 실행량은 최대 워크로드 $W_i$를 넘지 못하므로 성립합니다.

---

Lemma 1 (간섭 총합의 하한 조건)

$I_k(a, b) \ge x \iff \sum_{i \ne k} \min(I^i_k(a, b), x) \ge m x$

총 간섭량이 $x$ 이상이려면, 동시에 실행 중인 다른 태스크들의 간섭이 합쳐서 그만큼 되어야 합니다. $m$개 CPU 중 1개는 $\tau_k$가 쓸 수 없으므로, 나머지 $m$개의 태스크가 총합 $mx$만큼은 간섭해야 $\tau_k$에게 $x$만큼 간섭이 들어갈 수 있음

---

Theorem 3 (응답시간 상한 조건)

어떤 값 $R^{ub}_k$이 다음 부등식을 만족한다면 $\tau_k$의 응답시간 상한으로 사용 가능:
$\sum_{i \ne k} \min(I^i_k(r_k^*, r_k^* + R^{ub}_k), R^{ub}_k - C_k + 1) < m (R^{ub}_k - C_k + 1)$

간섭량이 $R^{ub}_k - C_k + 1$ 이상이면, 최소한 $C_k$ 만큼의 연산을 완료하지 못한다는 것과 Lemma 1을 활용해 부등식을 증명할 수 있습니다.

---

Theorem 4 (Workload 상한 계산)

길이 $L$의 구간에서 $\tau_i$의 워크로드 상한은:
$W_i(L) = N_i(L) C_i + \min(C_i, L + D_i - C_i - N_i(L) T_i)$

여기서:
$N_i(L) = \left\lfloor \frac{L + D_i - C_i}{T_i} \right\rfloor$

Body: $N_i(L) C_i$

• 분석 구간 $[a, a+L)$ 안에서 완전히 포함된 작업들의 수를 셈.

• 즉, release 시간도 deadline도 모두 구간 안에 있는 작업들.

• 이 작업들은 $C_i$만큼 전부 구간 내에서 실행됨 → 정확하게 워크로드로 포함됨.

• 작업 주기가 $T_i$이고, 구간 길이가 $L$이므로, 그 안에 최대 몇 개의 full job이 들어오는지 계산:

  $N_i(L) = \left\lfloor \frac{L + D_i - C_i}{T_i} \right\rfloor$

  이 식은 슬랙과 정렬을 고려한 conservative bound입니다.

Carry-in: (암묵적으로 포함됨)

• 구간 전에 release되었지만 아직 끝나지 않은 job이 있을 수 있음
• 이 job은 구간 안에서 일부 또는 전부 수행될 수 있음
• 사실 carry-in job은 body 계산의 기준점을 조정하는 데 간접적으로 반영됨
• 위의 $N_i(L)$ 계산식은 carry-in job 이후부터 몇 개가 나오는지를 포함함

---

Carry-out: $\min(C_i,\ L + D_i - C_i - N_i(L) T_i)$

• 구간 안에 release되었지만, deadline은 구간 밖인 job
• 구간 내에 일부만 실행됨 → 전체 $C_i$가 아니라 남은 시간만큼만 계산
• 구간 내에 실행된 양은 최대 $C_i$지만, 남은 시간보다 클 수는 없음
• 따라서 구간에 남은 시간과 $C_i$ 중 작은 값을 취함

---

분석 구간 $L$ 동안,

• 완전한 job이 $N_i(L)$개 존재하고,
• 끝나지 않은 job이 최대 1개, 시작은 되었지만 끝나지 않은 job도 최대 1개,
  이 모든 걸 고려해서 태스크가 요구할 수 있는 최대 실행량을 보수적으로 합산한 결과가 $W_i(L)$이다.

---

Theorem 5 (EDF 간섭 상한 수식)

where

• $\mathcal{J}^i_k(D_k)$ : task $\tau_i$가 $\tau_k$에게 $D_k$ 길이 구간에서 주는 간섭량 상한
• $\text{DBF}^i_k$: deadline-bound job들의 누적 실행량
• $\frac{T_i}{C_i}$: 하나의 job이 주기를 기준으로 얼만큼 시간에 해당하는지를 역으로 환산하는 간접적 scaling factor
  → 사실상 job 개수를 시간 기준으로 환산해 residual carry-in을 구하려는 식입니다

• body는 DBF로, carry-in은 추가 연산량으로 나타남. 단, 이 식은 $[a, b) = [r_k, r_k + D_k)$인 경우에만 사용 가능.

---

Theorem 5는 간섭을 분석하는 구간을 딱 $[r_k, r_k + D_k)$ 로 고정하고,
해당 구간에 deadline이 포함되는 job들만 간섭 가능하다는 점을 이용한 EDF-specific worst-case 분석입니다. 즉, EDF에서는 간섭의 우선순위가 deadline에 따라 정해집니다. $\tau_i$가 $\tau_k$보다 더 빠른 deadline을 갖고 있어야 간섭 가능합니다. 따라서 release 시점보다 deadline이 더 간섭 조건에 중요합니다.

---

Theorem 6 (EDF 시스템에서의 응답시간 상한 반복 수식)

EDF 기반 글로벌 스케줄링 시스템에서 태스크 $\tau_k$의 응답시간 상한 $R_k^{ub}$는 다음 고정점 반복 수식을 통해 구할 수 있습니다:

---

정의 및 기호

• $C_k$: 태스크 $\tau_k$의 WCET (최악 실행 시간)

• $m$: 프로세서 수

• $W_i(R)$: 길이 $R$의 구간에서 $\tau_i$가 요구할 수 있는 최대 워크로드 (Theorem 4):

  $W_i(R) = N_i(R) \cdot C_i + \min\left(C_i,\ R + D_i - C_i - N_i(R) \cdot T_i\right)$
  $N_i(R) = \left\lfloor \frac{R + D_i - C_i}{T_i} \right\rfloor$

• $\mathcal{J}^i_k(D_k)$: 간섭 상한 (Theorem 5), $\tau_i$가 $\tau_k$에게 $D_k$ 길이의 구간 내에서 줄 수 있는 최대 간섭:

  $\mathcal{J}^i_k(D_k) = \text{DBF}^i_k + \min\left(C_i,\ \max\left(0,\ D_k - \text{DBF}^i_k \cdot \frac{T_i}{C_i} \right)\right)$
  $\text{DBF}^i_k = \left( \left\lfloor \frac{D_k - D_i}{T_i} \right\rfloor + 1 \right) \cdot C_i$

• $R_k^{ub} - C_k + 1$: $\tau_k$가 실행되지 못하고 백로그 상태에 있는 최대 간섭 허용 시간

---

직관

• 이 수식은 태스크 $\tau_k$가 응답시간 $R_k^{ub}$ 이내에 완료되기 위해, 다른 태스크들로부터 받는 간섭량이 프로세서 수 m으로 감당 가능한지를 확인하는 방식입니다.

• 각 태스크 $\tau_i$의 간섭량은 세 가지 보수적 upper bound 중 가장 작은 값을 선택합니다:

  1. $W_i(R_k^{ub})$: 워크로드 기반 상한
  2. $\mathcal{J}^i_k(D_k)$: EDF 특화 간섭 상한
  3. $R_k^{ub} - C_k + 1$: 최대 간섭 허용량

---

증명을 아래와 같이 스케치해볼 수 있습니다.

[1] 시작점: Theorem 3 (간섭 총합 조건)

다음 조건이 성립하면 $R_k^{ub}$는 태스크 $\tau_k$의 응답시간 상한입니다:

• 좌변: $\tau_k$가 백로그 상태일 때 실제 간섭을 받는 시간
• 우변: $m$개의 CPU가 간섭을 처리할 수 있는 시간량

---

[2] 간섭 상한 대체 (Theorem 2, 4, 5 활용)

• 실제 간섭 $I^i_k$는 계산이 어렵기 때문에, 다음 conservative한 upper bound를 사용합니다:

• 즉, 간섭이 실제로 발생할 수 있는 최대량을 안전하게 과대 추정하는 방식

---

[3] 고정점 반복 수식 구성

이러한 conservative한 간섭 상한을 바탕으로 Theorem 3의 좌변을 보수적으로 평가하면:

이 값을 $m$으로 나눈 후 $C_k$를 더해, 새로운 $R_k^{ub}$를 갱신하는 반복 수식을 구성합니다:

---

• 이 수식은 단조 증가 혹은 일정한 수열을 생성하며, 값이 정수이므로 유한한 반복 후 반드시 수렴합니다.
• 반복 종료 시 $R_k^{ub} \le D_k$이면 태스크는 schedulable합니다.
• 이는 Theorem 3이 제시한 조건을 반복적으로 만족시키는 가장 작은 $R_k^{ub}$를 탐색하는 과정입니다.

---

Theorem 7 (Fixed Priority 시스템에서의 응답시간 상한 반복 수식)

고정 우선순위(Fixed Priority) 기반 글로벌 스케줄링 시스템에서, 태스크 $\tau_k$의 응답시간 상한 $R_k^{ub}$는 다음 고정점 반복으로 계산할 수 있습니다:

• $i < k$: 우선순위가 $\tau_k$보다 높은 태스크만 간섭을 줄 수 있음
• $W_i(R)$: 구간 내 $\tau_i$의 워크로드 upper bound
• $R_k^{ub} - C_k + 1$: $\tau_k$가 백로그 상태일 수 있는 최대 간섭 허용 시간
• 두 항의 최소값을 통해 간섭량을 안전하게 상한함
• $\mathcal{J}^i_k$는 EDF 스케줄링에 특화된 간섭 상한으로,
  우선순위가 아닌 deadline 기반 간섭 모델을 전제로 함
• FP 시스템에서는 간섭 여부가 우선순위만으로 결정되기 때문에,
  굳이 $\mathcal{J}^i_k$ 같은 job-count 기반 상한을 도입할 필요가 없음

항목	Theorem 6 (EDF)	Theorem 7 (FP)
간섭 대상	모든 $i \ne k$	$i < k$ (우선순위 상위)
사용 bound	$W_i(R), I^i_k(D_k)$	$W_i(R)$
조건 기반	Theorem 3 + 2 + 4 + 5	Theorem 3 + 2 + 4
수렴 방식	고정점 반복	고정점 반복
장점	EDF의 정확한 간섭 반영	빠른 수렴, 더 tight

---

4. Slack-Aware RTA

슬랙을 고려하여 간섭량을 줄일 수 있습니다.

• 태스크 $\tau_i$의 슬랙 $s_i$는 다음과 같이 정의:

• 이 말은 “$\tau_i$는 deadline보다 실제로 $s_i$만큼 더 일찍 끝남” → 간섭 여지가 줄어듦

→ 따라서 이전 Theorem 4/5에서 등장한 workload, interference bound 식을 slack-aware하게 수정 가능

---

수정된 workload bound (슬랙 반영):

기존에는:

슬랙-aware하게 바꾸면:

• $s_i$만큼 더 일찍 끝나므로, carry-out job의 실행 여지가 줄어듦

• 이로 인해 $\tau_i$의 간섭량 upper bound가 작아지고 → $\tau_k$의 응답시간 upper bound도 작아짐

---

수정된 interference bound (EDF 전용 $\mathcal{J}^i_k$ 개선):

기존:

슬랙-aware 개선:

→ 즉 carry-in 간섭량도 줄어듦

---

Slack-aware 반복 구조

• 슬랙은 모든 태스크의 응답시간 $R_i^{ub}$이 구해져야만 계산 가능

• 그러므로 slack-aware RTA는 한 번 더 반복 수행:

  1. 초기 반복에서 모든 $R_k^{ub}$ 계산
  2. 각 태스크의 slack $s_k = D_k - R_k^{ub}$ 계산
  3. 이 slack을 반영한 간섭 bound로 다시 RTA 반복 수행
  4. 반복하며 갱신된 slack이 반영됨

계산 복잡도

• 각 반복에서 $R_k^{ub}$는 정수 단위로 증가

• 따라서 단일 태스크에 대해 최대 $D_k - C_k$회 반복

• 모든 태스크에 대해 반복 → 전체 복잡도는 $\mathcal{O}(n^2 D_{\max})$ 수준

• 슬랙 기반 반복을 적용할 경우 한 단계 더 반복되므로:

  • 전체 복잡도: $\mathcal{O}(n^3 D_{\max}^2)$ 정도로 증가

→ Pseudo-polynomial time이지만, 실험적으로는 수 초 이내 수천 개 태스크셋 평가 가능

• slack은 단지 응답시간 분석 결과의 부산물이 아님
• 시스템의 robustness 또는 동작 여유 시간을 측정하는 척도로 사용 가능
• 예: slack이 충분하다면 클럭 속도를 낮춰 전력 절감 가능

---

5. 실험 결과

실험 세부사항

• Task 수: 100만 세트
• 평균 Utilization: 0.25
• Platform: m=2, m=4
• 알고리즘: EDF vs FP, 테스트 종류: RTA, GFB, BAK, BCL, DB 등

---

조건	RTA 결과
EDF (m=2)	GFB/BAK/BCL보다 항상 우수
FP (DM, m=2)	EDF-RTA보다 더 많은 schedulable set 탐지
m=4	FP-RTA의 성능이 더욱 두드러짐

• RTA는 기존 수식 기반 테스트보다 훨씬 더 정밀하다.
• FP (Fixed Priority) 가 Global EDF보다 schedulability 관점에서는 유리할 수 있음
  → 이유: interference 계산 시 lower-priority 작업 무시 가능
• Slack을 반영한 반복 최적화가 실제 실시간 시스템의 안정성/전력효율성까지 연결될 수 있다.

---

6. 마치며

이전에 다뤘던 BCL 분석은 글로벌 EDF에서 간섭량을 carry-in task 수로 제한해 간단한 조건으로 schedulability를 빠르게 판단할 수 있도록 한 보수적인 방법입니다. 반면, RTA-G는 간섭을 시간 구간 내 carry-in, body, carry-out으로 분해하고 각 태스크에 대해 고정점 반복으로 응답시간 상한을 계산함으로써 훨씬 정밀하고 tight한 분석을 제공합니다. 즉, BCL은 빠르고 간결한 시스템 레벨 테스트에 적합하고, RTA-G는 태스크별 slack 분석이나 응답시간 기반 최적화에 유리한 per-task 정밀 분석 기법입니다.