Reliability-Aware Energy Management for Embedded Real-Time Systems with (m, k)-Hard Timing Constraint

Abstract

While energy consumption and Quality of Service (QoS) are primary concerns for the design of embedded systems, reliability requirement has become increasingly important in the development of today’s pervasive computing systems. In this paper, we present a reliability-aware energy management (RAEM) scheme for reducing the energy consumption for (m, k)-hard embedded real-time systems, which requires that at least m out of any k consecutive jobs of a real-time task meet their deadlines. In order to ensure the (m, k)-hard requirement while preserving the system reliability, we propose to reserve recovery space for real-time jobs in an adaptive way based on the mandatory/optional job partitioning strategy. Moreover, efficient off-line/online scheduling techniques are proposed to reduce the overall energy consumption while satisfying the reliability requirement. Through extensive simulations, our experiment results demonstrate that the proposed techniques significantly outperformed the previous research in reducing energy consumption for (m, k)-hard embedded real-time systems while preserving the system reliability.

Appendices

Appendix A: Proof for Theorem 2

Note that, in the following proof, to be concise, we assume that all recovery jobs of the mandatory jobs are “merged” into their corresponding primary jobs and each merged job is considered as a “whole” job. To be simple, we still call the merged whole jobs as mandatory jobs. Also since in the following we only consider mandatory jobs, for brevity, we also use job(s) to refer to mandatory job(s) when there is no confusion.

Before proving Theorem 2, we first prove the following lemma:

Lemma 3

Let $\mathcal {M}$ be the job set from $\mathcal {T}$ consisting of all the mandatory jobs according to E-pattern together with their recovery jobs in $\mathcal {X}$. Assume $\mathcal {M}$ is schedulalbe when all tasks are released synchronously at time 0. If the processor starts its execution at $t_{x} = \min (X_{j})$, j = 1, 2, ... , N, no mandatory job in $\mathcal {M}$ will miss its deadline.

Proof

We use contradiction. For ease of presentation, we use $\mathcal {J}(t_{1},t_{2})$ to represent the set of mandatory jobs with arrival times no earlier than t ₁ and with deadlines no later than t ₂. Meanwhile, we use W(t ₁, t ₂)to represent the total work demand within the interval [t ₁, t ₂] after delay. It is not hard to see that W(t ₁, t ₂) actually represents the work demand from jobs in $\mathcal {J}(t_{1},t_{2})$ after delay. Then for a given time interval [t _a , t _b ] and an arbitrary time point $\check {t}$ ($t_{a} \leq \check {t} \leq t_{b}$) in it, obviously, $\mathcal {J}$ $(t_{a},\check {t})\cup \mathcal {J}(\check {t},t_{b})\subseteq \mathcal {J}$ (t _a , t _b ). Correspondingly, we have,

$$ W(t_{a}, \check{t}) + W(\check{t}, t_{b}) \leq W(t_{a}, t_{b}) $$

(13)

Suppose after delay, some job J _k missed its deadline at d _k . Then we have

$$ W(t_{x}, d_{k}) > d_{k} - t_{x} $$

(14)

As we know, before delay, when all tasks start at time 0 synchronously, the total work demand before any time t is $({\sum }_{\tau _{x} \in \mathcal {X}} (\lceil \frac {(m_{x}+1)}{k_{x}} \lceil \frac {t-D_{x}}{T_{x}}\rceil ^{+} \rceil )\frac {C_{x}}{s_{x}} + {\sum }_{\tau _{y} \in \mathcal {Y}}$ $(\lceil \frac {m_{y}}{k_{y}} \lceil \frac {t-D_{y}}{T_{y}}\rceil ^{+} \rceil )C_{y})$. Since there is no deadline missing before delay, we have

$$\begin{array}{@{}rcl@{}} &&\left( \sum\limits_{\tau_{x} \in \mathcal{X}} \left( \lceil \frac{(m_{x}+1)}{k_{x}} \lceil \frac{d_{k}-D_{x}}{T_{x}}\rceil^{+} \rceil\right)\frac{C_{x}}{s_{x}}\right. \\&&\left.+ \sum\limits_{\tau_{y} \in \mathcal{Y}} \left( \lceil \frac{m_{y}}{k_{y}} \lceil \frac{d_{k}-D_{y}}{T_{y}}\rceil^{+} \rceil\right)C_{y}\right) + X_{k} \leq d_{k} \end{array} $$

(15)

On the other hand, after delay, the work demand between the interval [0, d _k ] cannot increase, so we have

$$\begin{array}{@{}rcl@{}} W(0, d_{k}) \leq &&\left( \sum\limits_{\tau_{x} \in \mathcal{X}} \left( \lceil \frac{(m_{x}+1)}{k_{x}} \lceil \frac{d_{k}-D_{x}}{T_{x}}\rceil^{+} \rceil\right)\frac{C_{x}}{s_{x}}\right. \\&&\left.+ \sum\limits_{\tau_{y} \in \mathcal{Y}} \left( \lceil \frac{m_{y}}{k_{y}} \lceil \frac{d_{k}-D_{y}}{T_{y}}\rceil^{+} \rceil\right)C_{y}\right) \end{array} $$

(16)

Meanwhile, from Eq. 13, we have

$$ W(0, t_{x}) + W(t_{x}, d_{k}) \leq W(0, d_{k}) $$

(17)

Since after delay W(0, t _x ) = 0, we have

$$\begin{array}{@{}rcl@{}} W(t_{x}, d_{k})\! \!\leq\! W(0, d_{k}) \!\leq\!\!\! &&\!\left( \sum\limits_{\tau_{x} \in \mathcal{X}} \!\left( \lceil \frac{(m_{x}+1)}{k_{x}} \lceil \frac{d_{k}-D_{x}}{T_{x}}\rceil^{+} \rceil\right)\frac{C_{x}}{s_{x}}\right.\\&& \left.+\! \sum\limits_{\tau_{y} \in \mathcal{Y}} \left( \lceil \frac{m_{y}}{k_{y}} \lceil \frac{d_{k}-D_{y}}{T_{y}}\rceil^{+} \rceil\right)C_{y}\right) \end{array} $$

(18)

In addition, by the definition of X _k and t _x , we have

$$ t_{x} \leq X_{k} $$

(19)

From the above Eqs. 15, 18, and 19, it is easy to get that, after delay

$$ W(t_{x}, d_{k}) \leq d_{k} - t_{x} $$

(20)

which contradicts to Eq. 14 □

Then we can move on to prove Theorem 2 based on Lemma 3. Assume the processor begins to idle at time t, we consider two cases:

• 1) The next mandatory jobs of all tasks arrive simultaneously at time t _a : If we let t _a = 0, the situation is the same as in Lemma 3. So no future mandatory job will miss its deadline.

• 2) The next mandatory jobs of all tasks does not arrive simultaneously: In this case let r _a be the earliest arrival time of all mandatory jobs. If we shift left all other tasks such that the arrival times of their next mandatory jobs coincide with r _a , it is easy to see that after such kind of shifting the task set will become harder to be schedulable than the original one as the work demand that is required to be finished before any deadline will not be decreased. On the other hand, it is easy to see that after shifting the situation is the same as in case 1). According to Lemma 3, the conclusion holds.

Appendix B: Proof for Theorem 3

Proof

Since it’s already proven in Appendix A that $\mathcal {J}$ could be delayed to t _s safely, we only need to prove that $\mathcal {J}$ could be delayed to $\tilde {T}_{LS}({\mathcal J}) = \min _{J_{i} \in {\mathcal J}_{s}} (d^{*}_{i} - {\sum }_{J_{k} \in hp(J_{i})}(\frac {c_{k}}{s_{k}}))$ without causing any deadline missing. Let $J_{n} \in {\mathcal J}_{s}$ and

$$ t_{LS}(J_{n})= d^{*}_{n} - \sum\limits_{J_{i} \in hp(J_{n})}\frac{c_{i}}{s_{i}}. $$

(21)

Since $\tilde {T}_{LS}({\mathcal J}) \leq t_{LS}(J_{n})$, therefore J _n and all the jobs with prioritieslower than that of J _n can meet their deadline. For any job J _i with priority higher than that of J _n , we consider two cases: (a) r _i < t _{p d} , (b) r _i ≥ t _{p d} . When r _i < t _{p d} , similarly as J _n , its schedulability is guaranteed. This also guarantees the schedulability for the jobs arriving later than t _{p d} with priorities higher than that of J _n but lower than that of J _i . Finally, for jobs arriving later than t _{p d} with priorities higher than that ofany job in ${\mathcal J}_{s}$, they must be schedulable since delaying the job set till t _{L S} (J _n ) ≤ t _{p d} has noimpact to their schedulability at all. □