Processor Voltage Scheduling for Real-Time Tasks with Non-Preemptible Sections

느낀점

 

 

Problem Statement

어떻게  Voltage Scheduling 기술이 실시간 시스템의 전력소모를 최소화할 수 있는가?

Voltage Scheduling 기술은 프로세서의 속도를 줄임으로써 에너지 소비를 최소화한다. 휴대 기기에게 배터리 수명을 연장하는 효과적인 방법이다. 

이 기술은 전력 소비율($P$), 공급 전압($V_s$), 클럭 주파수($f$) 간의 관계를 활용한다. 이 관계는 대략 $P = C \cdot V_s^2 \cdot f$로 설명된다. 프로세서 속도와 주파수($f$)는 공급 전압($V_s$)에 거의 비례하기 때문에, 전력 소비율은 공급 전압의 세제곱에 대략 비례하게 된다. ($P = K \cdot V_s^3$, 여기서 $K$는 상수). 따라서 공급 전압을 낮춰 프로세서 속도를 줄이면 전력 소비가 크게 감소한다.

실시간 어플리케이션의 경우, Deadline을 지키는 한 Computation Time이 길어져도 괜찮기 때문에 Voltage Scheduling이 특히 유용하다. 따라서 Scheduler는 어떤 Job을 실행할 지 뿐만 아니라 어떤 속도로 실행할 지도 결정해야 한다. 

논문에서 설명하는 Voltage Scheduling 방식은 다음과 같이 에너지 소비를 줄인다. 

• Static Speed Algorithm: Stack Resource Policy (SRP)를 기반으로 실현 가능한 최소 정적 속도($H$)를 계산한다. 이 속도는 WCET(Worst Case Execution Time)과 최대 Blocking Length를 기반으로 모든 Task의 실현 가능성을 보장하지만, 항상 최악의 상황이 발생하는 것은 아니므로 에너지 효율성 측면에서는 최적은 아닐 수도 있다. 
• Dual Speed Algorithm: 정적 속도($H$)와 활용률 속도($L$, 일반적으로 $H$보다 낮음)로 Cycle 전환을 한다. 가능한 한 속도 $L$로 실행하고, Task가 더 높은 우선순위 작업을 Block하는 경우에만 속도 $H$로 전환한다. 이는 최악의 Blocking이 항상 밣생하지 않고, 허용된 Task의 총 프로세서 활용률이 일반적으로 정적 속도 $H$보다 낮다는 사실을 활용하여 일부 구간에서는 더 낮은 속도로 작동하게 한다. 속도 $L$로 실행하는 것은 속도 $H$로 실행하는 것보다 전력을 적게 소모한다. 
• Dynamic Reclaiming Algorithm: 듀얼 속도 알고리즘을 확장하여, 예약 기반 방식을 사용하여 사용되지 않은 실행 시간(예: Job이 일찍 완료되거나 고속 구간에서 발생하는 잔여 시간)을 회수하고 다른 대기 중인 Job에 재분배한다. 이렇게 회수된 추가 실행 시간을 통해 해당 Job은 기본 속도($H$ 또는 $L$)보다 훨씬 낮은 속도로 처리될 수 있어, 에너지 소비를 더욱 줄이고 유휴 시간을 감소한다.

정리하면, Voltage Scheduling 기술은 프로세서 속도를 가변적으로 저절하고, 특히 Job 부하가 낮거나 최악의 경우가 발생하지 않을 때 속도를 낮춤으로써 전력을 절약한다. Deadline 준수를 보장하는 범위 내에서 이러한 속도 조절을 동적으로 수행하는 알고리즘은 정적 속도 방식에 비해 에너지 소비를 크게 줄일 수 있다. 시뮬레이션 결과는 동적 알고리즘이 정적 속도 방식에 비해 에너지 소비를 최대 80%까지 줄일 수 있음을 보여줄 수 있다.

Static Speed Algorithm의 단점은 무엇인가?

1. 최악의 경우를 기준으로 속도로를 설정하여 에너지 효율성이 떨어짐: Static Speed Algorithm은 Stack Resource Policy(SRP)에 기반하여 모든 Job의 실현 가능성을 보장하는 최소 정적 속도($H$)를 계산한다. 이 속도는 최악의 실행 시간(WCET)과 최대 Blocking Length를 고려하여 결정된다. 그러나 실제 실행 시간이나 Blocking Length는 최악의 경우보다 짧은 경우가 많다.
2. 실제 Job 부하 변동을 활용하지 못함: 프로세서는 항상 완전히 활용되지 않으며, 시스템 부하의 변동이 있을 수 있다. Static Speed Algorithm은 고정된 속도($H$)로 작동하므로, 실제 Job 부하가 최악의 경우보다 낮을 때에도 속도를 더 줄일 수 있는 기회를 활용하지 못한다. 
3. 결과적으로 Dynamic Algorithm에 비해 에너지 소비가 높음: 프로세서 속도를 낮추면 전력 소비가 크게 감소하는데, Static Speed Algorithm은 필요 이상으로 높은 속도를 유지하게 되어, 에너지 소비 측면에서 최적이 아닐 수 있다. 논문의 시뮬레이션 결과에 따르면, Dual Speed Algorithm과 Dynamic Reclaiming Algorithm 같은 Dynamic Algorithm은 Static Speed 방식에 비해 에너지 소비를 최대 80%까지 절감할 수 있을 보여준다. 이는 Static Speed Algorithm이 동적 변화에 덜 유연하게 대처하기 때문이다.

모바일 및 임베디드 시스템은 대부분 제한된 배터리로 작동하며, 에너지 효율은 시스템의 지속 가능성을 좌우하는 중요한 문제이다. 이를 해결하기 위해 Dynamic Voltage Scaling 기법이 사용되며, 이는 프로세서 속도를 낮춰 전력 소모를 줄이는 방식이다. 

하지만 대부분의 기존 연구는 Task가 전적으로 선점 가능(Preemptible) 하다는 가정을 한다. 현실에서는 Task가 lock, transaction 등으로 인해 선점 불가능(non-preemtible)한 구간(Blocking Section)을 가지는 경우가 많다.

연구 목표

Blocking 구간을 가지는 실시간 주기적 Task set에 대해, DVS를 활용하여 Deadline을 지키면서 에너지 소비를 최소화하는 Scheduling 기법을 설계한다.

 

Contributions

1. Task Model 확장: Blocking(non-preemptible) 구간을 포함한 실시간 주기적 Task Model 제시
2. 세 가지 Voltage Scheduling 기법 제안:
   • Static Speed Algorithm: SRP(Stack Resource Policy)를 기반으로 Task Set 전체에 대해 하나의 Static Speed 계산
   • Dual Speed Algorithm: 상황에 따라 고속($H$)과 저속($L$) 간 전환
   • Dynamic Reclaiming Algorithm: 실행 완료 후 남은 시간 예산을 회수하고 재배분하여 더 느린 속도로 실행 가능
3. 각 알고리즘의 정확한 수학적 타당성 조건 및 증명
4. 시뮬레이션을 통해 최대 80%까지 에너지 절감 확인

 

Key Ideas

• SRP(Stack Resource Policy): Preemption/Sharing Resource 접근을 위한 무기한 봉쇄 방지 기법
• EDF(Earliest Deadline First) 기반의 실시간 스케줄링
• Blocking이 있는 경우에는 언제 어떤 속도로 실행 가능한 지에 대한 정밀한 분석 필요
• DVS(Dynamic Voltage Scaling)는 속도(=전압)를 낮추어 전력($P \approx V^3$)을 줄이되, Deadline은 절대 초과하지 않아야 함

 

Mathematic Views

 

Theorem 1: SRP-based EDF Schedulability Condition

다음 식을 만족하면 Task Set은 SRP + EDF로 Deadline 내 실행 가능:
$$\sum_{i=1}^{k}\frac{E_i+B_k}{P_i}\leq 1\,\,\,\,\forall k$$

• $E_i$: Task $T_i$의 WCET
• $P_i$: Task $T_i$의 Period
• $B_k$: Task $T_k$의 Job이 받을 수 있는 Worst Blocking Time

증명:

1. EDF + SRP 스케줄링을 적용할 경우, 동시에 실행될 수 있는 Job은 자원 충돌이 없는 경우로 제한됨
2. Task $T_k$의 job이 최대 $B_k$만큼 Block이 될 수 있다고 가정
3. 각 Task의 처리 시간은 $E_i$, 이 때 실행이 가능하려면 모든 $k$에 대해 Deadline 이전에 실행이 완료되어야 함
4. 이를 위해 주어진 주기 $P_i$마다 $(E_i+B_k)$의 시간이 필요함

직관:

• CPU에 부하가 너무 많이 걸리면 안된다. 
• 각 Task는 자신의 실행 시간뿐 아니라 Blocking 당할 수 있는 시간까지 합쳐서 고려해야 한다.
• 이를 합산한 값이 프로세서가 처리할 수 있는 100% 용량을 넘지 않아야 Deadline 내에 모든 job을 끌낼 수 있음

 

Theorem 2: Voltage Scaling을 고려한 Schedulability Condtion

전압을 낮춰 CPU 속도를 $H$로 줄인 경우, 다음 식을 만족해야 Deadline 보장:
$$\sum_{i=1}^{k}\frac{E_i+B_k}{P_i}\leq H\,\,\,\,\forall k$$

증명:

1. CPU 속도를 $H$로 줄이면 실행 시간이 $1/H$배 증가하게 됨
2. 따라서 모든 실행 시간과 Blocking 시간도 $1/H$배로 늘어났다고 가정한 새로운 Task Set $T^*$을 생각
3. 이 $T^*$를 원래 속도(=1)로 실행하면, 정리 1의 조건이 적용됨
4. 따라서 아래 식이 성립해야 한다:

$$\sum_{i=1}^{k}\frac{E_i+B_k}{P_i}\leq H$$

직관:

• CPU 속도를 줄이면 에너지는 줄지만 처리 능력도 줄어듬
• 즉, 작업량은 늘어나고, 같은 Deadline 안에 처리하려면 "줄인 만큼 여유가 있어야" 한다
• 이 정리는 CPU를 얼마나 느리게 설정할 수 있는지를 수학적으로 알려줌

 

Corollary 1:  간단한 Static Speed 계산 공식

다음 식을 만족하면 속도 $H$로도 Task들을 Deadline 내에 처리할 수 있음:
$$\sum_{i=1}^{j}\frac{E_i}{P_i}+\frac{max\{G_k|P_k< P_j\}}{P_j}\leq H \,\,\,\,\forall j$$

• $G_k$: Task $T_k$의 최대 Blocking Section Length

증명:

1. EDF Scheduling 특성상, 작은 주기의 Task가 먼저 실행됨
2. 그러므로 Task $T_j$는 자신보다 주기가 큰 Task에게서만 Block될 수 있음
3. 그 중 가장 긴 Blocking Section을 하나만 고려하게 된다.
4. 이 Blocking 시간과 실행 시간들을 해당 Task의 주기를 나눠 모두 더함 -> $H$보다 작으면 OK

직관:

• Deadline 계산 시, Blocking은 자기보다 우선순위 낮은 Task만 고려하면 됨
• 실행 시간 대비 CPU 속도를 얼마까지 줄여도 되는지를 정량적으로 알려줌

 

Theorem 3: Dual Speed Algorithm의 Schedulability Condition

다음 두 식이 모두 성립하면 Dual Speed Algorithm으로도 스케줄 가능:
1. 고속에서의 타당성:
$$\sum_{i=1}^{j}\frac{E_i}{P_i}+\frac{max\{G_k|P_k< P_j|\}}{P_j}\leq H $$

2. 저속에서의 총 부하:
$$\sum_{i=1}^{n}\frac{E_i}{P_i}\leq L$$

증명:

1. 모순 가정: Deadline을 어기는 시점 $t$가 존재한다고 가정
2. $t'$를 정의: $t$보다 전 시점으로, 아직 $t$까지 마감인 Job이 실행되지 않은 시점
3. 두 가지 케이스:
   • (1) Blocking 없음: 해당 Job들만 고려하면 $ L \cdot (t-t')$이하로 충분히 처리 가능해야 함 -> 모순
   • (2) Blocking 있음: 최대 Blocki9ng 시간 $G_m$ 추가로 고려하여도 $H \cdot (t-t')$이하로 처리 가능 -> 모순

직관:

• 고속($H$)은 Blocking이 발생하는 Critical Section에서 사용
• 저속($L$)은 나머지 평상 시 실행
• 이 방식은 필요한 경우만 고속을 사용하므로 에너지 절약에 유리하면서도 Deadline 보장을 유지 

# 초기 설정
H = StaticHighSpeed()  # 정리 2 또는 보조정리 1을 사용해 고속(H) 계산
L = UtilizationSpeed()  # ∑Ei/Pi 로부터 저속(L) 계산
End_H = -1  # 현재 고속 구간이 없음을 의미

# 새로운 Job 도착 시
OnJobArrival(Job J):
    if J.priority > current_job.priority:
        if PreemptCurrentJob():  # 선점 가능하면
            Execute(J)
        else:
            # 블로킹 발생 - 고속으로 전환
            SetProcessorSpeed(H)
            End_H = max(End_H, current_job.deadline)

# 고속 구간 종료 시
OnHighSpeedEnd():
    End_H = -1
    SetProcessorSpeed(L)

# 실행 루프 예시
SystemLoop():
    while system_running:
        if current_time == End_H:
            OnHighSpeedEnd()

 

• StaticHighSpeed(): 모든 태스크 집합에 대해 마감시간 보장 가능한 고속 계산
• UtilizationSpeed(): 총 태스크 부하 기준으로 가능한 최소 속도 계산
• PreemptCurrentJob(): 현재 작업이 블로킹 중이 아닌지 확인
• SetProcessorSpeed(H): 블로킹이 발생한 경우 빠르게 마감시간을 맞추기 위해 고속 전환
• End_H: 고속 모드 유지 시간

 

 

Lemma 2: DSDR의 실행 시간 예산이 마감 전에 소진되는지 보장

다음 조건이 만족되면 DSDR에서 모든 Runtime과 FRT List 항목은 마감 전에 소진된다:
$$\sum_{i+1}^{j}\frac{E_i}{P_i}+\frac{max\{G_k|P_k<P_j\}}{P_j}\leq H, \,\,\,\,\sum_{i=1}^{n}\frac{E_i}{P_i}\leq L $$

증명:

1. 모순 가정: 런타임 또는 FRT 리스트가 Deadline까지 사용되지 못했다.
2. 시점 $t$에서 미사용 런타임 존재, $t_1$을 정의 (그 전에 마감된 Job 없음)
3. 두 경우로 나눔:
   • (1) A 타입 런타임(해당 기간 내 Job 런타임)만 소비 -> $\sum E_i/P_i > L \cdot (t-t_1)$이어야 함 -> 모순
   • (2) B 타입 런타임(앞 서 생성된 여유 시간)까지 소비한 경우 -> 이전 Blocking 및 재할당을 감안해도 계산 불가 -> 모순

직관:

• DSDR은 여유 시간을 누적 저장(FRT 리스트) 했다가 필요한 Job에 배분
• 실행 중인 Job이 Blocking없이 끝나면, 남는 시간은 다른 Job에 활용됨 
• 이 방식으로도 Deadline을 보장할 수 있음을 수학적 입증

 

Theorem 4: DSDR의 전체 타당성

DSDR은 다음 조건을 만족하면 Deadline을 보장하면서 실행 가능:
$$\sum_{i+1}^{j}\frac{E_i}{P_i}+\frac{max\{G_k|P_k<P_j\}}{P_j}\leq H, \,\,\,\,\sum_{i=1}^{n}\frac{E_i}{P_i}\leq L $$

증명: 

• Lemma 1,2에 의해, 모든 런타임과 여유 런타임은 마감 전에 소비됨 -> Deadline  qhwkd

직관:

• DSDR은 Dual Speed를 기반으로 확장한 모델
• 사용되지 않은 여유 런타임을 똑똑하게 재활용하여 에너지를 추가 절감하면서도 실시간 제약을 지킴

# 초기화
H = StaticHighSpeed()
L = UtilizationSpeed()
End_H = -1
FRT = []  # Free Run Time 리스트 (각 항목은 [시간, deadline])

# Job 도착 시
OnJobArrival(Job J):
    J.E_remaining = J.WCET
    J.R = J.WCET / L  # 초기 런타임 할당
    if J.priority > current_job.priority:
        if PreemptCurrentJob():
            Execute(J)
        else:
            # 블로킹 → 고속 전환
            base_speed = H
            End_H = max(End_H, current_job.deadline)
            SetProcessorSpeed(H)

# Job 실행 시
OnJobExecutionStart(Job J):
    if FirstExecution(J) and base_speed == H:
        reclaimed = J.R - (J.WCET / H)
        FRT.append([reclaimed, End_H])
        J.R = J.WCET / H

    usable_runtime = J.R + GetFRTBefore(J.deadline)
    required_speed = (J.E_remaining * S_max) / usable_runtime
    SetProcessorSpeed(ceil(required_speed))  # 실제 지원 가능한 가장 작은 상위 속도로 설정
    Execute(J)

# Job 완료 시
OnJobCompletion(Job J):
    if J.R > 0:
        FRT.append([J.R, J.deadline])  # 사용하지 않은 런타임을 회수

# 고속 구간 종료
OnHighSpeedEnd():
    End_H = -1
    base_speed = L

# FRT 리스트에서 usable time 계산
GetFRTBefore(deadline):
    usable = 0
    for block in FRT:
        if block.deadline <= deadline:
            usable += block.time
    return usable

• J.E_remaining: 남은 실행 시간 (WCET에서 줄어들며 추적)
• J.R: job이 할당받은 런타임(실제 소요 시간은 속도에 따라 달라짐)
• FirstExecution(): job이 처음 실행되는 경우 여부
• FRT: job의 미사용 런타임을 모아 둔 리스트 (동적 재분배에 사용)
• required_speed: 현재 job을 주어진 시간 내에 완료하기 위해 필요한 속도
• ceil(required_speed): CPU는 연속적인 속도를 지원하지 않으므로 상위 정수 속도로 설정
• base_speed == H: 현재 job이 블로킹 상황으로 인해 고속이 필요한 경우

 

항목	DS 알고리즘	DSDR 알고리즘
속도 프로파일	고속(H) / 저속(L) 두 가지	H, L + 동적 속도 조정
런타임 예산 추적	없음	job마다 런타임 R 추적
FRT 리스트	없음	미사용 런타임 재활용
고속 구간 조건	블로킹 발생 시	동일 + 여유 런타임 조건에 따라 조절
에너지 절감 효과	좋음	더 큼 (최대 80%)

 

 

REF

F. Zhang and S. T. Chanson, "Processor Voltage Scheduling for Real-Time Tasks with Non-Preemptible Sections," Proceedings 23rd IEEE Real-Time Systems Symposium, 2002, Austin, TX, USA, 2002, pp. 235-245, doi: 10.1109/REAL.2002.1181576.