스케쥴링 가능성을 분석하는 방법에 대해 배운다. 또한, 이론적으로 가능하더라도 현실적으로 불가능할 수 있다는 사실을 알아야 한다. 우선, 스케쥴링 분석 여부에 따라 Exact와 Only sufficient로 나뉘게 된다.

  • Exact : 모든 Task가 스케쥴링 가능하며, analysis 가능함
  • Only Sufficient : 일부 Task가 스케쥴링 가능하며, analysis 가능함

 

보다 쉬운 이해를 위해 지금부터는 다음의 가정을 사용한다. 반대로 말하면, 다음의 내용이 실제 구현에 있어 고려할 내용임을 의미한다.

  • Single processor
  • Hard deadline
  • Independent periodic tasks
  • $d_i = p_i$
  • Preemptable
  • No overhead for context switch

 

1. 스케쥴링 분류

  • Task-level fixed-priority (TFP) : RM이 optimal이다.
  • Task-level dynamic-priority
    • Job-level fixed-priority (JFP) : EDF가 optimal이다.
    • Job-level dynamic-priority (JDP) : LSTF가 optimal이다.

 

TFP < JFP < JDP 순의 포함 관계를 가지며 각각의 optimal policy에 대한 설명은 다음과 같다.

  • RM : period가 짧은 순서대로 우선순위 부여
  • EDF : deadline이 가까운 순서대로 우선순위 부여
  • LSTF : slack time이 작은 순서대로 우선순위 부여
    • slack time = deadline까지 남은 시간 - 남은 execution 시간

 

무엇이 좋은지 비교하는 metric으로 utilization이 있을 수 있다. 어떠한 policy도 $\sum U_i > 1$은 불가능하다.

 

2. RM

주기가 짧은 task에 높은 우선순위를 부여하는 방식으로 간단하고 효과적이지만, 항상 좋지만은 않다. Worst-case를 critical instant라 하며, RM의 critical instant는 모든 task가 동시에 release되는 경우이다.

 

우선 utilization과 responsetime에 의한 analysis의 특징은 다음과 같다.

  • Utilization based analysis
    • $U \leq n(2^{1/n}-1)$
    • $n \rightarrow \inf$, $n=0.69$ 이다. 따라서 Only sufficient이다.
  • Response time bsed analysis
    • Exact

 

3. RM : Critical Instant

Task 두 개가 release되는 경우는 크게 3가지 일 것이다. RM을 적용하였을 때, maximum response time을 발생하는 것은 위의 3가지 케이스 중 2번째 이다.

  • Case 1: maximum response time = $e_{T1}+T2_{release}-T1_{release}$ or $e_{T2}$
  • Case 2: maximum response time = $e_{T1}+e_{T2}$
  • Case 3: maximum response time = case1과 유사

 

4. RM : Utilization-based analysis

$U \leq n(2^{1/n}-1)$에 대한 증명이다. Processor utilization의 least upper bound를 보이면 된다. 그건 알아서 잘 해보자.

 

예제는 다음과 같다.

Task의 utilization 합은 0.753이고 $U(3)$은 0.779이므로 스케쥴링 가능하다.

 

5. RM : Response time-based analysis

Maximum response time을 구하는 공식은 위와 같다. $a_{n+1}=a_n$이면 maximum을 구한 것으로 생각한다. 그래서 만약 $a_n \leq p_i$이면 스케쥴링 가능하다. 

 

예제는 다음과 같다. T3가 스케쥴링 가능한지 확인해 보자.

  • $a_0 = \sum e_j = e_1 + e_2 + e_3 = 180$
  • $a_1 = e_i + \sum {a_0 \over p_j}e_j = e_3 + {180 \over 100}40 + {180 \over 150}40 = 260$
  • $a_2 = 300$
  • $a_3 = 300$

따라서 $a_3 =300$이고 $p_3 = 350$이므로 $a_3 < p_3$이므로 T3는 스케쥴링 가능하다.

 

6. RM : Transient overload

RM은 주기가 짧은 task에게 높은 우선순위를 부여했다. 다만, 주기가 짧은 task라도 주기가 긴 task보다 중요도가 낮을 수 있다. 가령 아래 예제에서 T4의 실행이 중요하지 않은 T3에 의해 지연되거나 스케쥴링이 안될 수 있다.

 

해결방안으로는 3가지가 있다. Period를 조절하여 우선순위를 맞추거나, 여러 small task를 하나의 task로 합치거나 큰 task를 작은 task로 나누는 방법이 있다.

 

7. RM : UB test with interrupt

주기가 짧은 task임에도 긴 interrupt이 발생하여 스케쥴링에 문제를 줄 수 있다. 이는 우선순위 불일치에 의한 실행 지연을 야기하며 이런 interrupt의 영향을 고려한 새로운 schedulability 분석이 필요하다. 이를 위해 수정된 사용률 기반 테스트, UB test가 진행된다.

 

UB test에서는 effective utilization, $f$를 구하여 분석한다.

  • $H$ : higher priority task
  • $H_n$ : $p_j < d_i$인 모든 task
  • $H_1$ : $p_j > d_i$인 모든 task

 

Effective utilization이 구해지면, 이를 $U(n=num(H_n)+1)$과 비교하여 스케쥴링 가능성을 분석한다.

 

예제는 다음과 같다.

 

  • $T_3$
    • $H=H_n=H_1=\{\}$
    • Bound = $U(1)$
    • $f_3 = 0 + e_3 / p_3 + 0 \leq U(1)$
  • $T_1$
    • $H=\{T_3\}; H_n=\{\}; H_1=\{T_3\}$
    • Bound = $U(1)$
    • $f_1 = 0 + e_1 /p_1 + {\sum_{k=3} e_k \over p_1} \leq U(1)$
  • $T_2$
    • $H=\{T_1, T_3\}, H_n = \{T_1\}, H_1 = \{T_3\}$
    • Bound = $U(2)$
    • $f_2 = {e_1 \over p_1} + {e_2 \over p_2} + {e_3 \over p_3}$
  • $T_4$
    • $H=\{T_1, T_2, T_3\}, H_n = \{T_1, T_2, T_3\}, H_1 = \{\}$
    • Boudn = $U(4)$
    • $f_4 = {e_1 \over p_1} + {e_2 \over p_2} + {e_3 \over p_3} + {e_4 \over p_4} + 0$

 

$T_2$와 $T_4$는 utilization보다 값이 커 스케쥴링 불가능하다는 것을 알 수 있다.

 

UB test를 이용해서 blocking이 있을 때, 스케쥴링 가능성도 검증 가능하다. 방식은 같으며 하나의 term이 추가된다.

 

이러한 내용은 response time 분석에도 사용 가능하다.

 

8. EDF : Schedulability analysis

음 그냥 $U \leq 1$이면 된다.

 

9. 정리

$d_i = p_i$인 경우, 각각의 policy가 optimal이다.

  • TFP : RM
    • $U \leq n(2^{1.n}-1)$
    • Response time analysis = exact
  • JFP : EDF
    • $U \leq 1$
  • JDP : LSTF
    • $U \leq 1$

 

$d_i \leq p_i$인 경우, 다음의 policy가 optimal이다.

  • TFP : DM (deadline monotonic)
    • $\sum e_i/d_i \leq n(2^{1/n}-1)$
    • Response time analysis $a_n \leq d_i$
  • JFP : EDF
    • $\sum e_i/d_i \leq 1$
  • JDP : LSTF
    • $\sum e_i/d_i \leq 1$

'Study > Real-Time Embedded System' 카테고리의 다른 글

[06] Mixed-Criticality Scheduling  (1) 2024.06.02
[05] Multiprocessor Real-Time Scheduling  (1) 2024.06.02
[03] Uniprocessor Real-Time Scheduling  (0) 2024.06.01
[02] Cyber-Physical Systems  (0) 2024.05.31
[01] Real-Time Systems  (0) 2024.05.31