이번 논문은 전체적으로 정독하면서 이해가 어려운 지점들을 중심으로 내용을 정리하며 학습하고자 합니다. 특히 Dual Speed 및 Dual Speed with Reclaiming 기법이 어떻게 구성되는지, 그리고 이론적으로 deadline 보장이 어떻게 이루어지는지에 대해 깊이 있게 이해하고 싶습니다. 또한, 실험 결과를 해석할 때 저자들이 제시한 직관이 무엇인지, 특히 slack을 활용했을 때의 결과 변화가 어떻게 해석될 수 있는지를 중점적으로 살펴보고자 합니다. 마지막으로, 이 기법들이 실제로 energy efficiency 측면에서 얼마나 효과적인지, 그리고 현실적인 시스템 구현에서 어떤 제약이나 고려사항이 있는지에 대한 논의 역시 주의 깊게 적어보려고 합니다.

---

0. Abstract

모바일 컴퓨팅의 확산으로 에너지 소비를 줄이고 배터리 수명을 늘리는 기술에 대한 관심이 증가하고 있습니다. 본 논문에서는 선점 불가능한 구간(non-preemptible sections)을 포함한 실시간 주기적 태스크를 대상으로 프로세서 전압 스케줄링을 통해 에너지를 절감하는 기법을 다룹니다.

다음의 세 가지 스케줄링 알고리즘을 제안합니다:

1. Static Speed Algorithm

   • Stack Resource Policy(SRP)를 기반으로 전체 태스크 집합을 처리할 수 있는 최소 고정 속도를 계산합니다.

2. Dual Speed Algorithm

   • 최악의 블로킹 상황이 항상 발생하지 않는다는 점을 활용해 가능한 구간에서는 더 낮은 속도로 스위칭합니다.

3. Dynamic Reclaiming Algorithm

   • 예약 기반 방식으로 사용되지 않은 실행 시간을 회수하여 다른 태스크에 재분배하고, 결과적으로 유휴 시간을 줄이고 에너지 효율을 높입니다.

세 알고리즘에 대해 스케줄 가능성 조건(feasibility conditions)을 이론적으로 증명하였고, 시뮬레이션 결과를 통해 동적 알고리즘들이 정적 방식 대비 최대 80%까지 에너지 절감 효과를 보이는 것을 확인하였습니다.

---

1. Introduction

연구 배경 및 동기

• 모바일 기기의 확산으로 인해 에너지 절감 기술이 중요해졌으며, 특히 프로세서 전력 소모가 전체 소비 전력의 큰 부분을 차지.
• 많은 모바일 기기(노트북, PDA 등)는 배터리 수명이 제한적이며, 반면 프로세서 성능은 계속 향상되므로 전력 효율적 프로세서 운영이 필요함.

전압 스케일링 (Dynamic Voltage Scaling, DVS)

• DVS는 프로세서 전압 및 속도를 동적으로 조절해 에너지를 절감하는 기술.
• 전력 소비는 대략 전압의 세제곱(V³)에 비례하기 때문에 속도를 낮추면 에너지 절감 효과가 큼.
• 특히 실시간 시스템에서는 마감시간(deadline)을 지키기만 하면 속도 저하는 허용되므로 DVS 적용이 적합함.

기존 연구의 한계

• 대부분의 선행 연구는 태스크가 완전히 선점 가능하다는 가정하에 이루어짐.
• 하지만 실제 시스템에서는 공유 자원을 사용하는 임계 구간(critical sections) 때문에 비선점(non-preemptible) 구간이 존재함.
• 이로 인해 기존 기법을 그대로 적용하면 데드라인 미스나 잘못된 동작이 발생할 수 있음.

기여

• 본 논문은 비선점 구간이 있는 실시간 주기적 태스크에 대해 전압 스케줄링 기법을 제안함.

• 세 가지 알고리즘 제안:

  1. Static Speed: SRP 기반으로 계산된 고정 속도.
  2. Dual Speed: 가능한 경우 낮은 속도로 전환.
  3. Dynamic Reclaiming: 실행시간의 slack을 회수하고 재분배하여 추가 절전.

비선점 구간을 고려한 에너지 효율적인 실시간 스케줄링 기법을 제안하고, 모든 작업이 데드라인을 지키면서도 에너지를 얼마나 절감할 수 있는지에 대해 이론적 조건과 실험 결과를 함께 제시함.

---

2. System Model 요약

이 시스템 모델은 blocking section이 존재하는 hard real-time 태스크 집합을 DVS(dynamic voltage scaling)가 가능한 프로세서에서 정해진 데드라인을 보장하면서 에너지 소모를 최소화하는 문제를 풀기 위한 기반 구조를 정의함.

2.1 Task Model (태스크 모델)

• Periodic Task Set $\mathcal{T}$: 각 태스크 $T_i$는 다음 네 가지 파라미터로 정의됨:

  • $A_i$: 첫 도착 시간
  • $D_i$: 상대 마감 시간 (본 논문에서는 $D_i = P_i$)
  • $P_i$: 주기 (Period)
  • $E_i$: 최대 실행 시간 (WCET)

• Job은 태스크가 주기적으로 생성하는 단위 작업이며,

  • 각 job $J_{i,j}$는 도착 시각 $r_{i,j}$, 실행 시간 $e_{i,j} \leq E_i$, 마감 시각 $d_{i,j}$로 구성됨.

• Blocking Sections (비선점 구간):

  • 태스크에는 0개 이상의 blocking section이 있을 수 있음.
  • 어떤 자원을 점유하거나 atomic transaction 중일 때 선점이 불가능.
  • $G_i$: 태스크 $T_i$ 내 가장 긴 blocking section의 길이.

• 가정:

  • 태스크는 비선점 구간을 제외하면 선점 가능.
  • 모든 태스크는 hard real-time 조건을 만족해야 함 (즉, 데드라인 미스는 허용되지 않음).

---

2.2 Processor Model (프로세서 모델)

• 프로세서는 Dynamic Voltage Scaling (DVS) 가능:

  • 공급 전압에 따라 속도(speed)가 결정됨.
  • 속도는 정규화되어 있음: 최대 속도 $S_{\max} = 1$, 최소 속도 $S_{\min}$

• 전력 소비 모델:

  $P = K \cdot V_s^3$
  • $V_s$: 공급 전압
  • $K$: 상수
  • 전압이 속도에 비례한다고 가정하므로, 속도를 줄이면 에너지 소비가 큼폭 줄어듦.

• 전압 전환 비용은 무시 가능하다고 가정:

  • 매우 짧은 시간 내 전환 가능
  • Blocking section 내부에서도 전압 전환 가능함

---

3. Static Blocking-aware Voltage Scheduling

• 비선점 구간(blocking section)이 존재할 때, 모든 태스크가 마감시간 내에 완료될 수 있도록 정적인 최소 프로세서 속도 $H$를 계산.
• 속도 $H$는 태스크 추가/삭제 시에만 재계산되며, 그 외에는 고정.

---

기본 개념 정리

• $E_i$: 태스크 $T_i$의 WCET
• $P_i$: 태스크 $T_i$의 주기
• $B_i$: 태스크 $T_i$가 최대 차단(block)될 수 있는 시간 (blocking time)
• $G_j$: 태스크 $T_j$ 내 가장 긴 blocking section
• $H$: 정적으로 고정한 프로세서 속도 (normalized, 최대값 1)
• 모든 태스크는 EDF + SRP 기반으로 스케줄됨

---

Theorem 1 (Baseline SRP Feasibility Condition)

EDF + SRP 하에서, 태스크 집합이 스케줄 가능하려면:

• 여기서 $B_k$는 $T_k$가 단 한 번 차단당하는 최악의 blocking 시간입니다.
• 첫 번째 항은 일반적인 utilization 합.
• 두 번째 항은 해당 수준에서 worst-case blocking이 한 번만 발생한다고 보는 보수적 모델.

---

Theorem 2 (Static Speed에서의 Feasibility 조건)

프로세서 속도가 $H \leq 1$일 때, 다음 조건을 만족하면 EDF + SRP 기반으로 스케줄 가능:

• 속도를 $H$배하면 실행 시간은 $\frac{1}{H}$배가 되므로 Theorem 1에 이를 적용해 위와 같은 inequaility를 유도할 수 있음.

---

Corollary 1 (Blocking 항을 더 명시적으로 표현)

태스크 집합이 단일 공유 리소스를 사용하는 경우(모든 태스크가 리소스를 요청하거나 요청하지 않더라도 0으로 간주), 다음 조건으로 스케줄 가능:

• EDF에서는 주기가 더 긴 태스크만 현재 태스크 $T_j$를 block할 수 있으므로(blocking은 근본적으로 priority inversion),

  • $T_j$의 blocking 시간은 $\max\{ G_k \mid P_k > P_j \}$

• 마찬가지로 이 항도 한 번만 추가되는 blocking overhead임.

---

조건	수식 형태	의미
Theorem 1	$\sum \frac{E_i}{P_i} + \frac{B_k}{P_k} \leq 1$	EDF + SRP 기준 스케줄 가능성 (속도 1)
Theorem 2	$\sum \frac{E_i}{P_i} + \frac{B_k}{P_k} \leq H$	속도 $H$로 줄였을 때 스케줄 가능 조건
Corollary 1	$\sum \frac{E_i}{P_i} + \frac{\max \{G_k \mid P_k > P_j\}}{P_j} \leq H$	단일 리소스 모델에서 $G_k$로 간단화

---

4. Dynamic Blocking-aware Voltage Scheduling

---

4.1 A Dual-Speed Switching Algorithm

Blocking이 발생하지 않을 때는 굳이 높은 속도로 실행할 필요가 없다. 따라서, 일부 구간에서는 낮은 속도로 운영하면서도 전체 시스템의 deadline 보장 조건은 유지하도록 하는 것이 이 알고리즘의 핵심!

알고리즘 핵심 개념

• 두 가지 속도를 사용함:

  • High Speed ($H$): static speed scheduling에서 계산한, worst-case blocking을 고려한 속도.
  • Low Speed ($L$): 단순히 WCET 기준으로 utilization만 고려한 속도. (blocking 미고려)

정의:

• $H$: blocking까지 고려한 정적 속도 (Theorem 2에서 나온 값)
• $L = \sum_{i} \frac{E_i}{P_i}$: blocking을 무시한 일반적인 utilization 기반 속도
  → $L \leq H$

---

알고리즘 동작 원리 요약

1. 기본적으로 프로세서는 낮은 속도 $L$로 동작함.
2. 어떤 태스크가 blocking 상태를 유발하면, 해당 blocking 기간 동안은 속도를 $H$로 높임.
3. blocking이 끝나면 다시 $L$로 전환.

---

알고리즘 절차 요약 (Figure 1 참조)

• Job Arrival:

  • 새로운 job이 도착하여 현재 실행 중인 job보다 우선순위가 높으면,

    • preemption 시도
    • 만약 실패 → blocking 발생 → 속도 $H$로 전환
    • high-speed interval의 종료 시점을 deadline으로 기록

• High-Speed Interval 종료:

  • 저장된 deadline 도달 시 → 다시 속도 $L$로 복귀

---

Theorem 3 – 스케줄 가능성 보장

Dual-Speed 알고리즘으로 전환해도 deadline miss는 발생하지 않음.

조건:

• 시스템이 static speed $H$로 스케줄 가능하다면,
• 일부 구간에서 $L$로 운영하더라도, blocking 발생 시에만 $H$로 전환하면 전체 데드라인 보장 가능함을 증명.

---

증명

1. 반례 가정

어떤 작업 $J$가 데드라인 $d_J = t$에 처음으로 마감시간을 초과한다고 가정한다.

2. 마지막 안전 구간 (latest busy interval) 설정

$t$보다 이전에 마감시간 초과가 없었으므로,
processor가 idle하지 않고 계속 실행되던 마지막 구간을 $(t', t]$라 하자.
($t'$은 $t$ 이전의 시점이며, $(t', t]$ 사이에는 idle 구간이 없음)

경우 1: $(t', t]$ 동안 블로킹이 발생하지 않음

• 이 경우, Dual-Speed 알고리즘은 항상 속도 $L$로 동작함.

• 프로세서 공급량:

  $S = L \cdot X$

• 작업 수요는 구간 내 도착한 작업들의 실행 시간 합으로,

  $D \leq \sum_{J_i \in M} E_i \leq L \cdot X$

→ $D \leq S$이므로 deadline miss가 발생할 수 없음 → 가정과 모순

---

경우 2: $(t', t]$ 동안 블로킹이 발생함

• 이 경우, processor는 구간 전체에서 속도 $H$로 동작함.

• 공급량:

  $S = H \cdot X$

• 수요는 블로킹 시간 $G_k$와 작업 실행 시간 합의 합으로,

  $D = G_k + \sum_{J_i \in M} E_i \leq H \cdot X \tag{조건 (3)}$

→ 역시 $D \leq S$이므로 deadline miss는 발생할 수 없음 → 가정과 모순

---

추가 최적화 (짧은 high-speed 종료 조건)

• High-speed 구간을 더 줄이기 위해 두 조건 중 하나 만족 시 조기 종료:

  1. 현재 실행 중인 job의 deadline ≥ high-speed 종료 시간
  2. 프로세서가 idle 상태가 됨

• 이로 인해 H 속도 사용 시간이 더 줄어듦 → 추가 에너지 절감 가능

---

4.2 A Dynamic Reclaiming Algorithm

Dual-Speed 알고리즘은 blocking 발생 시에만 고속으로 전환하여 에너지를 절약하지만,모든 작업이 WCET를 다 쓴다는 보수적인 가정에 기반합니다. → 실제로는 많은 작업이 WCET보다 일찍 종료되므로,남는 시간(slack)을 수집해서 다른 작업들이 더 느리게 실행할 수 있게 해주면, 추가적인 전력 절감이 가능합니다.

DSDR 알고리즘은 Dual-Speed 기반 구조 위에 슬랙 재분배 메커니즘을 도입하여,데드라인 보장은 그대로 유지하면서 processor 속도를 더 낮춰 에너지 효율을 높이는 진보된 전압 스케줄링 기법이다.

---

1. 작업 실행에 할당된 runtime과 실제 사용 시간 사이에 남는 시간이 생김.
2. 이 잔여 시간(= Free Run Time)을 FRT-list에 저장.
3. 이후 도착한 다른 작업이 이 시간을 가져다 쓰며 더 느리게 실행 가능.
4. 따라서 전체적으로 더 낮은 평균 속도로 실행 가능 → 에너지 절약.

---

Notation

용어	의미
$R_i(t)$	현재 시점에서 작업 $J_i$가 사용할 수 있는 runtime
$E_i$	WCET (Maximum Execution Time)
$R_i^{F}(t)$	FRT-list에서 $J_i$가 사용할 수 있는 잔여 runtime
FRT-list	(free runtime, deadline)의 쌍을 저장하는 리스트 (잔여 시간 저장소)
base speed	Dual-Speed 알고리즘이 지정한 속도 ($L$ 또는 $H$)
실제 속도	사용 가능한 runtime에 따라 계산된 실행 속도 $S = \frac{E_i}{R_i + R_i^F}$

---

DSDR 알고리즘 흐름 (논문의 Figure 3 참고)

작업 도착 시

• 초기 runtime은 $R_i = \frac{E_i}{L}$로 할당 (낮은 속도 기준)
• 만약 처음 실행이 고속 구간이라면 base speed = $H$ → runtime 재계산

작업 실행 시

• 사용 가능한 runtime = $R_i + R_i^F$
• 실행 속도 $S = \frac{E_i}{\text{available runtime}}$
• 실행하면서 runtime 감소 (FRT 먼저 소진)

작업 완료 시

• runtime이 남았다면 그 양을 FRT-list에 추가

High-speed 구간 진입 시

• 할당된 runtime보다 덜 필요해진 경우 → 차액을 FRT-list로 반환

---

수학적 조건 (Lemma 1, 2, Theorem 4)

Lemma 1

DSDR 알고리즘 하에서는 모든 작업이 runtime을 다 소진하기 전에 반드시 완료된다.

→ 왜냐하면 Dual-Speed 기준에서 runtime을 보수적으로 할당했고, 그 시간보다 짧게 실행될 수 있기 때문.

---

Lemma 2 + Theorem 4

다음 조건이 주어지면 DSDR에서도 모든 작업은 runtime을 deadline 내에 다 소진하며 완료됨:

→ 즉 Dual-Speed가 가능하다면, DSDR은 그 이용률을 더 낮춰서 효율적으로 실행할 수 있음이 증명됨.

---

5. Performance Evaluation

이 장에서는 제안한 세 가지 알고리즘 — Static Speed, Dual Speed, DSDR —의 에너지 소비 효율을 비교 실험을 통해 평가합니다.

---

5.1 Simulation Setup

시뮬레이션 구성:

• 싱글 프로세서, DVS (dynamic voltage scaling) 지원
• 속도 범위: $S_{\min} = 0.1$, $S_{\max} = 1.0$ (0.1 단위로 이산화)
• 프로세서 전력 모델: $P \propto V^3 \propto S^3$
• idle 상태일 땐 전력 소비 0

실험 환경:

• 30개의 주기적 태스크를 생성
• 다양한 태스크 주기 (long, medium, short)
• 태스크 WCET을 조절하여 target utilization 설정
• 실제 실행 시간은 WCET보다 작도록 slack factor로 조정
• blocking section은 확률적으로 부여하며 길이도 조절

---

5.2 Experimental Results

실험 1: Blocking Factor 변화

• blocking 길이 증가에 따라 Static speed는 더 많은 에너지를 소비
• Dual Speed는 최대 70%, DSDR은 그 이상 절감 가능
• 다만 blocking이 매우 드물게 발생하는 경우 Dual과 DSDR의 차이는 적음

실험 2: Blocking Probability 변화

• blocking 발생 확률을 증가시키면 전체 에너지 소모도 증가
• DSDR은 slack reclaim으로 인해 여전히 에너지 절약 효과 유지

실험 3: Slack Factor 변화

• 작업 실행 시간이 WCET보다 훨씬 짧아질수록:

  • DSDR의 에너지 절감 폭이 Dual Speed보다 확연히 큼
  • 예: slack factor 0.5일 때 DSDR은 최대 70% 절감, Dual은 50% 수준

실험 4: Utilization 변화

• 시스템 전체 utilization이 낮을수록 → 알고리즘 간 절감률 차이가 작음
• utilization이 0.6 이상이 되면, task drop 때문에 Static의 에너지 소비 증가
• DSDR은 consistently Dual보다 더 절감 효과 있음

---

6. Related Work

• 선행 연구는 크게 두 분류:

  1. Interval-based scheduling: 과거의 시스템 부하를 보고 다음 속도를 조절 (ex. PAST, AVG)

     • 하지만 real-time 보장 어려움

  2. Profile-based scheduling: task profile 또는 WCET에 기반해 DVS 결정

     • 대표: Yao et al.의 offline optimal, Pillai & Shin의 RM/EDF 기반 DVS

• 대부분 fully preemptive 또는 fully non-preemptive한 모델만 다룸

• 본 논문은 non-preemptible section이 있는 현실적인 시나리오에 대해 DVS 스케줄링을 설계했다는 점에서 차별화

---

7. Conclusion

• 비선점 구간(blocking section)을 가지는 실시간 태스크 환경에서의 에너지 효율적 스케줄링 문제를 다룸

• 3가지 voltage scheduling 알고리즘 제안:

  1. Static Speed: SRP 기반 고정 속도 계산
  2. Dual Speed: blocking 시에만 속도를 올림
  3. DSDR: slack을 회수하여 재분배

• 세 알고리즘 모두에 대해 feasibility 보장 수학적 증명 제시

• 시뮬레이션 결과, DSDR이 최대 80% 이상의 에너지 절감 가능