# A Work-Demand Analysis Compatible with Preemption-Aware Scheduling for Power-Aware Real-Time Tasks

Authors: Da-Ren Chen; Mu-Yen Chen; You-Shyang Chen; Lin-Chih Chen
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Due to the importance of slack time utilization for power-aware scheduling algorithms,we propose a work-demand analysis method called parareclamation algorithm (PRA) to increase slack time utilization of the existing real-time DVS algorithms. PRA is an online scheduling for power-aware real-time tasks under rate-monotonic (RM) policy. It can be implemented and fully compatible with preemption-aware or transition-aware scheduling algorithms without increasing their computational complexities. The key technique of the heuristics method doubles the analytical interval and turns the deferrable workload out the potential slack time. Theoretical proofs show that PRA guarantees the task deadlines in a feasible RM schedule and takes linear time and space complexities. Experimental results indicate that the proposed method combining the preemption-aware methods seamlessly reduces the energy consumption by 14% on average over their original algorithms.


---

## Body

## 1. Introduction

Power management is increasingly becoming a design factor in portable and hand-held computing/communication systems. Energy minimization is critically important for devices such as laptop computers, smartphones, PDAs, wireless sensor networks (WSNs), and other mobile or embedded computing systems simply because it leads to extended battery lifetime. The power consumption problem has been addressed in the last decade with a multidimensional effort by the introduction of engineering components and devices that consume less power, low power techniques involving the designs of VLSI/IC, computer architecture, algorithm, and compiler developments.Recently, dynamic power management (DPM) and dynamic voltage scaling (DVS) have been employed as available techniques to reduce the energy consumption of CMOS microprocessor system. DPM changes the power state of cores on chip to lower the energy consumption according to the performance constraints. DVS involves dynamically adjusting the voltage and frequency (hence, the CPU speed). By reducing the frequency at which a component operates, a specific operation will consume less energy but may take longer to complete. Although reducing the frequency alone will reduce the average energy used by a processor over that period of time, it may not always deliver a reduction in energy consumption overall, because the power consumption is linearly dependent on the increased time and quadratically dependent on the increased/decreased voltage. In the context of dynamic voltage scaled processors, DVS in real-time systems is a problem that assigns appropriate clock speeds to a set of periodic tasks and adjusts the voltage accordingly such that no task misses its predefined deadline while the total energy savings in the system is maximized.Many studies have proposed different real-time scheduling based on different system models [1–9], such as online and offline scheduling, handling discrete/continuous voltage levels, assuming average-case execution time (ACET), best-case execution time (BCET), or worst-case execution time (WCET) of each task, allowing intratask/intertask voltage transitions, and assuming fixed/dynamic priority assignment. These approaches have a common objective and encounter the same difficulties. Because reducing the supply voltage decreases the clock speed of processors [10], most DVS algorithms for real-time systems reduce supply voltage dynamically to the lowest possible level while satisfying the soft/hard timing constraints of each task. To satisfy the timing constraints of real-time tasks, DVS technique must utilize available slack time when adjusting voltage/speed levels. Consequently, the energy efficiency of a DVS algorithm markedly depends on the accuracy of computing available slack time.Work-demand analysis on embedded real-time scheduling has been investigated by previous studies [3, 5–7, 11]. Pillai and Shin [7] proposed a cycle-conserving rate-monotonic (ccRM) scheduling scheme that contains offline and online algorithms. The offline algorithm computes the WCET of each task and derives the maximum speed needed to meet all tasks deadlines. It recomputes the utilization by comparing the actual time for completed tasks with WCET schedule. In other words, when a task completes early, they have to compare the used actual processor cycles to a precomputed worst-case execution time schedule. This WCET schedule is also called canonical schedule [1] whose length could be the least common multiplier of task periods. ccRM is a conservative method, as it only considers possible slack time before the next task arrival (NTA) of a current job. Gruian proposed a DVS method for offline task stretching and online slack distribution [3]. The offline part of this method consists of two separate techniques. One focuses on the intratask stochastic voltage scheduling that employs a task-execution length probability function. The second technique computes stretching factors by using a response time analysis. It is similar to Pillar and Shin’s offline technique, but instead of adopting a stretching factor for all tasks before NTA, Gruian assigns a different stretching factor to the individual task within the longest task period. Kim et al. [6] proposed a greedy online algorithm called the low-power work-demand analysis (lpWDA) that derives slack from low-priority tasks, as opposed to the method in [3, 7] that gains slack time from high-priority tasks. This algorithm also balances the gap in voltage levels between high-priority and low-priority tasks. Its analysis interval limited by the longest of task periods is longer than NTA. Thus, lpWDA gains more energy saving than the previous rate-monotonic (RM) DVS schemes applying NTA. Many slack time analysis methods considered additional assumptions [4, 11, 12]. Kim et al. proposed a preemption-aware DVS algorithm based on lpWDA, which is composed of accelerated-completion (lpWDA-AC) and delayed-preemption (lpWDA-DP) techniques to decrease the preemption times of DVS schedules [11]. lpWDA-AC attempts to avoid preemption by adjusting voltage/clock speed, such that it is higher than the lowest possible values computed using lpWDA. lpWDA-DP postpones preemption points by delaying an activated high-priority task as late as possible while guaranteeing a feasible task schedule. Both techniques reduce energy consumption more than the initial ccRM and lpWDA techniques on the assumption of context-switching overhead. Mochocki et al. in [12] also proposed a transition-aware DVS algorithm for decreasing the number of voltage/speed adjustments, called the low-power limited-demand analysis with transition overhead (lpLDAT) scheme, which accounts for both time and energy transition overhead. Its algorithm computes an efficient speed level based on average-case workload; notably, this speed can be used as a limiter. If the limiter is higher than the speed predicted by lpWDA, lpLDAT knows that lpWDA is being too aggressive and applies the limiter to the present schedule. On the assumption of transition overhead, this technique with slack time analysis also saves considerable energy when compared with that by the previous methods. He and Jia [4] developed a fixed-priority scheduling with threshold (FPPT) scheme that eliminates unnecessary context switches, thereby saving energy. FPPT assigns each task a pair of predefined priority and corresponding preemption threshold. He et al. applied a novel algorithm to compute a static slowdown factors by formulating the problem as a linear optimization problem. In addition, they considered energy consumption of a task set under different preemption threshold assignments.Recently, experimental results obtained by Kim et al. [6] indicated that recent DVS algorithms for fixed-priority real-time tasks are less efficient than that of dynamic-priority tasks, leading to more improvements for a better DVS method. The main reason for energy inefficiency of RM DVS scheduling is that, in RM schedules, priority-based slack-stealing methods do not work as efficiently as they do in earliest-deadline first (EDF) scheduling [6]. In the EDF schedules, high-priority tasks play an efficient slack distributor of tasks because their slack can be utilized fully by tasks starting before NTA. Therefore, the energy saving achieved by EDF scheduling algorithms, such as that by the ccEDF [7], DRA, and AGR [1] is close to the theoretical lower bound [13].


## 2. Motivations

So far, there are a large number of studies on DVS-based RM scheduling for energy saving [1–4, 6–8, 11–14]; most existing studies are proposed for computing and predicting the length and occurrence of slack time. The reason is that the more precise estimation on the slack time, the more energy efficiency we obtain. Those methods for computing available slack time either construct a canonical schedule and compare it to current schedule or propose best-effort algorithms under empirical rules and heuristics. Those methods adopting different strategies and assumptions such as task preemption or voltage transition time on the similar models gain considerable energy saving, but few of them can be combined without difficulty to further enhance their performance. Additionally, modern processor with DVS or DPM feature must be equipped with dc-to-dc converter that varies the processor speed in appropriate levels and requires additional switching time and power [15]. It is harmful to power saving in a system when many fragments of short slack time appear. Many of those methods also propose the notions of postponing and advancing task execution for increasing the length of slack time. Their performances for accumulating a continuous slack time are not impressive due to short analysis interval adopted in the schedules. Therefore, it is necessary to study a transplantable method that can cooperate with different existing methods without modification. This idea originate from the layered architecture used in designing computer software, hardware, and communications in which system or network components are isolated in layers so that changes can be made in one layer without affecting the others. The proposed method according the notion also requires the ability to compute and accumulate the slack time solely. By applying the layered architecture, it can also pass the slack time to lower-layered methods and reveals synergy effect to enhance overall energy saving.In this paper, we propose an online work-demand analysis called parareclamation algorithm (PRA) for RM scheduling which computes the length of potential slack in an interval which is two times longer than the longest task periods. PRA does not rely on the simulation for stochastic data which usually varies according to different applications, and can be applied to many RM scheduling algorithms with various criteria. Moreover, the proposed algorithm has a time complexity of O(n) where n is the number of tasks. In other words, it does not increase computational complexity of the existing online RM scheduling algorithms. Experimental results indicate that existing RM DVS algorithms combined with the proposed method can reduce energy consumption by 5%–21% compared with that by initial algorithms such as lpWDA and lpLDAT.The remainder of this paper is organized as follows. Section3 introduces the preliminaries of power-aware real-time scheduling. Section 4 introduces our technique and algorithm. Section 5 provides theorems to prove the schedulability of PRA as well as lpWDA. We present the performance evaluation in Section 6. Section 7 gives conclusions and the directions for future work.


## 3. Preliminaries

This paper focuses on how to obtain additional slack for existing RM DVS scheduling methods. Many slack time analysis techniques with different purposes (e.g., transition-aware and preemption-aware schemes) can utilizePRA easily; throughout this paper, these techniques are called host algorithms of PRA. This section also outlines the ideas underlying the lpWDA algorithm. Other techniques, such as the lpLDA, lpWDA-AC, lpWDA-DP [11], and lpLDAT [12] techniques, are abridged.


### 3.1. System Model

This paper considers preemptive hard real-time systems in which periodic real-time tasks are scheduled under an RM scheduling policy. The DVS processor used in the model operates at a finite set of supply voltage levelsV={v1,…,vmax}, each with an associated speed. Processor speed is normalized by Smax=1 corresponding to vmax=1, yielding a set S={s1,…,1} of speed levels. A set of n periodic tasks is denoted by T={τ1,τ2,…,τn}, where the tasks are assumed mutually independent. Each task τi is described by its worst-case execution cycles wci and average-case execution cycles aci (wci≥aci). Throughout this paper, the execution cycles of each task are called work for short. Additionally, each task τi has a shorter period length pi (i.e., a higher priority) than that of τj when i<j, and pn is the longest of task periods. The relative deadline di of τi is assumed equal to its period length pi. Each task is invoked periodically by a job, and the kth job of task τi is τi,k. The first job of each task is assumed activated at time t=0. Each job is described by a release time, ri,j, deadline, di,k, and number of cycles that have been executed exik. The utilization U of a task set T is denoted by ∑τi∈T‍(wci/pi). During run time, we refer to the earliest job of each task not completed as the current job for that task, and that job is indexed with cur. The deadline of the current job for task τi is dicur, and exicur denotes the number of cycles that the current job of τi has executed.Without loss of generality, whenτi is the first scheduled task after time rn,k-1, where i≠n, the bottleneck (shortened to bn) is the next release time of τn (i.e., the rn,k). In the work-demand analysis method, available slack in the interval [bn, rn,k+1) is estimated.


### 3.2.  Low-Power Work-Demand Analysis (lpWDA)

This section briefly introduces an online DVS scheme calledlpWDA [6]. Notations eExchange, ℓαright, and τasyn belong to PRA algorithm and are presented in Section 4. In line 2 of Algorithm 1, ε is an infinitesimal, and readyQ contains the currently activated tasks, and its subset, ΓαACT(t), containing the active tasks is
(1)ΓαACT(t):={τκ∣κ<α,τκ∈readyQ}.
In the lpWDA, the tasks in readyQ are scheduled according to RM priority policy. When a task is activated (released), its job τα is moved to readyQ, and the remaining WCET of this job is set to wci, which is Wirem(t)=wci. When τα is executed at time t, loadα(t) is the amount of work required to be processed in [t,dα).Algorithm 1:
IpWDA (PRA with ***). Compute the available execution time and set the voltage/clock speed for τα.
(
1
) set uda:=pα,eExchange:=0 and τasyn:=∅;
(
2
)  Compute Hα(t):=∑τk∈TαACT(t)wkrem(t)+∑i=1α-1(⌊(udα-ε)/pi⌋-⌈(t+ε)/pi⌉)·wi;
(
3
)  When a job τα is activated, set wkrem(t):=wα;
(
4
)  When a job τα is completed or preempted, UpdateLoadInfo(wαrem(t),udα,Hα(t));
(
5
)  When a job τα is scheduled for execution
(
6
)   ***eExchange:=PRA(t,T);          //get additional slack time
(
7
)  ***ifrα=τasyn and ℓαright<eExchangethenτα has the lowest priority in readyQ(t);
(
8
)  slackα(t):=ClacSlackTime(eExchange);     //get slack time
(
9
)  set the clock frequency as fclk:=wαrem(t)/(slackα(t)+wαrem(t))·fmax;
(
10
)  fclk:= max{fclk,fACL};
(
11
)  Set the voltage accordingly;In Algorithms1, 2, and 3 and Procedure 1, lpWDA performs in the following steps. First, the system is initialized by setting the initial upcoming deadlines (ud) and remaining worst-case execution (wrem) of each task. When τα is active at time t, notation udk of each task τk is defined as follows [6]:
(2)udk=⌈t+εpk⌉×pk,
where ε is the infinitesimal. The jobs which are active during [t,max{udk(t)}] will be examined for slack estimation. Hα(t) denotes the estimation of higher-priority work that must be executed before udα (lines 1-2). Whenever a job τα is completed or preempted at time t, the remaining workwαrem(t), upcoming deadline udα, and high-priority workHα(t) are updated in line 4. In lines 5–8, when a job τα is scheduled for execution at time t, Algorithm 2 computes the available slack for τα according to Hβ(t) and Lβ(t) (see lines 13 and 14), where udβ is the earliest upcoming deadline with respect to τα. Notably, function Lβ(t) computing the amount of low-priority work is performed recursively until it finds τγ with the longest of task periods and lowest priority with respect to τα. As defined in Section 3.1, the length of interval [0, bn) is pγ. Then, lpWDA computes the length of slack-time stealing from low-priority tasks in the interval [rα,bn) and applies the slack to the current job. Therefore, Algorithms 2 and 3 play crucial roles in slack-time analysis and dominate the run time complexity of lpWDA algorithm. Formally, to describe the slack analysis method using lpWDA, the following notations are defined:loadα(t): the amount of work required to be processed in interval [t, dα);slackα(t): the available slack for τα scheduled at time t can be computed as follows:
(3)slackα=dα-t-loadα(t).In (3), loadα(t) consists of three types of work: (1) Wαrem(t), (2) Hα(t) from the higher-priority tasks, and (3) Lα(t) from the lower-priority tasks. The workrequired by higher-priority tasks is derived as follows:
(4)Hα(t)=Hαpast(t)+Hαfuture,
where Hαpast(t) denotes the workrequired by uncompleted tasks released before t, and Hαfuture(t) denotes the work released during [t,dα]. We compute Hαpast(t) and Hαfuture(t) as follows:
(5)Hαpast(t)=∑τκ∈ΓαACT(t)‍Wκrem(t),Hαfuture(t)=∑i=1α-1‍(⌊dα-εpi⌋-⌈t+εpi⌉+1)·wci,
where ε is the infinitesimal. According to the above statements, the amount of work required by the scheduled task τα can be formulated as
(6)Hα(t)=∑τκ∈ΓαACT(t)‍Wκrem(t)+∑i=1α-1‍(⌊dα-εpi⌋-⌈t+εpi⌉+1)·wci,(7)Lα(t)=(loadβ(t)-wαrem(t)-Hα(t)-(udβ(t)-dα))+,(8)loadα(t)=Hα(t)+Lα(t)+wαrem(t),
where notation x+ stands for max(x,0). Equations (6), (7), and (8) are repeated iteratively until τα is the lowest priority task in T (i.e., Lα(t)=0). Conceptually, lpWDA uses this linear-time heuristics to estimate available slack in an interval up to the upcoming deadline of lower-priority tasks.Algorithm 2:
CalcSlackTime(additional slack eExchange).
Input: the active task τα, readyQ and current time t
Output: the slack time slackα(t) for τα
(
12
) Identify the task τβ that has the earliest upcoming deadline among tasks whose
priorities are not higher than that of τa;
(
13
) Lβ(t):=CalcLowerPriorityWork(τβ, t, eExchange);
(
14
) loadβ(t):=wβrem(t)+Hβ(t)+Lβ(t);
(
15
) slackα(t):= max(0,udβ-t-loadβ);
(
16
)  return(slackα(t));Algorithm 3:
CalcLowerPriorityWork(additional slack eExchange).
Input: a reference task τβ and current time t
Output: the amount of lower-priority work needed to be done before udβ
(
17
) ifτβ is identical to τnthenreturn 0;
(
18
) Identify the task τr that has the earliest upcoming deadline among the tasks
whose priorities are lower than that of τβ;
(
19
) Lr(t):=CalcLowerPriorityWork(τr, t, eExchange);
(
20
) loadr(t):=wβrem(t)+Hr(t)+Lr(t);
(
21
)  ***ifudr is multiple of pnthenudr:=udr+eExchange;
(
22
) Lβ(t):= max(0,loadr(t)-wβ(t)-Hβ(t)-udr+udβ);
(
23
)  returnLβ(t);Procedure 1:
PRA (time t, task set T).
Input
t: current time, Tb=T-{τn}
(
1
)
setb=n-1,eminExchange←∞,k=⌈(t+ε)/pn⌉,ℓ←0, Tbn={τi∣i<n and pi spans astride the bn};
(
2
) ifSyn(Tb,k):==0
(
3
)  fori:=1ton-1
(
4
)   ifSyn(Tb-τi,k):==0
(
5
)     then continue;
(
6
)   τasyn:=τi;
(
7
)  ifℓ≤0thenτasyn:=∅;
(
8
)  Compute the value of easynExchange;
(
9
) else ifSyn(Tb,k)>0oreasynExchange≤0
(
10
)  thenCompute the values of ebn and eslack;
(
11
)  ifeasynExchange≤0theneminExchange:= min{ebn,eslack};
(
12
)  elseeminExchange:= min{easynExchange,ebn,eslack};
(
13
) Choose a job τδ∈Tbn with ℓδright≥eminExchange and wcδ≥eminExchange;
(
14
) When τδ∈readyQ, change the priority of job τδ lower than that of job τn in readyQ;
(
15
) ReturneminExchange;


### 3.3. Motivational Example

The proposed method is to providelpWDA-based algorithms (e.g., lpWDA, lpLDAT, lpWDA-DP, and lpWDA-AC) with a subroutine to improve their work-demand analysis. The main advantage is that PRA can be independent of each function-specific slack analysis method. For instance, the main purpose of lpWDA-AC and lpWDA-DP techniques is to decrease context-switch overhead while that of lpLDAT is to reduce transition time and energy overhead. PRA can work together with these lpWDA-based algorithms to enhance their slack computation capability.Example 1.
Consider a periodic task setT in Table 1, which presents the period length, WCET, and ACET of each task. Figure 1(a) presents the execution schedule under the worst-case workload in the first hyperperiod. Figure 1(b) shows the speed schedule using lpWDA algorithm for task set T and assumes that actual work of each task equals its ACET. Before assigning τ1,1 at time t=0, lpWDA computes available slack time in an interval up to d3,1=6 by calling Algorithm 3, recursively. However, interval [0,6) has no slack-time under the WCET schedule. If the length of the analysis interval is extended to 2×pn, one unit of slack time is derived from 2×pn-∑i=1n‍⌊2pn/pi⌋×wci. The slack in [11,12) can be moved backward to the current scheduling point by a deferred execution of earlier work. For instance, in Figure 1(a), the slack in interval [11,12) can be exchanged with the work in interval [7,8), and then slack in interval [7,8) can be exchanged with the work in interval [4,5), and it can be exchanged once again with the work in interval [2,3). Finally, the slack in interval [2,3) can be exchanged with the work in interval [1,2). Therefore, τ1,1 is scheduled with speed S1,1=(wci/(wci+1)) (Figure 1(c)). Additional slack can be reclaimed without deadline missing from the interval that is, two times longer than the longest task period. Notably, this idea actually neither moves all of the jobs of a schedule to readyQ (e.g., t=0) nor Exchanges the slack with work for using this slack time. However, this primitive idea does not work in some situations. For example, in Figure 1(d), when p2 is increased to 6, slack in the interval [11,12) cannot be transferred before t=6. In fact, jobs τ1,3,τ2,2, and τ3,2 are released simultaneously at time 6. The slack in interval [11,12) cannot follow this idea, because a deadline is likely to be missed by one of those three jobs. Our goal is to devise an efficient work-demand analysis method that obtains additional slack while satisfying th tasks’ deadline.Table 1
An example of real-time task setT.
Task
Period (pi)
WCET (wci)
ACET (aci)
τ
1
3
1.0
0.5
τ
2
4
1.0
0.5
τ
3
6
2.0
1.0The intertask voltage scheduling examples of (a) worst-case scheduling, (b)lpWDA, (c) lpWDA + PRA, and (d) a modified worst-case schedule.
(a)
(b)
(c)
(d)


## 3.1. System Model

This paper considers preemptive hard real-time systems in which periodic real-time tasks are scheduled under an RM scheduling policy. The DVS processor used in the model operates at a finite set of supply voltage levelsV={v1,…,vmax}, each with an associated speed. Processor speed is normalized by Smax=1 corresponding to vmax=1, yielding a set S={s1,…,1} of speed levels. A set of n periodic tasks is denoted by T={τ1,τ2,…,τn}, where the tasks are assumed mutually independent. Each task τi is described by its worst-case execution cycles wci and average-case execution cycles aci (wci≥aci). Throughout this paper, the execution cycles of each task are called work for short. Additionally, each task τi has a shorter period length pi (i.e., a higher priority) than that of τj when i<j, and pn is the longest of task periods. The relative deadline di of τi is assumed equal to its period length pi. Each task is invoked periodically by a job, and the kth job of task τi is τi,k. The first job of each task is assumed activated at time t=0. Each job is described by a release time, ri,j, deadline, di,k, and number of cycles that have been executed exik. The utilization U of a task set T is denoted by ∑τi∈T‍(wci/pi). During run time, we refer to the earliest job of each task not completed as the current job for that task, and that job is indexed with cur. The deadline of the current job for task τi is dicur, and exicur denotes the number of cycles that the current job of τi has executed.Without loss of generality, whenτi is the first scheduled task after time rn,k-1, where i≠n, the bottleneck (shortened to bn) is the next release time of τn (i.e., the rn,k). In the work-demand analysis method, available slack in the interval [bn, rn,k+1) is estimated.


## 3.2.  Low-Power Work-Demand Analysis (lpWDA)

This section briefly introduces an online DVS scheme calledlpWDA [6]. Notations eExchange, ℓαright, and τasyn belong to PRA algorithm and are presented in Section 4. In line 2 of Algorithm 1, ε is an infinitesimal, and readyQ contains the currently activated tasks, and its subset, ΓαACT(t), containing the active tasks is
(1)ΓαACT(t):={τκ∣κ<α,τκ∈readyQ}.
In the lpWDA, the tasks in readyQ are scheduled according to RM priority policy. When a task is activated (released), its job τα is moved to readyQ, and the remaining WCET of this job is set to wci, which is Wirem(t)=wci. When τα is executed at time t, loadα(t) is the amount of work required to be processed in [t,dα).Algorithm 1:
IpWDA (PRA with ***). Compute the available execution time and set the voltage/clock speed for τα.
(
1
) set uda:=pα,eExchange:=0 and τasyn:=∅;
(
2
)  Compute Hα(t):=∑τk∈TαACT(t)wkrem(t)+∑i=1α-1(⌊(udα-ε)/pi⌋-⌈(t+ε)/pi⌉)·wi;
(
3
)  When a job τα is activated, set wkrem(t):=wα;
(
4
)  When a job τα is completed or preempted, UpdateLoadInfo(wαrem(t),udα,Hα(t));
(
5
)  When a job τα is scheduled for execution
(
6
)   ***eExchange:=PRA(t,T);          //get additional slack time
(
7
)  ***ifrα=τasyn and ℓαright<eExchangethenτα has the lowest priority in readyQ(t);
(
8
)  slackα(t):=ClacSlackTime(eExchange);     //get slack time
(
9
)  set the clock frequency as fclk:=wαrem(t)/(slackα(t)+wαrem(t))·fmax;
(
10
)  fclk:= max{fclk,fACL};
(
11
)  Set the voltage accordingly;In Algorithms1, 2, and 3 and Procedure 1, lpWDA performs in the following steps. First, the system is initialized by setting the initial upcoming deadlines (ud) and remaining worst-case execution (wrem) of each task. When τα is active at time t, notation udk of each task τk is defined as follows [6]:
(2)udk=⌈t+εpk⌉×pk,
where ε is the infinitesimal. The jobs which are active during [t,max{udk(t)}] will be examined for slack estimation. Hα(t) denotes the estimation of higher-priority work that must be executed before udα (lines 1-2). Whenever a job τα is completed or preempted at time t, the remaining workwαrem(t), upcoming deadline udα, and high-priority workHα(t) are updated in line 4. In lines 5–8, when a job τα is scheduled for execution at time t, Algorithm 2 computes the available slack for τα according to Hβ(t) and Lβ(t) (see lines 13 and 14), where udβ is the earliest upcoming deadline with respect to τα. Notably, function Lβ(t) computing the amount of low-priority work is performed recursively until it finds τγ with the longest of task periods and lowest priority with respect to τα. As defined in Section 3.1, the length of interval [0, bn) is pγ. Then, lpWDA computes the length of slack-time stealing from low-priority tasks in the interval [rα,bn) and applies the slack to the current job. Therefore, Algorithms 2 and 3 play crucial roles in slack-time analysis and dominate the run time complexity of lpWDA algorithm. Formally, to describe the slack analysis method using lpWDA, the following notations are defined:loadα(t): the amount of work required to be processed in interval [t, dα);slackα(t): the available slack for τα scheduled at time t can be computed as follows:
(3)slackα=dα-t-loadα(t).In (3), loadα(t) consists of three types of work: (1) Wαrem(t), (2) Hα(t) from the higher-priority tasks, and (3) Lα(t) from the lower-priority tasks. The workrequired by higher-priority tasks is derived as follows:
(4)Hα(t)=Hαpast(t)+Hαfuture,
where Hαpast(t) denotes the workrequired by uncompleted tasks released before t, and Hαfuture(t) denotes the work released during [t,dα]. We compute Hαpast(t) and Hαfuture(t) as follows:
(5)Hαpast(t)=∑τκ∈ΓαACT(t)‍Wκrem(t),Hαfuture(t)=∑i=1α-1‍(⌊dα-εpi⌋-⌈t+εpi⌉+1)·wci,
where ε is the infinitesimal. According to the above statements, the amount of work required by the scheduled task τα can be formulated as
(6)Hα(t)=∑τκ∈ΓαACT(t)‍Wκrem(t)+∑i=1α-1‍(⌊dα-εpi⌋-⌈t+εpi⌉+1)·wci,(7)Lα(t)=(loadβ(t)-wαrem(t)-Hα(t)-(udβ(t)-dα))+,(8)loadα(t)=Hα(t)+Lα(t)+wαrem(t),
where notation x+ stands for max(x,0). Equations (6), (7), and (8) are repeated iteratively until τα is the lowest priority task in T (i.e., Lα(t)=0). Conceptually, lpWDA uses this linear-time heuristics to estimate available slack in an interval up to the upcoming deadline of lower-priority tasks.Algorithm 2:
CalcSlackTime(additional slack eExchange).
Input: the active task τα, readyQ and current time t
Output: the slack time slackα(t) for τα
(
12
) Identify the task τβ that has the earliest upcoming deadline among tasks whose
priorities are not higher than that of τa;
(
13
) Lβ(t):=CalcLowerPriorityWork(τβ, t, eExchange);
(
14
) loadβ(t):=wβrem(t)+Hβ(t)+Lβ(t);
(
15
) slackα(t):= max(0,udβ-t-loadβ);
(
16
)  return(slackα(t));Algorithm 3:
CalcLowerPriorityWork(additional slack eExchange).
Input: a reference task τβ and current time t
Output: the amount of lower-priority work needed to be done before udβ
(
17
) ifτβ is identical to τnthenreturn 0;
(
18
) Identify the task τr that has the earliest upcoming deadline among the tasks
whose priorities are lower than that of τβ;
(
19
) Lr(t):=CalcLowerPriorityWork(τr, t, eExchange);
(
20
) loadr(t):=wβrem(t)+Hr(t)+Lr(t);
(
21
)  ***ifudr is multiple of pnthenudr:=udr+eExchange;
(
22
) Lβ(t):= max(0,loadr(t)-wβ(t)-Hβ(t)-udr+udβ);
(
23
)  returnLβ(t);Procedure 1:
PRA (time t, task set T).
Input
t: current time, Tb=T-{τn}
(
1
)
setb=n-1,eminExchange←∞,k=⌈(t+ε)/pn⌉,ℓ←0, Tbn={τi∣i<n and pi spans astride the bn};
(
2
) ifSyn(Tb,k):==0
(
3
)  fori:=1ton-1
(
4
)   ifSyn(Tb-τi,k):==0
(
5
)     then continue;
(
6
)   τasyn:=τi;
(
7
)  ifℓ≤0thenτasyn:=∅;
(
8
)  Compute the value of easynExchange;
(
9
) else ifSyn(Tb,k)>0oreasynExchange≤0
(
10
)  thenCompute the values of ebn and eslack;
(
11
)  ifeasynExchange≤0theneminExchange:= min{ebn,eslack};
(
12
)  elseeminExchange:= min{easynExchange,ebn,eslack};
(
13
) Choose a job τδ∈Tbn with ℓδright≥eminExchange and wcδ≥eminExchange;
(
14
) When τδ∈readyQ, change the priority of job τδ lower than that of job τn in readyQ;
(
15
) ReturneminExchange;


## 3.3. Motivational Example

The proposed method is to providelpWDA-based algorithms (e.g., lpWDA, lpLDAT, lpWDA-DP, and lpWDA-AC) with a subroutine to improve their work-demand analysis. The main advantage is that PRA can be independent of each function-specific slack analysis method. For instance, the main purpose of lpWDA-AC and lpWDA-DP techniques is to decrease context-switch overhead while that of lpLDAT is to reduce transition time and energy overhead. PRA can work together with these lpWDA-based algorithms to enhance their slack computation capability.Example 1.
Consider a periodic task setT in Table 1, which presents the period length, WCET, and ACET of each task. Figure 1(a) presents the execution schedule under the worst-case workload in the first hyperperiod. Figure 1(b) shows the speed schedule using lpWDA algorithm for task set T and assumes that actual work of each task equals its ACET. Before assigning τ1,1 at time t=0, lpWDA computes available slack time in an interval up to d3,1=6 by calling Algorithm 3, recursively. However, interval [0,6) has no slack-time under the WCET schedule. If the length of the analysis interval is extended to 2×pn, one unit of slack time is derived from 2×pn-∑i=1n‍⌊2pn/pi⌋×wci. The slack in [11,12) can be moved backward to the current scheduling point by a deferred execution of earlier work. For instance, in Figure 1(a), the slack in interval [11,12) can be exchanged with the work in interval [7,8), and then slack in interval [7,8) can be exchanged with the work in interval [4,5), and it can be exchanged once again with the work in interval [2,3). Finally, the slack in interval [2,3) can be exchanged with the work in interval [1,2). Therefore, τ1,1 is scheduled with speed S1,1=(wci/(wci+1)) (Figure 1(c)). Additional slack can be reclaimed without deadline missing from the interval that is, two times longer than the longest task period. Notably, this idea actually neither moves all of the jobs of a schedule to readyQ (e.g., t=0) nor Exchanges the slack with work for using this slack time. However, this primitive idea does not work in some situations. For example, in Figure 1(d), when p2 is increased to 6, slack in the interval [11,12) cannot be transferred before t=6. In fact, jobs τ1,3,τ2,2, and τ3,2 are released simultaneously at time 6. The slack in interval [11,12) cannot follow this idea, because a deadline is likely to be missed by one of those three jobs. Our goal is to devise an efficient work-demand analysis method that obtains additional slack while satisfying th tasks’ deadline.Table 1
An example of real-time task setT.
Task
Period (pi)
WCET (wci)
ACET (aci)
τ
1
3
1.0
0.5
τ
2
4
1.0
0.5
τ
3
6
2.0
1.0The intertask voltage scheduling examples of (a) worst-case scheduling, (b)lpWDA, (c) lpWDA + PRA, and (d) a modified worst-case schedule.
(a)
(b)
(c)
(d)


## 4. Work-Demand Computation

Letrn,k be the bn of τi, which is the first scheduled job at time t where t≥rn,k-1. PRA computes the length of additional slack in the interval [bn, rn,k+1). As long as the slack time can be reclaimed at a time earlier than bn, lpWDA can utilize it by postponing lower-priority task and improve energy efficiency of schedules. Why PRA focuses on slack computation in the interval [bn, rn,k+1) while longer or shorter intervals? Even if all job (except τn) periods are within [bn, rn,k+1) and cannot make a target slack be available for the task right side to bn, job τn can still postpone its work for moving the slack forward and approaching bn. For example, in Figure 1(a), when the period length of τ1 is increased from 3 to 4, the slack in interval [11,12) cannot be reclaimed by postponing the work of τ1,3 or τ2,3 because it is hampered at time 8. Therefore, τ3,2 can defer its work and the slack time in [6,7) will be available. On the contrary, if one extends the additional analysis interval such that it is longer than or even several times of pn, job τn cannot move the slack after bn+pn to approach the bn and may be blocked in this interval. For an analytical interval whose length is equal to pn, it has the following advantages. After deriving the amount of slack time which will be available to the tasks nearby bn, those jobs whose period spanning astride the bn can be deferred to reclaim additional slack before bn. That is, the current job can utilize the additional slack by performing a lpWDA-based method. Notably, in an actual scheduling process, PRA does not exchange any work with slack. Instead, it only passes the length of additional slack time for current job to lpWDA and does not affect schedulability of subsequent jobs.To present the proposed method, we define the following notations:(9)Tb=T-{τn},
where b denotes the number of tasks in the set of Tb, b<n, and τn is the task with the longest period in T. A set of tasks are called synchronous at time t if their jobs are released at time t. In an extended analysis interval [bn, rn,k+1), the number of synchronization points of the tasks in Tb can be derived as follows:
(10)Syn(Tb,k)=⌊rn,k+1LCM(Tb)⌋-⌊rn,kLCM(Tb)⌋,
where LCM(Tb) denotes the least common multiplier of task periods in Tb. As shown in Figure 2, the first synchronization point of Tb within the interval [bn, rn,k+1) is derived as
(11)t(Tb,k)=⌈rn,k+1LCM(Tb)⌉×LCM(Tb).
When t(Tb,k)=t∈(rn,k,rn,k+1), slack time is likely to be blocked or shrunken at time t. In Figure 3, when all tasks except τn are synchronized at time t, a slack may not be moved backward from the right to the left side of t. In this case, slack can still be moved to the current time by postponing the execution of the work of τn. When n-1 tasks are synchronized in interval (bn,rn,k+1), we can derive Syn(Tb,k)≥0, and their the earliest synchronization point is derived by t(Tn-1,k). The worst-case execution time in interval (bn,t(Tn-1,k)) is
(12)[t(Tn-1,k)-bn]×U.
Therefore, the available slack for τn,k+1 in this interval is at least
(13)[(t(Tn-1,k)-bn)×(1-U)].
Similarly, when {τi,τn}⊂Tn-2 and τi≠τn, there are n-2 tasks that synchronize at time t(Tn-2,k). The available slack time for τn,k+1 in interval [bn,t(Tn-2,k)) is at least
(14)[(t(Tn-2,k)-bn)×(1-(U-wcipi))].
Therefore, if f of tasks are synchronized in interval [bn,rn,k+1), the minimal available slack time for τn in interval [bn,t(Tn-f,k)) is denoted as
(15)eiExchange=[∑τi∉Tn-f∪{τn}‍(t(Tn-f,k)-bn)×(1-(U-∑τi∉Tn-f∪{τn}‍wcipi))],
where eiExchange denotes the estimated slack in interval [bn,t(Tx,k)). For example, τi does not synchronize with other tasks in Tb (Figure 4). Therefore, one can compute the value of Syn(Tx=Tb-τi,k) for each τi, where x=n-2 and b=n-1. Suppose Syn(Tb-τi,k)>0, the earliest synchronization point of tasks in Tb-τi is derived using (11).Figure 2
An example of task synchronization points.Figure 3
The task periods span astride thebn.The slack reclamation inlpWDA algorithm.
(a)
(b)After deriving available slack time within interval[bn,t(Tb,k)) where b≤n-1, we compute the length of the slack time which is available for the task in interval [bn,t(Tb,k)). We assume Tbn denotes a set of tasks in which task periods go astride the bn. Let τi∈Tbn; the lengths of left and right parts of pi split by bn are defined as ℓileft and ℓiright, respectively, and the longest ℓileft and ℓiright are defined as ℓmaxleft and ℓmaxright, respectively. Additionally, we define
(16)accubn=∑τi∈Tbn‍wci
as the total amount of work in Tbn. As shown in Figure 3, the lengths of ℓmaxleft, ℓmaxright, and accubn limit the maximum length of slack that can be moved in interval [rn,k-1, bn). Consequently, the restriction on the length of slack time is as follows:
(17)ebn=min{ℓmaxleft,ℓmaxright,accubn}.
According to the work demand in a WCET schedule, the slack time in interval [rn,k-1,rn,k+1) is computed as follows:
(18)eslack=2×pn-∑τi∈T‍⌈2×pnpi⌉wci.PRA computes the length of additional slack time within interval [bn, rn,k+1) by (17). It then computes the length of this slack time that can be available for the jobs in interval [rn,k-1, bn) according to (17) and (18). Finally, it changes the priority of a job that goes astride the bn when this job is moved to readyQ according to RM scheduling. In line 1 of Procedure PRA, ε denotes an infinitesimal value.Example 2.
Consider the WCET schedule shown in Figure1(a), τ1,1 is scheduled at time t=0, we set bn=6 and Tbn={τ2,2} because the period of τ2,2 goes astride bn. Procedure PRA computes the length of available slack time from interval [6,12) as follows. When task set T2={τ1,τ2}, Procedure PRA computes Syn(T2,1)=0. Therefore, the bottleneck caused by τ1 and τ2 is t(T2-{τ2,1})=9 and t(T2-{τ1,1})=8, respectively. Line 6 derives ℓ=2 and τasyn=τ1. Equations (14)–(17) derive easynExchange=(9-6)×(1-(11/12-1/3))=1. In line 10, the value of enExchange, ebn, eslack, and accubn is 1, 1, 1, and 2, respectively. The value of eminExchange is 1 by line 12. Therefore, Procedure PRA returns eminExchange=1 to the lpWDA algorithm and passes additional slack eExchange to CalcLowerPriorityWork() in Algorithm 3. Notably, the tasks using PRA still execute under RM priority policy except one of the jobs whose periods span astride the bn. At time t=0, when jobs τ1,1, τ2,1, and τ3,1 enter readyQ at time t=0, τ1,1 has the highest priority and utilizes additional slack eminExchange estimated by PRA. Therefore, job τ1,1 obtains one unit of time of slack and changes its voltage level from 1 to 0.5. On the contrary, if primitive lpWDA performs τ1,1 at time t=0, τ1,1 cannot obtain any slack. When lpWDA executes iteratively, the value of eExchange does not change until τ1,1 is completed. Figure 1(c) presents the scheduling result obtained using Procedure PRA. After completing τ1,1, eminExchange unit of slack has been run out, primitive lpWDA continuously performs voltage scaling on the subsequent jobs of τ1,1. In the case of τ2,1, it begins after τ1,1 (t=1) and obtains one unit of slack time from primitive lpWDA. Therefore, its WCET under voltage v=0.5 is changed to wc2,1=2, and actual execution time is ac2,1=1. At time t=4, job τ2,2 is released and moved to readyQ. Its priority is changed to and lower than the remaining execution time of τ3,1 by executing line 14 in Procedure PRA. Therefore, job τ2,2 begins its work after completing the remaining work of τ3,1. Notably, PRA only changes job’s priority in Tbn and does not affect the feasibility of lpWDA schedule. The correctness proof is discussed later in the next section. Table 2 shows the values of scheduling parameters. The rightmost job in readyQ is being executed at that time. In Algorithm 1, job τδ is a global variable. Whenever job τδ executes and eExchange>0, Procedure PRA lowers its priority to guarantee the timing constraint of jobs τn and τδ.Table 2
Scheduling parameters in Example2.
Time
readyQ
u
d
y
e
E
x
c
h
a
n
g
e
Slack
Voltage
w
c
a
c
0
→
τ
3,1
,
τ
2,1
,
τ
1,1
→
6
1
1
1
/
(
1
+
1
)
=
0.5
2
1
1
→
τ
3,1
,
τ
2,1
→
6
1
1
1
/
(
1
+
1
)
=
0.5
2
1
2
→
τ
3,1
→
6
1
1
2
/
(
2
+
1
)
=
0.67
3
1.5
3
→
τ
3,1
,
τ
1,2
→
6
1
1.5
1
/
(
1
+
1.5
)
=
0.4
2.5
1.25
4
→
τ
2,2
,
τ
3,1
,
τ
1,2
→
6
1
0.5
1
/
(
1
+
1.5
)
=
0.4
2.5
1.25
4.25
→
τ
2,2
,
τ
3,1
→
6
1
1
2
/
(
2
+
1
)
=
0.67
1
0.5
4.75
→
τ
2,2
→
12
0
1.25
1
/
(
1
+
1.25
)
=
0.44
2.25
1.125
5.875
→
→
6
→
τ
3,2
,
τ
1,3
→


## 5. Correctness Proof

In this section, we prove the correctness of the schedules produced bylpWDA and PRA based on worst-case response time (WCRT) analysis and assume that the given task sets are feasible under preemptive RM scheduling. For the fixed-priority preemptive scheduling, a critical instant for a task τi is given by a moment in which the release time of τi coincides with all higher-priority tasks. Let WRi denote the WCRT of τi, without loss of generality, the higher-priority tasks have simultaneous release time with the job of τi.Lemma 3.
When a task setT contains only one task τγ, the available slack produced by lpWDA for τγ is
(19)slackγ(t)=dγ-t-wcγrem(t).Proof.
By (8), the amount of work required to be processed in interval [t,dγ) is
(20)loadγ(t)=wγrem(t).
According to (3), the available slack is derived as
(21)slackγ(t)=dγ-t-loadγ(t)=dγ-t-wγrem(t),
which completes the proof.InlpWDA, the slack derived from lower-priority task is given to the highest priority job in the readyQ. In the WCET case, after applying the slack to the highest priority job, the execution cycles of lower-priority jobs are postponed and their WCRTs will be increased in the length equal to that slack.Lemma 4.
When a task setT contains n tasks where n≥2, the amount of work required to be processed in [t,dα] (α≤n) for the highest priority job τα is
(22)loadα(t)=wnrem(t)+Hn(t)-(udn-dα).Proof.
Assuming thatT contains n tasks where n≥2, we prove that this lemma form the lowest priority task (i.e., τn) to the highest priority task using mathematical induction. The case of τn is proved separately because the third term of loadn(t) is different from those with α<n in (22). From (8), when τα is the lowest priority task (i.e., α=n), the workload of the tasks whose priorities lower than τn are zero (i.e., Ln(t)=0). Therefore, the amount of work required to be processed at time t is
(23)loadn(t)=wnrem(t)+Hn(t).
Because τn=udn before completing τn, we add (udn-τn) to (23) and derive
(24)loadn(t)=wnrem(t)+Hn(t)-(udn-dn),
and this completes the proof of τn.
Basic Step. First, we discuss the value of loadn-1(t) which can be estimated under two cases: udn(t)>dn-1 (Case  1) and udn(t)≤dn-1 (Case  2).
Case  1(udn(t)>dn-1). If udn(t) is later than dn-1, loadn(t) is greater than wn-1rem(t)+Hn-1(t), that is, the work in wn-1rem(t)+Hn-1(t) is the subset of the work in loadn(t). Let Δ=loadn(t)-wn-1rem(t)+Hn-1(t), if Δ≤udn(t)-dn-1, Δ amount of work can be processed in [dn-1, udn(t)], and only wn-1rem(t)+Hn-1(t) is required to be processed before dn-1. Otherwise, Δ-(udn(t)-dn-1) amount of work should be processed before dn-1. That is,
(25)Ln-1(t)=((udn(t)-dn-1)loadn(t)-wn-1rem(t)-Hn-1(t)-(udn(t)-dn-1))+,
where the notation x+ stands for max(x,0). Substituting (23) in the above equation, we get
(26)Ln-1(t)=([wnrem(t)+Hn(t)]-wn-1rem(t)-Hn-1(t)-(udn(t)-dn-1))+.
Substituting this result in loadn-1(t) defined in (8), we obtain
(27)loadn-1(t)=wn-1rem(t)-Hn-1(t)+[wnrem(t)+Hn(t)-wn-1rem(t)+Hn-1(t)-(udn(t)-dn-1)]+=wnrem(t)+Hn(t)-(udn(t)-dn-1).
Case  2
(
u
d
n
(
t
)
≤
d
n
-
1
). When udn(t) is earlier than dn-1, loadn(t) must be processed before dn-1. However, the value of loadn(t) does not change, and the value of loadn-1(t) is obtained as follows:
(28)Ln-1(t)=wnrem(t)+Hn(t).
Inductive Step. When task τ2 is considered, the value of load2(t) can be obtained as follows:
(29)load2(t)=(wnrem(t)+Hn(t)-(udn(t)-d2))+.
When we consider the task with the highest priority (i.e., τ1), the amount of work of its lower-priority task is
(30)L1(t)=(load2(t)-w1rem(t)-H1(t)-(ud2(t)-d1))+.
Substituting load2(t) in (30), we get
(31)L1(t)=[(wnrem+Hn(t)-(udn(t)-d2)]-w1rem(t)-H1(t)-(ud2(t)-d1))+.
When all tasks release at time t, we have ud2(t)=d2. Therefore, we get
(32)L1(t)=((udn(t)-d1)wnrem+Hn(t)-w1rem(t)-H1(t)-(udn(t)-d1))+.
By (8), substituting (32) in load1(t), we get
(33)load1(t)=w1rem(t)+H1(t)+L1(t)+w1rem(t)+H1(t)+[(udn(t)-d1)+wnrem+Hn(t)-w1rem(t)-H1(t)-(udn(t)-d1)+]=wnrem+Hn(t)-(udn(t)-d1).
The proof of Case  2 is similar to that of Case  1 and this completes the proof.Lemma 5.
The length of slack, that is, provided bylpWDA for the highest priority task in readyQ is at most
(34)slackα(t)=udn(t)-t-wnrem(t)-Hn(t).Proof.
Assuming thatτα has the highest priority in readyQ, this proof can be derived directly from (3), (19), and (22).The following theorem proves the schedulability oflpWDA by using worst-case response time analysis. We consider each active job τi in readyQ has a simultaneous release with all higher priority tasks.Theorem 6.
Given a setT of tasks is feasible in RM schedule, the maximum response time of task τγ under lpWDA is less than or equal to its deadline.Proof.
Assuming jobτα has the highest priority in readyQ. By (8), we get WRα=loadα at time t=0. Due to (3) proposed by lpWDA, the deadline of τα can be guaranteed by
(35)slackα(t)=dα-loadα,
when t=0. Therefore, we get
(36)WRα+slackα≤dα.
When τα runs out slackα, all of subsequent jobs of τα have to postpone their response times separately at most slackα unit of times comparing to those in their WCET RM schedule. Assuming τγ has lower priority than that of τα, we prove that the length of new WCRT of τγ including slackα is less than dγ. In a feasible RM schedule, the WCRT of τγ is
(37)WRγ≤wcγ+∑i<γ⌊pγpi⌋·wci.
The new WCRT of τγ considering the length of slackα is denoted as
(38)WRγnew=wcγ+∑i<γ‍⌊pγpi⌋·wci+slackα=wcγ+∑i<γ‍⌊pγpi⌋·wci+[dα-t-loadα(t)].
Based on (22) in Lemma 4 and set t=0, we derive
(39)WRγnew=wcγ+∑i<γ‍⌊pγpi⌋·wci+dα-[wcγ+Hγ(0)-udγ+dα]=∑i<γ⌊pγpi⌋·wci-Hγ(0)+udγ.
From the definitions of function Hγ(t) in (4) and (5), we derive
(40)WRγnew=∑i<γ‍⌊pγpi⌋·wci-[Hγpast+Hγfuture]+dγ=∑i<γ‍⌊pγpi⌋·wci-(∑i<γ‍wci+∑i<γ‍(⌊dγ-εpi⌋-1+1)·wci)+dγ=∑i<γ‍⌊pγpi⌋·wci-(∑i<γ‍(⌊dγ-εpi⌋+1)·wci)+dγ,
and ε is the infinitesimal. Because
(41)WRγnew=∑i<γ‍⌊pγpi⌋·wci≤∑i<γ‍(⌊dγ-εpi⌋+1)·wci,
we derive
(42)WRγnew≤dγ
from (40) and complete the proof.From (41) in Theorem 6, the difference between WRγnew and dγ is derived from the following corollary.Corollary 7.
For some tasksτi∈Tbn, i<γ and dγ=bn, and pγ is not the multiple of these pis; the difference between WRγnew and dγ is formulated as
(43)dγ-WRγnew=∑k<γ‍(⌊dγ-εpk⌋+1)·wck-∑k<γ‍⌊pγpk⌋·wck=∑τi∈Tbn‍wci.
Notably, WRγnew presents the length of WCRT proposed by lpWDA, and therefore the slack between WRγnew and dγ could be utilized by PRA.Consider the example shown in Figure4(a). The value of load3,1(0) is set to the sum of wc3 and H3,1(0) which is shown in the gray box of Figure 4(b). There are 6 time units that are required to be processed before ud3,1=8. In order to guarantee the feasible schedule of higher-priority jobs whose periods span astrideud3,1 (i.e., τ1,2 and τ2,2), lpWDA estimates how much time should be reserved for the higher-priority jobs. In this case, wc1,2+wc2,2=2 is derived from (43). We investigate the difference between dγ and WRγnew to keep the deadlines of PRA jobs.Lemma 8.
AlgorithmlpWDA selects an effective feasible speed for the active job in the analysis scope generated by upcoming deadlines.Proof.
Lemma8 is derived directly from Theorem 6 and Corollary 7.Lemma 9.
Letγ>δ, dγ=bn and τδ∈Tbn. When job τγ is feasible under PRA, τδ also keeps its deadline.Proof.
According to Theorem6, we have
(44)WRγnew≤dγ.
The WCRT of job τγ under PRA is changed to
(45)WRγPRA=WRγnew-wcδ+eminExchange.
By (45), the deadline of job τγ is still guaranteed by PRA. Additionally, the priority of job τδ is changed temporarily lower than τγ, and τδ executes immediately after wcγ. Therefore, the WCRT of job τδ is denoted as
(46)WRδPRA=WRδPRA+wcδ=WRδPRA+eminExchange≤dγ+eminExchange.
Due to the definition of ℓδright, we get
(47)dγ+eminExchange≤dγ+ℓδright
and complete the proof.Lemma9 proves that additional slack produced by PRA is shorter than the right part of pδ split by bn. Therefore, the deadline of job τδ is kept after changing the priority of τδ to the lowest priority in the readyQ. After completing τδ, the schedule is performed continuously under lpWDA. The schedulability proof in interval [bn,rn,k+1) is similar to Theorem 6 except additional workeExchange in the WCET schedule.Lemma 10.
AnlpWDA schedule remains feasible when eExchange unit of work is postponed to interval [bn,rγ,k+1) using PRA.Proof.
In the interval[bn,rγ,k+1), the critical instant appears in a situation that job τδ released before bn may remain incomplete at bn, while other tasks are released at bn. In accordance with (47), the maximum uncompleted work for job τδ at bn is eExchange. Let WRγ′ denote the WCRT of job τγ,k in the interval [bn,rγ,k+1) where γ>δ>α. According to (40) in Theorem 6, we have
(48)WRγ′=∑i<γ‍⌊pγpi⌋·wci-(∑i<γ‍(⌊dγ-εpi⌋+1)·wci)+dγ-wcδ+eExchange.
According to line 13 in algorithmPRA, the length of available slack is eExchange≤wcδ. From (48), the following statement still holds:
(49)∑i<γ‍⌊pγpi⌋·wci≤(∑i<γ‍(⌊dγ-εpi⌋+1)·wci)-wcδ+eExchange.
Therefore, we derive
(50)WRγ′≤dγ,k=rγ,k+1
which completes the proof.In fact, Procedure PRA focuses on providing the potential and available slack time to thelpWDA-based algorithms.Theorem 11.
Procedure  PRA provides additional slack that guarantees all task deadlines in the lpWDA.Proof.
In the interval [rn,k-1,bn), suppose job τα is being executed in [rn,k-1,bn). By executing line 9 in Algorithm 1 while passing the additional slack eExchange to the function CalcSlackTime() in the lpWDA algorithm, Algorithm 2 computes the length of the slack, which τα can use by calling the function CalcLowerPriorityWork() recursively. When job τα uses complete eExchange and all of its subsequent jobs execute in their WCET, job rn,k-1 is likely to miss its deadline. However, line 14 in Procedure PRA solves this problem by changing the priority of job τδ to the lowest priority job in readyQ. Because ℓδright≥eExchange, according to Lemma 9, the deadline of jobs τδ and τn is guaranteed in the interval [rn,k-1,bn).
In the interval[bn,rn,k+1), Procedure PRA computes the length of additional slack in [bn,rn,k+1). Given that τδ has been assigned to the lowest priority in readyQ, and all deadlines before the completion time of τδ are met. Based on the completion time of τδ, we divide it into two cases.
Case  1. Job τδ completes at time t≤ and t≤≤bn. In this case, the slack computed by Procedure PRA is not to be used by the jobs started before t≤. Because eExchange produced by Procedure PRA does not shift to the time before the bn, it has no influence on the job execution cycles after bn. Therefore, the initial lpWDA algorithm guarantees the deadline of jobs that started after the bn.
Case 2. Job τδ completes at time t> and t>>bn. When a scheduling point is at t>, the analysis scope defined in (2) is extended up to rn,k+1 by calling the Procedure CalcLowerPriorityWork() in Algorithm 3 recursively. In a feasible schedule, when slack eExchange has been exchanged on the left side of the bn and jobs before t> have been performed according to their WCET, the length of delayed work is not longer than eExchange. Therefore, the length of the additional work moved in interval [bn,rn,k+1) is at most eExchange. By Lemma 10, the additional work does not affect the feasibility of lpWDA schedule and completes the proof.


## 6.        Performance Evaluation

In this section, we evaluate the time and energy efficiency ofPRA scheme for randomly generated task sets and compare them with those of the ccRM, lpWDA and lpLDAT schemes. Both the ccRM and lpWDA are modified to account for transition time overhead. In simulations, lpWDA, and lpLDAT are called the host algorithms of PRA and cooperate with PRA to compare its performance with those of initial ccRM, lpWDA, and lpLDAT methods.


### 6.1. Complexity and Execution Time of Algorithms

Theorem 12.
ThePRA algorithm has a computational complexity of O(n) per scheduling point, where n denotes the number of tasks in the systems.Proof.
Lines 4 and 5 are completed in constant time for each iterative step according to (19) and (23). In line 8, the value of easynExchange is derived from (24)–(27), where the value of eiExchange(ℓ) in (27) needs O(n) time to compute the length of slack time. In line 10, the computation of ebn and eslack needs O(n) time. Therefore, the overall time complexity is O(n).In the simulation results, for any given pair oftotaltasks, U and bc/wc ratio in T, 10000 task sets are generated randomly. The experiment result is the average value over the 10000-task sets. In a task set, every task period pi (as well as deadline di) is uniformly distributed in the range [1,100] ms. The length of each schedule is at least ten times of its tasks hyperperiod except the fourth experiment in Section 6.2. Execution time wci of each task is assigned a real number in the range of [1, min{pi-1, 90}]ms. In a task set, after assigning values to the execution time of all tasks, we give a utilization U to the task set and rescale the pi of each task, such that the summation of task weights (i.e., wci/pi) equals the given U.Due to the limited execution speed of embedded processors, anLCM(Tb) function is implemented by offline nonrecursive programs. This function is composed of lcm(a,b) and gcd(a,b) which compute the least common multiplier (LCM) and greatest common divisor (GCD), respectively. In these programs, each integer is represented by a 32-bit word. Each experiment (schedule) has a maximum of 20 tasks, and each task has an integer variable for storing the period lengths of accumulated values of an LCM. Additionally, two integers are needed to record GCD and LCM of all task periods. Therefore, each schedule requires at most 100 bytes for storing data, which include local variables.In Figure5, we examine the execution time required by each online algorithm, including the following algorithms: ccRM: the ccRM algorithm from [7] is modified to account for transition overhead;lpWDA: the lpWDA algorithm from [6] is modified to account for transition overhead;lpLDAT: the algorithm from [12];lpWDA-PRA: the lpWDA is the host algorithm of PRA and cooperates with Procedure PRA;lpLDAT-PRA: the lpLDAT is the host algorithm of PRA and cooperates with Procedure PRA;lpWDA-DP-PRA: the lpWDA-DP is a host algorithm and cooperates with Procedure PRA;lpWDA-AC-PRA: the lpWDA-AC is a host algorithm and cooperates with Procedure PRA.Figure 5
Maximum execution time for the scheduling algorithms versus the number of tasks on a 100 MHz processor.Figure5 presents maximum execution time of each algorithm on a processor versus the number of tasks in the system. Notably, the simulation results produced by lpWDA-DP-PRA and lpWDA-AC-PRA are very close to those of lpWDA-PRA and lpLDAT-PRA, for a clear presentation of this figure, they are abridged. All algorithms executing on the simulated processor are based on ARM8 core with the highest speed (100 MHz) and voltage level. The measurement results were generated by inserting a system timer function and executing each algorithm individually. Obviously, ccRM has a significant advantage in terms of execution time when compared with that of the other online algorithms. Because the algorithms are invoked upon each release and completion, one must increase execution time of each task by two times the maximum execution time of the algorithm to account for scheduling overhead. To present the maximum execution times of these algorithms, the simulation process is as follows. First, a set of experiments performed Procedure PRA with its host algorithms (lpWDA and lpLDAT) and other initial algorithms. The functions of the system timer are used to record the duration of each algorithm, choose their longest execution times in each schedule, and accumulate execution times separately with respect to different methods. At experiment end, these accumulated execution times are divided by the number of schedules generated. PRA is an efficient online algorithm that increases in average additional execution time by less than 12% of those of their host algorithms.


### 6.2. Simulation Results

The following four parameters are varied in simulations: (1) number of taskstotaltasks in T is varied at 2–18 in two task increments; (2) utilization U for task set is varied at 0.1–0.9; (3) the bc/wc ratio of BCET to WCET is varied at 0.1–0.9; and (4) the analytical interval in bound being the multiples of pn is denoted as Mpnanalysis. Before performing these experiments, 10000 task sets have been generated randomly including the number of tasks in each set, task period lengths, and their worst-case execution requirements in accordance with a uniformed distribution function. Early completion time of each job in simulation (1), (2), and (4) was randomly drawn from a Gaussian distribution in the range of [BCET, WCET], where BCET/WCET = 0.1. In simulation (3), each experiment was performed by varying BCET at 10%–90% of WCET.For all experiments, we assume that 10 frequency levels are available in the range of 10–100 MHz, with corresponding voltage levels of 1–3.3 Volts. The energy consumption caused by memory access and cache misses are ignored, and all experimental results are normalized against the same processor running at maximum speed without a DVS technique (non-DVS for short). Table3 presents the power specification of the ARM8 processor [15].Table 3
Power specification.
Frequency
Voltage
Power
Sleep (idle)
0.8 V
<500μW
10 MHz
1.1 V
18 mW
20 MHz
1.2 V
32.3 mW
30 MHz
1.5 V
40.4 mW
40 MHz
1.8 V
56.5 mW
50 MHz
2.0 V
68.7 mW
60 MHz
2.3 V
86.9 mW
70 MHz
2.5 V
110 mW
80 MHz
2.7 V
137.5 mW
90 MHz
2.95 V
178 mW
100 MHz
3.3 V
220 mWThe overhead considered in simulations is as follows.(1)Algorithm Execution Time and Energy. The execution time overhead is referred to the simulation results in Figure 5. Energy overhead is obtained under the assumption of maximum speed Smax.(2)Voltage Transition Time and Energy. The assumption of voltage scaling overhead is the same with that in [17]. For the voltage scaling from Vdd1 to Vdd2, the transition time is
(51)Δt≈2·CImax·|Vdd2-Vdd1|,
where C and Imax the charge to the capacitor and maximum output current of the converter, respectively. Transition time is at most 70 μs between maximum transition [15]. The energy consumed during each transition is
(52)ΔE=n(1-λ)·C·|Vdd2-Vdd1|,
where λ denotes the efficiency of a DC-DC converter.(3)Context-Switch Time and Energy. Context-switch time is assumed 50 μs at the highest speed Smax, as in [18].Figures6, 7, 8, and 9 list the energy consumption of each method. Energy consumption includes both execution duration of PRA and its host algorithms (i.e., the lpWDA and lpLDA), and the context-switch time required to switch to and from other real-time tasks. Since the range of task periods has been shortened to a scale of [1,100] ms, the difference between task periods and context-switch times or transition times is smaller than those assumed in [6, 12]. Additionally, these energy overheads arose from PRA, and its host algorithms are also taken into account, such that the experimental results are close to actual situations. In these simulations, the host algorithms cooperating with PRA are better than its initial algorithms, respectively.Figure 6
Energy consumption under differenttotaltask.Figure 7
Energy consumption under differentU.Figure 8
Energy consumption under differentbc/wc ratio.Figure 9
Energy consumption under different values ofMpnanalysisFigures6, 7, 8, and 9 also present the results for a clairvoyant algorithm, named bound, which knows the actual execution cycle of each task beforehand and adopts the optimal speed accordingly. The length of analytical interval utilized by algorithm bound is set at least four times the length of pn except the fourth experiment in Figure 9. This setting ensures that bound’s analytical length is longer than those utilized by other methods and equal to the length of the schedules. Every scheduling point in the entire schedule is examined when looking for the best start and finish times. The context-switch and transition overhead assumed in the bound are the same as those with other methods while its execution time is assumed zero. In fact, bound is not a practical algorithm because it is extremely time consuming when finding the suitable start, preemption, and completion times, and no algorithm can predict the exact amount of job execution cycles beforehand. Thus, bound functions a yardstick in simulations because no real DVS algorithm can achieve better performance than that of bound.As shown in Figure6, the lpWDA-PRA and lpLDAT-PRA method, respectively, reduces the energy consumption by at least 12% and 4% over that of primitive lpWDA and lpLDAT. The energy efficiency of lpWDA-DP-PRA is between those of lpWDA-PRA and lpLDAT-PRA, while the energy efficiency of lpWDA-AC-PRA is 6%–3% worse than those of lpWDA-PRA and lpLDAT-PRA. The difference between lpWDA-AC-PRA and lpWDA-PRA is that lpWDA-AC in lower layer tries to schedule tasks with higher speed and leaves additional slack that PRA is unaware of. Therefore, this slack time becomes a fragment of slack time that is harmful to power saving. The following series of experiments almost reveal the phenomenon that the performance of lpWDA-AC-PRA is worse than those of lpWDA-PRA and lpWDA-DP-PRA. The value of U of each task set is assigned randomly at 10%–70% by uniform probability distribution function. The value of U and the bc/wc ratio for each task set are 0.8 and 0.5, respectively. With a large U, PRA outperforms its host algorithms in a small totaltask, consuming up to 25% and 24% less energy than lpWDA and lpLDAT, respectively. Although execution overhead of PRA is included, for a large totaltask, PRA still outperforms its host algorithms. The reason is likely that when the number of tasks increases, the number of task synchronization points appeared in the analytical interval likely decreases and benefits slack time computation.Experimental results in Figure7 indicate that lpWDA-PRA and lpLDAT-PRA saved up to 25% and 4% more energy than their host algorithms. Among lpWDA-based methods, although lpWDA-DP-PRA has the best performance, it slightly outperforms lpWDA-PRA. In other words, when PRA is applied in lpWDA, the delayed-preemption (DP) technique contributes little energy saving to the host methods. In the experiment, the totaltask and the bc/wc ratio of each task set are 10 and 0.5, respectively. Increasing the value of U in Figure 7 increases the energy consumption of PRA and its host algorithms. With a small U, the gain from PRA is modest, with 1% and 4% saving compared to that of the initial lpLDAT and lpWDA algorithms, respectively. Additionally, with these methods, U is an important factor when computing the slack for deciding processor speeds. With a moderate U value, lpWDA-PRA and lpLDAT-PRA consume at most 16% and 4% less energy than that of the initial lpWDA and lpLDAT algorithm, respectively. Therefore, PRA utilizes not only the advantages of its host algorithms but also slack belonging to the value of 1-U as possible and shifts the slack to the current job.In Figure8, the set of experiments varies the bc/wc ratio at 0.1–0.9, and the value of U and totaltask is 0.8 and 10, respectively. The energy consumed by PRA is positively correlated with the bc/wc ratio, while their hosts are not sensitive to the bc/wc ratio. In this experiment, lpWDA-DP-PRA still outperforms other lpWDA-based methods but not obviously. With a low bc/wc ratio, PRA is the best, consuming up to 26% and 16% less energy than the lpWDA and lpLDAT, respectively. With a bc/wc ratio of 0.9, PRA collaborated with lpLDAT which consumes slightly more energy than the initial lpLDAT algorithm. The reason is likely that the additional saving gained by the PRA algorithm is compromised by its execution overhead.In Figure9, the analytical interval in bound is exactly Mpnanalysis times the length of pn. The values of Mpnanalysis are controlled by the simulation from 2 to 18 and the totaltask of each task set is assigned randomly at 2 to 20 tasks. For simplicity, the length of each schedule is also controlled in Mpnanalysis×pn. When the value of Mpnanalysis increases, the energy saving of bound is not obvious, and the energy consumption required by the schemes with PRA are not sensitive to Mpnanalysis. Notably, when Mpnanalysis=2, PRA and bound have equal length of analytical interval; bound gains at most 33% energy savings less than the proposed schemes. Therefore, extending the additional analysis interval, such that it is several times longer than pn does not increase an already substantial energy saving but rather increases computing overhead during slack time analysis. There exist some limits and difficulties whenever extending analysis interval that is longer than two times of pn. Firstly, the length of the potential slack time is affected by the length of analytical interval, the values of Syn(Tf,k) and t(Tf,k), and by the locations of actual execution cycles of job. In Figure 3, the locations of the job workload affect the available length of slack time. Additionally, utilization of a task set influences the length of available slack time. For example, for a task set with high utilization, actual workload of many tasks may appear after t(Tf,k) where b=n or b=n-1 and cannot be exchanged with the slack. Therefore, the longer the analytical interval is, the harder the prediction of the length of additional slack becomes. For a longer interval than pn, we may need considerably more time and memory space than those required by PRA. Additionally, the length of a hyperperiod can vary from one to many times of pn as long as one task period is changed. When an analytical interval extends up to a hyperperiod, execution time required by algorithms may change severely and adversely affect the predictability of a real-time schedule.


## 6.1. Complexity and Execution Time of Algorithms

Theorem 12.
ThePRA algorithm has a computational complexity of O(n) per scheduling point, where n denotes the number of tasks in the systems.Proof.
Lines 4 and 5 are completed in constant time for each iterative step according to (19) and (23). In line 8, the value of easynExchange is derived from (24)–(27), where the value of eiExchange(ℓ) in (27) needs O(n) time to compute the length of slack time. In line 10, the computation of ebn and eslack needs O(n) time. Therefore, the overall time complexity is O(n).In the simulation results, for any given pair oftotaltasks, U and bc/wc ratio in T, 10000 task sets are generated randomly. The experiment result is the average value over the 10000-task sets. In a task set, every task period pi (as well as deadline di) is uniformly distributed in the range [1,100] ms. The length of each schedule is at least ten times of its tasks hyperperiod except the fourth experiment in Section 6.2. Execution time wci of each task is assigned a real number in the range of [1, min{pi-1, 90}]ms. In a task set, after assigning values to the execution time of all tasks, we give a utilization U to the task set and rescale the pi of each task, such that the summation of task weights (i.e., wci/pi) equals the given U.Due to the limited execution speed of embedded processors, anLCM(Tb) function is implemented by offline nonrecursive programs. This function is composed of lcm(a,b) and gcd(a,b) which compute the least common multiplier (LCM) and greatest common divisor (GCD), respectively. In these programs, each integer is represented by a 32-bit word. Each experiment (schedule) has a maximum of 20 tasks, and each task has an integer variable for storing the period lengths of accumulated values of an LCM. Additionally, two integers are needed to record GCD and LCM of all task periods. Therefore, each schedule requires at most 100 bytes for storing data, which include local variables.In Figure5, we examine the execution time required by each online algorithm, including the following algorithms: ccRM: the ccRM algorithm from [7] is modified to account for transition overhead;lpWDA: the lpWDA algorithm from [6] is modified to account for transition overhead;lpLDAT: the algorithm from [12];lpWDA-PRA: the lpWDA is the host algorithm of PRA and cooperates with Procedure PRA;lpLDAT-PRA: the lpLDAT is the host algorithm of PRA and cooperates with Procedure PRA;lpWDA-DP-PRA: the lpWDA-DP is a host algorithm and cooperates with Procedure PRA;lpWDA-AC-PRA: the lpWDA-AC is a host algorithm and cooperates with Procedure PRA.Figure 5
Maximum execution time for the scheduling algorithms versus the number of tasks on a 100 MHz processor.Figure5 presents maximum execution time of each algorithm on a processor versus the number of tasks in the system. Notably, the simulation results produced by lpWDA-DP-PRA and lpWDA-AC-PRA are very close to those of lpWDA-PRA and lpLDAT-PRA, for a clear presentation of this figure, they are abridged. All algorithms executing on the simulated processor are based on ARM8 core with the highest speed (100 MHz) and voltage level. The measurement results were generated by inserting a system timer function and executing each algorithm individually. Obviously, ccRM has a significant advantage in terms of execution time when compared with that of the other online algorithms. Because the algorithms are invoked upon each release and completion, one must increase execution time of each task by two times the maximum execution time of the algorithm to account for scheduling overhead. To present the maximum execution times of these algorithms, the simulation process is as follows. First, a set of experiments performed Procedure PRA with its host algorithms (lpWDA and lpLDAT) and other initial algorithms. The functions of the system timer are used to record the duration of each algorithm, choose their longest execution times in each schedule, and accumulate execution times separately with respect to different methods. At experiment end, these accumulated execution times are divided by the number of schedules generated. PRA is an efficient online algorithm that increases in average additional execution time by less than 12% of those of their host algorithms.


## 6.2. Simulation Results

The following four parameters are varied in simulations: (1) number of taskstotaltasks in T is varied at 2–18 in two task increments; (2) utilization U for task set is varied at 0.1–0.9; (3) the bc/wc ratio of BCET to WCET is varied at 0.1–0.9; and (4) the analytical interval in bound being the multiples of pn is denoted as Mpnanalysis. Before performing these experiments, 10000 task sets have been generated randomly including the number of tasks in each set, task period lengths, and their worst-case execution requirements in accordance with a uniformed distribution function. Early completion time of each job in simulation (1), (2), and (4) was randomly drawn from a Gaussian distribution in the range of [BCET, WCET], where BCET/WCET = 0.1. In simulation (3), each experiment was performed by varying BCET at 10%–90% of WCET.For all experiments, we assume that 10 frequency levels are available in the range of 10–100 MHz, with corresponding voltage levels of 1–3.3 Volts. The energy consumption caused by memory access and cache misses are ignored, and all experimental results are normalized against the same processor running at maximum speed without a DVS technique (non-DVS for short). Table3 presents the power specification of the ARM8 processor [15].Table 3
Power specification.
Frequency
Voltage
Power
Sleep (idle)
0.8 V
<500μW
10 MHz
1.1 V
18 mW
20 MHz
1.2 V
32.3 mW
30 MHz
1.5 V
40.4 mW
40 MHz
1.8 V
56.5 mW
50 MHz
2.0 V
68.7 mW
60 MHz
2.3 V
86.9 mW
70 MHz
2.5 V
110 mW
80 MHz
2.7 V
137.5 mW
90 MHz
2.95 V
178 mW
100 MHz
3.3 V
220 mWThe overhead considered in simulations is as follows.(1)Algorithm Execution Time and Energy. The execution time overhead is referred to the simulation results in Figure 5. Energy overhead is obtained under the assumption of maximum speed Smax.(2)Voltage Transition Time and Energy. The assumption of voltage scaling overhead is the same with that in [17]. For the voltage scaling from Vdd1 to Vdd2, the transition time is
(51)Δt≈2·CImax·|Vdd2-Vdd1|,
where C and Imax the charge to the capacitor and maximum output current of the converter, respectively. Transition time is at most 70 μs between maximum transition [15]. The energy consumed during each transition is
(52)ΔE=n(1-λ)·C·|Vdd2-Vdd1|,
where λ denotes the efficiency of a DC-DC converter.(3)Context-Switch Time and Energy. Context-switch time is assumed 50 μs at the highest speed Smax, as in [18].Figures6, 7, 8, and 9 list the energy consumption of each method. Energy consumption includes both execution duration of PRA and its host algorithms (i.e., the lpWDA and lpLDA), and the context-switch time required to switch to and from other real-time tasks. Since the range of task periods has been shortened to a scale of [1,100] ms, the difference between task periods and context-switch times or transition times is smaller than those assumed in [6, 12]. Additionally, these energy overheads arose from PRA, and its host algorithms are also taken into account, such that the experimental results are close to actual situations. In these simulations, the host algorithms cooperating with PRA are better than its initial algorithms, respectively.Figure 6
Energy consumption under differenttotaltask.Figure 7
Energy consumption under differentU.Figure 8
Energy consumption under differentbc/wc ratio.Figure 9
Energy consumption under different values ofMpnanalysisFigures6, 7, 8, and 9 also present the results for a clairvoyant algorithm, named bound, which knows the actual execution cycle of each task beforehand and adopts the optimal speed accordingly. The length of analytical interval utilized by algorithm bound is set at least four times the length of pn except the fourth experiment in Figure 9. This setting ensures that bound’s analytical length is longer than those utilized by other methods and equal to the length of the schedules. Every scheduling point in the entire schedule is examined when looking for the best start and finish times. The context-switch and transition overhead assumed in the bound are the same as those with other methods while its execution time is assumed zero. In fact, bound is not a practical algorithm because it is extremely time consuming when finding the suitable start, preemption, and completion times, and no algorithm can predict the exact amount of job execution cycles beforehand. Thus, bound functions a yardstick in simulations because no real DVS algorithm can achieve better performance than that of bound.As shown in Figure6, the lpWDA-PRA and lpLDAT-PRA method, respectively, reduces the energy consumption by at least 12% and 4% over that of primitive lpWDA and lpLDAT. The energy efficiency of lpWDA-DP-PRA is between those of lpWDA-PRA and lpLDAT-PRA, while the energy efficiency of lpWDA-AC-PRA is 6%–3% worse than those of lpWDA-PRA and lpLDAT-PRA. The difference between lpWDA-AC-PRA and lpWDA-PRA is that lpWDA-AC in lower layer tries to schedule tasks with higher speed and leaves additional slack that PRA is unaware of. Therefore, this slack time becomes a fragment of slack time that is harmful to power saving. The following series of experiments almost reveal the phenomenon that the performance of lpWDA-AC-PRA is worse than those of lpWDA-PRA and lpWDA-DP-PRA. The value of U of each task set is assigned randomly at 10%–70% by uniform probability distribution function. The value of U and the bc/wc ratio for each task set are 0.8 and 0.5, respectively. With a large U, PRA outperforms its host algorithms in a small totaltask, consuming up to 25% and 24% less energy than lpWDA and lpLDAT, respectively. Although execution overhead of PRA is included, for a large totaltask, PRA still outperforms its host algorithms. The reason is likely that when the number of tasks increases, the number of task synchronization points appeared in the analytical interval likely decreases and benefits slack time computation.Experimental results in Figure7 indicate that lpWDA-PRA and lpLDAT-PRA saved up to 25% and 4% more energy than their host algorithms. Among lpWDA-based methods, although lpWDA-DP-PRA has the best performance, it slightly outperforms lpWDA-PRA. In other words, when PRA is applied in lpWDA, the delayed-preemption (DP) technique contributes little energy saving to the host methods. In the experiment, the totaltask and the bc/wc ratio of each task set are 10 and 0.5, respectively. Increasing the value of U in Figure 7 increases the energy consumption of PRA and its host algorithms. With a small U, the gain from PRA is modest, with 1% and 4% saving compared to that of the initial lpLDAT and lpWDA algorithms, respectively. Additionally, with these methods, U is an important factor when computing the slack for deciding processor speeds. With a moderate U value, lpWDA-PRA and lpLDAT-PRA consume at most 16% and 4% less energy than that of the initial lpWDA and lpLDAT algorithm, respectively. Therefore, PRA utilizes not only the advantages of its host algorithms but also slack belonging to the value of 1-U as possible and shifts the slack to the current job.In Figure8, the set of experiments varies the bc/wc ratio at 0.1–0.9, and the value of U and totaltask is 0.8 and 10, respectively. The energy consumed by PRA is positively correlated with the bc/wc ratio, while their hosts are not sensitive to the bc/wc ratio. In this experiment, lpWDA-DP-PRA still outperforms other lpWDA-based methods but not obviously. With a low bc/wc ratio, PRA is the best, consuming up to 26% and 16% less energy than the lpWDA and lpLDAT, respectively. With a bc/wc ratio of 0.9, PRA collaborated with lpLDAT which consumes slightly more energy than the initial lpLDAT algorithm. The reason is likely that the additional saving gained by the PRA algorithm is compromised by its execution overhead.In Figure9, the analytical interval in bound is exactly Mpnanalysis times the length of pn. The values of Mpnanalysis are controlled by the simulation from 2 to 18 and the totaltask of each task set is assigned randomly at 2 to 20 tasks. For simplicity, the length of each schedule is also controlled in Mpnanalysis×pn. When the value of Mpnanalysis increases, the energy saving of bound is not obvious, and the energy consumption required by the schemes with PRA are not sensitive to Mpnanalysis. Notably, when Mpnanalysis=2, PRA and bound have equal length of analytical interval; bound gains at most 33% energy savings less than the proposed schemes. Therefore, extending the additional analysis interval, such that it is several times longer than pn does not increase an already substantial energy saving but rather increases computing overhead during slack time analysis. There exist some limits and difficulties whenever extending analysis interval that is longer than two times of pn. Firstly, the length of the potential slack time is affected by the length of analytical interval, the values of Syn(Tf,k) and t(Tf,k), and by the locations of actual execution cycles of job. In Figure 3, the locations of the job workload affect the available length of slack time. Additionally, utilization of a task set influences the length of available slack time. For example, for a task set with high utilization, actual workload of many tasks may appear after t(Tf,k) where b=n or b=n-1 and cannot be exchanged with the slack. Therefore, the longer the analytical interval is, the harder the prediction of the length of additional slack becomes. For a longer interval than pn, we may need considerably more time and memory space than those required by PRA. Additionally, the length of a hyperperiod can vary from one to many times of pn as long as one task period is changed. When an analytical interval extends up to a hyperperiod, execution time required by algorithms may change severely and adversely affect the predictability of a real-time schedule.


## 7. Conclusions

In this paper, we proposed the parareclamation algorithm (PRA) based on the concept of work-demand computation. This method can serve many existing RM scheduling methods as aguest algorithm. PRA cooperating with the host algorithms such as lpWDA, lpWDA-DP, lpWDA-AC, lpLDA, and lpLDAT can further decrease energy consumption without increasing time complexities. It is fully compatible not only with transition-aware (i.e., lpLDAT,) methods but also preemption-aware (i.e., lpWDA-AC and lpWDA-DP,) methods. Experimental results indicate that PRA can utilize the additional slack produced by lpWDA-AC and lpWDA-DP and reduce average energy consumption by 14% when compared with that of the initial schemes.



---

*Source: 581570-2013-08-18.xml*