Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms

느낀점

 

• 이 논문은 멀티프로세서 실시간 시스템에서의 응답시간 분석의 복잡성과 한계를 뛰어넘기 위한 정교한 수학적 모델을 제시했다는 점에서 인상 깊었다.
• 간섭과 워크로드를 정량적으로 상한 처리하며 반복적으로 응답시간을 수렴시키는 방식은 논리적이고 적용 가능성도 높다고 느꼈다.
• 특히 slack을 활용해 분석 정확도를 점진적으로 높이는 방식은 단순한 이론을 넘어서 실용적인 해법임을 보여준다.

 

Problem Statement

멀티프로세서 하에서 Real Time Scheduling 분석의 근본적인 문제가 무엇일까? 

(논문 발행 기준으로) 최근 몇 년 동안 일반 및 임베디드 시스템 시장에서 단일 프로세서 칩에서 멀티코어 컴퓨팅 장치로 점진적인 전환이 일루어졌다. 이러한 추세에 따라 실시간 커뮤니티에서는 고전적인 스케줄링 분석 기법을 병렬 컴퓨팅 시스템에 적용하는 연구 결과가 증가했다. 그러나 다중 프로세서 시스템의 내재적인 복잡성으로 인해 분석의 복잡성이 증가한다. 

실시간 스케줄링을 다중 프로세서에서 분석하는데 따르는 근본적인 과제는 아래와 같다. 

• 단일 프로세서 기법의 확장 어려움: RTA(Real Time Analysis)와 같은 단일 프로세서에서 널리 사용되는 효과적인 기법을 다중 프로세서 시스템에 그대로 적용하는 것은 여러 가지로 어려움이 있다. 기존의 전역 스케줄링 다중 프로세서 시스템에 RTA를 적용하려는 소수의 시도는 단일 프로세서 기법을 일반화하려는 초기 시도에 불과했다.
• Worst Case Scenario 식별 문제(Critical Section 부재): 단일 프로세서 시스템에서는 모든 Task가 동시에 활성화되는 경우가 종종 Critical Section으로 간주되어 WCRT을 찾을 수 있었다. 그러나 다중 프로세서에서는 동기화된 상황이 최악이 아닐 수 있으며, 심지어 Task의 도착 간격을 늘리면 시스템이 실행 불가능해지는 상황(Anomalies)도 발생할 수 있다. 이로 인해 최악의 경우 Deadline이 충족되는지 확인할 수 있는 "대표적인" 간격을 찾는 것이 쉽지 않다. 
• Computational Complexity: 다중 프로세서 플랫폼에서는 시스템을 시뮬레이션하거나 Task의 모든 가능한 합법적인 도착 상황을 확인하지 않고는 Task의 최악의 행동을 찾는 것이 쉽지 않다. 
• Interference 및 Workload 추정의 어려움: 다중 프로세서 플랫폼에서 동시에 실행되는 Task간의 상호 작용을 분석하기 위해 Interference 및 Workload와 같은 개념이 사용된다. 단일 프로세서 경우와 달리, 제한된 Computational effort로 모든 Interference나 Workload의 정확한 값을 도출하는 것은 쉽지 않다. 따라서 분석을 위해 일반적으로 Workload나 Interference에 대한 Upper Bound를 사용하게 된다. 
• 이론의 미완성: 문제의 복잡성과 차원 때문에 다중 프로세서 시스템의 실시간 스케줄링에 대한 완전한 이론은 아직 확립되지 않았다. 
• 기존 테스트의 효율성: 기존의 다중 프로세서 스케줄 가능성 테스트, 특히 전역 스케줄링의 경우, 파티션된 시스템을 위해 테스트나 단일 프로세서 기법에 비해 효율성이 떨어지는 경향이 있다. 

Workload를 분석하는데 무엇이 사용되는가?

다중 프로세서 환경에서 실시간 스케줄링 분석을 수행할 때 Workload는 Task들이 동시에 실행될 때 상호작용을 분석하는데 사용되는 핵심 Parameter 중 하나이다. Workload는 Interference와 함께 사용된다.

Task $\tau_k$의 특정 시간 간격 $[a,b)$에서의 Workload $W_k(a,b)$는 해당 간격동안 Task가 요구하는 계산량(Amount of Computation)을 나타냈다. 이 Workload는 다음 3가지 기여 요소를 고려하여 정의한다.

1. Body: 간격 $[a,b)$ 내에 Release 시간과 Deadline을 모두 가지는 모든 Job의 기여분이다. 각 Job은 전체 Worst Case Execution Time($C_k$)으로 기여한다. 
2. Carry-In: 'a' 시점 이전에 Release되었지만 Deadline이 $[a,b)$내에 있는 최대 하나의 Job의 기여분이다. 이 Job은 해당 간격이 $[a,b)$ 내에서 실제로 실행된 시간의 일부분 $\varepsilon_k$으로 기여한다. 
3. Carry-Out: $[a,b)$ 시점 이전에 Release되었지만 Deadline 'b' 시점 이후에 있는 최대 하나의 Job의 기여분이다. 이 Job은 해당 간격 $[a,b)$ 내에서 실제로 시간의 일부분 $z_k$으로 기여한다.

다중 프로세서 환경에서는 Interference나 Workload의 정확한 값을 제한된 Computational effort로 도출하는 것이 쉽지 않다. 따라서 시스템을 시뮬레이션할 필요 없이 분석을 진행하기 위해 Workload의 Upper Bound가 일반적으로 사용된다.

논문에 제시된 새로운 분석 방식에서는 Task $\tau_i$의 길이 L인 일반적인 간격 $[a,b)$에서의 Workload에 대한 Upper Bound $W_i(L)$을 계산하는 방법이 제시된다. 이 Upper Bound 계산은 어떤 스케줄링 알고리즘이 사용되는 유효하며, Task의 Worst Case Execution Time $C_i$, Deadline $D_i$, Period 또는 Least Arrival Interval $T_i$ 및 Interval의 Length $L$를 기반으로 한다. 이 분석에서는 Interference Task에 대해 이전에 계산된 Slack 값을 포함하여 이 Workload Upper Bound estimated value를 개선할 수도 있다.

이러한 Workload에 대한 Upper Bound estimated value는 RTA(Real Time Analysis)에서 Task의 Worst Case Response Time을 계산하고 시스템의 스케줄 가능성을 판단하는데 활용된다.

다양한 Global 실시간 스케줄링 알고리즘 간의 Performance Trade-Off는 어떤 것이 있는가?

단일 프로세서 칩에서 멀티코어 장치로 점진적으로 전환되면서, 실시간 시스템 커뮤니티는 고전적이니 스케줄링 분석 기법을 병렬 컴퓨팅 시스템에 적용하는 연구를 활발히 진행하고 있다. 다중 프로세서 환경에서 시스템 전체의 단일 스케줄링 Queue를 유지하는 Global Scheduling Algorithm은 사용 가능한 CPU에서 Task 동적으로 실행한다. 

1. Global Scheduling vs. Partitioned Scheduling (일반적인 비교):

• 평균 성능: Global Scheduler는 일반적으로 단일 Queue를 사용하여 Work-Conserving 방식으로 동작하므로 평균 응답 시간이 Partitioned System보다 낮다. Partitioned System은 부하 분산이 불균형할 경우 프로세서가 유휴 상태가 될 수 있다. Partitioned System의 평균 Preemption 횟수도 Global Schedule System보다 일반적으로 높다.
• Worst Case Performance & Schedulability: Global 방식과 Partitioned 방식 중 한 방식이 압도하지는 않는다. 즉, Partitioned Solution으로만 스케줄 가능한 Task Set와 Global Scheduler를 사용해야만 스케줄 가능한 Task Set이 존재한다. 역사적으로 Partion System에 대한 Schedulability Test는 단일 프로세서 기법에 의존하기 때문에 더 효율적이었다. 이 논문은 Global Schedulability Analysis의 효율성을 개선하는데 기여한다. 

2. Global Scheduling Algorithms 내의 비교:

• EDF(Earliest Deadline First) vs. FP(Fixed Priority):
  • 증명 가능한 Schedulability (본 논문의 RTA 기반): 이 논문에서 제시하는 새로운 RTA 기반 테스트는 Fixed Priority (특히, DM, Deadline Monotonic) 스케줄링이 EDF 스케줄링보다 더 많은 수의 Task Set를 스케줄 가능하다고 증명할 수 있음을 보여준다. 이러한 결과는 프로세서 수가 증가할 수록 더욱 두드러진다. 이는 Fixed Priority System의 분석에서 낮은 우선순위 Task의 Interference를 무시할 수 있기 때문이다. 이는 순수 EDF에서는 불가하다.
  • 일반적인 의견 (본 논문의 분석 외): 일반적인 의견으로는 EDF의 절대적인 성능이 FPS보다 더 우수할 수 있다고 여겨진다. 그러나 이 논문은 실시간 시스템에서 증명 가능한 Schedulability를 찾는 것이 중요하며, 제시된 RTA를 사용했을 때 FP가 기존의 가장 우수한 Schedulability Test에 비해 보여주는 우월성이 이러한 절대 성능의 잠재적인 단점을 상쇄할 수 있다고 제안한다. 또한 FPS 구현이 더 쉽다는 점도 고려하면, 많은 경우 FPS가 더 선호될 수 있다.
• Pfair: 이 알고리즘은 암묵적 Deadline 시스템에 대해 최적이며 시스템 용량과 동일한 스케줄 가능 활용도를 달성할 수 있다. 하지만 우선순위 기반 스케줄러에 비해 상당히 많은 Contect Switching이 발생할 수 있다는 단점이 있다.
• EDZL: 이 알고리즘은 Dynamic Job Priority 스케줄러의 한 종류이다. EDZL은 EDF와 동일한 최악의 경우 Preemption 횟수를 가지면서도 다중 프로세서에서 훨씬 우수한 스케줄링 성능을 보여준다. 필요한 스케줄 가능성 조건과의 격차가 더 작을 것으로 예상되다.
• 하이브리드 알고리즘: 이 알고리즘은 FP와 Dynamic Priority Scheduler의 장점을 결합하는 것을 목표로 한다. 예로는 EDF-US, fpEDF, EDFk 등이 있다. 기존의 이러한 하이브리드 알고리즘에 대한 스케줄 가능성 테스트는 종종 시스템 용량의 절반에 가까운 활용도 및 밀도 경계에 의존하여 필요한 조건에 비해 상당한 성능 손실을 보인다. 

결론적으로, Global Scheduling은 평균 응답 시간 및 평균 Preemption 측면에서 Partitioned Scheduling에 비해 장점이 있지만, 최악의 경우 스케줄 가능성 측면에서는 상호 보완적이다. Global Algorithm 내에서는 EDF와 FP 사이에 흥미로운 절충이 존재한다. 일반적인 인식은 EDF의 절대 성능이 더 좋을 수 있다는 것이지만, 이 논문의 새로운 RTA 분석 결과는 증명 가능한 스케줄 가능성 측면에서 FP가 더 뛰어날 수 있음을 시사하며, 이는 구현의 용이성과 함께 FP를 매력적인 선택지로 만든다. Pfair는 이론적 최적성을 제공하지만, 스위칭 비용이 높고, EDZL과 같은 Dynamic Job Priority 알고리즘 및 하이브리드 스케줄러는 향상된 성능을 제공할 잠재력이 있지만, 기존 분석은 개선의 여지가 있다. 

 

Contribution

• Global EDF 및 FP 스케줄링 시스템에 대한 새로운 RTA 기법 제안
• 기존 방식보다 정확한 Carry-In/ Carry-Out WorkLoad 모델 도입
• System Slack을 활용한 분석 성능 개선 기법 제안
• 이 기법은 Hard Real Time System에서의 Schedulability를 향상시키고, 높은 시스템 사용률에서도 안정적으로 작동함

 

Key Ideas

• RTA는 각 Task가 가장 많은 Interference를 받을 수 있는 Worst Case Window에 집중하여 분석
• Global Multi Core System에서는 이러한 Worst Case 상황이 명확하지 않기 때문에, 대신 Upper Bound를 기반으로 한 보수적 Interference 추정이 필요
•  Theorem 2 ~ 7을 통해 Interference, Workload, Response Time 등를 Upper Bound로 모델링하고 반복 계산으로 수렴
• Slack을 계산해 반복적으로 Interference를 줄이면서 Response Time을 개선

 

Mathematical View & Detailed Proofs

Theorem 1 (Fixed Priority RTA)

$$R_{k}^{max}=C_k+\frac{1}{m}\sum_{\tau_j\in hp(k)}^{}(\left \lceil \frac{R_{k}^{max}}{T_j}C_j+C_j\right \rceil)$$

개념 설명:

• $C_k$:$\tau_k$의 WCET(Worst Case Execution Time)
• $T_j$: Interference을 주는 High Priority Task $\tau_j$의 Period
• $m$: 프로세서 수
• Interference로 인해 $\tau_k$는 $C_k$ 외의 시간동안 대기해야 함
• $\left \lceil R_{k}/T_j\right \rceil$: 분석 구간 동안 $\tau_j$가 실행되는 Job 수 
• 보수적 가정으로 Carry-In과 Carry-Out Job 각각이 $C_j$를 추가로 소비한다고 가정

증명 아이디어:

1. 분석 시작 시점에 $\tau_j$의 Job이 하나 존재한다고 가정 (Carry-In)
2. 분석 구간 내 반복적으로 Task가 도착 (Body)
3. 마지막으로 구간의 끝에 걸쳐있는 Job이 있다고 가정 (Carry-Out)

 

Theorem 2 - Interference $\leq$ Workload

$$I_{k}^{i}\leq W_{i}(a,b)$$

직관:

• Task $\tau_i$가 실행 중일 때만 Interference가 발생
• 전체 실행량(Workload)은 실행 시간의 누적값이므로 간섭량의 상한임

증명:

• Interference $I_k^i(a,b)$:$\tau_k$가 Ready이지만 실행되지 못하는 시간 중 $\tau_i$가 실행 중인 시간의 총합
• Workload $W_i(a,b)$: 실제 $\tau_i$가 그 구간에서 요구하는 CPU 시간ㄴ
• Interference는 Execution Time보다 클 수 없음 -> 불등식 성립

 

Lemma 1 (총 간섭 하한 조건)

$$I_{k}(a,b)\geq x\Leftrightarrow \sum_{i\neq k}^{}min(I_{k}^{i}(a,b),x)\geq m\cdot x$$

직관:

• $x$시간 동안 $\tau_k$가 모두 차단되려면 $m$개의 프로세서가 모두 다른 Task로 채워져야 함
• 각 Task의 Interference가 $x$이상인 경우만 유효한 간섭으로 계산됨

증명:

• $m$개의 CPU가 동시에 바빠야 $\tau_k$가 실행되지 못함
• 따라서, 간섭량이 $x$이상이라는 것은 각 Task 간섭량을 $x$로 자른 합이 $m \cdot x$이상이어야 한다는 것과 동치

 

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

$$\sum_{i\neq k}^{}min(I_{k}^{i}(r_{k}^{*},r_{k}^{*}+R_{k}^{ub}),R_{k}^{ub}-C_k+1)< m(R_{k}^{ub}-C_k+1)\Rightarrow R_k\leq R_{k}^{ub}$$

직관:

• 응답시간은 실행시간과 간섭시간의 합
• 간섭이 총합 기준을 넘지 않으면, 그 시간 이내에 실행 가능

증명:

• Lemma1을 이용하여 $\tau_k$의 간섭 상한을 $m(R_{k}^{ub}-C_k+1)\$로 설저ㅓㅇ
• 이보다 간섭이 작다면, $\tau_k$는 시간 내에 실행 가능하므로 $R_k \leq R_{k}^{ub}$

 

Theorem 4 (Workload Upper Bound)

$$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$$

직관:

• Workload:
  1. Body Job 수만큼의 $C_i$,
  2. Carry-Out Job의 일부 시간만 더함
• Carry-In은 $L$ 시작 전이므로 고려되지 않음

증명:

1. 구간 $[a,b=a+L)$에서 Body Jobs 수 계산: $N_i(L)$
2. Carry-Out Job이 있다면 그 일부만 영향을 줌
3. 총합은: 전체 Body + Carry-Out의 일부

 

Theorem 5 (EDF 스케줄러의 간섭 상한)

$$I_{k}^{i}(D_k)=DBF_k^i+min(C_i,max(0,D_k-DBF_k^i-\frac{T_i}{C_i}-s_i))$$

$$DBF_k^i=(\left \lfloor \frac{D_k-D_i}{T_i}+1\right \rfloor)C_i$$

직관:

• DBF(=Demand Bound Function)는 Body의 간섭량
• Carry-In 또는 Carry-Out은 1개만 발생 가능 -> min으로 보정

증명:

• $D_k$ 구간 내에 기여하는 $\tau_i$의 Body Jobs 계산 -> DBF
• Carry-In/ Carry-Out 중 하나만 발생한다고 가정해 $max(0,...)$로 보정된 간섭량 계산

 

Theorem 6 (EDF용 RTA 반복식)

$$R_{k}^{ub}=C_k+\left \lfloor \frac{1}{m}\sum_{i\neq k}^{}\hat{I_k^i}(R_k^{ub})\right \rfloor$$

$$\hat{I_k^i}(R_k^{ub})=min(W_i(R_k^{ub}),I_k^i(D_k),R_k^{ub}-C_k+1)$$

직관:

• RTA 반복식: 간섭량 기반 응답시간 추정
• 3가지 상한을 취해 보수적 간섭량 추정
  • $W_i$: 실제 수행량
  • $I_k^i(D_k)$: EDF 전용 간섭 상한
  • $(R_k^{ub}-C_k+1)$: Theorem 3 기반 상한

증명:

1. $R_k^{ub}$ 초기값을 $C_k$로 설정
2. 각 간섭량을 구해 반복적으로 적용
3. 수렴 조검은 Theorem 3에 의해 보장

 

Theorem 7 (FP용 RTA 반복식)

$$R_k_{ub}=C_k+\left \lfloor \frac{1}{m}\sum_{i<k}^{}\hat{I_k^i}(R_k^{ub})\right \rfloor$$

직관:

• Fixed Priority에서는 낮은 우선순위 Task는 간섭 없음 -> $i<k$만 합산
• EDF보다 더 강력한 상한 도출 가능

 

Slack 보정 기법

$$s_i=D_i-R_i^{ub}, \,\,\,\,\,\,\, Task\,\,i's\,\,slack$$

$$W_i(L)=N_i(L)C_i+min(C_i,L+D_i-C_i-s_i-N_i(L)T_i)$$

직관:

• Slack 값이 클수록 실제 간섭량 감소 -> 간섭 상한 조정 가능
• 반복 계산에서 각 Task의 Slack을 반영하여 재계산 -> 수렴성 향상

 

위의 수학적 모델들은 멀티프로세서에서의 Global Scheduling(RT-EDF FP)에 대한 응답시간을 추정하고, 보수적인 스케줄링 분석을 통해 보다 많은 Task Set이 Schedulable하다는 것을 증명할 수 있게 해준다. 

 

 

 

Ref

M. Bertogna and M. Cirinei, "Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms," 2007 28th IEEE International Real-Time Systems Symposium (RTSS), Tucson, AZ, USA, 2007, pp. 149–160, doi: 10.1109/RTSS.2007.31.